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

Ilias Diakonikolas, Giannis Iakovidis, Daniel Kane, Sihan Liu
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:24702-24723, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-diakonikolas26a, title = {Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination}, author = {Diakonikolas, Ilias and Iakovidis, Giannis and Kane, Daniel and Liu, Sihan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {24702--24723}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/diakonikolas26a/diakonikolas26a.pdf}, url = {https://proceedings.mlr.press/v306/diakonikolas26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination %A Ilias Diakonikolas %A Giannis Iakovidis %A Daniel Kane %A Sihan Liu %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-diakonikolas26a %I PMLR %P 24702--24723 %U https://proceedings.mlr.press/v306/diakonikolas26a.html %V 306 %X 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.
APA
Diakonikolas, I., Iakovidis, G., Kane, D. & Liu, S.. (2026). Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:24702-24723 Available from https://proceedings.mlr.press/v306/diakonikolas26a.html.

Related Material