Research map / Learning theory and algorithms / Sample complexity
Robust Mixture Learning when Outliers Overwhelm Small Groups
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a two-stage meta-algorithm for list-decodable mixture learning that separates clusters with a multi-scale outer stage and runs list-decodable and robust mean estimation base learners in an inner stage, achieving near-optimal errors with list size k + O(ε/w_min).
Problem
Estimating the means of well-separated Gaussian or sub-Gaussian mixture components when the adversarial outlier fraction can exceed the weight of some small inlier clusters, so that outliers can crowd out and mimic small groups.
Approach
A meta-algorithm that first partitions the samples into a small collection of overlapping sets via a two-scale filtering outer stage (each containing at most one inlier cluster), then runs an agnostic list-decodable mean estimator with an unknown inlier fraction on each set, optionally refined by robust mean estimation for large clusters.
Key results
- Theoretical guarantee: list size k + O(ε/w_min) with error O(sqrt(log 1/w̃_i)) for Gaussian mixtures, matching information-theoretic lower bounds up to constants.
- In synthetic experiments (k=7, d=100, ε=0.12, w_min=0.02), the method outperforms LD-ME and is comparable or better than k-means, robust k-means, and DBSCAN across attack models.
- As w_min decreases, the proposed method's error stays roughly constant while LD-ME's error increases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the separated-mixture meta-algorithm instead of list-decodable mean estimation | List-decodable mixture learning · Small-weight separated Gaussian mixtures | mean estimation error: O\left(\sqrt{\log \frac{1}{\wmin}}\right) -> O\left(\sqrt{\log\frac{\epsilon + w_i}{w_i}}\right) | Helped |
| Use the separated-mixture meta-algorithm instead of list-decodable mean estimation | List-decodable mixture learning · Small-weight separated Gaussian mixtures | output list size: O(\frac{1}{\wmin}) -> k + O(\frac{\epsilon}{\wmin}) | Helped |
| Use the separated-mixture meta-algorithm instead of list-decodable mean estimation | List-decodable mixture learning · Non-separated mixtures | mean estimation error for component i: O\left(\sqrt{\log\frac{1}{\wmin}}\right) -> O\left(\sqrt{\log\frac{1}{w_i}}\right) | Helped |
| Use the proposed method instead of best prior work | List-decodable mixture learning · Large-weight separated Gaussian mixtures | mean estimation error: \widetilde O(\epsilon / w_i) -> \widetilde O(\epsilon / w_i) | No clear effect |
Surprising findings
- Under a uniform mixture with ε = w_i = 1/(k+1), prior LD-ME gives O(sqrt(log k)) error whereas the method gives O(1).
Limitations
- Theory requires well-separated means (distance ≳ sqrt(log 1/w_min)) for the main upper bound; no separation is needed only for a weaker result.
- Experiments are limited to synthetic data with identity covariances and an RME base learner omitted.
Experimental setup
Datasets: synthetic Gaussian mixtures in d=100
Benchmarks: synthetic separated Gaussian mixture with adversarial noise models
Metrics: worst-cluster estimation error at fixed list size minimal list size at fixed error
Baselines: LD-ME with alpha = w_min k-means Robust k-means DBSCAN
Builds on: list-decodable mean estimation robust mean estimation robust mixture learning
Closest papers by meaning
- Out-Of-Domain Unlabeled Data Improves Generalization (ICLR 2024 · similarity 0.84)
- Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness (NeurIPS 2024 · similarity 0.84)
- DOS: Diverse Outlier Sampling for Out-of-Distribution Detection (ICLR 2024 · similarity 0.83)
- RODEO: Robust Outlier Detection via Exposing Adaptive Out-of-Distribution Samples (ICML 2024 · similarity 0.83)
- Consistent Adversarially Robust Linear Classification: Non-Parametric Setting (ICML 2024 · similarity 0.83)
- A Subquadratic Time Algorithm for Robust Sparse Mean Estimation (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.