mlsanityData to 13 Oct 2026

SQ Lower Bounds for Learning Bounded Covariance GMMs

arXiv 2306.13057 ↗First posted 22 Jun 2023cs.LG cs.DS math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the complexity of learning mixtures of separated Gaussians with common unknown bounded covariance matrix. Specifically, we focus on learning Gaussian mixture models (GMMs) on ℝd of the form P= sumi=1k wi N(boldsymbol μi,mathbf Sigmai), where mathbf Sigmai = mathbf Sigma preceq mathbf I and mini neq j | boldsymbol μi - boldsymbol μj|2 ≥ kε for some ε>0. Known learning algorithms for this family of GMMs have complexity (dk)O(1/ε). In this work, we prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least dOmega(1/ε). In the special case where the separation is on the order of k1/2, we additionally obtain fine-grained SQ lower bounds with the correct exponent. Our SQ lower bounds imply similar lower bounds for low-degree polynomial tests. Conceptually, our results provide evidence that known algorithms for this problem are nearly best possible.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Builds on 28 of its 61 references that are in the map. First posted on arXiv 22 Jun 2023.

Builds on

28 of 61 references.

References · 28

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  2. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 84
  3. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  4. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  5. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  6. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  7. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  8. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  9. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  10. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  11. 2020Continuous LWEcited by 37
  12. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
16 more
  1. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  2. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  3. 2014Tight bounds for learning a mixture of two gaussianscited by 29
  4. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  5. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  6. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  7. 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
  8. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  9. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  10. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  11. 2013Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussianscited by 20
  12. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  13. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  14. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  15. 2021SoS Degree Reduction with Applications to Clustering and Robust Moment Estimationcited by 7
  16. 2021Lecture notes on high-dimensional datacited by 5

Built on by

Not cited yet.