Mixture models, robustness, and sum of squares proofs

DOI10.1145/3188745.3188748MaRDI QIDQ5230359zbMATH OpenOpenAlexFDO

Authors Samuel B. Hopkins, Jerry Li

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.07454

zbMATH Keywords

clusteringhigh-dimensional statisticsmixture modelsmixture of Gaussiansrobust statisticssemidefinite programmingsum-of-squares methodunsupervised learning

Mathematics Subject Classification ID

Robustness and adaptive procedures (parametric inference) (62F35) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that substantially improve upon the statistical guarantees achieved by previous efficient algorithms. Firstly, we study mixtures of $k$ distributions in $d$ dimensions, where the means of every pair of distributions are separated by at least $k^{varepsilon}$. In the special case of spherical Gaussian mixtures, we give a $(dk{)}^{O(1/varepsilo{n}^2)}$-time algorithm that learns the means assuming separation at least $k^{varepsilon}$, for any $varepsilon>0$. This is the first algorithm to improve on greedy ("single-linkage") and spectral clustering, breaking a long-standing barrier for efficient algorithms at separation $k^{1/4}$. We also study robust estimation. When an unknown $(1-varepsilon)$-fraction of $X_1,ldots,X_n$ are chosen from a sub-Gaussian distribution with mean $mu$ but the remaining points are chosen adversarially, we give an algorithm recovering $mu$ to error $varepsilo{n}^{1-1/t}$ in time $d^{O(t^2)}$, so long as sub-Gaussian-ness up to $O(t)$ moments can be certified by a Sum of Squares proof. This is the first polynomial-time algorithm with guarantees approaching the information-theoretic limit for non-Gaussian distributions. Previous algorithms could not achieve error better than $varepsilo{n}^{1/2}$. Both of these results are based on a unified technique. Inspired by recent algorithms of Diakonikolas et al. in robust statistics, we devise an SDP based on the Sum of Squares method for the following setting: given $X_1,ldots,X_{n}inmathbb{R}^d$ for large $d$ and $n=poly(d)$ with the promise that a subset of $X_1,ldots,X_n$ were sampled from a probability distribution with bounded moments, recover some information about that distribution.

Recommendations

• Robust moment estimation and improved clustering via sum of squares
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• Efficiently learning mixtures of two Gaussians
• A spectral algorithm for learning mixture models
• Learning mixtures of separated nonspherical Gaussians

Cited in

(28)

• Mean estimation with sub-Gaussian rates in polynomial time
• Optimal estimation of Gaussian mixtures via denoised method of moments
• Robust estimation of mixing measures in finite mixture models
• Partial recovery bounds for clustering with the relaxed K-means
• Mean estimation and regression under heavy-tailed distributions: A survey
• Qualitative robustness of von Mises statistics based on strongly mixing data
• Robust PCA and clustering in noisy mixtures
• Robust estimators in high-dimensions without the computational intractability
• Low rank approximation in the presence of outliers
• Graph powering and spectral robustness
• Trace reconstruction: generalized and parameterized
• Robust moment estimation and improved clustering via sum of squares
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• GAT–GMM: Generative Adversarial Training for Gaussian Mixture Models
• Optimal estimation of high-dimensional Gaussian location mixtures
• A faster interior-point method for sum-of-squares optimization
• Sum-of-squares lower bounds for densest k-subgraph
• Learning polynomial transformations via generalized tensor decompositions
• Algorithms approaching the threshold for semi-random planted clique
• Robust and computationally efficient gradient-based estimation
• Distributionally robust optimization and robust statistics
• Mixtures of Gaussians are privately learnable with a polynomial number of samples
• Polynomial-time sum-of-squares can robustly estimate mean and covariance of Gaussians optimally
• Robustly learning general mixtures of Gaussians
• Adaptive robust confidence intervals
• Robustly learning mixtures of k arbitrary Gaussians
• A Fourier analytic approach to Gaussian mixture learning

This page was built for publication: Mixture models, robustness, and sum of squares proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230359)