Learning General Gaussian Mixtures With Efficient Score Matching
summary
Provides an algorithm that constructs a sampling oracle within epsilon total-variation for a k-component Gaussian mixture under well-conditioned covariances and bounded parameter radius, using d^{poly(k)} (condition-number)/epsilon samples and polynomial runtime. Key tools are a reduction from distribution learning to score matching via diffusion models, a structural proof that the score is approximable by piecewise-polynomial* functions, and a pipeline of PCA, crude clustering, and low-degree regression per cluster; improves runtimes for k = O(log d).
AI-written summary · about
chapters (13)
- 0:00Introduction
- 2:14Distribution learning focus
- 5:56Diffusion models and score basics
- 10:02Efficient score challenges
- 12:58Gaussian mixtures learning
- 14:27Main result for mixtures
- 16:18Score function structure
- 18:49Why naive fitting fails
- 24:08Piecewise polynomial score
- 26:20Clustering preprocessing
- 30:26Clustering algorithm design
- 32:19Full algorithm process
- 33:03Conclusion
related talks
29mApproximating Spherical Gaussian Mixtures
01h 31mUnsupervised Learning
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
44mMixture Models, Robustness, and Sum of Squares Proofs
52mLearning Mixture of Gaussians using Moment Tensor
20mInference of Probabilistic Programs with Moment-Matching Gaussian Mixtures
36mPrivately Learning High-Dimensional Distributions
01h 17mTowards Understanding Generalization Properties of Score-Based Losses