Mixture models, robustness, and sum of squares proofs

DOI10.1145/3188745.3188748zbMATH Open1428.68240arXiv1711.07454OpenAlexW2962820675MaRDI QIDQ5230359FDOQ5230359

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)

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.

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

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

zbMATH Keywords

clusteringmixture modelshigh-dimensional statisticsrobust statisticsunsupervised learningsemidefinite programmingmixture of Gaussianssum-of-squares method

Mathematics Subject Classification ID

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

Cited In (20)

• Low rank approximation in the presence of outliers
• Title not available (Why is that?)
• Optimal estimation of Gaussian mixtures via denoised method of moments
• Mean estimation with sub-Gaussian rates in polynomial time
• Robust estimators in high-dimensions without the computational intractability
• Robust moment estimation and improved clustering via sum of squares
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• Qualitative robustness of von Mises statistics based on strongly mixing data
• A faster interior-point method for sum-of-squares optimization
• Mean estimation and regression under heavy-tailed distributions: A survey
• Graph powering and spectral robustness
• Partial recovery bounds for clustering with the relaxed \(K\)-means
• Robust estimation of mixing measures in finite mixture models
• Algorithms approaching the threshold for semi-random planted clique
• Learning polynomial transformations via generalized tensor decompositions
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• Robust PCA and clustering in noisy mixtures
• Optimal estimation of high-dimensional Gaussian location mixtures
• GAT–GMM: Generative Adversarial Training for Gaussian Mixture Models

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)