Lower Bounds for Parallel Diffusion Sampling

Key points

• Standard diffusion samplers generate samples through repeated evaluations of a learned score function.1
• Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds.1
• Specifically, we prove (1) a $\widetildeΩ(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $R^d$, and (2) an $Ω(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball.1
• Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy.1

Sources (1)

• [1]Lower Bounds for Parallel Diffusion Sampling
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 6, 10:09 PM

  We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores.

  Standard diffusion samplers generate samples through repeated evaluations of a learned score function.

Extractive summary: sentences quoted from the sources.