Convergence in KL Divergence of the Inexact Langevin Algorithm with Application to Score-based Generative Models

Andre Wibisono, Kaylee Yingxi Yang

Abstract

We study the Inexact Langevin Dynamics (ILD), Inexact Langevin Algorithm (ILA), and Score-based Generative Modeling (SGM) when utilizing estimated score functions for sampling. Our focus lies in establishing stable biased convergence guarantees in terms of the Kullback-Leibler (KL) divergence. To achieve these guarantees, we impose two key assumptions: 1) the target distribution satisfies the log-Sobolev inequality (LSI), and 2) the score estimator exhibits a bounded Moment Generating Function (MGF) error. Notably, the MGF error assumption we adopt is more lenient compared to the $L^\infty$ error assumption used in existing literature. However, it is stronger than the $L^2$ error assumption utilized in recent works, which often leads to unstable bounds. We explore the question of how to obtain a provably accurate score estimator that satisfies the MGF error assumption. Specifically, we demonstrate that a simple estimator based on kernel density estimation fulfills the MGF error assumption for sub-Gaussian target distribution, at the population level.

Introduction

Sampling from a target distribution $\nu$ is a cornerstone of modern machine learning, particularly in generative modeling. Langevin-based algorithms achieve this by following the "score function"—the gradient of the log-density. However, in practical applications like Score-based Generative Models (SGM), the exact score is unknown and must be estimated, typically via neural networks. This raises a critical theoretical question: how does the error in score estimation affect the convergence and accuracy of the generated samples?

The Challenge of Error Metrics

Existing theoretical frameworks for inexact Langevin sampling generally fall into two categories, both with significant drawbacks:

  1. $L^\infty$ Error: Assumes the score error is bounded everywhere. While mathematically convenient, this is far too restrictive for real-world neural network estimators.
  2. $L^2$ Error: Assumes the error is small on average. While more realistic, this often leads to "unstable" bounds where the error in the final distribution grows indefinitely as the algorithm runs longer ($T \to \infty$).

The MGF Error Assumption: A Middle Ground

This paper introduces the Moment Generating Function (MGF) error assumption as a "Goldilocks" metric. It is more lenient than $L^\infty$ but stronger than $L^2$, requiring the score error to have sub-Gaussian tails. When combined with the assumption that the target distribution satisfies a Log-Sobolev Inequality (LSI), this metric allows for the derivation of stable, biased convergence bounds.

Convergence of Inexact Langevin Algorithms

The authors analyze both continuous-time (ILD) and discrete-time (ILA) versions of the algorithm. Under the MGF assumption, they prove that the distribution of the particles converges exponentially fast to a "bias floor" determined by the score estimation error.

Convergence rates for continuous and discrete Inexact Langevin Algorithms under LSI.

As shown in the table above, the bias term for the inexact cases is proportional to the MGF error $\epsilon_{mgf}^2$. For the discrete case, an additional term related to the step size $h$ appears, representing the discretization error.

Stability in Score-based Generative Models (SGM)

A major contribution of this work is providing the first stable convergence bound for SGM (specifically the DDPM variant) in KL divergence. Previous research using $L^2$ error metrics resulted in bounds that diverged as the number of steps $K$ increased. By utilizing the MGF assumption, the authors demonstrate that SGM eventually settles into a stable distribution near the target.

Comparison of convergence stability for SGM under different error assumptions.

The comparison highlights that while $L^2$-based bounds are unstable ("no"), the proposed MGF-based approach yields a stable ("yes") convergence result.

Provable Score Estimators

To bridge the gap between theory and practice, the authors show that a simple Kernel Density Estimator (KDE) satisfies the MGF error assumption at the population level for sub-Gaussian targets. This provides a concrete, provable example of a score estimator that fits within their theoretical framework.

Conclusion and Limitations

While this work provides a significant step forward in understanding the stability of generative models, several challenges remain. The analysis of the KDE estimator assumes infinite data (population level), and the reliance on the LSI constant may limit applicability to highly multimodal distributions where LSI constants are poor. Furthermore, extending these stable bounds from KL divergence to the stronger Rényi divergence remains an open problem for future research.

Summary updated

Abstract

We study the Inexact Langevin Dynamics (ILD), Inexact Langevin Algorithm (ILA), and Score-based Generative Modeling (SGM) when utilizing estimated score functions for sampling. Our focus lies in establishing stable biased convergence guarantees in terms of the Kullback-Leibler (KL) divergence. To achieve these guarantees, we impose two key assumptions: 1) the target distribution satisfies the log-Sobolev inequality (LSI), and 2) the score estimator exhibits a bounded Moment Generating Function (MGF) error. Notably, the MGF error assumption we adopt is more lenient compared to the $L^\infty$ error assumption used in existing literature. However, it is stronger than the $L^2$ error assumption utilized in recent works, which often leads to unstable bounds. We explore the question of how to obtain a provably accurate score estimator that satisfies the MGF error assumption. Specifically, we demonstrate that a simple estimator based on kernel density estimation fulfills the MGF error assumption for sub-Gaussian target distribution, at the population level.
BibTeX
@misc{wibisono2022convergence,
  author = {Andre Wibisono and Kaylee Yingxi Yang},
  title = {{Convergence in KL Divergence of the Inexact Langevin Algorithm with Application to Score-based Generative Models}},
  year = {2022},
  eprint = {2211.01512},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.01512},
}
Figure