# Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 50 references that are in the map.
- First posted on arXiv 27 Oct 2023.

## Builds on (most cited first, 30 of 34)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Sliced Score Matching: A Scalable Approach to Density and Score Estimation](https://mlsanity.com/paper/1905.07088/) (2019)
- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [Generative Modeling with Denoising Auto-Encoders and Langevin Sampling](https://mlsanity.com/paper/2002.00107/) (2020)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [Causal Machine Learning for Healthcare and Precision Medicine](https://mlsanity.com/paper/2205.11402/) (2022)
- [Diffusion Models for Causal Discovery via Topological Ordering](https://mlsanity.com/paper/2210.06201/) (2022)
- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [Ordering-Based Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/2105.06631/) (2021)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [Denoising Likelihood Score Matching for Conditional Score-based Data Generation](https://mlsanity.com/paper/2203.14206/) (2022)
- [Scalable Causal Discovery with Score Matching](https://mlsanity.com/paper/2304.03382/) (2023)
- [Causal Discovery with Score Matching on Additive Models with Arbitrary Noise](https://mlsanity.com/paper/2304.03265/) (2023)
- [Blindness of score-based methods to isolated components and mixing proportions](https://mlsanity.com/paper/2008.10087/) (2020)

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

- [Score matching through the roof: linear, nonlinear, and latent variables causal discovery](https://mlsanity.com/paper/2407.18755/) (2024)
- [Identifiability Guarantees for Causal Disentanglement from Purely Observational Data](https://mlsanity.com/paper/2410.23620/) (2024)
- [Optimal and Diffusion Transports in Machine Learning](https://mlsanity.com/paper/2512.06797/) (2025)
- [Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models](https://mlsanity.com/paper/2405.14496/) (2024)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [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)
- [Causal Structure and Representation Learning with Biomedical Applications](https://mlsanity.com/paper/2511.04790/) (2025)
- [Regularization can make diffusion models more efficient](https://mlsanity.com/paper/2502.09151/) (2025)
- [Understanding Generalization in Diffusion Distillation via Probability Flow Distance](https://mlsanity.com/paper/2505.20123/) (2025)
- [Causal Order Discovery based on Monotonic SCMs](https://mlsanity.com/paper/2410.19870/) (2024)
- [Shallow Diffuse: Robust and Invisible Watermarking through Low-Dimensional Subspaces in Diffusion Models](https://mlsanity.com/paper/2410.21088/) (2024)
- [When Additive Noise Meets Unobserved Mediators: Bivariate Denoising Diffusion for Causal Discovery](https://mlsanity.com/paper/2506.23374/) (2025)
- [Ordering-based Causal Discovery via Generalized Score Matching](https://mlsanity.com/paper/2601.16249/) (2026)
- [Linear Causal Discovery with Interventional Constraints](https://mlsanity.com/paper/2510.26342/) (2025)
- [Bridging Dynamics Gaps via Diffusion Schr"odinger Bridge for Cross-Domain Reinforcement Learning](https://mlsanity.com/paper/2602.23737/) (2026)
- [Intervention-Based Time Series Causal Discovery via Simulator-Generated Interventional Distributions](https://mlsanity.com/paper/2605.09870/) (2026)

## Abstract (arXiv)

This paper provides statistical sample complexity bounds for score-matching and its applications in causal discovery. We demonstrate that accurate estimation of the score function is achievable by training a standard deep ReLU neural network using stochastic gradient descent. We establish bounds on the error rate of recovering causal relationships using the score-matching-based causal discovery method of Rolland et al. [2022], assuming a sufficiently good estimation of the score function. Finally, we analyze the upper bound of score-matching estimation within the score-based generative modeling, which has been applied for causal discovery but is also of independent interest within the domain of generative models.