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

arXiv: https://arxiv.org/abs/2112.03898 · HTML: https://mlsanity.com/paper/2112.03898/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 100 references that are in the map.
- First posted on arXiv 7 Dec 2021.

## Builds on (most cited first, 30 of 44)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Phase retrieval in high dimensions: Statistical and computational phase transitions](https://mlsanity.com/paper/2006.05228/) (2020)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Finding a sparse vector in a subspace: Linear sparsity using alternating directions](https://mlsanity.com/paper/1412.4659/) (2014)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications](https://mlsanity.com/paper/2001.06970/) (2020)

## Built on by (most cited first, 25 of 25)

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (2022)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures](https://mlsanity.com/paper/2201.09040/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures](https://mlsanity.com/paper/2112.05445/) (2021)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)
- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression](https://mlsanity.com/paper/2402.14103/) (2024)
- [SQ Lower Bounds for Random Sparse Planted Vector Problem](https://mlsanity.com/paper/2301.11124/) (2023)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Cryptographic Hardness of Score Estimation](https://mlsanity.com/paper/2404.03272/) (2024)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds](https://mlsanity.com/paper/2506.06259/) (2025)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)
- [Sparse Linear Regression and Lattice Problems](https://mlsanity.com/paper/2402.14645/) (2024)
- [On the Hardness of Learning One Hidden Layer Neural Networks](https://mlsanity.com/paper/2410.03477/) (2024)
- [Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit](https://mlsanity.com/paper/2502.02668/) (2025)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)

## Abstract (arXiv)

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.