Mixture Models, Robustness, and Sum of Squares Proofs
Talkat Robust and High-Dimensional Statistics (Simons Institute workshop, 2018) · 2018-10-29..11-02·
summary
Gives an efficient pipeline using the Sum of Squares hierarchy to find bounded high-moment subsets and then recover parameters. For mixtures of K Gaussians with identity-bounded covariances, an algorithm works when separation Δ = K^ε (any fixed ε>0), runs in time and samples D^{O(1/ε^2)}, and outputs means to polynomial-in-1/K accuracy; pushing to Δ ≈ √log K needs quasi-polynomial time. For robust mean estimation, SOS yields error ε^{1−1/t} assuming T-bounded moments, implemented via an SDP and rounding.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:26Topics
- 1:09Mixture Models
- 4:11Output Hypothesis
- 10:03Robustness
- 17:15Empirical Bounded Teeth
- 25:16Two Simple Facts
- 30:09Recap
- 30:51Sum of Squares Paradigm
- 32:26Finding Subsets
- 39:46Open Questions
related talks
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
29mApproximating Spherical Gaussian Mixtures
52mLearning Mixture of Gaussians using Moment Tensor
35mLearning General Gaussian Mixtures With Efficient Score Matching
42mRobust Mixture Learning when Outliers Overwhelm Small Groups
01h 31mUnsupervised Learning
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
01h 00mAlgorithmic High Dimensional Robust Statistics I