From optimal score matching to optimal sampling

Zehao Dou, Subhodh Kotekal, Zhehao Xu, Harrison H. ZhouarXiv 2024 · OpenReview

Introduction

Score-based diffusion models have revolutionized generative modeling, enabling high-fidelity synthesis of images, audio, and video. These models operate by learning the "score function"—the gradient of the log-density of data perturbed by noise—and then reversing the diffusion process to generate new samples. Despite their empirical dominance, a significant gap has persisted between their practical performance and theoretical understanding. Specifically, existing bounds often included extraneous logarithmic factors or required "early stopping" of the reverse process, a practice not typically used by practitioners.

This research bridges that gap by establishing the first sharp minimax rates for both score estimation and density estimation. By analyzing $\alpha$-Hölder smooth densities, the authors demonstrate that diffusion models can achieve optimal statistical efficiency without the need for heuristic adjustments.

The Problem: Suboptimality and Early Stopping

Prior theoretical work on diffusion models faced three primary hurdles:

  1. Suboptimal Rates: Theoretical bounds often included $\text{poly}(\log n)$ terms, suggesting a lower efficiency than what is observed in practice.
  2. The Early Stopping Requirement: Mathematical singularities near zero noise led previous researchers to conclude that the reverse process must stop early. This contradicted the standard practice of running the diffusion process until the noise is fully removed.
  3. Boundary Effects: Estimating scores for densities with compact support (e.g., image data constrained to a specific range) is difficult near the boundaries.

Methodology: A Multi-Regime Analysis

The study focuses on the variance exploding SDE, where noise is added to a target density $f$ supported on a compact interval like $[-1, 1]$. To derive sharp rates, the authors decompose the noise level ($t$) into three distinct regimes:

  • Very High Noise ($t \gtrsim 1$): Handled via a regularized plug-in estimator.
  • High Noise ($n^{-2/(2\alpha+1)} \lesssim t \lesssim 1$): Addressed using an unbiased estimator with specific regularization.
  • Low Noise ($t \lesssim n^{-2/(2\alpha+1)}$): Managed through a novel kernel-based score estimator that leverages the underlying smoothness of the density.

For the lower bounds, the authors employ Fano’s method with a nonstandard construction of test densities, facilitating a rigorous application of the heat equation to prove that no estimator can surpass these rates.

Key Insights

A central discovery is the "self-normalizing" nature of the score function $s(x, t) = \nabla \log p(x, t)$. This property naturally mitigates the lack of regularity at the boundaries of the support, explaining why diffusion models are particularly robust when handling bounded data.

Furthermore, the analysis proves that early stopping is a limitation of previous proof techniques rather than a fundamental requirement of the diffusion framework. By using the proposed estimators, the score matching error can be integrated all the way to $t=0$. This aligns the theory with the actual implementation of these models in the field.

Main Results

The paper establishes the sharp minimax rate for estimating the score function of the diffused distribution $f * \mathcal{N}(0, t)$. For all $\alpha > 0$ and $t \ge 0$, the risk is bounded by: $$\frac{1}{nt^2} \wedge \frac{1}{nt^{3/2}} \wedge (t^{\alpha-1} + n^{-2(\alpha-1)/(2\alpha+1)})$$

Consequently, the law $\hat{f}$ of a sample generated from the diffusion model achieves the sharp minimax rate for density estimation in Total Variation (TV) distance: $$\mathbb{E}[d_{TV}(\hat{f}, f)^2] \lesssim n^{-\frac{2\alpha}{2\alpha+1}}$$

This result is significant because it matches the known lower bounds for non-parametric density estimation without any extra logarithmic terms, providing a "clean" theoretical guarantee for the efficiency of diffusion-based sampling.

Conclusion and Future Directions

While this work provides a rigorous foundation for 1D densities with compact support, several avenues for future research remain. The current theory focuses on the variance exploding SDE; extending these sharp rates to variance preserving SDEs (like the Ornstein-Uhlenbeck process) is a natural next step. Additionally, while the paper provides a framework for multivariate cases, further exploration of the "curse of dimensionality" and how diffusion models interact with low-dimensional data manifolds will be crucial for fully understanding their success in high-dimensional image generation.

Summary updated

Abstract

The recent, impressive advances in algorithmic generation of high-fidelity image, audio, and video are largely due to great successes in score-based diffusion models. A key implementing step is score matching, that is, the estimation of the score function of the forward diffusion process from training data. As shown in earlier literature, the total variation distance between the law of a sample generated from the trained diffusion model and the ground truth distribution can be controlled by the score matching risk. Despite the widespread use of score-based diffusion models, basic theoretical questions concerning exact optimal statistical rates for score estimation and its application to density estimation remain open. We establish the sharp minimax rate of score estimation for smooth, compactly supported densities. Formally, given \(n\) i.i.d. samples from an unknown \(\alpha\)-H\"{o}lder density \(f\) supported on \([-1, 1]\), we prove the minimax rate of estimating the score function of the diffused distribution \(f * \mathcal{N}(0, t)\) with respect to the score matching loss is \(\frac{1}{nt^2} \wedge \frac{1}{nt^{3/2}} \wedge (t^{\alpha-1} + n^{-2(\alpha-1)/(2\alpha+1)})\) for all \(\alpha > 0\) and \(t \ge 0\). As a consequence, it is shown the law \(\hat{f}\) of a sample generated from the diffusion model achieves the sharp minimax rate \(\bE(\dTV(\hat{f}, f)^2) \lesssim n^{-2\alpha/(2\alpha+1)}\) for all \(\alpha > 0\) without any extraneous logarithmic terms which are prevalent in the literature, and without the need for early stopping which has been required for all existing procedures to the best of our knowledge.
BibTeX
@misc{dou2024from,
  author = {Zehao Dou and Subhodh Kotekal and Zhehao Xu and Harrison H. Zhou},
  title = {{From optimal score matching to optimal sampling}},
  year = {2024},
  eprint = {2409.07032},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.07032},
}
Figure