Robust moment estimation and improved clustering via sum of squares

DOI10.1145/3188745.3188970MaRDI QIDQ5230360zbMATH OpenOpenAlexFDO

Authors Pravesh Kothari, Jacob Steinhardt, David Steurer

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://doi.org/10.1145/3188745.3188970

zbMATH Keywords

momentsclusteringsum-of-squaresrobust learning

Mathematics Subject Classification ID

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

Recommendations

• Mixture models, robustness, and sum of squares proofs
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• Efficiently learning mixtures of two Gaussians
• Robust \(k\)-means clustering for distributions with two moments
• A spectral algorithm for learning mixture models

Cited in

(16)

• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
• Robust M-Estimation Based Bayesian Cluster Enumeration for Real Elliptically Symmetric Distributions
• Mean estimation with sub-Gaussian rates in polynomial time
• Robust estimators in high-dimensions without the computational intractability
• Robust \(k\)-means clustering for distributions with two moments
• Mixture models, robustness, and sum of squares proofs
• Sum-of-squares bounds via Boolean function analysis
• scientific article; zbMATH DE number 7378399 (Why is no real title available?)
• Sum of Squares Bounds for the Empty Integral Hull Problem
• Mean estimation and regression under heavy-tailed distributions: A survey
• Graph powering and spectral robustness
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• 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
• Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence

This page was built for publication: Robust moment estimation and improved clustering via sum of squares

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