Lattice-Based Methods Surpass Sum-of-Squares in Clustering
2. července 2022
Řečníci
Min Jae Song
Sprecher:in · 0 Follower:innen
Ilias Zadik
Sprecher:in · 0 Follower:innen
Joan Bruna
Sprecher:in · 4 Follower:innen
O prezentaci
Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canonical task of clustering d-dimensional Gaussian mixtures with unknown (and possibly degenerate) covariance. Recent works (Ghosh et al. '20; Mao, Wein '21; Davis, Diaz, Wang '21) have established lower bounds against the class of low-degree polynomial methods and the sum-of-squares (SoS) hierarchy for recovering certain hidden structures planted in Gaussian clustering instances. Prior work on many similar inference tasks portends that such lower bounds strongly suggest the presence of an inherent statistical-to-computational gap for clustering, that is, a parameter regime where the clustering task is statistically possible but no polynomial-time algorithm succeeds. One special case of the clustering task we consider is equivalent to the problem of finding a planted hypercube vector in an otherwise random subspace. We show that, perhaps surprisingly, this particular clustering model does not exhibit a statistical-to-computational gap, even though the aforementioned low-degree and SoS lower bounds continue to apply in this case. To achieve this, we give a polynomial-time algorithm based on the Lenstra–Lenstra–Lovasz lattice basis reduction method which achieves the statistically-optimal sample complexity of d+1 samples. This result extends the class of problems whose conjectured statistical-to-computational gaps can be "closed" by "brittle" polynomial-time algorithms, highlighting the crucial but subtle role of noise in the onset of statistical-to-computational gaps.Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canonical task of clustering d-dimensional Gaussian mixtures with unknown (and possibly degenerate) covariance. Recent works (Ghosh et al. '20; Mao, Wein '21; Davis, Diaz, Wang '21) have established lower bounds against the class of low-degree polynomial methods and the sum-of-squares (SoS) hierarchy for recovering certain h…
O organizátorovi (COLT)
The conference is held annually since 1988 and has become the leading conference on Learning theory by maintaining a highly selective process for submissions. It is committed in high-quality articles in all theoretical aspects of machine learning and related topics.
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Gradient descent algorithms for Bures-Wasserstein barycenters
Später ansehen
How Good is SGD with Random Shuffling?
Später ansehen
On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
Später ansehen
A Corrective View of Neural Networks: Representation, Memorization and Learning
Später ansehen
Guy Bresler, …
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
Später ansehen
Mean-Field Nonparametric Estimation of Interacting Particle Systems
Später ansehen
Rentian Yao, …