Robust Mixture Learning when Outliers Overwhelm Small Groups
summary
Claims an algorithm that attains order-optimal error for each mixture mean while keeping the extra output size minimal, provably requiring list size about k + Θ(ε / w_low) and per-mean error on the order of √(log(1 / w_i)) (with standard Gaussian / sub-Gaussian assumptions). Method first leverages separation to partially cluster samples, then runs list-decodable mean estimation at multiple scales as a black box. Empirically the implementation matches common heuristics and sometimes loses to DBSCAN but provides theoretical guarantees.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:28Robustness objectives
- 3:58Preserving minority groups
- 8:35Gaussian mixture problem
- 13:00List decodable learning
- 17:16Tradeoffs in small groups
- 23:27Algorithm design
- 30:34Guarantees for cases
- 34:59Theoretical analysis
- 40:51Summary
- 41:15Q&A
related talks
44mMixture Models, Robustness, and Sum of Squares Proofs
01h 31mUnsupervised Learning
29mApproximating Spherical Gaussian Mixtures
17mTowards Practical Algorithms for Outlier-Robust Estimation
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
17mSelf-Training Converts Weak Learners to Strong Learners in Mixture Models
45mHigh Dimensional Robust Sparse Regression
01h 12mRecent Progress in High-Dimensional Learning