Computational bottlenecks for denoising diffusions

arXiv:2503.08028v3 Announce Type: replace-cross Abstract: Denoising diffusions sample from a probability distribution mu in R^d by constructing a stochastic process ({hat{oldsymbol x}}_t:tge 0) in R^d such that {hat{oldsymbol x}}_0 is easy to sample, but the distribution of hat{oldsymbol x}_T at large T approximates mu. The drift {oldsymbol m}:R^dimesRoR^d of this diffusion process is learned my minimizing a score-matching objective. Is every probability distribution mu, for which sampling is tractable, also amenable to sampling via diffusions? We provide evidence to the contrary by studying a probability distribution mu 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.

Related

• Resistance Distance and Linearized Optimal Transport on Graphs
• Adaptive Symmetrization of the KL Divergence

Source: arXiv cs.LG | 2026-04-10