List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians

Original · EN

We study the problem of list-decodable Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. We develop a set of techniques that yield new efficient algorithms with significantly improved guarantees for these problems. List-Decodable Mean Estimation. Fix any d ∈ Z+ and 0< α<1/2. We design an algorithm with runtime O (poly(n/α)ᵈ) that outputs a list of O(1/α) many candidate vectors such that with high probability one of the candidates is within ℓ₂-distance O(α⁻¹/⁽²ᵈ⁾) from the true mean. The only previous algorithm for this problem achieved error O(α⁻¹/²) under second moment conditions. For d = O(1/ε), our algorithm runs in polynomial time and achieves error O(αε). We also give a Statistical Query lower bound suggesting that the complexity of our algorithm is qualitatively close to best possible. Learning Mixtures of Spherical Gaussians. We give a learning algorithm for mixtures of spherical Gaussians that succeeds under significantly weaker separation assumptions compared to prior work. For the prototypical case of a uniform mixture of k identity covariance Gaussians we obtain: For any ε>0, if the pairwise separation between the means is at least Ω(kε+√(1/δ)), our algorithm learns the unknown parameters within accuracy δ with sample complexity and running time poly (n, 1/δ, (k/ε)¹/ε). The previously best known polynomial time algorithm required separation at least k¹/⁴ polylog(k/δ). Our main technical contribution is a new technique, using degree-d multivariate polynomials, to remove outliers from high-dimensional datasets where the majority of the points are corrupted.