# Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination

arXiv: https://arxiv.org/abs/2502.14772 · HTML: https://mlsanity.com/paper/2502.14772/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 59 references that are in the map.
- First posted on arXiv 20 Feb 2025.

## Builds on (most cited first, 24 of 24)

- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [How Does Unlabeled Data Provably Help Out-of-Distribution Detection?](https://mlsanity.com/paper/2402.03502/) (2024)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Optimal estimation of the null distribution in large-scale inference](https://mlsanity.com/paper/2401.06350/) (2024)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Learning Entangled Single-Sample Distributions via Iterative Trimming](https://mlsanity.com/paper/2004.09563/) (2020)
- [On Mean Estimation for Heteroscedastic Random Variables](https://mlsanity.com/paper/2010.11537/) (2020)
- [Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances](https://mlsanity.com/paper/2312.02417/) (2023)
- [Estimating minimum effect with outlier selection](https://mlsanity.com/paper/1809.08330/) (2018)
- [Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model](https://mlsanity.com/paper/2007.05557/) (2020)
- [Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation](https://mlsanity.com/paper/2312.11769/) (2023)
- [Entangled Mean Estimation in High-Dimensions](https://mlsanity.com/paper/2501.05425/) (2025)
- [A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm](https://mlsanity.com/paper/2305.00966/) (2023)

## Built on by (most cited first, 6 of 6)

- [EXACT: Explicit Attribute-Guided Decoding-Time Personalization](https://mlsanity.com/paper/2602.17695/) (2026)
- [Revisiting Active Sequential Prediction-Powered Mean Estimation](https://mlsanity.com/paper/2604.18569/) (2026)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)
- [Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination](https://mlsanity.com/paper/2602.22130/) (2026)
- [Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model](https://mlsanity.com/paper/2604.26992/) (2026)
- [Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination](https://mlsanity.com/paper/2510.10665/) (2025)

## Abstract (arXiv)

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 ℝd generated i.i.d. via the following process. For a parameter α<1/2, the i-th sample xi is obtained as follows: with probability 1-α, xi is drawn from N(μ, I), where μ ∈ ℝd is the target mean; and with probability α, xi is drawn from N(zi, I), where zi is unknown and potentially arbitrary. Prior work characterized the information-theoretic limits of this task. Specifically, it was shown that, in contrast to Huber contamination, in 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.