Agnostic Estimation of Mean and Covariance

2016/04/24 by Lai, Kevin A., Rao, Anup B., Vempala, Santosh · 11 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1604.06968

Abstract

We consider the problem of estimating the mean and covariance of a distribution from iid samples in ℝⁿ, in the presence of an η 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 η fraction of data is adversarially corrupted, agnostically learning a mixture of Gaussians, 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.

Cited by

• Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
• Robust and Sparse Estimation of Unbounded Density Ratio under Heavy Contamination
• High-Accuracy List-Decodable Mean Estimation
• Watermark Robustness and Radioactivity May Be at Odds in Federated Learning
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
• Agnostic Product Mixed State Tomography via Robust Statistics
• Linear Regression under Missing or Corrupted Coordinates
• Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates
• On the Learnability of Distribution Classes with Adaptive Adversaries
• Robust Estimation Under Heterogeneous Corruption Rates
• Adversarially robust multiple testing in high dimensions

Related

• Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
• How Hard Is Robust Mean Estimation?
• Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• Robustly Learning a Gaussian: Getting Optimal Error, Efficiently