Diffusion sampling from d-dimensional distributions requires at least ~sqrt(d) adaptive score queries when score estimates have polynomial accuracy.
High-accuracy sampling for diffusion models and log-concave distributions
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We present algorithms for diffusion model sampling which obtain $\delta$-error in $\mathrm{polylog}(1/\delta)$ steps, given access to $\widetilde O(\delta)$-accurate score estimates in $L^2$. This is an exponential improvement over all previous results. Specifically, under minimal data assumptions, the complexity is $\widetilde O(d_\star \mathrm{polylog}(1/\delta))$ where $d_\star$ is the intrinsic dimension of the data. Further, under a non-uniform $L$-Lipschitz condition, the complexity reduces to $\widetilde O(L \mathrm{polylog}(1/\delta))$. Our approach also yields the first $\mathrm{polylog}(1/\delta)$ complexity sampler for general log-concave distributions using only gradient evaluations.
years
2026 3verdicts
UNVERDICTED 3representative citing papers
Metropolis-adjusted Langevin correctors using score-based acceptance probabilities, including an exact Bernoulli factory method and a Simpson's rule approximation, reduce sampling bias in diffusion models and improve FID scores.
A proximal gradient sampler for composite log-concave distributions achieves near-optimal iteration complexity of order kappa sqrt(d) log^4(1/epsilon) in total variation distance under strong convexity and smoothness.
citing papers explorer
-
Query Lower Bounds for Diffusion Sampling
Diffusion sampling from d-dimensional distributions requires at least ~sqrt(d) adaptive score queries when score estimates have polynomial accuracy.
-
Metropolis-Adjusted Diffusion Models
Metropolis-adjusted Langevin correctors using score-based acceptance probabilities, including an exact Bernoulli factory method and a Simpson's rule approximation, reduce sampling bias in diffusion models and improve FID scores.
-
A proximal gradient algorithm for composite log-concave sampling
A proximal gradient sampler for composite log-concave distributions achieves near-optimal iteration complexity of order kappa sqrt(d) log^4(1/epsilon) in total variation distance under strong convexity and smoothness.