Query Lower Bounds for Diffusion Sampling

• URL: http://arxiv.org/abs/2604.10857v1
• Date: Sun, 12 Apr 2026 23:47:46 GMT
• Title: Query Lower Bounds for Diffusion Sampling
• Abstract summary: We prove that for $d$-dimensional distributions given access to score estimates with accuracy, any sampling requires $widetilde(sqrtd)$ score queries.<n>Our proof shows that any sampler must search over $widetilde(sqrtd)$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.
• Score: 5.541583428822629
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for $d$-dimensional distributions, given access to score estimates with polynomial accuracy $\varepsilon=d^{-O(1)}$ (in any $L^p$ sense), any sampling algorithm requires $\widetildeΩ(\sqrt{d})$ adaptive score queries. In particular, our proof shows that any sampler must search over $\widetildeΩ(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Related papers

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
  We show that high-accuracy guarantees for log-concave sampling are achievable using iteration gradients with subexponential tails.<n>Our framework also provides similar high accuracy guarantees under zeroth order (value) queries.
  arXiv  Detail & Related papers  (2026-02-15T23:19:07Z)
• Score-based sampling without diffusions: Guidance from a simple and modular scheme [0.0]
  We show how to design forward trajectories that both (a) the terminal distribution, and (b) each of the backward conditional distribution is defined by a strongly log concave (SLC) distribution.<n>This modular reduction allows us to exploit emphany SLC sampling algorithm in order to traverse the backwards path.<n>The use of high-accuracy routines yields $varepsilon$-accurate answers, in either KL or Wasserstein distances.
  arXiv  Detail & Related papers  (2025-12-30T11:34:59Z)
• Faster Diffusion Models via Higher-Order Approximation [28.824924809206255]
  We propose a principled, training-free sampling algorithm that requires only the order of $$ d1+2/K varepsilon-1/K $$ score function evaluations.<n>Our theory is robust vis-a-vis inexact score estimation, degrading gracefully as the score estimation error increases.<n>More broadly, our work develops a theoretical framework towards understanding the efficacy of high-order methods for accelerated sampling.
  arXiv  Detail & Related papers  (2025-06-30T16:49:03Z)
• Diffusion Tree Sampling: Scalable inference-time alignment of diffusion models [13.312007032203857]
  Adapting a pretrained diffusion model to new objectives at inference time remains an open problem in generative modeling.<n>We introduce a tree-based approach that samples from the reward-aligned target density by propagating terminal rewards back through the diffusion chain.<n>By reusing information from previous generations, we get an anytime algorithm that turns additional compute into steadily better samples.
  arXiv  Detail & Related papers  (2025-06-25T17:59:10Z)
• Distributional Diffusion Models with Scoring Rules [83.38210785728994]
  Diffusion models generate high-quality synthetic data.<n> generating high-quality outputs requires many discretization steps.<n>We propose to accomplish sample generation by learning the posterior em distribution of clean data samples.
  arXiv  Detail & Related papers  (2025-02-04T16:59:03Z)
• Provable Acceleration for Diffusion Models under Minimal Assumptions [8.15094483029656]
  We propose a novel training-free acceleration scheme for score-based samplers.<n>Under minimal assumptions, our scheme achieves iterations in total variation within $widetildeO(d5/4/sqrtvarepsilon)$.
  arXiv  Detail & Related papers  (2024-10-30T17:59:06Z)
• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
  We show that our algorithm can be parallelized to run in only $widetilde O(log2 d)$ parallel rounds. We also show that our algorithm can be parallelized to run in only $widetilde O(log2 d)$ parallel rounds.
  arXiv  Detail & Related papers  (2024-06-03T01:34:34Z)
• Improved Sample Complexity Bounds for Diffusion Model Training [6.20468094368214]
  We show an emphexponential improvement in the dependence onlinear error and depth, along with other relevant parameters.<n>We show an emphexponential improvement in the dependence onlinear error and depth, along with improved dependencies on other relevant parameters.
  arXiv  Detail & Related papers  (2023-11-23T00:27:13Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. We propose to tackle the exploration-exploitation problem following a decoupled approach composed of: 1) An "objective-specific" algorithm that prescribes how many samples to collect at which states, as if it has access to a generative model (i.e., sparse simulator of the environment); 2) An "objective-agnostic" sample collection responsible for generating the prescribed samples as fast as possible.
  arXiv  Detail & Related papers  (2020-07-13T15:17:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.