Learning Mixture of Gaussians using Moment Tensor
summary
Provides a polynomial-time, polynomial-sample algorithm that recovers parameters of a smoothed mixture of K general Gaussians by converting folded empirical moments into unfolded moment tensors and applying tensor decomposition, works under random perturbations of parameters and outputs the perturbed means, covariances, and weights. Key tools are linear systems on projected 4th and 6th moments, span recovery from tensor slices, and robust matrix sensing, it uses 3rd, 4th and 6th moments and requires n >> K^2 (constants ≈100 in the paper).
AI-written summary · about
chapters (10)
- 0:00The crab problem
- 3:31Method of moments limitations
- 6:06High-dimensional advantages
- 12:25Smooth analysis framework
- 17:10Algorithm overview
- 20:17Tensors and moments
- 25:41Matrix sensing approach
- 30:30Finding covariance spans
- 36:42Algorithm reconstruction
- 42:48Conclusion and discussion
related talks
49mSpectral Algorithms for Learning Latent Variable Models
44mMixture Models, Robustness, and Sum of Squares Proofs
53mTensor Decompositions for Learning Latent Variable Models II
52mTensor Methods for Learning Latent Variable Models: Theory and Practice
01h 31mUnsupervised Learning
29mApproximating Spherical Gaussian Mixtures
01h 11mTensor Decompositions: Uniqueness and Smoothed Analysis
54mLearning Overcomplete Latent Variable Models through Tensor Power Method