Introduction
Diffusion and score-based generative models have become a central framework for high-dimensional generative modeling ([29 , 16 , 30 ] ). Conditional diffusion models extend this framework by learning a family of generative distributions indexed by side information, enabling applications such as text-to-image generation [6 , 27 ] , conditional molecular design [24 ] , and conditional time-series imputation [34 ] . In score-based formulations, the learned object is a conditional score
s ⋆ ( x , t , y ) = ∇ x log p t ( x ∣ y ) , s^\star(x,t,y)=\nabla_x\log p_t(x\mid y), s ⋆ ( x , t , y ) = ∇ x log p t ( x ∣ y ) ,
which depends jointly on the noised data variable x x x , the conditioning variable y y y , and diffusion time t t t , and is used to construct the reverse-time generative dynamics. Practical conditional diffusion systems employ a variety of conditioning mechanisms, including classifier guidance [6 , 28 ] , classifier-free guidance [15 ] , and transformer-based score architectures [26 ] .
A complete theoretical analysis of conditional diffusion training must connect several distinct components. First, the conditional score must be approximated by the chosen function class. Second, the score-matching objective must be optimized using only a finite amount of computation and data. Third, the resulting score-estimation error must be propagated through a discretized reverse diffusion process. Finally, when the data or conditioning variables are unbounded, the approximation argument must control contributions from regions far from the bulk of the distribution. These issues are coupled in conditional models because approximation takes place jointly over the response, conditioning variable, and diffusion time.
In this work, we study this training-to-sampling problem for conditional diffusion models trained by online stochastic-gradient denoising score matching . Our objective is not to assume that the training procedure returns an exact optimizer and then analyze the resulting score estimator. Instead, we ask how the error of a score network obtained after finitely many stochastic gradient updates propagates to the distribution generated by the reverse process. More precisely, we seek a decomposition in which approximation error, finite-time optimization error, discretization error, and terminal initialization error remain separately visible.
This perspective differs from a common abstraction in statistical analyses of conditional diffusion, where the score estimator is defined through an exact empirical or population risk minimizer [36 , 8 , 33 , 17 ] . Such an abstraction is useful for isolating score-estimation error, but it does not directly describe the output of a finite stochastic-gradient training procedure. A fixed-dataset analysis may additionally require controlling the generalization gap between empirical and population objectives. Finite-time gradient training has already been analyzed in unconditional settings [13 , 14 ] . Recent work has also analyzed SGD dynamics for unconditional score-based generative models [32 ] . Thus finite-time gradient training is not, by itself, the novelty claimed here. We instead consider an online sampling model in which each stochastic-gradient update uses fresh draws of the data pair, diffusion time, and Gaussian perturbation. This allows the optimization error to be analyzed directly at the level of the population randomized-time denoising objective.
Replacing exact minimizer access by finite-time optimization requires additional optimization regularity. We make this tradeoff explicit. In particular, our analysis assumes local smoothness, stochastic-gradient regularity, and a localized Polyak–Łojasiewicz (PL) condition along the relevant training trajectory. The PL condition is not derived in this paper for the full neural score class; rather, it is an explicit optimization assumption under which the effect of a finite online SGD budget can be quantified. Thus, the finite-time result should be interpreted as a conditional training guarantee: given the stated localized optimization geometry, we characterize how the remaining optimization error enters the final sampling bound.
The approximation side of the analysis addresses a different difficulty. Conditional score estimation can depend strongly on the dimensions of both the response and the conditioning variable. Some existing guarantees exhibit ambient-dimensional dependence [8 ] , while intrinsic-dimensional analyses exploit manifold or latent low-dimensional structure [33 , 17 ] . We work with a joint intrinsic-dimensional structure for the clean pair ( X 0 , Y ) (X_0,Y) ( X 0 , Y ) , together with anisotropic regularity that permits different smoothness along response and conditioning coordinates. We also impose an explicit approximation-class compatibility condition linking our smooth-gated score class to the localized blockwise construction used in the cited conditional approximation theorem; the geometric assumptions alone do not imply the claimed network rate. We denote the corresponding intrinsic dimensions by d x ′ d'_x d x ′ and d y ′ d'_y d y ′ , and their smoothness exponents by α x \alpha_x α x and α y \alpha_y α y , respectively. The associated approximation exponent is
η a p p : = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ . \eta_{\mathrm{app}} := \frac{2\alpha_x}{2\alpha_x + d'_x + (\alpha_x/\alpha_y)d'_y}. η app := 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x .
We additionally allow the data and conditioning variables to have sub-exponential tails. The proof localizes the denoising problem to logarithmic-radius high-probability regions and controls the contribution of their complements through tail decay.
Main result and scope. A central feature of our formulation is that we distinguish the complexity of the score class from the amount of online training data. Let
M = score-network approximation complexity , N = R B = number of online denoising samples , M = \text{score-network approximation complexity}, \qquad N = RB = \text{number of online denoising samples}, M = score-network approximation complexity , N = R B = number of online denoising samples ,
where R R R is the number of SGD iterations and B B B is the mini-batch size. For a discretization grid with K K K steps and total time weight H K H_K H K , our main theorem takes the schematic form
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≲ C t e r m e − T + C d i s c r d x + m 2 K + C s t a b H K [ A K ( M ) + E o p t ( N , M ) ] . \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\lesssim C_{\mathrm{term}}e^{-T} + C_{\mathrm{discr}}\sqrt{\frac{d_x+m_2}{K}} + C_{\mathrm{stab}}\sqrt{H_K\left[\mathcal{A}_K(M)+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}. E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≲ C term e − T + C discr K d x + m 2 + C stab H K [ A K ( M ) + E opt ( N , M ) ] .
under the stated localized PL and trajectory-containment assumptions. Here A K ( M ) \mathcal{A}_K(M) A K ( M ) is the score-class approximation/localization error and E o p t ( N , M ) \mathcal{E}_{\mathrm{opt}}(N,M) E opt ( N , M ) is the excess population denoising risk remaining after finite-time online optimization. Under the anisotropic intrinsic-dimensional approximation assumptions developed in this paper,
A K ( M ) = O ~ ( M − η a p p ) . \mathcal{A}_K(M)=\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). A K ( M ) = O ( M − η app ) .
Under localized PL geometry and the decreasing step-size schedule analyzed below, the optimization component satisfies a bound of the form
E o p t ( N , M ) ≲ Δ 0 , M r 0 2 ( R + r 0 ) 2 + L M σ M 2 μ M 2 B ( R + r 0 ) , N = R B , \mathcal{E}_{\mathrm{opt}}(N,M)\lesssim\frac{\Delta_{0,M}r_0^2}{(R+r_0)^2}+\frac{L_M\sigma_M^2}{\mu_M^2B(R+r_0)}, \qquad N=RB, E opt ( N , M ) ≲ ( R + r 0 ) 2 Δ 0 , M r 0 2 + μ M 2 B ( R + r 0 ) L M σ M 2 , N = R B ,
where L M L_M L M , μ M \mu_M μ M , and σ M 2 \sigma_M^2 σ M 2 denote the relevant smoothness, PL, and stochastic-gradient variance constants, and Δ 0 , M \Delta_{0,M} Δ 0 , M is the initial population excess risk. Keeping these quantities explicit separates the approximation and optimization requirements of the result. If these optimization constants remain uniformly controlled along the chosen sequence of score classes, the leading requirements reduce, up to logarithmic factors, to
M = Θ ~ ( ϵ − 2 / η a p p ) , N = Θ ~ ( ϵ − 2 ) , M=\widetilde{\Theta}\left(\epsilon^{-2/\eta_{\mathrm{app}}}\right), \qquad N=\widetilde{\Theta}\left(\epsilon^{-2}\right), M = Θ ( ϵ − 2/ η app ) , N = Θ ( ϵ − 2 ) ,
together with a sufficiently fine reverse-time discretization, for O ~ ( ϵ ) \widetilde{O}(\epsilon) O ( ϵ ) expected total-variation error relative to the positive-time target p t 0 ( ⋅ ∣ Y ) p_{t_0}(\cdot\mid Y) p t 0 ( ⋅ ∣ Y ) . The positive stopping time t 0 > 0 t_0>0 t 0 > 0 is important for interpreting this statement. Our primary result concerns the forward-smoothed conditional law p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) . This permits intrinsic low-dimensional clean-data structure while the reverse-process analysis operates away from the singular endpoint t = 0 t=0 t = 0 . A total-variation guarantee for the original law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) requires an additional smoothing-bias argument. We provide such an extension under stronger full-dimensional integral density regularity. The stopped-law theorem and the original-law extension therefore have different assumptions and should be viewed as separate results.
Table 1. Structural comparison with representative adjacent theory. “Gradient training” records whether a concrete finite-run gradient method is analyzed. The rows are not rate comparisons.
Table 1 separates two adjacent lines of work: conditional distribution-estimation theory and algorithm-dependent score-training theory. The assumptions, estimator definitions, and target laws differ, so their rates are not directly comparable. The table locates our contribution at their intersection; it does not assert priority for finite-time diffusion optimization in general.
Contributions. The main contributions of the paper are as follows:
Finite-time training-to-sampling decomposition. We give an end-to-end error decomposition for conditional diffusion trained by online stochastic-gradient denoising score matching. The bound keeps terminal initialization, reverse-time discretization, score-class approximation/localization, and finite-time optimization as separate components. In particular, the score network need not be an exact population or empirical minimizer; the remaining optimization error is quantified explicitly under localized PL geometry.
Explicit separation of approximation and optimization complexity. We distinguish the score-class complexity M M M from the online denoising sample budget N N N . Under anisotropic intrinsic-dimensional regularity and the stated approximation-class compatibility condition, the approximation contribution scales as
O ~ ( M − η a p p ) , η a p p = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ , \widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right), \qquad\eta_{\mathrm{app}} = \frac{2\alpha_x}{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y}, O ( M − η app ) , η app = 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x ,
while the finite-time optimization term is controlled separately through the smoothness, PL, gradient-noise, initialization, and online-sample parameters. This separation avoids conflating network approximation scale with the number of samples consumed by SGD.
Stopped-law guarantee and original-law extension. Our primary theorem controls the learned discretized sampler relative to the forward-smoothed conditional law at a positive stopping time t 0 t_0 t 0 . Under additional full-dimensional integral density regularity, we prove a smoothing-bias bound and extend the analysis to total-variation convergence to the original conditional law. This makes explicit where stronger regularity is required and avoids conflating the two guarantees.
At a technical level, the analysis makes compatible three ingredients that are usually treated separately: conditional score approximation, finite-time stochastic optimization, and reverse-diffusion stability. We use existing reverse-process stability and conditional approximation results as inputs where appropriate, while proving the localization, randomized-time approximation transfer, finite-time online-SGD excess-risk control, and their combination into the final training-to-sampling guarantee. Our emphasis is therefore on a transparent and auditable finite-time analysis, including the assumptions under which each component is valid, rather than on claiming a uniformly improved statistical exponent over existing conditional diffusion theory. Relative to unconditional optimization analyses [13 , 14 , 32 ] , the additional contribution is the conditional coupling: one time-conditioned score must approximate a family indexed by Y Y Y , the approximation rate depends on joint fibered geometry, and the resulting randomized-time population error must match the forward-marginal quantity in the conditional reverse-process stability bound. We do not claim a new proof of PL geometry for neural networks or a new reverse-SDE discretization theorem.
Preliminaries and Problem Formulation
Let ( X 0 , Y ) ∼ P 0 (X_0,Y) \sim P_0 ( X 0 , Y ) ∼ P 0 be a random pair, where Y ∈ R d y Y \in\mathbb{R}^{d_y} Y ∈ R d y has marginal law P Y P_Y P Y , and, conditional on Y = y Y=y Y = y , the data variable X 0 ∈ R d x X_0 \in\mathbb{R}^{d_x} X 0 ∈ R d x has conditional law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) . Thus
P 0 ( d x , d y ) = p 0 ( d x ∣ y ) P Y ( d y ) . P_0(dx,dy) = p_0(dx \mid y)P_Y(dy). P 0 ( d x , d y ) = p 0 ( d x ∣ y ) P Y ( d y ) .
We write d = d x + d y d=d_x+d_y d = d x + d y . The unconditional setting is recovered by taking d y = 0 d_y=0 d y = 0 . We use p t ( ⋅ ∣ y ) p_t(\cdot\mid y) p t ( ⋅ ∣ y ) for a conditional probability law and, when the corresponding density exists, for its density as well.
Throughout, O ~ \widetilde{O} O and Θ ~ \widetilde{\Theta} Θ suppress only multiplicative constants independent of the displayed asymptotic variables and factors that are polylogarithmic in those variables. Dependence that is polynomial in a vanishing time cutoff such as t 0 t_0 t 0 is displayed explicitly. Fixed distributional, geometric, and moment parameters may enter the implicit constants unless a result states otherwise.
The generative target is the original conditional law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) . Our primary theorem, however, controls the learned sampler relative to the forward-smoothed law p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) at a positive stopping time t 0 > 0 t_0>0 t 0 > 0 . Convergence to the original law is treated separately through a smoothing-bias argument under stronger full-dimensional density regularity.
Forward diffusion and conditional score. We consider the variance-preserving Ornstein–Uhlenbeck forward process
d X t = − X t d t + 2 d B t , X 0 ∼ p 0 ( ⋅ ∣ y ) , (1) dX_t=-X_t\,dt+\sqrt{2}\,dB_t,\qquad X_0\sim p_0(\cdot\mid y), \tag*{(1)} d X t = − X t d t + 2 d B t , X 0 ∼ p 0 ( ⋅ ∣ y ) , (1)
where B t B_t B t is a standard Brownian motion independent of ( X 0 , Y ) (X_0,Y) ( X 0 , Y ) . Conditional on X 0 = x 0 X_0=x_0 X 0 = x 0 , the forward transition can be written as
X t = e − t X 0 + σ t ε , σ t 2 : = 1 − e − 2 t , ε ∼ N ( 0 , I d x ) , X_t=e^{-t}X_0+\sigma_t\varepsilon,\qquad\sigma_t^2:=1-e^{-2t},\qquad\varepsilon\sim\mathcal{N}(0,I_{d_x}), X t = e − t X 0 + σ t ε , σ t 2 := 1 − e − 2 t , ε ∼ N ( 0 , I d x ) ,
with ε \varepsilon ε independent of ( X 0 , Y ) (X_0,Y) ( X 0 , Y ) . Consequently,
q t ( x ∣ x 0 ) = N ( e − t x 0 , σ t 2 I d x ) , q_t(x\mid x_0)=\mathcal{N}\left(e^{-t}x_0,\sigma_t^2I_{d_x}\right), q t ( x ∣ x 0 ) = N ( e − t x 0 , σ t 2 I d x ) ,
and the corresponding kernel score is
∇ x log q t ( x ∣ x 0 ) = − x − e − t x 0 σ t 2 . (2) \nabla_x\log q_t(x\mid x_0)=-\frac{x-e^{-t}x_0}{\sigma_t^2}. \tag*{(2)} ∇ x log q t ( x ∣ x 0 ) = − σ t 2 x − e − t x 0 . (2)
Let p t ( ⋅ ∣ y ) p_t(\cdot\mid y) p t ( ⋅ ∣ y ) denote the conditional law of X t X_t X t given Y = y Y=y Y = y . The conditional marginal score is
s ∗ ( x , t , y ) : = ∇ x log p t ( x ∣ y ) ∈ R d x . (3) s^*(x,t,y):=\nabla_x\log p_t(x\mid y)\in\mathbb{R}^{d_x}. \tag*{(3)} s ∗ ( x , t , y ) := ∇ x log p t ( x ∣ y ) ∈ R d x . (3)
The distinction between dimensions is important throughout the paper: x ∈ R d x x\in\mathbb{R}^{d_x} x ∈ R d x , y ∈ R d y y\in\mathbb{R}^{d_y} y ∈ R d y , whereas the score itself always takes values in R d x \mathbb{R}^{d_x} R d x .
Reverse process and stopped target. Fix diffusion times 0 < t 0 < 1 ≤ T 0 < t_0 < 1 \le T 0 < t 0 < 1 ≤ T , as required by the early-stopped reverse-process stability result used below. Writing X ˉ τ = X T − τ \bar{X}_{\tau} = X_{T-\tau} X ˉ τ = X T − τ , stochastic time reversal [1 ] gives
d X ˉ τ = ( X ˉ τ + 2 s ⋆ ( X ˉ τ , T − τ , y ) ) d τ + 2 d B ˉ τ , 0 ≤ τ ≤ T − t 0 , (4) \mathrm{d}\bar{X}_{\tau} = \left(\bar{X}_{\tau} + 2s^{\star}(\bar{X}_{\tau},T-\tau,y)\right)\mathrm{d}\tau+ \sqrt{2}\,\mathrm{d}\bar{B}_{\tau}, \qquad0 \le\tau\le T-t_0, \tag*{(4)} d X ˉ τ = ( X ˉ τ + 2 s ⋆ ( X ˉ τ , T − τ , y ) ) d τ + 2 d B ˉ τ , 0 ≤ τ ≤ T − t 0 , (4)
when initialized from the forward terminal law p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) . Running this process down to forward time t 0 t_0 t 0 recovers p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) .
The implementable sampler differs from this ideal reverse process in three ways: it is initialized from the reference Gaussian N ( 0 , I d x ) \mathcal{N}(0,I_{d_x}) N ( 0 , I d x ) , the true score s ⋆ s^{\star} s ⋆ is replaced by a learned score, and the reverse SDE is discretized. These three changes give rise, respectively, to the terminal-initialization, score-estimation, and time-discretization terms in the main theorem.
Approximation complexity and score class. We distinguish throughout the paper between the complexity of the score class and the number of samples consumed by stochastic-gradient training. Let
M = approximation-complexity index , N = number of online denoising samples used for training . M = \text{approximation-complexity index}, \qquad N = \text{number of online denoising samples used for training}. M = approximation-complexity index , N = number of online denoising samples used for training .
These are independent quantities.
For each approximation scale M M M , let
F Θ , M = { s θ : θ ∈ Θ M } \mathcal{F}_{\Theta,M} = \{s_{\theta} : \theta\in\Theta_M\} F Θ , M = { s θ : θ ∈ Θ M }
denote the conditional score class. The class used in the approximation analysis is a single time-conditioned, smooth-gated dyadic-block class. Let
t 0 = u 0 < u 1 < ⋯ < u I = T t_0 = u_0 < u_1 < \cdots< u_I = T t 0 = u 0 < u 1 < ⋯ < u I = T
be a dyadic cover satisfying
u i + 1 ≤ 2 u i , i = 0 , … , I − 1. u_{i+1} \le2u_i, \qquad i = 0,\ldots,I-1. u i + 1 ≤ 2 u i , i = 0 , … , I − 1.
We take
s θ ( x , y , t ) = ∑ i = 0 I − 1 χ i ( t ) s θ ( i ) ( x , y , t ) , (5) s_{\theta}(x,y,t) = \sum_{i=0}^{I-1}\chi_i(t)s_{\theta}^{(i)}(x,y,t), \tag*{(5)} s θ ( x , y , t ) = i = 0 ∑ I − 1 χ i ( t ) s θ ( i ) ( x , y , t ) , (5)
where { χ i } i = 0 I − 1 \{\chi_i\}_{i=0}^{I-1} { χ i } i = 0 I − 1 are fixed deterministic nonnegative smooth gates forming a partition of unity over the time interval and each s θ ( i ) s_{\theta}^{(i)} s θ ( i ) belongs to the corresponding blockwise conditional score-approximation class.
The gates are part of the theoretical construction and are not optimized by SGD. Their support, overlap, and derivative bounds are absorbed into the approximation-class compatibility condition and the logarithmic factors in the rate. The index M M M records the calibrated approximation scale of this class; it is not identified with either the raw parameter count or the training sample size N N N . For the localized approximants used in the proof, the parameter bounds imply a polynomial output envelope: for fixed t 0 > 0 t_0 > 0 t 0 > 0 , there exist fixed exponents q 1 , q 2 q_1,q_2 q 1 , q 2 such that
∥ s θ ( x , y , t ) ∥ 2 ≤ C M q 1 ( 1 + ∥ x ∥ 2 + ∥ y ∥ 2 ) q 2 , t ∈ [ t 0 , T ] . \lVert s_{\theta}(x,y,t)\rVert_2 \le CM^{q_1}(1+\lVert x\rVert_2+\lVert y\rVert_2)^{q_2}, \qquad t \in[t_0,T]. ∥ s θ ( x , y , t ) ∥ 2 ≤ C M q 1 ( 1 + ∥ x ∥ 2 + ∥ y ∥ 2 ) q 2 , t ∈ [ t 0 , T ] .
This condition is used only to control the tail complement after localization.
Time grid and randomized-time distribution. Let
t 0 < t 1 < ⋯ < t K = T t_0 < t_1 < \cdots< t_K = T t 0 < t 1 < ⋯ < t K = T
be the time grid used in training and reverse sampling, and define
Δ k : = t k − t k − 1 , H K : = ∑ k = 1 K Δ k = T − t 0 , Δ max : = max 1 ≤ k ≤ K Δ k . \Delta_k := t_k - t_{k-1}, \qquad H_K := \sum_{k=1}^{K} \Delta_k = T - t_0, \qquad\Delta_{\max} := \max_{1 \le k \le K} \Delta_k. Δ k := t k − t k − 1 , H K := k = 1 ∑ K Δ k = T − t 0 , Δ m a x := 1 ≤ k ≤ K max Δ k .
Let J ∈ { 1 , … , K } J \in\{1,\ldots,K\} J ∈ { 1 , … , K } be independent of ( X 0 , Y , ε ) (X_0,Y,\varepsilon) ( X 0 , Y , ε ) , with
P ( J = k ) = π K , k : = Δ k H K . (6) \mathbb{P}(J=k)=\pi_{K,k}:=\frac{\Delta_k}{H_K}. \tag*{(6)} P ( J = k ) = π K , k := H K Δ k . (6)
This choice makes expectation with respect to J J J exactly the normalized time-weighted grid average that appears in the reverse-process stability argument. The right-endpoint convention t J = t k t_J=t_k t J = t k matches the score evaluation in the exponential-integrator reverse sampler used below.
A single randomized-time denoising observation is
ξ = ( X 0 , Y , J , ε ) , \xi=(X_0,Y,J,\varepsilon), ξ = ( X 0 , Y , J , ε ) ,
with
( X 0 , Y ) ∼ P 0 , J ∼ π K , ε ∼ N ( 0 , I d x ) , (X_0,Y)\sim P_0,\qquad J\sim\pi_K,\qquad\varepsilon\sim\mathcal{N}(0,I_{d_x}), ( X 0 , Y ) ∼ P 0 , J ∼ π K , ε ∼ N ( 0 , I d x ) ,
all sampled independently except for the dependence between X 0 X_0 X 0 and Y Y Y specified by P 0 P_0 P 0 . The corresponding noised state and denoising target are
X t J = e − t J X 0 + σ t J ε , (7) X_{t_J}=e^{-t_J}X_0+\sigma_{t_J}\varepsilon, \tag*{(7)} X t J = e − t J X 0 + σ t J ε , (7)
Z J : = ∇ x log q t J ( X t J ∣ X 0 ) = − X t J − e − t J X 0 σ t J 2 . (8) Z_J:=\nabla_x\log q_{t_J}(X_{t_J}\mid X_0)=-\frac{X_{t_J}-e^{-t_J}X_0}{\sigma_{t_J}^2}. \tag*{(8)} Z J := ∇ x log q t J ( X t J ∣ X 0 ) = − σ t J 2 X t J − e − t J X 0 . (8)
Randomized-time population denoising objective. For θ ∈ Θ M \theta\in\Theta_M θ ∈ Θ M , define
L K ( θ ) : = E ξ [ ∥ s θ ( X t J , Y , t J ) − Z J ∥ 2 2 ] . (9) \mathcal{L}_K(\theta):=\mathbb{E}_{\xi}\left[\left\|s_\theta(X_{t_J},Y,t_J)-Z_J\right\|_2^2\right]. \tag*{(9)} L K ( θ ) := E ξ [ ∥ s θ ( X t J , Y , t J ) − Z J ∥ 2 2 ] . (9)
This is a population objective: no fixed empirical dataset is introduced. The network-class dependence enters through the feasible set Θ M \Theta_M Θ M . We define its best achievable population denoising risk by
L K , M ⋆ : = inf θ ∈ Θ M L K ( θ ) . (10) \mathcal{L}_{K,M}^{\star}:=\inf_{\theta\in\Theta_M}\mathcal{L}_K(\theta). \tag*{(10)} L K , M ⋆ := θ ∈ Θ M inf L K ( θ ) . (10)
The infimum in (10) is an analytical benchmark only. The training algorithm is neither assumed to have access to it nor assumed to return a parameter attaining it.
Denoising identity and approximation error. Although the denoising objective uses the kernel score Z J Z_J Z J , the reverse process requires the marginal conditional score s ⋆ s^\star s ⋆ . They are related by the conditional denoising identity
s ⋆ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] . (11) s^\star(X_{t_J},t_J,Y)=\mathbb{E}\left[Z_J\mid X_{t_J},Y,t_J\right]. \tag*{(11)} s ⋆ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] . (11)
Consequently, for every measurable score predictor s s s ,
E [ ∥ s ( X t J , Y , t J ) − Z J ∥ 2 2 ] = C K + E [ ∥ s ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (12) \begin{aligned}
\mathbb{E}\left[\left\|s(X_{t_J},Y,t_J)-Z_J\right\|_2^2\right]
&=C_K+\mathbb{E}\left[\left\|s(X_{t_J},Y,t_J)-s^\star(X_{t_J},t_J,Y)\right\|_2^2\right]. \tag*{(12)}
\end{aligned} E [ ∥ s ( X t J , Y , t J ) − Z J ∥ 2 2 ] = C K + E [ ∥ s ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (12)
where
C K : = E [ ∥ Z J − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] C_K := \mathbb{E}\left[\left\|Z_J-s^\star(X_{t_J},t_J,Y)\right\|_2^2\right] C K := E [ ∥ Z J − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ]
does not depend on s s s .
This motivates the randomized-time best-in-class score approximation error
A K ( M ) : = inf θ ∈ Θ M E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (13) A_K(M) := \inf_{\theta\in\Theta_M}\mathbb{E}\left[\left\|s_\theta(X_{t_J},Y,t_J)-s^\star(X_{t_J},t_J,Y)\right\|_2^2\right]. \tag*{(13)} A K ( M ) := θ ∈ Θ M inf E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (13)
By (12) ,
L K , M ⋆ = C K + A K ( M ) . (14) \mathcal{L}^\star_{K,M}=C_K+A_K(M). \tag*{(14)} L K , M ⋆ = C K + A K ( M ) . (14)
Importantly, A K ( M ) A_K(M) A K ( M ) is an approximation property of the score class; it does not involve the online training budget N N N . Under the intrinsic-dimensional and anisotropic regularity assumptions introduced below, we will prove a bound of the form
A K ( M ) ≤ O ~ ( M − η a p p ) , A_K(M)\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right), A K ( M ) ≤ O ( M − η app ) ,
subject to the stated grid-resolution and localization conditions.
Online stochastic-gradient training. The training algorithm uses fresh randomized-time denoising observations. At SGD iteration r = 0 , … , R − 1 r=0,\ldots,R-1 r = 0 , … , R − 1 , a mini-batch
{ ξ r , b } b = 1 B \{\xi_{r,b}\}_{b=1}^{B} { ξ r , b } b = 1 B
of B B B independent copies of ξ \xi ξ is drawn, and the mini-batch stochastic gradient is
g ˉ r : = 1 B ∑ b = 1 B g ( θ r ; ξ r , b ) , \bar{g}_r:=\frac{1}{B}\sum_{b=1}^{B}g(\theta_r;\xi_{r,b}), g ˉ r := B 1 b = 1 ∑ B g ( θ r ; ξ r , b ) ,
where g ( θ ; ξ ) g(\theta;\xi) g ( θ ; ξ ) denotes the stochastic gradient of the squared denoising loss associated with one online sample. The update is
θ r + 1 = θ r − η r g ˉ r . (15) \theta_{r+1}=\theta_r-\eta_r\bar{g}_r. \tag*{(15)} θ r + 1 = θ r − η r g ˉ r . (15)
The total online denoising-sample budget is therefore
N = R B . (16) N=RB. \tag*{(16)} N = R B . (16)
We denote the final parameter and score by
θ ^ : = θ R , s ^ : = s θ ^ . \widehat{\theta}:=\theta_R,\qquad\widehat{s}:=s_{\widehat{\theta}}. θ := θ R , s := s θ .
For later use, define the finite-time population optimization error
E o p t ( N , M ) : = E S G D [ L K ( θ ^ ) − L K , M ⋆ ] , (17) \mathcal{E}_{\mathrm{opt}}(N,M):=\mathbb{E}_{\mathrm{SGD}}\left[\mathcal{L}_K(\widehat{\theta})-\mathcal{L}^\star_{K,M}\right], \tag*{(17)} E opt ( N , M ) := E SGD [ L K ( θ ) − L K , M ⋆ ] , (17)
with the expectation taken over the randomness of the online stochastic-gradient procedure. The localized optimization analysis assumes explicitly that the unmodified SGD trajectory remains in the PL region throughout the analyzed run. The notation E o p t ( N , M ) \mathcal{E}_{\mathrm{opt}}(N,M) E opt ( N , M ) suppresses the chosen factorization N = R B N=RB N = R B , initialization, and step-size schedule. The general bound retains R R R and B B B explicitly; only under the fixed-B B B specialization does the leading rate depend on N N N alone.
Thus M M M controls the representation error of the score class, whereas N N N controls how accurately online SGD optimizes the population denoising objective within that class. These two quantities are kept separate throughout the analysis.
Generated law. For a conditioning value y y y , let p ^ t 0 ( ⋅ ∣ y ) \widehat{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) denote the law produced by initializing the discretized reverse process at N ( 0 , I d x ) \mathcal{N}(0,I_{d_x}) N ( 0 , I d x ) , using the grid { t k } k = 0 K \{t_k\}_{k=0}^{K} { t k } k = 0 K , and replacing s ⋆ s^\star s ⋆ by the learned score s ^ \widehat{s} s . Specifically, with h k = Δ k h_k=\Delta_k h k = Δ k , the sampler uses the exponential-integrator update
X t k − 1 = e h k X t k + 2 ( e h k − 1 ) s ^ ( X t k , Y , t k ) + e 2 h k − 1 ξ k , ξ k ∼ N ( 0 , I d x ) , (18) X_{t_{k-1}}=e^{h_k}X_{t_k}+2(e^{h_k}-1)\widehat{s}(X_{t_k},Y,t_k)+\sqrt{e^{2h_k}-1}\,\xi_k,\qquad\xi_k\sim\mathcal{N}(0,I_{d_x}), \tag*{(18)} X t k − 1 = e h k X t k + 2 ( e h k − 1 ) s ( X t k , Y , t k ) + e 2 h k − 1 ξ k , ξ k ∼ N ( 0 , I d x ) , (18)
for k = K , … , 1 k=K,\ldots,1 k = K , … , 1 . The primary goal of the analysis is to control
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] . \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]. E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] .
A separate corollary adds the smoothing bias TV ( p 0 , p t 0 ) \operatorname{TV}(p_0,p_{t_0}) TV ( p 0 , p t 0 ) in order to obtain a guarantee relative to the original conditional data law.
Notation summary. For convenience, the principal quantities used in the analysis are summarized below.
Table 1 (PDF p. 9).
Algorithm 1 gives the corresponding training-and-sampling procedure. The theoretical analysis below considers its online fresh-sample form described above.
Main Results
We now state the assumptions and main finite-time guarantees. A central distinction throughout this section is between the approximation-complexity index M M M , which determines the richness of the score class F Θ , M \mathcal{F}_{\Theta,M} F Θ , M , and the online denoising-sample budget N = R B N=RB N = R B , which determines the amount of stochastic-gradient training. The two quantities are not identified.
Distributional and Geometric Assumptions
Assumption 3.1 (Distributional regularity and approximation-class compatibility). Let ( X 0 , Y ) ∼ P 0 (X_0,Y)\sim P_0 ( X 0 , Y ) ∼ P 0 take values in R d x × R d y \mathbb{R}^{d_x}\times\mathbb{R}^{d_y} R d x × R d y . The following conditions hold.
1. Joint fibered intrinsic geometry. There exists an embedded manifold
M ⊂ R d x × R d y \mathcal{M}\subset\mathbb{R}^{d_x}\times\mathbb{R}^{d_y} M ⊂ R d x × R d y of dimension
dim ( M ) = d x ′ + d y ′ . \dim(\mathcal{M})=d'_x+d'_y. dim ( M ) = d x ′ + d y ′ .
containing the support of P 0 P_0 P 0 . Let
π Y : M ⟶ M Y \pi_Y:\mathcal{M}\longrightarrow\mathcal{M}_Y π Y : M ⟶ M Y
denote the restriction to M \mathcal{M} M of the projection onto the conditioning coordinate, where M Y ⊂ R d y ′ \mathcal{M}_Y\subset\mathbb{R}^{d'_y} M Y ⊂ R d y ′ is an embedded d y ′ d'_y d y ′ -dimensional manifold. We assume that π Y \pi_Y π Y is a smooth submersion. Hence, for P Y P_Y P Y -a.e. y y y , the fiber
M y : = π Y − 1 ( y ) \mathcal{M}_y:=\pi_Y^{-1}(y) M y := π Y − 1 ( y )
is a d x ′ d'_x d x ′ -dimensional submanifold describing the intrinsic support of X 0 ∣ Y = y X_0\mid Y=y X 0 ∣ Y = y .
On each localization region used below, the joint manifold admits a finite family of fiber-compatible charts of the form
( u , v ) ∈ R d x ′ × R d y ′ ⟼ Φ ( u , v ) = ( Φ X ( u , v ) , Φ Y ( v ) ) , (u,v)\in\mathbb{R}^{d'_x}\times\mathbb{R}^{d'_y}\longmapsto\Phi(u,v)=\left(\Phi_X(u,v),\Phi_Y(v)\right), ( u , v ) ∈ R d x ′ × R d y ′ ⟼ Φ ( u , v ) = ( Φ X ( u , v ) , Φ Y ( v ) ) ,
with uniformly controlled chart and inverse-chart Lipschitz constants, Jacobians, reach, condition number, and the encoder–decoder quantities required by the manifold-adapted approximation argument. The chart smoothness satisfies the hypotheses of the approximation theorem invoked below, and the geometric approximation remainder is no larger than the leading density-approximation term.
2. Anisotropic smooth conditional laws. The conditioning law P Y P_Y P Y admits a density with respect to the intrinsic volume measure on M Y \mathcal{M}_Y M Y . In the local coordinate v v v , this density is locally Hölder smooth of order α y > 0 \alpha_y>0 α y > 0 .
For P Y P_Y P Y -a.e. y y y , the conditional law P X 0 ∣ Y = y P_{X_0\mid Y=y} P X 0 ∣ Y = y admits a density with respect to the induced volume measure on the fiber M y \mathcal{M}_y M y , bounded by a constant B d e n s < ∞ B_{\mathrm{dens}}<\infty B dens < ∞ . In a fiber-compatible chart, the resulting conditional density, viewed as a function of ( u , v ) (u,v) ( u , v ) , has response-coordinate Hölder smoothness α x > 0 \alpha_x>0 α x > 0 in u u u and conditioning-coordinate Hölder smoothness α y > 0 \alpha_y>0 α y > 0 in v v v . The corresponding localized Hölder constants are uniformly controlled on the logarithmic-radius regions used in the approximation proof. The localized density nondegeneracy and inverse-density quantities required by the conditional score approximation construction are also controlled on those regions.
3. Sub-exponential tails. There exist constants λ Y , λ X > 0 \lambda_Y,\lambda_X>0 λ Y , λ X > 0 such that
E exp ( λ Y ∥ Y ∥ 2 ) < ∞ , \mathbb{E}\exp(\lambda_Y\lVert Y\rVert_2)<\infty, E exp ( λ Y ∥ Y ∥ 2 ) < ∞ ,
and
ess sup y ∼ P Y E [ exp ( λ X ∥ X 0 ∥ 2 ) ∣ Y = y ] < ∞ . \operatorname*{ess\,sup}_{y\sim P_Y}\mathbb{E}\left[\exp(\lambda_X\lVert X_0\rVert_2)\mid Y=y\right]<\infty. y ∼ P Y ess sup E [ exp ( λ X ∥ X 0 ∥ 2 ) ∣ Y = y ] < ∞.
4. Approximation-class compatibility. On every logarithmic localization region used in the proof, the chart, decoder, density, and geometric-remainder conditions required by the blockwise conditional score-approximation theorem of Tang et al. [33 ] hold with the growth recorded in the O ~ \widetilde{O} O -notation. The class F Θ , M \mathcal{F}_{\Theta,M} F Θ , M contains smooth-activation, smooth-gated realizations of those localized blockwise approximants at squared-error rate M − η a p p M^{-\eta_{\mathrm{app}}} M − η app , with activation and gate smoothing affecting only logarithmic factors.
Define the anisotropic approximation exponent
η a p p : = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ . (19) \eta_{\mathrm{app}}:=\frac{2\alpha_x}{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y}. \tag*{(19)} η app := 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x . (19)
The fibered formulation in Assumption 3.1 makes precise the joint low-dimensional structure used by the approximation argument. In particular, the separate statements that Y Y Y is low dimensional and X 0 ∣ Y = y X_0\mid Y=y X 0 ∣ Y = y is low dimensional are not by themselves sufficient to imply a regular joint intrinsic geometry. The submersion and local fiber-compatible-chart conditions make explicit the effective anisotropic dimension
d x ′ + α x α y d y ′ d'_x+\frac{\alpha_x}{\alpha_y}d'_y d x ′ + α y α x d y ′
that appears in (19) .
The sub-exponential tail condition is used to reduce the approximation problem to logarithmic-radius high-probability regions. It also implies the finite conditional second-moment quantity
m 2 : = ess sup y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞ . (20) m_2 := \operatorname{ess\,sup}_{y\sim P_Y} \mathbb{E}\left[\lVert X_0\rVert_2^2 \mid Y=y\right] < \infty. \tag*{(20)} m 2 := ess sup y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞. (20)
Finite-Time Optimization Assumption
Assumption 3.2 (Localized PL and stochastic-gradient regularity). Fix a score-class complexity M M M and time grid K K K . Let L K \mathcal{L}_K L K be the randomized-time population denoising objective in (9) . Define its optimal value over the class by
L K , M ⋆ : = inf θ ∈ Θ M L K ( θ ) . \mathcal{L}^{\star}_{K,M} := \inf_{\theta\in\Theta_M} \mathcal{L}_K(\theta). L K , M ⋆ := θ ∈ Θ M inf L K ( θ ) .
There exist a parameter region U K , M ⊆ Θ M \mathcal{U}_{K,M} \subseteq\Theta_M U K , M ⊆ Θ M and constants
L M < ∞ , μ M > 0 , σ M 2 < ∞ L_M < \infty,\qquad\mu_M > 0,\qquad\sigma_M^2 < \infty L M < ∞ , μ M > 0 , σ M 2 < ∞
such that the following conditions hold.
The notation L M L_M L M , μ M \mu_M μ M , σ M 2 \sigma_M^2 σ M 2 suppresses their possible dependence on the current grid, cutoff, and horizon ( K , t 0 , T ) (K,t_0,T) ( K , t 0 , T ) . Every statement below uses the constants associated with the particular randomized-time objective L K \mathcal{L}_K L K under consideration.
Local smoothness. For all θ , θ ′ ∈ U K , M \theta,\theta' \in\mathcal{U}_{K,M} θ , θ ′ ∈ U K , M ,
L K ( θ ′ ) ≤ L K ( θ ) + ⟨ ∇ L K ( θ ) , θ ′ − θ ⟩ + L M 2 ∥ θ ′ − θ ∥ 2 2 . \mathcal{L}_K(\theta') \le\mathcal{L}_K(\theta) + \langle\nabla\mathcal{L}_K(\theta),\theta'-\theta\rangle+ \frac{L_M}{2}\lVert\theta'-\theta\rVert_2^2. L K ( θ ′ ) ≤ L K ( θ ) + ⟨ ∇ L K ( θ ) , θ ′ − θ ⟩ + 2 L M ∥ θ ′ − θ ∥ 2 2 .
Localized PL inequality. For all θ ∈ U K , M \theta\in\mathcal{U}_{K,M} θ ∈ U K , M ,
∥ ∇ L K ( θ ) ∥ 2 2 ≥ 2 μ M ( L K ( θ ) − L K , M ⋆ ) . (21) \lVert\nabla\mathcal{L}_K(\theta)\rVert_2^2 \ge2\mu_M\left(\mathcal{L}_K(\theta)-\mathcal{L}^{\star}_{K,M}\right). \tag*{(21)} ∥ ∇ L K ( θ ) ∥ 2 2 ≥ 2 μ M ( L K ( θ ) − L K , M ⋆ ) . (21)
Stochastic-gradient oracle. For a single online denoising sample ξ \xi ξ , the stochastic gradient g ( θ ; ξ ) g(\theta;\xi) g ( θ ; ξ ) satisfies, for every θ ∈ U K , M \theta\in\mathcal{U}_{K,M} θ ∈ U K , M ,
E [ g ( θ ; ξ ) ∣ θ ] = ∇ L K ( θ ) , \mathbb{E}\left[g(\theta;\xi)\mid\theta\right] = \nabla\mathcal{L}_K(\theta), E [ g ( θ ; ξ ) ∣ θ ] = ∇ L K ( θ ) ,
and
E [ ∥ g ( θ ; ξ ) − ∇ L K ( θ ) ∥ 2 2 ∣ θ ] ≤ σ M 2 . \mathbb{E}\left[\lVert g(\theta;\xi)-\nabla\mathcal{L}_K(\theta)\rVert_2^2\mid\theta\right] \le\sigma_M^2. E [ ∥ g ( θ ; ξ ) − ∇ L K ( θ ) ∥ 2 2 ∣ θ ] ≤ σ M 2 .
For a mini-batch of size B B B , the corresponding variance is bounded by σ M 2 / B \sigma_M^2/B σ M 2 / B .
Trajectory containment. The initialization satisfies θ 0 ∈ U K , M \theta_0 \in\mathcal{U}_{K,M} θ 0 ∈ U K , M , and the analyzed SGD run satisfies
θ r ∈ U K , M , r = 0 , … , R . \theta_r \in\mathcal{U}_{K,M},\qquad r=0,\ldots,R. θ r ∈ U K , M , r = 0 , … , R .
This is an explicit almost-sure condition on the unmodified SGD trajectory analyzed below. A projected or stopped variant would require its own descent analysis.
Assumption 3.2 is an explicit optimization regularity assumption. We do not derive the PL inequality (21) for the entire nonlinear score-network class. Instead, the theorem quantifies the finite-time optimization error under this localized geometry and trajectory-containment condition. In particular, the constants L M L_M L M , μ M \mu_M μ M , and σ M 2 \sigma_M^2 σ M 2 are retained explicitly rather than being hidden inside the headline rate.
The optimization diagnostics reported in Appendix § 10 record finite-run loss and parameter trajectories. They do not test the population PL inequality, identify a region on which it holds, or establish Assumption 3.2.
General Training-to-Sampling Bound
Theorem 3.3 (Finite-time total-variation decomposition). Let M M M be the score-class complexity, let N = R B N = RB N = R B be the total number of online denoising samples used by SGD, and let p ^ t 0 ( ⋅ ∣ y ) \widehat{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) be the law generated by the admissibly discretized reverse sampler initialized from N ( 0 , I d x ) \mathcal{N}(0, I_{d_x}) N ( 0 , I d x ) and using s ^ = s θ ^ \widehat{s} = s_{\widehat{\theta}} s = s θ . Assume 0 < t 0 < 1 ≤ T 0 < t_0 < 1 \le T 0 < t 0 < 1 ≤ T . Suppose Assumptions 3.1 and 3.2 hold. Let
Δ k : = t k − t k − 1 , H K : = ∑ k = 1 K Δ k , Δ max : = max 1 ≤ k ≤ K Δ k . \Delta_k := t_k - t_{k-1}, \qquad H_K := \sum_{k=1}^{K} \Delta_k, \qquad\Delta_{\max} := \max_{1 \le k \le K} \Delta_k. Δ k := t k − t k − 1 , H K := k = 1 ∑ K Δ k , Δ m a x := 1 ≤ k ≤ K max Δ k . Assume that the reverse-time grid is admissible in the sense of Lemma E.1 . Then
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T + C d i s c d x + m 2 K + C s t a b H K [ A K ( M ) + E o p t ( N , M ) ] . (22) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_{Y}\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y), \widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{term}}e^{-T} + C_{\mathrm{disc}}\sqrt{\frac{d_x + m_2}{K}} + C_{\mathrm{stab}}\sqrt{H_K\left[\mathcal{A}_K(M) + \mathcal{E}_{\mathrm{opt}}(N,M)\right]}. \tag*{(22)} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T + C disc K d x + m 2 + C stab H K [ A K ( M ) + E opt ( N , M ) ] . (22) Here C t e r m C_{\mathrm{term}} C term , C d i s c C_{\mathrm{disc}} C disc , and C s t a b C_{\mathrm{stab}} C stab depend only on fixed diffusion, moment, and grid parameters. The notation for C d i s c C_{\mathrm{disc}} C disc absorbs the logarithmic factors associated with the admissible grid; none of these factors has polynomial dependence on M M M , N N N , or K K K .
Theorem 3.3 is the structural form of our main result. It separates four sources of error:
e − T ⏟ terminal initialization , K − 1 / 2 ⏟ time discretization , H K A K ( M ) ⏟ approximation/localization , H K E o p t ( N , M ) ⏟ finite-time optimization . \underbrace{e^{-T}}_{\text{terminal initialization}}, \qquad
\underbrace{K^{-1/2}}_{\text{time discretization}}, \qquad
\underbrace{\sqrt{H_K\mathcal{A}_K(M)}}_{\text{approximation/localization}}, \qquad
\underbrace{\sqrt{H_K\mathcal{E}_{\mathrm{opt}}(N,M)}}_{\text{finite-time optimization}}. terminal initialization e − T , time discretization K − 1/2 , approximation/localization H K A K ( M ) , finite-time optimization H K E opt ( N , M ) .
In particular, no relationship between M M M and N N N is imposed by the decomposition itself.
Instantiation of the Approximation and Optimization Terms
The first ingredient needed to specialize Theorem 3.3 is the approximation bound. Under Assumption 3.1, the smooth-gated dyadic-block construction described in § 2 and proved in Appendix § 6 .§ 1 yields
A K ( M ) ≤ C ~ a p p ( M − η a p p + Δ max ) , (23) \mathcal{A}_K(M) \le\widetilde{C}_{\mathrm{app}}\left(M^{-\eta_{\mathrm{app}}} + \Delta_{\max}\right), \tag*{(23)} A K ( M ) ≤ C app ( M − η app + Δ m a x ) , (23)
where
η a p p = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ . \eta_{\mathrm{app}} = \frac{2\alpha_x}{2\alpha_x + d'_x + (\alpha_x/\alpha_y)d'_y}. η app = 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x .
The logarithmic factors contained in C ~ a p p \widetilde{C}_{\mathrm{app}} C app arise from tail localization, the dyadic time cover, and the localized chart and smoothness constants. Consequently, if
Δ max ≤ O ~ ( M − η a p p ) , (24) \Delta_{\max} \le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right), \tag*{(24)} Δ m a x ≤ O ( M − η app ) , (24)
then
A K ( M ) ≤ O ~ ( M − η a p p ) . (25) \mathcal{A}_K(M) \le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). \tag*{(25)} A K ( M ) ≤ O ( M − η app ) . (25)
The second ingredient is finite-time online optimization.
Proposition 3.4 (Finite-time online SGD under localized PL geometry). Suppose Assumption 3.2 holds. Define the initial population excess risk by
Δ 0 , M : = L K ( θ 0 ) − L K , M ⋆ . \Delta_{0,M} := \mathcal{L}_K(\theta_0) - \mathcal{L}_{K,M}^{\star}. Δ 0 , M := L K ( θ 0 ) − L K , M ⋆ . and run R R R SGD iterations with mini-batch size B B B , so that N = R B N = RB N = R B . Choose
η r = 2 μ M ( r + r 0 ) , r = 0 , … , R − 1 , (26) \eta_r = \frac{2}{\mu_M(r+r_0)}, \qquad r=0,\ldots,R-1, \tag*{(26)} η r = μ M ( r + r 0 ) 2 , r = 0 , … , R − 1 , (26) where
r 0 ≥ max { 4 , 2 L M μ M } . r_0 \ge\max\left\{4,\frac{2L_M}{\mu_M}\right\}. r 0 ≥ max { 4 , μ M 2 L M } . Then there exist universal constants C 1 , C 2 > 0 C_1,C_2>0 C 1 , C 2 > 0 such that
E o p t ( N , M ) ≤ C 1 Δ 0 , M r 0 2 ( R + r 0 ) 2 + C 2 L M σ M 2 μ M 2 B ( R + r 0 ) . (27) \mathcal{E}_{\mathrm{opt}}(N,M) \le C_1\frac{\Delta_{0,M}r_0^2}{(R+r_0)^2}+C_2\frac{L_M\sigma_M^2}{\mu_M^2B(R+r_0)}. \tag*{(27)} E opt ( N , M ) ≤ C 1 ( R + r 0 ) 2 Δ 0 , M r 0 2 + C 2 μ M 2 B ( R + r 0 ) L M σ M 2 . (27)
Proposition 3.4 makes explicit the quantities suppressed in the earlier sample-complexity presentation. The first term in (27) is the initialization transient; the second is the stochastic-gradient contribution. The dependence on L M L_M L M , μ M \mu_M μ M , σ M 2 \sigma_M^2 σ M 2 , and Δ 0 , M \Delta_{0,M} Δ 0 , M is retained because these quantities can, in principle, change as the score class becomes more expressive.
Combining Theorem 3.3, (23) , and Proposition 3.4 yields the explicit version of the stopped-law guarantee.
Corollary 3.5 (Explicit stopped-law bound). Under the assumptions of Theorem 3.3, run online SGD with (26) . If the approximation construction satisfies (23) , then
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T + C d i s c d x + m 2 K + C s t a b H K [ C ~ a p p ( M − η a p p + Δ max ) + C 1 Δ 0 , M r 0 2 ( R + r 0 ) 2 + C 2 L M σ M 2 μ M 2 B ( R + r 0 ) ] . (28) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{term}}e^{-T}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}}
+C_{\mathrm{stab}}\sqrt{H_K\left[\widetilde{C}_{\mathrm{app}}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right)+C_1\frac{\Delta_{0,M}r_0^2}{(R+r_0)^2}+C_2\frac{L_M\sigma_M^2}{\mu_M^2B(R+r_0)}\right]}. \tag*{(28)} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T + C disc K d x + m 2 + C stab H K [ C app ( M − η app + Δ m a x ) + C 1 ( R + r 0 ) 2 Δ 0 , M r 0 2 + C 2 μ M 2 B ( R + r 0 ) L M σ M 2 ] . (28)
Equation (28) is the main quantitative training-to-sampling statement. It does not require that the PL, smoothness, or gradient-noise constants be uniform across network sizes, and therefore makes explicit the tradeoff between increasing approximation capacity and the resulting optimization geometry.
Simplified Rate Under Uniform Optimization Geometry
A simpler rate follows if the optimization constants remain controlled along the chosen sequence of score classes.
Corollary 3.6 (Simplified complexity for the stopped conditional law). Suppose the assumptions of Corollary 3.5 hold and, along a family of score classes, horizons, and admissible grids indexed by ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 , the constants of the corresponding objectives satisfy
sup ϵ L M ( ϵ ) ≤ L ‾ < ∞ , inf ϵ μ M ( ϵ ) ≥ μ ‾ > 0 , sup ϵ σ M 2 ( ϵ ) ≤ σ ‾ 2 < ∞ , (29) \sup_{\epsilon}L_M(\epsilon)\le\overline{L}<\infty,\qquad
\inf_{\epsilon}\mu_M(\epsilon)\ge\underline{\mu}>0,\qquad
\sup_{\epsilon}\sigma_M^2(\epsilon)\le\overline{\sigma}^2<\infty, \tag*{(29)} ϵ sup L M ( ϵ ) ≤ L < ∞ , ϵ inf μ M ( ϵ ) ≥ μ > 0 , ϵ sup σ M 2 ( ϵ ) ≤ σ 2 < ∞ , (29) and
sup ϵ Δ 0 , M ( ϵ ) ≤ Δ ‾ 0 < ∞ . \sup_{\epsilon}\Delta_{0,M}(\epsilon)\le\overline{\Delta}_0<\infty. ϵ sup Δ 0 , M ( ϵ ) ≤ Δ 0 < ∞.
Here each displayed constant is evaluated for the grid and horizon paired with M ( ϵ ) M(\epsilon) M ( ϵ ) . In the stopped-law result, t 0 t_0 t 0 is fixed; when (29) is invoked for the original-law extension, the same uniformity is additionally required along its varying cutoffs t 0 ( ϵ ) t_0(\epsilon) t 0 ( ϵ ) . Fix t 0 > 0 t_0>0 t 0 > 0 independently of ϵ \epsilon ϵ . Take B B B to be a positive constant independent of ϵ \epsilon ϵ , and choose a fixed r 0 r_0 r 0 satisfying
r 0 ≥ max { 4 , 2 L ‾ μ } . r_0 \ge\max\left\{4,\frac{2\overline{L}}{\mu}\right\}. r 0 ≥ max { 4 , μ 2 L } .
Then
E o p t ( N , M ) = O ( N − 1 ) , (30) \mathcal{E}_{\mathrm{opt}}(N,M)=\mathcal{O}(N^{-1}), \tag*{(30)} E opt ( N , M ) = O ( N − 1 ) , (30)
where the initialization transient is of smaller order O ( N − 2 ) \mathcal{O}(N^{-2}) O ( N − 2 ) .
Consequently, there exists ϵ 0 ∈ ( 0 , 1 ) \epsilon_0\in(0,1) ϵ 0 ∈ ( 0 , 1 ) such that, for every 0 < ϵ < ϵ 0 0<\epsilon<\epsilon_0 0 < ϵ < ϵ 0 , one may choose
M = Θ ~ ( ϵ − 2 / η a p p ) = Θ ~ ( ϵ − ( 2 + d x ′ / α x + d y ′ / α y ) ) , (31) M=\widetilde{\Theta}\left(\epsilon^{-2/\eta_{\mathrm{app}}}\right)
=\widetilde{\Theta}\left(\epsilon^{-(2+d_x'/\alpha_x+d_y'/\alpha_y)}\right), \tag*{(31)} M = Θ ( ϵ − 2/ η app ) = Θ ( ϵ − ( 2 + d x ′ / α x + d y ′ / α y ) ) , (31)
N = Θ ~ ( ϵ − 2 ) , (32) N=\widetilde{\Theta}\left(\epsilon^{-2}\right), \tag*{(32)} N = Θ ( ϵ − 2 ) , (32)
and
T = Θ ( log ( 1 / ϵ ) ) . T=\Theta(\log(1/\epsilon)). T = Θ ( log ( 1/ ϵ )) .
Take an admissible grid satisfying
Δ max ≤ O ~ ( M − η a p p ) \Delta_{\max}\le\widetilde{\mathcal{O}}\left(M^{-\eta_{\mathrm{app}}}\right) Δ m a x ≤ O ( M − η app )
and, up to logarithmic and fixed moment factors,
K = Θ ~ ( ( d x + m 2 ) ϵ − 2 ) . (33) K=\widetilde{\Theta}\left((d_x+m_2)\epsilon^{-2}\right). \tag*{(33)} K = Θ ( ( d x + m 2 ) ϵ − 2 ) . (33)
Then
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ O ~ ( ϵ ) . (34) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_{Y}\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]\le\widetilde{\mathcal{O}}(\epsilon). \tag*{(34)} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ O ( ϵ ) . (34)
Corollary 3.6 should be interpreted with an important qualification. The requirement
N = Θ ~ ( ϵ − 2 ) N=\widetilde{\Theta}\left(\epsilon^{-2}\right) N = Θ ( ϵ − 2 )
is the number of fresh online denoising samples consumed by SGD under the uniform optimization-geometry condition (29) . Separately, the score class must have approximation complexity
M = Θ ~ ( ϵ − 2 / η a p p ) . M=\widetilde{\Theta}\left(\epsilon^{-2/\eta_{\mathrm{app}}}\right). M = Θ ( ϵ − 2/ η app ) .
Thus the approximation requirement should not be interpreted as an additional online sample-complexity term. If L M L_M L M , μ M \mu_M μ M , or σ M 2 \sigma_M^2 σ M 2 deteriorate with increasing M M M , the appropriate guarantee is the explicit bound (28) , rather than the simplified O ~ ( ϵ − 2 ) \widetilde{\mathcal{O}}(\epsilon^{-2}) O ( ϵ − 2 ) online-sample statement.
Extension to the Original Conditional Data Law
The preceding results deliberately concern the positive-time law p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) . This distinction is essential when the clean data are supported on a strict lower-dimensional manifold. For every t 0 > 0 t_0>0 t 0 > 0 , the OU forward process Gaussian-smooths the data law, so a singular p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) need not approach p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) in ambient total variation.
To obtain convergence to the original conditional law, we therefore impose the stronger full-dimensional density condition in Assumption D.1 and use the smoothing-bias result in Appendix § 8 .
Define
a β : = max { 1 , 2 β } , a_{\beta} := \max\left\{1,\frac{2}{\beta}\right\}, a β := max { 1 , β 2 } ,
and
ρ 0 : = 2 2 α x + d x + ( α x / α y ) d y ′ , ζ 0 : = 2 α y 2 α y + d y ′ , γ 0 : = α y d x 2 α y + d y ′ . (35) \rho_0 := \frac{2}{2\alpha_x+d_x+(\alpha_x/\alpha_y)d'_y}, \qquad\zeta_0 := \frac{2\alpha_y}{2\alpha_y+d'_y}, \qquad\gamma_0 := \frac{\alpha_y d_x}{2\alpha_y+d'_y}. \tag*{(35)} ρ 0 := 2 α x + d x + ( α x / α y ) d y ′ 2 , ζ 0 := 2 α y + d y ′ 2 α y , γ 0 := 2 α y + d y ′ α y d x . (35)
Corollary 3.7 (TV bound for the original conditional law). Suppose Assumptions D.1 and 3.2 hold, and assume 0 < t 0 < 1 ≤ T 0<t_0<1\le T 0 < t 0 < 1 ≤ T . Define
m 2 : = e s s s u p y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞ , m_2 := \mathop{\mathrm{ess\,sup}}_{y\sim P_Y}\mathbb{E}\left[\left\|X_0\right\|_2^2\mid Y=y\right]<\infty, m 2 := ess sup y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞ , which is finite by Assumption D.1. Choose a class of approximation complexity M M M satisfying the later-time-regime condition
M − ρ 0 ≤ t 0 , (36) M^{-\rho_0}\le t_0, \tag*{(36)} M − ρ 0 ≤ t 0 , (36) and take an admissible grid satisfying
Δ max ≤ O ~ ( t 0 − γ 0 M − ζ 0 ) . (37) \Delta_{\max}\le\widetilde{O}\left(t_0^{-\gamma_0}M^{-\zeta_0}\right). \tag*{(37)} Δ m a x ≤ O ( t 0 − γ 0 M − ζ 0 ) . (37) Run online SGD with N = R B N=RB N = R B samples and the step-size schedule in Proposition 3.4 . Then
E S G D E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T + C d i s c d x + m 2 K + C s m o o t h t 0 ( β ∧ 2 ) / 2 + C O U d x t 0 + C s t a b H K [ C ~ a p p , 0 t 0 − γ 0 M − ζ 0 + E o p t ( N , M ) ] . (38) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_0(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{term}}e^{-T}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}}+C_{\mathrm{smooth}}t_0^{(\beta\wedge2)/2}+C_{\mathrm{OU}}d_xt_0+C_{\mathrm{stab}}\sqrt{H_K\left[\widetilde{C}_{\mathrm{app},0}t_0^{-\gamma_0}M^{-\zeta_0}+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}. \tag*{(38)} E SGD E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T + C disc K d x + m 2 + C smooth t 0 ( β ∧ 2 ) /2 + C OU d x t 0 + C stab H K [ C app , 0 t 0 − γ 0 M − ζ 0 + E opt ( N , M ) ] . (38)
Corollary 3.7 exhibits the additional smoothing-bias terms that do not occur in the stopped-law theorem. It also replaces the lower-dimensional response approximation rate by the appropriate full-dimensional later-time rate
t 0 − γ 0 M − ζ 0 . t_0^{-\gamma_0}M^{-\zeta_0}. t 0 − γ 0 M − ζ 0 .
Accordingly, the original-law and stopped-law guarantees have different regularity assumptions and different complexity requirements.
Under the uniform optimization conditions (29) , there exists ϵ 0 ∈ ( 0 , 1 ) \epsilon_0\in(0,1) ϵ 0 ∈ ( 0 , 1 ) such that the preceding expression admits the following simplified specialization for every 0 < ϵ < ϵ 0 0<\epsilon<\epsilon_0 0 < ϵ < ϵ 0 . Define
Γ a p p , 0 : = max { 2 + d y ′ α y + a β d x 2 , a β 2 ( 2 α x + d x + α x α y d y ′ ) } . (39) \Gamma_{\mathrm{app},0}:=\max\left\{2+\frac{d'_y}{\alpha_y}+\frac{a_{\beta}d_x}{2},\frac{a_{\beta}}{2}\left(2\alpha_x+d_x+\frac{\alpha_x}{\alpha_y}d'_y\right)\right\}. \tag*{(39)} Γ app , 0 := max { 2 + α y d y ′ + 2 a β d x , 2 a β ( 2 α x + d x + α y α x d y ′ ) } . (39)
and
Λ 0 : = max { 2 , Γ a p p , 0 ζ 0 − a β γ 0 } . (40) \Lambda_0:=\max\left\{2,\Gamma_{\mathrm{app},0}\zeta_0-a_{\beta}\gamma_0\right\}. \tag*{(40)} Λ 0 := max { 2 , Γ app , 0 ζ 0 − a β γ 0 } . (40)
For every 0 < ϵ < ϵ 0 0<\epsilon<\epsilon_0 0 < ϵ < ϵ 0 , choose
t 0 = Θ ~ ( ϵ a β ) , M = Θ ~ ( ϵ − Γ a p p , 0 ) , N = Θ ~ ( ϵ − 2 ) , (41) t_0=\widetilde{\Theta}\left(\epsilon^{a_{\beta}}\right),\qquad M=\widetilde{\Theta}\left(\epsilon^{-\Gamma_{\mathrm{app},0}}\right),\qquad N=\widetilde{\Theta}\left(\epsilon^{-2}\right), \tag*{(41)} t 0 = Θ ( ϵ a β ) , M = Θ ( ϵ − Γ app , 0 ) , N = Θ ( ϵ − 2 ) , (41)
together with
T = Θ ( log ( 1 / ϵ ) ) T=\Theta(\log(1/\epsilon)) T = Θ ( log ( 1/ ϵ ))
and an admissible grid satisfying, up to fixed dimension, moment, and logarithmic factors,
K = Θ ~ ( ϵ − Λ 0 ) . (42) K = \widetilde{\Theta}\left(\epsilon^{-\Lambda_0}\right). \tag*{(42)} K = Θ ( ϵ − Λ 0 ) . (42)
Then
E S G D E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ O ~ ( ϵ ) . (43) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_{Y}\left[\operatorname{TV}\left(p_0(\cdot\mid Y), \widehat{p}_{t_0}(\cdot\mid Y)\right)\right] \leq\widetilde{O}(\epsilon). \tag*{(43)} E SGD E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ O ( ϵ ) . (43)
The complexity exponent Γ a p p , 0 \Gamma_{\mathrm{app},0} Γ app , 0 in (39) concerns the approximation class M M M , whereas the online stochastic-gradient sample requirement remains Θ ~ ( ϵ − 2 ) \widetilde{\Theta}(\epsilon^{-2}) Θ ( ϵ − 2 ) under uniform optimization geometry. This separation is the analogue, for the original-law extension, of the distinction between M M M and N N N in Corollary 3.6 .
Conclusion
We analyzed conditional diffusion trained by fresh-sample online denoising SGD. The main result is a training-to-sampling decomposition for the stopped law p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) that keeps terminal initialization, reverse-time discretization, score-class approximation, and finite-time optimization separate. In particular, M M M denotes approximation capacity, whereas N = R B N = RB N = R B denotes the number of online denoising samples; these are distinct resources. Under the stated anisotropic fibered-geometry and approximation-class compatibility assumptions, A K ( M ) = O ~ ( M − η a p p ) \mathcal{A}_K(M) = \widetilde{O}(M^{-\eta_{\mathrm{app}}}) A K ( M ) = O ( M − η app ) . Under uniform localized optimization geometry, the separate sufficient scales are
M = Θ ~ ( ϵ − ( 2 + d x ′ / α x + d y ′ / α y ) ) , N = Θ ~ ( ϵ − 2 ) , M = \widetilde{\Theta}\left(\epsilon^{-\left(2+d_x'/\alpha_x+d_y'/\alpha_y\right)}\right), \qquad N = \widetilde{\Theta}\left(\epsilon^{-2}\right), M = Θ ( ϵ − ( 2 + d x ′ / α x + d y ′ / α y ) ) , N = Θ ( ϵ − 2 ) ,
up to the stated grid and logarithmic factors.
The optimization guarantee is conditional on an explicit PL geometry and trajectory-containment assumption; the paper does not derive that geometry for general neural score networks. Likewise, the intrinsic-dimensional approximation step adapts existing conditional approximation theory under the class-containment and regularity conditions stated in the paper. Under stronger full-dimensional Besov and weighted-gradient regularity, the smoothing bias can also be controlled, yielding an extension to p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) . Establishing trajectory containment for concrete architectures and optimizers, and deriving conditional optimization guarantees without a PL assumption, remain important open problems.
Algorithm 1 Conditional Score Training and Sampling for the OU Conditional Diffusion Model
Input: Online sampling access to P 0 ( d x , d y ) P_0(dx,dy) P 0 ( d x , d y ) , time interval [ t 0 , T ] [t_0,T] [ t 0 , T ] , admissible grid { t k } k = 0 K \{t_k\}_{k=0}^K { t k } k = 0 K with t K = T t_K=T t K = T , complexity M M M , initial parameter θ 0 ∈ Θ M \theta_0 \in\Theta_M θ 0 ∈ Θ M , score network s θ ∈ F Θ , M s_\theta\in\mathcal{F}_{\Theta,M} s θ ∈ F Θ , M , mini-batch size B B B , number of training iterations R R R , and decreasing step sizes η r = 2 / ( μ M ( r + r 0 ) ) \eta_r = 2/(\mu_M(r+r_0)) η r = 2/ ( μ M ( r + r 0 )) , where r 0 ≥ max { 4 , 2 L M / μ M } r_0 \ge\max\{4,2L_M/\mu_M\} r 0 ≥ max { 4 , 2 L M / μ M } .
The online denoising-sample budget is N = R B N=RB N = R B .
Set Δ k = t k − t k − 1 \Delta_k=t_k-t_{k-1} Δ k = t k − t k − 1 , H K = ∑ k = 1 K Δ k H_K=\sum_{k=1}^K\Delta_k H K = ∑ k = 1 K Δ k , and P ( J = k ) = Δ k / H K \mathbb{P}(J=k)=\Delta_k/H_K P ( J = k ) = Δ k / H K , for k = 1 , … , K k=1,\ldots,K k = 1 , … , K .
Initialize θ ← θ 0 \theta\leftarrow\theta_0 θ ← θ 0 .
Training: Conditional Denoising Score Matching
for r = 0 r=0 r = 0 to R − 1 R-1 R − 1 do
Draw a fresh mini-batch { ( x 0 , i , y i ) } i = 1 B ∼ P 0 \{(x_{0,i},y_i)\}_{i=1}^B \sim P_0 {( x 0 , i , y i ) } i = 1 B ∼ P 0 .
Sample J i ∼ π K J_i \sim\pi_K J i ∼ π K and ε i ∼ N ( 0 , I d x ) \varepsilon_i \sim\mathcal{N}(0,I_{d_x}) ε i ∼ N ( 0 , I d x ) , independently.
Set t i = t J i t_i=t_{J_i} t i = t J i , σ t i 2 = 1 − e − 2 t i \sigma_{t_i}^2=1-e^{-2t_i} σ t i 2 = 1 − e − 2 t i , and x t i , i = e − t i x 0 , i + σ t i ε i x_{t_i,i}=e^{-t_i}x_{0,i}+\sigma_{t_i}\varepsilon_i x t i , i = e − t i x 0 , i + σ t i ε i .
Set z i = − ( x t i , i − e − t i x 0 , i ) / σ t i 2 z_i=-(x_{t_i,i}-e^{-t_i}x_{0,i})/\sigma_{t_i}^2 z i = − ( x t i , i − e − t i x 0 , i ) / σ t i 2 .
Compute L ^ r ( θ ) = B − 1 ∑ i = 1 B ∥ s θ ( x t i , i , y i , t i ) − z i ∥ 2 2 \widehat{\mathcal{L}}_r(\theta)=B^{-1}\sum_{i=1}^B\lVert s_\theta(x_{t_i,i},y_i,t_i)-z_i\rVert_2^2 L r ( θ ) = B − 1 ∑ i = 1 B ∥ s θ ( x t i , i , y i , t i ) − z i ∥ 2 2 .
Update θ ← θ − η r ∇ θ L ^ r ( θ ) \theta\leftarrow\theta-\eta_r\nabla_\theta\widehat{\mathcal{L}}_r(\theta) θ ← θ − η r ∇ θ L r ( θ ) .
end for
Set θ ^ ← θ \widehat{\theta}\leftarrow\theta θ ← θ .
Sampling: Conditional Generation
Given y y y , sample x t K ∼ N ( 0 , I d x ) x_{t_K}\sim\mathcal{N}(0,I_{d_x}) x t K ∼ N ( 0 , I d x ) .
for k = K k=K k = K down to 1 1 1 do
Set h k = t k − t k − 1 h_k=t_k-t_{k-1} h k = t k − t k − 1 and sample ξ k ∼ N ( 0 , I d x ) \xi_k\sim\mathcal{N}(0,I_{d_x}) ξ k ∼ N ( 0 , I d x ) .
Evaluate s ^ k = s θ ^ ( x t k , y , t k ) \widehat{s}_k=s_{\widehat{\theta}}(x_{t_k},y,t_k) s k = s θ ( x t k , y , t k ) .
Set x t k − 1 = e h k x t k + 2 ( e h k − 1 ) s ^ k + e 2 h k − 1 ξ k x_{t_{k-1}}=e^{h_k}x_{t_k}+2(e^{h_k}-1)\widehat{s}_k+\sqrt{e^{2h_k}-1}\xi_k x t k − 1 = e h k x t k + 2 ( e h k − 1 ) s k + e 2 h k − 1 ξ k .
end for
Return x t 0 x_{t_0} x t 0 .
Related Work
Diffusion and score-based generative models build on reverse-time stochastic dynamics [1 ] and have been developed into modern denoising diffusion and score-SDE frameworks [29 , 16 , 30 ] . Recent theoretical work has studied how score-estimation error propagates to sampling error, as well as discretization and convergence of reverse diffusion samplers (Chen et al., 2023b; Benton et al., 2024; Li et al., 2024a,b; Dou et al., 2024). A parallel line of work develops statistical guarantees for diffusion models, including score approximation, minimax distribution estimation, low-dimensional adaptation, and sample-complexity bounds for denoising score matching [4 , 25 , 37 , 35 , 18 , 23 ] (Li and Yan 2024). Conditional diffusion models have also been studied for guided generation and conditional distribution estimation, including classifier-free guidance, reward-directed conditional diffusion, and minimax or manifold-adaptive conditional diffusion guarantees [2 , 36 , 8 , 33 , 17 , 22 ] .
Algorithm-dependent diffusion training has been analyzed in several unconditional settings. Gaur et al. [13 ] derive a finite-time SGD sample-complexity bound without empirical-risk minimizer access; Han et al. [14 ] analyze optimization and generalization for a particular two-layer score parameterization trained by gradient descent; and Strasman et al. [32 ] study non-asymptotic SGD convergence for weighted denoising score matching, including an overparameterized-network regime. Our contribution is not the first finite-time optimization analysis for diffusion models. It combines such an online population-optimization component with conditional, joint-intrinsic score approximation and conditional reverse-process stability, while keeping approximation capacity and online training budget separate. This work is inspired by existing theoretical analyses such as [9 ] , [10 ] , [11 ] , as well as flow-matching [12 ] and diffusion models [13 , 31 ] .
Proofs of Intermediate Lemmas
This section proves the approximation, finite-time optimization, and smoothing-bias ingredients used in the main results. Throughout, we keep the score-class complexity M M M separate from the online denoising-sample budget N = R B N = RB N = R B .
Randomized-Time Approximation Error
Lemma B.1 (Randomized-time conditional score approximation). Suppose Assumption 3.1 holds, let M ≥ 2 M \ge2 M ≥ 2 , and let F Θ , M \mathcal{F}_{\Theta,M} F Θ , M be the smooth-gated time-conditioned score class described in § 2 . Then
A K ( M ) ≤ O ~ ( M − η a p p + Δ max ) , (44) \mathcal{A}_{K}(M) \le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right), \tag*{(44)} A K ( M ) ≤ O ( M − η app + Δ m a x ) , (44) where
η a p p = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ . \eta_{\mathrm{app}}=\frac{2\alpha_x}{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y}. η app = 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x . Consequently, if
Δ max ≤ O ~ ( M − η a p p ) , (45) \Delta_{\max}\le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right), \tag*{(45)} Δ m a x ≤ O ( M − η app ) , (45) then
A K ( M ) ≤ O ~ ( M − η a p p ) . (46) \mathcal{A}_{K}(M)\le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). \tag*{(46)} A K ( M ) ≤ O ( M − η app ) . (46)
Proof. Recall from (13) that
A K ( M ) : = inf θ ∈ Θ M E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . \mathcal{A}_{K}(M):=\inf_{\theta\in\Theta_M}\mathbb{E}\left[\left\|s_{\theta}(X_{t_J},Y,t_J)-s^{\star}(X_{t_J},t_J,Y)\right\|_2^2\right]. A K ( M ) := θ ∈ Θ M inf E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] .
Unlike the previous formulation, the proof does not introduce or assume the existence of a parameter attaining this infimum. It is sufficient to construct one comparison predictor in F Θ , M \mathcal{F}_{\Theta,M} F Θ , M .
Step 1: Localization. Let
R M : = C l o c log M , R_M:=C_{\mathrm{loc}}\log M, R M := C loc log M ,
where C l o c > 0 C_{\mathrm{loc}}>0 C loc > 0 will be chosen sufficiently large, and define
G M : = { ∥ Y ∥ 2 ≤ R M , ∥ X 0 ∥ 2 ≤ R M , ∥ ε ∥ 2 ≤ R M } . (47) \mathcal{G}_M:=\left\{\|Y\|_2\le R_M,\ \|X_0\|_2\le R_M,\ \|\varepsilon\|_2\le R_M\right\}. \tag*{(47)} G M := { ∥ Y ∥ 2 ≤ R M , ∥ X 0 ∥ 2 ≤ R M , ∥ ε ∥ 2 ≤ R M } . (47)
Here
X t J = e − t J X 0 + 1 − e − 2 t J ε , ε ∼ N ( 0 , I d x ) . X_{t_J}=e^{-t_J}X_0+\sqrt{1-e^{-2t_J}}\varepsilon,\qquad\varepsilon\sim\mathcal{N}(0,I_{d_x}). X t J = e − t J X 0 + 1 − e − 2 t J ε , ε ∼ N ( 0 , I d x ) .
By Lemma E.2, applied with localization radius R M R_M R M , the sub-exponential assumptions on X 0 X_0 X 0 and Y Y Y , together with Gaussian concentration for ε \varepsilon ε , imply that there exist constants C 1 , C 2 , c 1 , c 2 > 0 C_1,C_2,c_1,c_2>0 C 1 , C 2 , c 1 , c 2 > 0 such that
P ( G M c ) ≤ C 1 e − c 1 R M + C 2 e − c 2 R M 2 . (48) \mathbb{P}(\mathcal{G}_M^c)\le C_1e^{-c_1R_M}+C_2e^{-c_2R_M^2}. \tag*{(48)} P ( G M c ) ≤ C 1 e − c 1 R M + C 2 e − c 2 R M 2 . (48)
Moreover, on G M G_M G M ,
∥ X t J ∥ 2 ≤ 2 R M , \lVert X_{t_J}\rVert_2 \le2R_M, ∥ X t J ∥ 2 ≤ 2 R M ,
and, because t J ≥ t 0 > 0 t_J \ge t_0 > 0 t J ≥ t 0 > 0 , the denoising target
Z J : = ∇ x log q t J ( X t J ∣ X 0 ) = − X t J − e − t J X 0 1 − e − 2 t J Z_J := \nabla_x \log q_{t_J}(X_{t_J}\mid X_0) = -\frac{X_{t_J}-e^{-t_J}X_0}{1-e^{-2t_J}} Z J := ∇ x log q t J ( X t J ∣ X 0 ) = − 1 − e − 2 t J X t J − e − t J X 0
satisfies
∥ Z J ∥ 2 ≤ R M 1 − e − 2 t 0 . (49) \lVert Z_J\rVert_2 \le\frac{R_M}{\sqrt{1-e^{-2t_0}}}. \tag*{(49)} ∥ Z J ∥ 2 ≤ 1 − e − 2 t 0 R M . (49)
Thus, after localization, the approximation problem is restricted to a compact response–conditioning region whose radius grows only logarithmically with M M M .
Step 2: Approximation on the localized region. Apply Lemma E.3 with approximation scale M M M . Under the joint fibered intrinsic geometry, anisotropic smoothness, and approximation-class compatibility in Assumption 3.1, there exists a comparison network
s ~ M ∈ F Θ , M \widetilde{s}_M \in\mathcal{F}_{\Theta,M} s M ∈ F Θ , M
such that
E [ ∥ s ~ M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M ] ≤ C ~ a p p ( M − η a p p + Δ max ) . (50) \mathbb{E}\left[\left\lVert\widetilde{s}_M(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\rVert_2^2\mathbf{1}_{G_M}\right]
\le\widetilde{C}_{\mathrm{app}}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right). \tag*{(50)} E [ ∥ s M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M ] ≤ C app ( M − η app + Δ m a x ) . (50)
The hidden logarithmic factors account for the localization radius R M = O ( log M ) R_M=O(\log M) R M = O ( log M ) , the dyadic time cover, the lower cutoff t 0 t_0 t 0 , and the uniform chart and Hölder constants on the localized region. The exponent
η a p p = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ \eta_{\mathrm{app}}=\frac{2\alpha_x}{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y} η app = 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x
arises from balancing approximation resolution in the response and conditioning intrinsic coordinates. In particular, if h x h_x h x and h y h_y h y denote the corresponding resolutions, the anisotropic balance
h y ≍ h x α x / α y h_y\asymp h_x^{\alpha_x/\alpha_y} h y ≍ h x α x / α y
gives the effective intrinsic covering dimension
d x ′ + α x α y d y ′ d'_x+\frac{\alpha_x}{\alpha_y}d'_y d x ′ + α y α x d y ′
and hence the squared approximation rate appearing in (50) .
Step 3: Control of the tail complement. It remains to bound the approximation error on G M c G_M^c G M c . The bounded-parameter smooth score class used in the approximation construction has at most polynomial output growth. Together with the sub-exponential moments of X 0 X_0 X 0 and Y Y Y , Gaussian moments of ε \varepsilon ε , and the positive lower cutoff t 0 t_0 t 0 , Lemma E.2 gives constants q m o m , q l o g ≥ 0 q_{\mathrm{mom}},q_{\mathrm{log}}\ge0 q mom , q log ≥ 0 such that
E [ ∥ s ~ M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 4 ] ≤ C m o m M q m o m ( log M ) q l o g . (51) \mathbb{E}\left[\left\lVert\widetilde{s}_M(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\rVert_2^4\right]
\le C_{\mathrm{mom}}M^{q_{\mathrm{mom}}}(\log M)^{q_{\mathrm{log}}}. \tag*{(51)} E [ ∥ s M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 4 ] ≤ C mom M q mom ( log M ) q log . (51)
By Cauchy–Schwarz,
E [ ∥ s ~ M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M c ] ≤ ( E [ ∥ s ~ M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 4 ] ) 1 / 2 P ( G M c ) 1 / 2 . (52) \mathbb{E}\left[\left\|\widetilde{s}_M(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^2\mathbf{1}_{\mathcal{G}_M^c}\right]
\leq\left(\mathbb{E}\left[\left\|\widetilde{s}_M(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^4\right]\right)^{1/2}\mathbb{P}(\mathcal{G}_M^c)^{1/2}. \tag*{(52)} E [ ∥ s M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M c ] ≤ ( E [ ∥ s M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 4 ] ) 1/2 P ( G M c ) 1/2 . (52)
Substituting (48) and (51) , and using R M = C l o c log M R_M=C_{\mathrm{loc}}\log M R M = C loc log M , gives
P ( G M c ) ≤ C 1 M − c 1 C l o c + C 2 exp [ − c 2 C l o c 2 ( log M ) 2 ] . \mathbb{P}(\mathcal{G}_M^c)\leq C_1M^{-c_1C_{\mathrm{loc}}}+C_2\exp\left[-c_2C_{\mathrm{loc}}^2(\log M)^2\right]. P ( G M c ) ≤ C 1 M − c 1 C loc + C 2 exp [ − c 2 C loc 2 ( log M ) 2 ] .
The second term is super-polynomially small. Since q m o m q_{\mathrm{mom}} q mom is fixed for the chosen approximation family, we may choose C l o c C_{\mathrm{loc}} C loc sufficiently large that the first term dominates the polynomial moment envelope by an arbitrary prescribed polynomial power. In particular, we may ensure
E [ ∥ s ~ M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M c ] ≤ O ~ ( M − 2 ) . (53) \mathbb{E}\left[\left\|\widetilde{s}_M(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^2\mathbf{1}_{\mathcal{G}_M^c}\right]\leq\widetilde{O}(M^{-2}). \tag*{(53)} E [ ∥ s M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M c ] ≤ O ( M − 2 ) . (53)
Since 0 < η a p p ≤ 1 0<\eta_{\mathrm{app}}\leq1 0 < η app ≤ 1 , this term is of smaller order than M − η a p p M^{-\eta_{\mathrm{app}}} M − η app .
Step 4: Pass from the candidate to the class infimum. Combining (50) and (53) yields
E [ ∥ s ~ M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] ≤ O ~ ( M − η a p p + Δ max ) . (54) \mathbb{E}\left[\left\|\widetilde{s}_M(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^2\right]
\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right). \tag*{(54)} E [ ∥ s M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] ≤ O ( M − η app + Δ m a x ) . (54)
Since s ~ M ∈ F Θ , M \widetilde{s}_M\in\mathcal{F}_{\Theta,M} s M ∈ F Θ , M , the definition of A K ( M ) \mathcal{A}_K(M) A K ( M ) immediately gives
A K ( M ) ≤ E [ ∥ s ~ M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] . \mathcal{A}_K(M)\leq\mathbb{E}\left[\left\|\widetilde{s}_M(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^2\right]. A K ( M ) ≤ E [ ∥ s M ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] .
Therefore
A K ( M ) ≤ O ~ ( M − η a p p + Δ max ) , \mathcal{A}_K(M)\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right), A K ( M ) ≤ O ( M − η app + Δ m a x ) ,
which proves (44) . Under (45) , the two terms have the same or smaller order, giving
A K ( M ) ≤ O ~ ( M − η a p p ) . \mathcal{A}_K(M)\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). A K ( M ) ≤ O ( M − η app ) .
Remark B.2 (No risk-minimizer access is used). Lemma B.1 is formulated entirely through the infimum A K ( M ) \mathcal{A}_K(M) A K ( M ) . The proof constructs a single admissible comparison network and upper-bounds the infimum by its error. Neither existence of an exact best-in-class minimizer nor algorithmic access to such a minimizer is required.
Finite-Time Online Optimization
We next prove Proposition 3.4. For mathematical clarity, the localized optimization argument is stated for a training trajectory that remains inside the PL region throughout the analyzed run. This avoids conditioning the stochastic-gradient oracle on a future trajectory event. If trajectory containment is instead available only with high probability, an additional stopped-process or exit-time argument is required; such a conclusion does not follow merely by conditioning the final bound on the future localization event.
Proof of Proposition 3.4. Fix M M M and K K K , and write
F ( θ ) : = L K ( θ ) , F ⋆ : = L K , M ⋆ , F(\theta) := \mathcal{L}_K(\theta), \qquad F^\star:= \mathcal{L}^\star_{K,M}, F ( θ ) := L K ( θ ) , F ⋆ := L K , M ⋆ ,
and
Δ 0 , M : = F ( θ 0 ) − F ⋆ . (55) \Delta_{0,M} := F(\theta_0) - F^\star. \tag*{(55)} Δ 0 , M := F ( θ 0 ) − F ⋆ . (55)
Note that F ⋆ F^\star F ⋆ is the infimum of the population objective over Θ M \Theta_M Θ M ; attainment is not required. At iteration r r r , SGD uses a fresh mini-batch { ξ r , b } b = 1 B \{\xi_{r,b}\}_{b=1}^{B} { ξ r , b } b = 1 B and forms
g ˉ r : = 1 B ∑ b = 1 B g ( θ r ; ξ r , b ) , \bar{g}_r := \frac{1}{B}\sum_{b=1}^{B}g(\theta_r;\xi_{r,b}), g ˉ r := B 1 b = 1 ∑ B g ( θ r ; ξ r , b ) ,
followed by
θ r + 1 = θ r − η r g ˉ r . (56) \theta_{r+1} = \theta_r - \eta_r\bar{g}_r. \tag*{(56)} θ r + 1 = θ r − η r g ˉ r . (56)
After R R R iterations, the total number of fresh online denoising samples is
Let F r \mathcal{F}_r F r denote the sigma-field generated by the initialization and all stochastic-gradient samples through iteration r − 1 r-1 r − 1 . Since the batch at iteration r r r is fresh and independent of F r \mathcal{F}_r F r , the stochastic-gradient assumption gives
E [ g ˉ r ∣ F r ] = ∇ F ( θ r ) (57) \mathbb{E}\left[\bar{g}_r \mid\mathcal{F}_r\right] = \nabla F(\theta_r) \tag*{(57)} E [ g ˉ r ∣ F r ] = ∇ F ( θ r ) (57)
and
E [ ∥ g ˉ r − ∇ F ( θ r ) ∥ 2 2 ∣ F r ] ≤ σ M 2 B . (58) \mathbb{E}\left[\left\|\bar{g}_r-\nabla F(\theta_r)\right\|_2^2 \mid\mathcal{F}_r\right] \le\frac{\sigma_M^2}{B}. \tag*{(58)} E [ ∥ g ˉ r − ∇ F ( θ r ) ∥ 2 2 ∣ F r ] ≤ B σ M 2 . (58)
Consequently,
E [ ∥ g ˉ r ∥ 2 2 ∣ F r ] = ∥ ∇ F ( θ r ) ∥ 2 2 + E [ ∥ g ˉ r − ∇ F ( θ r ) ∥ 2 2 ∣ F r ] ≤ ∥ ∇ F ( θ r ) ∥ 2 2 + σ M 2 B . (59) \begin{aligned}
\mathbb{E}\left[\left\|\bar{g}_r\right\|_2^2 \mid\mathcal{F}_r\right]
&= \left\|\nabla F(\theta_r)\right\|_2^2 + \mathbb{E}\left[\left\|\bar{g}_r-\nabla F(\theta_r)\right\|_2^2 \mid\mathcal{F}_r\right] \\
&\le\left\|\nabla F(\theta_r)\right\|_2^2 + \frac{\sigma_M^2}{B}. \tag*{(59)}
\end{aligned} E [ ∥ g ˉ r ∥ 2 2 ∣ F r ] = ∥ ∇ F ( θ r ) ∥ 2 2 + E [ ∥ g ˉ r − ∇ F ( θ r ) ∥ 2 2 ∣ F r ] ≤ ∥ ∇ F ( θ r ) ∥ 2 2 + B σ M 2 . (59)
We use the decreasing step-size sequence
η r = 2 μ M ( r + r 0 ) , r = 0 , … , R − 1 , (60) \eta_r = \frac{2}{\mu_M(r+r_0)}, \qquad r=0,\ldots,R-1, \tag*{(60)} η r = μ M ( r + r 0 ) 2 , r = 0 , … , R − 1 , (60)
where
r 0 ≥ max { 4 , 2 L M μ M } . r_0 \ge\max\left\{4,\frac{2L_M}{\mu_M}\right\}. r 0 ≥ max { 4 , μ M 2 L M } .
Hence
η r ≤ 2 μ M r 0 ≤ 1 L M . \eta_r \le\frac{2}{\mu_M r_0} \le\frac{1}{L_M}. η r ≤ μ M r 0 2 ≤ L M 1 .
Because the analyzed trajectory remains in U K , M \mathcal{U}_{K,M} U K , M , local L M L_M L M -smoothness gives
F ( θ r + 1 ) ≤ F ( θ r ) − η r ⟨ ∇ F ( θ r ) , g ˉ r ⟩ + L M η r 2 2 ∥ g ˉ r ∥ 2 2 . (61) F(\theta_{r+1}) \le F(\theta_r) - \eta_r\left\langle\nabla F(\theta_r),\bar{g}_r\right\rangle+ \frac{L_M\eta_r^2}{2}\left\|\bar{g}_r\right\|_2^2. \tag*{(61)} F ( θ r + 1 ) ≤ F ( θ r ) − η r ⟨ ∇ F ( θ r ) , g ˉ r ⟩ + 2 L M η r 2 ∥ g ˉ r ∥ 2 2 . (61)
Taking conditional expectation given F r \mathcal{F}_r F r and applying (57) –(59) ,
E [ F ( θ r + 1 ) ∣ F r ] ≤ F ( θ r ) − η r ∥ ∇ F ( θ r ) ∥ 2 2 + L M η r 2 2 ( ∥ ∇ F ( θ r ) ∥ 2 2 + σ M 2 B ) = F ( θ r ) − η r ( 1 − L M η r 2 ) ∥ ∇ F ( θ r ) ∥ 2 2 + L M η r 2 σ M 2 2 B . (62) \begin{aligned}
\mathbb{E}\left[F(\theta_{r+1}) \mid\mathcal{F}_r\right]
&\leq F(\theta_r)-\eta_r\left\|\nabla F(\theta_r)\right\|_2^2
+\frac{L_M\eta_r^2}{2}\left(\left\|\nabla F(\theta_r)\right\|_2^2+\frac{\sigma_M^2}{B}\right)\\
&=F(\theta_r)-\eta_r\left(1-\frac{L_M\eta_r}{2}\right)\left\|\nabla F(\theta_r)\right\|_2^2+\frac{L_M\eta_r^2\sigma_M^2}{2B}. \tag*{(62)}
\end{aligned} E [ F ( θ r + 1 ) ∣ F r ] ≤ F ( θ r ) − η r ∥ ∇ F ( θ r ) ∥ 2 2 + 2 L M η r 2 ( ∥ ∇ F ( θ r ) ∥ 2 2 + B σ M 2 ) = F ( θ r ) − η r ( 1 − 2 L M η r ) ∥ ∇ F ( θ r ) ∥ 2 2 + 2 B L M η r 2 σ M 2 . (62)
Since η r ≤ 1 / L M \eta_r \leq1/L_M η r ≤ 1/ L M ,
1 − L M η r 2 ≥ 1 2 . 1-\frac{L_M\eta_r}{2}\geq\frac{1}{2}. 1 − 2 L M η r ≥ 2 1 .
Therefore
E [ F ( θ r + 1 ) ∣ F r ] ≤ F ( θ r ) − η r 2 ∥ ∇ F ( θ r ) ∥ 2 2 + L M η r 2 σ M 2 2 B . (63) \mathbb{E}\left[F(\theta_{r+1}) \mid\mathcal{F}_r\right]\leq F(\theta_r)-\frac{\eta_r}{2}\left\|\nabla F(\theta_r)\right\|_2^2+\frac{L_M\eta_r^2\sigma_M^2}{2B}. \tag*{(63)} E [ F ( θ r + 1 ) ∣ F r ] ≤ F ( θ r ) − 2 η r ∥ ∇ F ( θ r ) ∥ 2 2 + 2 B L M η r 2 σ M 2 . (63)
The localized PL inequality gives
∥ ∇ F ( θ r ) ∥ 2 2 ≥ 2 μ M ( F ( θ r ) − F ⋆ ) . \left\|\nabla F(\theta_r)\right\|_2^2\geq2\mu_M\left(F(\theta_r)-F^\star\right). ∥ ∇ F ( θ r ) ∥ 2 2 ≥ 2 μ M ( F ( θ r ) − F ⋆ ) .
Substituting into (63) yields
E [ F ( θ r + 1 ) − F ⋆ ∣ F r ] ≤ ( 1 − μ M η r ) ( F ( θ r ) − F ⋆ ) + L M η r 2 σ M 2 2 B . (64) \mathbb{E}\left[F(\theta_{r+1})-F^\star\mid\mathcal{F}_r\right]\leq(1-\mu_M\eta_r)\left(F(\theta_r)-F^\star\right)+\frac{L_M\eta_r^2\sigma_M^2}{2B}. \tag*{(64)} E [ F ( θ r + 1 ) − F ⋆ ∣ F r ] ≤ ( 1 − μ M η r ) ( F ( θ r ) − F ⋆ ) + 2 B L M η r 2 σ M 2 . (64)
Define
e r : = E S G D [ F ( θ r ) − F ⋆ ] . e_r:=\mathbb{E}_{\mathrm{SGD}}\left[F(\theta_r)-F^\star\right]. e r := E SGD [ F ( θ r ) − F ⋆ ] .
Taking expectations in (64) and substituting (60) ,
e r + 1 ≤ ( 1 − 2 r + r 0 ) e r + 2 L M σ M 2 μ M 2 B ( r + r 0 ) 2 . (65) e_{r+1}\leq\left(1-\frac{2}{r+r_0}\right)e_r+\frac{2L_M\sigma_M^2}{\mu_M^2B(r+r_0)^2}. \tag*{(65)} e r + 1 ≤ ( 1 − r + r 0 2 ) e r + μ M 2 B ( r + r 0 ) 2 2 L M σ M 2 . (65)
Set
A M : = 2 L M σ M 2 μ M 2 B . A_M:=\frac{2L_M\sigma_M^2}{\mu_M^2B}. A M := μ M 2 B 2 L M σ M 2 .
Then
e r + 1 ≤ ( 1 − 2 r + r 0 ) e r + A M ( r + r 0 ) 2 . e_{r+1}\leq\left(1-\frac{2}{r+r_0}\right)e_r+\frac{A_M}{(r+r_0)^2}. e r + 1 ≤ ( 1 − r + r 0 2 ) e r + ( r + r 0 ) 2 A M .
Since r 0 ≥ 4 r_0\geq4 r 0 ≥ 4 , all contraction factors are nonnegative. Unrolling the recursion gives
e R ≤ Δ 0 , M ∏ j = 0 R − 1 ( 1 − 2 j + r 0 ) + ∑ j = 0 R − 1 A M ( j + r 0 ) 2 ∏ ℓ = j + 1 R − 1 ( 1 − 2 ℓ + r 0 ) . (66) \begin{aligned}
e_R\leq{}&\Delta_{0,M}\prod_{j=0}^{R-1}\left(1-\frac{2}{j+r_0}\right)\\
&+\sum_{j=0}^{R-1}\frac{A_M}{(j+r_0)^2}\prod_{\ell=j+1}^{R-1}\left(1-\frac{2}{\ell+r_0}\right). \tag*{(66)}
\end{aligned} e R ≤ Δ 0 , M j = 0 ∏ R − 1 ( 1 − j + r 0 2 ) + j = 0 ∑ R − 1 ( j + r 0 ) 2 A M ℓ = j + 1 ∏ R − 1 ( 1 − ℓ + r 0 2 ) . (66)
For the initialization term,
∏ j = 0 R − 1 ( 1 − 2 j + r 0 ) = ∏ j = 0 R − 1 j + r 0 − 2 j + r 0 = ( r 0 − 2 ) ( r 0 − 1 ) ( R + r 0 − 2 ) ( R + r 0 − 1 ) ≤ r 0 2 ( R + r 0 − 2 ) 2 . (67) \prod_{j=0}^{R-1}\left(1-\frac{2}{j+r_0}\right)=\prod_{j=0}^{R-1}\frac{j+r_0-2}{j+r_0}
=\frac{(r_0-2)(r_0-1)}{(R+r_0-2)(R+r_0-1)}
\le\frac{r_0^2}{(R+r_0-2)^2}. \tag*{(67)} j = 0 ∏ R − 1 ( 1 − j + r 0 2 ) = j = 0 ∏ R − 1 j + r 0 j + r 0 − 2 = ( R + r 0 − 2 ) ( R + r 0 − 1 ) ( r 0 − 2 ) ( r 0 − 1 ) ≤ ( R + r 0 − 2 ) 2 r 0 2 . (67)
For j ≤ R − 1 j\le R-1 j ≤ R − 1 ,
∏ ℓ = j + 1 R − 1 ( 1 − 2 ℓ + r 0 ) = ( j + r 0 − 1 ) ( j + r 0 ) ( R + r 0 − 2 ) ( R + r 0 − 1 ) . (68) \prod_{\ell=j+1}^{R-1}\left(1-\frac{2}{\ell+r_0}\right)=\frac{(j+r_0-1)(j+r_0)}{(R+r_0-2)(R+r_0-1)}. \tag*{(68)} ℓ = j + 1 ∏ R − 1 ( 1 − ℓ + r 0 2 ) = ( R + r 0 − 2 ) ( R + r 0 − 1 ) ( j + r 0 − 1 ) ( j + r 0 ) . (68)
Hence
e R ≤ r 0 2 Δ 0 , M ( R + r 0 − 2 ) 2 + A M ( R + r 0 − 2 ) ( R + r 0 − 1 ) ∑ j = 0 R − 1 j + r 0 − 1 j + r 0 ≤ r 0 2 Δ 0 , M ( R + r 0 − 2 ) 2 + A M R ( R + r 0 − 2 ) ( R + r 0 − 1 ) ≤ r 0 2 Δ 0 , M ( R + r 0 − 2 ) 2 + A M R + r 0 − 2 . (69) \begin{aligned}
e_R &\le\frac{r_0^2\Delta_{0,M}}{(R+r_0-2)^2}
+\frac{A_M}{(R+r_0-2)(R+r_0-1)}
\sum_{j=0}^{R-1}\frac{j+r_0-1}{j+r_0}\\
&\le\frac{r_0^2\Delta_{0,M}}{(R+r_0-2)^2}
+\frac{A_MR}{(R+r_0-2)(R+r_0-1)}\\
&\le\frac{r_0^2\Delta_{0,M}}{(R+r_0-2)^2}
+\frac{A_M}{R+r_0-2}. \tag*{(69)}
\end{aligned} e R ≤ ( R + r 0 − 2 ) 2 r 0 2 Δ 0 , M + ( R + r 0 − 2 ) ( R + r 0 − 1 ) A M j = 0 ∑ R − 1 j + r 0 j + r 0 − 1 ≤ ( R + r 0 − 2 ) 2 r 0 2 Δ 0 , M + ( R + r 0 − 2 ) ( R + r 0 − 1 ) A M R ≤ ( R + r 0 − 2 ) 2 r 0 2 Δ 0 , M + R + r 0 − 2 A M . (69)
Absorbing the harmless shifts by 2 into universal constants C 1 , C 2 > 0 C_1,C_2>0 C 1 , C 2 > 0 gives
E S G D [ L K ( θ R ) − L K , M ⋆ ] ≤ C 1 Δ 0 , M r 0 2 ( R + r 0 ) 2 + C 2 L M σ M 2 μ M 2 B ( R + r 0 ) . (70) \mathbb{E}_{\mathrm{SGD}}\left[\mathcal{L}_K(\theta_R)-\mathcal{L}_{K,M}^{\star}\right]\le C_1\frac{\Delta_{0,M}r_0^2}{(R+r_0)^2}+C_2\frac{L_M\sigma_M^2}{\mu_M^2B(R+r_0)}. \tag*{(70)} E SGD [ L K ( θ R ) − L K , M ⋆ ] ≤ C 1 ( R + r 0 ) 2 Δ 0 , M r 0 2 + C 2 μ M 2 B ( R + r 0 ) L M σ M 2 . (70)
Since θ ^ = θ R \hat{\theta}=\theta_R θ ^ = θ R , this is the desired finite-time optimization bound.
Finally, N = R B N=RB N = R B . If B B B and r 0 r_0 r 0 are fixed and the quantities
L M , μ M − 1 , σ M 2 , Δ 0 , M L_M,\qquad\mu_M^{-1},\qquad\sigma_M^2,\qquad\Delta_{0,M} L M , μ M − 1 , σ M 2 , Δ 0 , M
remain uniformly bounded over the chosen sequence of score classes, then R ≍ N R\asymp N R ≍ N , and
E S G D [ L K ( θ ^ ) − L K , M ⋆ ] = O ( N − 1 ) , \mathbb{E}_{\mathrm{SGD}}\left[\mathcal{L}_K(\hat{\theta})-\mathcal{L}_{K,M}^{\star}\right]=O(N^{-1}), E SGD [ L K ( θ ^ ) − L K , M ⋆ ] = O ( N − 1 ) ,
with an initialization transient of order N − 2 N^{-2} N − 2 . This simplified rate is therefore a consequence of uniform optimization geometry; it is not assumed in the general finite-time bound.
Remark B.3 (Trajectory localization). The preceding proof uses stochastic-gradient unbiasedness with respect to the natural filtration F r \mathcal{F}_r F r . If one conditions instead on a future event of the form
E = { θ 0 , … , θ R ∈ U K , M } , \mathcal{E}=\{\theta_0,\ldots,\theta_R\in\mathcal{U}_{K,M}\}, E = { θ 0 , … , θ R ∈ U K , M } ,
the gradient noise need not remain conditionally unbiased after that conditioning. Thus a high-probability trajectory-localization formulation requires an additional exit-time or stopped-process argument, or an algorithmically enforced localization mechanism. The factor ( 1 − δ ) − 1 (1-\delta)^{-1} ( 1 − δ ) − 1 alone does not establish this property. For the main theorem we therefore use the trajectory-contained form of Assumption 3.2.
Smoothing Bias for the Original Data Law
The preceding approximation and optimization results control the learned sampler relative to the positive-time law p t 0 p_{t_0} p t 0 . To extend the guarantee to p 0 p_0 p 0 , we need to quantify the error introduced by forward Gaussian smoothing. Such a statement requires full-dimensional density regularity.
Lemma B.4 (Smoothing bias under integral density regularity). Suppose Assumption D.1 holds. In particular, for P Y P_Y P Y -a.e. y y y , the conditional law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) admits a Lebesgue density on R d x \mathbb{R}^{d_x} R d x satisfying the uniform B 1 , ∞ β ∧ 2 B_{1,\infty}^{\beta\wedge2} B 1 , ∞ β ∧ 2 and weighted-gradient bounds stated there.
Let p t ( ⋅ ∣ y ) p_t(\cdot\mid y) p t ( ⋅ ∣ y ) denote the conditional law of
X t = α t X 0 + σ t W , α t = e − t , σ t 2 = 1 − e − 2 t , W ∼ N ( 0 , I d x ) . X_t = \alpha_t X_0 + \sigma_t W,\qquad\alpha_t = e^{-t},\qquad\sigma_t^2 = 1-e^{-2t},\qquad W\sim\mathcal{N}(0,I_{d_x}). X t = α t X 0 + σ t W , α t = e − t , σ t 2 = 1 − e − 2 t , W ∼ N ( 0 , I d x ) . Then, for sufficiently small t > 0 t>0 t > 0 ,
E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t ( ⋅ ∣ Y ) ) ] ≤ C s m t ( β ∧ 2 ) / 2 + C O U d x t . (71) \mathbb{E}_Y\left[\operatorname{TV}\left(p_0(\cdot\mid Y),p_t(\cdot\mid Y)\right)\right]\le C_{\mathrm{sm}}t^{(\beta\wedge2)/2}+C_{\mathrm{OU}}d_xt. \tag*{(71)} E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t ( ⋅ ∣ Y ) ) ] ≤ C sm t ( β ∧ 2 ) /2 + C OU d x t . (71) The exponent saturates at order t t t when β ≥ 2 \beta\ge2 β ≥ 2 . The constants are uniform in y y y and depend only on the integral regularity and dimension parameters in Assumption D.1.
Proof. Fix y y y in the full-P Y P_Y P Y -measure set from Assumption D.1, write p = p 0 ( ⋅ ∣ y ) p=p_0(\cdot\mid y) p = p 0 ( ⋅ ∣ y ) , and set
s : = β ∧ 2 , α t = e − t , τ t : = σ t α t = e 2 t − 1 . s:=\beta\wedge2,\qquad\alpha_t=e^{-t},\qquad\tau_t:=\frac{\sigma_t}{\alpha_t}=\sqrt{e^{2t}-1}. s := β ∧ 2 , α t = e − t , τ t := α t σ t = e 2 t − 1 . If φ τ \varphi_\tau φ τ denotes the centered Gaussian density with covariance τ 2 I d x \tau^2I_{d_x} τ 2 I d x , then the density of X t X_t X t is
p t ( x ) = α t − d x ( p ∗ φ τ t ) ( x / α t ) . p_t(x)=\alpha_t^{-d_x}(p\ast\varphi_{\tau_t})(x/\alpha_t). p t ( x ) = α t − d x ( p ∗ φ τ t ) ( x / α t ) . Let D a f ( x ) : = a − d x f ( x / a ) D_af(x):=a^{-d_x}f(x/a) D a f ( x ) := a − d x f ( x / a ) . Since D a D_a D a is an L 1 L^1 L 1 -isometry,
∥ p t − p ∥ 1 ≤ ∥ D α t ( p ∗ φ τ t ) − D α t p ∥ 1 + ∥ D α t p − p ∥ 1 = ∥ p ∗ φ τ t − p ∥ 1 + ∥ D α t p − p ∥ 1 . (72) \begin{aligned}
\|p_t-p\|_1
&\le\|D_{\alpha_t}(p\ast\varphi_{\tau_t})-D_{\alpha_t}p\|_1+\|D_{\alpha_t}p-p\|_1\\
&=\|p\ast\varphi_{\tau_t}-p\|_1+\|D_{\alpha_t}p-p\|_1. \tag*{(72)}
\end{aligned} ∥ p t − p ∥ 1 ≤ ∥ D α t ( p ∗ φ τ t ) − D α t p ∥ 1 + ∥ D α t p − p ∥ 1 = ∥ p ∗ φ τ t − p ∥ 1 + ∥ D α t p − p ∥ 1 . (72) The standard Gaussian mollification characterization of B 1 , ∞ s B_{1,\infty}^s B 1 , ∞ s , valid for 0 < s ≤ 2 0<s\le2 0 < s ≤ 2 , gives
∥ p ∗ φ τ t − p ∥ 1 ≤ C s τ t s ∥ p ∥ B 1 , ∞ s ≤ C s ′ t s / 2 , \|p\ast\varphi_{\tau_t}-p\|_1\le C_s\tau_t^s\|p\|_{B_{1,\infty}^s}\le C'_st^{s/2}, ∥ p ∗ φ τ t − p ∥ 1 ≤ C s τ t s ∥ p ∥ B 1 , ∞ s ≤ C s ′ t s /2 , for sufficiently small t t t , because τ t 2 = e 2 t − 1 ≍ t \tau_t^2=e^{2t}-1\asymp t τ t 2 = e 2 t − 1 ≍ t .
It remains to control the OU rescaling. For a ∈ [ α t , 1 ] a\in[\alpha_t,1] a ∈ [ α t , 1 ] , weak differentiation and a change of variables give
∥ d d a D a p ∥ 1 ≤ 1 a ( d x ∥ p ∥ 1 + ∫ R d x ∥ u ∥ 2 ∥ ∇ p ( u ) ∥ 2 d u ) . (73) \left\|\frac{d}{da}D_ap\right\|_1\le\frac{1}{a}\left(d_x\|p\|_1+\int_{\mathbb{R}^{d_x}}\|u\|_2\|\nabla p(u)\|_2\,du\right). \tag*{(73)} d a d D a p 1 ≤ a 1 ( d x ∥ p ∥ 1 + ∫ R d x ∥ u ∥ 2 ∥∇ p ( u ) ∥ 2 d u ) . (73) Integrating from a = α t a=\alpha_t a = α t to a = 1 a=1 a = 1 , using − log α t = t -\log\alpha_t=t − log α t = t , and applying the uniform weighted-gradient assumption, we obtain
∥ D α t p − p ∥ 1 ≤ C O U d x t . \|D_{\alpha_t}p-p\|_1\le C_{\mathrm{OU}}d_xt. ∥ D α t p − p ∥ 1 ≤ C OU d x t . Combining the last two estimates with (72) and using that total variation is half the L 1 L^1 L 1 distance proves
TV ( p 0 ( ⋅ ∣ y ) , p t ( ⋅ ∣ y ) ) ≤ C s m t ( β ∧ 2 ) / 2 + C O U d x t . \operatorname{TV}\left(p_0(\cdot\mid y),p_t(\cdot\mid y)\right)\le C_{\mathrm{sm}}t^{(\beta\wedge2)/2}+C_{\mathrm{OU}}d_xt. TV ( p 0 ( ⋅ ∣ y ) , p t ( ⋅ ∣ y ) ) ≤ C sm t ( β ∧ 2 ) /2 + C OU d x t . The constants are uniform in y y y ; averaging over Y Y Y proves (71) .
Remark B.5 (Why the smoothing lemma is separate from the stopped-law theorem). Lemma B.4 is used only for the extension from p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) to p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) . It is not required for the primary stopped-law result. In particular, the exact low-dimensional support allowed by Assumption 3.1 is compatible with the stopped-law theorem but generally incompatible with vanishing ambient total variation between p 0 p_0 p 0 and p t 0 p_{t_0} p t 0 . This is why the original-law extension uses the separate full-dimensional Assumption D.1.
Obtaining the Final Result
We now combine the reverse-process stability, score approximation, and finite-time optimization bounds to prove Theorem 3.3 and its simplified complexity specialization. The key point is that the approximation complexity M M M and the online denoising-sample budget N = R B N = RB N = R B remain separate throughout the argument.
Recall
Δ k : = t k − t k − 1 , H K : = ∑ k = 1 K Δ k = T − t 0 , Δ max : = max 1 ≤ k ≤ K Δ k . \Delta_k := t_k - t_{k-1}, \qquad H_K := \sum_{k=1}^{K} \Delta_k = T - t_0, \qquad\Delta_{\max} := \max_{1 \le k \le K} \Delta_k. Δ k := t k − t k − 1 , H K := k = 1 ∑ K Δ k = T − t 0 , Δ m a x := 1 ≤ k ≤ K max Δ k .
and
P ( J = k ) = Δ k H K . \mathbb{P}(J = k) = \frac{\Delta_k}{H_K}. P ( J = k ) = H K Δ k .
The randomized-time population denoising objective is
L K ( θ ) : = E [ ∥ s θ ( X t J , Y , t J ) − Z J ∥ 2 2 ] , Z J : = ∇ x log q t J ( X t J ∣ X 0 ) . (74) \mathcal{L}_K(\theta) := \mathbb{E}\left[\left\|s_\theta(X_{t_J},Y,t_J) - Z_J\right\|_2^2\right], \qquad Z_J := \nabla_x \log q_{t_J}(X_{t_J} \mid X_0). \tag*{(74)} L K ( θ ) := E [ ∥ s θ ( X t J , Y , t J ) − Z J ∥ 2 2 ] , Z J := ∇ x log q t J ( X t J ∣ X 0 ) . (74)
and, for a score class of complexity M M M ,
L K , M ⋆ : = inf θ ∈ Θ M L K ( θ ) . \mathcal{L}_{K,M}^{\star} := \inf_{\theta\in\Theta_M} \mathcal{L}_K(\theta). L K , M ⋆ := θ ∈ Θ M inf L K ( θ ) .
The learned score
s ^ = s θ ^ \widehat{s} = s_{\widehat{\theta}} s = s θ
is the output of R R R online SGD iterations with mini-batch size B B B , so that
We also recall the randomized-time best-in-class approximation error
A K ( M ) : = inf θ ∈ Θ M E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (75) \mathcal{A}_K(M) := \inf_{\theta\in\Theta_M} \mathbb{E}\left[\left\|s_\theta(X_{t_J},Y,t_J) - s^{\star}(X_{t_J},t_J,Y)\right\|_2^2\right]. \tag*{(75)} A K ( M ) := θ ∈ Θ M inf E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (75)
and the finite-time population optimization error
E o p t ( N , M ) : = E S G D [ L K ( θ ^ ) − L K , M ⋆ ] . (76) \mathcal{E}_{\mathrm{opt}}(N,M) := \mathbb{E}_{\mathrm{SGD}}\left[\mathcal{L}_K(\widehat{\theta}) - \mathcal{L}_{K,M}^{\star}\right]. \tag*{(76)} E opt ( N , M ) := E SGD [ L K ( θ ) − L K , M ⋆ ] . (76)
Under the trajectory-contained localized PL formulation used in Proposition 3.4 , the expectation in (76) is taken over the ordinary online SGD randomness while the analyzed trajectory remains in the stated PL region.
Proof of the General Training-to-Sampling Bound
Proof of Theorem 3.3 . Step 1: Introduce the intermediate reverse law.
For each fixed conditioning value y y y , let p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) denote the forward-smoothed target law at time t 0 t_0 t 0 . Equivalently, this is the law obtained by running the exact reverse SDE from p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) down to time t 0 t_0 t 0 using
s ⋆ ( x , t , y ) = ∇ x log p t ( x ∣ y ) . s^{\star}(x,t,y) = \nabla_x \log p_t(x \mid y). s ⋆ ( x , t , y ) = ∇ x log p t ( x ∣ y ) .
Let
p ~ t 0 ( ⋅ ∣ y ) \widetilde{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y )
denote the law of the admissibly discretized reverse process initialized from the exact terminal law p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) and using the learned score s ^ \widehat{s} s . Finally, let
p ^ t 0 ( ⋅ ∣ y ) \widehat{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y )
denote the same learned-score discretized reverse process initialized instead from the Gaussian reference law N ( 0 , I d x ) \mathcal{N}(0, I_{d_x}) N ( 0 , I d x ) .
The triangle inequality gives
TV ( p t 0 ( ⋅ ∣ y ) , p ~ t 0 ( ⋅ ∣ y ) ) ≤ TV ( p t 0 ( ⋅ ∣ y ) , p ~ t 0 ( ⋅ ∣ y ) ) + TV ( p ~ t 0 ( ⋅ ∣ y ) , p ^ t 0 ( ⋅ ∣ y ) ) . (77) \operatorname{TV}(p_{t_0}(\cdot\mid y), \widetilde{p}_{t_0}(\cdot\mid y))
\le\operatorname{TV}(p_{t_0}(\cdot\mid y), \widetilde{p}_{t_0}(\cdot\mid y)) + \operatorname{TV}(\widetilde{p}_{t_0}(\cdot\mid y), \widehat{p}_{t_0}(\cdot\mid y)). \tag*{(77)} TV ( p t 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y )) ≤ TV ( p t 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y )) + TV ( p t 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y )) . (77)
The two terms in (77) represent, respectively, the learned-score/discretization error and the terminal-initialization error.
Step 2: Terminal-initialization error.
For a fixed realization of s ^ \widehat{s} s , the laws p ~ t 0 ( ⋅ ∣ y ) \widetilde{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) and p ^ t 0 ( ⋅ ∣ y ) \widehat{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) are obtained by applying the same discretized reverse Markov kernel to two different initial laws, p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) and N ( 0 , I d x ) \mathcal{N}(0, I_{d_x}) N ( 0 , I d x ) . Total variation contracts under a Markov kernel. Therefore
TV ( p ~ t 0 ( ⋅ ∣ y ) , p ^ t 0 ( ⋅ ∣ y ) ) ≤ TV ( p T ( ⋅ ∣ y ) , N ( 0 , I d x ) ) . (78) \operatorname{TV}(\widetilde{p}_{t_0}(\cdot\mid y), \widehat{p}_{t_0}(\cdot\mid y))
\le\operatorname{TV}(p_T(\cdot\mid y), \mathcal{N}(0, I_{d_x})). \tag*{(78)} TV ( p t 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y )) ≤ TV ( p T ( ⋅ ∣ y ) , N ( 0 , I d x )) . (78)
Let γ = N ( 0 , I d x ) \gamma= \mathcal{N}(0, I_{d_x}) γ = N ( 0 , I d x ) . Conditional on X 0 = x X_0 = x X 0 = x , the terminal law is
N ( e − T x , ( 1 − e − 2 T ) I d x ) . \mathcal{N}\left(e^{-T}x, (1-e^{-2T})I_{d_x}\right). N ( e − T x , ( 1 − e − 2 T ) I d x ) .
Convexity of relative entropy in its first argument and the Gaussian relative-entropy formula therefore give
KL ( p T ( ⋅ ∣ y ) ∥ γ ) ≤ 1 2 e − 2 T E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] + d x 2 [ − e − 2 T − log ( 1 − e − 2 T ) ] ≤ C ( d x + m 2 ) e − 2 T , (79) \operatorname{KL}(p_T(\cdot\mid y) \mathbin{\|} \gamma)
\le\frac{1}{2}e^{-2T}\mathbb{E}\left[\lVert X_0\rVert_2^2 \mid Y=y\right]
+ \frac{d_x}{2}\left[-e^{-2T}-\log(1-e^{-2T})\right]
\le C(d_x+m_2)e^{-2T}, \tag*{(79)} KL ( p T ( ⋅ ∣ y ) ∥ γ ) ≤ 2 1 e − 2 T E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] + 2 d x [ − e − 2 T − log ( 1 − e − 2 T ) ] ≤ C ( d x + m 2 ) e − 2 T , (79)
where the last inequality uses T ≥ 1 T \ge1 T ≥ 1 . Pinsker’s inequality and averaging over Y Y Y give
E Y [ TV ( p ~ t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T . (80) \mathbb{E}_Y\left[\operatorname{TV}(\widetilde{p}_{t_0}(\cdot\mid Y), \widehat{p}_{t_0}(\cdot\mid Y))\right]
\le C_{\mathrm{term}}e^{-T}. \tag*{(80)} E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y )) ] ≤ C term e − T . (80)
Step 3: Reverse-process stability for the learned score.
Apply Lemma E.1 with s ˉ = s ^ \bar{s}=\widehat{s} s ˉ = s . Since the corresponding discretized law initialized from p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) is precisely p ~ t 0 ( ⋅ ∣ y ) \widetilde{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) , the lemma gives, for every fixed realization of s ^ \widehat{s} s ,
E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ~ t 0 ( ⋅ ∣ Y ) ) ] ≤ C s t a b ( ∑ k = 1 K Δ k E [ ∥ s ^ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] ) 1 / 2 + C d i s c r d x + m 2 K . (81) \mathbb{E}_Y\left[\operatorname{TV}(p_{t_0}(\cdot\mid Y),\widetilde{p}_{t_0}(\cdot\mid Y))\right]
\le C_{\mathrm{stab}}\left(\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\lVert\widehat{s}(X_{t_k},Y,t_k)-s^\star(X_{t_k},t_k,Y)\right\rVert_2^2\right]\right)^{1/2}
+ C_{\mathrm{discr}}\sqrt{\frac{d_x+m_2}{K}}. \tag*{(81)} E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y )) ] ≤ C stab ( k = 1 ∑ K Δ k E [ ∥ s ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] ) 1/2 + C discr K d x + m 2 . (81)
Here
m 2 = ess sup y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞ m_2=\mathop{\operatorname{ess\,sup}}_{y\sim P_Y}\mathbb{E}\left[\lVert X_0\rVert_2^2\mid Y=y\right]<\infty m 2 = ess sup y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞
by Assumption 3.1.
The score error in (81) is evaluated under the forward noised marginals
Y ∼ P Y , X t k ∼ p t k ( ⋅ ∣ Y ) , Y \sim P_Y,\qquad X_{t_k} \sim p_{t_k}(\cdot\mid Y), Y ∼ P Y , X t k ∼ p t k ( ⋅ ∣ Y ) ,
which is exactly the distribution entering the randomized-time population denoising objective. Define the randomized-time score error of the learned network by
A ^ K : = E [ ∥ s ^ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (82) \widehat{\mathcal{A}}_K := \mathbb{E}\left[\left\|\widehat{s}(X_{t_J},Y,t_J)-s^\star(X_{t_J},t_J,Y)\right\|_2^2\right]. \tag*{(82)} A K := E [ ∥ s ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] . (82)
Since
P ( J = k ) = Δ k H K , \mathbb{P}(J=k)=\frac{\Delta_k}{H_K}, P ( J = k ) = H K Δ k ,
we have the exact identity
H K A ^ K = ∑ k = 1 K Δ k E [ ∥ s ^ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] . (83) H_K\widehat{\mathcal{A}}_K
=
\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\|\widehat{s}(X_{t_k},Y,t_k)-s^\star(X_{t_k},t_k,Y)\right\|_2^2\right]. \tag*{(83)} H K A K = k = 1 ∑ K Δ k E [ ∥ s ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] . (83)
Hence (81) becomes
E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C s t a b H K A ^ K + C d i s c d x + m 2 K . (84) \mathbb{E}_Y\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{stab}}\sqrt{H_K\widehat{\mathcal{A}}_K}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}}. \tag*{(84)} E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C stab H K A K + C disc K d x + m 2 . (84)
Step 4: Decompose learned-score error into approximation and optimization. The denoising identity gives
s ⋆ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] . s^\star(X_{t_J},t_J,Y)=\mathbb{E}[Z_J\mid X_{t_J},Y,t_J]. s ⋆ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] .
Therefore, for every θ ∈ Θ M \theta\in\Theta_M θ ∈ Θ M , the orthogonal projection identity for conditional expectations yields
L K ( θ ) = C K + E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] , (85) \mathcal{L}_K(\theta)=C_K+\mathbb{E}\left[\left\|s_\theta(X_{t_J},Y,t_J)-s^\star(X_{t_J},t_J,Y)\right\|_2^2\right], \tag*{(85)} L K ( θ ) = C K + E [ ∥ s θ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] , (85)
where
C K : = E [ ∥ Z J − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ] C_K:=\mathbb{E}\left[\left\|Z_J-s^\star(X_{t_J},t_J,Y)\right\|_2^2\right] C K := E [ ∥ Z J − s ⋆ ( X t J , t J , Y ) ∥ 2 2 ]
does not depend on θ \theta θ . Taking the infimum over θ ∈ Θ M \theta\in\Theta_M θ ∈ Θ M in (85) gives
L K , M ⋆ = C K + A K ( M ) . (86) \mathcal{L}^\star_{K,M}=C_K+\mathcal{A}_K(M). \tag*{(86)} L K , M ⋆ = C K + A K ( M ) . (86)
No minimizer attaining either infimum is required. Applying (85) at θ ^ \widehat{\theta} θ and then using (86) ,
A ^ K = L K ( θ ^ ) − C K = [ L K ( θ ^ ) − L K , M ⋆ ] + A K ( M ) . (87) \begin{aligned}
\widehat{\mathcal{A}}_K=\mathcal{L}_K(\widehat{\theta})-C_K \\
&=\left[\mathcal{L}_K(\widehat{\theta})-\mathcal{L}^\star_{K,M}\right]+\mathcal{A}_K(M). \tag*{(87)}
\end{aligned} A K = L K ( θ ) − C K = [ L K ( θ ) − L K , M ⋆ ] + A K ( M ) . (87)
Taking expectation over the online SGD randomness yields
E S G D [ A ^ K ] = A K ( M ) + E o p t ( N , M ) . (88) \mathbb{E}_{\mathrm{SGD}}\left[\widehat{\mathcal{A}}_K\right]=\mathcal{A}_K(M)+\mathcal{E}_{\mathrm{opt}}(N,M). \tag*{(88)} E SGD [ A K ] = A K ( M ) + E opt ( N , M ) . (88)
This identity is the point at which approximation and finite-time optimization enter the sampling analysis, and the two quantities remain separate.
Step 5: Average over the SGD randomness. Taking expectation over SGD in (84) and applying Jensen’s inequality to the concave square-root function gives
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C s t a b H K E S G D [ A ^ K ] + C d i s c d x + m 2 K = C s t a b H K [ A K ( M ) + E o p t ( N , M ) ] + C d i s c d x + m 2 K . (89) \begin{aligned}
\mathbb{E}_{\mathrm{SGD}}\mathbb{E}_{Y}\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{stab}}\sqrt{H_K\mathbb{E}_{\mathrm{SGD}}\left[\widehat{A}_K\right]}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}} \\
&= C_{\mathrm{stab}}\sqrt{H_K\left[A_K(M)+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}}. \tag*{(89)}
\end{aligned} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C stab H K E SGD [ A K ] + C disc K d x + m 2 = C stab H K [ A K ( M ) + E opt ( N , M ) ] + C disc K d x + m 2 . (89)
Combining (77) , (80) , and (89) therefore gives
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T + C d i s c d x + m 2 K + C s t a b H K [ A K ( M ) + E o p t ( N , M ) ] . (90) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_{Y}\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{term}}e^{-T}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}}
+C_{\mathrm{stab}}\sqrt{H_K\left[A_K(M)+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}. \tag*{(90)} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T + C disc K d x + m 2 + C stab H K [ A K ( M ) + E opt ( N , M ) ] . (90)
This proves the general decomposition asserted in Theorem 3.3 . □
Explicit Approximation and Optimization Instantiation
We next substitute the approximation and finite-time optimization bounds into (90) . By Lemma B.1 ,
A K ( M ) ≤ C ~ a p p ( M − η a p p + Δ max ) . (91) A_K(M)\le\widetilde{C}_{\mathrm{app}}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right). \tag*{(91)} A K ( M ) ≤ C app ( M − η app + Δ m a x ) . (91)
where
η a p p = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ . \eta_{\mathrm{app}}=\frac{2\alpha_x}{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y}. η app = 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x .
By Proposition 3.4 , if
η r = 2 μ M ( r + r 0 ) , r 0 ≥ max { 4 , 2 L M μ M } , \eta_r=\frac{2}{\mu_M(r+r_0)},\qquad r_0\ge\max\left\{4,\frac{2L_M}{\mu_M}\right\}, η r = μ M ( r + r 0 ) 2 , r 0 ≥ max { 4 , μ M 2 L M } ,
then
E o p t ( N , M ) ≤ C 1 Δ 0 , M r 0 2 ( R + r 0 ) 2 + C 2 L M σ M 2 μ M 2 B ( R + r 0 ) , (92) \mathcal{E}_{\mathrm{opt}}(N,M)\le C_1\frac{\Delta_{0,M}r_0^2}{(R+r_0)^2}+C_2\frac{L_M\sigma_M^2}{\mu_M^2B(R+r_0)}, \tag*{(92)} E opt ( N , M ) ≤ C 1 ( R + r 0 ) 2 Δ 0 , M r 0 2 + C 2 μ M 2 B ( R + r 0 ) L M σ M 2 , (92)
where
N = R B , Δ 0 , M : = L K ( θ 0 ) − L K , M ⋆ . N=RB,\qquad\Delta_{0,M}:=\mathcal{L}_K(\theta_0)-\mathcal{L}_{K,M}^{\star}. N = R B , Δ 0 , M := L K ( θ 0 ) − L K , M ⋆ .
Substituting (91) and (92) into (90) yields
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T + C d i s c d x + m 2 K + C s t a b { H K [ C ~ a p p ( M − η a p p + Δ max ) + C 1 Δ 0 , M r 0 2 ( R + r 0 ) 2 + C 2 L M σ M 2 μ M 2 B ( R + r 0 ) ] } 1 / 2 . (93) \begin{aligned}
\mathbb{E}_{\mathrm{SGD}}\mathbb{E}_{Y}\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
&\le C_{\mathrm{term}}e^{-T}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}}\\
&\quad+C_{\mathrm{stab}}\left\{H_K\left[\widetilde{C}_{\mathrm{app}}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right)\right.\right.\\
&\qquad\left.\left.{}+C_1\frac{\Delta_{0,M}r_0^2}{(R+r_0)^2}+C_2\frac{L_M\sigma_M^2}{\mu_M^2B(R+r_0)}\right]\right\}^{1/2}. \tag*{(93)}
\end{aligned} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T + C disc K d x + m 2 + C stab { H K [ C app ( M − η app + Δ m a x ) + C 1 ( R + r 0 ) 2 Δ 0 , M r 0 2 + C 2 μ M 2 B ( R + r 0 ) L M σ M 2 ] } 1/2 . (93)
Equation (93) is the explicit finite-time training-to-sampling guarantee. It makes no assumption that the optimization constants are independent of the score-class complexity M M M . In particular, increasing M M M decreases the approximation term but may change L M L_M L M , μ M \mu_M μ M , σ M 2 \sigma_M^2 σ M 2 , or Δ 0 , M \Delta_{0,M} Δ 0 , M .
Verification of the Simplified ϵ \epsilon ϵ -Rate
We now verify Corollary 3.6. Fix t 0 > 0 t_0 > 0 t 0 > 0 independently of ϵ \epsilon ϵ , and suppose the optimization geometry is uniformly controlled along the chosen sequence of score classes, horizons, and grids. Thus, for the constants of each corresponding randomized-time objective,
L M ≤ L ‾ , μ M ≥ μ > 0 , σ M 2 ≤ σ ‾ 2 , Δ 0 , M ≤ Δ ‾ 0 . L_M \le\overline{L}, \qquad\mu_M \ge\mu> 0, \qquad\sigma_M^2 \le\overline{\sigma}^2, \qquad\Delta_{0,M} \le\overline{\Delta}_0. L M ≤ L , μ M ≥ μ > 0 , σ M 2 ≤ σ 2 , Δ 0 , M ≤ Δ 0 .
Take B B B fixed independently of ϵ \epsilon ϵ and a fixed
r 0 ≥ max { 4 , 2 L ‾ μ } . r_0 \ge\max\left\{4,\frac{2\overline{L}}{\mu}\right\}. r 0 ≥ max { 4 , μ 2 L } .
Since N = R B N = RB N = R B , we then have
R = Θ ( N ) , R = \Theta(N), R = Θ ( N ) ,
and (92) gives
E o p t ( N , M ) = O ( N − 1 ) , (94) \mathcal{E}_{\mathrm{opt}}(N,M) = \mathcal{O}(N^{-1}), \tag*{(94)} E opt ( N , M ) = O ( N − 1 ) , (94)
with an initialization transient of order N − 2 N^{-2} N − 2 .
Choose
T = C T log ( 1 / ϵ ) (95) T = C_T \log(1/\epsilon) \tag*{(95)} T = C T log ( 1/ ϵ ) (95)
with C T C_T C T sufficiently large. Then
e − T = O ( ϵ ) , e^{-T} = \mathcal{O}(\epsilon), e − T = O ( ϵ ) ,
and
H K = T − t 0 ≤ T = O ( log ( 1 / ϵ ) ) . H_K = T - t_0 \le T = \mathcal{O}(\log(1/\epsilon)). H K = T − t 0 ≤ T = O ( log ( 1/ ϵ )) .
For the approximation class, choose
M = Θ ~ ( ϵ − 2 / η a p p ) . (96) M = \widetilde{\Theta}\left(\epsilon^{-2/\eta_{\mathrm{app}}}\right). \tag*{(96)} M = Θ ( ϵ − 2/ η app ) . (96)
Then
M − η a p p = O ~ ( ϵ 2 ) . M^{-\eta_{\mathrm{app}}} = \widetilde{\mathcal{O}}(\epsilon^2). M − η app = O ( ϵ 2 ) .
Since
2 η a p p = 2 + d x ′ α x + d y ′ α y , \frac{2}{\eta_{\mathrm{app}}} = 2 + \frac{d'_x}{\alpha_x} + \frac{d'_y}{\alpha_y}, η app 2 = 2 + α x d x ′ + α y d y ′ ,
the same requirement can be written as
M = Θ ~ ( ϵ − ( 2 + d x ′ / α x + d y ′ / α y ) ) . (97) M = \widetilde{\Theta}\left(\epsilon^{-\left(2+d'_x/\alpha_x+d'_y/\alpha_y\right)}\right). \tag*{(97)} M = Θ ( ϵ − ( 2 + d x ′ / α x + d y ′ / α y ) ) . (97)
For online optimization, choose
N = Θ ~ ( ϵ − 2 ) . (98) N = \widetilde{\Theta}(\epsilon^{-2}). \tag*{(98)} N = Θ ( ϵ − 2 ) . (98)
By (94) ,
E o p t ( N , M ) = O ~ ( ϵ 2 ) . \mathcal{E}_{\mathrm{opt}}(N,M) = \widetilde{\mathcal{O}}(\epsilon^2). E opt ( N , M ) = O ( ϵ 2 ) .
Finally, choose an admissible reverse-time grid satisfying
Δ max ≤ O ~ ( M − η a p p ) = O ~ ( ϵ 2 ) (99) \Delta_{\max} \le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right) = \widetilde{O}(\epsilon^2) \tag*{(99)} Δ m a x ≤ O ( M − η app ) = O ( ϵ 2 ) (99)
and
K = Θ ~ ( ( d x + m 2 ) ϵ − 2 ) . (100) K = \widetilde{\Theta}\left((d_x + m_2)\epsilon^{-2}\right). \tag*{(100)} K = Θ ( ( d x + m 2 ) ϵ − 2 ) . (100)
For the admissible grids of Lemma E.1 , the maximum step size satisfies, up to logarithmic factors,
Δ max ≲ H K K , \Delta_{\max} \lesssim\frac{H_K}{K}, Δ m a x ≲ K H K ,
so the choice (100) is compatible with (99) after absorbing the H K = O ( log ( 1 / ϵ ) ) H_K = O(\log(1/\epsilon)) H K = O ( log ( 1/ ϵ )) factor into the O ~ \widetilde{O} O -notation. With these choices,
C d i s c d x + m 2 K = O ~ ( ϵ ) , C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}} = \widetilde{O}(\epsilon), C disc K d x + m 2 = O ( ϵ ) ,
and
H K [ A K ( M ) + E o p t ( N , M ) ] ≤ O ~ ( log ( 1 / ϵ ) ( ϵ 2 + ϵ 2 ) ) = O ~ ( ϵ ) . (101) \sqrt{H_K\left[\mathcal{A}_K(M)+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}
\le\widetilde{O}\left(\sqrt{\log(1/\epsilon)\left(\epsilon^2+\epsilon^2\right)}\right)
= \widetilde{O}(\epsilon). \tag*{(101)} H K [ A K ( M ) + E opt ( N , M ) ] ≤ O ( log ( 1/ ϵ ) ( ϵ 2 + ϵ 2 ) ) = O ( ϵ ) . (101)
Substituting into (90) gives
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ O ~ ( ϵ ) . (102) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]\le\widetilde{O}(\epsilon). \tag*{(102)} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ O ( ϵ ) . (102)
This is the claimed O ~ ( ϵ ) \widetilde{O}(\epsilon) O ( ϵ ) expected total-variation guarantee. The complexity requirements should therefore be read as two distinct statements:
M = Θ ~ ( ϵ − 2 / η a p p ) and N = Θ ~ ( ϵ − 2 ) . (103) M=\widetilde{\Theta}\left(\epsilon^{-2/\eta_{\mathrm{app}}}\right)
\qquad\text{and}\qquad
N=\widetilde{\Theta}\left(\epsilon^{-2}\right). \tag*{(103)} M = Θ ( ϵ − 2/ η app ) and N = Θ ( ϵ − 2 ) . (103)
under uniform optimization geometry. The first is an approximation-capacity requirement; the second is the number of fresh denoising samples consumed by online SGD. They should not be combined into a single online sample-complexity exponent.
If the optimization constants L M L_M L M , μ M \mu_M μ M , σ M 2 \sigma_M^2 σ M 2 , Δ 0 , M \Delta_{0,M} Δ 0 , M are not uniformly controlled as M M M grows, then the appropriate result is the explicit bound (93) , rather than the simplified N = O ~ ( ϵ − 2 ) N=\widetilde{O}(\epsilon^{-2}) N = O ( ϵ − 2 ) statement.
This completes the proof of the stopped-law results. The extension from p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) to the original conditional law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) requires the additional smoothing-bias analysis and is treated separately in Appendix § 8 .
Extension: Total Variation Guarantee to the Original Data Law
The primary result of the paper controls the implementable reverse sampler relative to the positive-time conditional law p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) . In this section, we show how this stopped-law guarantee can be extended to the original conditional data law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) .
An additional regularity assumption is necessary. If the clean conditional law is exactly supported on a strict lower-dimensional manifold in R d x \mathbb{R}^{d_x} R d x , then p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) is singular with respect to Lebesgue measure, whereas p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) is Gaussian-smoothed and absolutely continuous for every t 0 > 0 t_0>0 t 0 > 0 . In that setting, ambient total variation between the two laws does not vanish as t 0 ↓ 0 t_0\downarrow0 t 0 ↓ 0 . Accordingly, the extension below assumes that the response distribution is full-dimensional.
Assumption D.1 (Full-dimensional regularity for the TV-to-p 0 p_0 p 0 extension). Let Y ∼ P Y Y \sim P_Y Y ∼ P Y take values in R d y \mathbb{R}^{d_y} R d y , and let X 0 ∣ Y = y ∼ p 0 ( ⋅ ∣ y ) X_0 \mid Y = y \sim p_0(\cdot\mid y) X 0 ∣ Y = y ∼ p 0 ( ⋅ ∣ y ) take values in R d x \mathbb{R}^{d_x} R d x . The following conditions hold.
Full-dimensional Hölder conditional density. For P Y P_Y P Y -a.e. y y y , the conditional law P X 0 ∣ Y = y P_{X_0\mid Y=y} P X 0 ∣ Y = y admits a Lebesgue density p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) on R d x \mathbb{R}^{d_x} R d x . There exists B d e n s < ∞ B_{\mathrm{dens}} < \infty B dens < ∞ such that
ess sup y ∼ P Y ∥ p 0 ( ⋅ ∣ y ) ∥ ∞ ≤ B d e n s . \operatorname*{ess\,sup}_{y\sim P_Y}\|p_0(\cdot\mid y)\|_\infty\le B_{\mathrm{dens}}. y ∼ P Y ess sup ∥ p 0 ( ⋅ ∣ y ) ∥ ∞ ≤ B dens . Moreover, for some β > 0 \beta> 0 β > 0 , p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) is uniformly β \beta β -Hölder smooth in the response coordinate x x x . More precisely, if
m = ⌈ β ⌉ − 1 , β = m + α , α ∈ ( 0 , 1 ] , m = \lceil\beta\rceil- 1,\qquad\beta= m + \alpha,\qquad\alpha\in(0,1], m = ⌈ β ⌉ − 1 , β = m + α , α ∈ ( 0 , 1 ] , then derivatives up to order m m m are uniformly bounded and the derivatives of order m m m are uniformly α \alpha α -Hölder continuous, with constants independent of y y y .
For the total-variation smoothing step, assume in addition the uniform integral regularity
ess sup y ∼ P Y { ∥ p 0 ( ⋅ ∣ y ) ∥ B 1 , ∞ β ∧ 2 + ∫ R d x ( 1 + ∥ x ∥ 2 ) ∥ ∇ x p 0 ( x ∣ y ) ∥ 2 d x } < ∞ . \operatorname*{ess\,sup}_{y\sim P_Y}\left\{\|p_0(\cdot\mid y)\|_{B^{\beta\wedge2}_{1,\infty}}+\int_{\mathbb{R}^{d_x}}(1+\|x\|_2)\|\nabla_xp_0(x\mid y)\|_2\,dx\right\}<\infty. y ∼ P Y ess sup { ∥ p 0 ( ⋅ ∣ y ) ∥ B 1 , ∞ β ∧ 2 + ∫ R d x ( 1 + ∥ x ∥ 2 ) ∥ ∇ x p 0 ( x ∣ y ) ∥ 2 d x } < ∞. where the derivative may be interpreted weakly. For s > 0 s > 0 s > 0 , we use the equivalent modulus-of-smoothness norm
∥ f ∥ B 1 , ∞ s : = ∥ f ∥ 1 + sup 0 < ∥ h ∥ 2 ≤ 1 ∥ h ∥ 2 − s ∥ Δ h r f ∥ 1 , r ∈ N , r > s , \|f\|_{B^s_{1,\infty}} := \|f\|_1+\sup_{0<\|h\|_2\le1}\|h\|_2^{-s}\|\Delta_h^r f\|_1,\qquad r\in\mathbb{N},\quad r>s, ∥ f ∥ B 1 , ∞ s := ∥ f ∥ 1 + 0 < ∥ h ∥ 2 ≤ 1 sup ∥ h ∥ 2 − s ∥ Δ h r f ∥ 1 , r ∈ N , r > s , with Δ h r \Delta_h^r Δ h r the r r r -fold finite difference. The Besov condition supplies the Gaussian mollification rate, while the weighted gradient term controls the deterministic OU rescaling.
Anisotropic approximation smoothness. The conditioning law P Y P_Y P Y is supported on a d y ′ d_y' d y ′ -dimensional embedded submanifold
M Y ⊂ R d y , \mathcal{M}_Y\subset\mathbb{R}^{d_y}, M Y ⊂ R d y , and admits a density with respect to the intrinsic volume measure on M Y \mathcal{M}_Y M Y .
In local intrinsic coordinates for Y Y Y , the conditional density p 0 ( x ∣ y ) p_0(x\mid y) p 0 ( x ∣ y ) satisfies the anisotropic regularity used by the conditional score-approximation argument: the response coordinate has smoothness α x > 0 \alpha_x>0 α x > 0 , while the intrinsic conditioning coordinate has smoothness α y > 0 \alpha_y>0 α y > 0 . The corresponding localized Hölder constants, chart constants, and density regularity quantities are uniformly controlled on the logarithmic localization regions used in the proof. The score class contains the later-time blockwise approximants used in the conditional approximation theorem, and the required density nondegeneracy and inverse-density quantities are uniformly controlled on those regions.
Sub-exponential tails. There exist constants λ Y , λ X > 0 \lambda_Y,\lambda_X>0 λ Y , λ X > 0 such that
E exp ( λ Y ∥ Y ∥ 2 ) < ∞ , \mathbb{E}\exp(\lambda_Y\|Y\|_2)<\infty, E exp ( λ Y ∥ Y ∥ 2 ) < ∞ , and
ess sup y ∼ P Y E [ exp ( λ X ∥ X 0 ∥ 2 ) ∣ Y = y ] < ∞ . \operatorname*{ess\,sup}_{y\sim P_Y}\mathbb{E}\left[\exp(\lambda_X\|X_0\|_2)\mid Y=y\right]<\infty. y ∼ P Y ess sup E [ exp ( λ X ∥ X 0 ∥ 2 ) ∣ Y = y ] < ∞. Define the later-time approximation exponents
ρ 0 : = 2 2 α x + d x + ( α x / α y ) d y ′ , ζ 0 : = 2 α y 2 α y + d y ′ , γ 0 : = α y d x 2 α y + d y ′ . (104) \rho_0:=\frac{2}{2\alpha_x+d_x+(\alpha_x/\alpha_y)d_y'},\qquad\zeta_0:=\frac{2\alpha_y}{2\alpha_y+d_y'},\qquad\gamma_0:=\frac{\alpha_y d_x}{2\alpha_y+d_y'}. \tag*{(104)} ρ 0 := 2 α x + d x + ( α x / α y ) d y ′ 2 , ζ 0 := 2 α y + d y ′ 2 α y , γ 0 := 2 α y + d y ′ α y d x . (104)
For an approximation class of complexity M M M , the later-time regime used below requires
M − ρ 0 ≤ t 0 . (105) M^{-\rho_0} \le t_0. \tag*{(105)} M − ρ 0 ≤ t 0 . (105)
We additionally assume that the class F Θ , M \mathcal{F}_{\Theta,M} F Θ , M contains the later-time blockwise conditional score approximants furnished by the conditional approximation theorem, so that after localization and grid transfer their error is bounded by O ~ ( t 0 − γ 0 M − ζ 0 + Δ max ) \widetilde{O}(t_0^{-\gamma_0}M^{-\zeta_0}+\Delta_{\max}) O ( t 0 − γ 0 M − ζ 0 + Δ m a x ) .
Remark D.2 (Relation to the stopped-law assumption). Assumption D.1 is used only for convergence to the original law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) . It is deliberately different from Assumption 3.1. The latter permits exact lower-dimensional response support because the primary target is the positive-time smoothed law p t 0 p_{t_0} p t 0 . The present assumption instead requires a full-dimensional response density so that the smoothing bias
TV ( p 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) ) \operatorname{TV}\left(p_0(\cdot\mid y),p_{t_0}(\cdot\mid y)\right) TV ( p 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) )
can converge to zero as t 0 ↓ 0 t_0\downarrow0 t 0 ↓ 0 . Its integral Besov and weighted-gradient conditions are stronger than pointwise Hölder smoothness alone and are used only to obtain the stated uniform total-variation smoothing rate.
For this extension, define the best-in-class randomized-time score error
A K , 0 ( M ) : = inf θ ∈ Θ M E [ ∥ s θ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] . (106) A_{K,0}(M):=\inf_{\theta\in\Theta_M}\mathbb{E}\left[\left\|s_\theta(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^2\right]. \tag*{(106)} A K , 0 ( M ) := θ ∈ Θ M inf E [ ∥ s θ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] . (106)
Under Assumption D.1 and the second-regime condition (105), the later-time conditional score-approximation input adapted from the blockwise construction of Tang et al. [33 ] , together with the class-containment clause in the assumption, gives
A K , 0 ( M ) ≤ C ~ a p p , 0 ( t 0 − γ 0 M − ζ 0 + Δ max ) . (107) A_{K,0}(M)\le\widetilde{C}_{\mathrm{app},0}\left(t_0^{-\gamma_0}M^{-\zeta_0}+\Delta_{\max}\right). \tag*{(107)} A K , 0 ( M ) ≤ C app , 0 ( t 0 − γ 0 M − ζ 0 + Δ m a x ) . (107)
The Δ max \Delta_{\max} Δ m a x term arises from transferring the time-integrated approximation guarantee to the randomized grid-time objective. Consequently, if
Δ max ≤ O ~ ( t 0 − γ 0 M − ζ 0 ) , (108) \Delta_{\max}\le\widetilde{O}\left(t_0^{-\gamma_0}M^{-\zeta_0}\right), \tag*{(108)} Δ m a x ≤ O ( t 0 − γ 0 M − ζ 0 ) , (108)
then
A K , 0 ( M ) ≤ O ~ ( t 0 − γ 0 M − ζ 0 ) . (109) A_{K,0}(M)\le\widetilde{O}\left(t_0^{-\gamma_0}M^{-\zeta_0}\right). \tag*{(109)} A K , 0 ( M ) ≤ O ( t 0 − γ 0 M − ζ 0 ) . (109)
The response dimension appearing in this rate is the ambient dimension d x d_x d x , rather than the intrinsic dimension d x ′ d'_x d x ′ , because the present extension assumes a full-dimensional response density.
General Total-Variation Bound to the Original Law
Corollary D.3 (Total-variation guarantee to the original conditional law). Suppose Assumptions D.1 and 3.2 hold. Let p ^ t 0 ( ⋅ ∣ y ) \widehat{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) denote the law generated by the admissibly discretized reverse process initialized from N ( 0 , I d x ) \mathcal{N}(0,I_{d_x}) N ( 0 , I d x ) and using the score s ^ = s θ ^ \widehat{s}=s_{\widehat{\theta}} s = s θ produced by online SGD.
Assume 0 < t 0 < 1 ≤ T 0<t_0<1\le T 0 < t 0 < 1 ≤ T .
Let M M M denote the score-class approximation complexity, and let
denote the total number of fresh online denoising samples used by SGD. Define
m 2 : = ess sup y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] . m_2 := \operatorname*{ess\,sup}_{y\sim P_Y} \mathbb{E}\left[\lVert X_0\rVert_2^2 \mid Y=y\right]. m 2 := y ∼ P Y ess sup E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] .
which is finite by the sub-exponential tail assumption.
Suppose
M − ρ 0 ≤ t 0 M^{-\rho_0} \le t_0 M − ρ 0 ≤ t 0
and that the admissible grid satisfies
Δ max ≤ O ~ ( t 0 − γ 0 M − ζ 0 ) . \Delta_{\max} \le\widetilde{O}\left(t_0^{-\gamma_0}M^{-\zeta_0}\right). Δ m a x ≤ O ( t 0 − γ 0 M − ζ 0 ) .
Then
E S G D E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T + C d i s c d x + m 2 K + C s m o o t h t 0 ( β ∧ 2 ) / 2 + C O U d x t 0 + C s t a b H K [ C ~ a p p , 0 t 0 − γ 0 M − ζ 0 + E o p t ( N , M ) ] . (110) \mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_0(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{term}}e^{-T}
+ C_{\mathrm{disc}}\sqrt{\frac{d_x+m_2}{K}}
+ C_{\mathrm{smooth}}t_0^{(\beta\wedge2)/2}
+ C_{\mathrm{OU}}d_xt_0
+ C_{\mathrm{stab}}\sqrt{H_K\left[\widetilde{C}_{\mathrm{app},0}t_0^{-\gamma_0}M^{-\zeta_0}+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}. \tag*{(110)} E SGD E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T + C disc K d x + m 2 + C smooth t 0 ( β ∧ 2 ) /2 + C OU d x t 0 + C stab H K [ C app , 0 t 0 − γ 0 M − ζ 0 + E opt ( N , M ) ] . (110)
Here E o p t ( N , M ) \mathcal{E}_{\mathrm{opt}}(N,M) E opt ( N , M ) denotes the finite-time population optimization error defined in (17) .
The terms in (110) have the following interpretation:
e − T ⏟ terminal initialization , ( d x + m 2 ) / K ⏟ time discretization , t 0 ( β ∧ 2 ) / 2 + d x t 0 ⏟ smoothing bias , \underbrace{e^{-T}}_{\text{terminal initialization},
\qquad
\underbrace{\sqrt{(d_x+m_2)/K}}_{\text{time discretization},
\qquad
\underbrace{t_0^{(\beta\wedge2)/2}+d_xt_0}_{\text{smoothing bias},}}} terminal initialization , time discretization , smoothing bias , t 0 ( β ∧ 2 ) /2 + d x t 0 ( d x + m 2 ) / K e − T
and
H K [ t 0 − γ 0 M − ζ 0 + E o p t ( N , M ) ] ⏟ approximation and finite-time optimization . \underbrace{\sqrt{H_K\left[t_0^{-\gamma_0}M^{-\zeta_0}+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}}_{\text{approximation and finite-time optimization}}. approximation and finite-time optimization H K [ t 0 − γ 0 M − ζ 0 + E opt ( N , M ) ] .
Thus, unlike the stopped-law theorem, the original-law guarantee contains an additional smoothing-bias contribution and uses the full-dimensional later-time approximation rate.
Proof of Corollary D.3
Proof. Step 1: Decompose the total-variation error. For each fixed y y y , let p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) denote the OU-smoothed conditional law at time t 0 t_0 t 0 . Let p ~ t 0 ( ⋅ ∣ y ) \widetilde{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) denote the admissibly discretized reverse law initialized from p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) and using the learned score s ^ \widehat{s} s . Finally, let p ^ t 0 ( ⋅ ∣ y ) \widehat{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) denote the same learned-score reverse chain initialized from N ( 0 , I d x ) \mathcal{N}(0,I_{d_x}) N ( 0 , I d x ) . By the triangle inequality,
TV ( p 0 ( ⋅ ∣ y ) , p ^ t 0 ( ⋅ ∣ y ) ) ≤ TV ( p 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) ) + TV ( p t 0 ( ⋅ ∣ y ) , p ~ t 0 ( ⋅ ∣ y ) ) + TV ( p ~ t 0 ( ⋅ ∣ y ) , p ^ t 0 ( ⋅ ∣ y ) ) . (111) \operatorname{TV}\left(p_0(\cdot\mid y),\widehat{p}_{t_0}(\cdot\mid y)\right)
\le\operatorname{TV}\left(p_0(\cdot\mid y),p_{t_0}(\cdot\mid y)\right)
+ \operatorname{TV}\left(p_{t_0}(\cdot\mid y),\widetilde{p}_{t_0}(\cdot\mid y)\right)
+ \operatorname{TV}\left(\widetilde{p}_{t_0}(\cdot\mid y),\widehat{p}_{t_0}(\cdot\mid y)\right). \tag*{(111)} TV ( p 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) ) ≤ TV ( p 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) ) + TV ( p t 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) ) + TV ( p t 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) ) . (111)
These are, respectively, the smoothing-bias, learned-score/discretization, and terminal-initialization errors.
Step 2: Bound the smoothing bias.
Lemma Lemma B.4 gives
E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C s m o o t h t 0 ( β ∧ 2 ) / 2 + C O U d x t 0 . (112) \mathbb{E}_{Y}\left[\operatorname{TV}\left(p_0(\cdot\mid Y),p_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{smooth}}t_0^{(\beta\wedge2)/2}+C_{\mathrm{OU}}d_x t_0. \tag*{(112)} E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C smooth t 0 ( β ∧ 2 ) /2 + C OU d x t 0 . (112)
Step 3: Bound the terminal-initialization error.
For a fixed learned score, the laws p ~ t 0 ( ⋅ ∣ y ) \widetilde{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) and p ^ t 0 ( ⋅ ∣ y ) \widehat{p}_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) are obtained by applying the same reverse Markov kernel to the initial distributions p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) and N ( 0 , I d x ) \mathcal{N}(0,I_{d_x}) N ( 0 , I d x ) . Therefore, by contraction of total variation under Markov kernels,
TV ( p ~ t 0 ( ⋅ ∣ y ) , p ^ t 0 ( ⋅ ∣ y ) ) ≤ TV ( p T ( ⋅ ∣ y ) , N ( 0 , I d x ) ) . \operatorname{TV}\left(\widetilde{p}_{t_0}(\cdot\mid y),\widehat{p}_{t_0}(\cdot\mid y)\right)
\le\operatorname{TV}\left(p_T(\cdot\mid y),\mathcal{N}(0,I_{d_x})\right). TV ( p t 0 ( ⋅ ∣ y ) , p t 0 ( ⋅ ∣ y ) ) ≤ TV ( p T ( ⋅ ∣ y ) , N ( 0 , I d x ) ) .
The conditional Gaussian-KL calculation in Eq. (79) , followed by Pinsker’s inequality, therefore yields
E Y [ TV ( p ~ t 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T . (113) \mathbb{E}_{Y}\left[\operatorname{TV}\left(\widetilde{p}_{t_0}(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{term}}e^{-T}. \tag*{(113)} E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T . (113)
Step 4: Bound the score and discretization error.
For a fixed realization of s ^ \widehat{s} s , apply Lemma E.1 . This gives
E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ~ t 0 ( ⋅ ∣ Y ) ) ] ≤ C s t a b ( ∑ k = 1 K Δ k E [ ∥ s ^ ( X t k , Y , t k ) − s ∗ ( X t k , t k , Y ) ∥ 2 2 ] ) 1 / 2 + C d i s c d x + m 2 K . (114) \begin{aligned}
\mathbb{E}_{Y}\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widetilde{p}_{t_0}(\cdot\mid Y)\right)\right]
&\le C_{\mathrm{stab}}\left(\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\|\widehat{s}(X_{t_k},Y,t_k)-s^*(X_{t_k},t_k,Y)\right\|_2^2\right]\right)^{1/2}\\
&\quad+C_{\mathrm{disc}}\sqrt{\frac{d_x+m^2}{K}}. \tag*{(114)}
\end{aligned} E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C stab ( k = 1 ∑ K Δ k E [ ∥ s ( X t k , Y , t k ) − s ∗ ( X t k , t k , Y ) ∥ 2 2 ] ) 1/2 + C disc K d x + m 2 . (114)
Define
A ^ K , 0 : = E [ ∥ s ^ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] . (115) \widehat{A}_{K,0}:=\mathbb{E}\left[\left\|\widehat{s}(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^2\right]. \tag*{(115)} A K , 0 := E [ ∥ s ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] . (115)
Because
P ( J = k ) = Δ k H K , \mathbb{P}(J=k)=\frac{\Delta_k}{H_K}, P ( J = k ) = H K Δ k ,
we have
H K A ^ K , 0 = ∑ k = 1 K Δ k E [ ∥ s ^ ( X t k , Y , t k ) − s ∗ ( X t k , t k , Y ) ∥ 2 2 ] . (116) H_K\widehat{A}_{K,0}=\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\|\widehat{s}(X_{t_k},Y,t_k)-s^*(X_{t_k},t_k,Y)\right\|_2^2\right]. \tag*{(116)} H K A K , 0 = k = 1 ∑ K Δ k E [ ∥ s ( X t k , Y , t k ) − s ∗ ( X t k , t k , Y ) ∥ 2 2 ] . (116)
Hence
E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ~ t 0 ( ⋅ ∣ Y ) ) ] ≤ C s t a b H K A ^ K , 0 + C d i s c d x + m 2 K . (117) \mathbb{E}_{Y}\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widetilde{p}_{t_0}(\cdot\mid Y)\right)\right]
\le C_{\mathrm{stab}}\sqrt{H_K\widehat{A}_{K,0}}+C_{\mathrm{disc}}\sqrt{\frac{d_x+m^2}{K}}. \tag*{(117)} E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C stab H K A K , 0 + C disc K d x + m 2 . (117)
Step 5: Separate approximation and optimization.
Let
Z J : = ∇ x log q t J ( X t J ∣ X 0 ) . Z_J:=\nabla_x\log q_{t_J}(X_{t_J}\mid X_0). Z J := ∇ x log q t J ( X t J ∣ X 0 ) .
The denoising identity gives
s ∗ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] . s^*(X_{t_J},t_J,Y)=\mathbb{E}[Z_J\mid X_{t_J},Y,t_J]. s ∗ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] .
Therefore, for every θ ∈ Θ M \theta\in\Theta_M θ ∈ Θ M ,
L K ( θ ) = C K + E [ ∥ s θ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] , (118) \mathcal{L}_K(\theta)=C_K+\mathbb{E}\left[\left\|s_\theta(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\right\|_2^2\right], \tag*{(118)} L K ( θ ) = C K + E [ ∥ s θ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 ] , (118)
where C K C_K C K is independent of θ \theta θ .
Taking the infimum over Θ M \Theta_M Θ M gives
L K , M ∗ = C K + A K , 0 ( M ) . (119) \mathcal{L}_{K,M}^*=C_K+A_{K,0}(M). \tag*{(119)} L K , M ∗ = C K + A K , 0 ( M ) . (119)
Applying (118) at θ ^ \hat{\theta} θ ^ ,
A ^ K , 0 = L K ( θ ^ ) − C K = [ L K ( θ ^ ) − L K , M ∗ ] + A K , 0 ( M ) . (120) \begin{aligned}
\widehat{A}_{K,0}=\mathcal{L}_K(\hat{\theta})-C_K \\
&=\left[\mathcal{L}_K(\hat{\theta})-\mathcal{L}_{K,M}^*\right]+A_{K,0}(M). \tag*{(120)}
\end{aligned} A K , 0 = L K ( θ ^ ) − C K = [ L K ( θ ^ ) − L K , M ∗ ] + A K , 0 ( M ) . (120)
Taking expectation over online SGD yields
E S G D [ A ^ K , 0 ] = A K , 0 ( M ) + E o p t ( N , M ) . (121) \mathbb{E}_{\mathrm{SGD}}\left[\widehat{A}_{K,0}\right]=A_{K,0}(M)+\mathcal{E}_{\mathrm{opt}}(N,M). \tag*{(121)} E SGD [ A K , 0 ] = A K , 0 ( M ) + E opt ( N , M ) . (121)
By (109) ,
A K , 0 ( M ) ≤ O ~ ( t 0 − γ 0 M − ζ 0 ) . A_{K,0}(M)\leq\widetilde{O}\left(t_0^{-\gamma_0}M^{-\zeta_0}\right). A K , 0 ( M ) ≤ O ( t 0 − γ 0 M − ζ 0 ) .
Consequently,
E S G D [ A ^ K , 0 ] ≤ C ~ a p p , 0 t 0 − γ 0 M − ζ 0 + E o p t ( N , M ) . (122) \mathbb{E}_{\mathrm{SGD}}\left[\widehat{A}_{K,0}\right]\leq\widetilde{C}_{\mathrm{app},0}t_0^{-\gamma_0}M^{-\zeta_0}+\mathcal{E}_{\mathrm{opt}}(N,M). \tag*{(122)} E SGD [ A K , 0 ] ≤ C app , 0 t 0 − γ 0 M − ζ 0 + E opt ( N , M ) . (122)
Taking expectation over SGD in (117) and using Jensen’s inequality,
E S G D E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ~ t 0 ( ⋅ ∣ Y ) ) ] ≤ C d i s c r d x + m 2 K + C s t a b H K [ C ~ a p p , 0 t 0 − γ 0 M − ζ 0 + E o p t ( N , M ) ] . (123) \begin{aligned}
\mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\widetilde{p}_{t_0}(\cdot\mid Y)\right)\right] \\
&\leq C_{\mathrm{discr}}\sqrt{\frac{d_x+m_2}{K}}
+C_{\mathrm{stab}}\sqrt{H_K\left[\widetilde{C}_{\mathrm{app},0}t_0^{-\gamma_0}M^{-\zeta_0}+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}. \tag*{(123)}
\end{aligned} E SGD E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C discr K d x + m 2 + C stab H K [ C app , 0 t 0 − γ 0 M − ζ 0 + E opt ( N , M ) ] . (123)
Step 6: Combine all terms.
Taking expectations in (111) and substituting (112) , (113) , and (123) , we obtain
E S G D E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ C t e r m e − T + C d i s c r d x + m 2 K + C s m o o t h t 0 ( β ∧ 2 ) / 2 + C O U d x t 0 + C s t a b H K [ C ~ a p p , 0 t 0 − γ 0 M − ζ 0 + E o p t ( N , M ) ] . (124) \begin{aligned}
\mathbb{E}_{\mathrm{SGD}}\mathbb{E}_Y\left[\operatorname{TV}\left(p_0(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right] \\
&\leq C_{\mathrm{term}}e^{-T}
+C_{\mathrm{discr}}\sqrt{\frac{d_x+m_2}{K}}
+C_{\mathrm{smooth}}t_0^{(\beta\wedge2)/2}
+C_{\mathrm{OU}}d_xt_0
+C_{\mathrm{stab}}\sqrt{H_K\left[\widetilde{C}_{\mathrm{app},0}t_0^{-\gamma_0}M^{-\zeta_0}+\mathcal{E}_{\mathrm{opt}}(N,M)\right]}. \tag*{(124)}
\end{aligned} E SGD E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ C term e − T + C discr K d x + m 2 + C smooth t 0 ( β ∧ 2 ) /2 + C OU d x t 0 + C stab H K [ C app , 0 t 0 − γ 0 M − ζ 0 + E opt ( N , M ) ] . (124)
This proves (110) .
Simplified ϵ \epsilon ϵ -Complexity
We now specialize the general bound under the uniform optimization-geometry condition used in Corollary 3.6 . In this extension, the uniformity is required along the full chosen sequence of score classes, grids, horizons, and cutoffs t 0 ↓ 0 t_0 \downarrow0 t 0 ↓ 0 . Thus, for the constants of each corresponding randomized-time objective, assume
L M ≤ L ‾ , μ M ≥ μ > 0 , σ M 2 ≤ σ ‾ 2 , Δ 0 , M ≤ Δ ‾ 0 . L_M \le\overline{L}, \qquad\mu_M \ge\mu> 0, \qquad\sigma_M^2 \le\overline{\sigma}^2, \qquad\Delta_{0,M} \le\overline{\Delta}_0. L M ≤ L , μ M ≥ μ > 0 , σ M 2 ≤ σ 2 , Δ 0 , M ≤ Δ 0 .
With mini-batch size B B B fixed independently of ϵ \epsilon ϵ and a fixed admissible r 0 r_0 r 0 , Proposition 3.4 gives
E o p t ( N , M ) = O ~ ( N − 1 ) . (125) \mathcal{E}_{\mathrm{opt}}(N,M)=\widetilde{O}(N^{-1}). \tag*{(125)} E opt ( N , M ) = O ( N − 1 ) . (125)
Define
a β : = max { 1 , 2 β } . (126) a_\beta:= \max\left\{1,\frac{2}{\beta}\right\}. \tag*{(126)} a β := max { 1 , β 2 } . (126)
Choose
t 0 = Θ ~ ( ϵ a β ) . (127) t_0=\widetilde{\Theta}\left(\epsilon^{a_\beta}\right). \tag*{(127)} t 0 = Θ ( ϵ a β ) . (127)
Then both smoothing-bias contributions satisfy
t 0 ( β ∧ 2 ) / 2 = O ~ ( ϵ ) , t_0^{(\beta\wedge2)/2}=\widetilde{O}(\epsilon), t 0 ( β ∧ 2 ) /2 = O ( ϵ ) ,
and
d x t 0 = O ~ ( ϵ ) , d_x t_0=\widetilde{O}(\epsilon), d x t 0 = O ( ϵ ) ,
for fixed d x d_x d x .
The approximation term requires
t 0 − γ 0 M − ζ 0 = O ~ ( ϵ 2 ) . t_0^{-\gamma_0}M^{-\zeta_0}=\widetilde{O}(\epsilon^2). t 0 − γ 0 M − ζ 0 = O ( ϵ 2 ) .
If
M = Θ ~ ( ϵ − Γ a p p , 0 ) , M=\widetilde{\Theta}\left(\epsilon^{-\Gamma_{\mathrm{app},0}}\right), M = Θ ( ϵ − Γ app , 0 ) ,
this condition is satisfied whenever
Γ a p p , 0 ζ 0 − a β γ 0 ≥ 2. \Gamma_{\mathrm{app},0}\zeta_0-a_\beta\gamma_0\ge2. Γ app , 0 ζ 0 − a β γ 0 ≥ 2.
Equivalently,
Γ a p p , 0 ≥ 2 + d y ′ α y + a β d x 2 . \Gamma_{\mathrm{app},0}\ge2+\frac{d_y'}{\alpha_y}+\frac{a_\beta d_x}{2}. Γ app , 0 ≥ 2 + α y d y ′ + 2 a β d x .
The second-regime requirement
M − ρ 0 ≤ t 0 M^{-\rho_0}\le t_0 M − ρ 0 ≤ t 0
is satisfied whenever
Γ a p p , 0 ρ 0 ≥ a β , \Gamma_{\mathrm{app},0}\rho_0\ge a_\beta, Γ app , 0 ρ 0 ≥ a β ,
or equivalently,
Γ a p p , 0 ≥ a β 2 ( 2 α x + d x + α x α y d y ′ ) . \Gamma_{\mathrm{app},0}\ge\frac{a_\beta}{2}\left(2\alpha_x+d_x+\frac{\alpha_x}{\alpha_y}d_y'\right). Γ app , 0 ≥ 2 a β ( 2 α x + d x + α y α x d y ′ ) .
Thus define
Γ a p p , 0 : = max { 2 + d y ′ α y + a β d x 2 , a β 2 ( 2 α x + d x + α x α y d y ′ ) } . (128) \Gamma_{\mathrm{app},0}:=\max\left\{2+\frac{d_y'}{\alpha_y}+\frac{a_\beta d_x}{2},\frac{a_\beta}{2}\left(2\alpha_x+d_x+\frac{\alpha_x}{\alpha_y}d_y'\right)\right\}. \tag*{(128)} Γ app , 0 := max { 2 + α y d y ′ + 2 a β d x , 2 a β ( 2 α x + d x + α y α x d y ′ ) } . (128)
Then the choice
M = Θ ~ ( ϵ − Γ a p p , 0 ) (129) M=\widetilde{\Theta}\left(\epsilon^{-\Gamma_{\mathrm{app},0}}\right) \tag*{(129)} M = Θ ( ϵ − Γ app , 0 ) (129)
controls both the full-dimensional approximation error and the later-time regime condition. Separately, choose
N = Θ ~ ( ϵ − 2 ) . (130) N = \widetilde{\Theta}\left(\epsilon^{-2}\right). \tag*{(130)} N = Θ ( ϵ − 2 ) . (130)
Then, under uniform optimization geometry,
E o p t ( N , M ) = O ~ ( ϵ 2 ) . \mathcal{E}_{\mathrm{opt}}(N,M) = \widetilde{O}\left(\epsilon^2\right). E opt ( N , M ) = O ( ϵ 2 ) .
Choose also
T = Θ ( log ( 1 / ϵ ) ) . T = \Theta\left(\log(1/\epsilon)\right). T = Θ ( log ( 1/ ϵ ) ) .
Then
e − T = O ( ϵ ) , H K ≤ T = O ( log ( 1 / ϵ ) ) . e^{-T} = O(\epsilon), \qquad H_K \le T = O\left(\log(1/\epsilon)\right). e − T = O ( ϵ ) , H K ≤ T = O ( log ( 1/ ϵ ) ) .
Finally, define
Λ 0 : = max { 2 , Γ a p p , 0 ζ 0 − a β γ 0 } . (131) \Lambda_0 := \max\{2,\Gamma_{\mathrm{app},0}\zeta_0-a\beta\gamma_0\}. \tag*{(131)} Λ 0 := max { 2 , Γ app , 0 ζ 0 − a β γ 0 } . (131)
An admissible grid satisfying
K = Θ ~ ( ( d x + m 2 ) ϵ − 2 ∨ ϵ − Λ 0 ) (132) K = \widetilde{\Theta}\left((d_x+m_2)\epsilon^{-2}\vee\epsilon^{-\Lambda_0}\right) \tag*{(132)} K = Θ ( ( d x + m 2 ) ϵ − 2 ∨ ϵ − Λ 0 ) (132)
controls both the reverse-process discretization term and the grid-fineness requirement
Δ max ≤ O ~ ( t 0 − γ 0 M − ζ 0 ) . \Delta_{\max}\le\widetilde{O}\left(t_0^{-\gamma_0}M^{-\zeta_0}\right). Δ m a x ≤ O ( t 0 − γ 0 M − ζ 0 ) .
Equivalently, retaining the total grid weight explicitly, it is sufficient to take
K ≳ ( d x + m 2 ) ϵ − 2 ∨ H K ϵ − ( Γ a p p , 0 ζ 0 − a β γ 0 ) , K\gtrsim(d_x+m_2)\epsilon^{-2}\vee H_K\epsilon^{-(\Gamma_{\mathrm{app},0}\zeta_0-a\beta\gamma_0)}, K ≳ ( d x + m 2 ) ϵ − 2 ∨ H K ϵ − ( Γ app , 0 ζ 0 − a β γ 0 ) ,
up to logarithmic factors. With the choices
t 0 = O ~ ( ϵ a β ) , t_0=\widetilde{O}\left(\epsilon^{a\beta}\right), t 0 = O ( ϵ a β ) ,
M = Θ ~ ( ϵ − Γ a p p , 0 ) , M=\widetilde{\Theta}\left(\epsilon^{-\Gamma_{\mathrm{app},0}}\right), M = Θ ( ϵ − Γ app , 0 ) ,
N = Θ ~ ( ϵ − 2 ) , N=\widetilde{\Theta}\left(\epsilon^{-2}\right), N = Θ ( ϵ − 2 ) ,
T = Θ ( log ( 1 / ϵ ) ) , T=\Theta\left(\log(1/\epsilon)\right), T = Θ ( log ( 1/ ϵ ) ) ,
and the admissible grid above, every term in (110) is O ~ ( ϵ ) \widetilde{O}(\epsilon) O ( ϵ ) . Therefore,
E S G D ∣ E Y [ TV ( p 0 ( ⋅ ∣ Y ) , p ^ t 0 ( ⋅ ∣ Y ) ) ] ≤ O ~ ( ϵ ) . (133) \mathbb{E}_{\mathrm{SGD|EY}}\left[\operatorname{TV}\left(p_0(\cdot\mid Y),\widehat{p}_{t_0}(\cdot\mid Y)\right)\right]\le\widetilde{O}(\epsilon). \tag*{(133)} E SGD∣EY [ TV ( p 0 ( ⋅ ∣ Y ) , p t 0 ( ⋅ ∣ Y ) ) ] ≤ O ( ϵ ) . (133)
As in the stopped-law result, the two main complexity requirements should be kept distinct:
M = Θ ~ ( ϵ − Γ a p p , 0 ) and N = Θ ~ ( ϵ − 2 ) . (134) M=\widetilde{\Theta}\left(\epsilon^{-\Gamma_{\mathrm{app},0}}\right)
\qquad\text{and}\qquad
N=\widetilde{\Theta}\left(\epsilon^{-2}\right). \tag*{(134)} M = Θ ( ϵ − Γ app , 0 ) and N = Θ ( ϵ − 2 ) . (134)
The first is the approximation-capacity requirement for the full-dimensional score class. The second is the number of fresh online denoising samples consumed by SGD under uniform optimization geometry. If the optimization constants deteriorate with M M M , the correct statement is the general bound (110) together with the explicit finite-time optimization bound from Proposition 3.4 .
Supplementary Lemmas
Lemma E.1 (Forward-law TV stability for discretized reverse sampling). Let 0 < t 0 < 1 ≤ T 0 < t_0 < 1 \le T 0 < t 0 < 1 ≤ T , and let
t 0 < t 1 < ⋯ < t K = T , Δ k : = t k − t k − 1 , k = 1 , … , K . t_0 < t_1 < \cdots< t_K = T, \qquad\Delta_k := t_k - t_{k-1}, \qquad k = 1,\ldots,K. t 0 < t 1 < ⋯ < t K = T , Δ k := t k − t k − 1 , k = 1 , … , K . For P Y P_Y P Y -a.e. y y y , let p t ( ⋅ ∣ y ) p_t(\cdot\mid y) p t ( ⋅ ∣ y ) denote the OU forward marginal at time t t t , and let
s ⋆ ( x , t , y ) : = ∇ x log p t ( x ∣ y ) s^\star(x,t,y) := \nabla_x \log p_t(x \mid y) s ⋆ ( x , t , y ) := ∇ x log p t ( x ∣ y ) be the conditional score. Let p t 0 ( ⋅ ∣ y ) p_{t_0}(\cdot\mid y) p t 0 ( ⋅ ∣ y ) be the law obtained by running the continuous reverse SDE from p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) down to time t 0 t_0 t 0 using the true score s ⋆ s^\star s ⋆ . For a fixed score estimator s ˉ \bar{s} s ˉ , let p ˉ t 0 d i s ( ⋅ ∣ y ) \bar{p}^{\mathrm{dis}}_{t_0}(\cdot\mid y) p ˉ t 0 dis ( ⋅ ∣ y ) denote the law of the corresponding exponential-integrator reverse sampler on the above grid, initialized from p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) and using s ˉ \bar{s} s ˉ in place of s ⋆ s^\star s ⋆ , with the update specified in Eq. (18) .
Assume the grid is chosen in the admissible form of Benton et al. [3 ] , with early-stopping parameter t 0 t_0 t 0 . In the forward-time notation used here, the corresponding admissible grid condition can be written as
Δ k ≤ κ min { 1 , t k − 1 } , κ = Θ ( T + log ( 1 / t 0 ) K ) , \Delta_k \le\kappa\min\{1,t_{k-1}\}, \qquad\kappa= \Theta\left(\frac{T+\log(1/t_0)}{K}\right), Δ k ≤ κ min { 1 , t k − 1 } , κ = Θ ( K T + log ( 1/ t 0 ) ) , with K K K large enough for the grid construction in that corollary. Suppose also that the conditional second moments are uniformly bounded:
m 2 : = e s s s u p y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞ . m_2 := \mathop{\mathrm{ess\,sup}}_{y\sim P_Y} \mathbb{E}\left[\lVert X_0\rVert_2^2 \mid Y=y\right] < \infty. m 2 := ess sup y ∼ P Y E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] < ∞. Then, whenever the score-error term below is finite,
E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ˉ t 0 d i s ( ⋅ ∣ Y ) ) ] ≲ ( ∑ k = 1 K Δ k E [ ∥ s ˉ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] ) 1 / 2 + O ~ ( d x + m 2 K ) . (135) \mathbb{E}_Y\left[\operatorname{TV}\left(p_{t_0}(\cdot\mid Y),\bar{p}^{\mathrm{dis}}_{t_0}(\cdot\mid Y)\right)\right]
\lesssim
\left(\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\lVert\bar{s}(X_{t_k},Y,t_k)-s^\star(X_{t_k},t_k,Y)\right\rVert_2^2\right]\right)^{1/2}
+\widetilde{O}\left(\sqrt{\frac{d_x+m_2}{K}}\right). \tag*{(135)} E Y [ TV ( p t 0 ( ⋅ ∣ Y ) , p ˉ t 0 dis ( ⋅ ∣ Y ) ) ] ≲ ( k = 1 ∑ K Δ k E [ ∥ s ˉ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] ) 1/2 + O ( K d x + m 2 ) . (135) In the normalized presentation where m 2 = O ( d x ) m_2 = O(d_x) m 2 = O ( d x ) , the last term is
O ~ ( d x K ) . \widetilde{O}\left(\sqrt{\frac{d_x}{K}}\right). O ( K d x ) . If d x d_x d x and m 2 m_2 m 2 are treated as fixed problem-dependent constants in the main-text notation, this term is written as O ~ ( K − 1 / 2 ) \widetilde{O}(K^{-1/2}) O ( K − 1/2 ) .
Proof. The result is a conditional version of the reverse-process KL discretization bound of Benton et al. [3 ] , converted to total variation. We give the reduction for completeness.
Fix y y y such that the conditional law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) has finite second moment. Apply the discretization theorem of Benton et al. [3 ] to the conditional OU diffusion with data law p 0 ( ⋅ ∣ y ) p_0(\cdot\mid y) p 0 ( ⋅ ∣ y ) , with the stopping time t 0 t_0 t 0 playing the role of their early-stopping parameter. Their path-space argument bounds the KL divergence between the exact reverse process and the admissibly discretized reverse process by a score-estimation term plus a discretization term. In the present notation this gives
KL ( p t 0 ( ⋅ ∣ y ) ∥ p ˉ t 0 d i s ( ⋅ ∣ y ) ) ≲ ∑ k = 1 K Δ k E [ ∥ s ˉ ( X t k , y , t k ) − s ⋆ ( X t k , t k , y ) ∥ 2 2 ∣ Y = y ] + Disc K ( y ) . (136) \operatorname{KL}\left(p_{t_0}(\cdot\mid y)\,\middle\|\,\bar{p}^{\mathrm{dis}}_{t_0}(\cdot\mid y)\right)
\lesssim
\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\lVert\bar{s}(X_{t_k},y,t_k)-s^\star(X_{t_k},t_k,y)\right\rVert_2^2 \mid Y=y\right]
+\operatorname{Disc}_K(y). \tag*{(136)} KL ( p t 0 ( ⋅ ∣ y ) p ˉ t 0 dis ( ⋅ ∣ y ) ) ≲ k = 1 ∑ K Δ k E [ ∥ s ˉ ( X t k , y , t k ) − s ⋆ ( X t k , t k , y ) ∥ 2 2 ∣ Y = y ] + Disc K ( y ) . (136)
where the expectation in the score-error term is under the forward noised marginal X t k ∼ p t k ( ⋅ ∣ y ) X_{t_k} \sim p_{t_k}(\cdot\mid y) X t k ∼ p t k ( ⋅ ∣ y ) .
The use of the forward marginal in the score-error term is the key point. It is exactly the form appearing in the randomized-time denoising objective. Thus this bound does not require a true-score discretized reverse chain to have exact grid marginals p t k ( ⋅ ∣ y ) p_{t_k}(\cdot\mid y) p t k ( ⋅ ∣ y ) .
The initialization term is absent from (136) because both processes in this lemma are initialized from the same law p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) . Equivalently, this follows from the path-KL decomposition in Eq. (17) of Benton et al. [3 ] : the path KL separates into a reverse path-measure term and an initial-law mismatch term, and the latter is zero when the two reverse processes start from the same p T ( ⋅ ∣ y ) p_T(\cdot\mid y) p T ( ⋅ ∣ y ) .
It remains to control the discretization contribution. The general second-moment bound in Benton et al. [3 ] gives
Disc K ( y ) ≲ κ 2 d x K + κ d x T + κ E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] . \operatorname{Disc}_K(y) \lesssim\kappa^2 d_x K + \kappa d_x T + \kappa\mathbb{E}[\lVert X_0\rVert_2^2 \mid Y=y]. Disc K ( y ) ≲ κ 2 d x K + κ d x T + κ E [∥ X 0 ∥ 2 2 ∣ Y = y ] .
Combining this expression with the admissible-grid construction in Benton et al. [3 ] yields, up to factors polynomial in T T T and logarithmic in 1 / t 0 1/t_0 1/ t 0 ,
Disc K ( y ) ≤ O ~ ( d x + E [ ∥ X 0 ∥ 2 2 ∣ Y = y ] K ) . \operatorname{Disc}_K(y) \le\widetilde{O}\left(\frac{d_x+\mathbb{E}[\lVert X_0\rVert_2^2 \mid Y=y]}{K}\right). Disc K ( y ) ≤ O ( K d x + E [∥ X 0 ∥ 2 2 ∣ Y = y ] ) .
Taking the essential supremum over y y y gives
Disc K ( y ) ≤ O ~ ( d x + m 2 K ) \operatorname{Disc}_K(y) \le\widetilde{O}\left(\frac{d_x+m_2}{K}\right) Disc K ( y ) ≤ O ( K d x + m 2 )
for P Y P_Y P Y -a.e. y y y .
Pinsker’s inequality and data processing from path space to the terminal marginal yield, for each such y y y ,
TV ( p t 0 ( ⋅ ∣ y ) , p t 0 d i s ( ⋅ ∣ y ) ) ≤ 1 2 KL ( p t 0 ( ⋅ ∣ y ) ∥ p t 0 d i s ( ⋅ ∣ y ) ) \operatorname{TV}\left(p_{t_0}(\cdot\mid y),p_{t_0}^{\mathrm{dis}}(\cdot\mid y)\right)
\le\sqrt{\frac{1}{2}\operatorname{KL}\left(p_{t_0}(\cdot\mid y)\mathbin{\|}p_{t_0}^{\mathrm{dis}}(\cdot\mid y)\right)} TV ( p t 0 ( ⋅ ∣ y ) , p t 0 dis ( ⋅ ∣ y ) ) ≤ 2 1 KL ( p t 0 ( ⋅ ∣ y ) ∥ p t 0 dis ( ⋅ ∣ y ) )
≲ ( ∑ k = 1 K Δ k E [ ∥ s ˉ ( X t k , y , t k ) − s ⋆ ( X t k , t k , y ) ∥ 2 2 ∣ Y = y ] ) 1 / 2 + O ~ ( d x + m 2 K ) . (137) \lesssim\left(\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\lVert\bar{s}(X_{t_k},y,t_k)-s^\star(X_{t_k},t_k,y)\right\rVert_2^2\mid Y=y\right]\right)^{1/2}
+\widetilde{O}\left(\sqrt{\frac{d_x+m_2}{K}}\right). \tag*{(137)} ≲ ( k = 1 ∑ K Δ k E [ ∥ s ˉ ( X t k , y , t k ) − s ⋆ ( X t k , t k , y ) ∥ 2 2 ∣ Y = y ] ) 1/2 + O ( K d x + m 2 ) . (137)
Finally, take expectation over Y Y Y . Jensen’s inequality gives
E Y [ ( ∑ k = 1 K Δ k E [ ∥ s ˉ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ∣ Y ] ) 1 / 2 ] ≤ ( ∑ k = 1 K Δ k E [ ∥ s ˉ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] ) 1 / 2 . (138) \begin{aligned}
\mathbb{E}_Y\left[\left(\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\lVert\bar{s}(X_{t_k},Y,t_k)-s^\star(X_{t_k},t_k,Y)\right\rVert_2^2\mid Y\right]\right)^{1/2}\right] \\
&\le\left(\sum_{k=1}^{K}\Delta_k\mathbb{E}\left[\left\lVert\bar{s}(X_{t_k},Y,t_k)-s^\star(X_{t_k},t_k,Y)\right\rVert_2^2\right]\right)^{1/2}. \tag*{(138)}
\end{aligned} E Y ( k = 1 ∑ K Δ k E [ ∥ s ˉ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ∣ Y ] ) 1/2 ≤ ( k = 1 ∑ K Δ k E [ ∥ s ˉ ( X t k , Y , t k ) − s ⋆ ( X t k , t k , Y ) ∥ 2 2 ] ) 1/2 . (138)
This proves (135) .
Lemma E.2 (Tail localization for randomized-time denoising). Suppose Assumption 3.1 holds. Let J ∼ π K J\sim\pi_K J ∼ π K be any random grid index supported on { 1 , … , K } \{1,\ldots,K\} { 1 , … , K } , with t J ∈ [ t 0 , T ] t_J\in[t_0,T] t J ∈ [ t 0 , T ] , and define
X t J = e − t J X 0 + 1 − e − 2 t J ε , ε ∼ N ( 0 , I d x ) . X_{t_J}=e^{-t_J}X_0+\sqrt{1-e^{-2t_J}}\,\varepsilon,\qquad\varepsilon\sim\mathcal{N}(0,I_{d_x}). X t J = e − t J X 0 + 1 − e − 2 t J ε , ε ∼ N ( 0 , I d x ) .
For R > 0 R>0 R > 0 , define
G ( R ) : = { ∥ Y ∥ 2 ≤ R , ∥ X 0 ∥ 2 ≤ R , ∥ ε ∥ 2 ≤ R } . \mathcal{G}(R):=\{\|Y\|_2\le R,\ \|X_0\|_2\le R,\ \|\varepsilon\|_2\le R\}. G ( R ) := { ∥ Y ∥ 2 ≤ R , ∥ X 0 ∥ 2 ≤ R , ∥ ε ∥ 2 ≤ R } .
Then there exist constants C , c > 0 C,c>0 C , c > 0 , depending only on the tail parameters and the dimensions, such that
P ( G ( R ) c ) ≤ C e − c R + C e − c R 2 . \mathbb{P}(\mathcal{G}(R)^c)\le Ce^{-cR}+Ce^{-cR^2}. P ( G ( R ) c ) ≤ C e − c R + C e − c R 2 .
Moreover, on G ( R ) \mathcal{G}(R) G ( R ) ,
∥ X t J ∥ 2 ≤ 2 R , \|X_{t_J}\|_2\le2R, ∥ X t J ∥ 2 ≤ 2 R ,
and the denoising target
Z J : = ∇ x log q t J ( X t J ∣ X 0 ) = − X t J − e − t J X 0 1 − e − 2 t J Z_J:=\nabla_x\log q_{t_J}(X_{t_J}\mid X_0)=-\frac{X_{t_J}-e^{-t_J}X_0}{1-e^{-2t_J}} Z J := ∇ x log q t J ( X t J ∣ X 0 ) = − 1 − e − 2 t J X t J − e − t J X 0
satisfies
∥ Z J ∥ 2 ≤ R 1 − e − 2 t 0 . \|Z_J\|_2\le\frac{R}{\sqrt{1-e^{-2t_0}}}. ∥ Z J ∥ 2 ≤ 1 − e − 2 t 0 R .
Finally, suppose s θ s_\theta s θ belongs to a bounded-parameter smooth-activation network class whose output has polynomial growth in the input. Then, for every integer m ≥ 1 m\ge1 m ≥ 1 ,
E [ ∥ s θ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 m ] ≤ C m P m ( θ , M , t 0 ) , \mathbb{E}\left[\|s_\theta(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\|_2^m\right]\le C_m\mathcal{P}_m(\theta,M,t_0), E [ ∥ s θ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 m ] ≤ C m P m ( θ , M , t 0 ) ,
where C m < ∞ C_m<\infty C m < ∞ , and P m ( θ , M , t 0 ) \mathcal{P}_m(\theta,M,t_0) P m ( θ , M , t 0 ) is a polynomial envelope depending on the network-size and parameter bounds and on ( 1 − e − 2 t 0 ) − 1 / 2 (1-e^{-2t_0})^{-1/2} ( 1 − e − 2 t 0 ) − 1/2 . In particular, for the approximation classes used in the theorem, this moment grows at most polynomially in M M M and polylogarithmic factors.
Proof. By Assumption 3.1,
E e λ Y ∥ Y ∥ < ∞ , ess sup y ∼ P Y E [ e λ X ∥ X 0 ∥ ∣ Y = y ] < ∞ . \mathbb{E}e^{\lambda_Y\|Y\|}<\infty,\qquad\operatorname*{ess\,sup}_{y\sim P_Y}\mathbb{E}\left[e^{\lambda_X\|X_0\|}\mid Y=y\right]<\infty. E e λ Y ∥ Y ∥ < ∞ , y ∼ P Y ess sup E [ e λ X ∥ X 0 ∥ ∣ Y = y ] < ∞.
Markov’s inequality therefore gives constants C 1 , c 1 > 0 C_1,c_1>0 C 1 , c 1 > 0 such that
P ( ∥ Y ∥ 2 > R ) + P ( ∥ X 0 ∥ 2 > R ) ≤ C 1 e − c 1 R . \mathbb{P}(\|Y\|_2>R)+\mathbb{P}(\|X_0\|_2>R)\le C_1e^{-c_1R}. P ( ∥ Y ∥ 2 > R ) + P ( ∥ X 0 ∥ 2 > R ) ≤ C 1 e − c 1 R .
Since ε ∼ N ( 0 , I d X ) \varepsilon\sim\mathcal{N}(0,I_{d_X}) ε ∼ N ( 0 , I d X ) , standard Gaussian concentration gives constants C 2 , c 2 > 0 C_2,c_2>0 C 2 , c 2 > 0 such that
P ( ∥ ε ∥ 2 > R ) ≤ C 2 e − c 2 R 2 . \mathbb{P}(\|\varepsilon\|_2>R)\le C_2e^{-c_2R^2}. P ( ∥ ε ∥ 2 > R ) ≤ C 2 e − c 2 R 2 .
A union bound gives the stated bound on P ( G ( R ) c ) \mathbb{P}(\mathcal{G}(R)^c) P ( G ( R ) c ) .
On G ( R ) \mathcal{G}(R) G ( R ) ,
∥ X t J ∥ 2 ≤ e − t J ∥ X 0 ∥ 2 + 1 − e − 2 t J ∥ ε ∥ 2 ≤ 2 R . \|X_{t_J}\|_2\le e^{-t_J}\|X_0\|_2+\sqrt{1-e^{-2t_J}}\|\varepsilon\|_2\le2R. ∥ X t J ∥ 2 ≤ e − t J ∥ X 0 ∥ 2 + 1 − e − 2 t J ∥ ε ∥ 2 ≤ 2 R .
Also,
X t J − e − t J X 0 = 1 − e − 2 t J ε . X_{t_J}-e^{-t_J}X_0=\sqrt{1-e^{-2t_J}}\,\varepsilon. X t J − e − t J X 0 = 1 − e − 2 t J ε .
Therefore,
∥ Z J ∥ 2 = ∥ ε ∥ 2 1 − e − 2 t J ≤ R 1 − e − 2 t 0 , \|Z_J\|_2=\frac{\|\varepsilon\|_2}{\sqrt{1-e^{-2t_J}}}\le\frac{R}{\sqrt{1-e^{-2t_0}}}, ∥ Z J ∥ 2 = 1 − e − 2 t J ∥ ε ∥ 2 ≤ 1 − e − 2 t 0 R ,
because t J ≥ t 0 t_J\ge t_0 t J ≥ t 0 .
For the moment bound, the denoising identity gives
s ∗ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] . s^*(X_{t_J},t_J,Y)=\mathbb{E}[Z_J\mid X_{t_J},Y,t_J]. s ∗ ( X t J , t J , Y ) = E [ Z J ∣ X t J , Y , t J ] .
By Jensen’s inequality,
E [ ∥ s ∗ ( X t J , t J , Y ) ∥ 2 m ] ≤ E [ ∥ Z J ∥ 2 m ] < ∞ , \mathbb{E}\left[\|s^*(X_{t_J},t_J,Y)\|_2^m\right]\le\mathbb{E}\left[\|Z_J\|_2^m\right]<\infty, E [ ∥ s ∗ ( X t J , t J , Y ) ∥ 2 m ] ≤ E [ ∥ Z J ∥ 2 m ] < ∞ ,
where finiteness follows from Gaussian moments of ε \varepsilon ε and the lower cutoff t J ≥ t 0 > 0 t_J\ge t_0>0 t J ≥ t 0 > 0 . Polynomial growth of s θ s_\theta s θ , together with the sub-exponential moments of X 0 X_0 X 0 and Y Y Y , Gaussian moments of ε \varepsilon ε , and the bounded time interval, gives the claimed polynomial envelope. ∎
Lemma E.3 (Localized manifold-adapted score approximation). Suppose Assumption 3.1 holds, let M ≥ 2 M \ge2 M ≥ 2 , and let J ∼ π K J \sim\pi_K J ∼ π K be the randomized grid-time index with t J ∈ [ t 0 , T ] t_J \in[t_0,T] t J ∈ [ t 0 , T ] . Define
Δ max : = max 1 ≤ k ≤ K ( t k − t k − 1 ) , H K : = ∑ k = 1 K ( t k − t k − 1 ) . \Delta_{\max} := \max_{1 \le k \le K}(t_k-t_{k-1}), \qquad H_K := \sum_{k=1}^{K}(t_k-t_{k-1}). Δ m a x := 1 ≤ k ≤ K max ( t k − t k − 1 ) , H K := k = 1 ∑ K ( t k − t k − 1 ) . Let
η a p p : = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ . \eta_{\mathrm{app}} := \frac{2\alpha_x}{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y}. η app := 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x . Let
G M : = { ∥ Y ∥ 2 ≤ C log M , ∥ X 0 ∥ 2 ≤ C log M , ∥ ε ∥ 2 ≤ C log M } , \mathcal{G}_M := \{\lVert Y\rVert_2 \le C\log M,\ \lVert X_0\rVert_2 \le C\log M,\ \lVert\varepsilon\rVert_2 \le C\log M\}, G M := {∥ Y ∥ 2 ≤ C log M , ∥ X 0 ∥ 2 ≤ C log M , ∥ ε ∥ 2 ≤ C log M } , where
X t = e − t X 0 + 1 − e − 2 t ε . X_t=e^{-t}X_0+\sqrt{1-e^{-2t}}\,\varepsilon. X t = e − t X 0 + 1 − e − 2 t ε . Let u 0 = t 0 u_0=t_0 u 0 = t 0 and define a dyadic cover of the time interval by
u i + 1 : = min { 2 u i , T } , i = 0 , … , I − 1 , u_{i+1}:=\min\{2u_i,T\}, \qquad i=0,\ldots,I-1, u i + 1 := min { 2 u i , T } , i = 0 , … , I − 1 , so that
[ t 0 , T ] ⊆ ⋃ i = 0 I − 1 [ u i , u i + 1 ] , I ≤ 1 + ⌈ log 2 ( T t 0 ) ⌉ . [t_0,T]\subseteq\bigcup_{i=0}^{I-1}[u_i,u_{i+1}], \qquad I\le1+\left\lceil\log_2\left(\frac{T}{t_0}\right)\right\rceil. [ t 0 , T ] ⊆ i = 0 ⋃ I − 1 [ u i , u i + 1 ] , I ≤ 1 + ⌈ log 2 ( t 0 T ) ⌉ . Assume that the approximation-scale class F Θ , M \mathcal{F}_{\Theta,M} F Θ , M in (5) is chosen large enough to contain smooth time-gated realizations of the dyadic-block conditional neural-network construction:
( x , y , t ) ↦ ∑ i = 0 I − 1 χ i ( t ) ϕ i ( x , y , t ) , (x,y,t)\mapsto\sum_{i=0}^{I-1}\chi_i(t)\phi_i(x,y,t), ( x , y , t ) ↦ i = 0 ∑ I − 1 χ i ( t ) ϕ i ( x , y , t ) , where { χ i } i = 0 I − 1 \{\chi_i\}_{i=0}^{I-1} { χ i } i = 0 I − 1 is a nonnegative smooth partition of unity adapted to the dyadic blocks, the time derivatives of the gates are controlled by polylogarithmic factors in the theorem regime, and each ϕ i \phi_i ϕ i belongs to the corresponding blockwise conditional score-approximation class used in the anisotropic manifold-adaptive approximation theorem of Tang et al. [33 ] . Then there exists s ~ ∈ F Θ , M \widetilde{s}\in\mathcal{F}_{\Theta,M} s ∈ F Θ , M such that
E [ ∥ s ~ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M ] ≤ O ~ ( M − η a p p + Δ max ) . \mathbb{E}\left[\lVert\widetilde{s}(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\rVert_2^2\mathbf{1}_{\mathcal{G}_M}\right]\le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right). E [ ∥ s ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M ] ≤ O ( M − η app + Δ m a x ) . In particular, if
Δ max ≤ O ~ ( M − η a p p ) , \Delta_{\max}\le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right), Δ m a x ≤ O ( M − η app ) , then
E [ ∥ s ~ ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M ] ≤ O ~ ( M − η a p p ) . \mathbb{E}\left[\lVert\widetilde{s}(X_{t_J},Y,t_J)-s^*(X_{t_J},t_J,Y)\rVert_2^2\mathbf{1}_{\mathcal{G}_M}\right]\le\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). E [ ∥ s ( X t J , Y , t J ) − s ∗ ( X t J , t J , Y ) ∥ 2 2 1 G M ] ≤ O ( M − η app ) . The hidden logarithmic factors may depend on the localization radius, the dyadic block count I I I , the lower cutoff t 0 t_0 t 0 , the upper horizon T T T , and the uniform chart and local smoothness constants in Assumption 3.1.
Proof. The proof reduces the localized approximation problem to the anisotropic time-dependent conditional manifold approximation theorem of Tang et al. [33 ] . The additional steps are localization, smooth time-gating, and transfer from continuous-time integrated error to the discrete randomized grid-time error used in L K \mathcal{L}_K L K .
On the event G M \mathcal{G}_M G M , the variables X 0 X_0 X 0 , Y Y Y , and ϵ \epsilon ϵ are restricted to a compact set of radius
R M : = C log M . R_M := C\log M. R M := C log M .
Since t ≥ t 0 > 0 t \ge t_0 > 0 t ≥ t 0 > 0 , the OU variance 1 − e − 2 t 1-e^{-2t} 1 − e − 2 t is uniformly bounded below. Consequently,
s ⋆ ( x , t , y ) = ∇ x log p t ( x ∣ y ) s^\star(x,t,y)=\nabla_x\log p_t(x\mid y) s ⋆ ( x , t , y ) = ∇ x log p t ( x ∣ y )
is a Gaussian-smoothed conditional score on the localized region. The smoothness part of Assumption 3.1, together with the lower cutoff t 0 t_0 t 0 , gives local anisotropic Hölder and time-regularity constants on this compact region. These constants grow at most polylogarithmically in M M M , with additional dependence on t 0 − 1 t_0^{-1} t 0 − 1 , T T T , and the chart constants.
We now identify the approximation input. In the notation of Tang et al. [33 ] , the covariate is denoted by x x x , the noisy response by w w w , and the approximating network by ϕ i ( w , x , t ) \phi_i(w,x,t) ϕ i ( w , x , t ) on a dyadic time block. We apply the same construction after the relabeling
x T a n g ↔ y , w T a n g ↔ x . x_{\mathrm{Tang}}\leftrightarrow y,\qquad w_{\mathrm{Tang}}\leftrightarrow x. x Tang ↔ y , w Tang ↔ x .
Thus their conditional score ∇ log p t ( ⋅ ∣ x ) ( w ) \nabla\log p_t(\cdot\mid x)(w) ∇ log p t ( ⋅ ∣ x ) ( w ) corresponds here to
∇ x log p t ( x ∣ y ) = s ⋆ ( x , t , y ) . \nabla_x\log p_t(x\mid y)=s^\star(x,t,y). ∇ x log p t ( x ∣ y ) = s ⋆ ( x , t , y ) .
The manifold assumptions needed for this application are supplied locally by Assumption 3.1. The conditioning variable Y Y Y has intrinsic dimension d y ′ d'_y d y ′ , and, for each y y y , the clean conditional support of X 0 ∣ Y = y X_0\mid Y=y X 0 ∣ Y = y has intrinsic dimension d x ′ d'_x d x ′ . The fibered chart regularity in Assumption 3.1 ensures that, on the localized region, the clean pair ( X 0 , Y ) (X_0,Y) ( X 0 , Y ) is represented by d x ′ + d y ′ d'_x+d'_y d x ′ + d y ′ intrinsic coordinates with uniformly controlled chart, encoder–decoder, and local smoothness constants. The approximation is anisotropic: the response coordinate has smoothness α x \alpha_x α x , while the conditioning coordinate has smoothness α y \alpha_y α y .
The anisotropic balance gives the effective approximation exponent
η a p p = 2 α x 2 α x + d x ′ + ( α x / α y ) d y ′ . \eta_{\mathrm{app}}=\frac{2\alpha_x}{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y}. η app = 2 α x + d x ′ + ( α x / α y ) d y ′ 2 α x .
Equivalently, if h x h_x h x denotes the response-coordinate resolution and h y h_y h y the conditioning-coordinate resolution, the balanced choice satisfies
h y ≍ h x α x / α y , h x 2 α x ≍ h y 2 α y , h_y\asymp h_x^{\alpha_x/\alpha_y},\qquad h_x^{2\alpha_x}\asymp h_y^{2\alpha_y}, h y ≍ h x α x / α y , h x 2 α x ≍ h y 2 α y ,
and the effective intrinsic covering dimension is
d x ′ + ( α x / α y ) d y ′ . d'_x+(\alpha_x/\alpha_y)d'_y. d x ′ + ( α x / α y ) d y ′ .
Choosing the approximation scale indexed by M M M according to
h x ≍ M − 1 / { 2 α x + d x ′ + ( α x / α y ) d y ′ } h_x\asymp M^{-1/\{2\alpha_x+d'_x+(\alpha_x/\alpha_y)d'_y\}} h x ≍ M − 1/ { 2 α x + d x ′ + ( α x / α y ) d y ′ }
yields squared localized approximation error
h x 2 α x = M − η a p p . h_x^{2\alpha_x}=M^{-\eta_{\mathrm{app}}}. h x 2 α x = M − η app .
This is the anisotropic version of the Lipschitz-specialized rate M − 2 / ( 2 + d x ′ + d y ′ ) M^{-2/(2+d'_x+d'_y)} M − 2/ ( 2 + d x ′ + d y ′ ) , which is recovered only when α x = α y = 1 \alpha_x=\alpha_y=1 α x = α y = 1 .
Applying the blockwise anisotropic conditional score approximation theorem on each dyadic block [ u i , u i + 1 ] [u_i,u_{i+1}] [ u i , u i + 1 ] , with the localized chart and smoothness constants absorbed into logarithmic factors, gives blockwise networks ϕ i \phi_i ϕ i satisfying
1 H K ∑ i = 0 I − 1 ∫ u i u i + 1 E [ ∥ ϕ i ( X t , Y , t ) − s ⋆ ( X t , t , Y ) ∥ 2 2 1 G M ] d t ≤ O ~ ( M − η a p p ) . \frac{1}{H_K}\sum_{i=0}^{I-1}\int_{u_i}^{u_{i+1}}\mathbb{E}\left[\left\lVert\phi_i(X_t,Y,t)-s^\star(X_t,t,Y)\right\rVert_2^2\mathbf{1}_{\mathcal{G}_M}\right]\,dt\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). H K 1 i = 0 ∑ I − 1 ∫ u i u i + 1 E [ ∥ ϕ i ( X t , Y , t ) − s ⋆ ( X t , t , Y ) ∥ 2 2 1 G M ] d t ≤ O ( M − η app ) .
The logarithmic factors absorb the dyadic block count I I I , the localized radius R M = C log M R_M=C\log M R M = C log M , the chart cover, the lower-time cutoff t 0 t_0 t 0 , and the upper horizon T T T .
The cited construction is blockwise in time. Our network class uses a single time-conditioned network. Let { χ i } i = 0 I − 1 \{\chi_i\}_{i=0}^{I-1} { χ i } i = 0 I − 1 be smooth gates forming a partition of unity over a slightly enlarged dyadic cover, with controlled time derivatives. Define
s ~ ( x , y , t ) : = ∑ i = 0 I − 1 χ i ( t ) ϕ i ( x , y , t ) . \widetilde{s}(x,y,t):=\sum_{i=0}^{I-1}\chi_i(t)\phi_i(x,y,t). s ( x , y , t ) := i = 0 ∑ I − 1 χ i ( t ) ϕ i ( x , y , t ) .
By the containment condition on F Θ , M \mathcal{F}_{\Theta,M} F Θ , M , s ~ ∈ F Θ , M \widetilde{s}\in\mathcal{F}_{\Theta,M} s ∈ F Θ , M . By convexity of the squared norm and the partition-of-unity property, the same integrated approximation bound holds for s ~ \widetilde{s} s , up to logarithmic factors:
1 H K ∫ t 0 T E [ ∥ s ~ ( X t , Y , t ) − s ⋆ ( X t , t , Y ) ∥ 2 2 1 G M ] d t ≤ O ~ ( M − η a p p ) . \frac{1}{H_K}\int_{t_0}^{T}\mathbb{E}\left[\left\lVert\widetilde{s}(X_t,Y,t)-s^\star(X_t,t,Y)\right\rVert_2^2\mathbf{1}_{\mathcal{G}_M}\right]\,dt\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). H K 1 ∫ t 0 T E [ ∥ s ( X t , Y , t ) − s ⋆ ( X t , t , Y ) ∥ 2 2 1 G M ] d t ≤ O ( M − η app ) .
It remains to transfer the continuous-time integrated approximation bound to the discrete randomized-time quantity used in L K \mathcal{L}_K L K . Define
a ( t ) : = E [ ∥ s ~ ( X t , Y , t ) − s ⋆ ( X t , t , Y ) ∥ 2 2 1 G M ] . a(t):=\mathbb{E}\left[\left\lVert\widetilde{s}(X_t,Y,t)-s^\star(X_t,t,Y)\right\rVert_2^2\mathbf{1}_{\mathcal{G}_M}\right]. a ( t ) := E [ ∥ s ( X t , Y , t ) − s ⋆ ( X t , t , Y ) ∥ 2 2 1 G M ] .
On [ t 0 , T ] [t_0,T] [ t 0 , T ] , the localized score, the OU transition map, and the smooth time-gated network have time-regularity constants controlled by polylogarithmic factors in the theorem regime. Equivalently, on each grid interval [ t k − 1 , t k ] [t_{k-1},t_k] [ t k − 1 , t k ] , the localized approximation-error curve a ( t ) a(t) a ( t ) is absolutely continuous with modulus
∣ a ( t ) − a ( t ′ ) ∣ ≤ O ~ ( 1 ) ∣ t − t ′ ∣ , t , t ′ ∈ [ t k − 1 , t k ] , |a(t)-a(t')|\leq\widetilde{O}(1)|t-t'|,\qquad t,t'\in[t_{k-1},t_k], ∣ a ( t ) − a ( t ′ ) ∣ ≤ O ( 1 ) ∣ t − t ′ ∣ , t , t ′ ∈ [ t k − 1 , t k ] ,
where the hidden factor may depend on t 0 − 1 t_0^{-1} t 0 − 1 , T T T , the localized smoothness constants, and the time-gate derivative bounds. Therefore,
a ( t k ) ≤ 1 t k − t k − 1 ∫ t k − 1 t k a ( t ) d t + O ~ ( Δ max ) . a(t_k)\leq\frac{1}{t_k-t_{k-1}}\int_{t_{k-1}}^{t_k}a(t)\,dt+\widetilde{O}(\Delta_{\max}). a ( t k ) ≤ t k − t k − 1 1 ∫ t k − 1 t k a ( t ) d t + O ( Δ m a x ) .
This is the only place where time regularity of the smoothed score and the smooth time gates is used; equivalently, it can be viewed as a standard Riemann-sum transfer bound for the localized approximation-error function a ( t ) a(t) a ( t ) .
Multiplying by Δ k = t k − t k − 1 \Delta_k=t_k-t_{k-1} Δ k = t k − t k − 1 , summing over k k k , and dividing by H K H_K H K , we obtain
∑ k = 1 K Δ k H K a ( t k ) ≤ 1 H K ∫ t 0 T a ( t ) d t + O ~ ( Δ max ) . \sum_{k=1}^{K}\frac{\Delta_k}{H_K}a(t_k)\leq\frac{1}{H_K}\int_{t_0}^{T}a(t)\,dt+\widetilde{O}(\Delta_{\max}). k = 1 ∑ K H K Δ k a ( t k ) ≤ H K 1 ∫ t 0 T a ( t ) d t + O ( Δ m a x ) .
Since P ( J = k ) = Δ k / H K \mathbb{P}(J=k)=\Delta_k/H_K P ( J = k ) = Δ k / H K , the left-hand side is exactly
E [ ∥ s ~ ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 1 G M ] . \mathbb{E}\left[\left\lVert\widetilde{s}(X_{t_J},Y,t_J)-s^\star(X_{t_J},t_J,Y)\right\rVert_2^2\mathbf{1}_{\mathcal{G}_M}\right]. E [ ∥ s ( X t J , Y , t J ) − s ⋆ ( X t J , t J , Y ) ∥ 2 2 1 G M ] .
Combining the grid-transfer bound with the anisotropic dyadic-block approximation bound gives
E [ ∥ s ~ ( X t j , Y , t j ) − s ⋆ ( X t j , t j , Y ) ∥ 2 2 1 G M ] ≤ O ~ ( M − η a p p + Δ max ) . \mathbb{E}\left[\left\|\widetilde{s}(X_{t_j},Y,t_j)-s^{\star}(X_{t_j},t_j,Y)\right\|_2^2\mathbf{1}_{\mathcal{G}_M}\right]\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}+\Delta_{\max}\right). E [ s ( X t j , Y , t j ) − s ⋆ ( X t j , t j , Y ) 2 2 1 G M ] ≤ O ( M − η app + Δ m a x ) .
If
Δ max ≤ O ~ ( M − η a p p ) , \Delta_{\max}\leq\widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right), Δ m a x ≤ O ( M − η app ) ,
the displayed bound reduces to
O ~ ( M − η a p p ) . \widetilde{O}\left(M^{-\eta_{\mathrm{app}}}\right). O ( M − η app ) .
This proves the lemma.
Experiments
The theory analyzes a single time-conditioned conditional score network
s θ ( x t , y , t ) s_\theta(x_t,y,t) s θ ( x t , y , t )
trained with fresh randomized-time denoising samples. The experiments in this appendix are therefore organized around the corresponding online training protocol. The goal is not to verify the asymptotic rates or prove the structural assumptions empirically. Rather, the experiments test whether the analyzed training model can be implemented directly, whether the approximation-complexity and online-budget effects can be separated in practice, and what trajectory behavior is observed in relation to the local geometry assumed in the proof.
Experimental Goals and Scope
The empirical study addresses five questions motivated by the theorem. First, can a single randomized-time score network be trained successfully using fresh online denoising samples? Second, can the effects of model complexity M M M and online denoising budget N = R B N=RB N = R B be varied separately? Third, does the randomized-time objective exhibit stable finite-run loss and parameter trajectories? Fourth, does score-estimation difficulty increase with intrinsic dimension in a generator that satisfies the fibered-manifold structure? Finally, does the online training procedure remain informative under conditional distributions with genuine sub-exponential tails?
All experiments use controlled synthetic conditional laws for which the conditional score can be computed analytically or by exact one-dimensional normal-Laplace score evaluation. This lets us measure score error directly, rather than relying only on downstream sample quality. Since the theory assumes smooth activations, the score network is a fully connected MLP with Softplus10 _{10} 10 activation, a smooth approximation to ReLU. This MLP is an implementation surrogate for the theoretical smooth-gated blockwise class; it does not instantiate the exact approximation construction.
Online Randomized-Time DDPM Training
We use an implementation-time coordinate u u u and a variance-preserving forward process
x u = α ( u ) x 0 + 1 − α ( u ) 2 ξ . x_u=\alpha(u)x_0+\sqrt{1-\alpha(u)^2}\,\xi. x u = α ( u ) x 0 + 1 − α ( u ) 2 ξ .
with a linear β \beta β -schedule. Define the effective OU time τ ( u ) : = − log α ( u ) \tau(u):=-\log\alpha(u) τ ( u ) := − log α ( u ) ; then x u = e − τ ( u ) x 0 + 1 − e − 2 τ ( u ) ξ x_u=e^{-\tau(u)}x_0+\sqrt{1-e^{-2\tau(u)}}\,\xi x u = e − τ ( u ) x 0 + 1 − e − 2 τ ( u ) ξ . For an implementation grid u 0 < ⋯ < u K u_0<\cdots<u_K u 0 < ⋯ < u K , set t k : = τ ( u k ) t_k:=\tau(u_k) t k := τ ( u k ) . The interval weights are formed on this effective OU-time grid using the right-endpoint convention in the analysis. At each SGD iteration, we draw a fresh mini-batch of conditional data ( X 0 , Y ) (X_0, Y) ( X 0 , Y ) , a grid index J J J , and Gaussian diffusion noise. We then form
X t J = α ( u J ) X 0 + 1 − α ( u J ) 2 ε X_{t_J} = \alpha(u_J)X_0 + \sqrt{1-\alpha(u_J)^2}\,\varepsilon X t J = α ( u J ) X 0 + 1 − α ( u J ) 2 ε
and train with the denoising loss
ℓ ( θ ) = ∥ s θ ( X t J , Y , t J ) + X t J − α ( u J ) X 0 1 − α ( u J ) 2 ∥ 2 . \ell(\theta) = \left\|s_\theta(X_{t_J},Y,t_J) + \frac{X_{t_J}-\alpha(u_J)X_0}{1-\alpha(u_J)^2}\right\|^2. ℓ ( θ ) = s θ ( X t J , Y , t J ) + 1 − α ( u J ) 2 X t J − α ( u J ) X 0 2 .
The reported online budget is N = R B N = RB N = R B , where R R R is the number of SGD updates and B B B is the mini-batch size. The optimizer is plain SGD with a decreasing step size of the form η r = c / ( r + r 0 ) \eta_r = c/(r+r_0) η r = c / ( r + r 0 ) .
Our baseline conditional benchmark is
x 0 = W y y + W z z + σ o b s ε , x_0 = W_y y + W_z z + \sigma_{\mathrm{obs}}\varepsilon, x 0 = W y y + W z z + σ obs ε ,
with Gaussian y y y , z z z , ε \varepsilon ε . Conditional on y y y , the law of x t x_t x t is Gaussian, so the true conditional score is available in closed form. The primary readout is randomized-time score MSE evaluated on fresh Monte Carlo batches.
Figure 1 shows the pilot online-budget trajectory from the online randomized-time training loop. The error remains finite and fluctuates within a relatively narrow range, but it does not decrease systematically over the displayed budget. Thus this single-seed pilot establishes only that the online randomized-time protocol can be executed without separate frozen-time training; it is not evidence of a sample-complexity trend or successful convergence. Larger multi-seed runs and additional tuning would be needed for such a claim.
Figure 1. Randomized-time score MSE versus online denoising budget N = R B N = RB N = R B for a single time-conditioned score network trained with fresh online SGD samples.
Separating Approximation Complexity and Online Budget
The theorem separates an approximation term depending on the score class complexity M M M from an online optimization term depending on the fresh sample budget N N N . To mirror this decomposition, we vary network width while holding depth and activation fixed. Width and parameter count are used only as operational proxies for M M M ; we do not claim that parameter count realizes the theoretical approximation index exactly. Figure 2 –Figure 4 show the resulting M M M -versus-N N N diagnostic. In the current pilot run, the curves are not monotone at every checkpoint, reflecting the variability of plain small-batch SGD. Nevertheless, the experiment cleanly separates the two axes emphasized by the theorem: one can hold architecture fixed and vary the online budget, or hold budget fixed and compare model capacities. We therefore interpret this experiment as an implementation-level diagnostic for the decomposition
Figure 2. Randomized-time score MSE versus online budget N N N , with network width used as an operational proxy for approximation complexity M M M .
Figure 4. Joint M M M -versus-N N N diagnostic. The heat map summarizes randomized-time score MSE over width and online denoising budget.
A K ( M ) + E o p t ( N , M ) , \mathcal{A}_{K}(M) + \mathcal{E}_{\mathrm{opt}}(N,M), A K ( M ) + E opt ( N , M ) ,
not as an empirical fit of the theoretical exponents.
Randomized-Time Optimization and Trajectory Diagnostics
The optimization analysis assumes a localized PL-type condition for the randomized-time denoising objective. We report related finite-trajectory diagnostics using evaluation batches independent of the online training samples; these diagnostics do not test the PL inequality. At checkpoints r r r , we estimate an evaluation loss L ^ K , e v a l ( θ r ) \widehat{\mathcal{L}}_{K,\mathrm{eval}}(\theta_r) L K , eval ( θ r ) and its gradient norm. Let L r e f L_{\mathrm{ref}} L ref be the smallest evaluation loss observed along the trajectory. The plotted quantity L ^ K , e v a l ( θ r ) − L r e f \widehat{\mathcal{L}}_{K,\mathrm{eval}}(\theta_r) - L_{\mathrm{ref}} L K , eval ( θ r ) − L ref is a reference-subtracted loss, not an estimate of the population excess risk L K ( θ r ) − L K , M ⋆ \mathcal{L}_{K}(\theta_r) - \mathcal{L}^{\star}_{K,M} L K ( θ r ) − L K , M ⋆ . We also track the parameter displacement ∥ θ r − θ 0 ∥ 2 \lVert\theta_r-\theta_0\rVert_2 ∥ θ r − θ 0 ∥ 2 . These are trajectory diagnostics only.
The plug-in PL ratio obtained by replacing the unknown optimum with L r e f L_{\mathrm{ref}} L ref is not reported: its denominator becomes numerically unstable near a checkpoint attaining the empirical reference loss and produces an artificial spike. The displacement curve records the radius explored in this finite run, but it does not identify a region on which the population PL inequality holds and does not establish the trajectory-containment assumption.
Figure 3. Final randomized-time score MSE versus parameter count, used as a practical proxy for the complexity index M M M .
Fiber-Compatible Intrinsic Dimension
The theory uses a joint fibered-manifold structure. To avoid making the clean response full dimensional through ambient observation noise, we use the synthetic construction
V ∈ R d y ′ , Z ∈ R d x ′ , V \in\mathbb{R}^{d'_y}, \qquad Z \in\mathbb{R}^{d'_x}, V ∈ R d y ′ , Z ∈ R d x ′ ,
Y = Φ Y ( V ) , X 0 = m ( Y ) + B Z , Y = \Phi_Y(V), \qquad X_0 = m(Y) + BZ, Y = Φ Y ( V ) , X 0 = m ( Y ) + B Z ,
where B ∈ R d x × d x ′ B \in\mathbb{R}^{d_x \times d'_x} B ∈ R d x × d x ′ has rank d x ′ d'_x d x ′ . The map Φ Y \Phi_Y Φ Y concatenates linear, sinusoidal, and quadratic features, giving a mildly nonlinear conditioning manifold. Conditional on Y = y Y = y Y = y , the positive time law X t ∣ Y = y X_t \mid Y = y X t ∣ Y = y is Gaussian with covariance
α ( t ) 2 B B ⊤ + ( 1 − α ( t ) 2 ) I d x , \alpha(t)^2 BB^\top+ (1-\alpha(t)^2)I_{d_x}, α ( t ) 2 B B ⊤ + ( 1 − α ( t ) 2 ) I d x ,
so the conditional score remains available in closed form. Figure 7 reports the pilot intrinsic-dimension diagnostic. The current smoke run covers only a reduced grid, so we do not read off a scaling law from it. Its main role is to instantiate the exact fiber-compatible construction required by the theory and confirm that the analytic score evaluation remains numerically usable at positive diffusion times.
Figure 7. Randomized-time score MSE for the fiber-compatible intrinsic-dimension generator. The ambient dimension is fixed while the joint intrinsic dimension is varied.
Sub-Exponential Tail Stress Test
Finally, we stress-test the online learner under conditionals with genuine sub-exponential tails. We use
x 0 = W y y + η G + η L , x_0 = W_y y + \eta_G + \eta_L, x 0 = W y y + η G + η L ,
where η G \eta_G η G is coordinatewise Gaussian and η L \eta_L η L is coordinatewise Laplace. The total coordinatewise variance is matched across regimes, so changes in performance are driven by tail shape rather than by a trivial scale change. After forward diffusion, each coordinate follows a normal-Laplace law, and the score is evaluated using the exact normal-Laplace density.
Figure Figure 8 confirms that the synthetic regimes become increasingly heavy-tailed as the Laplace component grows. In the current online-SGD pilot, Figure 9 also reveals that exact normal-Laplace score evaluation can make the score-MSE readout numerically sensitive for some intermediate regimes. We therefore interpret this experiment as a stress test of the online pipeline under unbounded sub-exponential tails: the tail construction itself matches the assumption, while the score-error readout should be stabilized with larger evaluation batches and full multi-seed runs before being used as a final quantitative claim.
Figure 8. Standardized excess kurtosis for the Gaussian-matched and sub-exponential regimes. Larger Laplace components produce visibly heavier tails.
Figure 9. Randomized-time score MSE under online SGD for Gaussian-matched and sub-exponential conditional laws.
Summary
The experiments implement the key training model appearing in the theorem: a single smooth time-conditioned score network trained by online SGD with fresh randomized-time denoising samples. The implementation also separates model capacity from online budget and adds randomized-time trajectory diagnostics, implements a fiber-compatible intrinsic-dimension generator, and retains a sub-exponential-tail stress test. The current pilot results show that the pipeline is operational, while also showing that the online-SGD diagnostics are noisy and do not yet display a clear learning curve. The appropriate empirical claim is therefore limited: these experiments instantiate the training protocol and stress-test several ingredients of the setup, but they do not validate the population PL condition, establish convergence or scaling exponents, or replace the formal theorem.
Figure 5. Randomized-time reference-subtracted evaluation loss along the online SGD trajectory.
Figure 6. Parameter displacement ∥ θ r − θ 0 ∥ 2 \lVert\theta_r - \theta_0 \rVert_2 ∥ θ r − θ 0 ∥ 2 along the online SGD trajectory.