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

Ilias Diakonikolas; Giannis Iakovidis; Daniel M. Kane; Sihan Liu

cs.LGFeb 25, 2026

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

Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu

Organizations: UW Madison · UC San Diego

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.

Figures & tables

Distribution $D$	Upper bound	Lower bound $(d=1)$
$\mathcal{N}(0,I_{d})$	$\widetilde{O}\!\left(d\,e^{O\!\left((\alpha/\epsilon)^{2}\right)}\right)$	$\Omega\!\left(e^{\Omega\!\left((\alpha/\epsilon)^{2}\right)}\right)$
$\mathrm{Lap}_{d}(0,I_{d})$	$\widetilde{O}\!\left(d\,\alpha^{2}/\epsilon^{4}\right)$	$\Omega\!\left((\alpha/\epsilon)^{1/2}\right)$
$\mathrm{Unif}([-1,1])$	$\widetilde{O}\!\left(1/\epsilon\right)$	$\Omega\!\left((\alpha/\epsilon)^{1/6}\right)$
$\big(\mathrm{Unif}([-1,1])\big)^{*m}$	$\widetilde{O}\!\left(\alpha^{-2}\,(O(\alpha/\epsilon))^{2m}\right)$	$\Omega\!\left((\alpha/\epsilon)^{(2m-1)/6}\right)$

Table 1: Sample complexity for mean estimation under

\alpha

-mean-shift contamination.

Robust Mean Estimation

See all 10 papers

High-Dimensional Gaussian Mean Estimation under Realizable Contamination
Mar 17, 2026Ilias Diakonikolas, Daniel M. Kane, Thanasis PittasData Contamination Statistical Learning Theory
University of Wisconsin-Madison · University of California, San Diego
High-Dimensional Robust Mean Estimation with Untrusted Batches
Feb 24, 2026Maryam Aliakbarpour, Vladimir Braverman, Yuhan Liu +1Robust Mean Estimation Robust Estimation
Department of Computer Science, Ken Kennedy Institute, Rice University. · Johns Hopkins University. · Rice University.
Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
Feb 26, 2026Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis +2Query Identifiability
Yale University · Stanford University · IMC Trading

Mar 17, 2026J/K move · Enter open · S save

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

University of Wisconsin-Madison · University of California, San Diego

Data Contamination Statistical Learning Theory

Open paper AskPDF arXiv

We study mean estimation for a Gaussian distribution with identity covariance in

\mathbb{R}^d

under a missing data scheme termed realizable

ε

-contamination model. In this model an adversary can choose a function

r(x)

between 0 and

ε

and each sample

x

goes missing with probability

r(x)

. Recent work Ma et al., 2024 proposed this model as an intermediate-strength setting between Missing Completely At Random (MCAR) -- where missingness is independent of the data -- and Missing Not At Random (MNAR) -- where missingness may depend arbitrarily on the sample values and can lead to non-identifiability issues. That work established information-theoretic upper and lower bounds for mean estimation in the realizable contamination model. Their proposed estimators incur runtime exponential in the dimension, leaving open the possibility of computationally efficient algorithms in high dimensions. In this work, we establish an information-computation gap in the Statistical Query model (and, as a corollary, for Low-Degree Polynomials and PTF tests), showing that algorithms must either use substantially more samples than information-theoretically necessary or incur exponential runtime. We complement our SQ lower bound with an algorithm whose sample-time tradeoff nearly matches our lower bound. Together, these results qualitatively characterize the complexity of Gaussian mean estimation under

ε

-realizable contamination.

Abstract

Robust Mean Estimation

Explore similar work

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

High-Dimensional Robust Mean Estimation with Untrusted Batches

Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms