# Learning Mixtures of Gaussians Using Diffusion Models

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 17 of its 60 references that are in the map.
- First posted on arXiv 29 Apr 2024.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 17 of 17)

- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [Diffusion Models are Minimax Optimal Distribution Estimators](https://mlsanity.com/paper/2303.01861/) (2023)
- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [Optimal score estimation via empirical Bayes smoothing](https://mlsanity.com/paper/2402.07747/) (2024)
- [Score-based Diffusion Models via Stochastic Differential Equations -- a Technical Tutorial](https://mlsanity.com/paper/2402.07487/) (2024)
- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [Critical windows: non-asymptotic theory for feature emergence in diffusion models](https://mlsanity.com/paper/2403.01633/) (2024)
- [Theoretical Insights for Diffusion Guidance: A Case Study for Gaussian Mixture Models](https://mlsanity.com/paper/2403.01639/) (2024)
- [Sampling, Diffusions, and Stochastic Localization](https://mlsanity.com/paper/2305.10690/) (2023)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)
- [Analysis of learning a flow-based generative model from limited sample complexity](https://mlsanity.com/paper/2310.03575/) (2023)
- [Optimal estimation of high-dimensional location Gaussian mixtures](https://mlsanity.com/paper/2002.05818/) (2020)
- [Score-based generative models break the curse of dimensionality in learning a family of sub-Gaussian probability distributions](https://mlsanity.com/paper/2402.08082/) (2024)
- [Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions](https://mlsanity.com/paper/2306.09332/) (2023)

## Built on by (most cited first, 30 of 42)

- [Masked Autoencoders Are Effective Tokenizers for Diffusion Models](https://mlsanity.com/paper/2502.03444/) (2025)
- [Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributions](https://mlsanity.com/paper/2409.02426/) (2024)
- [What does guidance do? A fine-grained analysis in a simple setting](https://mlsanity.com/paper/2409.13074/) (2024)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [The Unreasonable Effectiveness of Gaussian Score Approximation for Diffusion Models and its Applications](https://mlsanity.com/paper/2412.09726/) (2024)
- [Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspective](https://mlsanity.com/paper/2405.16418/) (2024)
- [Minimax Optimality of the Probability Flow ODE for Diffusion Models](https://mlsanity.com/paper/2503.09583/) (2025)
- [Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixtures](https://mlsanity.com/paper/2504.05300/) (2025)
- [Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Models](https://mlsanity.com/paper/2505.21400/) (2025)
- [On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimality](https://mlsanity.com/paper/2411.17522/) (2024)
- [On the Edge of Memorization in Diffusion Models](https://mlsanity.com/paper/2508.17689/) (2025)
- [On the Feature Learning in Diffusion Models](https://mlsanity.com/paper/2412.01021/) (2024)
- [How much is a noisy image worth? Data Scaling Laws for Ambient Diffusion](https://mlsanity.com/paper/2411.02780/) (2024)
- [Confidence-Based Decoding is Provably Efficient for Diffusion Language Models](https://mlsanity.com/paper/2603.22248/) (2026)
- [Does Generation Require Memorization? Creative Diffusion Models using Ambient Diffusion](https://mlsanity.com/paper/2502.21278/) (2025)
- [Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond](https://mlsanity.com/paper/2405.03251/) (2024)
- [On the Interpolation Effect of Score Smoothing in Diffusion Models](https://mlsanity.com/paper/2502.19499/) (2025)
- [A solvable model of learning generative diffusion: theory and insights](https://mlsanity.com/paper/2501.03937/) (2025)
- [Generalization of Diffusion Models Arises with a Balanced Representation Space](https://mlsanity.com/paper/2512.20963/) (2025)
- [Adaptation to Intrinsic Dependence in Diffusion Language Models](https://mlsanity.com/paper/2602.20126/) (2026)
- [Slight Corruption in Pre-training Data Makes Better Diffusion Models](https://mlsanity.com/paper/2405.20494/) (2024)
- [Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers](https://mlsanity.com/paper/2410.13746/) (2024)
- [Optimizing Noise Schedules of Generative Models in High Dimensionss](https://mlsanity.com/paper/2501.00988/) (2025)
- [Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis](https://mlsanity.com/paper/2507.03756/) (2025)
- [High-accuracy and dimension-free sampling with diffusions](https://mlsanity.com/paper/2601.10708/) (2026)
- [LLM-Prior: A Framework for Knowledge-Driven Prior Elicitation and Aggregation](https://mlsanity.com/paper/2508.03766/) (2025)
- [DiffEM: Learning from Corrupted Data with Diffusion Models via Expectation Maximization](https://mlsanity.com/paper/2510.12691/) (2025)
- [Localized Diffusion Models](https://mlsanity.com/paper/2505.04417/) (2025)
- [Diffusion Models with Heavy-Tailed Targets: Score Estimation and Sampling Guarantees](https://mlsanity.com/paper/2601.06715/) (2026)
- [Weak Diffusion Priors Can Still Achieve Strong Inverse-Problem Performance](https://mlsanity.com/paper/2601.22443/) (2026)

## Abstract (arXiv)

We give a new algorithm for learning mixtures of k Gaussians (with identity covariance in ℝn) to TV error varepsilon, with quasi-polynomial (O(n^poly,logleft(fracn+kvarepsilonright))) time and sample complexity, under a minimum weight assumption. Our results extend to continuous mixtures of Gaussians where the mixing distribution is supported on a union of k balls of constant radius. In particular, this applies to the case of Gaussian convolutions of distributions on low-dimensional manifolds, or more generally sets with small covering number, for which no sub-exponential algorithm was previously known. Unlike previous approaches, most of which are algebraic in nature, our approach is analytic and relies on the framework of diffusion models. Diffusion models are a modern paradigm for generative modeling, which typically rely on learning the score function (gradient log-pdf) along a process transforming a pure noise distribution, in our case a Gaussian, to the data distribution. Despite their dazzling performance in tasks such as image generation, there are few end-to-end theoretical guarantees that they can efficiently learn nontrivial families of distributions; we give some of the first such guarantees. We proceed by deriving higher-order Gaussian noise sensitivity bounds for the score functions for a Gaussian mixture to show that that they can be inductively learned using piecewise polynomial regression (up to poly-logarithmic degree), and combine this with known convergence results for diffusion models.