A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance

Abstract

We study the algorithmic problem of robust Gaussian mean estimation in the mean-shift contamination model with unknown covariance. Specifically, we are allowed to draw samples from a statistical mixture of an unknown target Gaussian 𝒩(μ, Σ) (with weight at least 1-α), and arbitrary unknown mean-shifts of it, i.e., 𝒩(μ_i, Σ)_i, and the goal is to estimate μ up to any desired accuracy ϵ in ℓ_2-norm. In the special case where Σ is known to be the identity, prior work gave an algorithm with a near-optimal sample complexity of poly(d,2^ϵ^-2) and sample-polynomial time. In this work, we provide a quasi-polynomial time algorithm with sample complexity 2^poly(log d/ϵ) in the more general unknown covariance case, markedly improving upon the only previously known estimator for this setting that incurs exponential runtime.