# Computational bottlenecks for denoising diffusions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 11 Mar 2025.

## Placed in

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

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [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)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Sampling, Diffusions, and Stochastic Localization](https://mlsanity.com/paper/2305.10690/) (2023)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [Towards a mathematical theory for consistency training in diffusion models](https://mlsanity.com/paper/2402.07802/) (2024)
- [Sparse PCA via Covariance Thresholding](https://mlsanity.com/paper/1311.5179/) (2013)
- [All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation](https://mlsanity.com/paper/2006.07971/) (2020)
- [Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix](https://mlsanity.com/paper/1502.01988/) (2015)
- [Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization](https://mlsanity.com/paper/2310.01762/) (2023)

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

- [On the Robustness of Langevin Dynamics to Score Function Error](https://mlsanity.com/paper/2603.11319/) (2026)
- [Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems](https://mlsanity.com/paper/2603.20589/) (2026)
- [A computational phase transition for learning-to-sample from Ising models](https://mlsanity.com/paper/2605.24752/) (2026)

## Abstract (arXiv)

Denoising diffusions sample from a probability distribution μ in ℝd by constructing a stochastic process (hatboldsymbol xt:t≥ 0) in ℝd such that hatboldsymbol x0 is easy to sample, but the distribution of hatboldsymbol xT at large T approximates μ. The drift boldsymbol m:ℝd×ℝ→ℝd of this diffusion process is learned my minimizing a score-matching objective. Is every probability distribution μ, for which sampling is tractable, also amenable to sampling via diffusions? We provide evidence to the contrary by studying a probability distribution μ for which sampling is easy, but the drift of the diffusion process is intractable -- under a popular conjecture on information-computation gaps in statistical estimation. We show that there exist drifts that are superpolynomially close to the optimum value (among polynomial time drifts) and yet yield samples with distribution that is very far from the target one.