Research map / Learning theory and algorithms / Sample complexity
Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions
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.
Shows that a truncated kernel density score estimator gives near-minimax-optimal sampling error for score-based diffusion models under only sub-Gaussian (and, for minimax, Sobolev β≤2) assumptions, removing the density lower bound.
Problem
Existing minimax-optimality results for score-based diffusion models rely on uniform-in-time score error bounds or strong assumptions (bounded support and density lower bound), which exclude multimodal and well-separated mixtures; the paper asks when diffusion sampling attains the statistically opti
Approach
Uses a truncated kernel score estimator (numerator and denominator from Legendre-polynomial kernel density estimates, set to zero where the density estimate falls below 1/(n t^{d/2})) with time-dependent error analysis, plus early stopping and Girsanov's theorem, to remove the density lower bound while retaining minimax rates.
Key results
- Kernel-based truncated score estimator achieves MSE of order n^{-1} t^{-(d+2)/2}(t^{d/2} ∨ 1) (up to polylog) for score of p_0*N(0,tI_d) under sub-Gaussian p_0.
- Sampling TV error of Õ(n^{-1/2} t^{-d/4}) under sub-Gaussian assumption alone, with early stopping t0=n^{-C}.
- Under Sobolev β≤2 with early stopping t0=n^{-2/(2β+d)}, diffusion sampling TV error is Õ(n^{-β/(2β+d)}), matching the nonparametric minimax rate up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the truncated kernel score estimator instead of estimating the score without density thresholding | Kernel score estimation for p_t under a sub-Gaussian p_0 · Gaussian-smoothed distribution p_t | score estimation MSE: \mathrm{polylog}(n) \, n^{-1} t^{-\frac{d+2}{2}} \left(t^{\frac{d}{2}}+ \sigma_0^d\right) | Helped |
| Use early stopping at t_0 = n^{-2/(2β+d)} | Brownian diffusion model with truncated kernel score estimator · p_0 in the Sobolev density class, β ≤ 2 | total variation distance: \mathrm{polylog}(n) \, n^{-\frac{\beta}{2\beta+d}} | Helped |
| Remove early stopping by setting t_0 = 0 (ablation) | Score estimation for the diffusion model · Score function at t = 0 | score estimation error | Hurt |
| Use the Sobolev-tuned early stopping time t_0 = n^{-2/(2β+d)} | Brownian diffusion model with truncated kernel score estimator · p_0 in the Sobolev density class, β ≤ 2 | total variation distance: n^{-\frac{\beta}{2 \beta+d}} | Helped |
Surprising findings
- The density lower bound assumption used in prior minimax diffusion proofs can be removed without degrading the rate.
Limitations
- Minimax result proven only for Sobolev smoothness β≤2.
- Analysis uses an exact kernel score estimator rather than neural score networks; discretization error only sketched.
- Experiments are a limited MNIST U-Net illustration not tied to the theorem's estimator.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: score error slope vs t total variation error bound (theoretical)
Baselines: Oko et al. 2023 minimax diffusion result Wibisono et al. 2024 regularized kernel score estimator U-Net score network (numerical experiment)
Builds on: Oko et al. diffusion minimax (density lower bound) empirical Bayes truncated score estimator (Saremi et al.) Girsanov-based diffusion analysis Holley-Stroock perturbation
Closest papers by meaning
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis (ICLR 2025 · similarity 0.91)
- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions (ICLR 2025 · similarity 0.91)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.90)
- Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models (NeurIPS 2024 · similarity 0.90)
- Unified Convergence Analysis for Score-Based Diffusion Models with Deterministic Samplers (ICLR 2025 · similarity 0.90)
- Accelerating Convergence of Score-Based Diffusion Models, Provably (ICML 2024 · 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.