Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Ilias Diakonikolas, Giannis Iakovidis, Daniel Kane, Thanasis Pittas
Abstract
We study the algorithmic problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. In this contamination model, we are given a set of points in R d generated i.i.d. via the following process. For a parameter α < 1/2, the i-th sample x i is obtained as follows: with probability 1 -α, x i is drawn from N (µ, I), where µ ∈ R d is the target mean; and with probability α, x i is drawn from N (z i , I), where z i is unknown and potentially arbitrary. Prior work characterized the informationtheoretic limits of this task. Specifically, it was shown that-in contrast to Huber contaminationin the presence of mean-shift contamination consistent estimation is possible. On the other hand, all known robust estimators in the mean-shift model have running times exponential in the dimension. Here we give the first computationally efficient algorithm for high-dimensional robust mean estimation with mean-shift contamination that can tolerate a constant fraction of outliers. In particular, our algorithm has near-optimal sample complexity, runs in sample-polynomial time, and approximates the target mean to any desired accuracy. Conceptually, our result contributes to a growing body of work that studies inference with respect to natural noise models lying in between fully adversarial and random settings.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination cites How Does Unlabeled Data Provably Help Out-of-Distribution Detection?
- Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination cites Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms
- Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression cites Clustering mixture models in almost-linear time via list-decodable mean estimation
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination cites Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression
- Clustering mixture models in almost-linear time via list-decodable mean estimation cites Robustly learning mixtures of k arbitrary Gaussians
Cited by top-tier papers4
- Revisiting Active Sequential Prediction-Powered Mean EstimationMaria-Eleni Sfyraki, Jun-Kun WangICLR 2026 · 4 citations
- Learning Mixture Models via Efficient High-Dimensional Sparse Fourier TransformsAlkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis ZampetakisSTOC 2026 · 1 citation
- Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift ContaminationIlias Diakonikolas, Giannis Iakovidis, Daniel Kane, Sihan LiuICML 2026
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious ContaminationIlias Diakonikolas, Chao Gao, Daniel Kane, John D. Lafferty et al.NeurIPS 2025
Builds on8
- Meta-learning for Mixed Linear RegressionWeihao Kong, Raghav Somani, Zhao Song, Sham M. Kakade et al.ICML 2020 · 70 citations
- How Does Unlabeled Data Provably Help Out-of-Distribution Detection?Xuefeng Du, Zhen Fang, Ilias Diakonikolas, Yixuan LiICLR 2024 · 39 citations
- Robustly learning mixtures of k arbitrary GaussiansAinesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane et al.STOC 2022 · 21 citations
- Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear RegressionIlias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis PittasNeurIPS 2023 · 9 citations
- Clustering mixture models in almost-linear time via list-decodable mean estimationIlias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li et al.STOC 2022 · 6 citations
Related papers
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber ContaminationIlias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Ankit Pensia et al.ICML 2024 · 1 citation
- Outlier Robust Mean Estimation with Subgaussian Rates via StabilityIlias Diakonikolas, Daniel M. Kane, Ankit PensiaNeurIPS 2020 · 76 citations
- The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive ContaminationClément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu et al.FOCS 2023 · 1 citation
- Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication TimeJerry Li, Guanghao YeNeurIPS 2020 · 13 citations
- Streaming Algorithms for High-Dimensional Robust StatisticsIlias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis PittasICML 2022 · 25 citations
