mlsanityData to 7 Oct 2026

Learning Mixtures of Gaussians Using Diffusion Models

arXiv 2404.18869 ↗First posted 29 Apr 2024cs.LG cs.DS math.PRcited by 41

On the map: Diffusion models → Diffusion foundations and sampling

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.

Key facts. Cited by 41 papers in the map (data through 7 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.

Builds on

17 of 60 references.

Closest ancestors · 10

Same direction, newest first

  1. 2024Theoretical Insights for Diffusion Guidance: A Case Study for Gaussian Mixture Models3 Mar
  2. 2024Critical windows: non-asymptotic theory for feature emergence in diffusion models3 Mar
  3. 2024Score-based generative models break the curse of dimensionality in learning a family of sub-Gaussian probability distributions12 Feb
  4. 2024Score-based Diffusion Models via Stochastic Differential Equations -- a Technical Tutorial12 Feb
  5. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models20 Sep
  6. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization7 Aug
  7. 2023Learning Mixtures of Gaussians Using the DDPM Objective3 Jul
  8. 2023Diffusion Models are Minimax Optimal Distribution Estimators3 Mar
  9. 2023Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data14 Feb
  10. 2022Convergence of denoising diffusion models under the manifold hypothesis10 Aug

Other references · 7

  1. 2022Statistical Efficiency of Score Matching: The View from Isoperimetrycited by 63
  2. 2024Optimal score estimation via empirical Bayes smoothingcited by 60
  3. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 53
  4. 2023Sampling, Diffusions, and Stochastic Localizationcited by 38
  5. 2023Analysis of learning a flow-based generative model from limited sample complexitycited by 38
  6. 2020Optimal estimation of high-dimensional location Gaussian mixturescited by 16
  7. 2023Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusionscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 13; 2025: 18; 2026: 10.

41 papers.

Sort:

By area:

  1. 2025Masked Autoencoders Are Effective Tokenizers for Diffusion Modelscited by 93
  2. 2024Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributionscited by 53
  3. 2024What does guidance do? A fine-grained analysis in a simple settingcited by 45
  4. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  5. 2024The Unreasonable Effectiveness of Gaussian Score Approximation for Diffusion Models and its Applicationscited by 32
  6. 2024Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspectivecited by 24
  7. 2025Minimax Optimality of the Probability Flow ODE for Diffusion Modelscited by 23
  8. 2025Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixturescited by 23
  9. 2025Breaking AR's Sampling Bottleneck: Provable Acceleration via Diffusion Language Modelscited by 23
  10. 2025On the Edge of Memorization in Diffusion Modelscited by 22
  11. 2024On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimalitycited by 21
  12. 2024On the Feature Learning in Diffusion Modelscited by 19
29 more
  1. 2024How much is a noisy image worth? Data Scaling Laws for Ambient Diffusioncited by 18
  2. 2025Does Generation Require Memorization? Creative Diffusion Models using Ambient Diffusioncited by 17
  3. 2026Confidence-Based Decoding is Provably Efficient for Diffusion Language Modelscited by 17
  4. 2024Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyondcited by 15
  5. 2025On the Interpolation Effect of Score Smoothing in Diffusion Modelscited by 15
  6. 2025A solvable model of learning generative diffusion: theory and insightscited by 14
  7. 2025Generalization of Diffusion Models Arises with a Balanced Representation Spacecited by 10
  8. 2024Slight Corruption in Pre-training Data Makes Better Diffusion Modelscited by 9
  9. 2026Adaptation to Intrinsic Dependence in Diffusion Language Modelscited by 9
  10. 2026High-accuracy and dimension-free sampling with diffusionscited by 7
  11. 2024Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplerscited by 6
  12. 2025Optimizing Noise Schedules of Generative Models in High Dimensionsscited by 6
  13. 2025Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysiscited by 6
  14. 2025DiffEM: Learning from Corrupted Data with Diffusion Models via Expectation Maximizationcited by 6
  15. 2025Localized Diffusion Modelscited by 5
  16. 2025LLM-Prior: A Framework for Knowledge-Driven Prior Elicitation and Aggregationcited by 5
  17. 2026Diffusion Models with Heavy-Tailed Targets: Score Estimation and Sampling Guaranteescited by 4
  18. 2026Weak Diffusion Priors Can Still Achieve Strong Inverse-Problem Performancecited by 4
  19. 2025CCS: Controllable and Constrained Sampling with Diffusion Models via Initial Noise Perturbationcited by 3
  20. 2025Dimension-free error estimate for diffusion model and optimal schedulingcited by 3
  21. 2025Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussiancited by 2
  22. 2026Diffusion models recover accurate mixture weights despite score function insensitivitycited by 2
  23. 2026Denoising growth complexity: Data geometry and certified schedules for diffusion samplingcited by 2
  24. 2024Unrolled denoising networks provably learn optimal Bayesian inferencecited by 1
  25. 2024Phase-aware Training Schedule Simplifies Learning in Flow-Based Generative Modelscited by 1
  26. 2026Noise Schedule Design for Diffusion Models: An Optimal Control Perspectivecited by 1
  27. 2025Personalized Federated Training of Diffusion Models with Privacy Guaranteescited by 0
  28. 2026A Quantitative Approximation Framework for Flow Distillation in Diffusion Modelscited by 0
  29. 2026Robustness of Diffusion Models under Distribution Shiftcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Learning general Gaussian mixtures with efficient score matching
  2. 2024Diffusion Model Conditioning on Gaussian Mixture Model and Negative Gaussian Mixture Gradient
  3. 2024Structured Diffusion Models with Mixture of Gaussians as Prior Distribution
  4. 2026Diffusion Models for High-Dimensional Clustered Data: Intrinsic-Dimension Adaptivity via Bayesian Classification
  5. 2025End-To-End Learning of Gaussian Mixture Priors for Diffusion Sampler
  6. 2023Generative Modeling on Manifolds Through Mixture of Riemannian Diffusion Processes
  7. 2023Product of Gaussian Mixture Diffusion Models
  8. 2026Multi-Subspace Multi-Modal Modeling for Diffusion Models: Estimation, Convergence and Mixture of Experts