Structures Of Local Minima In K-Means And Mixture Models

on YouTube ↗51m

" summary

For two-component mixtures the population negative log-likelihood has exactly five stationary points and the only local minima correspond to the true centers, so EM and gradient methods converge from random initialization at geometric rates. For three-or-more components bad local minima provably exist but always take one-fit-many and many-fit-one forms (centers split or merge true components); results hold at the population level under a high-SNR separation and contrast k-means versus likelihood behavior.

AI-written summary · about

" chapters (7)

1. 0:00Intro
2. 0:45Background
3. 6:08Estimating Mixture Models
4. 17:11Mixture of Two Components Convergence Rate
5. 31:27Algorithmic Implications
6. 37:19Summary
7. 45:41Structures of Local Minima

" related talks

• 42mRobust Mixture Learning when Outliers Overwhelm Small GroupsFanny Yang · Joint IFML/MPG Symposium 2024
• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 28mCertified Sub-Linear Lower Bounds for K-Means ClusteringSoledad Villar · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 31mUnsupervised LearningSantosh Vempala · The Brain and Computation Boot Camp
• 44mA Modern Maximum-Likelihood Theory for High-Dimensional Logistic RegressionPragya Sur · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 40mIdentifying Mixture ModelsLeonard J. Schulman · Algorithmic Aspects of Causal Inference 2022
• 53mTensor Decompositions for Learning Latent Variable Models IIDaniel Hsu · Foundations of Machine Learning Boot Camp 2017
• 01h 06mNonparametric Bayesian Methods: Models, Algorithms, and Applications ITamara Broderick · Foundations of Machine Learning Boot Camp 2017