# Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 52 of its 101 references that are in the map.
- First posted on arXiv 20 Sep 2023.

## Placed in

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

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [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)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding](https://mlsanity.com/paper/2205.11487/) (2022)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Diffusion Models: A Comprehensive Survey of Methods and Applications](https://mlsanity.com/paper/2209.00796/) (2022)
- [Diffusion Models in Vision: A Survey](https://mlsanity.com/paper/2209.04747/) (2022)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Grad-TTS: A Diffusion Probabilistic Model for Text-to-Speech](https://mlsanity.com/paper/2105.06337/) (2021)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [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)
- [Conditional Random Fields as Recurrent Neural Networks](https://mlsanity.com/paper/1502.03240/) (2015)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [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)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)

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

- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretraining](https://mlsanity.com/paper/2310.08566/) (2023)
- [An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimization](https://mlsanity.com/paper/2404.07771/) (2024)
- [Unveil Conditional Diffusion Models with Classifier-free Guidance: A Sharp Statistical Theory](https://mlsanity.com/paper/2403.11968/) (2024)
- [Gradient Guidance for Diffusion Models: An Optimization Perspective](https://mlsanity.com/paper/2404.14743/) (2024)
- [Theoretical Insights for Diffusion Guidance: A Case Study for Gaussian Mixture Models](https://mlsanity.com/paper/2403.01639/) (2024)
- [Learning general Gaussian mixtures with efficient score matching](https://mlsanity.com/paper/2404.18893/) (2024)
- [Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization](https://mlsanity.com/paper/2401.15604/) (2024)
- [Learning Mixtures of Gaussians Using Diffusion Models](https://mlsanity.com/paper/2404.18869/) (2024)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Low-dimensional adaptation of diffusion models: Convergence in total variation](https://mlsanity.com/paper/2501.12982/) (2025)
- [Analysis of learning a flow-based generative model from limited sample complexity](https://mlsanity.com/paper/2310.03575/) (2023)
- [Stochastic Runge-Kutta Methods: Provable Acceleration of Diffusion Models](https://mlsanity.com/paper/2410.04760/) (2024)
- [Contractive Diffusion Probabilistic Models](https://mlsanity.com/paper/2401.13115/) (2024)
- [Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics](https://mlsanity.com/paper/2405.04669/) (2024)
- [How Compositional Generalization and Creativity Improve as Diffusion Models are Trained](https://mlsanity.com/paper/2502.12089/) (2025)
- [Diffusion Model for Data-Driven Black-Box Optimization](https://mlsanity.com/paper/2403.13219/) (2024)
- [Dimension-Free Convergence of Diffusion Models for Approximate Gaussian Mixtures](https://mlsanity.com/paper/2504.05300/) (2025)
- [TREAD: Token Routing for Efficient Architecture-agnostic Diffusion Training](https://mlsanity.com/paper/2501.04765/) (2025)
- [Constrained Diffusion Models via Dual Training](https://mlsanity.com/paper/2408.15094/) (2024)
- [Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach](https://mlsanity.com/paper/2402.13901/) (2024)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [Sample Complexity and Representation Ability of Test-time Scaling Paradigms](https://mlsanity.com/paper/2506.05295/) (2025)
- [Masked Completion via Structured Diffusion with White-Box Transformers](https://mlsanity.com/paper/2404.02446/) (2024)
- [Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers](https://mlsanity.com/paper/2410.13746/) (2024)
- [Diffusion Transformer Captures Spatial-Temporal Dependencies: A Theory for Gaussian Process Data](https://mlsanity.com/paper/2407.16134/) (2024)
- [Localized Diffusion Models](https://mlsanity.com/paper/2505.04417/) (2025)
- [Cryptographic Hardness of Score Estimation](https://mlsanity.com/paper/2404.03272/) (2024)
- [Neural Networks Generalize on Low Complexity Data](https://mlsanity.com/paper/2409.12446/) (2024)
- [Computational bottlenecks for denoising diffusions](https://mlsanity.com/paper/2503.08028/) (2025)

## Abstract (arXiv)

We investigate the approximation efficiency of score functions by deep neural networks in diffusion-based generative modeling. While existing approximation theories utilize the smoothness of score functions, they suffer from the curse of dimensionality for intrinsically high-dimensional data. This limitation is pronounced in graphical models such as Markov random fields, common for image distributions, where the approximation efficiency of score functions remains unestablished. To address this, we observe score functions can often be well-approximated in graphical models through variational inference denoising algorithms. Furthermore, these algorithms are amenable to efficient neural network representation. We demonstrate this in examples of graphical models, including Ising models, conditional Ising models, restricted Boltzmann machines, and sparse encoding models. Combined with off-the-shelf discretization error bounds for diffusion-based sampling, we provide an efficient sample complexity bound for diffusion-based generative modeling when the score function is learned by deep neural networks.