Convergence for score-based generative modeling with polynomial complexity

Holden Lee; Jianfeng Lu; Yixin Tan

Source-linked AI summary

Convergence for score-based generative modeling with polynomial complexity

Holden Lee, Jianfeng Lu, Yixin Tan

arXiv:2206.06227v2Jun 13, 2022cs.LGmath.PRmath.STstat.ML

TL;DR

The paper addresses how to sample from a distribution using only an L2(p)-accurate score estimate, a setting where prior guarantees could suffer dimensionality or exponential-time dependence. It develops a general bad-set-based analysis for Langevin and reverse-SDE samplers, obtaining polynomial convergence guarantees and showing why annealing and predictor-corrector procedures help.

Problem
Prior theory for SGM with L2(p)-accurate scores could suffer curse-of-dimensionality or exponential-time dependence, while L∞-based analyses imposed stronger accuracy requirements.
Method
The paper analyzes discretized sampling with L2(p)-accurate scores by constructing a small-measure bad set and conditioning convergence on avoiding it.
Results
The analysis gives the first convergence bounds with polynomial dependence on running time, dimension, and distribution smoothness, with rates that are a fixed power of ε.
Takeaways & Limitations
Annealing supplies warm starts between noise levels, while predictor-corrector sampling improves parameter dependence by combining reverse-SDE prediction with Langevin correction.
Takeaways & Limitations
The guarantees require moderate-time runs, warm starts in χ2-divergence, smoothness, and a bounded log-Sobolev constant.

Abstract

from arXiv · show

Score-based generative modeling (SGM) is a highly successful approach for learning a probability distribution from data and generating further samples. We prove the first polynomial convergence guarantees for the core mechanic behind SGM: drawing samples from a probability density $p$ given a score estimate (an estimate of $\nabla \ln p$) that is accurate in $L^2(p)$. Compared to previous works, we do not incur error that grows exponentially in time or that suffers from a curse of dimensionality. Our guarantee works for any smooth distribution and depends polynomially on its log-Sobolev constant. Using our guarantee, we give a theoretical analysis of score-based generative modeling, which transforms white-noise input into samples from a learned data distribution given score estimates at different noise scales. Our analysis gives theoretical grounding to the observation that an annealed procedure is required in practice to generate good samples, as our proof depends essentially on using annealing to obtain a warm start at each step. Moreover, we show that a predictor-corrector algorithm gives better convergence than using either portion alone.

1 Introduction

Score-based generative modeling learns score functions for noisy data distributions and uses them to transform white noise into data samples. This paper develops polynomial convergence guarantees for SGM despite the challenges of L2(p)-accurate scores, using annealing and a unified analysis framework.

Background: SGM learns a score function for noisy versions of the data distribution, then substitutes it for the exact log-density gradient in an SDE-based sampler.The score is the gradient of the log probability density, and sampling algorithms such as Langevin Monte Carlo can use it to sample from the target distribution.
Background: Annealing uses noise levels to interpolate between an easy-to-sample prior and the data distribution, providing the warm starts needed for successful sampling.The forward SDE produces distributions across increasing noise scales, while the reverse procedure moves from the prior toward the data distribution.
Challenges for theory: Prior analyses faced curse-of-dimensionality or exponential-time dependence, and some required L∞-accurate scores or difficult auxiliary problems.These limitations arise despite extensive convergence theory for Langevin Monte Carlo and related algorithms.
Contributions: The paper introduces a general framework for L2(p)-accurate scores based on isolating a small-measure bad set and analyzing the discretized process conditioned on avoiding it.The framework supports end-to-end analyses of both annealed Langevin methods and reverse-SDE-based algorithms.
Contributions: The resulting convergence bounds have polynomial dependence on running time, dimension, and smoothness, with error rates that are a fixed power of the score-estimation accuracy.The guarantees assume smoothness and a bounded log-Sobolev constant, and are stated in total variation distance.

2 Results for Langevin dynamics with estimated score

The paper proves polynomial convergence guarantees for Langevin sampling with L2-accurate score estimates, then extends the analysis to annealed Langevin dynamics. The results require smoothness, a log-Sobolev condition, and warm starts, while annealing and predictor steps address these requirements.

Assumptions: The analysis assumes a C1, L-smooth log-density satisfying a log-Sobolev inequality, with a C1, Ls-Lipschitz score estimate.These assumptions support the Langevin diffusion analysis and are stated as weaker than earlier assumptions that included log-concavity.
Langevin dynamics with estimated score: Theorem 2.1 gives an error bound for Langevin Monte Carlo using an L2-accurate score estimate under a χ2 warm-start condition.The guarantee controls both total variation and χ2 error for a finite-time run.
Langevin dynamics with estimated score: TV(pT, p) ≤ 2εTV when the χ2 and TV target accuracies are set equal.The bound applies after choosing the step size and running the algorithm for the theorem’s prescribed moderate time.
Langevin dynamics with estimated score: The finite-time guarantee requires a warm start, because the stationary distribution of LMC with an L2-accurate score can be arbitrarily far from p.For fixed target errors, the required score accuracy depends inversely on the warm-start parameter Kχ.
Annealed Langevin dynamics: Annealed Langevin dynamics starts from a Gaussian prior and successively applies estimated-score LMC across decreasing noise levels to approximate the data distribution.The construction uses distributions pσ² = pdata * ϕσ² and returns the final sample after processing the noise levels from largest to smallest.
Annealed Langevin dynamics: Under Lipschitz-score assumptions for all noise scales, the annealed method can produce qT with TV(qT, pdata) < εTV.The theorem provides a suitable sequence of noise levels and algorithm parameters; the analysis uses a score estimate with error ε at every scale.
Annealed Langevin dynamics: The proof uses geometrically spaced noise levels, while a predictor step based on the reverse SDE improves the rate and time complexity over annealed Langevin correction alone.The predictor-corrector analysis is presented as the next improvement after the annealed Langevin result.

3 Results for reverse SDE’s with estimated score

The paper analyzes reverse-SDE predictors with L2-accurate score estimates and shows that combining predictor and corrector steps improves convergence dependence while achieving TV-accurate samples under stated assumptions.

Reverse SDE framework: The reverse-time SDE starts from an approximately Gaussian prior and aims to recover samples from the data distribution using the estimated score.The prior is chosen so the forward process approaches a distribution that can be sampled accurately, then the reverse process is simulated back toward the data distribution.
Predictor: The predictor discretizes the reverse SDE and tracks the sequence of evolving noisy distributions across time.The analysis uses constant step sizes after reversing and rescaling time; the relevant schedule dependence is expressed through the integral of g(s)^2.
Predictor: Under DDPM assumptions, the predictor with L2-accurate score estimates produces a distribution within εTV of pdata.The theorem assumes M2 = O(d), Lipschitz scores for every time, and score estimates satisfying the stated accuracy conditions.
Predictor-corrector: Corrector steps are LMC updates inserted after predictor steps to provide additional mixing as the target distribution changes.The resulting algorithm alternates reverse-SDE predictor updates with estimated-score LMC corrector updates before returning an approximate sample.
Predictor-corrector: The predictor-corrector method achieves TV error below εTV and improves parameter dependence by combining predictor warm starts with corrector error reduction.The predictor need only track the changing distribution with O(1) χ2 error, while final corrector steps reduce the error to the desired TV level.

4 Theoretical framework and proof sketches

The proof framework converts L2 score accuracy into an analyzable L∞ setting by excluding bad sets, then applies χ2 convergence bounds and warm-start arguments to establish the main results.

Proof framework: The framework converts an L2 score-error guarantee into an L∞ guarantee outside a small bad set.The bad set contains points where the score error exceeds ε1; its measure is controlled with Chebyshev’s inequality.
Proof framework: A coupling compares the estimated-score process with a hypothetical process having uniformly bounded error, and disagreement occurs when the bad set is hit.Bounding the probability of hitting the bad set produces the total-variation error contribution.
L∞ analysis: The L∞ analysis derives χ2 convergence using a continuous-time interpolation, a differential inequality, and the log-Sobolev inequality.The inaccurate gradient contributes an additional error term relative to exact-score analyses.
Limitations: The proof is inefficient because Chebyshev’s inequality controls the bad-set probability, and an Lp error bound with p > 2 could improve the result.The paper also requires sufficiently small predictor step sizes for exponential error decay.
Annealed LMC: Annealed Langevin sampling uses geometrically spaced noise levels to maintain O(1) χ2 divergence between successive distributions and obtain warm starts.The resulting warm-start parameter is Kχ = (M/εTV)^1/2, and TV errors from all levels add to O(εTV).
Predictor analysis: The predictor analysis has extra error terms because its target density evolves, but DDPM obtains better bounds than SMLD through stronger mixing behavior.For DDPM, the warm start improves exponentially rather than inversely with T, and its log-Sobolev constant remains uniformly bounded by that of pdata.

5 Conclusion

The paper develops a general framework yielding polynomial-complexity convergence bounds for SDE-based sampling with L2-accurate score estimates. It identifies multimodality, practical score-estimation accuracy, and learning guarantees as important directions for extending the analysis.

The framework gives the first convergence bounds for several score-based generative models with polynomial complexity in all parameters.The authors suggest that the analysis may extend to other SDEs and sampling algorithms beyond Langevin Monte Carlo.
The proof framework analyzes SDE-based sampling algorithms when an L2-error score estimate is available.The supplied proof passages describe interpolated processes, density evolution, and χ2-divergence calculations used in the analysis.
A bounded log-Sobolev constant limits the current multimodal-distribution analysis because it essentially restricts attention to distributions close to unimodal.The authors point to mixtures of distributions with bounded log-Sobolev constants as a possible extension.
The assumed O(1)-accurate L2 score estimate remains a strong and difficult-to-check practical condition for complex distributions such as images.The paper asks what weaker score-estimation condition could still yield reasonable samples.
The framework assumes an L2 estimate of the score function, leaving open when neural networks can learn such estimates.The paper identifies optimization and generalization as more challenging questions than representability alone.
The proof computations use interpolated processes and Fokker–Planck-based density evolution to analyze divergence between approximate and exact distributions.The derivation also uses integration by parts and bounds terms in the χ2-divergence evolution.

B Analysis for LMC

This section proves convergence for Langevin Monte Carlo using an L2-accurate score estimate. The argument requires a warm start and a moderate run time because the score-induced stationary distribution can remain far from the target.

If the score estimate has sufficiently small L2(p) error, LMC reaches a distribution close in TV distance to one close in χ2-divergence to p.The theorem is stated for a target density p, an estimated score s, and a starting distribution with a bounded χ2 divergence.
The algorithm must stop within an upper-bounded time window because its stationary distribution may be arbitrarily far from p despite bounded L2 score error.The paper instead exploits short- or medium-term improvement before the probability of entering the bad set grows.
The proof proceeds in two stages: first establish the L∞-error result, then control disagreement between the actual process and an auxiliary process at the bad set.The auxiliary-process construction supplies the coupling used in the L2-error theorem.
The proof reduces L2 error to an L∞-controlled analysis by defining a small-measure bad set where the score error is large.Away from this set, the L∞-error theorem applies; the remaining task is to bound the probability of hitting the bad set.
A warm start is required because the bound on the probability of hitting the bad set depends on the current χ2-divergence to p.The argument uses Cauchy–Schwarz to relate this probability to the bad-set mass and χ2 divergence.

B.1 LMC under L∞gradient error

The L∞-error analysis derives χ2-divergence convergence for LMC using interpolation and the log-Sobolev inequality. This result supports the later L2 analysis but also clarifies why an average-error bound alone is insufficient for the intermediate step.

The L∞-error theorem provides a long-time convergence bound for LMC with a score estimate whose gradient error is bounded everywhere.The paper notes that this result may be of independent interest.
The analysis also derives a stationary-distribution bound for Langevin diffusion with uniformly bounded score-estimation error.The stationary result follows by taking the iteration count to infinity and the step size to zero.
The proof interpolates the discrete LMC process and bounds the derivative of Rényi divergence using the target distribution’s log-Sobolev inequality.The inaccurate gradient contributes an additional error term alongside discretization error.
For the L2 theorem, the proof defines a bad set, replaces the estimated score by the exact gradient in an auxiliary process, and couples the two processes until the bad set is hit.Chebyshev’s inequality bounds the bad-set mass, while the coupling transfers the auxiliary-process control to LMC with the estimated score.

B.3 Proof of Theorem 2.2

The proof of the annealed LMC theorem propagates accuracy from a warm-started highest-noise distribution through a sequence of decreasing noise levels. It controls successive distributions using bounded χ2 divergence and TV error.

The annealed theorem constructs a geometric sequence of noise levels from σ_min to σ_M under Lipschitz score assumptions for every smoothed distribution.The theorem states that an appropriate sequence exists with a number of levels determined by the stated complexity bound.
The proof accounts for the number of annealing levels and the per-level iteration counts through the relations M = O(...) and T_M = 0, N_m = T_m/h.The supplied passages show these quantities as part of the theorem’s complexity bookkeeping.
At the final low-noise level, the algorithm outputs a sample from a distribution q whose TV distance to the corresponding smoothed target is bounded.The same conclusion is stated in the theorem’s result passage.
The successive smoothed distributions have O(1) χ2-divergence under the chosen noise schedule.This bounded divergence is the bridge used to continue the downward induction.
The highest-noise level provides a warm start, enabling the induction to begin from the prior distribution.The proof invokes the warm-start lemma and Theorem 2.1 at the largest noise scale.
The induction transfers closeness from level m+1 to level m using the closeness of the previous output to p_{m+1} and bounded χ2 divergence between successive smoothed distributions.Because χ2 divergence lacks a triangle inequality, the proof incurs an additional TV error.

C Analysis for SGM based on reverse SDE’s

This section formulates reverse-SDE sampling for score-based generative models, then replaces exact scores with estimates and continuous dynamics with a discretized interpolation.

The reverse SDE evolves white-noise input toward the data distribution when run from time 0 to T.The process starts from the terminal noisy distribution and exactly obtains the data distribution in the idealized continuous-time setting.
Discretized sampling uses an Euler-Maruyama predictor with step size h = T/N and independent Gaussian noise.The update combines the drift, estimated score, and Gaussian diffusion increments.
The interpolation process holds the estimated score at the previous discretization time while integrating the drift and diffusion within each interval.This construction enables exact integration of the drift and diffusion terms in SMLD and DDPM settings.
Running the interpolation reduces discretization error, so its final distribution is expected to approach the target process distribution.The analysis assumes the initial interpolation distribution is close to the initial target distribution.
The score estimate is assumed to satisfy a pointwise error bound ε_kh at every discretization time.The bound compares the estimated score with the exact score at time T − kh.
The analysis assumes g(t)^2 is Lipschitz on [0, T], an assumption satisfied by both SMLD and DDPM.

C.2 Predictor

The predictor analysis bounds one-step and accumulated sampling error under score-estimation assumptions, using χ2-divergence inequalities, log-Sobolev properties, and discretization-error control.

One-step predictor analysis: Theorem C.1 assumes Lipschitz exact and estimated scores, bounded score error, and log-Sobolev control of the evolving target distribution.Its bound depends on the time-varying log-Sobolev constant, second moments, dimension, smoothness, and score-estimation error.
Complexity conditions: For DDPM, the theorem imposes a step-size restriction involving the score smoothness and dimension terms.The corresponding argument combines the one-step theorem with log-Sobolev and second-moment bounds.
Model relationship: SMLD and DDPM are equivalent under time-and-space rescaling, although the stated SMLD parameterization yields slightly worse complexity.
One-step predictor analysis: The predictor proof derives a differential inequality for χ2(q_t||p_t) and applies Gronwall’s inequality to obtain convergence bounds.The discretization error is decomposed into terms A and B, which are bounded separately.
Discretization-error control: The discretization error is difficult because expectations are taken under a changed measure ψ_tq_t rather than directly under p_t.The proof uses change-of-measure bounds and the Donsker-Varadhan variational principle to control these expectations.
Discretization-error control: The proof controls the changed-measure terms using log-Sobolev inequalities, KL bounds, second-moment estimates, and Gaussian variance bounds.

C.7 Proof of Theorem 3.1

This section proves convergence of the predictor with an L2-accurate score estimate by isolating large-error regions, coupling processes, and converting χ2 control into total-variation control.

Theorem C.16 analyzes DDPM under an L2 score-estimation assumption for a smooth data distribution with M2 = O(d).It also assumes Lipschitz scores for every forward-SDE marginal.
The proof defines bad sets where the score-estimation error is large and uses an auxiliary process that switches to the exact score outside the good set.This auxiliary process is analytical because the exact score is unavailable to the algorithm.
The auxiliary process can be coupled with the predictor algorithm while the iterates remain outside the bad sets.
The final argument applies Chebyshev’s inequality and χ2-divergence bounds to control the probability of entering bad regions and the resulting distributional error.
For sufficiently large T, the initial χ2 divergence is O(1), which yields the stated final convergence bound.The supplied proof specifies the sufficient condition T = Ω(ln(C_LS d)).

C.8 Proof of Theorem 3.2

The predictor-corrector analysis combines predictor and Langevin-corrector guarantees to obtain total-variation convergence, while interleaving can damp predictor error and potentially permit larger steps.

Theorem 3.2 establishes that the predictor-corrector algorithm produces a distribution q_T with TV(q_T, p_data) < ε_TV.
The proof chains the predictor guarantee with the Langevin Monte Carlo guarantee, considering first a schedule with all corrector steps at the end.
The analysis selects predictor and corrector step sizes and numbers of corrector steps to achieve the target total-variation accuracy.
The final conversion to total variation splits the target error between the predictor and corrector components.
Interleaving predictor and corrector steps can exponentially damp error accumulated during prediction and potentially allow larger step sizes.Under the stated theorem assumptions, interleaving does not improve parameter dependence, but it may extend the permitted step-size range.

D Stationary distribution of LD with score estimate can be arbitrarily far away

The section constructs a smooth one-dimensional counterexample showing that Langevin dynamics using an L2(p)-accurate score estimate can converge to a distribution arbitrarily far from the target. The discrepancy is hidden in a tail region where p has negligible mass, motivating convergence analyses based on finite-time behavior rather than stationary distributions.

Counterexample: An L2(p)-accurate score estimate can produce a Langevin stationary distribution arbitrarily far from the true distribution.The construction applies even in one dimension and takes the target distribution to be standard Gaussian.
Counterexample: The construction changes the target only in a far tail, where the modified distribution has a large mode that L2(p) loss fails to detect.The target density is vanishing near the added mode, so the score discrepancy contributes little under p.
Assumptions: The constructed q satisfies smoothness assumptions, including a uniformly smooth log-density, so smoothness alone does not prevent the failure.The theorem states that for every ε > 0, a distribution q with C-smooth ln q exists under the construction.
Counterexample: As the tail mode grows, qL([−L, L]) tends to zero and the total variation distance between pL and qL tends to one.This establishes an arbitrarily large distributional discrepancy despite vanishing score-estimation error.