mlsanityData to 14 Oct 2026

SQ Lower Bounds for Learning Mixtures of Linear Classifiers

arXiv 2310.11876 ↗First posted 18 Oct 2023cs.LG cs.DS math.STcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning mixtures of linear classifiers under Gaussian covariates. Given sample access to a mixture of r distributions on ℝn of the form (x,yℓ), ℓ∈ [r], where x~N(0,In) and yℓ=sign(langlevℓ,xrangle) for an unknown unit vector vℓ, the goal is to learn the underlying distribution in total variation distance. Our main result is a Statistical Query (SQ) lower bound suggesting that known algorithms for this problem are essentially best possible, even for the special case of uniform mixtures. In particular, we show that the complexity of any SQ algorithm for the problem is npoly(1/Delta) log(r), where Delta is a lower bound on the pairwise ℓ2-separation between the vℓ's. The key technical ingredient underlying our result is a new construction of spherical designs that may be of independent interest.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 20 of its 51 references that are in the map. First posted on arXiv 18 Oct 2023.

Builds on

20 of 51 references.

References · 20

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  2. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  3. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  4. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  5. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  6. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  7. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  8. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  9. 2019Convergence Rates for Gaussian Mixtures of Expertscited by 39
  10. 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
  11. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  12. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
8 more
  1. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  2. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
  3. 2019Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Momentscited by 26
  4. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  5. 2018Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithmscited by 13
  6. 2013Learning Mixtures of Linear Classifierscited by 8
  7. 2020Recovery of sparse linear classifiers from mixture of responsescited by 6
  8. 2021Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixturescited by 5

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 1.

4 papers.

  1. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  2. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  3. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  4. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 2