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

clusteringmomentsrobust learningsum-of-squares

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

(26)

• Robust \(k\)-means clustering for distributions with two moments
• Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
• Mean estimation with sub-Gaussian rates in polynomial time
• Mean estimation and regression under heavy-tailed distributions: A survey
• Robust estimators in high-dimensions without the computational intractability
• scientific article; zbMATH DE number 7378399 (Why is no real title available?)
• Graph powering and spectral robustness
• Sum-of-squares bounds via Boolean function analysis
• Robust M-Estimation Based Bayesian Cluster Enumeration for Real Elliptically Symmetric Distributions
• Mixture models, robustness, and sum of squares proofs
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• Sum of Squares Bounds for the Empty Integral Hull Problem
• 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
• Outlier robust and sparse estimation of linear regression coefficients
• Tight sum-of-squares lower bounds for binary polynomial optimization problems
• Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination
• Clustering a mixture of Gaussians with unknown covariance
• Mixtures of Gaussians are privately learnable with a polynomial number of samples
• Algebraic and analytic approaches for parameter learning in mixture models
• Robustly learning general mixtures of Gaussians
• SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
• Robustly learning mixtures of k arbitrary Gaussians

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)