Research map / Learning theory and algorithms / Sample complexity
Reverse Transition Kernel: A Flexible Framework to Accelerate Diffusion Inference
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.
Proposes a reverse transition kernel (RTK) framework that splits diffusion sampling into O~(1) strongly log-concave subproblems solved with MALA or underdamped Langevin, with TV convergence guarantees and small MoG experiments.
Problem
DDPM-style diffusion inference needs many small-step subproblems (about O(d eps^-2) or O(1/eps^2) steps) to reach TV error eps; the trade-off between number and difficulty of subproblems is unexplored.
Approach
Use a large step size eta = Theta(1) so each reverse transition kernel target is strongly log-concave with only O~(1) segments, then solve each segment with fast MCMC samplers (MALA or underdamped Langevin), including a score-only MALA variant that estimates energy differences from score via Taylor expansion.
Key results
- RTK-MALA attains the highest marginal accuracy among RTK methods on a 10-D mixture of Gaussians and converges faster along NFE than DDPM.
- Theory: RTK-ULD achieves O~(L^2 d^{1/2} eps^-1) gradient complexity in TV distance, versus O~(L^2 d eps^-2) for SDE-based DDPM analysis.
- RTK-MALA gives O(L^4 d^2 log(d/eps)) complexity, linear in log(1/eps) with respect to accuracy, under stricter assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RTK-based sampling instead of DDPM | Diffusion inference · 10D MoG | marginal accuracy | Helped |
| Use RTK-MALA instead of RTK-ULD | RTK inference · 10D MoG | marginal accuracy | Helped |
| Estimate the energy difference from scores rather than using RTK-MALA | RTK-MALA · 10D MoG | marginal accuracy | Hurt |
| Use RTK-ULA instead of DDPM | Diffusion inference · 10D MoG | marginal accuracy | Helped |
| Use RTK-based methods instead of DDPM | Diffusion inference · 10D MoG | reconstruction of local structure | Helped |
| Use RTK-ULD, score-only RTK-MALA, or RTK-MALA instead of RTK-ULA | RTK inference · 10D MoG | reconstruction of fine-grained structure | Helped |
| Use RTK-MALA instead of other compared methods | Diffusion inference · 10D MoG | reconstruction in low-probability regions | Helped |
Surprising findings
- Score-only RTK-MALA, which estimates energy differences from score, is slightly better than RTK-ULD in the MoG experiment.
Limitations
- No large-scale experiments on real data or pretrained diffusion models.
- RTK-MALA's fastest rate requires an energy difference estimator not available from pretrained diffusion models; score-only variant is slower.
- Cheeger constant lower bound is loose, making complexity bounds pessimistic.
Experimental setup
Datasets: synthetic 10-dimensional mixture of 12 Gaussians
Benchmarks: 10-dimensional mixture of Gaussians (marginal accuracy)
Metrics: marginal accuracy histogram fidelity NFE
Baselines: DDPM RTK-ULA DDIM
Builds on: DDPM DDIM Langevin dynamics Metropolis-adjusted Langevin algorithm underdamped Langevin dynamics
Closest papers by meaning
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.90)
- EVODiff: Entropy-aware Variance Optimized Diffusion Inference (NeurIPS 2025 · similarity 0.90)
- Efficient Denoising Diffusion via Probabilistic Masking (ICML 2024 · similarity 0.90)
- Divide-and-Conquer Posterior Sampling for Denoising Diffusion priors (NeurIPS 2024 · similarity 0.89)
- Robust Diffusion Models via Divergence-Induced Weighted Denoising (NeurIPS 2026 · similarity 0.89)
- TRIM: Scalable 3D Gaussian Diffusion Inference with Temporal and Spatial Trimming (NeurIPS 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.