Research map / Learning theory and algorithms / Sample complexity
On Learning Parallel Pancakes with Mostly Uniform Weights
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
placeholder
Problem
Learning k-component Gaussian mixtures with shared unknown covariance (parallel pancakes) when mixing weights are not exponentially small; the existing algorithm is quasi-polynomial in 1/w_min and it is unknown whether this is necessary.
Approach
Relate the number of matchable moments of a discrete distribution with k' arbitrary weights and k-k' equal weights to O(log k + k') via a polynomial-vanishing argument plus hypercontractivity; this gives an SQ lower bound via designs for uniform weights and a moment-tensor tester whose cost depends on k' rather than on w_min.
Key results
- SQ lower bound: distinguishing uniform-weight k-parallel-pancake GMMs from N(0,I) requires either 2^{d^{Omega(1)}} queries or accuracy d^{-Omega(log k)}, showing the quasi-polynomial algorithm is essentially tight.
- Testing algorithm with n = O((kd/δ)^{O(k'+log k)} + log(k)/w_min) samples when k' weights are arbitrary and the rest are equal.
- Impossibility of moment matching: a discrete distribution with k' arbitrary and k-k' equal weights cannot match more than O(log k + k') moments with N(0,1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| restrict all mixture weights to be uniform | SQ algorithms for the Parallel Pancakes Testing Problem · Parallel Pancakes Testing Problem | SQ complexity: $2^{d^{\Omega(1)}}$ queries or at least one query of accuracy $d^{-\Omega(\log k)}$ | Hurt |
| allow $k'$ weights to be unconstrained while the remaining weights are equal | Parallel Pancakes Testing Problem · Parallel Pancakes Testing Problem | sample complexity: $O\left((k d/\delta)^{O(k' + \log(k))} + \log(k)/w_{\min}\right)$ | Helped |
| use the mostly-equal-weights testing algorithm instead of the prior minimum-weight-dependent algorithm | Parallel Pancakes testing · Parallel Pancakes Testing Problem | dependence on $w_{\min}$: $d^{\log(1/w_{\min})}$; $(kd)^{O(k' + \log k)} + (\log k)/w_{\min}$ | Helped |
Limitations
- The result is for testing the existence of parallel pancake structure, not for learning the mixture or its direction.
- The algorithm does not imply a general quasi-polynomial-free learning algorithm for k-GMMs.
- Extension to unknown and non-collinear means or unequal covariances is open.
Experimental setup
Baselines: d^{O(log(1/w_min))} algorithm for common-covariance GMMs d^{O(k)} general GMM learning
Builds on: non-Gaussian component analysis design theory (Dwivedi et al.) quasi-polynomial parallel pancake learning algorithm
Closest papers by meaning
- Toward Global Convergence of Gradient EM for Over-Paramterized Gaussian Mixture Models (NeurIPS 2024 · similarity 0.86)
- Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions? (NeurIPS 2026 · similarity 0.86)
- Sample-Efficient Private Learning of Mixtures of Gaussians (NeurIPS 2024 · similarity 0.86)
- Sublinear Variational Optimization of Gaussian Mixture Models with Millions to Billions of Parameters (NeurIPS 2026 · similarity 0.85)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.84)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.