# On Learning Parallel Pancakes with Mostly Uniform Weights

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

## 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 (most cited first, 18 of 18)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Tight bounds for learning a mixture of two gaussians](https://mlsanity.com/paper/1404.4997/) (2014)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Outlier-robust moment-estimation via sum-of-squares](https://mlsanity.com/paper/1711.11581/) (2017)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures](https://mlsanity.com/paper/2112.05445/) (2021)

## 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.