Agnostic Estimation of Mean and Covariance
This addresses robust statistical estimation for applications like learning Gaussian parameters under adversarial corruption, but it is incremental as it builds on prior work in agnostic settings.
The paper tackles the problem of estimating the mean and covariance of a distribution from i.i.d. samples in ℝⁿ with an η fraction of adversarial noise, presenting polynomial-time algorithms that achieve error guarantees matching information-theoretic lower bounds.
We consider the problem of estimating the mean and covariance of a distribution from iid samples in $\mathbb{R}^n$, 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.