Approximating Spherical Gaussian Mixtures
summary
Proves an algorithmic pipeline that learns mixtures of spherical Gaussians with no separability or weight assumptions and near–optimal sample scaling: previous bounds that scale like d^k collapse to roughly d log^2 d times a polynomial in k (information-theoretic lower bound is Θ(dk/ε^2)). One-dimensional case uses a Cheffé-style estimator (combinatorial, sample-optimal). High-dimensional method projects to the span of means via PCA + recursive clustering, uses random matrix concentration to control covariance noise, and yields polynomial-time recovery (≈d^3 times poly(k)) with explicit ε dependence.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:32Recap
- 1:42Uber distribution
- 3:51Uber-2.0 distribution
- 6:12Previous results
- 9:20Duck test
- 9:59PAC learning
- 15:13Slightly complicated
- 15:28Quantization using samples
- 17:04Mixtures k-2
- 20:37Motivation for algorithm
- 22:13Spectral projection
- 22:50Variance of the mixture vs. variance of the components
- 23:50Algorithm outline
- 25:27Corollaries for parameter learning
- 26:15Summary and challenges
related talks
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
01h 31mUnsupervised Learning
35mLearning General Gaussian Mixtures With Efficient Score Matching
44mMixture Models, Robustness, and Sum of Squares Proofs
01h 14mRecent Progress in High-Dimensional Learning
52mLearning Mixture of Gaussians using Moment Tensor
01h 30mAnalytic Methods for Supervised Learning IV
42mRobust Mixture Learning when Outliers Overwhelm Small Groups