Agnostic Estimation of Mean and Covariance

By Kevin A. Lai, Anup B. Rao, Santosh Srinivas Vempala. 2016

375 citations recorded by the source corpus.

We consider the problem of estimating the mean and covariance of a distribution from i.i.d. samples in the presence of a fraction of malicious noise. This is in contrast to much recent work where the noise itself is assumed to be from a distribution of known type. The agnostic problem includes many interesting special cases, e.g., learning the parameters of a single Gaussian (or finding the best-fit Gaussian) when a fraction of data is adversarially corrupted, agnostically learning mixtures, agnostic ICA, etc. We present polynomial-time algorithms to estimate the mean and covariance with error guarantees in terms of information-theoretic lower bounds. As a corollary, we also obtain an agnostic algorithm for Singular Value Decomposition.

Subfields: Artificial Intelligence, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Stronger data poisoning attacks break data sanitization defenses (2018, background): “7b) design robust classication algorithms that avoid the poor dimension-dependence of traditional estimators, although only under strong distributional assumptions such as log-concavity. Separately, Lai et al. (2016) and Diakonikolas et al. (2016) designed robust procedures for mean estimation, whic”
Spectral Signatures in Backdoor Attacks (2018, background): “Another line of work focuses on applying the robust statistics tools developed in [8, 22, 5, 9] to robust stochastic optimization problems [2, 5, 10, 17, 27].”
Byzantine Stochastic Gradient Descent (2018, background): “Recently, efficient algorithms for high dimensional optimization which are tolerant to a small fraction of adversarial corruptions have been developed [1, 7, 11, 16, 24], building on new algorithms for high dimensional robust statistics [5, 7, 9, 18].”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “In the context of unsupervised learning, two concurrent works [DKK + 16, LRV16] gave the ﬁrst provably robust and eﬃciently computable estimators for several basic high-dimensional unsupervised tasks, including robust mean and covariance estimation.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “…much progress has been made recently in terms of improved performance in high-dimensional problems (Bhatia et al., 2015, Diakonikolas et al., 2016, Lai et al., 2016) as well as developing list-decodable and semi-veriﬁed learning schemes when a majority of the data points are adversarial (Charikar…”
Certified Defenses for Data Poisoning Attacks (2017, methodology): “Robust algorithms have been exhibited for mean and covariance estimation and clustering (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017), classiﬁcation (Klivans et al., 2009; Awasthi et al., 2014), regression (Nasrabadi et al., 2011; Nguyen and Tran, 2013; Chen et al., 2013;…”
Distributed Statistical Machine Learning in Adversarial Settings (2017, background): “A recent line of work [8, 15] presents polynomial algorithms to consistently estimate the mean and covariance of a distribution from N i.”
Learning Discrete Distributions from Untrusted Batches (2017, background): “These recent works include [LRV16, DKK + 16, DKK + 17] who consider the problem of robustly estimating the mean and covariance of high-dimensional Gaussians (and other distributions such as product distributions), and [SVC16] who consider a sparse ratings aggregation setting.”
Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, background): “The error rate of most of these aggregation algorithms depends on the dimensionality of their inputs [31], [17], [16].”
Robust Estimators in High Dimensions without the Computational Intractability (2016, background): “In contrast, by virtue of being close in total variation distance, our estimates for the mean and covariance are within Õ(ε √‖Σ‖2) and Õ(ε‖Σ‖2) of the true values, again measured in 2 norm and Frobenius norm respectively.”
Being Robust (in High Dimensions) Can Be Practical (2017, methodology): “On this data, we compared the performance of our Filter algorithm to that of (1) the empirical mean of all the points, (2) a trivial pruning procedure, (3) the geometric median of the data, (4) a RANSAC-based mean estimation algorithm, and (5) a recently proposed robust estimator for the mean due to”
A Data Prism: Semi-verified learning in the small-alpha regime (2018, background): “Recent works from the TCS community tackled this general problem in several basic settings, including robustly estimating the mean and covariance of natural classes of distribution, including multivariate Gaussians (Diakonikolas et al., 2016; Lai et al., 2016).”
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, background): “Recent work in the TCS community made the first algorithmic progress on this front: Two contemporaneous works [13, 37] gave the first computationally efficient robust algorithms for learning high-dimensional Gaussians (and many other high-dimensional models) with error close to the information-theor”
Robust Federated Learning in a Heterogeneous Environment (2019, background): “There is a recent line of work on robust mean estimation that adapts nicely to high dimension [37, 38].”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, methodology): “[LRV16] and later improvements [DKK + 17, SCV18] show how to estimate the mean of an unknown distribution (with bounded second moments) where an ε fraction of points are adversarially corrupted, obtaining additive error O √ ε .”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, background): “Robust optimization Robust optimization has received a renewed impetus following the works in [10, 22, 7].”
High-Dimensional Robust Mean Estimation in Nearly-Linear Time (2018, methodology): “Since the dissemination of [DKK + 16, LRV16], there has been a ﬂurry of research activity on robust learning algorithms in both supervised and unsupervised settings [BDLS17, CSV17, DKK + 17, DKS17, DKK + 18a, SCV18, DKS18b, DKS18a, HL18, KSS18, PSBR18, DKK + 18b, KKM18, DKS19, LSLC18, CDKS18].”