The Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
summary
Polynomial-time algorithm uses the Sum-of-Squares framework to robustly cluster non‑spherical k‑Gaussian mixtures with adversarially corrupted epsilon fraction of samples and outputs 99% accurate clustering up to the unavoidable k·epsilon error; runtime is astronomical but polynomial in d (roughly d^{k^{O(k)}} for constant k). The method certifiably exploits analytic properties—certifiable hypercontractivity and anti‑concentration—to handle mean, spectral, and relative‑Frobenius separations, including subspace‑clustering cases where TV distance is one.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:48Algorithm Problem
- 5:52The Problem
- 12:34Mandatory Motivations
- 13:37Argument
- 16:57Proof
- 17:42Separation
- 19:34Spectral Separation
- 21:56Pairwise TV Separation
- 23:15Parameter Separation
- 26:16Sources
- 27:01Open Questions
related talks
29mApproximating Spherical Gaussian Mixtures
44mMixture Models, Robustness, and Sum of Squares Proofs
35mLearning General Gaussian Mixtures With Efficient Score Matching
01h 31mUnsupervised Learning
01h 00mAlgorithmic High Dimensional Robust Statistics I
40mThe Hidden Convexity of Spectral Clustering
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
39mAbove Average-Case Analysis?