Research map / Optimization / Nonconvex and smooth optimization
Nearly $d$-Linear Convergence Bounds for Diffusion Models via Stochastic Localization
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.
Proves linear-in-dimension (up to logs) KL convergence bounds for denoising diffusion models with only finite second moments, using a stochastic-localization-inspired differential inequality to control time-discretization error.
Problem
Existing polynomial convergence bounds for diffusion models without smoothness assumptions scale quadratically (or worse) in data dimension d, while lower-bound intuition suggests linear scaling; the paper aims to close this gap for KL error of score-based sampling.
Approach
Uses an Itô-calculus differential inequality for the expected squared difference of score drifts at different times, with coefficients controlled via the stochastic localization identity d/ds E[A_s] = -E[A_s^2] (equivalently E[Σ_t^2] identity), combined with Girsanov-based path-measure KL bounds.
Key results
- Main theorem: KL(q_delta || p_{t_N}) ≲ eps_score^2 + kappa^2 d N + kappa d T + d e^{-2T}.
- Corollary: diffusion models need Õ(d log^2(1/δ)/ε^2) steps to reach ε^2 KL under finite second moments, improving the prior Õ(d^2 log^2(1/δ)/ε^2) bound.
- Discretization error bound is linear in d (up to logs), and the matching-in-d dependence is argued to be optimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use stochastic-localization-inspired control of reverse-SDE discretization error | Diffusion models with early stopping · Diffusion models, early stopping | steps: \tilde O \big( \frac{d^2 \log^2(1/\delta)}{\varepsilon^2} \big) -> \tilde O \big( \frac{d \log^2(1/\delta)}{\varepsilon^ | Helped |
Surprising findings
- The linear-in-eta KL discretization rate may not be optimal, yet Girsanov-based methods cannot improve it without significant modification.
Limitations
- Assumes perfect score estimation apart from the L2 score error term; no empirical validation.
- Linear-in-step-size KL rate likely not tight; quadratic-in-step-size bounds possible only with superlinear-in-d constants.
Experimental setup
Metrics: KL divergence (theoretical bound) iteration complexity
Baselines: Chen et al. 2022 bound (d^2 dependence) Lee et al. 2022 Lipschitz-score bound Benton et al. 2023 Lipschitz-free bounds
Builds on: Girsanov-based convergence analysis of diffusion models (Chen et al. 2022) Benton et al. 2023 polynomial bounds stochastic localization (Eldan) exponential integrator
Closest papers by meaning
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.89)
- Assessing the quality of denoising diffusion models in Wasserstein distance: noisy score and optimal bounds (NeurIPS 2025 · similarity 0.88)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.88)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.88)
- Interpreting and Improving Diffusion Models from an Optimization Perspective (ICML 2024 · similarity 0.87)
- Generalization of noisy SGD in unbounded non-convex settings (ICML 2025 · similarity 0.87)
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.