Diffusion Models are Minimax Optimal Distribution Estimators

Kazusato OkoShunta AkiyamaTaiji Suzuki

article2023ICML190 citations

Establishes rigorous statistical learning guarantees for diffusion models by proving that neural network-based score matching achieves nearly minimax optimal estimation rates over Besov spaces under both total variation and Wasserstein distances.

Listen

Diffusion models have rapidly emerged as the state-of-the-art technique for generating high-quality images, video, and audio. Despite their extraordinary practical success, a critical theoretical foundation was missing: prior research largely failed to explain how efficiently these models learn true underlying data distributions from a limited number of training samples. Most existing guarantees assumed access to exact data scores or relied on empirical distribution bounds that severely limited statistical convergence rates, leaving open the fundamental question of whether diffusion models are statistically optimal distribution learners.

The article establishes a rigorous statistical learning theory for diffusion modeling by evaluating its approximation and generalization performance when estimating probability densities. Specifically, it demonstrates that when deep neural networks are properly trained on finite data, the resulting diffusion models achieve nearly optimal statistical estimation rates for complex, non-smooth function classes and adapt efficiently to low-dimensional data structures.

To conduct this evaluation, the authors developed a theoretical framework centered on Besov function spaces, which encompass standard Sobolev, Hölder, and potentially discontinuous data distributions. They introduced a novel basis decomposition called the diffused B-spline basis to approximate the score function across both spatial coordinates and time steps using deep ReLU neural networks. The analysis explicitly bounds generalization errors from empirical score-matching losses and translates these errors into global distribution estimation metrics, primarily total variation distance and first-order Wasserstein distance, across both continuous-time dynamics and discretized implementations.

The findings confirm that diffusion models are statistically near-optimal distribution estimators. First, the authors prove that diffusion models achieve the minimax optimal estimation rate in total variation distance up to logarithmic factors. Second, by introducing a time-interval network switching strategy, the model achieves the faster nearly minimax optimal rate in the Wasserstein distance, capitalizing on the principle that score errors occurring closer to the initial data step contribute less to the overall transportation error. Third, under the manifold hypothesis where data lies on a lower-dimensional subspace, the convergence rate scales with the intrinsic data dimension rather than the ambient space dimension, theoretically proving that diffusion models avoid the curse of dimensionality. Finally, the analysis proves that discretization errors can be rendered negligible using a polynomial number of time steps.

These insights provide essential reassurance for engineering and decision-making teams deploying diffusion architectures. They confirm that the exceptional performance of diffusion models is mathematically justified by optimal statistical efficiency and natural adaptivity to low-dimensional structures. Furthermore, the findings explain why practical training strategies—such as weighting score losses toward later diffusion times—enhance real-world sample quality and model accuracy.

Practitioners are recommended to leverage diffusion architectures with confidence in high-dimensional domains where data occupies lower-dimensional manifolds. To maximize statistical efficiency in practice, engineering workflows should consider time-dependent capacity allocation or weighted score-matching objectives that align with the theoretical switching framework. Further research should focus on the algorithmic optimization dynamics of score networks to bridge remaining gaps between theoretical risk minimization and practical gradient-based training.

The findings carry high theoretical confidence, supported by rigorous mathematical derivations under minimal assumptions. However, readers should note that the analysis assumes bounded data support, smooth boundary decay conditions, and optimal empirical loss minimization, without modeling the practical challenges of non-convex neural network training trajectories.

RIKEN AIP University of Tokyo diffusion probabilistic models estimation method diffusion models minimax optimal estimation rates density estimation

arXiv: 2303.01861

Paper: Score-Based Generative Modeling through Stochastic Differential Equations, Yang Song et al. (2021). Establishes the continuous-time stochastic differential equation and score-matching formulation that the source evaluates for minimax statistical optimality.
Paper: Denoising Diffusion Probabilistic Models, Jonathan Ho et al. (2020). Introduces the foundational denoising score-matching framework and training objectives whose sample complexity and statistical convergence rates are analyzed in the source.
Paper: Maximum Likelihood Training for Score-based Diffusion ODEs by High Order Denoising Score Matching, Cheng Lu et al. (2022). Analyzes the theoretical relationship between score-matching errors and probability distribution metrics in continuous-time diffusion equations.
Paper: Spectrally-normalized margin bounds for neural networks, Peter Bartlett et al. (2017). Develops the deep neural network statistical generalization and complexity bounds that underpin the source's empirical risk minimization guarantees.
Paper: Elucidating the Design Space of Diffusion-Based Generative Models, Tero Karras et al. (2022). Details the time-dependent score weighting and noise schedule parameterizations that motivate the source's time-interval network switching strategy.

Paper: Generalization in diffusion models arises from geometry-adaptive harmonic representations, Zahra Kadkhodaie et al. (2024). Extends the source's statistical generalization bounds by demonstrating how empirical score matching avoids memorization via geometry-adaptive harmonic representations.
Paper: Discrete State Diffusion Models: A Sample Complexity Perspective, Aadithya Srikanth et al. (2026). Generalizes the continuous-state minimax estimation and sample-complexity framework of the source to discrete-state Markov chain diffusion models.
Paper: A Mathematical Introduction to Diffusion Models, Jianfeng Lu (2026). Provides a comprehensive mathematical treatment connecting learned score estimation errors and discretization bounds to rigorous total sampling error decompositions.
Paper: Score-Based Diffusion Models in Function Space, Jae Hyun Lim 0001 et al. (2025). Extends continuous score-based generative estimation from finite-dimensional Euclidean distributions to infinite-dimensional function spaces.
Paper: An exact information theory of generalization phase transitions in Bayesian diffusion models, Henry Hunt et al. (2026). Develops an information-theoretic framework to further explain how score-based models overcome the curse of dimensionality and achieve statistical generalization.
Paper: Stochastic Interpolants: A Unifying Framework for Flows and Diffusions, Michael S. Albergo et al. (2025). Unifies score-based diffusion density estimation with continuous deterministic flow matching across finite time horizons.
Paper: There and Back Again: Bidirectional Diffusion Bridges for Multimodality Translation, Gabe Guo et al. (2026). Builds upon continuous-time score matching theory to establish population-optimal bidirectional diffusion bridge processes for cross-domain translation.

Cover for Diffusion Models are Minimax Optimal Distribution Estimators

Abstract

While efficient distribution learning is no doubt behind the groundbreaking success of diffusion modeling, its theoretical guarantees are quite limited. In this paper, we provide the first rigorous analysis on approximation and generalization abilities of diffusion modeling for well-known function spaces. The highlight of this paper is that when the true density function belongs to the Besov space and the empirical score matching loss is properly minimized, the generated data distribution achieves the nearly minimax optimal estimation rates in the total variation distance and in the Wasserstein distance of order one. Furthermore, we extend our theory to demonstrate how diffusion models adapt to low-dimensional data distributions. We expect these results advance theoretical understandings of diffusion modeling and its ability to generate verisimilar outputs.

Topics

diffusion probabilistic models estimation method

Keywords

diffusion models minimax optimal estimation rates density estimation distribution recovery estimation error bounds statistical learning theory total variation distance Wasserstein distance diffusion process

1. Introduction
1.1. Our contributions
1.2. Other related works
2. Preliminaries
2.1. Assumptions
3. Approximation of the true score
3.1. Proof overview
4. Generalization of the score network
4.1. Sampling t and x t instead of taking expectation
5. Estimation error analysis
5.1. Estimation rates in TV
5.2. Estimation rates in W 1
5.3. Discussion on the discretization error
6. Error analysis with intrinsic dimensionality
7. Conclusion
Acknowledgements
References
A. Several high-probability bounds on the backward paths
A.1. Bounds on ∥ Y t ∥ and ∥ ∆ Y t ∥ with high probability
A.2. Bounds on p t ( x )
A.3. Bounds on the derivatives of p t ( x ) and the score
B. Approximation of the score function
B.1. Approximation of m t and σ t
B.2. Approximation via the diffused B-spline basis
B.3. Approximation error bound: based on p 0
B.4. Approximation error bound: using the induced smoothness
C. Generalization of the score network
C.1. Bounding sup-norm
C.2. Covering number evaluation
C.3. Generalization error bound on the score matching loss
C.4. Sampling t and x t instead of taking expectation
D. Estimation error analysis
D.1. Estimation bounds in the TV distance
D.2. Estimation rate in the W 1 distance
D.3. Discussion on the discretization error
E. Error analysis with intrinsic dimensionality
E.1. Brief proof overview
E.2. Proof of Theorem 6.4
F. Auxiliary lemmas
F.1. Construction of a larger neural network
F.2. Basic neural network structure that approximates rational functions
F.3. How to deal with exponential functions
F.4. Existing results for approximation
F.5. Elementary bounds for the Gaussian and hitting time

Knowls

Knowl 1 — Minimax Optimal Density Estimation in Total Variation Distance via Diffusion Models
theoretical result
Let $p_0$ be an unknown true probability density on $\mathbb{R}^d$ supported on $[-1, 1]^d$ , satisfying $C_f^{-1} \le p_0(x) \le C_f$ for a constant $C_f > 0$ , belonging to the Besov space ball $U(B^s_{p,q}([-1, 1]^d); C)$ with $0 < p, q \le \infty$ and smoothness index $s > d(1/p - 1/2)_+$ , and having smooth decay near the boundary $[-1, 1]^d \setminus [-1+a_0, 1-a_0]^d$ with $a_0 \approx n^{-\frac{1}{d+2s}}$ .

Let $\hat{s}$ be a deep ReLU neural network estimator trained on $n$ i.i.d. data points by minimizing the empirical denoising score matching loss over the hypothesis class $\mathcal{S} \subset \Phi(L, W, S, B)$ . The distribution $p_{\hat{Y}}$ produced by the modified backward Ornstein-Uhlenbeck process initialized at $\hat{Y}_0 \sim \mathcal{N}(0, I_d)$ and integrated over $[0, \bar{T}-\underline{T}]$ with early stopping $\underline{T} = n^{-O(1)}$ and terminal time $\bar{T} = \frac{s \log n}{\beta(d+2s)}$ achieves the expected total variation (TV) error:

$\mathbb{E}[\mathrm{TV}(p_0, p_{\hat{Y}})] \lesssim n^{-\frac{s}{d+2s}} \log^8 n.$

This estimation rate is minimax optimal up to logarithmic factors, matching the non-parametric minimax lower bound for the Besov class:

$\inf_{\hat{\mu}} \sup_{p \in B^s_{p,q}([-1, 1]^d)} \mathbb{E}[\mathrm{TV}(\hat{\mu}, p)] \gtrsim n^{-\frac{s}{d+2s}},$

where $\hat{\mu}$ ranges over all distribution estimators constructed from $n$ observations.
Knowl 2 — Nearly Minimax Optimal 1-Wasserstein Estimation via Time-Switching Score Networks
theoretical result
For a true data density $p_0 \in B^s_{p,q}([-1, 1]^d)$ with $d \ge 2$ , $p, q \ge 1$ , and $s > 0$ , the minimax lower bound in 1-Wasserstein distance is:

$\inf_{\hat{\mu}} \sup_{p \in B^s_{p,q}} \mathbb{E}[W_1(\hat{\mu}, p)] \gtrsim n^{-\frac{s+1}{d+2s}}.$

A standard single score network achieves only $n^{-\frac{s}{d+2s}}$ in $W_1$ . Diffusion modeling achieves the nearly optimal rate $n^{-\frac{s+1-\delta}{d+2s}}$ for any fixed $\delta > 0$ by partitioning the time domain into $K_* = O(\log n)$ dyadic intervals $t_0 = \underline{T} < t_1 = 2n^{-\frac{2-\delta}{d+2s}} < \dots < t_{K_*} = \bar{T} - \underline{T}$ (with $t_{i+1}/t_i \le 2$ ) and learning tailored score networks $\hat{s}_i$ on each interval $[t_i, t_{i+1}]$ .

For each interval $i \ge 1$ , the network is trained to minimize the score matching loss restricted to $[t_i, t_{i+1}]$ . Because the transportation distance moved by backward trajectories from time $\bar{T}-t_i$ to $\bar{T}-\underline{T}$ scales with $\sqrt{t_i}$ , the contribution of score errors at small $t_i$ to the final $W_1$ distance is discounted:

$W_1(\bar{Y}^{(i-1)}_{\bar{T}-\underline{T}}, \bar{Y}^{(i)}_{\bar{T}-\underline{T}}) \lesssim \sqrt{t_i \log n} \left( \mathbb{E}\left[ \int_{t_{i-1}}^{t_i} \mathbb{E}_{X_t \sim p_t}[\|\hat{s}_i(X_t, t) - \nabla \log p_t(X_t)\|^2] dt \right] \right)^{1/2} + n^{-\frac{s+1}{d+2s}}.$

Summing the discounted errors over all $K_*$ intervals with $\underline{T} \lesssim n^{-\frac{2(s+1)}{d+2s}}$ and $\bar{T} = \frac{(s+1)\log n}{\beta(d+2s)}$ yields:

$\mathbb{E}[W_1(p_0, p_{\hat{Y}})] \lesssim n^{-\frac{s+1-\delta}{d+2s}}.$
Knowl 3 — Generalization Error Bound for Empirical Denoising Score Matching with Deep ReLU Networks
theoretical result
Given $n$ training samples $\{x_{0,i}\}_{i=1}^n \stackrel{\text{i.i.d.}}{\sim} p_0$ , the empirical score estimator $\hat{s}$ is obtained by minimizing the empirical denoising score matching loss:

$\hat{s} \in \arg\min_{s \in \mathcal{S}} \frac{1}{n} \sum_{i=1}^n \int_{\underline{T}}^{\bar{T}} \mathbb{E}_{X_t \sim p_t(\cdot \mid x_{0,i})}\left[ \|s(X_t, t) - \nabla \log p_t(X_t \mid x_{0,i})\|^2 \right] dt,$

over the bounded ReLU neural network class $\mathcal{S} = \{ \phi \in \Phi(L, W, S, B) : \|\phi(\cdot, t)\_\infty \lesssim \frac{\log^{1/2} n}{\sigma_t} \}$ .

For a target network size parameter $N = n^{\frac{d}{d+2s}}$ , with depth $L = O(\log^4 N)$ , maximum width $\|W\|_\infty = O(N \log^6 N)$ , sparsity constraint $S = O(N \log^8 N)$ , and norm bound $B = \exp(O(\log N \log \log N))$ , the expected $L^2(p_t)$ -score estimation error over $[\underline{T}, \bar{T}]$ satisfies:

$\mathbb{E}_{\{x_{0,i}\}_{i=1}^n} \left[ \int_{\underline{T}}^{\bar{T}} \int_{\mathbb{R}^d} \|\hat{s}(x, t) - \nabla \log p_t(x)\|^2 p_t(x) dx dt \right] \lesssim n^{-\frac{2s}{d+2s}} \log^{16} n.$

This bound is established by proving the equivalence between explicit and denoising score matching in expectation, bounding the uniform loss over the network class by $\sup_{s \in \mathcal{S}} \|\ell_s\|_\infty \lesssim \log^2 n$ , and bounding the covering entropy of the induced loss class $\mathcal{L} = \{ \ell_s : s \in \mathcal{S} \}$ by $\log \mathcal{N}(\mathcal{L}, \|\cdot\|_{L^\infty}, \varepsilon) \lesssim S L \log(\varepsilon^{-1} L \|W\|_\infty B n)$ .
Knowl 4 — Diffusion Models Avoid the Curse of Dimensionality Under the Manifold Hypothesis
theoretical result
Suppose the true data distribution $p_0$ on $\mathbb{R}^d$ is supported on a $d'$ -dimensional linear subspace $V = \{ y \in \mathbb{R}^d : \exists z \in \mathbb{R}^{d'} \text{ s.t. } y = Az \}$ , where $A \in \mathbb{R}^{d \times d'}$ is an orthogonal column matrix with $d' \le d$ . Let $q$ denote the probability density of $p_0$ on $V$ in canonical coordinates, satisfying $q \in U(B^s_{p,q}([-1, 1]^{d'}))$ with $C_f^{-1} \le q(z) \le C_f$ on $[-1, 1]^{d'}$ and smooth boundary decay.

The score function of the diffused distribution $p_t$ on $\mathbb{R}^d$ factors into intrinsic and orthogonal components:

$\nabla \log p_t(x) = \nabla \log p_t^{(1)}(x) + \nabla \log p_t^{(2)}(x) = A \nabla \log q_t(A^\top x) - \frac{1}{\sigma_t^2}(I_d - A A^\top)x,$

where $q_t$ is the diffused distribution on $\mathbb{R}^{d'}$ from initial density $q$ .

By approximating the intrinsic score $\nabla \log q_t$ using a $d'$ -dimensional score network and combining it with a network realizing the linear projection drift along $V^\perp$ , the generated distribution $p_{\hat{Y}}$ trained with $n$ samples achieves:

$\mathbb{E}[W_1(p_0, p_{\hat{Y}})] \lesssim n^{-\frac{s+1-\delta}{d'+2s}},$

for any fixed $\delta > 0$ . The exponent depends strictly on the intrinsic dimension $d'$ rather than the ambient dimension $d$ , showing that diffusion models adapt to low-dimensional structures.
Knowl 5 — Score Function Approximation in Besov Spaces via Deep ReLU Networks
theoretical result
Let $p_0 \in U(B^s_{p,q}([-1, 1]^d); C)$ with $s > d(1/p - 1/2)_+$ , and consider the Ornstein-Uhlenbeck forward process yielding marginal density $p_t(x) = \int p_0(y) \frac{1}{\sigma_t^d (2\pi)^{d/2}} \exp\left(-\frac{\|x-m_t y\|^2}{2\sigma_t^2}\right) dy$ .

For any $\delta > 0$ and network size parameter $N \gg 1$ , with early stopping time $\underline{T} = \mathrm{poly}(N^{-1})$ and $\bar{T} \simeq \log N$ , there exists a deep ReLU network $\phi_{\mathrm{score}} \in \Phi(L, W, S, B)$ satisfying:

$\int_{\mathbb{R}^d} p_t(x) \|\phi_{\mathrm{score}}(x, t) - \nabla \log p_t(x)\|^2 dx \lesssim \frac{N^{-2s/d} \log N}{\sigma_t^2}, \quad \forall t \in [\underline{T}, \bar{T}],$

with network parameters $L = O(\log^4 N)$ , $\|W\|_\infty = O(N \log^6 N)$ , $S = O(N \log^8 N)$ , $B = \exp(O(\log N \log \log N))$ , and $\|\phi_{\mathrm{score}}(\cdot, t)\_\infty = O(\sigma_t^{-1} \log^{1/2} N)$ .

Additionally, due to noise-induced smoothing, for any $t \ge 2t_*$ with $t_* \ge N^{-(2-\delta)/d}$ , a network $\phi'_{\mathrm{score}}$ with sparsity $S = O(N')$ for $N' \ge t_*^{-d/2} N^{\delta/2}$ achieves the faster approximation rate:

$\int_{\mathbb{R}^d} p_t(x) \|\phi'_{\mathrm{score}}(x, t) - \nabla \log p_t(x)\|^2 dx \lesssim \frac{N^{-\frac{2(s+1)}{d}}}{\sigma_t^2}.$
Knowl 6 — Diffused B-Spline Basis for Neural Score Function Approximation
model/method
To approximate the true score $\nabla \log p_t(x) = \frac{\nabla p_t(x)}{p_t(x)}$ for $p_0 \in B^s_{p,q}([-1, 1]^d)$ , the data density is expanded in tensor-product cardinal B-splines $M_{k,j}^d(x) = \prod_{i=1}^d N_m(2^{k_i} x_i - j_i)$ as $p_0(x) \approx f_N(x) = \sum_{(k,j)} \alpha_{(k,j)} M_{k,j}^d(x)$ . Convolving this expansion with the Gaussian transition kernel $K_t(x \mid y) = \frac{1}{\sigma_t^d (2\pi)^{d/2}} \exp\left(-\frac{\|x - m_t y\|^2}{2\sigma_t^2}\right)$ produces the diffused density and score representations via the tensor-product diffused B-spline bases:

$E_{k,j}^{(1)}(x, t) = \int_{\mathbb{R}^d} 1_{\{\|y\|_\infty \le 1\}} M_{k,j}^d(y) K_t(x \mid y) dy = \prod_{i=1}^d D_{k,j_i}(x_i, t),$

$E_{k,j}^{(2)}(x, t) = \int_{\mathbb{R}^d} \frac{x - m_t y}{\sigma_t} 1_{\{\|y\|_\infty \le 1\}} M_{k,j}^d(y) K_t(x \mid y) dy,$

where the 1D diffused B-spline basis is defined as:

$D_{k,j}(x_i, t) = \int_{\mathbb{R}} \frac{N_m(2^k y_i - j)}{\sigma_t \sqrt{2\pi}} \exp\left(-\frac{(x_i - m_t y_i)^2}{2\sigma_t^2}\right) dy_i.$

Deep ReLU networks approximate $D_{k,j}(x_i, t)$ and $E_{k,j}^{(1)}, E_{k,j}^{(2)}$ by clipping the integration interval to $a_i^{x,t} = [\frac{x_i}{m_t} \pm \frac{\sigma_t C_f}{m_t}\sqrt{\log \varepsilon^{-1}}]$ , performing local Taylor expansions of the exponential term, and implementing multiplications, reciprocals, and divisions via poly-logarithmic sub-networks.
Knowl 7 — Ornstein-Uhlenbeck Forward and Backward Diffusion Modeling Framework
definition
The forward diffusion process $(X_t)_{t \in [0, \bar{T}]}$ on $\mathbb{R}^d$ is governed by the Ornstein-Uhlenbeck (OU) SDE:

$dX_t = -\beta_t X_t dt + \sqrt{2\beta_t} dB_t, \quad X_0 \sim p_0,$

where $B_t$ is standard $d$ -dimensional Brownian motion and $\beta_t: [0, \bar{T}] \to \mathbb{R}_+$ is a positive weighting function satisfying $0 < \underline{\beta} \le \beta_t \le \bar{\beta}$ .

The conditional transition distribution is Gaussian: $X_t \mid X_0 \sim \mathcal{N}(m_t X_0, \sigma_t^2 I_d)$ , with mean factor $m_t = \exp\left(-\int_0^t \beta_s ds\right)$ and variance $\sigma_t^2 = 1 - \exp\left(-2\int_0^t \beta_s ds\right)$ , satisfying $1 - m_t \simeq t \wedge 1$ and $\sigma_t \simeq \sqrt{t \wedge 1}$ .

The time-reversed process $(Y_t)_{t \in [0, \bar{T}]}$ with $Y_t = X_{\bar{T}-t}$ satisfies:

$dY_t = \beta_{\bar{T}-t}\left( Y_t + 2\nabla \log p_{\bar{T}-t}(Y_t) \right)dt + \sqrt{2\beta_{\bar{T}-t}} dB_t, \quad Y_0 \sim p_{\bar{T}}.$

Given an empirical score estimator $\hat{s}(x, t) \approx \nabla \log p_t(x)$ , the generative model implements the modified reverse process $(\hat{Y}_t)_{t \in [0, \bar{T}-\underline{T}]}$ initialized with standard Gaussian noise $\hat{Y}_0 \sim \mathcal{N}(0, I_d)$ :

$d\hat{Y}_t = \beta_{\bar{T}-t}\left( \hat{Y}_t + 2\hat{s}(\hat{Y}_t, \bar{T}-t) \right)dt + \sqrt{2\beta_{\bar{T}-t}} dB_t.$
Knowl 8 — Discretization Error Bound for Backward Diffusion Sampling
theoretical result
Let $\underline{T} = t_0 < t_1 < \dots < t_K = \bar{T}$ be a discrete time grid with uniform step size $\eta = t_{k+1} - t_k$ . The discrete-time backward process $(Y^\mathrm{d}_t)_{t \in [0, \bar{T}-\underline{T}]}$ with $Y^\mathrm{d}_0 \sim \mathcal{N}(0, I_d)$ is defined on each interval $t \in [\bar{T}-t_{k+1}, \bar{T}-t_k]$ by holding the score drift constant at the discretized time step:

$dY^\mathrm{d}_t = \beta_t\left( Y^\mathrm{d}_t + 2\hat{s}(Y^\mathrm{d}_{\bar{T}-t_k}, \bar{T}-t_k) \right) dt + \sqrt{2\beta_{\bar{T}-t}} dB_t.$

When the score network $\hat{s}$ is trained by score matching evaluated at the discrete time steps $\{t_k\}_{k=1}^K$ , with $\underline{T} = n^{-O(1)}$ and $\bar{T} = \frac{s \log n}{\beta(2s+d)}$ , the expected total variation error between the true data distribution $X_0 \sim p_0$ and the generated sample $Y^\mathrm{d}_{\bar{T}-\underline{T}}$ satisfies:

$\mathbb{E}[\mathrm{TV}(X_0, Y^\mathrm{d}_{\bar{T}-\underline{T}})] \lesssim \tilde{O}\left( \eta^2 \underline{T}^{-3} + n^{-\frac{s}{d+2s}} \right).$

Selecting a step size $\eta = \underline{T}^{1.5} n^{-\frac{s}{d+2s}} = \mathrm{poly}(n^{-1})$ guarantees that the discretization error is dominated by the optimal statistical estimation rate $n^{-\frac{s}{d+2s}}$ .
Knowl 9 — Denoising Score Matching with Time-Distribution Importance Sampling
model/method
When expectations over $t \in [\underline{T}, \bar{T}]$ and $X_t \sim p_t(\cdot \mid x_{0,i})$ in score matching are approximated via finite Monte Carlo sampling, uniform sampling $t_j \sim \mathrm{Unif}[\underline{T}, \bar{T}]$ suffers from exploding variance as $t \to 0$ , requiring $M = \Omega(n \underline{T}^{-1})$ samples per data point.

To achieve statistical efficiency with only $M = n$ total samples, time points $t_j$ are sampled from the importance distribution $\mu(t) \propto \frac{1_{[\underline{T}, \bar{T}]}(t)}{t}$ , data sample indices $i_j \sim \mathrm{Unif}(\{1, \dots, n\})$ , and perturbed points $X_{t_j} \sim p_{t_j}(\cdot \mid x_{0,i_j})$ . The score network is trained by minimizing the weighted empirical objective:

$\hat{s} \in \arg\min_{s \in \mathcal{S}} \frac{1}{M} \sum_{j=1}^M \lambda(t_j) \|s(X_{t_j}, t_j) - \nabla \log p_{t_j}(X_{t_j} \mid x_{0,i_j})\|^2,$

with modified weighting function $\lambda(t) = \frac{t \log(\bar{T}/\underline{T})}{\bar{T} - \underline{T}}$ .

Under this weighting, $\lambda(t_j)\|s(X_{t_j}, t_j) - \nabla \log p_{t_j}(X_{t_j} \mid x_{0,i_j})\|^2 = \tilde{O}(1)$ with high probability, and for $M = n$ , the score generalization error bound matches the exact-expectation rate:

$\mathbb{E} \left[ \frac{1}{n} \sum_{i=1}^n \ell_{\hat{s}}(x_{0,i}) - \inf_{s \in \mathcal{S}} \frac{1}{n} \sum_{i=1}^n \ell_s(x_{0,i}) \right] \lesssim n^{-\frac{2s}{d+2s}} \log^{17} n.$
Knowl 10 — Structural Data Assumptions for Minimax Optimal Diffusion Density Estimation
assumption
The theoretical convergence results for diffusion modeling as a distribution estimator require four structural conditions on the data density $p_0$ and the forward process parameters:
1. Bounded Support and Density Bounds: $p_0$ is supported on $[-1, 1]^d$ , and there exists a constant $C_f > 0$ such that $C_f^{-1} \le p_0(x) \le C_f$ for all $x \in [-1, 1]^d$ .
2. Besov Space Regularity: $p_0$ restricted to $[-1, 1]^d$ belongs to the Besov ball $U(B^s_{p,q}([-1, 1]^d); C)$ for $0 < p, q \le \infty$ and smoothness index $s > d(1/p - 1/2)_+$ .
3. Boundary Region Smoothness: For a boundary parameter $a_0 = N^{-\frac{1-\delta}{d}} \approx n^{-\frac{1}{d+2s}}$ , $p_0$ restricted to the boundary strip $[-1, 1]^d \setminus [-1+a_0, 1-a_0]^d$ belongs to $U(C^\infty([-1, 1]^d \setminus [-1+a_0, 1-a_0]^d))$ .
4. Drift Schedule Smoothness: The weighting function $\beta_t: [0, \bar{T}] \to \mathbb{R}_+$ satisfies $0 < \underline{\beta} \le \beta_t \le \bar{\beta}$ and belongs to $U(C^\infty([0, \bar{T}]); 1)$ as a function of $t$ .

Coverage note — Auxiliary network construction lemmas (such as Taylor series polynomial approximation, network parallelization/concatenation, and elementary Gaussian tail integrals) from Appendix F were omitted as they are standard technical tools.

References

1.Amann, H., Bourguignon, J., Grove, K., Lions, P., Araki, H., Brezzi, F., Chang, K., Hitchin, N., Hofer, H., Knörrer, H., et al. Monographs in mathematics vol. 99. 1983.
2.Arora, S., Cohen, N., Hu, W., and Luo, Y. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
3.Bakry, D., Gentil, I., Ledoux, M., et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
4.Barron, A. R. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory, 39(3):930–945, 1993.
5.Batzolis, G., Stanczuk, J., and Schönlieb, C.-B. Your diffusion model secretly knows the dimension of the data manifold. arXiv preprint arXiv:2212.12611, 2022.
6.Block, A., Mroueh, Y., and Rakhlin, A. Generative modeling with denoising auto-encoders and langevin sampling. arXiv preprint arXiv:2002.00107, 2020.
7.Boullé, N., Nakatsukasa, Y., and Townsend, A. Rational neural networks. Advances in Neural Information Processing Systems, 33:14243–14253, 2020.
8.Chang, S.-H., Cosman, P. C., and Milstein, L. B. Chernoff-type bounds for the gaussian error function. IEEE Transactions on Communications, 59(11):2939–2944, 2011.
9.Chen, M., Huang, K., Zhao, T., and Wang, M. Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data. arXiv preprint arXiv:2302.07194, 2023a.
10.Chen, N., Zhang, Y., Zen, H., Weiss, R. J., Norouzi, M., and Chan, W. Wavegrad: Estimating gradients for waveform generation. In International Conference on Learning Representations, 2020.
11.Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023b. URL https://openreview.net/forum?id=zyLVMgsZ0U_.
12.De Bortoli, V. Convergence of denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022. URL https://openreview.net/forum?id=MhK5aXo3gB.
13.De Bortoli, V., Thornton, J., Heng, J., and Doucet, A. Diffusion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34:17695–17709, 2021.
14.DeVore, R. A. and Popov, V. A. Interpolation of Besov spaces. Transactions of the American Mathematical Society, 305(1):397–414, 1988.
15.Dhariwal, P. and Nichol, A. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34:8780–8794, 2021.
16.Dudley, R. M. The speed of mean glivenko-cantelli convergence. The Annals of Mathematical Statistics, 40(1): 40–50, 1969.
17.Fefferman, C., Mitter, S., and Narayanan, H. Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4):983–1049, 2016.
18.Glorot, X., Bordes, A., and Bengio, Y. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 315–323. JMLR Workshop and Conference Proceedings, 2011.
19.Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial networks. Communications of the ACM, 63(11):139–144, 2020.
20.Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
21.Haussmann, U. G. and Pardoux, E. Time Reversal of Diffusions. The Annals of Probability, 14(4):1188–1205, 1986. doi: 10.1214/aop/1176992362. URL https://doi.org/10.1214/aop/1176992362.
22.Hayakawa, S. and Suzuki, T. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, 123:343–361, 2020.
23.Ho, J., Jain, A., and Abbeel, P. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840–6851, 2020.
24.Ho, J., Salimans, T., Gritsenko, A., Chan, W., Norouzi, M., and Fleet, D. J. Video diffusion models. arXiv:2204.03458, 2022.
25.Hyvärinen, A. and Dayan, P. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
26.Ibragimov, I. A. and Khas'minskii, R. Z. More on the estimation of distribution densities. Journal of Soviet Mathematics, 25:1155–1165, 1984.
27.Karatzas, I., Karatzas, I., Shreve, S., and Shreve, S. E. Brownian motion and stochastic calculus, volume 113. Springer Science & Business Media, 1991.
28.Kong, Z., Ping, W., Huang, J., Zhao, K., and Catanzaro, B. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations, 2020.
29.Lee, H., Lu, J., and Tan, Y. Convergence of score-based generative modeling for general data distributions. In NeurIPS 2022 Workshop on Score-Based Methods, 2022a.
30.Lee, H., Lu, J., and Tan, Y. Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems, 2022b.
31.Lei, J. Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767–798, 2020.
32.Liang, T. How well can generative adversarial networks learn densities: A nonparametric view. arXiv preprint arXiv:1712.08244, 2017.
33.Meier, L., Van de Geer, S., and Bühlmann, P. High-dimensional additive modeling. 2009.
34.Mhaskar, H. N. and Micchelli, C. A. Approximation by superposition of sigmoidal and radial basis functions. Advances in Applied mathematics, 13(3):350–373, 1992.
35.Nair, V. and Hinton, G. E. Rectified linear units improve restricted boltzmann machines. In Icml, 2010.
36.Nakada, R. and Imaizumi, M. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. J. Mach. Learn. Res., 21(174):1–38, 2020.
37.Niles-Weed, J. and Berthet, Q. Minimax estimation of smooth densities in Wasserstein distance. The Annals of Statistics, 50(3):1519–1540, 2022.
38.Oono, K. and Suzuki, T. Approximation and non-parametric estimation of resnet-type convolutional neural networks. In International conference on machine learning, pp. 4922–4931. PMLR, 2019.
39.Petersen, P. and Voigtlaender, F. Optimal approximation of piecewise smooth functions using deep relu neural networks. Neural Networks, 108:296–330, 2018.
40.Petersen, P. and Voigtlaender, F. Equivalence of approximation by convolutional neural networks and fully-connected networks. Proceedings of the American Mathematical Society, 148(4):1567–1581, 2020.
41.Pidstrigach, J. Score-based generative models detect manifolds. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=AiNrnIrDfD9.
42.Ramesh, A., Dhariwal, P., Nichol, A., Chu, C., and Chen, M. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06125, 2022.
43.Ronneberger, O., Fischer, P., and Brox, T. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pp. 234–241. Springer, 2015.
44.Schmidt-Hieber, J. Deep relu network approximation of functions on a manifold. arXiv preprint arXiv:1908.00695, 2019.
45.Schmidt-Hieber, J. Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 48(4):1875–1897, 2020.
46.Schreuder, N., Brunel, V.-E., and Dalalyan, A. Statistical guarantees for generative models without domination. In Algorithmic Learning Theory, pp. 1051–1071. PMLR, 2021.
47.Singh, S. and Póczos, B. Minimax distribution estimation in Wasserstein distance. arXiv preprint arXiv:1802.08855, 2018.
48.Singh, S., Uppal, A., Li, B., Li, C.-L., Zaheer, M., and Póczos, B. Nonparametric density estimation under adversarial losses. Advances in Neural Information Processing Systems, 31, 2018.
49.Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pp. 2256–2265. PMLR, 2015.
50.Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
51.Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2020.
52.Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822–2878, 2018.
53.Suzuki, T. Adaptivity of deep relu network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representations, 2018.
54.Suzuki, T. and Nitanda, A. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. Advances in Neural Information Processing Systems, 34:3609–3621, 2021.
55.Telgarsky, M. Neural networks and rational functions. In International Conference on Machine Learning, pp. 3387–3393. PMLR, 2017.
56.Tenenbaum, J. B., Silva, V. d., and Langford, J. C. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319–2323, 2000.
57.Triebel, H. Entropy numbers in function spaces with mixed integrability. Revista matemática complutense, 24(1):169–188, 2011.
58.Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer series in statistics. Springer, 2009. ISBN 978-0-387-79051-0. doi: 10.1007/b13794. URL https://doi.org/10.1007/b13794.
59.Vahdat, A., Kreis, K., and Kautz, J. Score-based generative modeling in latent space. Advances in Neural Information Processing Systems, 34:11287–11302, 2021.
60.Vincent, P. A connection between score matching and denoising autoencoders. Neural computation, 23(7):1661–1674, 2011.
61.Weed, J. and Bach, F. Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25(4A):2620–2648, 2019.
62.Yang, Y. and Barron, A. Information-theoretic determination of minimax rates of convergence. Annals of Statistics, pp. 1564–1599, 1999.
63.Yarotsky, D. Error bounds for approximations with deep relu networks. Neural Networks, 94:103–114, 2017.
64.Zhou, D.-X. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):787–794, 2020.

Citation

MLA

Oko, K., et al. “Diffusion Models Are Minimax Optimal Distribution Estimators”. International Conference on Machine Learning, vol. 202, 2023, pp. 26517–82, https://proceedings.mlr.press/v202/oko23a.html.

APA

Oko, K., Akiyama, S., & Suzuki, T. (2023). Diffusion Models are Minimax Optimal Distribution Estimators. International Conference on Machine Learning, 202, 26517–26582. https://proceedings.mlr.press/v202/oko23a.html

Chicago

Oko, K., S. Akiyama, and T. Suzuki. 2023. “Diffusion Models Are Minimax Optimal Distribution Estimators”. International Conference on Machine Learning 202: 26517–82. https://proceedings.mlr.press/v202/oko23a.html.

Harvard

Oko, K., Akiyama, S. and Suzuki, T. (2023) “Diffusion Models are Minimax Optimal Distribution Estimators”, International Conference on Machine Learning. PMLR, pp. 26517–26582. Available at: https://proceedings.mlr.press/v202/oko23a.html.

Vancouver

1. Oko K, Akiyama S, Suzuki T (2023) Diffusion Models are Minimax Optimal Distribution Estimators. In: International Conference on Machine Learning. PMLR, pp 26517–26582

BibTeX

@InProceedings{pmlr-v202-oko23a,
  title = 	 {Diffusion Models are Minimax Optimal Distribution Estimators},
  author =       {Oko, Kazusato and Akiyama, Shunta and Suzuki, Taiji},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {26517--26582},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/oko23a/oko23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/oko23a.html},
  abstract = 	 {While efficient distribution learning is no doubt behind the groundbreaking success of diffusion modeling, its theoretical guarantees are quite limited. In this paper, we provide the first rigorous analysis on approximation and generalization abilities of diffusion modeling for well-known function spaces. The highlight of this paper is that when the true density function belongs to the Besov space and the empirical score matching loss is properly minimized, the generated data distribution achieves the nearly minimax optimal estimation rates in the total variation distance and in the Wasserstein distance of order one. Furthermore, we extend our theory to demonstrate how diffusion models adapt to low-dimensional data distributions. We expect these results advance theoretical understandings of diffusion modeling and its ability to generate verisimilar outputs.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Diffusion Models are Minimax Optimal Distribution Estimators

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Minimax Optimal Density Estimation in Total Variation Distance via Diffusion Models

Knowl 2 — Nearly Minimax Optimal 1-Wasserstein Estimation via Time-Switching Score Networks

Knowl 3 — Generalization Error Bound for Empirical Denoising Score Matching with Deep ReLU Networks

Knowl 4 — Diffusion Models Avoid the Curse of Dimensionality Under the Manifold Hypothesis

Knowl 5 — Score Function Approximation in Besov Spaces via Deep ReLU Networks

Knowl 6 — Diffused B-Spline Basis for Neural Score Function Approximation

Knowl 7 — Ornstein-Uhlenbeck Forward and Backward Diffusion Modeling Framework

Knowl 8 — Discretization Error Bound for Backward Diffusion Sampling

Knowl 9 — Denoising Score Matching with Time-Distribution Importance Sampling

Knowl 10 — Structural Data Assumptions for Minimax Optimal Diffusion Density Estimation

References

Citation

BibTeX

Access the Paper