Monte Carlo Approximation Certificates for K-Means Clustering

on YouTube ↗40m

" summary

Shows that a semi-definite relaxation of k‑means yields a verifiable certificate: compute an SDP solution, derive a dual certificate (reduced to an eigenvalue test), and if it is dual‑feasible then the delivered clustering is provably optimal. Under a stochastic ball model (disjoint unit balls) the SDP is tight with high probability when centers are separated beyond ~2, and the certificate test runs via power method with arbitrarily high confidence. Empirically SDP is slow; a faster certify‑then‑accept pipeline (PCC) recovers strong signal and denoises Gaussian mixtures.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:40The k-means problem
3. 2:25Lloyd's algorithm
4. 4:37An alternative: SDP relaxation
5. 10:47Faster certified clustering?
6. 17:13Preliminaries
7. 21:12The big idea (Afonso Bandeira)
8. 25:14A small technicality
9. 26:42It works, and it's fast!
10. 28:16Guarantee for random problem instances
11. 32:05When does SDP recover planted clustering?
12. 34:25What about outliers?
13. 39:30How to explain denoising?
14. 39:57Questions?

" related talks

• 37mPower to the Points: Local Certificates for ClusteringsSuresh Venkatasubramanian · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 51mExact Recovery via Convex RelaxationsMoses Charikar · Spectral Algorithms: From Theory to Practice 2014
• 40mClustering Under Perturbation ResilienceColin White · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian MixturesPravesh K. Kothari · Computational Phase Transitions (Simons Institute, 2020)
• 42mk-means and k-medians under Dimension ReductionYury Makarychev · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 04mFrom Proofs to Algorithms for Machine Learning ProblemsDavid Steurer · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 35mClustering: A Guide for the PerplexedLeland McInnes, John Healy · PyData DC 2016