mlsanityData to 7 Oct 2026

Computational bottlenecks for denoising diffusions

arXiv 2503.08028 ↗First posted 11 Mar 2025stat.ML cs.LGcited by 2

On the map: Diffusion models → Diffusion foundations and sampling

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.

Key facts. Cited by 2 papers in the map (data through 7 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.

Builds on

22 of 41 references.

Closest ancestors · 8

Same direction, newest first

  1. 2024Towards a mathematical theory for consistency training in diffusion models12 Feb
  2. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models20 Sep
  3. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization7 Aug
  4. 2023Learning Mixtures of Gaussians Using the DDPM Objective3 Jul
  5. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions3 Nov
  6. 2022Convergence of score-based generative modeling for general data distributions26 Sep
  7. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions22 Sep
  8. 2020Denoising Diffusion Probabilistic Models19 Jun

Other references · 14

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  3. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  4. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  5. 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
  6. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
  7. 2023Sampling, Diffusions, and Stochastic Localizationcited by 38
  8. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  9. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  10. 2023Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspectivecited by 26
  11. 2013Sparse PCA via Covariance Thresholdingcited by 21
  12. 2020All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimationcited by 16
2 more
  1. 2015Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrixcited by 12
  2. 2023Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initializationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problemscited by 3
  2. 2026On the Robustness of Langevin Dynamics to Score Function Errorcited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2023Denoising Diffusion Samplers
  2. 2023Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers
  3. 2023To smooth a cloud or to pin it down: Guarantees and Insights on Score Matching in Denoising Diffusion Models
  4. 2024Score-Optimal Diffusion Schedules
  5. 2024O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions
  6. 2025Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Bounds
  7. 2026Denoising growth complexity: Data geometry and certified schedules for diffusion sampling
  8. 2026High-accuracy and dimension-free sampling with diffusions