2025/02/20 by Diakonikolas, Ilias, Iakovidis, Giannis, Kane, Daniel M. +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2502.14772
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.