Name
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. 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 e . In the special case of spherical Gaussian mixtures, we give a k O (1/e) -time algorithm that learns the means assuming separation at least k e , for any eu003e 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 . Robust estimation: When an unknown (1−e)-fraction of X 1 ,…, 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 e 1−1/ t in time k O ( 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 e 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 X 1 ,…, X n ∈ ℝ k for large k and n = poly( k ) with the promise that a subset of X 1 ,…, X n were sampled from a probability distribution with bounded moments, recover some information about that distribution. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3188745.3188748 | STOC '18: Symposium on Theory of Computing
Los Angeles
CA
USA
June, 2018 |
Keywords | Field | DocType |
Unsupervised learning,clustering,mixture models,mixture of Gaussians,robust statistics,high-dimensional statistics,sum of squares method,semidefinite programming | Discrete mathematics,Combinatorics,Estimation of covariance matrices,Computer science,Robustness (computer science),Robust statistics,Probability distribution,Gaussian,High-dimensional statistics,Explained sum of squares,Mixture model | Journal |
Volume | ISSN | ISBN |
abs/1711.07454 | 0737-8017 | 978-1-4503-5559-9 |
Citations | PageRank | References |
9 | 0.54 | 51 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Hopkins | 1 | 88 | 9.47 |
| Jerry Li | 2 | 229 | 22.67 |