Source-linked AI summary
Agnostic Estimation of Mean and Covariance
Kevin A. Lai, Anup B. Rao, Santosh Vempala
TL;DR
The paper asks how to estimate means and covariances when an η fraction of samples is arbitrary rather than drawn from a known noise distribution. It develops polynomial-time robust estimators with near-information-theoretic guarantees and derives agnostic SVD and ICA results. The approach applies to Gaussian and broader bounded-moment settings, though one proposed improvement lacks a proof and ICA requires restrictive moment, conditioning, and noise assumptions.
Problem
Estimating means and covariances from iid data is fundamental, but classical estimators are highly sensitive to arbitrary adversarial noise.
Method
The paper develops polynomial-time mean and covariance estimators for contaminated distributions, using transformed quadratic samples for covariance estimation.
Results
The algorithms achieve errors close to information-theoretic limits and yield agnostic SVD, with applications including noisy ICA.
Takeaways & Limitations
The framework extends agnostic parameter estimation beyond Gaussians to general bounded-moment and Bernoulli product distributions, and supports agnostic ICA.
Takeaways & Limitations
The improved η-dependence procedure for higher moments is not proved, while the ICA guarantee requires restrictive moment, conditioning, and noise bounds.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies estimating means and covariances under arbitrary adversarial noise, addressing limitations of exact-model assumptions and computationally expensive or weakly guaranteed robust methods. It gives polynomial-time algorithms with error guarantees near information-theoretic limits and applies them to agnostic SVD, ICA, and related distributions.
- Problem: Arbitrary malicious noise makes classical sample mean and covariance estimators highly sensitive, motivating agnostic estimation of distribution parameters.The model allows an η fraction of samples to be chosen arbitrarily by an adversary.
- Motivation: Exact-model assumptions limit generative-model algorithms, while prior robust methods were often exponential-time or lacked strong output guarantees.The paper frames arbitrary-noise estimation as an important open problem, including robust Gaussian estimation.
- Mean estimation: Polynomial-time mean-estimation algorithms achieve dimension dependence only √log n and errors close to information-theoretic optima.The bounds are nearly optimal up to O(√log n) when covariance is a multiple of the identity.
- Generalizations: The algorithms extend beyond Gaussians to general bounded-moment distributions and noisy Bernoulli product distributions, with nearly linear sample complexity for mean estimation.The framework also supports higher moments and improves η dependence for non-spherical Gaussian mean estimation when η < c/log n.
- Covariance estimation: The paper provides polynomial-time covariance estimation under bounded fourth-moment and affine 4-wise-independence assumptions.The covariance result uses transformed quadratic samples and yields sample and error bounds stated in the main theorem.
- Applications: Agnostic SVD follows as a covariance-estimation corollary, enabling an agnostic ICA algorithm that tolerates η = O(1/log^c n) noise.The ICA result is presented as the first polynomial-time algorithm known to handle more than inverse-polynomial noise.
2 Main Ideas
The paper’s algorithms combine outlier control with recursive spectral projections to estimate means, covariances, operator norms, and related decompositions under arbitrary noise. The approach extends from spherical and nonspherical Gaussians to bounded-fourth-moment distributions and applications such as ICA.
- Mean estimation: AgnosticMean alternates outlier removal with projection onto the top n/2 principal components, recursively reducing the mean-estimation problem to one dimension.The final one-dimensional step uses the median.
- Gaussian extensions: For nonspherical Gaussians, damping downweights distant points instead of discarding them, while an auxiliary routine estimates the covariance scale needed for filtering.The damping strategy limits the effect of adversarial points when covariance is not spherical.
- General distributions: Bounded-fourth-moment distributions require truncation because outlier damping does not work; the moment condition controls changes in mean and covariance after conditioning.The resulting mean estimator supports substantially more general distributions than the Gaussian case.
- Covariance estimation: Covariance estimation reduces to mean estimation in n^2 dimensions by treating (x − µ)(x − µ)^T as a vector of second moments.The covariance identity is used after estimating the mean.
- Applications: The agnostic SVD and ICA applications use robust covariance estimates to obtain eigenspaces or isotropic transformations before subsequent spectral processing.The covariance-estimation guarantee controls the additional error in these downstream procedures.
- Lower-bound intuition: Two-point versus three-point constructions show that bounded fourth moments alone cannot support arbitrarily strong robustness to adversarial contamination.The second distribution is obtained from the first by adding an η fraction of noise points.
3 Mean Estimation: Theorem 1.1 and Theorem 1.3
The paper develops polynomial-time mean estimators for Gaussian and bounded-fourth-moment distributions by combining robust one-dimensional estimation, recursive projections, and outlier control. The guarantees improve on geometric-median dimension dependence and can improve further in spherical or suitably conditioned cases.
- Algorithmic framework: The recursive mean-estimation algorithm uses O(log n) levels, with sample-based concentration and VC-dimension bounds controlling the estimates at each level.The analyzed functions are low-degree polynomials restricted to intervals or balls, enabling inverse-polynomial sampling error.
- Gaussian mean estimation: In one dimension, the sample median estimates the mean under Gaussian contamination with error O((η + ǫ)σ) with high probability.This one-dimensional guarantee supplies the base case for the recursive procedure.
- Gaussian mean estimation: The multidimensional procedure uses medians in orthogonal directions, weighted covariance structure, and recursive projection to recover the mean-shift direction despite adversarial principal components.The top n/2 eigenspace retains a substantial projection of the mean shift, while the complementary space can use a projected sample mean.
- Gaussian mean estimation: For spherical covariance Σ = σ^2I, matching spectral scales cancels the leading term in the mean-estimation bound and yields better dependence on η.The improvement follows because the largest and smallest covariance eigenvalues coincide.
- Improved dependence on η: Adding isotropic Gaussian noise and reapplying the estimator provides a polynomial-time route to improved η dependence for nonspherical Gaussian mean estimation.The transformed distribution preserves the mean while adding a multiple of the identity to the covariance.
- General distributions: For bounded-fourth-moment distributions, outlier truncation and mean-shift bounds control the surviving sample’s bias, yielding the stated polynomial-time AgnosticMean guarantee.The analysis assumes bounded fourth moments and a sufficiently small retained contamination level.
4 Covariance Estimation
Covariance estimation is reduced to robust mean estimation on matrix-valued second moments, with separate one-dimensional variance procedures and a bounded-fourth-moment reduction. This produces a polynomial-time covariance estimator under adversarial contamination.
- One-dimensional covariance: In one dimension, the paper gives polynomial-time variance estimators for Gaussian distributions and for distributions satisfying bounded fourth-moment conditions.The Gaussian and general-moment cases receive separate guarantees.
- Multidimensional covariance: The covariance matrix is estimated by applying mean estimation to outer products of symmetrized samples, which reduces covariance estimation to robust mean estimation.The symmetrization uses differences of independent samples and preserves the target covariance up to the stated transformation.
- Multidimensional covariance: The transformed outer-product distribution has bounded fourth moments with parameter at most C4 + 3/2, while the new sample has at most twice the average contamination fraction.These properties permit invoking the bounded-moment mean-estimation theorem.
- Multidimensional covariance: Proposition 4.2 bounds the operator norm of the covariance of the outer-product random variable, supplying the scale needed for the final covariance guarantee.The proposition is combined with the mean-estimation reduction to prove Theorem 1.5.
5 Estimating ∥Σ∥2: Theorem 1.6
AgnosticOperatorNorm estimates the largest covariance eigenvalue by repeatedly identifying directions where empirical variance exceeds the estimated clean variance and removing points with large projections. The analysis establishes polynomial termination under a small-contamination condition.
- Algorithm and assumptions: AgnosticOperatorNorm assumes one-dimensional concentration and uses directional variance estimates to distinguish covariance energy from adversarial projections.The algorithm is analyzed for samples containing both clean points and adversarial points.
- Clean-data control: Truncation regions preserve all but an inverse-polynomial fraction of clean probability mass, and the covariance of the conditioned distribution remains close to the original covariance.The construction uses O(n) directional constraints and concentration across orthogonal directions.
- Guarantee: At termination, the retained sample’s covariance satisfies the theorem’s upper and lower operator-norm bounds, using the termination condition and accurate directional variance estimates.The lower bound follows from the surviving clean sample; the upper bound uses the top eigenvector of the retained covariance.
- Runtime: Each iteration removes a certain number of noise points, yielding polynomial termination when η is at most a sufficiently small inverse-logarithmic quantity in n.The analysis further shows termination in a nearly linear number of iterations under the stated condition.
Open Questions
The paper leaves open whether its mean-estimation analysis is tight, whether the √log n dependence can be removed, and whether optimal η-dependence is achievable for general distributions.
- The analysis of the mean-estimation algorithm may not be tight, leaving it open whether the √log n dependence can be avoided.
- For general distributions, the information-theoretic lower bound is η^3/4, but achieving O(η^3/4) error remains open.
- Other open problems include agnostic learning of mixtures of two arbitrary Gaussians and agnostic sparse recovery.