Unsupervised Learning
summary
Proven results and concrete limits: polynomial algorithms recover Gaussian-mixture parameters but sample complexity currently blows up with number of components (information lower bound 2^K and many methods need N^K), and two-Gaussian 1‑D recovery uses random projection plus matching a finite number of moments (six moments suffices for two). Spherical or isotropically whitened mixtures yield practical algorithms via isotropic PCA with reweighting when each mean is separated from the span of the rest. ICA is identifiable (up to sign/ordering) if at most one source is Gaussian. Planted-clique detection succeeds spectrally for k = Ω(√n) via spectral embedding (top eigenvector) but faster algorithms for smaller k remain open. Robust/agnostic results exist (mean estimation degrades proportionally to noise rate η), and many methods extend to streaming or small-noise models, though worst‑case hardness and stability gaps persist.
AI-written summary · about
chapters (8)
- 0:00Introduction to unsupervised
- 3:55Methodologies and goals
- 5:30Mixture models
- 18:56Principal component analysis
- 35:18Independent component analysis
- 43:27Finding planted structures
- 54:21Graph clustering
- 1:10:27Advanced topics and research
related talks
29mApproximating Spherical Gaussian Mixtures
35mLearning General Gaussian Mixtures With Efficient Score Matching
01h 30mAnalytic Methods for Supervised Learning IV
49mSpectral Algorithms for Learning Latent Variable Models
52mIndependent Component Analysis: From Theory to Practice and Back
52mLearning Mixture of Gaussians using Moment Tensor
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
44mMixture Models, Robustness, and Sum of Squares Proofs