Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination

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