Research map / Learning theory and algorithms / Sample complexity
Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Adapts Shen and Lee's randomized midpoint method to diffusion probability-flow ODE sampling with underdamped Langevin correctors, improving TV dimension dependence to d^{5/12} and giving the first provable O(polylog d) parallel-round diffusion sampler.
Problem
Provable diffusion sampling runs in O(sqrt(d)) iterations in total variation, and no provable parallel-sampling guarantees existed for diffusion models; log-concave TV sampling also had an O(sqrt(d)) bound.
Approach
Replace the exponential integrator in the predictor step of the predictor-corrector framework with randomized midpoint discretization (unbiased drift estimate at a random intermediate time), shorten corrector times to trade Wasserstein error against TV error, and parallelize via collocation fixed-point iteration over R sub-windows.
Key results
- Sequential diffusion sampler achieves O~(d^{5/12}) iteration complexity in TV for arbitrary smooth distributions, improving on O~(sqrt(d)) from prior work.
- Parallel sampler runs in O~(log^2 d) parallel rounds, the first provable parallel guarantee for diffusion sampling.
- Log-concave sampling in TV achieves O~(d^{5/12}) dimension dependence, improving on O~(sqrt(d)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the exponential-integrator predictor discretization with randomized midpoint | Diffusion sampling for arbitrary smooth distributions · Arbitrary smooth distributions (TV) | dimension dependence of iteration complexity: \widetilde O(\sqrt{d}) -> \widetilde O(d^{5/12}) | Helped |
| Use collocation with fixed-point iteration to parallelize diffusion sampling | Diffusion sampling for arbitrary smooth distributions · Arbitrary smooth distributions (TV) | parallel rounds: \widetilde O(\log^2 d) | Helped |
| Apply randomized midpoint and a corrector step to underdamped Langevin sampling | Log-concave sampling · Log-concave distributions (TV) | dimension dependence of iteration complexity: \widetilde O(\sqrt{d}) -> \widetilde O(d^{5/12}) | Helped |
Surprising findings
- Score estimation accuracy must be a factor d^{1/12} stronger than in prior analysis, a cost the authors attribute to their analysis rather than the method.
Limitations
- Requires L-Lipschitz score and score-estimate smoothness assumptions.
- Requires score estimation error about d^{1/12} smaller than prior work.
- Parallel algorithm's total work scales as O(sqrt(d)) because of the fixed-point error floor, so it does not improve total work.
Experimental setup
Metrics: total variation distance iteration complexity parallel rounds
Baselines: exponential integrator predictor-corrector (Chen et al., 2023) DDPM analyses (Benton et al., 2023)
Builds on: Shen and Lee randomized midpoint method predictor-corrector framework (Chen et al. 2023) parallel underdamped Langevin (Anari et al.) probability flow ODE
Closest papers by meaning
- Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models (ICML 2025 · similarity 0.93)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.90)
- Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity (NeurIPS 2024 · similarity 0.90)
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.89)
- Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion (NeurIPS 2024 · similarity 0.89)
- Unified Convergence Analysis for Score-Based Diffusion Models with Deterministic Samplers (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.