mlsanityData to 14 Oct 2026

On Learning Parallel Pancakes with Mostly Uniform Weights

arXiv 2504.15251 ↗First posted 21 Apr 2025cs.LG cs.DS math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the complexity of learning k-mixtures of Gaussians (k-GMMs) on ℝd. This task is known to have complexity dOmega(k) in full generality. To circumvent this exponential lower bound on the number of components, research has focused on learning families of GMMs satisfying additional structural properties. A natural assumption posits that the component weights are not exponentially small and that the components have the same unknown covariance. Recent work gave a d^O(log(1/wmin))-time algorithm for this class of GMMs, where wmin is the minimum weight. Our first main result is a Statistical Query (SQ) lower bound showing that this quasi-polynomial upper bound is essentially best possible, even for the special case of uniform weights. Specifically, we show that it is SQ-hard to distinguish between such a mixture and the standard Gaussian. We further explore how the distribution of weights affects the complexity of this task. Our second main result is a quasi-polynomial upper bound for the aforementioned testing task when most of the weights are uniform while a small fraction of the weights are potentially arbitrary.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 18 of its 36 references that are in the map. First posted on arXiv 21 Apr 2025.

Builds on

18 of 36 references.

References · 18

  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. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  5. 2020Continuous LWEcited by 37
  6. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  7. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  8. 2014Tight bounds for learning a mixture of two gaussianscited by 29
  9. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  10. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
  11. 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
  12. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
6 more
  1. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  2. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  3. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  4. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  5. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 6
  6. 2021Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixturescited by 5

Built on by

Not cited yet.