# Provable benefits of score matching

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 3 Jun 2023.

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

- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [Minimum Stein Discrepancy Estimators](https://mlsanity.com/paper/1906.08283/) (2019)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [A Computationally Efficient Method for Learning Exponential Family Distributions](https://mlsanity.com/paper/2110.15397/) (2021)
- [Structure learning of antiferromagnetic Ising models](https://mlsanity.com/paper/1412.1443/) (2014)
- [Computational Implications of Reducing Data to Sufficient Statistics](https://mlsanity.com/paper/1409.3821/) (2014)
- [Learning Continuous Exponential Families Beyond Gaussian](https://mlsanity.com/paper/2102.09198/) (2021)

## Built on by (most cited first, 18 of 18)

- [Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction](https://mlsanity.com/paper/2403.17042/) (2024)
- [Score-based Diffusion Models via Stochastic Differential Equations -- a Technical Tutorial](https://mlsanity.com/paper/2402.07487/) (2024)
- [Diffusing States and Matching Scores: A New Framework for Imitation Learning](https://mlsanity.com/paper/2410.13855/) (2024)
- [Improved Sample Complexity Bounds for Diffusion Model Training](https://mlsanity.com/paper/2311.13745/) (2023)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions](https://mlsanity.com/paper/2306.09332/) (2023)
- [Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines](https://mlsanity.com/paper/2407.21046/) (2024)
- [Can Diffusion Models Disentangle? A Theoretical Perspective](https://mlsanity.com/paper/2504.00220/) (2025)
- [On the Contractivity of Stochastic Interpolation Flow](https://mlsanity.com/paper/2504.10653/) (2025)
- [Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian](https://mlsanity.com/paper/2511.22069/) (2025)
- [On the Robustness of Langevin Dynamics to Score Function Error](https://mlsanity.com/paper/2603.11319/) (2026)
- [A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation](https://mlsanity.com/paper/2409.18209/) (2024)
- [Discrete distributions are learnable from metastable samples](https://mlsanity.com/paper/2410.13800/) (2024)
- [PearSAN: A Machine Learning Method for Inverse Design using Pearson Correlated Surrogate Annealing](https://mlsanity.com/paper/2412.19284/) (2024)
- [Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimation](https://mlsanity.com/paper/2508.02103/) (2025)
- [Scientific Data Compression and Super-Resolution Sampling](https://mlsanity.com/paper/2511.13675/) (2025)
- [Computationally sufficient statistics for Ising models](https://mlsanity.com/paper/2602.12449/) (2026)
- [Finite Sample Bounds for Learning with Score Matching](https://mlsanity.com/paper/2605.14168/) (2026)

## Abstract (arXiv)

Score matching is an alternative to maximum likelihood (ML) for estimating a probability distribution parametrized up to a constant of proportionality. By fitting the ''score'' of the distribution, it sidesteps the need to compute this constant of proportionality (which is often intractable). While score matching and variants thereof are popular in practice, precise theoretical understanding of the benefits and tradeoffs with maximum likelihood -- both computational and statistical -- are not well understood. In this work, we give the first example of a natural exponential family of distributions such that the score matching loss is computationally efficient to optimize, and has a comparable statistical efficiency to ML, while the ML loss is intractable to optimize using a gradient-based method. The family consists of exponentials of polynomials of fixed degree, and our result can be viewed as a continuous analogue of recent developments in the discrete setting. Precisely, we show: (1) Designing a zeroth-order or first-order oracle for optimizing the maximum likelihood loss is NP-hard. (2) Maximum likelihood has a statistical efficiency polynomial in the ambient dimension and the radius of the parameters of the family. (3) Minimizing the score matching loss is both computationally and statistically efficient, with complexity polynomial in the ambient dimension.