Introduction
Diffusion models are a widely used class of generative models [12 ] (Sohl-Dickstein et al. 2015; Song & Ermon 2020; Song et al. 2021b), with notable success in domains such as image and video generation [6 , 13 , 4 ] (Rombach et al. 2022). A fixed forward process corrupts the data with Gaussian noise of increasing scale, until it is indistinguishable from pure noise, and a stochastic generator is trained to undo it one step at a time. In their variational derivation [12 , 16 ] (Sohl-Dickstein et al. 2015), the training objective is a bound that decomposes into a sum of per-step KL divergences between the forward process and the generator. Deterministic generators, however, have been found to give better samples in fewer steps [14 ] (Song et al. 2021a). A deterministic generator is obtained by making each of its steps a Dirac delta function, in which case the KL divergence at each step is ill-defined. DDIM (Song et al., 2021a) bypasses this issue by training a stochastic model and setting its variance to zero only during sampling. However, this introduces a mismatch between the training objective, which assumes a stochastic per-step generator, and the use of a deterministic per-step generator after training.
Flow models [18 , 1 ] (Liu et al. 2023) are another important class of deterministic generators, now used at scale [8 ] . Their justification is based on continuous-time ODEs and the properties of flows, and, like the probability-flow ODE of score-based models (Song et al., 2021b), they are derived outside the variational framework altogether.
A variational perspective on deterministic generators offers three benefits. First, it provides a training objective for the generator that is actually used for sampling: the per-step generator is deterministic both during and after training, so there is no mismatch of the kind introduced by DDIM. Second, it works directly with the discrete-time chain that is implemented in practice, rather than with the continuous-time ODE on which the justification of flow models rests. Third, it explains the freedom in weighting the per-step loss terms. The heuristic weightings used in practice, such as that of EDM [14 ] , arise as different choices of a single free parameter of the objective (§ 3.2 ).
Since the KL divergence is ill-defined for a deterministic generator, we use the spread divergence (Zhang et al., 2020), which smooths both distributions with the same Gaussian noise so that the divergence between them is well-defined. We then define a discrete-time spread variational objective and show that, for a finite training set, the optimal deterministic generator recovers the data distribution as the number of steps tends to infinity (Theorem 1). Furthermore, the objective is equivalent to a discrete-time implementation of flow matching for a specific choice of spread noise and the linear schedule (§ 4 ). This therefore also justifies why flow matching converges to the data distribution as the number of steps tends to infinity, without requiring the continuous-time machinery typically used to justify flow models.
Background
Diffusion
A standard diffusion model is defined by a forward noising process q ( x 1 : T ∣ x 0 ) = ∏ t = 1 T q ( x t ∣ x t − 1 , x 0 ) q(x_{1:T} \mid x_0) = \prod_{t=1}^{T} q(x_t \mid x_{t-1}, x_0) q ( x 1 : T ∣ x 0 ) = ∏ t = 1 T q ( x t ∣ x t − 1 , x 0 ) x 1 : T = ( x 1 , … , x T ) x_{1:T} = (x_1, \ldots, x_T) x 1 : T = ( x 1 , … , x T ) q ( x t ∣ x t − 1 , x 0 ) q(x_t \mid x_{t-1}, x_0) q ( x t ∣ x t − 1 , x 0 ) q ( x 0 ) q(x_0) q ( x 0 ) R d \mathbb{R}^d R d q ( x 0 ) q(x_0) q ( x 0 ) q ( x 0 ) = 1 N ∑ n = 1 N δ ( x 0 ∣ x 0 n ) q(x_0) = \frac{1}{N} \sum_{n=1}^{N} \delta(x_0 \mid x_0^n) q ( x 0 ) = N 1 ∑ n = 1 N δ ( x 0 ∣ x 0 n ) δ ( x ∣ y ) \delta(x \mid y) δ ( x ∣ y ) x x x y y y p θ ( x 0 : T ) = p ( x T ) ∏ t = 1 T p θ ( x t − 1 ∣ x t ) p_\theta(x_{0:T}) = p(x_T) \prod_{t=1}^{T} p_\theta(x_{t-1} \mid x_t) p θ ( x 0 : T ) = p ( x T ) ∏ t = 1 T p θ ( x t − 1 ∣ x t ) p θ ( x t − 1 ∣ x t ) = N ( x t − 1 ∣ μ θ ( x t ) , β t I ) p_\theta(x_{t-1} \mid x_t) = \mathcal{N}(x_{t-1} \mid\mu_\theta(x_t), \beta_t I) p θ ( x t − 1 ∣ x t ) = N ( x t − 1 ∣ μ θ ( x t ) , β t I ) μ θ \mu_\theta μ θ β t > 0 \beta_t > 0 β t > 0 μ θ \mu_\theta μ θ t t t q ( x T ∣ x 0 ) ≈ p ( x T ) = N ( x T ∣ 0 , I ) q(x_T \mid x_0) \approx p(x_T) = \mathcal{N}(x_T \mid0, I) q ( x T ∣ x 0 ) ≈ p ( x T ) = N ( x T ∣ 0 , I ) KL [ q ( x 0 ) ∥ p θ ( x 0 ) ] ≤ KL [ q ( x 0 : T ) ∥ p θ ( x 0 : T ) ] \operatorname{KL}[q(x_0) \mathbin{\|} p_\theta(x_0)] \le\operatorname{KL}[q(x_{0:T}) \mathbin{\|} p_\theta(x_{0:T})] KL [ q ( x 0 ) ∥ p θ ( x 0 )] ≤ KL [ q ( x 0 : T ) ∥ p θ ( x 0 : T )]
− ⟨ log p θ ( x 0 ) ⟩ q ( x 0 ) ≤ ∑ t = 2 T ⟨ KL [ q ( x t − 1 ∣ x t , x 0 ) ∥ p θ ( x t − 1 ∣ x t ) ] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) − ⟨ log p θ ( x 0 ∣ x 1 ) ⟩ q ( x 1 ∣ x 0 ) q ( x 0 ) + C (1) -\left\langle\log p_\theta(x_0) \right\rangle_{q(x_0)} \le\sum_{t=2}^{T} \left\langle\operatorname{KL}[q(x_{t-1} \mid x_t, x_0) \mathbin{\|} p_\theta(x_{t-1} \mid x_t)] \right\rangle_{q(x_t \mid x_0)q(x_0)} - \left\langle\log p_\theta(x_0 \mid x_1) \right\rangle_{q(x_1 \mid x_0)q(x_0)} + C \tag*{(1)} − ⟨ log p θ ( x 0 ) ⟩ q ( x 0 ) ≤ t = 2 ∑ T ⟨ KL [ q ( x t − 1 ∣ x t , x 0 ) ∥ p θ ( x t − 1 ∣ x t )] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) − ⟨ log p θ ( x 0 ∣ x 1 ) ⟩ q ( x 1 ∣ x 0 ) q ( x 0 ) + C (1) where ⟨ ⋅ ⟩ p \langle\cdot\rangle_p ⟨ ⋅ ⟩ p p p p C = ⟨ KL [ q ( x T ∣ x 0 ) ∥ p ( x T ) ] ⟩ q ( x 0 ) C = \left\langle\operatorname{KL}[q(x_T \mid x_0) \mathbin{\|} p(x_T)] \right\rangle_{q(x_0)} C = ⟨ KL [ q ( x T ∣ x 0 ) ∥ p ( x T )] ⟩ q ( x 0 ) § 9 ). Setting q ( x t − 1 ∣ x t , x 0 ) = δ ( ⋅ ∣ x 0 ) q(x_{t-1} \mid x_t, x_0) = \delta(\cdot\mid x_0) q ( x t − 1 ∣ x t , x 0 ) = δ ( ⋅ ∣ x 0 ) t = 1 t = 1 t = 1 1 θ \theta θ
L ( θ ) = ∑ t = 1 T ⟨ KL [ q ( x t − 1 ∣ x t , x 0 ) ∥ p θ ( x t − 1 ∣ x t ) ] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (2) L(\theta) = \sum_{t=1}^{T} \left\langle\operatorname{KL}[q(x_{t-1} \mid x_t, x_0) \mathbin{\|} p_\theta(x_{t-1} \mid x_t)] \right\rangle_{q(x_t \mid x_0)q(x_0)}. \tag*{(2)} L ( θ ) = t = 1 ∑ T ⟨ KL [ q ( x t − 1 ∣ x t , x 0 ) ∥ p θ ( x t − 1 ∣ x t )] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (2) Spread Divergence
A divergence Div ( p ∥ q ) \operatorname{Div}(p \mathbin{\|} q) Div ( p ∥ q ) k ( y ∣ x ) k(y \mid x) k ( y ∣ x ) k ( y ∣ x ) = N ( y ∣ x , σ 2 I ) k(y \mid x) = \mathcal{N}(y \mid x, \sigma^2 I) k ( y ∣ x ) = N ( y ∣ x , σ 2 I ) σ > 0 \sigma> 0 σ > 0
p ~ ( y ) = ∫ d x k ( y ∣ x ) p ( x ) , q ~ ( y ) = ∫ d x k ( y ∣ x ) q ( x ) . (3) \tilde{p}(y) = \int dx\, k(y \mid x)p(x), \qquad\tilde{q}(y) = \int dx\, k(y \mid x)q(x). \tag*{(3)} p ~ ( y ) = ∫ d x k ( y ∣ x ) p ( x ) , q ~ ( y ) = ∫ d x k ( y ∣ x ) q ( x ) . (3) The spread distributions p ~ \tilde{p} p ~ q ~ \tilde{q} q ~ p p p q q q Div ( p ~ ∥ q ~ ) \operatorname{Div}(\tilde{p} \mathbin{\|} \tilde{q}) Div ( p ~ ∥ q ~ ) y − x y-x y − x p ~ = k ∗ p \tilde{p} = k * p p ~ = k ∗ p
@bibliography The main reference list (18 unnumbered entries) is already transcribed. Skip its entries if they are printed on this page; transcribe everything else and mark citations as above. Fourier transform F \mathcal{F} F F { p ~ } = F { k } F { p } \mathcal{F}\{\tilde{p}\}=\mathcal{F}\{k\}\mathcal{F}\{p\} F { p ~ } = F { k } F { p } F { k } \mathcal{F}\{k\} F { k }
Div ( p ~ ∥ q ~ ) = 0 ⇔ p ~ = q ~ ⇔ F { k } F { p } = F { k } F { q } ⇔ F { p } = F { q } ⇔ p = q . (4) \operatorname{Div}(\tilde{p}\mathbin{\|}\tilde{q})=0 \Leftrightarrow\tilde{p}=\tilde{q} \Leftrightarrow\mathcal{F}\{k\}\mathcal{F}\{p\}=\mathcal{F}\{k\}\mathcal{F}\{q\} \Leftrightarrow\mathcal{F}\{p\}=\mathcal{F}\{q\} \Leftrightarrow p=q. \tag*{(4)} Div ( p ~ ∥ q ~ ) = 0 ⇔ p ~ = q ~ ⇔ F { k } F { p } = F { k } F { q } ⇔ F { p } = F { q } ⇔ p = q . (4) Hence the spread divergence is zero if and only if p = q p=q p = q
Degenerate Diffusion Model
We define the Degenerate Diffusion Model, in which each step of both the forward noising process and the generator is deterministic. In the forward process, the only randomness comes from the data point x 0 x_0 x 0 ϵ \epsilon ϵ x T x_T x T λ t \lambda_t λ t t ∈ { 0 , 1 , … , T } t \in\{0,1,\ldots,T\} t ∈ { 0 , 1 , … , T } λ 0 = 0 \lambda_0=0 λ 0 = 0 λ T = 1 \lambda_T=1 λ T = 1 q ( x t ∣ x 0 , ϵ ) = δ ( x t ∣ ( 1 − λ t ) x 0 + λ t ϵ ) q(x_t\mid x_0,\epsilon)=\delta(x_t\mid(1-\lambda_t)x_0+\lambda_t\epsilon) q ( x t ∣ x 0 , ϵ ) = δ ( x t ∣ ( 1 − λ t ) x 0 + λ t ϵ ) ϵ ∈ R d \epsilon\in\mathbb{R}^d ϵ ∈ R d q ( ϵ ) = N ( ϵ ∣ 0 , I ) q(\epsilon)=\mathcal{N}(\epsilon\mid0,I) q ( ϵ ) = N ( ϵ ∣ 0 , I ) q ( x T ) = N ( x T ∣ 0 , I ) q(x_T)=\mathcal{N}(x_T\mid0,I) q ( x T ) = N ( x T ∣ 0 , I )
q ( x 1 : T ∣ x 0 ) = ∫ d ϵ q ( ϵ ) ∏ t = 1 T q ( x t ∣ x 0 , ϵ ) = q ( x 1 ∣ x 0 ) ∏ t = 2 T q ( x t ∣ x t − 1 , x 0 ) (5) q(x_{1:T}\mid x_0)=\int d\epsilon\,q(\epsilon)\prod_{t=1}^{T}q(x_t\mid x_0,\epsilon)=q(x_1\mid x_0)\prod_{t=2}^{T}q(x_t\mid x_{t-1},x_0) \tag*{(5)} q ( x 1 : T ∣ x 0 ) = ∫ d ϵ q ( ϵ ) t = 1 ∏ T q ( x t ∣ x 0 , ϵ ) = q ( x 1 ∣ x 0 ) t = 2 ∏ T q ( x t ∣ x t − 1 , x 0 ) (5) is a degenerate Gaussian on R T d \mathbb{R}^{Td} R T d d d d 2 p θ ( x t − 1 ∣ x t ) = δ ( x t − 1 ∣ μ θ ( x t ) ) p_\theta(x_{t-1}\mid x_t)=\delta(x_{t-1}\mid\mu_\theta(x_t)) p θ ( x t − 1 ∣ x t ) = δ ( x t − 1 ∣ μ θ ( x t )) p ( x T ) = N ( x T ∣ 0 , I ) p(x_T)=\mathcal{N}(x_T\mid0,I) p ( x T ) = N ( x T ∣ 0 , I ) x ^ T ∼ N ( ⋅ ∣ 0 , I ) \hat{x}_T\sim\mathcal{N}(\cdot\mid0,I) x ^ T ∼ N ( ⋅ ∣ 0 , I ) x ^ t − 1 = μ θ ( x ^ t ) \hat{x}_{t-1}=\mu_\theta(\hat{x}_t) x ^ t − 1 = μ θ ( x ^ t ) t = T , … , 1 t=T,\ldots,1 t = T , … , 1 x ^ 0 \hat{x}_0 x ^ 0 sampler , and the resulting sequence x ^ T , … , x ^ 0 \hat{x}_T,\ldots,\hat{x}_0 x ^ T , … , x ^ 0 sampled chain (the hat distinguishes its states from those of the forward process). Each term of the objective equation (2) compares the generator p θ ( x t − 1 ∣ x t ) p_\theta(x_{t-1}\mid x_t) p θ ( x t − 1 ∣ x t ) q ( x t − 1 ∣ x t , x 0 ) q(x_{t-1}\mid x_t,x_0) q ( x t − 1 ∣ x t , x 0 ) q ( x t ∣ x 0 ) q(x_t\mid x_0) q ( x t ∣ x 0 ) q ( x t − 1 ∣ x t , x 0 ) q(x_{t-1}\mid x_t,x_0) q ( x t − 1 ∣ x t , x 0 )
Lemma 1. Let ( λ t ) t = 0 T (\lambda_t)_{t=0}^{T} ( λ t ) t = 0 T λ 0 = 0 \lambda_0=0 λ 0 = 0 x 1 , … , x T x_1,\ldots,x_T x 1 , … , x T
x t = ( 1 − λ t ) x 0 + λ t ϵ , ϵ ∼ N ( ⋅ ∣ 0 , I ) . (6) x_t=(1-\lambda_t)x_0+\lambda_t\epsilon,\qquad\epsilon\sim\mathcal{N}(\cdot\mid0,I). \tag*{(6)} x t = ( 1 − λ t ) x 0 + λ t ϵ , ϵ ∼ N ( ⋅ ∣ 0 , I ) . (6) Then, for t = 1 , … , T t=1,\ldots,T t = 1 , … , T
q ( x t ∣ x 0 ) = N ( x t ∣ μ ⃗ t , Σ ⃗ t ) and q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ ← t − 1 ( x t , x 0 ) ) , (7) q(x_t\mid x_0)=\mathcal{N}(x_t\mid\vec{\mu}_t,\vec{\Sigma}_t)\qquad\text{and}\qquad q(x_{t-1}\mid x_t,x_0)=\delta(x_{t-1}\mid\overleftarrow{\mu}_{t-1}(x_t,x_0)), \tag*{(7)} q ( x t ∣ x 0 ) = N ( x t ∣ μ t , Σ t ) and q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ t − 1 ( x t , x 0 )) , (7) where
μ ⃗ t = ( 1 − λ t ) x 0 , Σ ⃗ t = λ t 2 I , μ ← t − 1 ( x t , x 0 ) = ( 1 − λ t − 1 λ t ) x 0 + λ t − 1 λ t x t . (8) \vec{\mu}_t=(1-\lambda_t)x_0,\qquad\vec{\Sigma}_t=\lambda_t^2 I,\qquad\overleftarrow{\mu}_{t-1}(x_t,x_0)=\left(1-\frac{\lambda_{t-1}}{\lambda_t}\right)x_0+\frac{\lambda_{t-1}}{\lambda_t}x_t. \tag*{(8)} μ t = ( 1 − λ t ) x 0 , Σ t = λ t 2 I , μ t − 1 ( x t , x 0 ) = ( 1 − λ t λ t − 1 ) x 0 + λ t λ t − 1 x t . (8) The proofs are given in Appendix § 10 . By Lemma 1 and the definition of the generator, both q ( x t − 1 ∣ x t , x 0 ) q(x_{t-1}\mid x_t,x_0) q ( x t − 1 ∣ x t , x 0 ) p θ ( x t − 1 ∣ x t ) p_\theta(x_{t-1}\mid x_t) p θ ( x t − 1 ∣ x t ) (2) are delta functions. For the Degenerate Diffusion Model, each KL divergence in the objective is therefore ill-defined.
Spread Divergence Objective
To resolve the issue with KL divergence between degenerate distributions, we use the spread divergence. This smooths the deterministic point masses by convolving them with noise distributions, thereby yielding a finite, well-behaved divergence. Applying the spread divergence to each term of equation (2) yields our spread objective :
L ′ ( θ ) = ∑ t = 1 T K L [ q ~ ( y t − 1 ∣ x t , x 0 ) ∥ p ~ θ ( y t − 1 ∣ x t ) ] q ( x t ∣ x 0 ) q ( x 0 ) . (9) L'(\theta)=\sum_{t=1}^{T}\mathop{\mathrm{KL}}\left[\tilde{q}(y_{t-1}\mid x_t,x_0)\mathbin{\|}\tilde{p}_\theta(y_{t-1}\mid x_t)\right]q(x_t\mid x_0)q(x_0). \tag*{(9)} L ′ ( θ ) = t = 1 ∑ T KL [ q ~ ( y t − 1 ∣ x t , x 0 ) ∥ p ~ θ ( y t − 1 ∣ x t ) ] q ( x t ∣ x 0 ) q ( x 0 ) . (9) where the spread distributions q ~ \tilde{q} q ~ p ~ θ \tilde{p}_{\theta} p ~ θ k ( y t − 1 ∣ x t − 1 ) = N ( y t − 1 ∣ x t − 1 , σ t 2 I ) k(y_{t-1} \mid x_{t-1}) = \mathcal{N}(y_{t-1} \mid x_{t-1}, \sigma_t^2 I) k ( y t − 1 ∣ x t − 1 ) = N ( y t − 1 ∣ x t − 1 , σ t 2 I ) σ t \sigma_t σ t spread noise level and to σ t 2 \sigma_t^2 σ t 2 spread variance :
q ~ ( y t − 1 ∣ x t , x 0 ) = ∫ d x t − 1 k ( y t − 1 ∣ x t − 1 ) δ ( x t − 1 ∣ μ ← t − 1 ( x t , x 0 ) ) = N ( y t − 1 ∣ μ ← t − 1 ( x t , x 0 ) , σ t 2 I ) (10) \tilde{q}(y_{t-1} \mid x_t, x_0) = \int dx_{t-1}\, k(y_{t-1} \mid x_{t-1}) \delta(x_{t-1} \mid\overleftarrow{\mu}_{t-1}(x_t, x_0)) = \mathcal{N}(y_{t-1} \mid\overleftarrow{\mu}_{t-1}(x_t, x_0), \sigma_t^2 I) \tag*{(10)} q ~ ( y t − 1 ∣ x t , x 0 ) = ∫ d x t − 1 k ( y t − 1 ∣ x t − 1 ) δ ( x t − 1 ∣ μ t − 1 ( x t , x 0 )) = N ( y t − 1 ∣ μ t − 1 ( x t , x 0 ) , σ t 2 I ) (10) p ~ θ ( y t − 1 ∣ x t ) = ∫ d x t − 1 k ( y t − 1 ∣ x t − 1 ) δ ( x t − 1 ∣ μ θ ( x t ) ) = N ( y t − 1 ∣ μ θ ( x t ) , σ t 2 I ) . (11) \tilde{p}_{\theta}(y_{t-1} \mid x_t) = \int dx_{t-1}\, k(y_{t-1} \mid x_{t-1}) \delta(x_{t-1} \mid\mu_{\theta}(x_t)) = \mathcal{N}(y_{t-1} \mid\mu_{\theta}(x_t), \sigma_t^2 I). \tag*{(11)} p ~ θ ( y t − 1 ∣ x t ) = ∫ d x t − 1 k ( y t − 1 ∣ x t − 1 ) δ ( x t − 1 ∣ μ θ ( x t )) = N ( y t − 1 ∣ μ θ ( x t ) , σ t 2 I ) . (11) Both spread distributions are normal with covariance σ t 2 I \sigma_t^2 I σ t 2 I μ ← t − 1 ( x t , x 0 ) \overleftarrow{\mu}_{t-1}(x_t, x_0) μ t − 1 ( x t , x 0 ) μ θ ( x t ) \mu_{\theta}(x_t) μ θ ( x t )
L ′ ( θ ) = ∑ t = 1 T 1 2 σ t 2 ⟨ ∥ μ ← t − 1 ( x t , x 0 ) − μ θ ( x t ) ∥ 2 ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (12) L'(\theta) = \sum_{t=1}^{T} \frac{1}{2\sigma_t^2} \left\langle\left\lVert\overleftarrow{\mu}_{t-1}(x_t, x_0) - \mu_{\theta}(x_t) \right\rVert^2 \right\rangle_{q(x_t \mid x_0)q(x_0)}. \tag*{(12)} L ′ ( θ ) = t = 1 ∑ T 2 σ t 2 1 ⟨ μ t − 1 ( x t , x 0 ) − μ θ ( x t ) 2 ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (12) A natural alternative is to spread the joint distributions q ( x 0 : T ) q(x_{0:T}) q ( x 0 : T ) p θ ( x 0 : T ) p_{\theta}(x_{0:T}) p θ ( x 0 : T ) y t = x t + σ t η t y_t = x_t + \sigma_t\eta_t y t = x t + σ t η t η t ∼ N ( η t ∣ 0 , I ) \eta_t \sim\mathcal{N}(\eta_t \mid0, I) η t ∼ N ( η t ∣ 0 , I ) x t x_t x t x T x_T x T x t = μ θ ( T − t ) ( x T ) x_t = \mu_{\theta}^{(T-t)}(x_T) x t = μ θ ( T − t ) ( x T ) μ θ ( n ) \mu_{\theta}^{(n)} μ θ ( n ) n n n μ θ \mu_{\theta} μ θ
p ~ θ ( y 0 : T ) = ∫ d x T p ( x T ) ∏ t = 0 T N ( y t ∣ μ θ ( T − t ) ( x T ) , σ t 2 I ) . (13) \tilde{p}_{\theta}(y_{0:T}) = \int dx_T\, p(x_T) \prod_{t=0}^{T} \mathcal{N}(y_t \mid\mu_{\theta}^{(T-t)}(x_T), \sigma_t^2 I). \tag*{(13)} p ~ θ ( y 0 : T ) = ∫ d x T p ( x T ) t = 0 ∏ T N ( y t ∣ μ θ ( T − t ) ( x T ) , σ t 2 I ) . (13) Evaluating it would require integrating over x T x_T x T (9) conditions on a clean x t x_t x t q ( x t ∣ x 0 ) q(x_t \mid x_0) q ( x t ∣ x 0 ) x t − 1 x_{t-1} x t − 1 (11) and the per-step mean squared error equation (12) .
Objective Reparameterisation
In objective(12) , the network directly predicts the next state x t − 1 = μ θ ( x t ) x_{t-1} = \mu_{\theta}(x_t) x t − 1 = μ θ ( x t ) v t ( x 0 ) = x t − x 0 λ t v_t(x_0) = \frac{x_t-x_0}{\lambda_t} v t ( x 0 ) = λ t x t − x 0 x 0 = x t − λ t v t ( x 0 ) x_0 = x_t - \lambda_t v_t(x_0) x 0 = x t − λ t v t ( x 0 ) x 0 x_0 x 0 μ ← t − 1 ( x t , x 0 ) \overleftarrow{\mu}_{t-1}(x_t, x_0) μ t − 1 ( x t , x 0 ) μ ← t − 1 ( x t , x 0 ) = x t − Δ λ t v t ( x 0 ) \overleftarrow{\mu}_{t-1}(x_t, x_0) = x_t - \Delta\lambda_t v_t(x_0) μ t − 1 ( x t , x 0 ) = x t − Δ λ t v t ( x 0 ) Δ λ t = λ t − λ t − 1 \Delta\lambda_t = \lambda_t - \lambda_{t-1} Δ λ t = λ t − λ t − 1 μ θ ( x t ) = x t − Δ λ t v θ ( x t ) \mu_{\theta}(x_t) = x_t - \Delta\lambda_t v_{\theta}(x_t) μ θ ( x t ) = x t − Δ λ t v θ ( x t )
L ′ ( θ ) = ∑ t = 1 T ( Δ λ t ) 2 2 σ t 2 ⟨ ∥ v t ( x 0 ) − v θ ( x t ) ∥ 2 ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (14) L'(\theta) = \sum_{t=1}^{T} \frac{(\Delta\lambda_t)^2}{2\sigma_t^2} \left\langle\left\lVert v_t(x_0) - v_{\theta}(x_t) \right\rVert^2 \right\rangle_{q(x_t \mid x_0)q(x_0)}. \tag*{(14)} L ′ ( θ ) = t = 1 ∑ T 2 σ t 2 ( Δ λ t ) 2 ⟨ ∥ v t ( x 0 ) − v θ ( x t ) ∥ 2 ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (14) Using the definition of the noising process in equation(6), the velocity can also be written in terms of the data and the noise alone, v t ( x 0 ) = ϵ − x 0 v_t(x_0) = \epsilon- x_0 v t ( x 0 ) = ϵ − x 0 ( x 0 , ϵ ) (x_0, \epsilon) ( x 0 , ϵ ) t t t x t x_t x t x 0 x_0 x 0 ϵ \epsilon ϵ
The spread noise level enters objective(14) only through the weight ω t = ( Δ λ t ) 2 / ( 2 σ t 2 ) \omega_t = (\Delta\lambda_t)^2/(2\sigma_t^2) ω t = ( Δ λ t ) 2 / ( 2 σ t 2 ) v θ v_{\theta} v θ ( x t , t ) (x_t,t) ( x t , t ) ⟨ v t ( x 0 ) ⟩ q ( x 0 ∣ x t ) \langle v_t(x_0)\rangle_{q(x_0\mid x_t)} ⟨ v t ( x 0 ) ⟩ q ( x 0 ∣ x t ) [14 ] ). The minimiser therefore does not depend on σ t \sigma_t σ t σ t \sigma_t σ t ω t \omega_t ω t σ t 2 = ( Δ λ t ) 2 / ( 2 ω t ) \sigma_t^2 = (\Delta\lambda_t)^2/(2\omega_t) σ t 2 = ( Δ λ t ) 2 / ( 2 ω t ) [14 ] ), therefore corresponds to a spread divergence with a different spread noise level at each step. In Section 3.2 we show that each such objective minimises a divergence to the backward distribution q ( x t − 1 ∣ x t ) q(x_{t-1} \mid x_t) q ( x t − 1 ∣ x t )
What the Spread Objective Learns
Each term of the spread objective equation (9) compares the generator with the data-conditioned backward distribution q ( x t − 1 ∣ x t , x 0 ) q(x_{t-1} \mid x_t, x_0) q ( x t − 1 ∣ x t , x 0 ) x 0 x_0 x 0 x t x_t x t backward distribution
q ( x t − 1 ∣ x t ) = ∫ d x 0 q ( x 0 ∣ x t ) q ( x t − 1 ∣ x t , x 0 ) , (15) q(x_{t-1} \mid x_t) = \int dx_0\,q(x_0 \mid x_t)q(x_{t-1} \mid x_t,x_0), \tag*{(15)} q ( x t − 1 ∣ x t ) = ∫ d x 0 q ( x 0 ∣ x t ) q ( x t − 1 ∣ x t , x 0 ) , (15) which does not depend on x 0 x_0 x 0 p θ ( x t − 1 ∣ x t ) = q ( x t − 1 ∣ x t ) p_\theta(x_{t-1} \mid x_t) = q(x_{t-1} \mid x_t) p θ ( x t − 1 ∣ x t ) = q ( x t − 1 ∣ x t ) t t t p ( x T ) = q ( x T ) p(x_T) = q(x_T) p ( x T ) = q ( x T ) p θ ( x t − 1 ) = ∫ d x t q ( x t − 1 ∣ x t ) q ( x t ) = q ( x t − 1 ) p_\theta(x_{t-1}) = \int dx_t\,q(x_{t-1} \mid x_t)q(x_t) = q(x_{t-1}) p θ ( x t − 1 ) = ∫ d x t q ( x t − 1 ∣ x t ) q ( x t ) = q ( x t − 1 ) t t t p θ ( x 0 ) = q ( x 0 ) p_\theta(x_0) = q(x_0) p θ ( x 0 ) = q ( x 0 ) L ′ L' L ′
The spread of the backward distribution q ( x t − 1 ∣ x t ) q(x_{t-1} \mid x_t) q ( x t − 1 ∣ x t )
q ~ ( y t − 1 ∣ x t ) = ∫ d x t − 1 k ( y t − 1 ∣ x t − 1 ) q ( x t − 1 ∣ x t ) = ∫ d x 0 q ( x 0 ∣ x t ) q ~ ( y t − 1 ∣ x t , x 0 ) . (16) \widetilde{q}(y_{t-1} \mid x_t) = \int dx_{t-1}\,k(y_{t-1} \mid x_{t-1})q(x_{t-1} \mid x_t) = \int dx_0\,q(x_0 \mid x_t)\widetilde{q}(y_{t-1} \mid x_t,x_0). \tag*{(16)} q ( y t − 1 ∣ x t ) = ∫ d x t − 1 k ( y t − 1 ∣ x t − 1 ) q ( x t − 1 ∣ x t ) = ∫ d x 0 q ( x 0 ∣ x t ) q ( y t − 1 ∣ x t , x 0 ) . (16) Then, the spread divergence between the backward distribution and the generator becomes:
D ( θ ) = ∑ t = 1 T ⟨ K L [ q ~ ( y t − 1 ∣ x t ) ∥ p ~ θ ( y t − 1 ∣ x t ) ] ⟩ q ( x t ) , (17) \mathcal{D}(\theta) = \sum_{t=1}^{T}\left\langle\mathrm{KL}[\widetilde{q}(y_{t-1} \mid x_t) \mathbin{\|} \widetilde{p}_\theta(y_{t-1} \mid x_t)]\right\rangle_{q(x_t)}, \tag*{(17)} D ( θ ) = t = 1 ∑ T ⟨ KL [ q ( y t − 1 ∣ x t ) ∥ p θ ( y t − 1 ∣ x t )] ⟩ q ( x t ) , (17) which, following the properties established in § 2.2 , is zero if and only if p θ ( x t − 1 ∣ x t ) = q ( x t − 1 ∣ x t ) p_\theta(x_{t-1} \mid x_t) = q(x_{t-1} \mid x_t) p θ ( x t − 1 ∣ x t ) = q ( x t − 1 ∣ x t ) t t t x t x_t x t
Lemma 2 (Decomposition of the spread objective). For every θ \theta θ
L ′ ( θ ) = D ( θ ) + C , (18) L'(\theta) = \mathcal{D}(\theta) + C, \tag*{(18)} L ′ ( θ ) = D ( θ ) + C , (18) where C C C θ \theta θ
The proof is given in Appendix § 11 . The divergence D ( θ ) \mathcal{D}(\theta) D ( θ ) (16) requires the posterior q ( x 0 ∣ x t ) q(x_0 \mid x_t) q ( x 0 ∣ x t ) L ′ L' L ′ ( x 0 , x t ) (x_0,x_t) ( x 0 , x t ) C C C θ \theta θ L ′ L' L ′
Lemma 2 holds for any σ t > 0 \sigma_t > 0 σ t > 0 σ t \sigma_t σ t § 3.1.1 ), every such weighting, including the heuristic weightings used in practice such as that of EDM [14 ] , minimises a spread divergence to the backward distribution. Within our framework these weightings are therefore principled: they correspond to different choices of the spread and all share the same minimiser.
Convergence to the Data Distribution
Since the sampler is deterministic given x ^ T \hat{x}_T x ^ T q ( x t − 1 ∣ x t ) q(x_{t-1} \mid x_t) q ( x t − 1 ∣ x t ) § 3.2 ) which is a mixture distribution over datapoints. We now show that, at the optimum of the spread objective, generator samples x ^ 0 \hat{x}_0 x ^ 0 T → ∞ T \to\infty T → ∞
We consider a finite training set of N ≥ 2 N \ge2 N ≥ 2 q ( x 0 ) = 1 N ∑ n = 1 N δ ( x 0 ∣ x 0 n ) q(x_0) = \frac{1}{N}\sum_{n=1}^{N}\delta(x_0 \mid x_0^n) q ( x 0 ) = N 1 ∑ n = 1 N δ ( x 0 ∣ x 0 n ) § 2.1 . The forward marginals are then mixtures of Gaussians,
q t ( x t ) : = q ( x t ) = 1 N ∑ n = 1 N N ( x t ∣ ( 1 − λ t ) x 0 n , λ t 2 I ) , (19) q_t(x_t) := q(x_t) = \frac{1}{N}\sum_{n=1}^{N}\mathcal{N}\left(x_t \mid(1-\lambda_t)x_0^n,\lambda_t^2 I\right), \tag*{(19)} q t ( x t ) := q ( x t ) = N 1 n = 1 ∑ N N ( x t ∣ ( 1 − λ t ) x 0 n , λ t 2 I ) , (19) and the posterior over training points is
q ( x 0 n ∣ x t ) = w n t ( x t ) , w n t ( x ) = exp { − ∥ x − ( 1 − λ t ) x 0 n ∥ 2 / ( 2 λ t 2 ) } ∑ k = 1 N exp { − ∥ x − ( 1 − λ t ) x 0 k ∥ 2 / ( 2 λ t 2 ) } . (20) q(x_0^n \mid x_t) = w_n^t(x_t), \qquad w_n^t(x) = \frac{\exp\left\{-\|x-(1-\lambda_t)x_0^n\|^2/(2\lambda_t^2)\right\}}{\sum_{k=1}^{N}\exp\left\{-\|x-(1-\lambda_t)x_0^k\|^2/(2\lambda_t^2)\right\}}. \tag*{(20)} q ( x 0 n ∣ x t ) = w n t ( x t ) , w n t ( x ) = ∑ k = 1 N exp { − ∥ x − ( 1 − λ t ) x 0 k ∥ 2 / ( 2 λ t 2 ) } exp { − ∥ x − ( 1 − λ t ) x 0 n ∥ 2 / ( 2 λ t 2 ) } . (20) Substituting this into equation (15) and using Lemma 1, the backward distribution is a mixture of deltas, one per training point:
q ( x t − 1 ∣ x t ) = ∑ n = 1 N w n t ( x t ) δ ( x t − 1 ∣ μ ˉ t − 1 ( x t , x 0 n ) ) . (21) q(x_{t-1}\mid x_t)=\sum_{n=1}^{N}w_n^t(x_t)\,\delta\left(x_{t-1}\mid\bar{\mu}_{t-1}(x_t,x_0^n)\right). \tag*{(21)} q ( x t − 1 ∣ x t ) = n = 1 ∑ N w n t ( x t ) δ ( x t − 1 ∣ μ ˉ t − 1 ( x t , x 0 n ) ) . (21) At the optimum of the spread objective, the generator outputs the mean of this mixture. Each term of equation (12) is a mean squared error in μ θ ( x t ) \mu_\theta(x_t) μ θ ( x t )
μ t ∗ ( x ) = ∑ n = 1 N w n t ( x ) μ ˉ t − 1 ( x , x 0 n ) = μ ˉ t − 1 ( x , m t ( x ) ) , m t ( x ) = ∑ n = 1 N w n t ( x ) x 0 n , (22) \mu_t^*(x)=\sum_{n=1}^{N}w_n^t(x)\,\bar{\mu}_{t-1}(x,x_0^n)=\bar{\mu}_{t-1}(x,m_t(x)),\qquad m_t(x)=\sum_{n=1}^{N}w_n^t(x)x_0^n, \tag*{(22)} μ t ∗ ( x ) = n = 1 ∑ N w n t ( x ) μ ˉ t − 1 ( x , x 0 n ) = μ ˉ t − 1 ( x , m t ( x )) , m t ( x ) = n = 1 ∑ N w n t ( x ) x 0 n , (22) where the second equality holds because μ ˉ t − 1 \bar{\mu}_{t-1} μ ˉ t − 1 x 0 x_0 x 0 m t ( x ) m_t(x) m t ( x ) μ θ \mu_\theta μ θ § 3.1.1 , it corresponds to v t ∗ ( x ) = ( x − m t ( x ) ) / λ t v_t^*(x)=(x-m_t(x))/\lambda_t v t ∗ ( x ) = ( x − m t ( x )) / λ t (21) by a delta at its mean introduces an error at every step, but we show that its accumulated effect vanishes as T → ∞ T\to\infty T → ∞
Theorem 1 (Weak convergence). Let q ( x 0 ) q(x_0) q ( x 0 ) N ≥ 2 N\geq2 N ≥ 2 x 0 1 , … , x 0 N ∈ R d x_0^1,\ldots,x_0^N\in\mathbb{R}^d x 0 1 , … , x 0 N ∈ R d T T T § 3 , and assume that the largest step size vanishes, max t Δ λ t → 0 \max_t\Delta\lambda_t\to0 max t Δ λ t → 0 T → ∞ T\to\infty T → ∞ x ^ T , … , x ^ 0 \hat{x}_T,\ldots,\hat{x}_0 x ^ T , … , x ^ 0 μ θ ( x ) = μ t ∗ ( x ) \mu_\theta(x)=\mu_t^*(x) μ θ ( x ) = μ t ∗ ( x ) t t t x ∈ R d x\in\mathbb{R}^d x ∈ R d γ T > 0 \gamma_T>0 γ T > 0 γ T → 0 \gamma_T\to0 γ T → 0 T → ∞ T\to\infty T → ∞ x 0 m x_0^m x 0 m
lim T → ∞ P ( ∥ x ^ 0 − x 0 m ∥ ≤ γ T ) = 1 N . (23) \lim_{T\to\infty}P\left(\lVert\hat{x}_0-x_0^m\rVert\leq\gamma_T\right)=\frac{1}{N}. \tag*{(23)} T → ∞ lim P ( ∥ x ^ 0 − x 0 m ∥ ≤ γ T ) = N 1 . (23) Consequently, the distribution of the generated sample x ^ 0 \hat{x}_0 x ^ 0 q ( x 0 ) q(x_0) q ( x 0 )
The theorem says that, starting from Gaussian noise, the generated sample x ^ 0 \hat{x}_0 x ^ 0 γ T \gamma_T γ T x 0 m x_0^m x 0 m 1 N \frac{1}{N} N 1 m m m N N N x ^ 0 \hat{x}_0 x ^ 0 γ T \gamma_T γ T 1 N \frac{1}{N} N 1 q ( x 0 ) q(x_0) q ( x 0 )
Proof sketch. We split the trajectory into two regimes, high and low noise levels. At high noise, we compare the sampled chain with a reference chain that starts from the same noise but where, instead of averaging over the posterior q ( x 0 ∣ x t ) q(x_0\mid x_t) q ( x 0 ∣ x t ) q t q_t q t ( Δ λ t ) 2 (\Delta\lambda_t)^2 ( Δ λ t ) 2 T → ∞ T\to\infty T → ∞ Lemma 4 ).
At low noise, the posterior concentrates on a single training point. Each data point x 0 m x_0^m x 0 m q t q_t q t ( 1 − λ t ) x 0 m (1-\lambda_t)x_0^m ( 1 − λ t ) x 0 m x 0 m x_0^m x 0 m λ t → 0 \lambda_t\to0 λ t → 0 t → 0 t\to0 t → 0 x 0 m x_0^m x 0 m λ 1 \lambda_1 λ 1 Lemma 5 ). Since the reference chain has marginals q t q_t q t 1 N \frac{1}{N} N 1 τ \tau τ τ \tau τ 1 N \frac{1}{N} N 1 § 12 .
Remarks. The theorem holds for any choice of the spread noise levels σ t \sigma_t σ t μ t ∗ \mu_t^* μ t ∗ § 3.1.1 ) for sampling. The result assumes the exact optimum on a finite dataset, for which the sampler reproduces the training points. It is therefore a consistency result for the objective and does not describe a trained network’s generalisation. Finally, the proof works purely in discrete-time, without relying on any continuous-time methods.
Connection to Flow Matching
While the forward path x t = ( 1 − λ t ) x 0 + λ t ϵ x_t = (1-\lambda_t)x_0 + \lambda_t\epsilon x t = ( 1 − λ t ) x 0 + λ t ϵ § 3 is the interpolant used by flow matching, we derived our objective and sampler solely from the variational bound. We now show that our objective, its minimiser and the resulting sampler are equivalent to those of flow matching.
We consider the standard conditional flow matching loss [18 ]
L C F M ( θ ) = ⟨ ∥ u s ( x s ∣ x 0 ) − u θ ( x s , s ) ∥ 2 ⟩ U ( s ) q ( x s ∣ x 0 ) q ( x 0 ) (24) \mathcal{L}_{\mathrm{CFM}}(\theta) = \left\langle\lVert u_s(x_s \mid x_0) - u_\theta(x_s,s) \rVert^2 \right\rangle_{U(s)\,q(x_s\mid x_0)\,q(x_0)} \tag*{(24)} L CFM ( θ ) = ⟨ ∥ u s ( x s ∣ x 0 ) − u θ ( x s , s ) ∥ 2 ⟩ U ( s ) q ( x s ∣ x 0 ) q ( x 0 ) (24) where U ( s ) U(s) U ( s ) [ 0 , 1 ] [0,1] [ 0 , 1 ] u θ u_\theta u θ u s ( x s ∣ x 0 ) = d x s d s u_s(x_s \mid x_0) = \frac{dx_s}{ds} u s ( x s ∣ x 0 ) = d s d x s s s s U ( s ) U(s) U ( s ) [8 ] correspond to a weighting of this loss over s s s § 3.1.1 ).
Let λ : [ 0 , 1 ] → [ 0 , 1 ] \lambda: [0,1] \to[0,1] λ : [ 0 , 1 ] → [ 0 , 1 ] λ ′ ( s ) > 0 \lambda'(s) > 0 λ ′ ( s ) > 0 λ ( 0 ) = 0 \lambda(0) = 0 λ ( 0 ) = 0 λ ( 1 ) = 1 \lambda(1) = 1 λ ( 1 ) = 1 x s = ( 1 − λ ( s ) ) x 0 + λ ( s ) ϵ x_s = (1-\lambda(s))x_0 + \lambda(s)\epsilon x s = ( 1 − λ ( s )) x 0 + λ ( s ) ϵ s ∈ [ 0 , 1 ] s \in[0,1] s ∈ [ 0 , 1 ] s = 0 s=0 s = 0 s = 1 s=1 s = 1 3 x s x_s x s
u s ( x s ∣ x 0 ) = d ( 1 − λ ( s ) ) d s x 0 + d λ ( s ) d s ϵ = λ ′ ( s ) ( ϵ − x 0 ) = λ ′ ( s ) v s ( x 0 ) , (25) u_s(x_s \mid x_0) = \frac{d(1-\lambda(s))}{ds}x_0 + \frac{d\lambda(s)}{ds}\epsilon= \lambda'(s)(\epsilon-x_0) = \lambda'(s)v_s(x_0), \tag*{(25)} u s ( x s ∣ x 0 ) = d s d ( 1 − λ ( s )) x 0 + d s d λ ( s ) ϵ = λ ′ ( s ) ( ϵ − x 0 ) = λ ′ ( s ) v s ( x 0 ) , (25) with v s ( x 0 ) = ϵ − x 0 v_s(x_0) = \epsilon-x_0 v s ( x 0 ) = ϵ − x 0 § 3.1.1 .4 § 3.1.1 , u θ ( x s , s ) : = λ ′ ( s ) v θ ( x s , s ) u_\theta(x_s,s) := \lambda'(s)v_\theta(x_s,s) u θ ( x s , s ) := λ ′ ( s ) v θ ( x s , s )
L C F M ( θ ) = ∫ 0 1 λ ′ ( s ) 2 ⟨ ∥ v s ( x 0 ) − v θ ( x s , s ) ∥ 2 ⟩ q ( x s ∣ x 0 ) q ( x 0 ) ⏟ = : ℓ ( s ) d s . (26) \mathcal{L}_{\mathrm{CFM}}(\theta) = \int_0^1 \lambda'(s)^2 \underbrace{\left\langle\lVert v_s(x_0)-v_\theta(x_s,s) \rVert^2 \right\rangle_{q(x_s\mid x_0)q(x_0)}}_{=:\ell(s)}\,ds. \tag*{(26)} L CFM ( θ ) = ∫ 0 1 λ ′ ( s ) 2 =: ℓ ( s ) ⟨ ∥ v s ( x 0 ) − v θ ( x s , s ) ∥ 2 ⟩ q ( x s ∣ x 0 ) q ( x 0 ) d s . (26) To relate equation (14) to equation (26) , we place our discrete steps on the time axis, s t = t / T s_t=t/T s t = t / T λ t = λ ( s t ) \lambda_t=\lambda(s_t) λ t = λ ( s t ) v θ ( x t ) = v θ ( x t , s t ) v_\theta(x_t)=v_\theta(x_t,s_t) v θ ( x t ) = v θ ( x t , s t ) Δ λ t \Delta\lambda_t Δ λ t λ ′ \lambda' λ ′ s s s h > 0 h>0 h > 0 s − h ∈ [ 0 , 1 ] s-h\in[0,1] s − h ∈ [ 0 , 1 ] λ ( s − h ) = λ ( s ) − h λ ′ ( s ) + O ( h 2 ) \lambda(s-h)=\lambda(s)-h\lambda'(s)+O(h^2) λ ( s − h ) = λ ( s ) − h λ ′ ( s ) + O ( h 2 ) λ ′ ′ \lambda'' λ ′′ [ 0 , 1 ] [0,1] [ 0 , 1 ] O ( h 2 ) O(h^2) O ( h 2 ) s s s s = s t s=s_t s = s t h = 1 / T h=1/T h = 1/ T s − h = ( t − 1 ) / T = s t − 1 s-h=(t-1)/T=s_{t-1} s − h = ( t − 1 ) / T = s t − 1
Δ λ t = λ ( s t ) − λ ( s t − 1 ) = λ ′ ( s t ) T + O ( T − 2 ) , (27) \Delta\lambda_t = \lambda(s_t)-\lambda(s_{t-1}) = \frac{\lambda'(s_t)}{T}+O(T^{-2}), \tag*{(27)} Δ λ t = λ ( s t ) − λ ( s t − 1 ) = T λ ′ ( s t ) + O ( T − 2 ) , (27) where O ( T − 2 ) O(T^{-2}) O ( T − 2 ) t t t
We now compare the two methods across three aspects: objective, minimiser, and sampler. The comparison holds for any schedule λ \lambda λ λ ( s ) = s \lambda(s)=s λ ( s ) = s Δ λ t = 1 / T \Delta\lambda_t=1/T Δ λ t = 1/ T O ( ⋅ ) O(\cdot) O ( ⋅ )
Objective. Since v t ( x 0 ) = ϵ − x 0 = v s t ( x 0 ) v_t(x_0)=\epsilon-x_0=v_{s_t}(x_0) v t ( x 0 ) = ϵ − x 0 = v s t ( x 0 ) σ t = σ \sigma_t=\sigma σ t = σ (14) gives
2 σ 2 T L ′ ( θ ) = T ∑ t = 1 T ( Δ λ t ) 2 ℓ ( s t ) = 1 T ∑ t = 1 T λ ′ ( s t ) 2 ℓ ( s t ) + O ( T − 1 ) . (28) 2\sigma^2 T L'(\theta) = T\sum_{t=1}^{T}(\Delta\lambda_t)^2\ell(s_t) = \frac{1}{T}\sum_{t=1}^{T}\lambda'(s_t)^2\ell(s_t)+O(T^{-1}). \tag*{(28)} 2 σ 2 T L ′ ( θ ) = T t = 1 ∑ T ( Δ λ t ) 2 ℓ ( s t ) = T 1 t = 1 ∑ T λ ′ ( s t ) 2 ℓ ( s t ) + O ( T − 1 ) . (28) Here we assume that v θ v_\theta v θ ( x , s ) (x,s) ( x , s ) x x x s s s ∥ v θ ( x , s ) ∥ ≤ A + B ∥ x ∥ k \lVert v_\theta(x,s)\rVert\le A+B\lVert x\rVert^k ∥ v θ ( x , s )∥ ≤ A + B ∥ x ∥ k k ≥ 1 k\ge1 k ≥ 1 x x x s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] q ( x 0 ) q(x_0) q ( x 0 ) x x x [2 , 5 ] ). The second holds for any finite dataset. Under these assumptions ℓ \ell ℓ [ 0 , 1 ] [0,1] [ 0 , 1 ] (27) , which gives ( Δ λ t ) 2 = λ ′ ( s t ) 2 / T 2 + O ( T − 3 ) (\Delta\lambda_t)^2 = \lambda'(s_t)^2/T^2 + O(T^{-3}) ( Δ λ t ) 2 = λ ′ ( s t ) 2 / T 2 + O ( T − 3 ) t t t λ ′ \lambda' λ ′ [ 0 , 1 ] [0,1] [ 0 , 1 ] ℓ \ell ℓ ℓ ( s t ) \ell(s_t) ℓ ( s t ) O ( T − 3 ) O(T^{-3}) O ( T − 3 ) T T T T T T O ( T − 1 ) O(T^{-1}) O ( T − 1 ) ℓ \ell ℓ ∫ 0 1 λ ′ ( s ) 2 ℓ ( s ) d s \int_0^1 \lambda'(s)^2\ell(s)\,ds ∫ 0 1 λ ′ ( s ) 2 ℓ ( s ) d s 2 σ 2 T L ′ ( θ ) → L C F M ( θ ) 2\sigma^2T L'(\theta) \to L_{\mathrm{CFM}}(\theta) 2 σ 2 T L ′ ( θ ) → L CFM ( θ ) T → ∞ T \to\infty T → ∞ σ 2 = 1 2 T \sigma^2 = \frac{1}{2T} σ 2 = 2 T 1 L ′ ( θ ) → L C F M ( θ ) L'(\theta) \to L_{\mathrm{CFM}}(\theta) L ′ ( θ ) → L CFM ( θ )
Minimiser. For any T T T L ′ L' L ′ s t s_t s t v ∗ ( ⋅ , s t ) v^*(\cdot,s_t) v ∗ ( ⋅ , s t ) v ∗ ( x , s ) = ⟨ ϵ − x 0 ⟩ q ( x 0 , ϵ ∣ x s = x ) v^*(x,s) = \langle\epsilon- x_0\rangle_{q(x_0,\epsilon\mid x_s=x)} v ∗ ( x , s ) = ⟨ ϵ − x 0 ⟩ q ( x 0 , ϵ ∣ x s = x ) L C F M L_{\mathrm{CFM}} L CFM s s s
Sampler. The generator mean μ θ ( x t ) = x t − Δ λ t v θ ( x t , s t ) \mu_\theta(x_t) = x_t - \Delta\lambda_t v_\theta(x_t,s_t) μ θ ( x t ) = x t − Δ λ t v θ ( x t , s t ) § 3.1.1 ) is exactly an Euler step of the ODE d x / d λ = v θ dx/d\lambda= v_\theta d x / d λ = v θ λ \lambda λ (27) and then u θ ( x , s ) = λ ′ ( s ) v θ ( x , s ) u_\theta(x,s) = \lambda'(s)v_\theta(x,s) u θ ( x , s ) = λ ′ ( s ) v θ ( x , s )
μ θ ( x t ) = x t − 1 T λ ′ ( s t ) v θ ( x t , s t ) + O ( T − 2 ) = x t − 1 T u θ ( x t , s t ) + O ( T − 2 ) . (29) \begin{aligned}
\mu_\theta(x_t) &= x_t - \frac{1}{T}\lambda'(s_t)v_\theta(x_t,s_t) + O(T^{-2}) \\
&= x_t - \frac{1}{T}u_\theta(x_t,s_t) + O(T^{-2}). \tag*{(29)}
\end{aligned} μ θ ( x t ) = x t − T 1 λ ′ ( s t ) v θ ( x t , s t ) + O ( T − 2 ) = x t − T 1 u θ ( x t , s t ) + O ( T − 2 ) . (29) That is, an Euler step of size 1 / T 1/T 1/ T d x / d s = u θ dx/ds = u_\theta d x / d s = u θ T → ∞ T \to\infty T → ∞
Hence, for σ 2 = 1 2 T \sigma^2 = \frac{1}{2T} σ 2 = 2 T 1 § 3.2 and § 3.3 apply directly to the flow matching loss and its weightings. For the default schedule λ ( s ) = s \lambda(s) = s λ ( s ) = s T T T L ′ ( θ ) = 1 T ∑ t = 1 T ℓ ( s t ) L'(\theta) = \frac{1}{T}\sum_{t=1}^{T}\ell(s_t) L ′ ( θ ) = T 1 ∑ t = 1 T ℓ ( s t )
Related Work
DDIM (Song et al., 2021a) with zero variance is the diffusion model closest to ours. Like our method, it samples with a deterministic generator, and its forward process reuses a single noise sample across all timesteps, though with a different noise schedule. The key difference is how the deterministic generator is obtained. DDIM trains a stochastic per-step generator and sets the variance to zero only at sampling time, so the generator assumed by the training objective is not the one used to produce samples. We instead apply spread divergence (Zhang et al., 2020) to each step of the variational bound, which gives a well-defined training objective for the deterministic generator itself. As a result, the same generator is used for both training and sampling.
Flow matching [18 ] (Liu et al. 2023) uses exactly our forward path, the straight line between the data point and the noise sample, but trains the generator with a regression loss rather than a variational objective. Gao et al. [9 ] show that, for such paths, flow matching and DDIM use the same sampler, and that their training losses differ only in how the network is parameterised and how the timesteps are weighted. Our model recovers this loss and sampler from a single variational objective (§ 4 ), and the difference in weighting corresponds to a different choice of spread (§ 3.1.1 ).
We also show that the optimum does not depend on the spread noise level, which only sets the weight ω t \omega_t ω t § 3.1.1 ). This relates to Kingma & Gao [15 ] , who show that weighted diffusion losses can be read as an ELBO of noise-perturbed data, provided that the forward process and the generator are Gaussian and the weighting is monotonic. In our framework, any fixed positive weighting ω t \omega_t ω t
Variational Flow Matching [7 ] also gives flow matching a variational interpretation, but in continuous time and of a different kind: the velocity field is parameterised through a variational approximation of the posterior q ( x 0 ∣ x t ) q(x_0 \mid x_t) q ( x 0 ∣ x t )
Under the variational view, we also prove convergence of the deterministic sampler to the data distribution. Convergence has already been shown in the continuous-time setting of flow matching (Benton et al., [2 ] ) and probability-flow ODEs (Chen et al., [5 ] ; Li et al., [17 ] ; Gao & Zhu, [10 ] ). Our proof instead works directly in discrete time, without the continuous-time arguments on which these results rely. It holds at the exact optimum on a finite training set, where the sampler reproduces the training points. This agrees with the memorisation of the training data observed for diffusion models at the empirical optimum (Gu et al., [11 ] ; Biroli et al., [3 ] ).
Conclusion
While deterministic samplers in diffusion models have largely fallen outside the variational framework, we have defined a deterministic model, the Degenerate Diffusion Model, and shown that it can be trained with a suitable variational method. Applying the spread divergence at each step, we derived a well-defined objective that equals, up to a parameter-independent constant, the spread divergence between the generator and the backward distribution. Its minimiser, the mean of the backward distribution, does not depend on the spread variance, so any fixed positive weighting of the per-step loss terms is itself a spread divergence. We proved, in discrete time and without continuous-time arguments, that for a finite training set, the deterministic sampler at the optimum converges weakly to the data distribution as the number of steps tends to infinity. Finally, although derived from the variational bound alone, the Degenerate Diffusion Model is equivalent to a discrete-time implementation of flow matching for a specific choice of spread, exactly so for the linear schedule, which gives the flow matching loss and its weightings a variational interpretation.
Acknowledgments
This work was supported by the Engineering and Physical Sciences Research Council and AI Hub in Generative Models [grant numbers EP/S021566/1, EP/Y028805/1, UKRI5028].
Use of Large Language Models
First, for Theorem 1, the authors formulated the result and devised the proof strategy and its key arguments, and Claude helped turn this informal argument into the detailed formal proof given in Appendix § 12 . All research ideas, results and claims are the authors’ own. The authors checked every step of the proof and take full responsibility for the content of the paper.
Standard Diffusion Bound
Lemma 3 (Standard diffusion bound). For the noise model q ( x 1 : T ∣ x 0 ) = ∏ t = 1 T q ( x t ∣ x t − 1 , x 0 ) q(x_{1:T} \mid x_0) = \prod_{t=1}^{T} q(x_t \mid x_{t-1},x_0) q ( x 1 : T ∣ x 0 ) = ∏ t = 1 T q ( x t ∣ x t − 1 , x 0 ) p θ ( x 0 : T ) = p ( x T ) ∏ t = 1 T p θ ( x t − 1 ∣ x t ) p_\theta(x_{0:T}) = p(x_T)\prod_{t=1}^{T}p_\theta(x_{t-1} \mid x_t) p θ ( x 0 : T ) = p ( x T ) ∏ t = 1 T p θ ( x t − 1 ∣ x t ) § 2.1 , the bound equation (1) holds, with C = ⟨ KL [ q ( x T ∣ x 0 ) ∥ p ( x T ) ] ⟩ q ( x 0 ) C = \left\langle\operatorname{KL}[q(x_T \mid x_0) \mathbin\Vert p(x_T)] \right\rangle_{q(x_0)} C = ⟨ KL [ q ( x T ∣ x 0 ) ∥ p ( x T )] ⟩ q ( x 0 ) θ \theta θ
Proof. Fix x 0 x_0 x 0 p θ ( x 0 ) = ∫ d x 1 : T p θ ( x 0 : T ) p_\theta(x_0) = \int\mathrm{d}x_{1:T}\,p_\theta(x_{0:T}) p θ ( x 0 ) = ∫ d x 1 : T p θ ( x 0 : T )
log p θ ( x 0 ) = log ⟨ p θ ( x 0 : T ) q ( x 1 : T ∣ x 0 ) ⟩ q ( x 1 : T ∣ x 0 ) ≥ ⟨ log p θ ( x 0 : T ) q ( x 1 : T ∣ x 0 ) ⟩ q ( x 1 : T ∣ x 0 ) . (30) \log p_\theta(x_0) = \log\left\langle\frac{p_\theta(x_{0:T})}{q(x_{1:T} \mid x_0)} \right\rangle_{q(x_{1:T} \mid x_0)} \ge\left\langle\log\frac{p_\theta(x_{0:T})}{q(x_{1:T} \mid x_0)} \right\rangle_{q(x_{1:T} \mid x_0)} . \tag*{(30)} log p θ ( x 0 ) = log ⟨ q ( x 1 : T ∣ x 0 ) p θ ( x 0 : T ) ⟩ q ( x 1 : T ∣ x 0 ) ≥ ⟨ log q ( x 1 : T ∣ x 0 ) p θ ( x 0 : T ) ⟩ q ( x 1 : T ∣ x 0 ) . (30) Because the noise model is Markov given x 0 x_0 x 0 q ( x 1 : T ∣ x 0 ) = q ( x T ∣ x 0 ) ∏ t = 2 T q ( x t − 1 ∣ x t , x 0 ) q(x_{1:T} \mid x_0) = q(x_T \mid x_0)\prod_{t=2}^{T}q(x_{t-1} \mid x_t,x_0) q ( x 1 : T ∣ x 0 ) = q ( x T ∣ x 0 ) ∏ t = 2 T q ( x t − 1 ∣ x t , x 0 ) p θ ( x 0 : T ) = p ( x T ) p θ ( x 0 ∣ x 1 ) ∏ t = 2 T p θ ( x t − 1 ∣ x t ) p_\theta(x_{0:T}) = p(x_T)p_\theta(x_0 \mid x_1)\prod_{t=2}^{T}p_\theta(x_{t-1} \mid x_t) p θ ( x 0 : T ) = p ( x T ) p θ ( x 0 ∣ x 1 ) ∏ t = 2 T p θ ( x t − 1 ∣ x t )
− log p θ ( x 0 ) ≤ ∑ t = 2 T ⟨ KL [ q ( x t − 1 ∣ x t , x 0 ) ∥ p θ ( x t − 1 ∣ x t ) ] ⟩ q ( x t ∣ x 0 ) + KL [ q ( x T ∣ x 0 ) ∥ p ( x T ) ] − ⟨ log p θ ( x 0 ∣ x 1 ) ⟩ q ( x 1 ∣ x 0 ) . (31) -\log p_\theta(x_0) \le\sum_{t=2}^{T}\left\langle\operatorname{KL}[q(x_{t-1} \mid x_t,x_0) \mathbin\Vert p_\theta(x_{t-1} \mid x_t)] \right\rangle_{q(x_t \mid x_0)}
+ \operatorname{KL}[q(x_T \mid x_0) \mathbin\Vert p(x_T)] - \left\langle\log p_\theta(x_0 \mid x_1) \right\rangle_{q(x_1 \mid x_0)} . \tag*{(31)} − log p θ ( x 0 ) ≤ t = 2 ∑ T ⟨ KL [ q ( x t − 1 ∣ x t , x 0 ) ∥ p θ ( x t − 1 ∣ x t )] ⟩ q ( x t ∣ x 0 ) + KL [ q ( x T ∣ x 0 ) ∥ p ( x T )] − ⟨ log p θ ( x 0 ∣ x 1 ) ⟩ q ( x 1 ∣ x 0 ) . (31) Averaging both sides over q ( x 0 ) q(x_0) q ( x 0 ) C C C C C C θ \theta θ q q q p ( x T ) p(x_T) p ( x T )
Proof of Lemma 1 (Forward Probabilities)
Lemma 1. Let ( λ t ) t = 0 T (\lambda_t)_{t=0}^{T} ( λ t ) t = 0 T λ 0 = 0 \lambda_0=0 λ 0 = 0 x 1 , … , x T x_1,\ldots,x_T x 1 , … , x T
x t = ( 1 − λ t ) x 0 + λ t ϵ , ϵ ∼ N ( ⋅ ∣ 0 , I ) . (32) x_t=(1-\lambda_t)x_0+\lambda_t\epsilon,\qquad\epsilon\sim\mathcal{N}(\cdot\mid0,I). \tag*{(32)} x t = ( 1 − λ t ) x 0 + λ t ϵ , ϵ ∼ N ( ⋅ ∣ 0 , I ) . (32) Then, for t = 1 , … , T t=1,\ldots,T t = 1 , … , T
q ( x t ∣ x 0 ) = N ( x t ∣ μ ⃗ t , Σ ⃗ t ) and q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ ← t − 1 ( x t , x 0 ) ) . (33) q(x_t\mid x_0)=\mathcal{N}\left(x_t\mid\vec{\mu}_t,\vec{\Sigma}_t\right)\quad\text{and}\quad q(x_{t-1}\mid x_t,x_0)=\delta\left(x_{t-1}\mid\overleftarrow{\mu}_{t-1}(x_t,x_0)\right). \tag*{(33)} q ( x t ∣ x 0 ) = N ( x t ∣ μ t , Σ t ) and q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ t − 1 ( x t , x 0 ) ) . (33) where
μ ⃗ t = ( 1 − λ t ) x 0 , Σ ⃗ t = λ t 2 I , μ ← t − 1 ( x t , x 0 ) = ( 1 − λ t − 1 λ t ) x 0 + λ t − 1 λ t x t . (34) \vec{\mu}_t=(1-\lambda_t)x_0,\qquad\vec{\Sigma}_t=\lambda_t^2I,\qquad\overleftarrow{\mu}_{t-1}(x_t,x_0)=\left(1-\frac{\lambda_{t-1}}{\lambda_t}\right)x_0+\frac{\lambda_{t-1}}{\lambda_t}x_t. \tag*{(34)} μ t = ( 1 − λ t ) x 0 , Σ t = λ t 2 I , μ t − 1 ( x t , x 0 ) = ( 1 − λ t λ t − 1 ) x 0 + λ t λ t − 1 x t . (34) Proof. Marginal. Conditioned on x 0 x_0 x 0 x t x_t x t ϵ \epsilon ϵ q ( x t ∣ x 0 ) q(x_t\mid x_0) q ( x t ∣ x 0 ) ⟨ ϵ ⟩ = 0 \langle\epsilon\rangle=0 ⟨ ϵ ⟩ = 0 ⟨ ϵ ϵ T ⟩ = I \langle\epsilon\epsilon^{\mathsf{T}}\rangle=I ⟨ ϵ ϵ T ⟩ = I
μ ⃗ t = ⟨ x t ⟩ = ( 1 − λ t ) x 0 + λ t ⟨ ϵ ⟩ = ( 1 − λ t ) x 0 , (35) \vec{\mu}_t=\langle x_t\rangle=(1-\lambda_t)x_0+\lambda_t\langle\epsilon\rangle=(1-\lambda_t)x_0, \tag*{(35)} μ t = ⟨ x t ⟩ = ( 1 − λ t ) x 0 + λ t ⟨ ϵ ⟩ = ( 1 − λ t ) x 0 , (35) Σ ⃗ t = ⟨ ( x t − μ ⃗ t ) ( x t − μ ⃗ t ) T ⟩ = λ t 2 ⟨ ϵ ϵ T ⟩ = λ t 2 I . (36) \vec{\Sigma}_t=\left\langle(x_t-\vec{\mu}_t)(x_t-\vec{\mu}_t)^{\mathsf{T}}\right\rangle=\lambda_t^2\langle\epsilon\epsilon^{\mathsf{T}}\rangle=\lambda_t^2I. \tag*{(36)} Σ t = ⟨ ( x t − μ t ) ( x t − μ t ) T ⟩ = λ t 2 ⟨ ϵ ϵ T ⟩ = λ t 2 I . (36) Posterior. Since x t − 1 x_{t-1} x t − 1 x t x_t x t ϵ \epsilon ϵ λ t > λ 0 = 0 \lambda_t>\lambda_0=0 λ t > λ 0 = 0 t ≥ 1 t\geq1 t ≥ 1
ϵ = x t − ( 1 − λ t ) x 0 λ t . (37) \epsilon=\frac{x_t-(1-\lambda_t)x_0}{\lambda_t}. \tag*{(37)} ϵ = λ t x t − ( 1 − λ t ) x 0 . (37) Substituting into x t − 1 = ( 1 − λ t − 1 ) x 0 + λ t − 1 ϵ x_{t-1}=(1-\lambda_{t-1})x_0+\lambda_{t-1}\epsilon x t − 1 = ( 1 − λ t − 1 ) x 0 + λ t − 1 ϵ
x t − 1 = ( 1 − λ t − 1 ) x 0 + λ t − 1 λ t ( x t − ( 1 − λ t ) x 0 ) (38) x_{t-1}=(1-\lambda_{t-1})x_0+\frac{\lambda_{t-1}}{\lambda_t}\left(x_t-(1-\lambda_t)x_0\right) \tag*{(38)} x t − 1 = ( 1 − λ t − 1 ) x 0 + λ t λ t − 1 ( x t − ( 1 − λ t ) x 0 ) (38) = [ 1 − λ t − 1 − λ t − 1 λ t + λ t − 1 ] x 0 + λ t − 1 λ t x t (39) =\left[1-\lambda_{t-1}-\frac{\lambda_{t-1}}{\lambda_t}+\lambda_{t-1}\right]x_0+\frac{\lambda_{t-1}}{\lambda_t}x_t \tag*{(39)} = [ 1 − λ t − 1 − λ t λ t − 1 + λ t − 1 ] x 0 + λ t λ t − 1 x t (39) = ( 1 − λ t − 1 λ t ) x 0 + λ t − 1 λ t x t = μ ← t − 1 ( x t , x 0 ) . (40) =\left(1-\frac{\lambda_{t-1}}{\lambda_t}\right)x_0+\frac{\lambda_{t-1}}{\lambda_t}x_t=\overleftarrow{\mu}_{t-1}(x_t,x_0). \tag*{(40)} = ( 1 − λ t λ t − 1 ) x 0 + λ t λ t − 1 x t = μ t − 1 ( x t , x 0 ) . (40) Hence, given ( x t , x 0 ) (x_t,x_0) ( x t , x 0 ) x t − 1 x_{t-1} x t − 1 q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ ← t − 1 ( x t , x 0 ) ) q(x_{t-1}\mid x_t,x_0)=\delta\left(x_{t-1}\mid\overleftarrow{\mu}_{t-1}(x_t,x_0)\right) q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ t − 1 ( x t , x 0 ) ) □ \square □
Proof of Lemma 2 (Decomposition of the Spread Objective)
Lemma 2 (Decomposition of the spread objective). For every θ \theta θ
L ′ ( θ ) = D ( θ ) + C , (41) L'(\theta)=D(\theta)+C, \tag*{(41)} L ′ ( θ ) = D ( θ ) + C , (41) where C C C θ \theta θ
Proof. Each term of L ′ L' L ′ q ( x 0 ) q ( x t ∣ x 0 ) = q ( x t ) q ( x 0 ∣ x t ) q(x_0)q(x_t\mid x_0)=q(x_t)q(x_0\mid x_t) q ( x 0 ) q ( x t ∣ x 0 ) = q ( x t ) q ( x 0 ∣ x t ) q ~ ( y t − 1 , x 0 ∣ x t ) : = q ( x 0 ∣ x t ) q ~ ( y t − 1 ∣ x t , x 0 ) \widetilde{q}(y_{t-1},x_0\mid x_t):=q(x_0\mid x_t)\widetilde{q}(y_{t-1}\mid x_t,x_0) q ( y t − 1 , x 0 ∣ x t ) := q ( x 0 ∣ x t ) q ( y t − 1 ∣ x t , x 0 ) x 0 x_0 x 0 x t x_t x t y t − 1 y_{t-1} y t − 1 q ~ ( y t − 1 ∣ x t ) \widetilde{q}(y_{t-1} \mid x_t) q ( y t − 1 ∣ x t ) log q ~ ( y t − 1 ∣ x t ) \log\widetilde{q}(y_{t-1} \mid x_t) log q ( y t − 1 ∣ x t )
⟨ KL [ q ~ ( y t − 1 ∣ x t , x 0 ) ∥ p ~ θ ( y t − 1 ∣ x t ) ] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) = ⟨ ∫ d y t − 1 q ~ ( y t − 1 ∣ x t , x 0 ) log q ~ ( y t − 1 ∣ x t ) p ~ θ ( y t − 1 ∣ x t ) ⟩ q ( x 0 ∣ x t ) q ( x t ) + ⟨ ∫ d y t − 1 q ~ ( y t − 1 ∣ x t , x 0 ) log q ~ ( y t − 1 ∣ x t , x 0 ) q ~ ( y t − 1 ∣ x t ) ⟩ q ( x 0 ∣ x t ) q ( x t ) (42) \left\langle\operatorname{KL}\left[\widetilde{q}(y_{t-1} \mid x_t,x_0) \,\middle\|\, \widetilde{p}_{\theta}(y_{t-1} \mid x_t)\right]\right\rangle_{q(x_t\mid x_0)q(x_0)}
= \left\langle\int\mathrm{d}y_{t-1}\,\widetilde{q}(y_{t-1} \mid x_t,x_0)\log\frac{\widetilde{q}(y_{t-1}\mid x_t)}{\widetilde{p}_{\theta}(y_{t-1}\mid x_t)}\right\rangle_{q(x_0\mid x_t)q(x_t)}
+ \left\langle\int\mathrm{d}y_{t-1}\,\widetilde{q}(y_{t-1}\mid x_t,x_0)\log\frac{\widetilde{q}(y_{t-1}\mid x_t,x_0)}{\widetilde{q}(y_{t-1}\mid x_t)}\right\rangle_{q(x_0\mid x_t)q(x_t)} \tag*{(42)} ⟨ KL [ q ( y t − 1 ∣ x t , x 0 ) ∥ p θ ( y t − 1 ∣ x t ) ] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) = ⟨ ∫ d y t − 1 q ( y t − 1 ∣ x t , x 0 ) log p θ ( y t − 1 ∣ x t ) q ( y t − 1 ∣ x t ) ⟩ q ( x 0 ∣ x t ) q ( x t ) + ⟨ ∫ d y t − 1 q ( y t − 1 ∣ x t , x 0 ) log q ( y t − 1 ∣ x t ) q ( y t − 1 ∣ x t , x 0 ) ⟩ q ( x 0 ∣ x t ) q ( x t ) (42) = ⟨ ∫ d y t − 1 d x 0 q ~ ( y t − 1 , x 0 ∣ x t ) log q ~ ( y t − 1 ∣ x t ) p ~ θ ( y t − 1 ∣ x t ) ⟩ q ( x t ) + G t (43) = \left\langle\int\mathrm{d}y_{t-1}\mathrm{d}x_0\,\widetilde{q}(y_{t-1},x_0\mid x_t)\log\frac{\widetilde{q}(y_{t-1}\mid x_t)}{\widetilde{p}_{\theta}(y_{t-1}\mid x_t)}\right\rangle_{q(x_t)}+G_t \tag*{(43)} = ⟨ ∫ d y t − 1 d x 0 q ( y t − 1 , x 0 ∣ x t ) log p θ ( y t − 1 ∣ x t ) q ( y t − 1 ∣ x t ) ⟩ q ( x t ) + G t (43) = ⟨ KL [ q ~ ( y t − 1 ∣ x t ) ∥ p ~ θ ( y t − 1 ∣ x t ) ] ⟩ q ( x t ) + G t . (44) = \left\langle\operatorname{KL}\left[\widetilde{q}(y_{t-1}\mid x_t)\,\middle\|\,\widetilde{p}_{\theta}(y_{t-1}\mid x_t)\right]\right\rangle_{q(x_t)}+G_t. \tag*{(44)} = ⟨ KL [ q ( y t − 1 ∣ x t ) ∥ p θ ( y t − 1 ∣ x t ) ] ⟩ q ( x t ) + G t . (44) Here G t G_t G t
G t = ⟨ KL [ q ~ ( y t − 1 ∣ x t , x 0 ) ∥ q ~ ( y t − 1 ∣ x t ) ] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (45) G_t=\left\langle\operatorname{KL}\left[\widetilde{q}(y_{t-1}\mid x_t,x_0)\,\middle\|\,\widetilde{q}(y_{t-1}\mid x_t)\right]\right\rangle_{q(x_t\mid x_0)q(x_0)}. \tag*{(45)} G t = ⟨ KL [ q ( y t − 1 ∣ x t , x 0 ) ∥ q ( y t − 1 ∣ x t ) ] ⟩ q ( x t ∣ x 0 ) q ( x 0 ) . (45) The resulting identity between the first and the last line is the chain rule of the KL divergence for the joint q ~ ( y t − 1 , x 0 ∣ x t ) \widetilde{q}(y_{t-1},x_0\mid x_t) q ( y t − 1 , x 0 ∣ x t )
Summing over t t t L ′ ( θ ) = D ( θ ) + C L'(\theta)=D(\theta)+C L ′ ( θ ) = D ( θ ) + C C = ∑ t = 1 T G t C=\sum_{t=1}^{T}G_t C = ∑ t = 1 T G t θ \theta θ
Proof of Theorem 1 (Convergence of the Deterministic Sampler)
Notation. As in Theorem 1, x ^ T , x ^ T − 1 , … , x ^ 0 \widehat{x}_T,\widehat{x}_{T-1},\ldots,\widehat{x}_0 x T , x T − 1 , … , x 0 x ^ 0 \widehat{x}_0 x 0 x t x_t x t q t q_t q t x 0 1 , … , x 0 N x_0^1,\ldots,x_0^N x 0 1 , … , x 0 N q t q_t q t m t m_t m t w n t w_n^t w n t x ∈ R d x\in\mathbb{R}^d x ∈ R d y T , … , y 0 y_T,\ldots,y_0 y T , … , y 0 y y y y t − 1 y_{t-1} y t − 1
Overview. The proof has four parts. (i) We define the reference chain, which starts from the same noise as the sampled chain but samples from the backward distribution, and we choose the constants R R R b b b ρ \rho ρ η \eta η ζ \zeta ζ λ t ≥ ζ \lambda_t\ge\zeta λ t ≥ ζ y t ∼ q t y_t\sim q_t y t ∼ q t x ^ t \widehat{x}_t x t y t y_t y t O ( h ) O(h) O ( h ) ζ \zeta ζ h h h λ t ≤ 2 ζ \lambda_t\le2\zeta λ t ≤ 2 ζ x 0 m x_0^m x 0 m q t q_t q t ( 1 − λ t ) x 0 m (1-\lambda_t)x_0^m ( 1 − λ t ) x 0 m ( ρ ) (\rho) ( ρ ) ρ \rho ρ x ^ 0 \widehat{x}_0 x 0 γ T = R η ( λ 1 ) \gamma_T=R\eta(\lambda_1) γ T = R η ( λ 1 ) x 0 m x_0^m x 0 m τ \tau τ t t t λ t ≥ ζ \lambda_t\ge\zeta λ t ≥ ζ q τ q_\tau q τ N N N 1 N \frac{1}{N} N 1 x 0 m x_0^m x 0 m ( 1 − λ τ ) x 0 m (1-\lambda_\tau)x_0^m ( 1 − λ τ ) x 0 m λ τ \lambda_\tau λ τ λ τ < 2 ζ \lambda_\tau<2\zeta λ τ < 2 ζ T T T h ≤ ζ h\le\zeta h ≤ ζ y τ ∼ q τ y_\tau\sim q_\tau y τ ∼ q τ ρ / 2 \rho/2 ρ /2 ( 1 − λ τ ) x 0 m (1-\lambda_\tau)x_0^m ( 1 − λ τ ) x 0 m x 0 m x_0^m x 0 m 1 N \frac{1}{N} N 1 ζ \zeta ζ x ^ τ \widehat{x}_\tau x τ ρ / 2 \rho/2 ρ /2 y τ y_\tau y τ ρ \rho ρ P ( ∥ x ^ 0 − x 0 m ∥ ≤ γ T ) P(\|\widehat{x}_0-x_0^m\|\le\gamma_T) P ( ∥ x 0 − x 0 m ∥ ≤ γ T ) N − 1 N-1 N − 1 1 N \frac{1}{N} N 1 T → ∞ T\to\infty T → ∞ ζ → 0 \zeta\to0 ζ → 0
Definitions. The sampled chain x ^ T , x ^ T − 1 , … , x ^ 0 \widehat{x}_T,\widehat{x}_{T-1},\ldots,\widehat{x}_0 x T , x T − 1 , … , x 0 x ^ T ∼ N ( ⋅ ∣ 0 , I ) \widehat{x}_T\sim\mathcal{N}(\cdot\mid0,I) x T ∼ N ( ⋅ ∣ 0 , I ) y T , y T − 1 , … , y 0 y_T,y_{T-1},\ldots,y_0 y T , y T − 1 , … , y 0 q t q_t q t
R = max n , m ∥ x 0 n − x 0 m ∥ , b = min n ≠ m ∥ x 0 n − x 0 m ∥ > 0 , (46) R=\max_{n,m}\left\|x_0^n-x_0^m\right\|,\qquad b=\min_{n\ne m}\left\|x_0^n-x_0^m\right\|>0, \tag*{(46)} R = n , m max ∥ x 0 n − x 0 m ∥ , b = n = m min ∥ x 0 n − x 0 m ∥ > 0 , (46) where b b b N > 2 N>2 N > 2 ρ \rho ρ η \eta η λ > 0 \lambda>0 λ > 0 λ \lambda λ λ → 0 \lambda\to0 λ → 0
ρ = b 8 , η ( λ ) = ( N − 1 ) exp { − b 2 16 λ 2 } . (47) \rho=\frac{b}{8},\qquad\eta(\lambda)=(N-1)\exp\left\{-\frac{b^2}{16\lambda^2}\right\}. \tag*{(47)} ρ = 8 b , η ( λ ) = ( N − 1 ) exp { − 16 λ 2 b 2 } . (47) Throughout this appendix, including Lemmas 4 and 5, we assume as in Theorem 1 that the generator is at the exact optimum of the spread objective, μ θ ( x ) = μ t ∗ ( x ) \mu_\theta(x)=\mu_t^*(x) μ θ ( x ) = μ t ∗ ( x ) x ∈ R d x\in\mathbb{R}^d x ∈ R d μ ← t − 1 ( x , x 0 ) = x − Δ λ t λ t ( x − x 0 ) \overleftarrow{\mu}_{t-1}(x,x_0)=x-\frac{\Delta\lambda_t}{\lambda_t}(x-x_0) μ t − 1 ( x , x 0 ) = x − λ t Δ λ t ( x − x 0 ) μ t ∗ ( x ) = x − Δ λ t v t ∗ ( x ) \mu_t^*(x)=x-\Delta\lambda_t v_t^*(x) μ t ∗ ( x ) = x − Δ λ t v t ∗ ( x ) v t ∗ ( x ) = ( x − m t ( x ) ) / λ t v_t^*(x)=(x-m_t(x))/\lambda_t v t ∗ ( x ) = ( x − m t ( x )) / λ t m t m_t m t q t q_t q t w n t w_n^t w n t K K K x t x_t x t
m t ( x ) = ⟨ x 0 ⟩ q ( x 0 ∣ x t = x ) = ∑ n = 1 N w n t ( x ) x 0 n , (48) m_t(x)=\langle x_0\rangle_{q(x_0\mid x_t=x)}=\sum_{n=1}^{N}w_n^t(x)x_0^n, \tag*{(48)} m t ( x ) = ⟨ x 0 ⟩ q ( x 0 ∣ x t = x ) = n = 1 ∑ N w n t ( x ) x 0 n , (48) w n t ( x ) = q ( K = n ∣ x t = x ) = exp { − ∥ x − ( 1 − λ t ) x 0 n ∥ 2 / ( 2 λ t 2 ) } ∑ k = 1 N exp { − ∥ x − ( 1 − λ t ) x 0 k ∥ 2 / ( 2 λ t 2 ) } . (49) w_n^t(x)=q(K=n\mid x_t=x)=\frac{\exp\left\{-\lVert x-(1-\lambda_t)x_0^n\rVert^2/(2\lambda_t^2)\right\}}{\sum_{k=1}^{N}\exp\left\{-\lVert x-(1-\lambda_t)x_0^k\rVert^2/(2\lambda_t^2)\right\}}. \tag*{(49)} w n t ( x ) = q ( K = n ∣ x t = x ) = ∑ k = 1 N exp { − ∥ x − ( 1 − λ t ) x 0 k ∥ 2 / ( 2 λ t 2 ) } exp { − ∥ x − ( 1 − λ t ) x 0 n ∥ 2 / ( 2 λ t 2 ) } . (49) With r t = λ t − 1 / λ t r_t=\lambda_{t-1}/\lambda_t r t = λ t − 1 / λ t μ ← t − 1 ( x , x 0 ) = r t x + ( 1 − r t ) x 0 \overleftarrow{\mu}_{t-1}(x,x_0)=r_t x+(1-r_t)x_0 μ t − 1 ( x , x 0 ) = r t x + ( 1 − r t ) x 0 x ^ t − 1 = x ^ t − Δ λ t v θ ( x ^ t ) \hat{x}_{t-1}=\hat{x}_t-\Delta\lambda_t v_\theta(\hat{x}_t) x ^ t − 1 = x ^ t − Δ λ t v θ ( x ^ t )
x ^ t − 1 = μ ← t − 1 ( x ^ t , m t ( x ^ t ) ) = r t x ^ t + ( 1 − r t ) m t ( x ^ t ) . (50) \hat{x}_{t-1}=\overleftarrow{\mu}_{t-1}(\hat{x}_t,m_t(\hat{x}_t))=r_t\hat{x}_t+(1-r_t)m_t(\hat{x}_t). \tag*{(50)} x ^ t − 1 = μ t − 1 ( x ^ t , m t ( x ^ t )) = r t x ^ t + ( 1 − r t ) m t ( x ^ t ) . (50) We define the reference chain to start from the same noise, y T = x ^ T y_T=\hat{x}_T y T = x ^ T
y t − 1 = μ ← t − 1 ( y t , x 0 J t ) = r t y t + ( 1 − r t ) x 0 J t , P ( J t = n ∣ F t ) = w n t ( y t ) , (51) y_{t-1}=\overleftarrow{\mu}_{t-1}(y_t,x_0^{J_t})=r_t y_t+(1-r_t)x_0^{J_t},\qquad P(J_t=n\mid\mathcal{F}_t)=w_n^t(y_t), \tag*{(51)} y t − 1 = μ t − 1 ( y t , x 0 J t ) = r t y t + ( 1 − r t ) x 0 J t , P ( J t = n ∣ F t ) = w n t ( y t ) , (51) where F t \mathcal{F}_t F t σ \sigma σ ( x ^ T , J T , … , J t + 1 ) (\hat{x}_T,J_T,\ldots,J_{t+1}) ( x ^ T , J T , … , J t + 1 ) y t y_t y t x ^ t \hat{x}_t x ^ t x ^ T \hat{x}_T x ^ T Δ λ t \Delta\lambda_t Δ λ t 1 − r t = Δ λ t / λ t 1-r_t=\Delta\lambda_t/\lambda_t 1 − r t = Δ λ t / λ t h = max t Δ λ t h=\max_t\Delta\lambda_t h = max t Δ λ t ζ > 0 \zeta>0 ζ > 0
ζ ≤ 1 4 and R η ( 2 ζ ) ≤ ρ . (52) \zeta\leq\frac{1}{4}\qquad\text{and}\qquad R\eta(2\zeta)\leq\rho. \tag*{(52)} ζ ≤ 4 1 and R η ( 2 ζ ) ≤ ρ . (52) Such a ζ \zeta ζ η ( λ ) → 0 \eta(\lambda)\to0 η ( λ ) → 0 λ → 0 \lambda\to0 λ → 0 η \eta η ζ \zeta ζ
Lemma 4 (Tracking). Let τ = min { t : λ t ≥ ζ } \tau=\min\{t:\lambda_t\geq\zeta\} τ = min { t : λ t ≥ ζ } y t ∼ q t y_t\sim q_t y t ∼ q t t t t τ \tau τ
⟨ ∥ x ^ τ − y τ ∥ 2 ⟩ ≤ exp ( 2 R 2 ζ 3 ) R 2 h ζ 2 . (53) \left\langle\lVert\hat{x}_\tau-y_\tau\rVert^2\right\rangle\leq\exp\left(\frac{2R^2}{\zeta^3}\right)\frac{R^2h}{\zeta^2}. \tag*{(53)} ⟨ ∥ x ^ τ − y τ ∥ 2 ⟩ ≤ exp ( ζ 3 2 R 2 ) ζ 2 R 2 h . (53) Moreover, λ τ < 2 ζ \lambda_\tau<2\zeta λ τ < 2 ζ h ≤ ζ h\leq\zeta h ≤ ζ
Proof. Reference chain marginals. By Lemma 1, q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ ← t − 1 ( x t , x 0 ) ) q(x_{t-1}\mid x_t,x_0)=\delta(x_{t-1}\mid\overleftarrow{\mu}_{t-1}(x_t,x_0)) q ( x t − 1 ∣ x t , x 0 ) = δ ( x t − 1 ∣ μ t − 1 ( x t , x 0 ))
q ( x t − 1 ∣ x t ) = ∑ n = 1 N q ( K = n ∣ x t ) q ( x t − 1 ∣ x t , x 0 n ) = ∑ n = 1 N w n t ( x t ) δ ( x t − 1 ∣ μ ← t − 1 ( x t , x 0 n ) ) . (54) q(x_{t-1}\mid x_t)=\sum_{n=1}^{N}q(K=n\mid x_t)q(x_{t-1}\mid x_t,x_0^n)=\sum_{n=1}^{N}w_n^t(x_t)\delta(x_{t-1}\mid\overleftarrow{\mu}_{t-1}(x_t,x_0^n)). \tag*{(54)} q ( x t − 1 ∣ x t ) = n = 1 ∑ N q ( K = n ∣ x t ) q ( x t − 1 ∣ x t , x 0 n ) = n = 1 ∑ N w n t ( x t ) δ ( x t − 1 ∣ μ t − 1 ( x t , x 0 n )) . (54) A step of the reference chain equation (47) is exactly a draw y t − 1 ∼ q ( x t − 1 ∣ x t = y t ) y_{t-1}\sim q(x_{t-1}\mid x_t=y_t) y t − 1 ∼ q ( x t − 1 ∣ x t = y t ) y t ∼ q t y_t\sim q_t y t ∼ q t y t − 1 y_{t-1} y t − 1
∫ q ( x t − 1 ∣ x t ) q t ( x t ) d x t = q t − 1 ( x t − 1 ) , (55) \int q(x_{t-1}\mid x_t)q_t(x_t)\,dx_t=q_{t-1}(x_{t-1}), \tag*{(55)} ∫ q ( x t − 1 ∣ x t ) q t ( x t ) d x t = q t − 1 ( x t − 1 ) , (55) and since y T ∼ N ( ⋅ ∣ 0 , I ) = q T y_T\sim\mathcal{N}(\mathord{\cdot}\mid0,I)=q_T y T ∼ N ( ⋅ ∣ 0 , I ) = q T y t ∼ q t y_t\sim q_t y t ∼ q t t t t
Lipschitz bound of posterior mean. Let C t ( x ) = ∑ n = 1 N w n t ( x ) ( x 0 n − m t ( x ) ) ( x 0 n − m t ( x ) ) T C_t(x) = \sum_{n=1}^{N} w_n^t(x)(x_0^n-m_t(x))(x_0^n-m_t(x))^{\mathsf{T}} C t ( x ) = ∑ n = 1 N w n t ( x ) ( x 0 n − m t ( x )) ( x 0 n − m t ( x ) ) T x t = x x_t=x x t = x ∇ w n t ( x ) = 1 − λ t λ t 2 w n t ( x ) ( x 0 n − m t ( x ) ) \nabla w_n^t(x) = \frac{1-\lambda_t}{\lambda_t^2}w_n^t(x)(x_0^n-m_t(x)) ∇ w n t ( x ) = λ t 2 1 − λ t w n t ( x ) ( x 0 n − m t ( x )) m t m_t m t
∇ m t ( x ) = ∑ n = 1 N x 0 n ∇ w n t ( x ) T = 1 − λ t λ t 2 C t ( x ) . (56) \nabla m_t(x)=\sum_{n=1}^{N}x_0^n\nabla w_n^t(x)^{\mathsf{T}}=\frac{1-\lambda_t}{\lambda_t^2}C_t(x). \tag*{(56)} ∇ m t ( x ) = n = 1 ∑ N x 0 n ∇ w n t ( x ) T = λ t 2 1 − λ t C t ( x ) . (56) As m t ( x ) m_t(x) m t ( x ) ∥ x 0 n − m t ( x ) ∥ ≤ R \lVert x_0^n-m_t(x)\rVert\le R ∥ x 0 n − m t ( x )∥ ≤ R ν ∈ R d \nu\in\mathbb{R}^d ν ∈ R d
∥ C t ( x ) ν ∥ = ∥ ∑ n = 1 N w n t ( x ) ( x 0 n − m t ( x ) ) ( x 0 n − m t ( x ) ) T ν ∥ ≤ ∑ n = 1 N w n t ( x ) ∥ x 0 n − m t ( x ) ∥ 2 ∥ ν ∥ ≤ R 2 ∥ ν ∥ . (57) \left\lVert C_t(x)\nu\right\rVert=\left\lVert\sum_{n=1}^{N}w_n^t(x)(x_0^n-m_t(x))(x_0^n-m_t(x))^{\mathsf{T}}\nu\right\rVert\le\sum_{n=1}^{N}w_n^t(x)\lVert x_0^n-m_t(x)\rVert^2\lVert\nu\rVert\le R^2\lVert\nu\rVert. \tag*{(57)} ∥ C t ( x ) ν ∥ = n = 1 ∑ N w n t ( x ) ( x 0 n − m t ( x )) ( x 0 n − m t ( x ) ) T ν ≤ n = 1 ∑ N w n t ( x ) ∥ x 0 n − m t ( x ) ∥ 2 ∥ ν ∥ ≤ R 2 ∥ ν ∥ . (57) Now fix x , x ′ ∈ R d x,x'\in\mathbb{R}^d x , x ′ ∈ R d x α = x ′ + α ( x − x ′ ) x_\alpha=x'+\alpha(x-x') x α = x ′ + α ( x − x ′ ) α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] x ′ x' x ′ x x x
m t ( x ) − m t ( x ′ ) = ∫ 0 1 d d α m t ( x α ) d α = ∫ 0 1 ∇ m t ( x α ) ( x − x ′ ) d α = 1 − λ t λ t 2 ∫ 0 1 C t ( x α ) ( x − x ′ ) d α . (58) m_t(x)-m_t(x')=\int_0^1\frac{d}{d\alpha}m_t(x_\alpha)\,d\alpha=\int_0^1\nabla m_t(x_\alpha)(x-x')\,d\alpha=\frac{1-\lambda_t}{\lambda_t^2}\int_0^1C_t(x_\alpha)(x-x')\,d\alpha. \tag*{(58)} m t ( x ) − m t ( x ′ ) = ∫ 0 1 d α d m t ( x α ) d α = ∫ 0 1 ∇ m t ( x α ) ( x − x ′ ) d α = λ t 2 1 − λ t ∫ 0 1 C t ( x α ) ( x − x ′ ) d α . (58) Taking norms, applying equation (57) with ν = x − x ′ \nu=x-x' ν = x − x ′ x α x_\alpha x α 1 − λ t ≤ 1 1-\lambda_t\le1 1 − λ t ≤ 1
∥ m t ( x ) − m t ( x ′ ) ∥ ≤ 1 − λ t λ t 2 ∫ 0 1 ∥ C t ( x α ) ( x − x ′ ) ∥ d α ≤ 1 − λ t λ t 2 ∫ 0 1 R 2 ∥ x − x ′ ∥ d α ≤ R 2 λ t 2 ∥ x − x ′ ∥ . (59) \lVert m_t(x)-m_t(x')\rVert\le\frac{1-\lambda_t}{\lambda_t^2}\int_0^1\lVert C_t(x_\alpha)(x-x')\rVert\,d\alpha\le\frac{1-\lambda_t}{\lambda_t^2}\int_0^1R^2\lVert x-x'\rVert\,d\alpha\le\frac{R^2}{\lambda_t^2}\lVert x-x'\rVert. \tag*{(59)} ∥ m t ( x ) − m t ( x ′ )∥ ≤ λ t 2 1 − λ t ∫ 0 1 ∥ C t ( x α ) ( x − x ′ )∥ d α ≤ λ t 2 1 − λ t ∫ 0 1 R 2 ∥ x − x ′ ∥ d α ≤ λ t 2 R 2 ∥ x − x ′ ∥ . (59) Error recursion. Let e t = x ^ t − y t e_t=\hat{x}_t-y_t e t = x ^ t − y t e T = 0 e_T=0 e T = 0 ξ t = m t ( y t ) − x 0 J t \xi_t=m_t(y_t)-x_0^{J_t} ξ t = m t ( y t ) − x 0 J t (51) from equation (50) , and adding and subtracting ( 1 − r t ) m t ( y t ) (1-r_t)m_t(y_t) ( 1 − r t ) m t ( y t )
e t − 1 = a t + ( 1 − r t ) ξ t , a t = r t e t + ( 1 − r t ) ( m t ( x ^ t ) − m t ( y t ) ) . (60) e_{t-1}=a_t+(1-r_t)\xi_t,\qquad a_t=r_te_t+(1-r_t)\left(m_t(\hat{x}_t)-m_t(y_t)\right). \tag*{(60)} e t − 1 = a t + ( 1 − r t ) ξ t , a t = r t e t + ( 1 − r t ) ( m t ( x ^ t ) − m t ( y t ) ) . (60) The term a t a_t a t F t \mathcal{F}_t F t x ^ t \hat{x}_t x ^ t y t y_t y t t t t J t J_t J t ξ t \xi_t ξ t F t \mathcal{F}_t F t J t J_t J t ( w n t ( y t ) ) n = 1 N (w_n^t(y_t))_{n=1}^N ( w n t ( y t ) ) n = 1 N ∥ x 0 n − m t ( y t ) ∥ ≤ R \lVert x_0^n-m_t(y_t)\rVert\le R ∥ x 0 n − m t ( y t )∥ ≤ R ∑ n = 1 N w n t ( y t ) = 1 \sum_{n=1}^Nw_n^t(y_t)=1 ∑ n = 1 N w n t ( y t ) = 1
⟨ ξ t ⟩ P ( ⋅ ∣ F t ) = m t ( y t ) − ∑ n = 1 N w n t ( y t ) x 0 n = 0 , \left\langle\xi_t\right\rangle_{P(\cdot\mid\mathcal{F}_t)}=m_t(y_t)-\sum_{n=1}^{N}w_n^t(y_t)x_0^n=0, ⟨ ξ t ⟩ P ( ⋅ ∣ F t ) = m t ( y t ) − n = 1 ∑ N w n t ( y t ) x 0 n = 0 , ⟨ ∥ ξ t ∥ 2 ⟩ P ( ⋅ ∣ F t ) = ∑ n = 1 N w n t ( y t ) ∥ m t ( y t ) − x 0 n ∥ 2 ≤ R 2 . (61) \left\langle\lVert\xi_t\rVert^2\right\rangle_{P(\cdot\mid\mathcal{F}_t)}=\sum_{n=1}^{N}w_n^t(y_t)\lVert m_t(y_t)-x_0^n\rVert^2\le R^2. \tag*{(61)} ⟨ ∥ ξ t ∥ 2 ⟩ P ( ⋅ ∣ F t ) = n = 1 ∑ N w n t ( y t ) ∥ m t ( y t ) − x 0 n ∥ 2 ≤ R 2 . (61) One step. Let V t = ⟨ ∥ e t ∥ 2 ⟩ V_t=\left\langle\lVert e_t\rVert^2\right\rangle V t = ⟨ ∥ e t ∥ 2 ⟩ (60) , the cross term vanishes by equation (61) , since ⟨ a t T ξ t ⟩ = ⟨ a t T ⟨ ξ t ⟩ P ( ⋅ ∣ F t ) ⟩ = 0 \langle a_t^{\mathsf{T}}\xi_t\rangle=\langle a_t^{\mathsf{T}}\langle\xi_t\rangle_{P(\cdot\mid\mathcal{F}_t)}\rangle=0 ⟨ a t T ξ t ⟩ = ⟨ a t T ⟨ ξ t ⟩ P ( ⋅ ∣ F t ) ⟩ = 0 1 − r t = Δ λ t / λ t 1-r_t=\Delta\lambda_t/\lambda_t 1 − r t = Δ λ t / λ t
V t − 1 = ⟨ ∥ a t ∥ 2 ⟩ + ( Δ λ t ) 2 λ t 2 ⟨ ∥ ξ t ∥ 2 ⟩ ≤ ⟨ ∥ a t ∥ 2 ⟩ + R 2 ( Δ λ t ) 2 λ t 2 . (62) V_{t-1}=\left\langle\lVert a_t\rVert^2\right\rangle+\frac{(\Delta\lambda_t)^2}{\lambda_t^2}\left\langle\lVert\xi_t\rVert^2\right\rangle\le\left\langle\lVert a_t\rVert^2\right\rangle+\frac{R^2(\Delta\lambda_t)^2}{\lambda_t^2}. \tag*{(62)} V t − 1 = ⟨ ∥ a t ∥ 2 ⟩ + λ t 2 ( Δ λ t ) 2 ⟨ ∥ ξ t ∥ 2 ⟩ ≤ ⟨ ∥ a t ∥ 2 ⟩ + λ t 2 R 2 ( Δ λ t ) 2 . (62) By equation (59) and r t ≤ 1 r_t\le1 r t ≤ 1
∥ a t ∥ ≤ r t ∥ e t ∥ + Δ λ t λ t R 2 λ t 2 ∥ e t ∥ ≤ ( 1 + κ t ) ∥ e t ∥ , κ t = R 2 Δ λ t λ t 3 , (63) \lVert a_t\rVert\le r_t\lVert e_t\rVert+\frac{\Delta\lambda_t}{\lambda_t}\frac{R^2}{\lambda_t^2}\lVert e_t\rVert\le(1+\kappa_t)\lVert e_t\rVert,\qquad\kappa_t=\frac{R^2\Delta\lambda_t}{\lambda_t^3}, \tag*{(63)} ∥ a t ∥ ≤ r t ∥ e t ∥ + λ t Δ λ t λ t 2 R 2 ∥ e t ∥ ≤ ( 1 + κ t ) ∥ e t ∥ , κ t = λ t 3 R 2 Δ λ t , (63) and therefore
V t − 1 ≤ ( 1 + κ t ) 2 V t + R 2 ( Δ λ t ) 2 λ t 2 . (64) V_{t-1} \le(1+\kappa_t)^2 V_t + \frac{R^2(\Delta\lambda_t)^2}{\lambda_t^2}. \tag*{(64)} V t − 1 ≤ ( 1 + κ t ) 2 V t + λ t 2 R 2 ( Δ λ t ) 2 . (64) Unrolling. Applying equation (64) from V T = 0 V_T=0 V T = 0 τ \tau τ 1 + κ ≤ e κ 1+\kappa\le e^\kappa 1 + κ ≤ e κ κ ≥ 0 \kappa\ge0 κ ≥ 0
V τ ≤ ∑ t = τ + 1 T ( ∏ s = τ + 1 t − 1 ( 1 + κ s ) 2 ) R 2 ( Δ λ t ) 2 λ t 2 ≤ exp ( 2 ∑ t = τ + 1 T κ t ) ∑ t = τ + 1 T R 2 ( Δ λ t ) 2 λ t 2 . (65) V_\tau\le\sum_{t=\tau+1}^{T}\left(\prod_{s=\tau+1}^{t-1}(1+\kappa_s)^2\right)\frac{R^2(\Delta\lambda_t)^2}{\lambda_t^2}
\le\exp\left(2\sum_{t=\tau+1}^{T}\kappa_t\right)\sum_{t=\tau+1}^{T}\frac{R^2(\Delta\lambda_t)^2}{\lambda_t^2}. \tag*{(65)} V τ ≤ t = τ + 1 ∑ T ( s = τ + 1 ∏ t − 1 ( 1 + κ s ) 2 ) λ t 2 R 2 ( Δ λ t ) 2 ≤ exp ( 2 t = τ + 1 ∑ T κ t ) t = τ + 1 ∑ T λ t 2 R 2 ( Δ λ t ) 2 . (65) Since λ \lambda λ λ t ≥ λ τ ≥ ζ \lambda_t \ge\lambda_\tau\ge\zeta λ t ≥ λ τ ≥ ζ ∑ t Δ λ t = λ T − λ 0 = 1 \sum_t\Delta\lambda_t=\lambda_T-\lambda_0=1 ∑ t Δ λ t = λ T − λ 0 = 1 Δ λ t ≤ h \Delta\lambda_t\le h Δ λ t ≤ h
∑ t = τ + 1 T κ t ≤ R 2 ζ 3 ∑ t = τ + 1 T Δ λ t ≤ R 2 ζ 3 , ∑ t = τ + 1 T R 2 ( Δ λ t ) 2 λ t 2 ≤ R 2 h ζ 2 ∑ t = τ + 1 T Δ λ t ≤ R 2 h ζ 2 . (66) \sum_{t=\tau+1}^{T}\kappa_t \le\frac{R^2}{\zeta^3}\sum_{t=\tau+1}^{T}\Delta\lambda_t \le\frac{R^2}{\zeta^3},\qquad
\sum_{t=\tau+1}^{T}\frac{R^2(\Delta\lambda_t)^2}{\lambda_t^2}
\le\frac{R^2h}{\zeta^2}\sum_{t=\tau+1}^{T}\Delta\lambda_t
\le\frac{R^2h}{\zeta^2}. \tag*{(66)} t = τ + 1 ∑ T κ t ≤ ζ 3 R 2 t = τ + 1 ∑ T Δ λ t ≤ ζ 3 R 2 , t = τ + 1 ∑ T λ t 2 R 2 ( Δ λ t ) 2 ≤ ζ 2 R 2 h t = τ + 1 ∑ T Δ λ t ≤ ζ 2 R 2 h . (66) which gives the bound on V τ = E [ ∥ x ^ τ − y τ ∥ 2 ] V_\tau=\mathbb{E}\left[\|\hat{x}_\tau-y_\tau\|^2\right] V τ = E [ ∥ x ^ τ − y τ ∥ 2 ]
Time τ \tau τ Since λ 0 = 0 < ζ \lambda_0=0<\zeta λ 0 = 0 < ζ τ ≥ 1 \tau\ge1 τ ≥ 1 λ τ − 1 < ζ \lambda_{\tau-1}<\zeta λ τ − 1 < ζ τ \tau τ λ τ = λ τ − 1 + Δ λ τ < ζ + h ≤ 2 ζ \lambda_\tau=\lambda_{\tau-1}+\Delta\lambda_\tau<\zeta+h\le2\zeta λ τ = λ τ − 1 + Δ λ τ < ζ + h ≤ 2 ζ h ≤ ζ h\le\zeta h ≤ ζ
Lemma 5 (Trapping). If λ s ≤ 2 ζ \lambda_s\le2\zeta λ s ≤ 2 ζ ∥ x ^ s − ( 1 − λ s ) x 0 m ∥ ≤ ρ \|\hat{x}_s-(1-\lambda_s)x_0^m\|\le\rho ∥ x ^ s − ( 1 − λ s ) x 0 m ∥ ≤ ρ s ≥ 1 s\ge1 s ≥ 1 x 0 m x_0^m x 0 m
∥ x ^ 0 − x 0 m ∥ ≤ R η ( λ 1 ) . (67) \|\hat{x}_0-x_0^m\|\le R\eta(\lambda_1). \tag*{(67)} ∥ x ^ 0 − x 0 m ∥ ≤ R η ( λ 1 ) . (67) Proof. Peaking. We first show that, for any t t t λ t ≤ 1 / 2 \lambda_t\le1/2 λ t ≤ 1/2 x x x ∥ x − ( 1 − λ t ) x 0 m ∥ ≤ ρ \|x-(1-\lambda_t)x_0^m\|\le\rho ∥ x − ( 1 − λ t ) x 0 m ∥ ≤ ρ
∥ m t ( x ) − x 0 m ∥ ≤ R η ( λ t ) . (68) \|m_t(x)-x_0^m\|\le R\eta(\lambda_t). \tag*{(68)} ∥ m t ( x ) − x 0 m ∥ ≤ R η ( λ t ) . (68) Fix n ≠ m n\ne m n = m b b b λ t ≤ 1 / 2 \lambda_t\le1/2 λ t ≤ 1/2
∥ ( 1 − λ t ) x 0 n − ( 1 − λ t ) x 0 m ∥ = ( 1 − λ t ) ∥ x 0 n − x 0 m ∥ ≥ ( 1 − λ t ) b ≥ b 2 . (69) \|(1-\lambda_t)x_0^n-(1-\lambda_t)x_0^m\|=(1-\lambda_t)\|x_0^n-x_0^m\|\ge(1-\lambda_t)b\ge\frac{b}{2}. \tag*{(69)} ∥ ( 1 − λ t ) x 0 n − ( 1 − λ t ) x 0 m ∥ = ( 1 − λ t ) ∥ x 0 n − x 0 m ∥ ≥ ( 1 − λ t ) b ≥ 2 b . (69) By assumption, the distance of x x x
∥ x − ( 1 − λ t ) x 0 m ∥ ≤ ρ = b 8 , (70) \|x-(1-\lambda_t)x_0^m\|\le\rho=\frac{b}{8}, \tag*{(70)} ∥ x − ( 1 − λ t ) x 0 m ∥ ≤ ρ = 8 b , (70) and hence, by the reverse triangle inequality, its distance to any other centre is
∥ x − ( 1 − λ t ) x 0 n ∥ ≥ ∥ ( 1 − λ t ) x 0 n − ( 1 − λ t ) x 0 m ∥ − ∥ x − ( 1 − λ t ) x 0 m ∥ ≥ b 2 − b 8 = 3 b 8 . (71) \|x-(1-\lambda_t)x_0^n\|\ge\|(1-\lambda_t)x_0^n-(1-\lambda_t)x_0^m\|-\|x-(1-\lambda_t)x_0^m\|
\ge\frac{b}{2}-\frac{b}{8}=\frac{3b}{8}. \tag*{(71)} ∥ x − ( 1 − λ t ) x 0 n ∥ ≥ ∥ ( 1 − λ t ) x 0 n − ( 1 − λ t ) x 0 m ∥ − ∥ x − ( 1 − λ t ) x 0 m ∥ ≥ 2 b − 8 b = 8 3 b . (71) The normaliser cancels in the ratio of the weights, so
w n t ( x ) w m t ( x ) = exp { ∥ x − ( 1 − λ t ) x 0 m ∥ 2 − ∥ x − ( 1 − λ t ) x 0 n ∥ 2 2 λ t 2 } ≤ exp { ( b / 8 ) 2 − ( 3 b / 8 ) 2 2 λ t 2 } = exp { − b 2 16 λ t 2 } . (72) \frac{w_n^t(x)}{w_m^t(x)}
=\exp\left\{\frac{\|x-(1-\lambda_t)x_0^m\|^2-\|x-(1-\lambda_t)x_0^n\|^2}{2\lambda_t^2}\right\}
\le\exp\left\{\frac{(b/8)^2-(3b/8)^2}{2\lambda_t^2}\right\}
=\exp\left\{-\frac{b^2}{16\lambda_t^2}\right\}. \tag*{(72)} w m t ( x ) w n t ( x ) = exp { 2 λ t 2 ∥ x − ( 1 − λ t ) x 0 m ∥ 2 − ∥ x − ( 1 − λ t ) x 0 n ∥ 2 } ≤ exp { 2 λ t 2 ( b /8 ) 2 − ( 3 b /8 ) 2 } = exp { − 16 λ t 2 b 2 } . (72) The weights sum to one, so 1 − w m t ( x ) = ∑ n ≠ m w n t ( x ) 1-w_m^t(x)=\sum_{n\ne m}w_n^t(x) 1 − w m t ( x ) = ∑ n = m w n t ( x ) 0 < w m t ( x ) ≤ 1 0<w_m^t(x)\le1 0 < w m t ( x ) ≤ 1 w n t ( x ) ≤ w n t ( x ) / w m t ( x ) w_n^t(x)\le w_n^t(x)/w_m^t(x) w n t ( x ) ≤ w n t ( x ) / w m t ( x ) N − 1 N-1 N − 1
1 − w m t ( x ) = ∑ n ≠ m w n t ( x ) ≤ ∑ n ≠ m w n t ( x ) w m t ( x ) ≤ ( N − 1 ) exp { − b 2 16 λ t 2 } = η ( λ t ) . (73) 1-w_m^t(x)=\sum_{n\ne m}w_n^t(x)\le\sum_{n\ne m}\frac{w_n^t(x)}{w_m^t(x)}
\le(N-1)\exp\left\{-\frac{b^2}{16\lambda_t^2}\right\}=\eta(\lambda_t). \tag*{(73)} 1 − w m t ( x ) = n = m ∑ w n t ( x ) ≤ n = m ∑ w m t ( x ) w n t ( x ) ≤ ( N − 1 ) exp { − 16 λ t 2 b 2 } = η ( λ t ) . (73) As the weights sum to one, m t ( x ) − x 0 m = ∑ n ≠ m w t n ( x ) ( x 0 n − x 0 m ) m_t(x)-x_0^m=\sum_{n\ne m}w_t^n(x)(x_0^n-x_0^m) m t ( x ) − x 0 m = ∑ n = m w t n ( x ) ( x 0 n − x 0 m ) R ( 1 − w t m ( x ) ) ≤ R η ( λ t ) R(1-w_t^m(x))\le R\eta(\lambda_t) R ( 1 − w t m ( x )) ≤ R η ( λ t )
Trapping. Let φ t = ∥ x ^ t − ( 1 − λ t ) x 0 m ∥ \varphi_t=\lVert\hat{x}_t-(1-\lambda_t)x_0^m\rVert φ t = ∥ x ^ t − ( 1 − λ t ) x 0 m ∥ 1 − λ t − 1 = r t ( 1 − λ t ) + ( 1 − r t ) 1-\lambda_{t-1}=r_t(1-\lambda_t)+(1-r_t) 1 − λ t − 1 = r t ( 1 − λ t ) + ( 1 − r t ) ( 1 − λ t − 1 ) x 0 m (1-\lambda_{t-1})x_0^m ( 1 − λ t − 1 ) x 0 m
x ^ t − 1 − ( 1 − λ t − 1 ) x 0 m = r t ( x ^ t − ( 1 − λ t ) x 0 m ) + ( 1 − r t ) ( m t ( x ^ t ) − x 0 m ) . (74) \hat{x}_{t-1}-(1-\lambda_{t-1})x_0^m=r_t\left(\hat{x}_t-(1-\lambda_t)x_0^m\right)+(1-r_t)\left(m_t(\hat{x}_t)-x_0^m\right). \tag*{(74)} x ^ t − 1 − ( 1 − λ t − 1 ) x 0 m = r t ( x ^ t − ( 1 − λ t ) x 0 m ) + ( 1 − r t ) ( m t ( x ^ t ) − x 0 m ) . (74) Take any 2 ≤ t ≤ s 2\le t\le s 2 ≤ t ≤ s φ t ≤ ρ \varphi_t\le\rho φ t ≤ ρ λ \lambda λ λ t ≤ λ s ≤ 2 ζ ≤ 1 / 2 \lambda_t\le\lambda_s\le2\zeta\le1/2 λ t ≤ λ s ≤ 2 ζ ≤ 1/2 ζ ≤ 1 / 4 \zeta\le1/4 ζ ≤ 1/4 x = x ^ t x=\hat{x}_t x = x ^ t r t ∈ [ 0 , 1 ] r_t\in[0,1] r t ∈ [ 0 , 1 ] η \eta η ζ \zeta ζ
φ t − 1 ≤ r t φ t + ( 1 − r t ) R η ( λ t ) ≤ r t ρ + ( 1 − r t ) R η ( 2 ζ ) ≤ ρ . (75) \varphi_{t-1}\le r_t\varphi_t+(1-r_t)R\eta(\lambda_t)\le r_t\rho+(1-r_t)R\eta(2\zeta)\le\rho. \tag*{(75)} φ t − 1 ≤ r t φ t + ( 1 − r t ) R η ( λ t ) ≤ r t ρ + ( 1 − r t ) R η ( 2 ζ ) ≤ ρ . (75) Since φ s ≤ ρ \varphi_s\le\rho φ s ≤ ρ φ t ≤ ρ \varphi_t\le\rho φ t ≤ ρ 1 ≤ t ≤ s 1\le t\le s 1 ≤ t ≤ s r 1 = λ 0 / λ 1 = 0 r_1=\lambda_0/\lambda_1=0 r 1 = λ 0 / λ 1 = 0 x ^ 0 = m 1 ( x ^ 1 ) \hat{x}_0=m_1(\hat{x}_1) x ^ 0 = m 1 ( x ^ 1 ) φ 1 ≤ ρ \varphi_1\le\rho φ 1 ≤ ρ ∥ x ^ 0 − x 0 m ∥ ≤ R η ( λ 1 ) \lVert\hat{x}_0-x_0^m\rVert\le R\eta(\lambda_1) ∥ x ^ 0 − x 0 m ∥ ≤ R η ( λ 1 )
Each step moves the sampled chain part of the way towards a point within ρ \rho ρ ρ \rho ρ ( 1 − λ t ) x 0 m (1-\lambda_t)x_0^m ( 1 − λ t ) x 0 m R η ( λ 1 ) R\eta(\lambda_1) R η ( λ 1 ) x 0 m x_0^m x 0 m 1 / λ 1 2 1/\lambda_1^2 1/ λ 1 2
Theorem 1 (Weak convergence). Let q ( x 0 ) q(x_0) q ( x 0 ) N ≥ 2 N\ge2 N ≥ 2 x 0 1 , … , x 0 N ∈ R d x_0^1,\ldots,x_0^N\in\mathbb{R}^d x 0 1 , … , x 0 N ∈ R d T T T max t Δ λ t → 0 \max_t\Delta\lambda_t\to0 max t Δ λ t → 0 T → ∞ T\to\infty T → ∞ x ^ T , … , x ^ 0 \hat{x}_T,\ldots,\hat{x}_0 x ^ T , … , x ^ 0 μ θ ( x ) = μ t ∗ ( x ) \mu_\theta(x)=\mu_t^*(x) μ θ ( x ) = μ t ∗ ( x ) t t t x ∈ R d x\in\mathbb{R}^d x ∈ R d γ T > 0 \gamma_T>0 γ T > 0 γ T → 0 \gamma_T\to0 γ T → 0 T → ∞ T\to\infty T → ∞ x 0 m x_0^m x 0 m
lim T → ∞ P ( ∥ x ^ 0 − x 0 m ∥ ≤ γ T ) = 1 N . (76) \lim_{T\to\infty}P\left(\lVert\hat{x}_0-x_0^m\rVert\le\gamma_T\right)=\frac{1}{N}. \tag*{(76)} T → ∞ lim P ( ∥ x ^ 0 − x 0 m ∥ ≤ γ T ) = N 1 . (76) Consequently, the distribution of the generated sample x ^ 0 \hat{x}_0 x ^ 0 q ( x 0 ) q(x_0) q ( x 0 )
Proof. Our aim is to show that, starting at a random noise point, the sampled chain ends near each training example with probability tending to 1 / N 1/N 1/ N τ \tau τ x 0 m x_0^m x 0 m
Setup. Let ζ \zeta ζ τ = min { t : λ t ≥ ζ } \tau=\min\{t:\lambda_t\ge\zeta\} τ = min { t : λ t ≥ ζ } T T T h ≤ ζ h\le\zeta h ≤ ζ λ τ < 2 ζ \lambda_\tau<2\zeta λ τ < 2 ζ γ T = R η ( λ 1 ) \gamma_T=R\eta(\lambda_1) γ T = R η ( λ 1 ) x 0 m x_0^m x 0 m
B m = { x : ∥ x − x 0 m ∥ ≤ γ T } . (77) B_m=\{x:\lVert x-x_0^m\rVert\le\gamma_T\}. \tag*{(77)} B m = { x : ∥ x − x 0 m ∥ ≤ γ T } . (77) With ρ = b / 8 \rho=b/8 ρ = b /8 τ \tau τ
E 1 E_1 E 1 m m m ∥ y τ − ( 1 − λ τ ) x 0 m ∥ ≤ ρ / 2 \lVert y_\tau-(1-\lambda_\tau)x_0^m\rVert\le\rho/2 ∥ y τ − ( 1 − λ τ ) x 0 m ∥ ≤ ρ /2
E 2 E_2 E 2 ∥ x ^ τ − y τ ∥ ≤ ρ / 2 \lVert\hat{x}_\tau-y_\tau\rVert\le\rho/2 ∥ x ^ τ − y τ ∥ ≤ ρ /2
Inclusion. We show that E 1 ∩ E 2 ⊆ { x ^ 0 ∈ B m } E_1\cap E_2\subseteq\{\hat{x}_0\in B_m\} E 1 ∩ E 2 ⊆ { x ^ 0 ∈ B m }
∥ x ^ τ − ( 1 − λ τ ) x 0 m ∥ ≤ ∥ x ^ τ − y τ ∥ + ∥ y τ − ( 1 − λ τ ) x 0 m ∥ ≤ ρ 2 + ρ 2 = ρ . (78) \lVert\hat{x}_\tau-(1-\lambda_\tau)x_0^m\rVert\le\lVert\hat{x}_\tau-y_\tau\rVert+\lVert y_\tau-(1-\lambda_\tau)x_0^m\rVert\le\frac{\rho}{2}+\frac{\rho}{2}=\rho. \tag*{(78)} ∥ x ^ τ − ( 1 − λ τ ) x 0 m ∥ ≤ ∥ x ^ τ − y τ ∥ + ∥ y τ − ( 1 − λ τ ) x 0 m ∥ ≤ 2 ρ + 2 ρ = ρ . (78) Since also λ τ < 2 ζ \lambda_\tau<2\zeta λ τ < 2 ζ s = τ s=\tau s = τ ∥ x ^ 0 − x 0 m ∥ ≤ R η ( λ 1 ) = γ T \lVert\hat{x}_0-x_0^m\rVert\le R\eta(\lambda_1)=\gamma_T ∥ x ^ 0 − x 0 m ∥ ≤ R η ( λ 1 ) = γ T x ^ 0 ∈ B m \hat{x}_0\in B_m x ^ 0 ∈ B m
Lower bound. By the inclusion, and since P ( E 1 ∩ E 2 ) = P ( E 1 ) − P ( E 1 ∩ E 2 c ) ≥ P ( E 1 ) − P ( E 2 c ) P(E_1\cap E_2)=P(E_1)-P(E_1\cap E_2^c)\ge P(E_1)-P(E_2^c) P ( E 1 ∩ E 2 ) = P ( E 1 ) − P ( E 1 ∩ E 2 c ) ≥ P ( E 1 ) − P ( E 2 c )
P ( x ^ 0 ∈ B m ) ≥ P ( E 1 ∩ E 2 ) ≥ P ( E 1 ) − P ( E 2 c ) . (79) P(\hat{x}_0\in B_m)\ge P(E_1\cap E_2)\ge P(E_1)-P(E_2^c). \tag*{(79)} P ( x ^ 0 ∈ B m ) ≥ P ( E 1 ∩ E 2 ) ≥ P ( E 1 ) − P ( E 2 c ) . (79) We bound the two terms in turn, starting with P ( E 1 ) P(E_1) P ( E 1 )
Write c = ( 1 − λ τ ) x 0 m c=(1-\lambda_\tau)x_0^m c = ( 1 − λ τ ) x 0 m S = { y : ∥ y − c ∥ ≤ ρ / 2 } S=\{y:\|y-c\|\le\rho/2\} S = { y : ∥ y − c ∥ ≤ ρ /2 } E 1 = { y τ ∈ S } E_1=\{y_\tau\in S\} E 1 = { y τ ∈ S } y τ y_\tau y τ
q τ ( y ) = 1 N ∑ n = 1 N N ( y ∣ ( 1 − λ τ ) x 0 n , λ τ 2 I ) q_\tau(y)=\frac{1}{N}\sum_{n=1}^{N}\mathcal{N}\left(y\mid(1-\lambda_\tau)x_0^n,\lambda_\tau^2 I\right) q τ ( y ) = N 1 n = 1 ∑ N N ( y ∣ ( 1 − λ τ ) x 0 n , λ τ 2 I ) Hence
P ( E 1 ) = ∫ S q τ ( y ) d y = 1 N ∑ n = 1 N ∫ S N ( y ∣ ( 1 − λ τ ) x 0 n , λ τ 2 I ) d y = 1 N ∫ S N ( y ∣ c , λ τ 2 I ) d y + 1 N ∑ n ≠ m ∫ S N ( y ∣ ( 1 − λ τ ) x 0 n , λ τ 2 I ) d y ≥ 1 N ∫ S N ( y ∣ c , λ τ 2 I ) d y . (80) \begin{aligned}
P(E_1)&=\int_S q_\tau(y)\,dy=\frac{1}{N}\sum_{n=1}^{N}\int_S\mathcal{N}\left(y\mid(1-\lambda_\tau)x_0^n,\lambda_\tau^2 I\right)\,dy\\
&=\frac{1}{N}\int_S\mathcal{N}\left(y\mid c,\lambda_\tau^2 I\right)\,dy+\frac{1}{N}\sum_{n\ne m}\int_S\mathcal{N}\left(y\mid(1-\lambda_\tau)x_0^n,\lambda_\tau^2 I\right)\,dy\\
&\ge\frac{1}{N}\int_S\mathcal{N}\left(y\mid c,\lambda_\tau^2 I\right)\,dy. \tag*{(80)}
\end{aligned} P ( E 1 ) = ∫ S q τ ( y ) d y = N 1 n = 1 ∑ N ∫ S N ( y ∣ ( 1 − λ τ ) x 0 n , λ τ 2 I ) d y = N 1 ∫ S N ( y ∣ c , λ τ 2 I ) d y + N 1 n = m ∑ ∫ S N ( y ∣ ( 1 − λ τ ) x 0 n , λ τ 2 I ) d y ≥ N 1 ∫ S N ( y ∣ c , λ τ 2 I ) d y . (80) The remaining integral is the probability that a variable with distribution N ( ⋅ ∣ c , λ τ 2 I ) \mathcal{N}(\cdot\mid c,\lambda_\tau^2I) N ( ⋅ ∣ c , λ τ 2 I ) S S S c + λ τ z c+\lambda_\tau z c + λ τ z z ∼ N ( ⋅ ∣ 0 , I ) z\sim\mathcal{N}(\cdot\mid0,I) z ∼ N ( ⋅ ∣ 0 , I ) c + λ τ z ∈ S c+\lambda_\tau z\in S c + λ τ z ∈ S ∥ ( c + λ τ z ) − c ∥ = λ τ ∥ z ∥ ≤ ρ / 2 \|(c+\lambda_\tau z)-c\|=\lambda_\tau\|z\|\le\rho/2 ∥ ( c + λ τ z ) − c ∥ = λ τ ∥ z ∥ ≤ ρ /2
∫ S N ( y ∣ c , λ τ 2 I ) d y = P ( c + λ τ z ∈ S ) = P ( λ τ ∥ z ∥ ≤ ρ / 2 ) = 1 − P ( ∥ z ∥ > ρ 2 λ τ ) . (81) \int_S\mathcal{N}\left(y\mid c,\lambda_\tau^2 I\right)\,dy=P(c+\lambda_\tau z\in S)=P(\lambda_\tau\|z\|\le\rho/2)=1-P\left(\|z\|>\frac{\rho}{2\lambda_\tau}\right). \tag*{(81)} ∫ S N ( y ∣ c , λ τ 2 I ) d y = P ( c + λ τ z ∈ S ) = P ( λ τ ∥ z ∥ ≤ ρ /2 ) = 1 − P ( ∥ z ∥ > 2 λ τ ρ ) . (81) By Markov’s inequality applied to ∥ z ∥ 2 ≥ 0 \|z\|^2\ge0 ∥ z ∥ 2 ≥ 0
P ( ∥ z ∥ > ρ 2 λ τ ) = P ( ∥ z ∥ 2 > ρ 2 4 λ τ 2 ) ≤ 4 λ τ 2 ⟨ ∥ z ∥ 2 ⟩ ρ 2 = 4 λ τ 2 d ρ 2 ≤ 16 d ζ 2 ρ 2 , (82) P\left(\|z\|>\frac{\rho}{2\lambda_\tau}\right)=P\left(\|z\|^2>\frac{\rho^2}{4\lambda_\tau^2}\right)\le\frac{4\lambda_\tau^2\langle\|z\|^2\rangle}{\rho^2}=\frac{4\lambda_\tau^2d}{\rho^2}\le\frac{16d\zeta^2}{\rho^2}, \tag*{(82)} P ( ∥ z ∥ > 2 λ τ ρ ) = P ( ∥ z ∥ 2 > 4 λ τ 2 ρ 2 ) ≤ ρ 2 4 λ τ 2 ⟨ ∥ z ∥ 2 ⟩ = ρ 2 4 λ τ 2 d ≤ ρ 2 16 d ζ 2 , (82) using ⟨ ∥ z ∥ 2 ⟩ = d \langle\|z\|^2\rangle=d ⟨ ∥ z ∥ 2 ⟩ = d λ τ < 2 ζ \lambda_\tau<2\zeta λ τ < 2 ζ
P ( E 1 ) ≥ 1 N ( 1 − 16 d ζ 2 ρ 2 ) . (83) P(E_1)\ge\frac{1}{N}\left(1-\frac{16d\zeta^2}{\rho^2}\right). \tag*{(83)} P ( E 1 ) ≥ N 1 ( 1 − ρ 2 16 d ζ 2 ) . (83) For the second term, the complement of E 2 E_2 E 2 E 2 c = { ∥ x ^ τ − y τ ∥ > ρ / 2 } = { ∥ x ^ τ − y τ ∥ 2 > ρ 2 / 4 } E_2^c=\{\|\hat{x}_\tau-y_\tau\|>\rho/2\}=\{\|\hat{x}_\tau-y_\tau\|^2>\rho^2/4\} E 2 c = { ∥ x ^ τ − y τ ∥ > ρ /2 } = { ∥ x ^ τ − y τ ∥ 2 > ρ 2 /4 } ∥ x ^ τ − y τ ∥ 2 ≥ 0 \|\hat{x}_\tau-y_\tau\|^2\ge0 ∥ x ^ τ − y τ ∥ 2 ≥ 0
P ( E 2 c ) ≤ 4 ⟨ ∥ x ^ τ − y τ ∥ 2 ⟩ ρ 2 ≤ 4 ρ 2 exp ( 2 R 2 ζ 3 ) R 2 h ζ 2 . (84) P(E_2^c)\le\frac{4\langle\|\hat{x}_\tau-y_\tau\|^2\rangle}{\rho^2}\le\frac{4}{\rho^2}\exp\left(\frac{2R^2}{\zeta^3}\right)\frac{R^2h}{\zeta^2}. \tag*{(84)} P ( E 2 c ) ≤ ρ 2 4 ⟨ ∥ x ^ τ − y τ ∥ 2 ⟩ ≤ ρ 2 4 exp ( ζ 3 2 R 2 ) ζ 2 R 2 h . (84) Substituting the two bounds into equation (79) ,
P ( x ^ 0 ∈ B m ) ≥ P ( E 1 ) − P ( E 2 c ) ≥ 1 N − 1 N 16 d ζ 2 ρ 2 − 4 ρ 2 exp ( 2 R 2 ζ 3 ) R 2 h ζ 2 = 1 N − β , β = 16 d ζ 2 N ρ 2 + 4 ρ 2 exp ( 2 R 2 ζ 3 ) R 2 h ζ 2 . (85) \begin{aligned}
P(\hat{x}_0\in B_m)&\ge P(E_1)-P(E_2^c)\ge\frac{1}{N}-\frac{1}{N}\frac{16d\zeta^2}{\rho^2}-\frac{4}{\rho^2}\exp\left(\frac{2R^2}{\zeta^3}\right)\frac{R^2h}{\zeta^2}\\
&=\frac{1}{N}-\beta,\qquad\beta=\frac{16d\zeta^2}{N\rho^2}+\frac{4}{\rho^2}\exp\left(\frac{2R^2}{\zeta^3}\right)\frac{R^2h}{\zeta^2}. \tag*{(85)}
\end{aligned} P ( x ^ 0 ∈ B m ) ≥ P ( E 1 ) − P ( E 2 c ) ≥ N 1 − N 1 ρ 2 16 d ζ 2 − ρ 2 4 exp ( ζ 3 2 R 2 ) ζ 2 R 2 h = N 1 − β , β = N ρ 2 16 d ζ 2 + ρ 2 4 exp ( ζ 3 2 R 2 ) ζ 2 R 2 h . (85) Upper bound. The lower bound equation (85) holds for every data point x 0 m x_0^m x 0 m β \beta β m m m γ T → 0 \gamma_T\to0 γ T → 0 T → ∞ T\to\infty T → ∞ γ T < b / 2 \gamma_T<b/2 γ T < b /2 T T T B n B_n B n B m B_m B m n ≠ m n\ne m n = m ∥ x 0 n − x 0 m ∥ ≤ 2 γ T < b \|x_0^n-x_0^m\|\le2\gamma_T<b ∥ x 0 n − x 0 m ∥ ≤ 2 γ T < b b b b (46) . The events { x ^ 0 ∈ B n } \{\hat{x}_0\in B_n\} { x ^ 0 ∈ B n }
∑ n = 1 N P ( x ^ 0 ∈ B n ) = P ( x ^ 0 ∈ ⋃ n = 1 N B n ) ≤ 1. (86) \sum_{n=1}^{N}P(\hat{x}_0\in B_n)=P\left(\hat{x}_0\in\bigcup_{n=1}^{N}B_n\right)\le1. \tag*{(86)} n = 1 ∑ N P ( x ^ 0 ∈ B n ) = P ( x ^ 0 ∈ n = 1 ⋃ N B n ) ≤ 1. (86) Hence, applying the lower bound to each of the N − 1 N-1 N − 1
P ( x ^ 0 ∈ B m ) ≤ 1 − ∑ n ≠ m P ( x ^ 0 ∈ B n ) ≤ 1 − ( N − 1 ) ( 1 N − β ) = 1 N + ( N − 1 ) β . (87) P(\hat{x}_0 \in B_m) \le1-\sum_{n\ne m}P(\hat{x}_0 \in B_n) \le1-(N-1)\left(\frac{1}{N}-\beta\right)=\frac{1}{N}+(N-1)\beta. \tag*{(87)} P ( x ^ 0 ∈ B m ) ≤ 1 − n = m ∑ P ( x ^ 0 ∈ B n ) ≤ 1 − ( N − 1 ) ( N 1 − β ) = N 1 + ( N − 1 ) β . (87) Limit. Fix ζ \zeta ζ T → ∞ T\to\infty T → ∞ h → 0 h\to0 h → 0 β \beta β T T T
lim T → ∞ β = 16 d ζ 2 N ρ 2 = : β ζ . (88) \lim_{T\to\infty}\beta=\frac{16d\zeta^2}{N\rho^2}=:\beta_\zeta. \tag*{(88)} T → ∞ lim β = N ρ 2 16 d ζ 2 =: β ζ . (88) Moreover, λ 1 ≤ h → 0 \lambda_1\le h\to0 λ 1 ≤ h → 0 γ T = R η ( λ 1 ) → 0 \gamma_T=R\eta(\lambda_1)\to0 γ T = R η ( λ 1 ) → 0 (85) and equation (87) ,
1 N − β ζ ≤ lim inf T → ∞ P ( x ^ 0 ∈ B m ) ≤ lim sup T → ∞ P ( x ^ 0 ∈ B m ) ≤ 1 N + ( N − 1 ) β ζ . (89) \frac{1}{N}-\beta_\zeta\le\liminf_{T\to\infty}P(\hat{x}_0\in B_m)\le\limsup_{T\to\infty}P(\hat{x}_0\in B_m)\le\frac{1}{N}+(N-1)\beta_\zeta. \tag*{(89)} N 1 − β ζ ≤ T → ∞ lim inf P ( x ^ 0 ∈ B m ) ≤ T → ∞ lim sup P ( x ^ 0 ∈ B m ) ≤ N 1 + ( N − 1 ) β ζ . (89) The event { x ^ 0 ∈ B m } \{\hat{x}_0\in B_m\} { x ^ 0 ∈ B m } ζ \zeta ζ ζ \zeta ζ ζ → 0 \zeta\to0 ζ → 0 β ζ → 0 \beta_\zeta\to0 β ζ → 0
lim T → ∞ P ( x ^ 0 ∈ B m ) = 1 N . (90) \lim_{T\to\infty}P(\hat{x}_0\in B_m)=\frac{1}{N}. \tag*{(90)} T → ∞ lim P ( x ^ 0 ∈ B m ) = N 1 . (90) Weak convergence. Let f f f B = ⋃ n = 1 N B n B=\bigcup_{n=1}^{N}B_n B = ⋃ n = 1 N B n T T T P ( x ^ 0 ∈ B ) = ∑ n = 1 N P ( x ^ 0 ∈ B n ) → 1 P(\hat{x}_0\in B)=\sum_{n=1}^{N}P(\hat{x}_0\in B_n)\to1 P ( x ^ 0 ∈ B ) = ∑ n = 1 N P ( x ^ 0 ∈ B n ) → 1
∣ ⟨ f ( x ^ 0 ) ⟩ − ∑ n = 1 N f ( x 0 n ) P ( x ^ 0 ∈ B n ) ∣ ≤ ∑ n = 1 N sup x ∈ B n ∣ f ( x ) − f ( x 0 n ) ∣ P ( x ^ 0 ∈ B n ) + sup x ∣ f ( x ) ∣ P ( x ^ 0 ∉ B ) . (91) \left|\langle f(\hat{x}_0)\rangle-\sum_{n=1}^{N}f(x_0^n)P(\hat{x}_0\in B_n)\right|
\le\sum_{n=1}^{N}\sup_{x\in B_n}|f(x)-f(x_0^n)|P(\hat{x}_0\in B_n)+\sup_{x}|f(x)|P(\hat{x}_0\notin B). \tag*{(91)} ⟨ f ( x ^ 0 )⟩ − n = 1 ∑ N f ( x 0 n ) P ( x ^ 0 ∈ B n ) ≤ n = 1 ∑ N x ∈ B n sup ∣ f ( x ) − f ( x 0 n ) ∣ P ( x ^ 0 ∈ B n ) + x sup ∣ f ( x ) ∣ P ( x ^ 0 ∈ / B ) . (91) The first term vanishes because f f f x 0 n x_0^n x 0 n γ T → 0 \gamma_T\to0 γ T → 0 P ( x ^ 0 ∉ B ) → 0 P(\hat{x}_0\notin B)\to0 P ( x ^ 0 ∈ / B ) → 0 ⟨ f ( x ^ 0 ) ⟩ = ⟨ f ( x 0 ) ⟩ p θ ( x 0 ) → 1 N ∑ n = 1 N f ( x 0 n ) = ⟨ f ( x 0 ) ⟩ q ( x 0 ) \langle f(\hat{x}_0)\rangle=\langle f(x_0)\rangle_{p_\theta(x_0)}\to\frac{1}{N}\sum_{n=1}^{N}f(x_0^n)=\langle f(x_0)\rangle_{q(x_0)} ⟨ f ( x ^ 0 )⟩ = ⟨ f ( x 0 ) ⟩ p θ ( x 0 ) → N 1 ∑ n = 1 N f ( x 0 n ) = ⟨ f ( x 0 ) ⟩ q ( x 0 ) x ^ 0 \hat{x}_0 x ^ 0 q ( x 0 ) q(x_0) q ( x 0 )
Continuity of the Per-Time Loss
Lemma 6. Let λ : [ 0 , 1 ] → [ 0 , 1 ] \lambda:[0,1]\to[0,1] λ : [ 0 , 1 ] → [ 0 , 1 ] v θ v_\theta v θ ( x , s ) (x,s) ( x , s ) ∥ v θ ( x , s ) ∥ ≤ A + B ∥ x ∥ k \lVert v_\theta(x,s)\rVert\le A+B\lVert x\rVert^k ∥ v θ ( x , s )∥ ≤ A + B ∥ x ∥ k k ≥ 1 k\ge1 k ≥ 1 x x x s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] q ( x 0 ) q(x_0) q ( x 0 ) ℓ \ell ℓ (26) is continuous on [ 0 , 1 ] [0,1] [ 0 , 1 ]
Proof. Since x s x_s x s ( x 0 , ϵ ) (x_0,\epsilon) ( x 0 , ϵ )
ℓ ( s ) = ⟨ g ( s ; x 0 , ϵ ) ⟩ q ( x 0 ) q ( ϵ ) , g ( s ; x 0 , ϵ ) = ∥ ϵ − x 0 − v θ ( x s , s ) ∥ 2 , (92) \ell(s)=\langle g(s;x_0,\epsilon)\rangle_{q(x_0)\,q(\epsilon)},\qquad g(s;x_0,\epsilon)=\lVert\epsilon-x_0-v_\theta(x_s,s)\rVert^2, \tag*{(92)} ℓ ( s ) = ⟨ g ( s ; x 0 , ϵ ) ⟩ q ( x 0 ) q ( ϵ ) , g ( s ; x 0 , ϵ ) = ∥ ϵ − x 0 − v θ ( x s , s ) ∥ 2 , (92) with x s = ( 1 − λ ( s ) ) x 0 + λ ( s ) ϵ x_s=(1-\lambda(s))x_0+\lambda(s)\epsilon x s = ( 1 − λ ( s )) x 0 + λ ( s ) ϵ q ( ϵ ) = N ( ϵ ∣ 0 , I ) q(\epsilon)=\mathcal{N}(\epsilon\mid0,I) q ( ϵ ) = N ( ϵ ∣ 0 , I )
Continuity of the integrand (g g g Fix ( x 0 , ϵ ) (x_0,\epsilon) ( x 0 , ϵ ) λ \lambda λ x s = ( 1 − λ ( s ) ) x 0 + λ ( s ) ϵ x_s=(1-\lambda(s))x_0+\lambda(s)\epsilon x s = ( 1 − λ ( s )) x 0 + λ ( s ) ϵ s s s v θ v_\theta v θ 6 v θ ( x s , s ) v_\theta(x_s,s) v θ ( x s , s ) s s s g ( s ; x 0 , ϵ ) = ∥ ϵ − x 0 − v θ ( x s , s ) ∥ 2 g(s;x_0,\epsilon)=\lVert\epsilon-x_0-v_\theta(x_s,s)\rVert^2 g ( s ; x 0 , ϵ ) = ∥ ϵ − x 0 − v θ ( x s , s ) ∥ 2
Domination. By the triangle inequality, and since 1 − λ ( s ) 1-\lambda(s) 1 − λ ( s ) λ ( s ) \lambda(s) λ ( s ) [ 0 , 1 ] [0,1] [ 0 , 1 ]
∥ x s ∥ ≤ ( 1 − λ ( s ) ) ∥ x 0 ∥ + λ ( s ) ∥ ϵ ∥ ≤ ∥ x 0 ∥ + ∥ ϵ ∥ = : r , (93) \lVert x_s\rVert\le(1-\lambda(s))\lVert x_0\rVert+\lambda(s)\lVert\epsilon\rVert\le\lVert x_0\rVert+\lVert\epsilon\rVert=:r, \tag*{(93)} ∥ x s ∥ ≤ ( 1 − λ ( s )) ∥ x 0 ∥ + λ ( s ) ∥ ϵ ∥ ≤ ∥ x 0 ∥ + ∥ ϵ ∥ =: r , (93) where r r r s s s v θ v_\theta v θ
∥ ϵ − x 0 − v θ ( x s , s ) ∥ ≤ ∥ ϵ ∥ + ∥ x 0 ∥ + A + B ∥ x s ∥ k ≤ A + r + B r k . (94) \lVert\epsilon-x_0-v_\theta(x_s,s)\rVert\le\lVert\epsilon\rVert+\lVert x_0\rVert+A+B\lVert x_s\rVert^k \le A+r+Br^k. \tag*{(94)} ∥ ϵ − x 0 − v θ ( x s , s )∥ ≤ ∥ ϵ ∥ + ∥ x 0 ∥ + A + B ∥ x s ∥ k ≤ A + r + B r k . (94) Squaring gives, for every s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ]
g ( s ; x 0 , ϵ ) ≤ G ( x 0 , ϵ ) : = ( A + r + B r k ) 2 . (95) g(s;x_0,\epsilon)\le G(x_0,\epsilon):=\left(A+r+Br^k\right)^2. \tag*{(95)} g ( s ; x 0 , ϵ ) ≤ G ( x 0 , ϵ ) := ( A + r + B r k ) 2 . (95) The bound G G G s s s r = ∥ x 0 ∥ + ∥ ϵ ∥ r=\lVert x_0\rVert+\lVert\epsilon\rVert r = ∥ x 0 ∥ + ∥ ϵ ∥ G G G c ∥ x 0 ∥ i ∥ ϵ ∥ j c\lVert x_0\rVert^i\lVert\epsilon\rVert^j c ∥ x 0 ∥ i ∥ ϵ ∥ j c ≥ 0 c\ge0 c ≥ 0 x 0 x_0 x 0 ϵ \epsilon ϵ c ⟨ ∥ x 0 ∥ i ⟩ q ( x 0 ) ⟨ ∥ ϵ ∥ j ⟩ q ( ϵ ) c\left\langle\lVert x_0\rVert^i\right\rangle_{q(x_0)}\left\langle\lVert\epsilon\rVert^j\right\rangle_{q(\epsilon)} c ⟨ ∥ x 0 ∥ i ⟩ q ( x 0 ) ⟨ ∥ ϵ ∥ j ⟩ q ( ϵ ) q ( x 0 ) q(x_0) q ( x 0 ) q ( ϵ ) q(\epsilon) q ( ϵ )
Limit. Let s k → s s_k\to s s k → s [ 0 , 1 ] [0,1] [ 0 , 1 ] ℓ ( s k ) → ℓ ( s ) \ell(s_k)\to\ell(s) ℓ ( s k ) → ℓ ( s ) ϵ \epsilon ϵ g ( s k ; x 0 , ϵ ) g(s_k;x_0,\epsilon) g ( s k ; x 0 , ϵ ) ( x 0 , ϵ ) (x_0,\epsilon) ( x 0 , ϵ ) g ( ⋅ ; x 0 , ϵ ) g(\cdot;x_0,\epsilon) g ( ⋅ ; x 0 , ϵ ) ( x 0 , ϵ ) (x_0,\epsilon) ( x 0 , ϵ ) g ( s k ; x 0 , ϵ ) → g ( s ; x 0 , ϵ ) g(s_k;x_0,\epsilon)\to g(s;x_0,\epsilon) g ( s k ; x 0 , ϵ ) → g ( s ; x 0 , ϵ ) ( x 0 , ϵ ) (x_0,\epsilon) ( x 0 , ϵ ) 0 ≤ g ( s k ; x 0 , ϵ ) ≤ G ( x 0 , ϵ ) 0\le g(s_k;x_0,\epsilon)\le G(x_0,\epsilon) 0 ≤ g ( s k ; x 0 , ϵ ) ≤ G ( x 0 , ϵ ) k k k ⟨ G ⟩ q ( x 0 ) q ( ϵ ) < ∞ \left\langle G\right\rangle_{q(x_0)q(\epsilon)}<\infty ⟨ G ⟩ q ( x 0 ) q ( ϵ ) < ∞ ℓ ( s k ) → ℓ ( s ) \ell(s_k)\to\ell(s) ℓ ( s k ) → ℓ ( s ) ℓ \ell ℓ [ 0 , 1 ] [0,1] [ 0 , 1 ] □ \square □
