# Learning general Gaussian mixtures with efficient score matching

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 18 of its 83 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, 18 of 18)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Let us Build Bridges: Understanding and Extending Diffusion Generative Models](https://mlsanity.com/paper/2208.14699/) (2022)
- [Error Bounds for Flow Matching Methods](https://mlsanity.com/paper/2305.16860/) (2023)
- [Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models](https://mlsanity.com/paper/2306.09251/) (2023)
- [Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers](https://mlsanity.com/paper/2303.03384/) (2023)
- [KL Convergence Guarantees for Score diffusion models under minimal data assumptions](https://mlsanity.com/paper/2308.12240/) (2023)
- [Optimal score estimation via empirical Bayes smoothing](https://mlsanity.com/paper/2402.07747/) (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)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [Fast parallel sampling under isoperimetry](https://mlsanity.com/paper/2401.09016/) (2024)
- [Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization](https://mlsanity.com/paper/2310.01762/) (2023)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)

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

- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [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)
- [Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Models](https://mlsanity.com/paper/2410.04760/) (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 the Feature Learning in Diffusion Models](https://mlsanity.com/paper/2412.01021/) (2024)
- [Diffusion Models and the Manifold Hypothesis: Log-Domain Smoothing is Geometry Adaptive](https://mlsanity.com/paper/2510.02305/) (2025)
- [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)
- [Posterior Sampling with Denoising Oracles via Tilted Transport](https://mlsanity.com/paper/2407.00745/) (2024)
- [Annealing Flow Generative Models Towards Sampling High-Dimensional and Multi-Modal Distributions](https://mlsanity.com/paper/2409.20547/) (2024)
- [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)
- [Denoising Score Distillation: From Noisy Diffusion Pretraining to One-Step High-Quality Generation](https://mlsanity.com/paper/2503.07578/) (2025)
- [Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis](https://mlsanity.com/paper/2507.03756/) (2025)
- [DiffEM: Learning from Corrupted Data with Diffusion Models via Expectation Maximization](https://mlsanity.com/paper/2510.12691/) (2025)
- [Diffusion Models with Heavy-Tailed Targets: Score Estimation and Sampling Guarantees](https://mlsanity.com/paper/2601.06715/) (2026)
- [Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion](https://mlsanity.com/paper/2501.00565/) (2024)
- [CCS: Controllable and Constrained Sampling with Diffusion Models via Initial Noise Perturbation](https://mlsanity.com/paper/2502.04670/) (2025)
- [A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations](https://mlsanity.com/paper/2508.14351/) (2025)
- [Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian](https://mlsanity.com/paper/2511.22069/) (2025)

## Abstract (arXiv)

We study the problem of learning mixtures of k Gaussians in d dimensions. We make no separation assumptions on the underlying mixture components: we only require that the covariance matrices have bounded condition number and that the means and covariances lie in a ball of bounded radius. We give an algorithm that draws dpoly(k/varepsilon) samples from the target mixture, runs in sample-polynomial time, and constructs a sampler whose output distribution is varepsilon-far from the unknown mixture in total variation. Prior works for this problem either (i) required exponential runtime in the dimension d, (ii) placed strong assumptions on the instance (e.g., spherical covariances or clusterability), or (iii) had doubly exponential dependence on the number of components k. Our approach departs from commonly used techniques for this problem like the method of moments. Instead, we leverage a recently developed reduction, based on diffusion models, from distribution learning to a supervised learning task called score matching. We give an algorithm for the latter by proving a structural result showing that the score function of a Gaussian mixture can be approximated by a piecewise-polynomial function, and there is an efficient algorithm for finding it. To our knowledge, this is the first example of diffusion models achieving a state-of-the-art theoretical guarantee for an unsupervised learning task.