# Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 25 Feb 2026.

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

- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [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)
- [How Does Unlabeled Data Provably Help Out-of-Distribution Detection?](https://mlsanity.com/paper/2402.03502/) (2024)
- [Optimal estimation of the null distribution in large-scale inference](https://mlsanity.com/paper/2401.06350/) (2024)
- [Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination](https://mlsanity.com/paper/2502.14772/) (2025)
- [Estimating minimum effect with outlier selection](https://mlsanity.com/paper/1809.08330/) (2018)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)

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

- [Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model](https://mlsanity.com/paper/2604.26992/) (2026)

## Abstract (arXiv)

We study the basic task of mean estimation in the presence of mean-shift contamination. In the mean-shift contamination model, an adversary is allowed to replace a small constant fraction of the clean samples by samples drawn from arbitrarily shifted versions of the base distribution. Prior work characterized the sample complexity of this task for the special cases of the Gaussian and Laplace distributions. Specifically, it was shown that consistent estimation is possible in these cases, a property that is provably impossible in Huber's contamination model. An open question posed in earlier work was to determine the sample complexity of mean estimation in the mean-shift contamination model for general base distributions. In this work, we study and essentially resolve this open question. Specifically, we show that, under mild spectral conditions on the characteristic function of the (potentially multivariate) base distribution, there exists a sample-efficient algorithm that estimates the target mean to any desired accuracy. We complement our upper bound with a qualitatively matching sample complexity lower bound. Our techniques make critical use of Fourier analysis, and in particular introduce the notion of a Fourier witness as an essential ingredient of our upper and lower bounds.