Research map / Learning theory and algorithms / Sample complexity
Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first polynomial-time, sample-near-optimal algorithm for high-dimensional Gaussian mean estimation under mean-shift contamination with a constant fraction of outliers, via iterative reweighted second-moment dimension reduction followed by a brute-force estimator on a O(1/eps^2)-dimensional subspace.
Problem
Robust mean estimation of an identity-covariance Gaussian under mean-shift contamination, where outliers are N(z_i, I) with arbitrary z_i; prior efficient algorithms were lacking, and prior exact estimators required exponential time in dimension.
Approach
Iteratively reduce dimension using a reweighted, exponentially-truncated non-centered second moment matrix (weights exp(-||x||^2 gamma)) whose expectation for inliers is proportional to mu mu^T, keeping eigenvectors with large eigenvalues; once dimension is O(1/eps^2), run a sample-polynomial brute-force LP-based estimator on the projected data.
Key results
- Algorithm uses n = d*polylog(d)*eps^{-(2+o(1))} + 2^{O(1/eps^2)} polylog(d) samples and poly(n,d) time to output mu-hat with ||mu-hat - mu|| <= eps with probability 0.99 for alpha <= 0.49.
- The estimator does not need to know alpha, and extends to alpha in (0, 1/2 - c) with mild increase in error and sample complexity.
- Dimension reduction halves dimension each round, with O(log d) rounds in phase 1 and O(log(log(d)/eps)) rounds in phase 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed dimension-reduction algorithm followed by the low-dimensional estimator | Multivariate robust mean estimation under mean-shift contamination · Mean-shift contamination (α ≤ 0.49) | runtime: 2^{O(d)}\poly(n, d) -> \poly(n, d) | Helped |
| use the proposed algorithm | Multivariate robust mean estimation under mean-shift contamination · Mean-shift contamination (α ≤ 0.49) | sample complexity: n = \tilde{O}(d/\epsilon^{2+o(1)} + 2^{O(1/\epsilon^2)}) | Helped |
Surprising findings
- Standard Huber-model robust estimators cannot achieve error below Omega(alpha), so consistency is achieved only by exploiting the mean-shift structure.
Limitations
- Known covariance Gaussian only; unknown covariance and non-Gaussian inliers remain open.
- Sample complexity still exponential in 1/eps^2 (2^{O(1/eps^2)}), matching information-theoretic lower bound in 1D but costly in practice.
- Final estimation step is brute-force exponential in the reduced dimension O(1/eps^2).
Experimental setup
Metrics: sample complexity runtime l2 estimation error
Baselines: brute-force exponential-time estimator for mean-shift model Huber-model robust estimators (error Omega(alpha))
Builds on: Mean-shift contamination 1D estimators (Kotekal and Gao type minimax results) Matrix Bernstein inequality Huber contamination robust mean estimation
Closest papers by meaning
- Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination (ICML 2026 · similarity 0.93)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.89)
- All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance (ICML 2025 · similarity 0.86)
- A Subquadratic Time Algorithm for Robust Sparse Mean Estimation (ICML 2024 · similarity 0.85)
- The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination (NeurIPS 2025 · similarity 0.85)
- Robust Estimation Under Heterogeneous Corruption Rates (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.