Mixture models, robustness, and sum of squares proofs

By Samuel B. Hopkins, Jerry Zheng Li. 2017

201 citations recorded by the source corpus.

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. Our contributions are: Mixture models with separated means: We study mixtures of poly(k)-many k-dimensional distributions 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 kO(1/ε)-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 k1/4. Robust estimation: When an unknown (1−ε)-fraction of X1,…,Xn 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 kO(t), 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. As a corollary, we achieve similar results for robust covariance estimation. 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 X1,…,Xn ∈ ℝk for large k and n = poly(k) with the promise that a subset of X1,…,Xn were sampled from a probability distribution with bounded moments, recover some information about that distribution.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “[27], Hopkins and Li [34], Klivans et al.”
Outlier-robust moment-estimation via sum-of-squares (2017, background): “We remark that in a concurrent and independent work, Hopkins and Li use similar ideas to learn mixtures of well-separated spherical Gaussians [HL17].”
High-Dimensional Robust Mean Estimation in Nearly-Linear Time (2018, methodology): “Can we speed-up the convex programs obtained via the SoS hierarchy in this setting [HL18, KSS18]?”
An Analysis of the t-SNE Algorithm for Data Visualization (2018, background): “…Vempala, 2007; Hsu and Kakade, 2013; Ge et al., 2015b; Kalai et al., 2012; Belkin and Sinha, 2010; Kalai et al., 2010; Kothari and Steinhardt, 2017; Hopkins and Li, 2017; Diakonikolas et al., 2017) have identiﬁed efﬁcient algorithms for clustering data from such models under various natural…”