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

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

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1247-1248
Number of pages2
JournalProceedings of Machine Learning Research
StatePublished - 2022
Event35th Conference on Learning Theory, COLT 2022 - London, United Kingdom
Duration: Jul 2 2022Jul 5 2022


  • 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


Dive into the research topics of 'Lattice-Based Methods Surpass Sum-of-Squares in Clustering'. Together they form a unique fingerprint.

Cite this