Lattice-Based Methods Surpass Sum-of-Squares in Clustering

Ilias Zadik; Min Jae Song; Alexander S. Wein; Joan Bruna

Lattice-Based Methods Surpass Sum-of-Squares in Clustering

Ilias Zadik, Min Jae Song, Alexander S. Wein, Joan Bruna

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

In this work we show that for an important case of the canonical clustering task of a d-dimensional Gaussian mixture with unknown (and possibly degenerate) covariance, a lattice-based polynomial-time method can provably succeed with the statistically-optimal sample complexity of d + 1 samples. This is in contrast with the evidence of “computational hardness” for this task, as suggested by the previously established failure of low-degree methods and the Sum-of-Squares hierarchy to succeed with access to õ(d³/²) and õ(d²) samples, respectively.

Original language	English (US)
Pages (from-to)	1247-1248
Number of pages	2
Journal	Proceedings of Machine Learning Research
Volume	178
State	Published - 2022
Event	35th Conference on Learning Theory, COLT 2022 - London, United Kingdom Duration: Jul 2 2022 → Jul 5 2022

Keywords

average-case complexity
lattice basis reduction
statistical-to-computational gaps
sum-of-squares lower bounds

ASJC Scopus subject areas

Artificial Intelligence
Software
Control and Systems Engineering
Statistics and Probability

Cite this

@article{608f92dc852d4ca8899cc69b49d54a32,

title = "Lattice-Based Methods Surpass Sum-of-Squares in Clustering",

abstract = "In this work we show that for an important case of the canonical clustering task of a d-dimensional Gaussian mixture with unknown (and possibly degenerate) covariance, a lattice-based polynomial-time method can provably succeed with the statistically-optimal sample complexity of d + 1 samples. This is in contrast with the evidence of “computational hardness” for this task, as suggested by the previously established failure of low-degree methods and the Sum-of-Squares hierarchy to succeed with access to {\~o}(d3/2) and {\~o}(d2) samples, respectively.",

keywords = "average-case complexity, lattice basis reduction, statistical-to-computational gaps, sum-of-squares lower bounds",

author = "Ilias Zadik and Song, {Min Jae} and Wein, {Alexander S.} and Joan Bruna",

note = "Publisher Copyright: {\textcopyright} 2022 I. Zadik, M.J. Song, A.S. Wein & J. Bruna.; 35th Conference on Learning Theory, COLT 2022 ; Conference date: 02-07-2022 Through 05-07-2022",

year = "2022",

language = "English (US)",

volume = "178",

pages = "1247--1248",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

}

TY - JOUR

T1 - Lattice-Based Methods Surpass Sum-of-Squares in Clustering

AU - Zadik, Ilias

AU - Song, Min Jae

AU - Wein, Alexander S.

AU - Bruna, Joan

PY - 2022

Y1 - 2022

N2 - In this work we show that for an important case of the canonical clustering task of a d-dimensional Gaussian mixture with unknown (and possibly degenerate) covariance, a lattice-based polynomial-time method can provably succeed with the statistically-optimal sample complexity of d + 1 samples. This is in contrast with the evidence of “computational hardness” for this task, as suggested by the previously established failure of low-degree methods and the Sum-of-Squares hierarchy to succeed with access to õ(d3/2) and õ(d2) samples, respectively.

AB - In this work we show that for an important case of the canonical clustering task of a d-dimensional Gaussian mixture with unknown (and possibly degenerate) covariance, a lattice-based polynomial-time method can provably succeed with the statistically-optimal sample complexity of d + 1 samples. This is in contrast with the evidence of “computational hardness” for this task, as suggested by the previously established failure of low-degree methods and the Sum-of-Squares hierarchy to succeed with access to õ(d3/2) and õ(d2) samples, respectively.

KW - average-case complexity

KW - lattice basis reduction

KW - statistical-to-computational gaps

KW - sum-of-squares lower bounds

UR - http://www.scopus.com/inward/record.url?scp=85142877918&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85142877918&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85142877918

SN - 2640-3498

VL - 178

SP - 1247

EP - 1248

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 35th Conference on Learning Theory, COLT 2022

Y2 - 2 July 2022 through 5 July 2022

ER -

Lattice-Based Methods Surpass Sum-of-Squares in Clustering

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this