Mixture Models, Robustness, and Sum of Squares Proofs

2017/11/20 by Samuel B. Hopkins, Hopkins, Samuel B., Jerry Li +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Statistical Methods and Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1711.07454

openalex publication_date 2017/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that substantially improve upon the statistical guarantees achieved by previous efficient algorithms. Firstly, we study mixtures of k distributions in d dimensions, where the means of every pair of distributions are separated by at least k^ε. In the special case of spherical Gaussian mixtures, we give a (dk)^O(1/ε2)-time algorithm that learns the means assuming separation at least k^ε, for any ε > 0. This is the first algorithm to improve on greedy ("single-linkage") and spectral clustering, breaking a long-standing barrier for efficient algorithms at separation k^1/4. We also study robust estimation. When an unknown (1-ε)-fraction of X₁,…,X_n are chosen from a sub-Gaussian distribution with mean μ but the remaining points are chosen adversarially, we give an algorithm recovering μ to error ε^1-1/t in time d^O(t2), so long as sub-Gaussian-ness up to O(t) moments can be certified by a Sum of Squares proof. This is the first polynomial-time algorithm with guarantees approaching the information-theoretic limit for non-Gaussian distributions. Previous algorithms could not achieve error better than ε^1/2. Both of these results are based on a unified technique. Inspired by recent algorithms of Diakonikolas et al. in robust statistics, we devise an SDP based on the Sum of Squares method for the following setting: given X₁,…,X_n ∈ ℝ^d for large d and n = poly(d) with the promise that a subset of X₁,…,X_n were sampled from a probability distribution with bounded moments, recover some information about that distribution.

Citations

• Learning mixtures of separated nonspherical Gaussians
• Robust Estimation of a Location Parameter
• On the Convergence Properties of the EM Algorithm
• Robust principal component analysis?
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• Fast and robust tensor decomposition with applications to dictionary learning
• On the Bit Complexity of Sum-of-Squares Proofs

Cited by

• On the Learnability of Distribution Classes with Adaptive Adversaries

Related

• Robustly Learning any Clusterable Mixture of Gaussians
• Robustly Learning Mixtures of k Arbitrary Gaussians
• Robust Learning of Mixtures of Gaussians
• Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
• On Learning Mixtures of Well-Separated Gaussians