Finite-Time Analysis of Discrete-Time Stochastic Interpolants
Authors: Yuhao Liu
Yu Chen
Rui Hu
Longbo Huang
Venue: ICML 2025 poster (2025)
Keywords: Stochastic Interpolants
Diffusion Models
Primary area: probabilistic_methods->gaussian_processes

Abstract: The stochastic interpolant framework offers a powerful approach for constructing generative models based on ordinary differential equations (ODEs) or stochastic differential equations (SDEs) to transform arbitrary data distributions. However, prior analyses of this framework have primarily focused on the continuous-time setting, assuming perfect solution of the underlying equations. In this work, we present the first discrete-time analysis of the stochastic interpolant framework, where we introduce a innovative discrete-time sampler and derive a finite-time upper bound on its distribution estimation error. Our result provides a novel quantification on how different factors, including 
the distance between source and target distributions and estimation accuracy, affect the convergence rate and also offers a new principled way to design efficient schedule for convergence acceleration. Finally, numerical experiments are conducted on the discrete-time sampler to corroborate our theoretical findings.

Finite-Time Analysis of Discrete-Time Stochastic Interpolants
Yuhao Liu
Yu Chen
Rui Hu
Longbo Huang
Abstract
applications. including probabilistic forecasting (Chen al., 2024b), image generation (Ma et al., 2024; Albergo et al., 2024), and sequential modeling (Chen et al., 2024a).
The stochastic interpolant framework offers a powerful approach for constructing generative models based on ordinary differential equa- tions (ODEs) or stochastic differential equations (SDEs) transform arbitrary data distributions. However, prior analyses of this framework have primarily focused on the continuous-ting ting, assuming a perfect solution of the under- lying equations. In this work, we present the first discrete-time analysis of the stochastic inter- polant framework, where we introduce an innova- tive discrete-time sampler and derive a finite-time upper bound on its distribution estimation error. Our result provides a novel quantification of how different factors, including the distance between source and target distributions and estimation ac- curacy, affect the convergence rate and also offers new principled way design efficient schedules for convergence acceleration. Finally, numerical experiments are conducted on the discrete-time sampler to corroborate our theoretical findings.
Despite its potential in real-world applications, there re- mains a gap between the theoretical analyses and practical implementations of stochastic interpolants. In practical sce- narios, instead of perfectly solving the underlying equations, one only access learned estimator for finite number of time steps, which necessitates the use of discrete-time samplers to simulate the true continuous generation pro- cess. However, previous analyses have largely focused on continuous-time generation, assuming perfect solutions to the underlying equations. This leads to a crucial question for bridging the gap:
set-
What is the convergence rate of discrete-time stochastic interpolant, and how to enhance its performance algorithmically?
Similar problems have been studied in the theories of dif- fusion models, and most results were derived based on Girsanov-based methods in SDE analyses, which reduce the problem to providing upper bounds on the discretization errors. Specifically, existing analyses on the discretization errors can be mainly categorized into two types. The first type partitions the error into space-die ciaee-dicrettzztionn and time- discretization. Among them, Lee et al. (2022) and Chen et al. (2023d) assume a uniform Lipschitz constant on the score function, while Chen et al. (2023a) do not, but they all utilize the Markovian property and the Gaussian form of the diffusion process to obtain their results. The sec- ond type uses Itô's calculus obtain upper bounds, such as Benton al. (2024), who adapt existing results from stochastic localization to produce tight bounds by finding the equivalence between two methods.
1. Introduction
Stochastic interpolants (Albergo & Vanden-Eijnden, 2023; Albergo et al., 2023) provide general framework for con- structing continuous mappings between arbitrary distribu- tions. This framework draws inspiration from flow-based and siffusion-based models, which generate samples by con- tinuously transforming data points from base distribution to target distribution via learned ordinary differential equa- tions (ODEs) or stochastic differential equations (SDEs).
Within the stochastic interpolant framework, one obtains learnalle ODEs or SDEs that transport data by defining an interpolation between data points sampled from different distributions. This framework offers significant design flex- ibility and has demonstrated promising results in various
However, the aforementioned ideas do not apply to stochas- tic interpolants due to the following key difference: the stochastic interpolant framework in consideration has dis- tinct structure introduced by random interpolation between two distributions instead of a linear combination of one dis- tribution with Gaussian, destroying the Markovian property. This difference not only necessitates novel analysis for the discretization errors of score functions but also requires ad- ditional analysis bound the discretization errors for the
'IIS, Tsinghua University, Beijing, China. Correspondence to: Longbo Huang <longbohuang wessinguu.cduuco
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Finite-Time Analysis of Discrete-Timg Stochastic Interpolants
velocity function, which arises from the general interpola- tion function introduced in this context.
(2023) investigate the impact of using estimators instead of the true velocities in the equations.
To tackle the above challenges, in this work, we offer the first finite-time convergence bound in Kullback-Leible (KL) error for the SDE-based generative model within the stochas- tic interpolant framework. Our result presents a novel anal- ysis building on existing Girsanov-basee techniques. In the analysis of discretization errors, one key highlight of our approach is modeling the evolution of discretized terms via stochastic calculus. This allows us to decompose the dis- cretization error into components linked to derivatives of conditional expectation. Notably, we leverage the Gaussian latent variables embedded within our stochastic interpolants, enabling the explicit representation of these derivatives as conditional expectations, and hence providing key solution to the challenges.
Following the stochastic interpolants framework, several works have focused on specific applications. Albergo et al. (2024) utilize the framework to develop novel data cou- pling methods, addressing image generation tasks such as in-painting and super-resolution. Chen et al. (2024b) and Chen et al. (2024a) adapt the conditional generation frame- work with stochastic interpolants to tackle future state pre- diction and sequential modeling problems, respectively.
Convergence Analysis of Diffusion Models Numerous results have been established on the convergence rates of diffusion models under various data assumptions (Bortoli, 2022: Lee al., 2022). Notably, Chen et al. (2023d) employ an approximation argument to apply Girsanov's theorem in scenarios where the Novikov condition does not hold. Based on this analysis, Chen et al. (2023d) and Chen et al. (2023a) provide error bounds assuming Lipschitz score functions. Chen et al. (2023a) also develop a KI. error bound with- out requiring Lipschitzness assumptions, leveraging early stopping. This bound is subsequently improved by Benton et al. (2024), achieving a E² KL error in Ô ( (dlos"(16))
Our contributions. The main contributions of our paper follows.
(i) This work presents the first finite-time convergence bound for the SDE-based generative model within the stochastic interpolant framework. Specifically, we formu- late the discrete-time sampler using the Maler-Ma scheme and derive a general error bound on the generative process, which notably does not require Lipschitz assump- tions on the score functions or velocity functions. This setting aligns with recent analyses of score-based diffusion models that relax Lipschitz assumptions on the score func- tions, such as those by Chen et al. (2023a) and Benton et al. (2024).
steps, which exhibits near- linear dependence on the dimen- sion d. In addition to convergence rate analysis, several works have focused on problems such as score approxima- tion (Chen et al., 2023b). improved DDPM samplers (Liang et al., 2024; Li et al., 2024b;a) and ODE-based methods (Chen et al., 2023c).
3. Preliminaries: Stochastic Interpolants
(ii) We propose a novel schedule of step sizes and rigorously bound the number of steps required to achieve an s² KL- error. In the specific case where the base distribution pa is Gaussian, where our setting reduces to the standard diffusion model, our bound achieves the same order of dependence as that by Chen et al. (2023a).
In this paper, we consider continuous-time stochastic pro- cesses that bridge any two arbitrary probability distributions in finite time. Formally, given two probability distributions Po and p1 in Rd, stochastic interpolant (Albergo et al., 2023; Albergo & Vanden-Fijnden 2023; Albergo et al., 2024) is a stochastic process defined as:
(iii) We implement the sampler with our proposed schedule and conduct a comparison against using uniform step sizes. Our results validate the theoretical findings and demonstrate the superior performance of our schedule when no additional regularity conditions are assumed.
It I(t, + (t)z, t t
(I)
where / is twice-continuoosly differentiable interpolation function satisfying the boundary conditions [(0, zg, 21)
zo and [11, zo, 21) I1, and there exists constant C >>> 0
such that for all E [0. 1] and 2o. x1 E Rdd
2. Related Works
0, xo, 11 < C1 x ||-
(2)
Stochastic Interpolants The concept of stochastic inter- polants introduced by Albergo & Vanden-Eijnden (2023), establishing a framework for constructing generative models based on continuous-time normalizing flows. Building upon this foundation, Albergo et al. (2023) extend the framework by incorporating Gaussian noise into the interpolant, ef- fectively unifying flow based and diffusion- based methods. Both Albergo & Vanden-Eijnden (2023) and Albergo et al.
Here 7()) a time-dependent scale function with y())²
C² 1), 7(0) = 7(1 = 0, and 7(t) > 0 for t E [0, 1).
This definition indicates that ar (()) is bounded by a constant. (I0, is drawn from a joint measure // with marginals Po and Pl. ie.. (d = vddoo Rd) and P1 (dæ1) = v(Rd, dr1). 2 ~ (N, is a standard Gaus- sian variable independent of (zo,21)
2

---

Finite-Time Analysis of Piscrete-Time Stochastic Interpolants
In the definition (1), [(1, #1; represents the interpolation component, while 7()) introduces Gaussian latent term crucial for subsequent analysis. We denote the density of Ie by p(t,-) -) or simply p(t). According to the construction, the stochastic interpolant satisfies p(0) = Po and p(1) = p1- This framework allows for a wide range of interpolation functions I [1,, zi; xi) and scale functions 7(). offering sig- nificant flexibility design.
where (0, Ia) is another standard Gaussian variable independent of ø1- Diffusion models (Song et al., 2021)
employ the Omstein-Uhlenbeck (OU) SDE:
dY, = YY,ds s + v2WW,. Yo ~ Pdata
which gradually adds noise to the data distribution Pauta- Given Yo. Y, can be written as
Stochastic interpolants provide a framework for gen- erative modeling through stochastic differential equa- tions. As shown by Albergo et al. (2023), when (1000,,tt To, x1)ll* and (( -10f are bounded, the solution to the following forward SDE
Y e "Yo + e1-6-212 Z N~,
Therefore, if we choose I1 ~ Pdata in the stochastic inter- polant, Y, and ze-- have the same distribution.
Previous Theoretical Results For SDE-based generative models, Albergo al. (2023) provide the following KL enror bound when an estimator (t, is used instead of the true drift term (t, x in the SDE. This bound, which can also be derived using Girsanov's Theorem (Chen et al., 2023d; Oko et al., 2023), is given by:
dx," = bf(t,x + ,2e(t)dW,,,xo Xo Po
(3)
satisfies X ~ p(t) for all E [0, 1]. Here E Clo, is non-negative function, and the drift term by is defined as
(t, b(t, + c(t)s(t,z)
(L(P(()I(((T)) S L. / ((x)(t,a) 4c
b(t,,)) Bf |x+ xi] |1,, Ho, 21) ) + +(1==//0 = a):
(4)
- (t, x)) ((t x ddddt.
((,,x) V Vlogp((,z)) -7 (1) a].
This inequality establishes an upper bound on the distribu- tion estimation error in terms of the error in estimating the drift function by (t,, xf"). This estimation error is evaluated with respect to the true underlying density p(t,
In the definition (4), at) is the well-known score fune- tion, and b(t, represents the mean velocity field of (1) (following the notations of Albergo et al. 2023). This im- plies that a process starting from Po and evolving according to the forward SDE (3) will have density p(t) at time f. Con- sequently, at time 1 = 1, the process will have the desired target density P1. This establishes a stochastic mapping from Po PI, providing a foundation for generative model- ing.
The primary limitation of the existing results is the assump- tion that the SDEs can be solved exactly (e.g.. Chen et al. 2024b; Albergo et al. 2023). However, obtaining exact solutions is often challenging in practice, leading to the use of discrete-time samplers for estimating these solutions. Yet, when an SDE is discretized, discretization error causes distribution estimation error, which ultimately invalidates previous results. Moreover, the choice of discretizations can have a significant impact on the convergence of the dynam- ies, (see, e.g., Wibisono et al. 2016), leaving the design of optimal discretization methods largely open.
Following Albergo et al. (2023), we further introduce the velocity function vtt,x)) as:
utt, x) = [t, zo. =1) = x]]
(5)
= =b(t,x) x) + (t,
Both b(t,z)) = - -(t))))(()))()))) æ) and by (t, = b(t,x)) + ((t)s(t,,)) .²) are linear combinations of v(t, and
4. Main Results
((t,z). The function c(t) controls the level of randomness in the mapping from Po to Pl. When el) = 0 the SDE reduces to an ODE. We assume e(t) e is a constant without loss of generality, similar Albergo al. (2023) and dos Santos Costa et al. (2024).
In this section, we present a novel analysis for the discrete- time stochastic interpolant framework. Specifically, we focus on the following formulation: given a schedule (tx) S [0, 1] where to < t < ... < Ix-1 < INx we define an estimated process using the following SDE:
Connection with Diffusion Models. Consider the special
dx F = bytte, Xt )t VedWe, E (tx, (6)
case where Zo and I1 are independent, with Do ~ (/ Ia). Let [t, zo, x1) = (1 1 t)20 + tx, and 7tt) / //8(1 - t). Then, the stochastic interpolant can be expressed as
In practice, we can express this as:
XF f4s1 = + (1++1 (1)6(((e, xF)
(7)
xt = tzı + v f2
+ /2eete+1 - -ta)en
E EN Ia)
3

---

Finite-Time Analysis of Eiscrete-Time Stochastic Interpolants
for k: = 0, 1....,, N Here (1, x represents an esti- mator of the true drift term by. Equation (6), or equivalently (7), corresponds to the Euler-Maruyama discretization of the continuous tottuuuuustmmeeeeee SDE (Chen et al., 2023a;b). In this paper, we refer to (6) as the estimated SDE, while (3) is referred to as the true SDE.
N
+
(fx+1 1xx)
k=
M2 + 7/2
0//0e + + 2 E 20 21
cd
N-1
Σ
(tx+1 to 1 dd v VEll,oo - 21114 + 3/ 2d
Below, we present our analysis for the discrete-time stochas- tic interpolant. We begin by introducing the main assump- tions, which will be crucial for bounding the error between the estimated distribution and the true target distribution.
Here the notation f S denotes f Ogg).
Theorem 4.3 provides the first finite-time error bound for the discrete- time stochastic interpolant framework (3), i.e., SDE (6). It explicitly quantifies the impact of the initial distribution mismatch (i.c., (L(p(to) ((((t) and the bf estimation error (i.e., eb demonstrates their dependence the choice of latent scale (() and the time discretization schedule {4x ) Notably, the bound offers novel theoret- ical explanation for how the convergence behavior depends on the distance between the source and destination distribu- tions, as reflected in the terms involving E| 2 I| with p = 4 and = 8.
Assumption 4.1. The joint measure y defined in the stochas- tic interpolants (1) satisfies
E (mr )ou
| - 2111* < xc,
and the interpolation function is such that
E 1
S M2 < oo, E [].
(10
The first moment bound assumes that the initial and target distributions, Po and Pl. are not excessively far apart. In fact, the inequality (2) further implies that B] [t., To, 21 < oo for any i E [0, 1]. The second part of the assumption ensures that the time derivative of the interpolation function does not exhibit significant variations. Assumption 4. is similar to previous assumptions on stochastic interpolants, with the exception of the first part, which utilizes the eighth moment instead of the fourth moment (see Albergo et al. 2023 or Appendix A).
Now we explain the terms in Theorem 4.3.
The terms (l4+1 - 433 M2 + 7% 2d El x2| 8
and
(l++1 14 1% 2 'd R| - x 11 quantify the discretization error associated with the velocity function v(t, x) (Equa- tion (5)), which is component of the drift term by (f(,, 2)). Notably, the distance of form B||220 z1||" I| is involved here, highlighting the influence of the distance between the source and target distributions on the discretization error.
Conversely, the terms (t&+1 - 2x) dd and (tx+1 fx) )x) dd quantify the discretization error arising from the score function 2.). This component of the discretization error exhibits stronger dependence on the latent scale 7() and the data dimension d. Specifically, assuming sufficiently small step sizes, the dependence of the score discretization error on (() is 7% (if we assume sufficiently small step sizes), which aligns with the findings for diffusion models (Chen et al., 2023a; Benton et al., 2024).
Assumption 4.2. The estimator by satisfies
Σ (tu+1 - to (1) -
S Ebp!
where the expectations is taken over It, p(tx)-
Assumption 4.2 assumes that we have sufficiently accu- rate estimator for the drift term 6p(t, at the discretized time points. This assumption is analogous to common as- sumptions employed in the theoretical analysis of diffusion models (Benton et al., 2024; Chen et al., 2023a).
Since (0) = 711) O. the discretization error will be- come unbounded if we were to simulate the estimated SDE (6) from to 0 to IN = 1. To address this, we choose 0 < to < IN < 1 to ensure that 5% is lower bounded, thereby maintaining a finite discretization error bound in Theorem 4.3. Under this approach, the SDE is simulated within the interval (l,, (N), and an estimation of p(tr) is obtained instead of P1. This is acceptable when fy is suf- ficiently close to 1, as p(tw) will be sufficiently close to Pi (e.g., in terms of Wasserstein distance). This practice of choosing iN < 1 is analogous to the early stopping tech- nique commonly employed in diffiusion models (Song et al., 2021; Chen et al., 2023a; Benton et al., 2024).
Now we are ready to present our main theorem.
Theorem 4.3. Suppose we start with an initial distribution p(to) and evolve the process according to the estimated SDE (6) with = O(1) until time be the distribution obtained at time = ty. Denote the ground truth marginal distributions by {o(t))eeto,1) and define 7t mintggta.teal (f). We have under Assump- tions 4.1 and 4.2 that:
t-- Let p(tx)
(L(((t>)))((t)) & (L(O(to)ll((to)) + tog
The term (l.())))))))((tt)) quantifies the effect of choosing
4

---

Finite-Tinee Analysis of Discrete-Time Stochastic Interpolants
slightly different base distribution. As discussed earlier, we typically choose tn O, and in many cases, the true hase distribution p(to) may not be readily available. This bound theoretically supports the use of a similar base distribution p(4)) as an approximation for the true base distribution.
The second term on the right-hand-side corresponds the estimation error of br(t,z), and its summation can be bounded by E according to Assumption 4.2. The first term, on the other hand, represents the discretization error associated with (f(t, and requires further analysis.
Finally, the term ey accounts for the error in estimating the drift term by(t, z².. Compared to previous continuous- analyses of the stochastic interpolant framework, which typ- ically measure the estimation error by averaged error over the entire time interval (Albergo & Vanden-Eijnden, 2023; Albergo et al., 2023), our analysis evaluates the esti- mation error using weighted average of the errors at the discretized time points.
Step Two: Bound the Diseretization Error. We now bound the discretization error above. A central tool in this part is the Itô's formula. By applying Itô's formula, we obtain:
[
X,,
The bound provided by Theorem 4.3 explicitly depends on the choice of latent scale (t) and the time schedule { This dependence can be leveraged to assess the computational complexity for given time schedule under specific choice of (t). In Section 5, we will develop a time schedule that achieves a fast convergence rate.
+
Vbr(s, by(s, bs x ds
(8)
S." [" V2,Vbr(s, dW..
+
(br(ssx;))d
We now provide a proof sketch for Theorem 4.3.
While the application of Itô's formula is analogous to that of Benton et al. (2024), we refrain from eliminating the three linear terms due their more complex forms in the context of stochastic interpolants. Instead, we apply Jensen's in- equality the integrals with respect to time and apply It6's isometry (Le Gall 2016, Equation 5.8) on the integral with respect to Brownian motion, so that we can bound the term by the derivatives of by (t, x) (i.c., terms like a,b x) and V bt,,t z),, see Lemma C.I).
Proof Sketch of Theorem 4.3 The proof of Theorem 4.3 contains two key steps. In step one, establish bound the KL divergence due to discretization error in the drift term (1, 2) of the SDE, based on Girsanov's theorem. Then, in step two, we exploit special structure of the by (t, x²) by expressing its derivatives as conditional covariances, en- abling the application of relevant expectation inequalities and eventually bounding the discretization error.
Since by (t)) can be expressed as a linear combination of v((,,r)) and s(t, ) it remains to bound the derivatives of both v(t, x and s(t, (t), respectively. Note that v(t, x) and s(t, .)) can be written as the conditional expectations of 0, and -- = _-_ given o, = x. To bound the derivatives of these conditional expectations, we employ the following key equality:
Step One: Bounding the KL-divergence with Discretiza- tion Error. Leveraging the results provided by Chen et al. (2023d) (see Proposition C.2), which are derived using Gir- sanov's theorem, we obtain the following bound:
(L(p((>)ll((W))
<
(L(p(t))ll((t)) - (L()))
= (L((((o)l(((to)
O,Eifl = =
E 2 x]]
Initialization emvor
+ +ovv(f. -112/=11 x).
Bllbb((, - by((t, Xx,
4e
Here a can represent either or t. This equality crucially relies on the Gaussian latent term >(t)2 introduced in the stochastic interpolant framework. This generalizes the re- sult for ((1,,) x) = V log p(t, = - - ax){æ; = x] in diffusion models, as found in previous works (see, e.g.. Bortoli 2022; Benton et al. 2024). We apply this equality extensively and derive bounds for both s(t, a:) and v(t, x)), where the function v((,,x) does not appear or appears in much simpler form (such as x) in the context of diffusion model theories. Subsequently, we apply a series of inequali- ties to ultimately bound the expectation over σ₁. Detailed derivations and proofs can be found in
where P and Q represent the path measures of the solutions to the true SDE (3) and estimated SDE (6), respectively, both with the same initial distribution p(to). Applying the triangle inequality yields:
Billbr (t, x - by (tx, )12) < 2 B[ (1, ) - by (4x, X 112]]
Discretization error
+ 2 2.EEllbb x bol 1P
Estimation emor
5

---

Fime Analysis of Discrete- Time Stochastic Interpolants
5. Schedule Design for Faster Convergence
Proposition 5.1. Consider the same settings as in Theo-
rem 4.3. Suppose h&g = -4+1 -o---gg b2 = 0(152) c= (1) and
In Theorem 4.3, we provide an upper bound on the KL divergence from the target distribution to the estimated dis- tribution for a general class of SDE-based generative models. Since the bound depends the choice of latent scale (tt) and schedule {4x J we are able to carefully design time schedule for a given latent scale, thereby achieving provably bounded error within a minimum number of steps.
h= 0(5). Then, we have
KL((O(t))l)((x)) - s8, + =KL(p(to)l(((to)
+ hdd Bl xill d
Proposition 5.1 provides the KL error bound when the step sizes is chosen so that the 7-terms canceled.
Specifically, we consider the common choice of latent scale in stochastic interpolants, (t) Vat(1 -t), which is first introduced in Albergo et al. (2023). This choice is equivalent to changing the definition
Corollary 5.2. Using Val(1 - L) and the time sched- ule defined above, suppose that KL(p(to)li((to) S s² and eip S c..?. Furthermore, assume that c = ((1) and h = 0(2) Then, under the same settings as in The- orem 4.3, the total number of steps required to achieve = O(=²) is:
Ft [t,, To, .1) + 7t)=
to
Z3 = [(t, zo. 21) + VadB,,
N = 0 { { E2
where B, is a standard Brownian bridge process independent of (.r. xi). For this 7(t,, we present the following time schedule to optimize the sample complexity.
xu - xn 1
to - tNN)
t lo?
to - (N)
Exponentially Decaying Time Schedule As suggested by Theorem 4.3, smaller steps need to be taken in order to balance the error terms. Moreover, to exactly cancel the y-terms, we need h4 = 0(22) where & is defined in Theorem 4.3, Hence, we propose an exponentially decaying time schedule inspired by the approach of Benton et al. (2024). Specifically, we first select a midpoint t 1. Let h (0, 1) be a parameter that controls the step size. We then define the time steps as follows:
Corollary 5.2 provides the computational complexity of sampling data using the forward SDE. For a fixed er- ror bound E, the complexity scales proportionally to e-2. We can further decompose the complexity into distance-related complexity and Gaussian diffusion com- plexity. Here O V x || [a(1-tx] is the distance-related complexity representing the number of steps required to achieve a sufficiently small discretiza- tion error associated with the velocity function v(t, 2).. o d (w)--w))) is the Gaussian diffusion com- plexity representing the number of steps required to achieve a sufficiently small discretization error associated with the score function s(t, z).
1 h1 b))--=1
M k Z M.
tx
111(1 h))-
This leads to
2 - h) M-
& k M.
4
(1-
We briefly explain how to obtain this complexity. First, given desired number of steps N, we select
The parameter determines the overall scale of the step sizes. smaller results in a finer discretization of the time interval.
1
h - N log 1n
in(1-(N))
Let h4g = 4A+11 - 1a denote the step size at the k-th step. We observe that
to achieve the specified number of steps. Since hy = (15hh), we have:
hg = (h (t,, 1 tx+1 1)) = O
N
which satisfies the condition of canceling the -tremms. More- over, the total number of steps is given by
Σ
M2 + +7,%%00
6d3 0,8 + + 2d Bl x 11$
S 3 +12 1M2 + d E xN x
log(1 (1(4) + loogl1(111 IN))
N = o
1og(1/(1 -h)
and
0
h 11-11o log
(12d2 + haghd / El 21 l1²)
1o - LN)
Now we can provide the following bound:
< 2d + hdd 2o x 11.
6

---

Sinite-Time Analysis of Discrete-Time Stochastic Interpolants
By substituting the chosen value of h for the given N into Theorem 4.3, can derive the stated complexity bound.
0.9
0.999
Real Densities
Comparison to Uniform Schedule. To highlight the benefits of our proposed exponentially decaying time sched- ule, compare it with natural uniform schedule that satisfies h&g to
Estimated with SDE
N 2 N. We further assume the ideal
case where b = 0 and p(to) = p(to) in our analysis.
Figure I. An illustration of the interpolants. We choose
[t, 20, m1) (1 t)ro (xı and 7() v /20 lj. The first row of graphs shows the densities given by (1). The second row of graphs shows the estimated densities using SDE (6), where the estimator by is learned by neural network.
According to Theorem 4.3, the error bound for the uniform schedule given by
N-1 (M2 + + "d² + 7/x dy 20 x1 11a)
For diffusion models with an early stopping time ö, Chen al. (2023a) established a complexity bound of ( log" (t)). By setting 8 = tN in our anal- ysis, we recover the same complexity bound as that ob- tained for diffusion models. While Benton et al. (2024) further improves the complexity bound for diffusion mod- els to Ô (E dd (t)) by leveraging techniques from stochastic localization, these techniques heavily rely on the Gaussian structure of diffusion models and cannot be di- rectly applied to the more general stochastic interpolant framework.
+
(T lel2 + 7 2 B ID x1 1t.
K=
Since -2 = @minn t++1)) ), and noting that
0.5 Pdt
(o(log(1/)),, (0(6-(e-1)),
p=1 1
p p>1
for uniform schedule, the overall error bound becomes:
kL(p(tx)l((tt))
Other Choices of (t). In addition to the commonly used 7(1) = Val(1 (), our framework can readily be extended to analyze other choices of xt). In Appendix C.6, we present an analysis for 2² = (1 s)²s, which is equiva- lent to the definition in Chen et al. (2024b). We show that the proposed time schedule Appendix C.6 also outperforms the uniform schedule in terms of computational complexity, demonstrating the effectiveness of our schedule design.
1
0
E No
N
to(1 IN)
1
d²
tu tN)
Consequently, the complexity of using a uniform schedule is given by
N = 0 0 log
1
d, B
B|
x1ll
6. Numerical Experiments
to tNl
+
to tN) d2
1
)
In this section, we conduct experiments to validate our the- oretical results. We implement the discretized sampler as defined in Equation (7), and evaluate its performance on on two-dimensional datasets (primarily from Grathwohl et al. 2019) and Gaussian mixtures. The experiments focus the following three aspects: (i) the convergence rate using the exponentially decaying schedule, (ii) the effect of choosing different Po as base densities, which is reflected by the distri- bution distance terms in our bound, and (iii) the dependence of the error bound on d.
which exhibits a higher computational complexity compared to the proposed exponentially decaying schedule.
Comparison to Diffusion Models Results. By setting I[t, Tu, _1) (1 t)zy + tz1, 7()) = 22 t), To Po = (N( and assuming that un and æ1 are independent, the stochastic interpolant reduces to x, = VI-f== + for some (0, Ia). which fits the dif- fusion model setting (Song et al., 2021). Assuming that the fourth moment of P1 is bounded by constant (see Ap- pendix C.5 for details), the complexity of our approach simplifies to
We employ 20, / 22t(1 and c in our experiments. Figure presents visualization of the interpolants and the estimated densi- ties generated using the forward SDE. As we can see in Figure 1, the density defined by the stochastic interpolant progressively changes from the checkerboard density to the spiral density, and the estimated density given by SDE (6)
tx + (1 t)æo, 7t)
N N=
288 2
(5
log
)
1
1 1-
7

---

Finite-Time Analysis of Discrete-Ting Stochastic Interpolants
=
N 36
N = N = 118 244
rate the superior convergence performance of exponentially decaying step sizes.
Exponential
Effect of Different Distribution Distances Second, we investigate the impact of different source densities (po) and couplings (v) on the complexity of the generation process while keeping the target density (pt) fixed. The densities are shown in 2b, where we have two source densities, namely "A" and "B". Each "block" in Pu is coupled with the corre- sponding "block" P1 the same vertical position.
Uniform
(a) An illustration of generation results using different sched- ules.
Po
N 18 N = 56 N 118
Figure 3b shows the estimated TV distances between the generated data distribution and the target distribution for both scenarios. For both choices of Po. we utilized the expo- nentially decaying step size schedule. The results demon- strate that the generation process converges faster when the source density (pu) is closer to the target density (p1) un- der the specified coupling (v). In contrast, the generation process converges slower when the source density is farther away from the target density. This observation highlights the influence of the initial distribution and the coupling structure on the overall convergence behavior.
A
B
(b) view of different pu and their effects the conver- gence rate.
Figure 2. A visualization of experiments.
KL divergence vs steps
KL divergence us steps
Eaponential Unitorm
Test on d-dimensional Gaussian Mixtures Next, we compare the performance of the sampler under different dimension d. The source and target distribution are chosen as Gaussian mixtures, as in this case the drift by (t,x) has analytical form (Albergo et al., 2023). The comparison is shown in Figure 4.
KL. divergence
divergence
Steps
Steps
(a) Different schedules.
(b) Different and
divergenre vs steps
divergence vs dimensizn
Figure 3. Estimated KL divergences. The æ-axis refers to the num- ber of steps, while the y-axis refers to the empirical KL. divergence between target distribution p(tx) and estimated distribution p(tx). Figure 3a compares the exponentially decaying schedule (red line) with the uniform schedule (green linc). Figure 3b compares differ- ent settings of Po and (sctring A: red line; setting green linc).
d+2
N=118
N-56
< divargence
d-10
N-244
d=30
N=:16
0-50
dimension
(a) Convergence for different d.
(b) Error for fixed N.
well tracks the change of the real density.
Figure 4. The impact of dimension d. Figure 4a shows the con- vergence for different d. Figure 4b compares
Comparison of Different Time Schedules We now com- pare the performance of different schedules, namely, those proposed in Section 5 and the uniform step sizes. The task involves transforming from a "checkerboard" density to "spiral" density. As illustrated in Figure 2a, employing ex- ponentially decaying step sizes results in about 10x faster convergence of the target density compared to using uniform step sizes.
error for different d under fixed number of iterations N.
The upper bound of the KL error provided by our theory is Odd²), but the empirical KL error evaluated in this ex- periment grows almost linearly w.r.t. d. This gap could be due to several reasons. For example, there might be some special properties of Gaussian mixtures which do not hold for general distributions, or there simply exists a sharper bound that have not found. Filling this gap would be an interesting direction for future research.
To quantitatively assess this, we estimate the KL divergence between the target density and the generated densities using sampled data points, and we put the details of the estimation of KL divergence in Appendix D. The lower bound observed in the estimated distances attributed to the estimation er- ror =i, and the inherent randomness in the TV distance estimation process. Both Figure 2a and Figure 3a corrobo-
7. Conclusion and Future Directions
This paper provides the first discrete-time analysis for the SDE-bbsed generative models within the stochastic inter-
8

---

Finite-Time Analysis of Discrete-Time Stochastic Interpolants
polant framework. We formulate a discrete-time sampler using the Fuler-Maruyama scheme estimate the target distribution by leveraging learned velocity estimators. We then provide an upper bound on the KL divergence from the target distribution to the estimated distribution. Our result provides a novel quantification on how different factors, in- cluding the distance between source and target distributions v / z1 I| and the desired estimation accuracy e?, affect the convergence rate and also offers new principled way to design efficient schedule for convergence accelera- tion. Finally, we also conduct numerical experiments with the discrete-time sampler, which validates our theoretical findings.
via stochastic localization. In The Twelfth International Conference on Learning Representations, 2024.
Bortoli, V. D. Convergence of denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022.
Chen, H., Lee, H.,, and Lu, J. Improved analysis of score- based generative modeling: User-friende bounds under minimal smoothness assumptions. In International Con- ference on Machine Learning, 2023a.
Chen, M., Huang, K., Zhao, T., and Wang. M. Score approx- imation, estimation and distribution recovery of diffusion models on low-dimensions data. In International Con- ference on Machine Learning, 2023b.
Future research avenues can fruitfully explore the enhance- ment of convergence bounds, with a particular focus on addressing the dependency the dimension d. Notably, diffusion models are demonstrated by previous works to exhibit near d-linear convergence rates, indicating the po- tential for improvement. Another direction is to investigate strategies for refining the sampling algorithm to attain con- vergence rates superior to the currently observed O(s-²) Furthermore, the finite-time convergence phenomenon of ODE-based generative models within the context of the stochastic interpolant framework warrants more compre- hensive investigation.
Chen, S., Chewi, S., Lee, H., Li, Y., Lu, J., and Salim, A. The probability flow ode is provably fast. Advances in Neural Information Processing Systems, 2023c.
Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions, 2023d.
Chen, Y., Biloš, M., Mittal, S., Deng, W., Rasul, K., and Schneider, A. Recurrent interpolants for probabilistic time series prediction, 2024a.
Grant Acknowledgement
Chen, Y., Goldstein, M., Hua, M., Albergo, M. S., Boffi, N. M., and Vanden- Vanden-Eijnden, Probabilistic forecasting with stochastic interpolants and föllmer processes, 2024b.
This work is supported by the National Natural Science Foundation of China Grants 52450016 and 52494974.
dos Santos Costa, A., Mitnikov, I., Pellegrini, F., Daigavane, A., Geiger, M., Cao, Z.,, Kreis, K., Smidt, T., Kucuk- benli, E., and Jacobson, J. Equijump: Protein dynamics simulation via so(3) -ex))-eqqvvariant stochastic interpolants, 2024.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Grathwohl, W., Chen, R. T. Q., Bettencourt, J., and Du- venaud, D. Scalable reversible generative models with free-form continuous dynamics. In International Confer- ence on Learning Representations, 2019.
References
Albergo, M. S. and Vanden- Building normaliz- ing flows with stochastic interpolants. In The Eleventh International Conference on Learning Representations, 2023.
Kingma, D. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Albergo, M. S., Boffi, N. M., and Vanden-Eijnden, E. Stochastic interpolants: A unifying framework for flows and diffusions, 2023.
Le Gall, J.-F. Brownian motion, martingales, and stochastic calculus. Springer, 2016.
Lee, H. Lu, J., and Tan, Y. Convergence for score-based generative modeling with polynomial complexity. In Ad- vances in Neural Information Processing Systems, 2022.
Albergo, M. S., Goldstein, M., Boffi, N. M., Ranganath, R., and Vanden-Eijnden, Stochastic interpolants with data-dependent couplings, 2024.
Li, G., Huang, Y., Efimov, T., Wei, Y., Chi, Y., and Chen, Y. Accelcrating convergence of score-based diffusion models, provably, 2024a.
Benton, J., Bortoli, V. D., Doucet, A., and Deligiannidis, G. Nearly d-linerr convergence bounds for diffusion models

---

Finite-Timi Analysis of Discrete-Timg Stochastic Interpolants
Li, G., Wei, Y., Chen, Y., and Chi, Y. Towards faster asymptotic convergence for diffusion-based generative models, 2024b.
Liang. Y. Ju, P., Liang Y., and Shroff, N. Broadening target distributions for accelerated diffusion models via novel analysis approach, 2024.
Ma, N., Goldstein, M., Albergo, M. S., Boffi, N.M. M., Vanden- Eijnden, E., and Xie, S. Sit: Exploring flow and diffusion- based generative models with scalable interpolant trans- formers, 2024.
Nair, V. and Hinton, G. E. Rectified linear units improve restricted boltzmann machines. Proceedings of the 27th international conference on machine learning (ICML-10), 2010.
Oko, K., Akiyama, S., and Suzuki, T. Diffusion models are minimax optimal distribution estimators. In Proceed- ings of the 40th International Conference on Machine Learning, 2023.
Song, Y., bihk-Dickstein, J., Kingma, D. P., Kumar, A., Er- mon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
Wibisono, A., Wilson, A. C., and Jordan, M. I. A varia- tional perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 2016.
10

---

Sinite-Time Analysis of Discrete-Ting Stochastic Interpolants
Appendices
Appendix A: Supplementary details for Section 3 3 This section provides additional details from (Albergo et al., 2023) that were not included in Section 3. It includes a formal statement of key equations and their associated conditions. Furthermore, it outlines the optimization objectives for the score and velocity estimators, which are used for model training in Section 6.
Appendix B: Useful lemmas in bounding derivatives - This section presents lemmas that essential for bounding the derivatives of velocity functions and score functions, along with their corresponding proofs. The proofs primarily rely on properties and inequalities related to (conditional) expectations. These lemmas play crucial role in deriving the overall KL error bounds.
Appendix C: Proofs of results in Section 4 and 5 This section provides the complete proofs for the results presented in Section 4 and Section 5. This includes the proof of Theorem 4.3 (Appendix C.2), the proof of Proposition 5.1 and Corollary 5.2 (Appendices C.3,C.4), and additional details regarding the discussions in Section 5 (Appendix C.6).
Appendix D: More details of numerical experiments This section provides omitted details for Section including the parameterization of estimators, choice of (4o, and optimizers, and how the TV distance is estimated. We also include additional experiments for y(t) v(1 t)2t.

---

Finite-Time Analysis of Discrete-Time Stochastic Interpolants
Notations
We use || || to denote l2 norm for both vectors and matrices. For a matrix A, we use ||A|| v Exs A3 to denote the Frobenious norm of A. We use du ou or just d2 to denote the (partial) derivative with respect to We use V to denote the gradient or Jacobian, depending on whether the function scalar-valued or vector-valued. If not specified, for the function in form of f(t,z) where is a scalar and æ is a vector, V ff(t, x) means the gradient vector or Jacobian matrix with respect to rather than I. We use af( = Σ i=1 Bay
d 2
f as the Laplace operator. We use [[[] to denote the expectation of random variable X, and Cov(X, Y) to denote the covariance of two random variables X, Y. EE] [[X|c] and (Xv(X, Y|c) denote the corresponding conditional expectation and conditional covariance given condition c. We use the notation f(z) S g(x) or
8
f()) = O(g(z)) to denote that there exists a constant > 0 such that f(x) S Cg(z).
A. Supplementary Details for Section
This part summarizes some of the results from (Albergo et al., 2023) that are not introduced in Section 3. Proposition A.1. ((Albergo et al., 2023), Theorem 2.6, Corollaries 2.10 and 2.18, and their proofs) Suppose that the joint measure u and the function satisfies
(t, Fo, #1)1 M1 oe,
(20, 10 (t, 21)11 S M₂ < co, Vt [0, 1].
(10
Then, p E ((0, 1), (P(R))) & e ((0, 1), (CP()))) and (²) (CP(())) and both the solution of the probability flow ODE
d
Xx = xx,,b(,,,.) bi),
Xo~
di
and the solution of the forward SDE
axf = by (t, xxxx))//>) dt + /e(()dW,, X ~ Po
have the same marginal densities as (It) Here E C,0, 1] with e(t) 2 0 for all t E [0, 1] and by is defined as br(1,0)= b0)] (())
(10)
Moreover, suppose that the densities Pu. P1 are strictly positive elements of C22 (R2)), and are such that
J&L (o))) pz c0.
V (oz) < co,
Then E ((O, 1]. (RR)). (² 1), (CP( and b E Co 1], (CP((R))) The notation is adapted from (Albergo et al., 2023) where f E (10 1], CP(RR)) means that the function f is C in t E [0, 1] and CP in x E Rd.
The above proposition provides generative modeling in the form of
dt X, b(t,
and
dx.- = by(t, X )d 22((D)W,
In practice, we need to train an estimator to estimate velocity functions. By the following proposition, we can use the optimization objectives train the estimators.
Proposition A.2. ((Albergo et al., 2023), Theorems 2.7 and 2.8) 6 is the unique minimizer of
[
6.
E
|b (80 + b(t, xZ2) dt,
2
and 8 is the unique minimizer of
2.18] =
11 ((1))x3((((,)) 8(1,zz) de.
Here the notation "." represents the inner product of two vectors.
12

---

Finite-Time Analysis of Discrete-Time Time Stochastic Interpolants
B. Bounding the Velocities and Scores
B.1. Useful Lemmas
To begin with, we first provide moment bounds on the Gaussian variable & ~ N0 Id). Lemma B.I. For any 2 1,
-| < C())d',
where C(p) is a constant that only depends on p.
Proof. First, ||=||2 1 27, where represent
... (21, 22.-..
.zd)"
For any n positive numbers d1, 022 ... On.
using Jensen's inequality,
P
p
Σ
0i
np
1
ai
S
n
n
i=
Then,
E
2p
E
2/
d <
dp.
B1| [2]
(Jensen's inequality)
d
1=1
d'E
[|=1|0] p0]
((1))/1 are i.i.d.)
C(p)dP.
Here the constant
C(p) = |
n
|
dz
00
/2T
only depends on p.
Also, the following is another simple fact that is useful for our analysis.
Lemma B.2. For vectors R", U Rm the matrix uo RRax satisfies
| 11 = [|u||-
where || F denotes the Frobenious norm and ||- denotes the 2-norm.
Proof. By the definition of the Frobenious norm,
m Σ
n
luv
2
11
(wo
)2
jm
m
ue 02
i=1 j=1
Σ n
-=1
= ||0||2 ||00|/2.
Recall that we have defined xt) = El0, zo, 21) 21) = z). We then give bounds for the score functions and the velocity functions.
13

---

Sinite-Time Analysis of Discrete-Ting Stochastic Interpolants
Lemma B.3, For p 2 1, there exists a constant Cp)) that depends only on p. s.t. for (0, 1),
(l|s(t,æ)) _ Cpp)y"'dp'
Bllu(t, x.)l C - zoll",
[ x C(p) |B|| zoll" + /2
(l (1) N C(p) [Blar xoll + (1 7 P dd
Proof. When p 2 1, use the conditional expectation form of and and apply Jensen's inequality, we then obtain
E Ets((t,)))11 E11 =]||" >B| < C(p)
x1))11 F. =]]l" < / C(p) =oll?,
Moreover, since b(l,,x) (ll, x) + ()) and br((, b(t,z) (l(
x1, 21) - ((p) B||a - zoll' + 2/1012
E| (t, < ((p)
- -
+ (3 P. Pe ?e2)dm/2
B.2. Bounds on Time and Space Derivatives
Note: In the following sections, will use the fact that 2 0(1) and d
de - O())
Before we move on to the lemmas, we first discuss the conditional expectation itself. By the definition 2; = I(t, 2o. 21) + 2(),,, we can just know that the density of x4 can be expressed as
p(l,2) = S (2T7(1)2)d/2 exp (- - [[t, xo. m))l") du d1(
(T(1)
Also, under the condition 2, z, the conditional measure of (zo. is then
|xx [(t, 2o. x1)]
p(t, x) (2my(t)2)d/22 exp
dv 21).
2y(t)²
Therefore, for any function fi ro. 11), its conditional expectation can be written as
2o, 21 22 = 2| / xRd
fi(2,,o.
(1)3)()2 exp | (t, x 1)I
21)
p(t,z)
2x(1)²
exp (- [_ [(,
fe (I, (2,)
E (5 ) Joy
2y(1)²
E (30001)) )
exp
-e--[(1. I[t I11 (r)
We first consider the time derivative of in the sense of expectation.
Lemma B.4. We have
El(a,o(t, x11 < E | +
-dE - -x1l -
f 1).
Proof. For t E (0, 1), we can first explicitly write
(()](())1))
E
exp
2y(0)²
(2o Jou
utt, xx)
[1)=1())112))
E
exp
2y(1)²
(so you
14

---

Finite-Time Analysis of Discrete-Time Stochastic Interpolants
Here write T(1) [1, Fo, 21,41) for simplicity, and below will omit when it is clear in the context. We want compute O,t(t, First notice that
d exp
| -1---1111 1112)
eep (- || | 1112)
(1=--11) 7
2 カ-
0.1)
0.1
0.1 + 0,1
7(1)3
d/
27,2
27
72
Note that suPZER
exp(-x"
/22/a = c 1/2 = C1 < 00, suPseR exp(- x² /2) 2 26- = =O²² < 0o, we know that
| I
0,1
- |10.11 2 11001| +
exp
di
2y²
Therefore, using dominated convergence theorem, we know that
d
|
7112)
| 711
E
exp
0.
exp
0.1
dt )
27
(20.5)) Jay
dt
272
Similarly we can do this for the denominator, so that we can compute the overall derivative. Let fi x1) for simplicity we may just write fr. Then,
-x--(()) |
2ny²
exp (ft) I
(10.21) )ov
0ev(t,
exp (ft))
(20,2)) mu
(exp (Je) 0.1 O.fr]
E
(exp (ft)
(20,21)~v
E
(exp (fi) 0cl
E
lexp (fi) -efe
(xo. Joy
2
E
exp (fe)
(x0.21) Jowe
= E|0 =x]
+ Cov( O,fr(l =x);
where the last equality uses the previous explanations of conditional expectations. Hence,
10,0(1, xill
s B|10@ + =z
27 / = x]
Therefore, have
Bl x.) 2 22101111011001111222200000001100
E [xr)]
((a + (a++b)² < 5 2a² + 2/²)
E 0 |3 2..1
(Cauchy-Schwarl incquality) (Jensen's inequality)
E |,.1]
< 2 2
Using the requirement 0 S Cl - || in the definition of stochastic interpolants, ||, $ I| -111.. For Ö.fr we can directly obtain
0,f = | 1|
33 3 + - -x - 1) -.T=- - Ö.
Recall that we have defined 2, I(,, zo, x1) + (())2 where is an independent gaussian variable Io). By Lemma 1.
|| S d',
E|| S de,
we have
E|a.A 4 S (7 1)) 4d + 2 x1l'
15

---

Sinite-Time Analysis of Discrete-Tinge Time Stochastic Interpolants
Therefore, finally deduce that
Bl(a,u(t, S 1| + - x1ll" + 2-
In addition, we want to consider the space derivative of the velocity for a fixed E (0, 1). That is, we want to give a bound for Vo(t, x).. Here we use the notation Vo(t, æ)) to denote the Jacobian matrix d vlt, x)g) sy* where xf represents the
value of vector x at the i-th dimension. Lemma B.S. We have
ol C(p)y~PP''
E / 31 22
for p 2 1, (0, where Cp)) is a constant that only depends on p and || || denotes the Frobenius norm.
Proof. Similar the proof of Lemma B.4,
|| /11
2y² 0d1) exp (- (-11a 272
-100-11 113
[_1x ||x-- 7112) ) 27,2
))
0
exp
where & denotes the tensor product, which denotes 0,1 V Again, by dominated convergence theorem (i.e., fe and so on), we can deduce that
(- = 0, V
--
here in the matrix form.
the gradient operator into the expectation. Using the same notations
E (mo )ov
exp(ft))
(0.1 & Vf.i)
Vo(t,
E
(x)((fe)
E
(exp(fi) -.,1]
E
(exp(ft) V
(Mop Jou
(2
E
exp fc)]
)
Cov(a,I, felez x))
Again, the last equality uses the definition of covariance. Thus, by Cauchy-Schwarz inequality,
[v((tx)]| VE[ x B ff æ].
Therefore, we can use Cauchy-Schward inequality again and apply Jensen's inequality deduce that for any p 2 1,
E a 2p
2..
is clear that 2| S E|| - x 2p Note
f
= -
72
we then deduce that
E V s C(p) -20 22
for some constant that only depends on p. The lemma is then obtained.
Despite the function utt, æ),, we are also interested in the score function s(t, 2). The following lemmas provide some similar bounds for at)
16

---

Finite-Time Analysis of Discrete-Tinee Stochastic Interpolants
Lemma B.6.
B|ja (ys(t, [12 2 dd 3o x1 ||
and
BB x1 2| 2 + +
for any t E 1).
Proof. First using the analysis for the conditional expectations, we obtain that
1x=11| 27
exp
x1, V 2lggp(t,z)
|| 112
E
exp
2
(zg.21)ou Jow
In order to compute Ōe (t()s((,,))) x)), we apply a similar analysis as the proof of Lemma B.4 with exactly the same notations to deduce that
E (sone) No
(fx
xl)
E (exp(f)l
(mo
(exp(It) 7V...
(20. Jww
E
[exp(fi))
(zure))~
(ep((ft) fil
(exp(f)) 0cfil
)
(2
E
(exp(f.))
(x0,51)
Vl)((+Vi))zzz = = + Cov(y fc, a I = x)
The above term has exactly the same form as which in the proof of Lemma B.4, so by similar analysis we can obtain that We have already deduced that
El(0((s((( 2BI + +2/EB VEbTAA
E V fell* 4d
and
E|a,f S (1))))))) 'd' + d - x1
Also,
ft = a (-#-1) - - 1) = - + 1212
Hence,
O, 2x 21 2522222
11
which completes the first part. The proof of the second part is exactly the same by replacing V with Sz-
Lemma B.7. For any p 2 there exists a constant C(p) that only depends on p such that
V s C(p)
Proof. With exactly the same ideas of the previous lemmas, we can obtain
vs(t,z) = E fele: = z| + Cov(V Vfi x))
-1 - 2oov(2, 2 x)
17

---

Finite-Tinee Time Analysis of Discrete-Tinee Time Stochastic Interpolants
Then, for p 2 1, we have
Vs((, 1 - 2p 20-117-2-111 s y 2212 + 2" , 2B
|=| =]|
(Jensen's 's inequality)
C(ph d'.
Here for the first inequality we have used the fact (a b)d - 20-1ap 20-11 for a, 2262 O.
We also need some bounds for As and Ac, where A represents the Laplace operator. Lemma B.8.
E At,, S > ddB| z1ll + -
for all t E 10.
Proof. We still the notations in the proof of Lemma B.4. First, in the proof of Lemma B.5, we have already shown that
E
(exp(It) (0,1 - Se1
(20.z1)~0
(t,)
[exp(fi)
(w0.
E
(exp(fi) 0.1]
(exp(fi) fcl
(2 )rvv
(#g. Jov
[oxp ff))
E
E
(exp(si) exp([i)(O1- (0.. 0
(
(Ro youy
I (Zo,Z))~v
(xxp(f))xpp(f) )aw
The last equality is an alternative form of the covariance, and we use notations I = I(t, To, T1) and ft = f(( F2) for intermediate variables (To, 11). Hence,
8. (t, x) = 0 =x)
Cov[(O,T Cov((0,T-0 (a -.. - =;; =x]
+ 2
For the first term, note that 02, ft
- is fixed. So.
Av(1,)) _ -ov[((8)-- - V V/, VSle, = x, = =].
Here the covariance refers to the expectation of dot product instead of the expectation of tensor product. Then, use the fact X| - 2 < 2 we know that
(tv(t, x311 S
- (11(0-11,,))1 11 Iz = F. x]
[EllI + fall v, = x]
(Cauchy-Schwarz inequality)
/illaa1r a/ lx, vz 21]
1/4
1/4
vill' lx, 3. x0|
(Cauchy- Schwarz inequality)
f = x
(by symmetry)
1i E[1|a/111* way = [a] 1/4
(by symmetry)
18

---

Finite-Timi Analysis of Discrete-Tinee Time Stochastic Interpolants
Therefore,
E A x1)
2 IE
E|ll V - a1]
24
12
2 at] Blll0 111
E E V = x]?]
(Cauchy-Schwarz inequality)
23 28
/B110/111
2 x1 21 de
(Jensen's inequality)
24
+
Lemma B.9.
B]A 66
fort E (0,1)
Proof.
Vflz, =x). + Cov(V =
Hence, with similar calculations and notations in the proof of Lemma B.8, can deduce that
As(t, x) = 2Cov =
1 2
Cov( VfA(A VîJ" V.. Vfla. x).
Covl(V/: V).) V V V = T. = =]]
Then, with Hölder's inequality, we have
||ss(t, x)11 $ B fo - V =; 2/|///3
BIll V.)( - 11332133123 2/3
|B| 1 = =1] 1/3
(by symmetry)
[B||| V. v. = = =x|]
B f la= md)
(by symmetry)
Hence, by Jensen's 's incquality,
E (1, & /|
209 - 8||1211 BB]=11 = -6
C. Omitted Proofs in Sections 4 and 5
C.1. Bounds along the forward Path
Recall the forward ODE
d.X, = Xt),
and the forward SDE
dx.' = (1, dd /2edW,
Their solutions are denoted by X, and X respectivell. Using the chain rule or Ité's formula, for a function [(1,2: that is twice continuously differentiable, we have
df(t, X,) (t.s(t, Xx) + VI(, b(t, d.))dt,
19

---

Finite-Tinie Analysis of Discrete-Time Time Stochastic Interpolants
and
= (0.f(1, (0.,),,)) V br((t, + cAf)dt V2VV)(, dW.
With the above formula, we can now provide the following bound on the discretization error. Lemma C.I. For 0 < to I L < I, suppose e - O(),, then,
Bi|o(to: xf)) - v(t,, x(t,, 2 (t1 - to)2 M2 c(1 to) d 1 Io I1 11
{ + Mmin dt + Ymin dv /3 xo - x x1ll
and
Ells(to, ) - s(1,, x12 z (41 - to)²
Imin d BBl - x1||4 + m of
+ e(ll - -m) d2
Here we denote Timin min 7.
Proof. According to the formula
dt, x = [8,u(t, x.) + Vu(t, x() by(t, x.) + csu(t, )et + (2t, dW.
we know that
||e(t), (0,t),x;,) v(to, x2 S $11
1/ Ono(u, X Idu
1/2 xu(uxx))) blu, x du
4
1 eAu(u, x x. )du
4
4 1
V2eVu(u, X dWn,
For the first three terms, by Jensen's inequality we know that for any function Y, we have
11100 (u)du
s (t1 to) 1/h (w))
For the last term, use ItO's isometry (Le Gall 2016, Equation 5.8), we can get
V2eVo(u, dW., 1
E
E| EIV,, x.)
Therefore, we can use Fubini's theorem to change the order of expectation and integral, and combine the results of Lemma B.4, B.5, B.8 and B.3 and Assumption 4.1 to get
[1t1,, Xf, - v(to. x,,11 S - to) / Bl, (x))
+ (ti -to) 30
[ dt ' Velu, +mm dEElbb (u, Xx))l* du
+ 2 to)
E El Ao(u,, X.)ll
+ 2e
E Velu, X |1
$ (4 40)2
M2 - d3 + z
EE 21 1
+ ((1 - to) - dd / 1 11
20

---

Sinite-Time Analysis of Discrete- Time Stochastic Interpolants Note that we have already used the condition 7² [ and y - 0(1) Similarly, use Lemma B.6, B.7, B.9 and B.3, and the formula
ds xf") [0,s(t, X + Vs(t, by (t, + ess(t, ) + Vtt dW,
to bound
E| (1,,(t1, s(to X 11 x (t1 -to)
-4 VB z1ll= + 7 dd + c(t +to) d? M
where Ymin [i.
C.2. Proof of Theorem 4.3
We first give the following proposition, which is a result from (Chen et al., 2023d).
Proposition C.2. (Section 5.2 of (Chen et al., 2023d)) Let P, Q be the path measures of solutions of SDE (3) and (6), where they both start from the same distribution p(()) at time = to and end at time t = IN. Then, if
(t, x.)) - (ts. x > SC
for any t. E [1,, IN) and some constant C, we have
KL(PIIQ)
1
Σ
1k+1 [1]bb((, - by(tte ]dd
4E k=0
Here the expectations are taken over the ground-truth forward process )eE(tane)) P.
Now, using the above proposition, we are ready to prove Theorem 4.3.
Proof. Let P. Q be the path measures of the solutions to the SDE (3) and (6), where the solutions start from the same distribution p(ta) at time t = to. as in Proposition C.2. We first want to check the condition of Proposition C.2. Note that
(ler x by (t,
2B | (tx, x br x || 23|
by (f.
2E br (IN, x - by +B)l (((
c)s((t c)s(t x( +0
+ 4EI (t( +
(->
(0)
2 2B
x.. -x)
by (t)
u(t, utt, X("
+ 8( (())(()(((t)++))))))))))))))))))
x - stt, x )1
+ -((()))())(((())())))))))))))) |1
Here (a), (b) and (c) use the triangle inequality and the fact (a 6)2 < 2n 2 By Lemmas B.3 and C.I, this term is
uniformly bounded in the closed interval [4o, (x]. In fact, we can apply these lemmas to obtain that
Ellbb((k, X (F((,
Ellbr(tu: x bF X11
+ (t 1² M2 + 7% -6,
2 E x1 111
+ c(t 4 4)7%% dd
EP. v00 x1 1
+ (t )²
Fix dd /Ellzro 2111
5h dd) c(t tx) 'd
+ (t (x) 2 2d
(b)
S TE (1,,, x - bp 1k: xx
+ (t - )x M2 + 7k
6 dd 5/ dd
/ E 220
21 11
+ +(l 4x) 7/= 2d /VBlara
2n 1 + 7/ d)
21

---

Finite-Time Analysis of Discrete- Time Stochastic Interpolants
Here step (a) directly expands the discretization error using Lemmas B.3 and C.I;; step (b) simplifies the terms by applying Young's inequality and that 1 + 2² O(1). Then, by Proposition C.2,
N --1
te+1
(L((1IQ) = 4
(t, by (tx. ((.)))
km
N-1
2
+
(tx+1 - tx)² M2 + dds + Th dd E 2o 21
hp
k=0
(tx+1 - (u) 2 3d
/El
xill
x
+ 3d
Here step (a) just integrates over the upper bound the disretization error. Now, consider KL(o(tw)ll((xx)) Let Q be the path measure of solutions of (6) starting from p(tu) instead of p(tu). Then,
dP (X)
KL(o(t))ll((N)) S KL(PIIQ) Ep
log
dQ
log dP
dQ
)
Ep
(X)
(x)
dQ
dQ
dP
log dp(to)
Ep
log dQ (X) + Ep
dp(to) (Xe.)
KL(PIIQ) + KL(p(to)ll((to))
The proof is then completed.
C.3. Proof of Proposition 5.1 Proof. Using the results of Theorem 4.3,
N-1
kL(p(tx)ll((tN) & che (L(p(tu)ll((to)) -c- Σ
(t++1 - xx) M2 + 6 + + 2d 21
N
(tx+1 - tx) 2 2d /
E 1o
1| + TT
k=
bp
+ (L(p(t))l(p(to) + -
Myhj 1d3d3 + hh
E 211
h=
hha 100 - x1 1| + 122
+
(LL((to) + 11 (M2 R/ 11118) -c-
b
/lLEEl - x1 22
2 bp + KL(p(ta))|((to) + hd El x1 + Nh dd
Here step (a) is the result of Theorem 4.3; step (b) uses the fact by tx+1 to 0(h7²); step (c) uses the fact
END1 hi = =x 40 S 1; step (d) omits the higher-order terms.
C.4. Proof of Corollary 5.2
Proof. When the number of steps is N, we have
h = θ
N NN-1log log
tol1 - tx)
22

---

Finite-Tinee Time Analysis of Discrete-Tinge Stochastic Interpolants
Then, by Corollary 5.1 and the assumptions,
1 ) + de log² 60(1 - (6(1- (N) (
(L(p(t))l)((t)) & e² N-1 d dVEEl xıll cill=log log [6(1- [N)
+ogog
This gives the complexity to to make (L(p(tw)ll a
C.5. Reducing to Diffusion Models
By modifying the definition of stochastic interpolant to
= x11 + +t))z
and change the condition on / to [[,T S ClI can repeat the previous analysis while replacing v Bl xi| by / BB] 21 [l. For the case diffusion models, we can choose [tt, x1) = tæ and 7(t) = vI to obtain a process with the same marginal distributions. Moreover, under this definition of interpolants, we can choose to 0 and hy 1++1 4 (1 1x)) the time schedule recover the sample complexity of diffusion models.
C.6. Omitted Proofs for (t) t)
In this section, we will design schedule for (t) = (1 - t)2t, and provide the corresponding complexity deduced using Theorem 4.3. Moreover, also derived the complexity of using uniform schedule for comparison.
Corollary C.3. For (1) = (1 - t) there exists a schedule so that under the same assumptions as Corollary 5.2, the complexity is given by
N O
V
1 B xo xill'd
log ) dP
log² (1)
(1--
VI-TN
In addition, the complexity for using uniform schedule
(
(1 1-tN tN
) d (a--to)a to 1)
N o 2 VE
x111#d
log
Proof. Here we also take hm 0.5 for some M O. Then, we define
hA tx-1,
k < M
hg
hB (1 - 112)2 12)255
k 2 M.
for some A E [0, 0.5), hB E [0, 1). For the part < and ta [0,0.5), (1x) = (tzz), so the same as what we have discussed for the case, and we need
M N;
M- =
1
B Ad
1 d log
to 1
steps to make the discretization error
(l+41
4x) M2 + 666 + 2 / 20 - 11/
0m0
M-1
(tx+1 - 2= [ El - 2111 + 7x { S E².
+
For the part& k 2 M,
N
(tut1 - tx)3
M2 + -7 663 + 77x 2d E2 21 = -(b)),
000
M
23

---

Fime Analysis of Discrete-Time Stochastic Interpolants
and by that hig 011
(1 12)3..) (use in step (a) below).
7
1 2o d
11111 7/ 2d)
N N-1
2
hB
Σ hi dv
Bl - 21 7% 0.5 + 9x8
2.5 d2
Jo
(b)
/ (1 (1- (1-s)-0.50) ds ds + d?
f((( (1-
AN
hB
dv /E/ 120 x1l1
s) ds
0.5
0.3
1
X hB
dv dvBBlan Bl
=1|l= 1| d² (1 |N)
Here the inequality (b) is by that " = @(1 - 1) for t E [t,, 12-1). Now, we want to compute the number steps
N2 = N .M for the part k 2 M. Note that if l. = P_ it takes (12 more steps to reach - 2---11 Hence
N2 = 0 (hi IN) -05)) so we need to take hB θ (N 10-(11 - -N)) 0.5). Therefore.
N
h TR
2d
v /El==0 - x1 11 + Pk Rd
E
2a 21
de
N
IN
(1 - tN )
Thus, for the part k > M, we need
dd E
x1 21 v1
d2
N N M- N2
0²
iN
(1 - (N
steps to make the discretization error bounded by (E²²). Hence, the overall complexity is given by N N1 + N2. which result.
If we use uniform schedule, by Theorem 4.3 and that (2) (minn(4 (1 (1-11-))) 1)2 we can bound
Kl(((tN))l(((N)) $ o + kl.(p(()))l(((o)
0.5
AN
El
- +
- s) -)
60
0.5
U.5
pN
N d
8
2
+
(1 8) ds
u.3
x 6 + KL (p((o))l(((t))
1
E =
+
log
I-tN IN
to
1 (1
d²
+ to
(1-tx)²
which further gives the complexity bound for uniform schedule. Here the incquality (a) is by applying Theorem 4.3 and replacing Th with the term of the same order. This bound is worse than using the schedule satisfying that hyg S hok-
D. More Details of Numerical Experiments
To parameterize the estimator (1, (1, .r) for two-dimensional data, we utilize a simple multilayer perceptron (MLP) network. The input of the network comprises a three-dimensional vector (a, t), and its output is a two-dimensional vector ( x). The MLP architecture consists of three hidden layers, each with 256 neurons, followed by ReLU activation functions (Nair Hinton, 2010).
24

---

Finite-Time Analysis of Tanerete-Time Stochastic Interpolants
To train the estimator (l, v)), we leverage simple quadratie objective (see Appendix for details) whose optimizer is the real drift by (t, Given the estimator, data batches, and sampled time points, are ready compute empirical loss. We employ the Adam optimizer (Kingma & Ba, 2015) to train the network using the gradient computed on the empirical loss.
We set to = 0.001 and iy = 0.999 to ensure that the initial density p(to) is close to Pa and the estimated density p(tx) ) closely approximates P1. During the training process of the estimator by (f, I), we employ an importance sampling technique so that E [fo, IN] is sampled with probability proportional to (t).. We implement the discretized sampler as defined in Equation (7). We use more than 10, 000 data samples to empirically visualize the densities in Figures 1, 2a and 2b.
In addition, for KL divergence estimation, we estimate the density ratio by comparing the distance the k-th nearest neighborhood. Specifically, for some RR let {=bH== and {> { be i..d. samples from po and PL. and do, dj be the corresponding distance from x to the k-th nearest neighborhood, then estimate
po(2)
k/(nd))
md? nd
Pi (1(
k/(mdd))
KL divergence v5 steps
10-
Non Uniform Uniform
KL divergence
0.6
100
150
300
250
300
Steps
Figure 5. Estimated KI. divergence for different step size schedules, where we use (1) = (1 - t) The red curve denotes the distance when we use the schedule designed in Appendix C.6, while the green curve denotes the distance when we use the uniform schedule.
D.I. Additional Experiments for 7tt) (1-
We implement the schedule discussed in Appendix C.6 and compare it to the uniform schedule. We choose tx) (0.001, 0.97) since (t) is @((1 t)²) near = 1. We choose Po as the "checkerboard" density and Pi as the "spiral" density. We estimate the KL divergence (L(p(t>)]l((tv)) to indicate how close the estimated distribution is to the target distribution. The comparison is shown in Figure 5.
25


Reviews:
[{"review_id": "zHNTbcG7Tk", "reviewer": "Reviewer_9oGn", "summary": "This paper derives a convergence bound for the stochastic interpolants framework. The discretized SDE analyzed in this work is more general than the SDE analyzed in existing diffusion model convergence bounds. Like in the diffusion setting, the derived bound suggest an that an exponentially decaying discretization schedule is a better choice. The authors show empirically that this is indeed the case.\n\n## update after rebuttal\n\nI thank the authors for their clarifications. The more general interpolant analysis remains quite close to existing work but I believe it could be interesting to have the result out there, I therefore increase my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! We are grateful for your constructive suggestions, which have significantly guided our improvements. Please find our responses to your comments below.\n\n### Claims And Evidence / Weakness\n\n> The differences introduced by the slightly more general interpolant $I(x_0, x_1, t)$ are dealt with in Lemmas B.3 and C.1, which are the main technical contribution of the work (Could the authors confirm?).\n> A minor weakness: The technical extension over prior work might be slightly limited but it can still be worthwhile to have the bound in the literature\n\nA: The main contributions of our work include the following. First, we propose the first discrete-time analysis for the stochastic interpolant framework, where we propose a new discrete-time sampler and provide the rigorous distribution estimation error bound for the sampler (Theorem 4.3). Second, based on the error bound, we further develop a time schedule for the discretization to achieve lower sample complexity (Corollary 5.2), when the latent scale is defined by $\\gamma(t)=\\sqrt{at(1-t)}$. Lastly, we validate our theoretical results with numerical experiments.\n\nAmong our technical results, Lemma B.3, Lemma C.1 and Appendix B.2 address the discretization error of the drift term $b_F(t,x)$. In this part, the main difference between our result and previous results is that we utilize a more general interpolant $I(t,x_0,x_1)+\\gamma(t)z$ between two general distributions. This introduces a novel velocity term $v(t,x)$ in the process, and demands new analysis for the estimation error compared to existing results on diffusion models. \n\n### Questions\n\n> Could an additional assumption on the target distribution remove the unfortunate initial KL term in the bound?\n\nA: Firstly, the initial KL term quantifies the discrepancy between the true initial distribution $\\rho(t_0)$ and the estimated distribution $\\hat{\\rho}(t_0)$, where $\\hat X_{t_0}$ is sampled from. We incorporate this term into our theorem to comprehensively cover the scenario where $\\hat{X}_{t_0}$ differs from $\\hat{\\rho}(t_0)$, and provide a corresponding error bound in Theorem 4.3 \n\nNext, we look at two examples on how this term affects our error bound. If we define $I$ such that $I(t,x_0,x_1)=x_0$ within the interval $t\\in[0,t_0]$, the initial error becomes exactly $0$ because we can directly sample from $\\rho(t_0)$ (note that during generation, data from $\\rho_0$ is accessible). Furthermore, if $\\gamma^2(t)=\\Theta(t)$ near $t=0$, we can achieve an $O(t_0)$ initial KL error if we choose $\\hat{\\rho}(t_0)$ such that $\\hat{X}_{t_0}=x_0+\\gamma(t)z$ for $x_0\\sim\\rho_0$ and $z\\sim\\mathcal{N}(0,I_d)$. In this case, the initial KL error is the same to the initial KL error of diffusion models with $T=\\Theta(\\log(1/t_0))$ [1].\n\n### References\n\n[1] Benton, J., Bortoli, V. D., Doucet, A., and Deligiannidis, G. Nearly d-linear convergence bounds for diffusion models via stochastic localization\n\n---\nWe hope our response addresses your concerns. If so, we wonder if you could kindly consider raising your score? We will also be happy to answer any further questions you may have. Thank you very much!", "claims_and_evidence": "The central claim in the paper is the convergence bound is provided in Theorem 4.3. The proof adapts the result of Chen et al [A] on the discretization of SDE to the stochastic interpolant framework. The differences introduced by the slightly more general interpolant I(x_0, x_1, t) are dealt with in Lemmas B.3 and C.1, which are the main technical contribution of the work (Could the authors confirm?).  \n\nA secondary claim is derived from the theorem which shows that an exponentially decaying schedule cancels out terms appropriately and leads to a simplified bound in Proposition 5.1. This claim is confirmed experimentally in Figure 3.\n\n---\n[A] Chen, Sitan, et al. \"Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions.\"", "methods_and_evaluation_criteria": ".", "theoretical_claims": "The analysis is sound. The only unfortunate element is the need for $t_0 > 0$ and the initialization error resulting from this. It creates a discrepancy between the bounds in the paper and bounds for diffusion models whose initialization error can be made exponentially small by increasing the simulation interval T.", "experimental_designs_or_analyses": ".", "relation_to_broader_scientific_literature": "There are some papers already providing analysis of the flow matching framework and the authors clearly compare their techniques with prior work.", "essential_references_not_discussed": ".", "other_strengths_and_weaknesses": "The strengths: The paper is clearly written and easy to follow. It adapts prior work and adds to the literature on discretized SDEs used for sampling. The derived bound gives indication on a good choice of step-size schedule and the authors confirm this experimentally. \n\nA minor weakness: The technical extension over prior work might be slightly limited but it can still be worthwhile to have the bound in the literature.", "other_comments_or_suggestions": ".", "questions_for_authors": "Could an additional assumption on the target distribution remove the unfortunate initial KL term in the bound?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CXffNmYw5f", "reviewer": "Reviewer_5Shm", "summary": "This paper proposes a finite time analysis of discretization of stochastic interpolants. The paper presents assumptions on the initial and final distributions, score estimators, then provides a complexity bound in KL divergence.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! We are grateful for your constructive suggestions, which have significantly guided our improvements. Please find our responses to your comments below.\n\n### Experimental Designs Or Analyses\n\nA: Thanks for the suggestion. We tested the samplers on $d$-dimensional Gaussian mixtures ($\\rho_0$ and $\\rho_1$) and compared the distribution estimation error for different $d$. The real drift terms used in the sampler are analytically computed [1]. You can check [link1](https://drive.google.com/file/d/1PuZy-aR9OYwBtB9xdnPaxn5qAP2G3-3O/view) or [link2](https://drive.google.com/file/d/1wkOsPsqq0wzCCd8paGZL8qIpK2aYMD52/view) for results. The first figure compares the error for different $d$ with fixed iterations, and the second shows convergence for higher dimensions. Both results align with our theory and validate the $d$ dependence.\n\n### Other Comments Or Suggestions\n\nA: Thank you for your suggestions! We will update them in the revision.\n\n### Questions For Authors\n\nA1: We first emphasize that our work primarily focuses on the theoretical analysis of the general stochastic interpolant method. We provide the first discrete-time analysis and propose an upper bound for the distribution estimation error. Additionally, we develop a discretization time schedule that optimizes this bound for a specified $\\gamma$.\n\nTheorem 4.3 offers a general upper bound, controlling the error using $\\varepsilon_{b_F}^2$, the distance between distributions, data dimension $d$, and step sizes $h_k$. Assumption 4.2 quantifies how close $\\hat b_F(t,x)$ is to $b_F(t,x)$ and holds for some $\\varepsilon_{b_F}^2$ if $\\hat b(t,x_t)$ has finite second moments. Theorem 4.3 illustrates how this impacts the final distribution error.\n\nOur numerical experiments validate these findings. We use the loss function $\\mathcal{L}[\\hat{v}]=\\frac{1}{2}\\int_{t_0}^{t_N}\\mathbb{E}[|\\hat{v}|^2-2\\partial_tI\\cdot\\hat{v}]\\text{d}t$ to train the estimator $\\hat{v}(t,x)$ for $v(t,x)$. This choice proved effective and is commonly used (e.g., [1], [2], [3]).\n\nHowever, creating robust estimators for general applications is challenging, requiring careful designs for network architectures, learning algorithms, and learning rate schedules, which is a direction for future research.\n\nA2: Regarding dimension dependence in Theorem 4.3, the key terms contributing to the discretization error are:\n$$\\varepsilon_{\\text{dis}}\\lesssim\\sum_{k=0}^{N-1}h_k^3(d^3\\bar \\gamma_k^{-6}+d\\sqrt{\\mathbb{E}|x_0-x_1|^8}\\bar\\gamma_k^{-2})+\\sum_{k=0}^{N-1}h_k^2(d^2\\bar\\gamma_k^{-4}+d\\sqrt{\\mathbb{E}|x_0-x_1|^4}\\bar\\gamma_k^{-2}).$$\nFor a multivariate Gaussian $z\\sim\\mathcal{N}(0,I_d)$, $\\mathbb{E}|z|^{2p}\\le C(p)d^p$. If $x_0$ and $x_1$ are multivariate Gaussians, $\\mathbb{E}|x_0-x_1|^8=O(d^4)$. Substituting this shows the dependence on $d$ is $O(d^3)$ in the $h_k^3$ term and $O(d^2)$ in the $h_k^2$ term. The dimensional dependence is also consistent in Corollary 5.2.\n\nA3:Our work is focused on discrete-time analysis, which is new for the stochastic interpolant framework. Unlike continuous-time error bounds that use the 4th moment assumption (see [1]), our discrete-time analysis requires the 8th moment assumption. In Theorem 4.2, we control $\\mathbb{E}|\\nabla b_F(t,x_t)\\cdot b_F(t,x_t)|^2$, requiring $\\mathbb{E}|x_0-x_1|^8<\\infty$. This term appears as $h_k^3\\bar{\\gamma}_k^{-2}d\\sqrt{\\mathbb{E}|x_0-x_1|^8}$ in Theorem 4.3's error bound.\n\nHowever, this term doesn't dominate when the step size is small, with the error bound being dominated by $h_k^2\\bar{\\gamma}_k^{-2}d\\sqrt{\\mathbb{E}|x_0-x_1|^4}$. Relaxing the 8th moment assumption is a future research direction.\n\nA4: It is true that the drift term $b_F(t,x)$ has larger variation near boundaries, motivating our exponentially decaying schedule in both theory and experiments. Our estimator approximates $b_F(t,x)$ well for $t_0=0.001$, so this choice does not pose a problem. We will add more details and visualizations in the revision.\n\nA5: While analyzing the estimation errors of score and velocity terms separately is suggested, we find it unnecessary for our analysis. Partitioning $b_F(t,x)=v(t,x)+(\\epsilon-\\dot{\\gamma}\\gamma)s(t,x)$ results in $\\varepsilon_{b_F}^2\\lesssim\\varepsilon_v^2+\\sup(\\epsilon-\\dot{\\gamma}\\gamma)^2\\cdot\\varepsilon_s^2$, which is similar to [1] for continuous-time stochastic interpolants.\n\n### References\n\n[1] Albergo, M. S., Boffi, N. M., and Vanden-Eijnden, E. Stochastic interpolants: A unifying framework for flows and diffusions, 2023.\n\n[2] Yaron Lipman, Ricky T. Q. Chen, Heli Ben-Hamu, Maximilian Nickel, and Matthew Le. Flow matching for generative modeling, 2023.\n\n[3] Albergo, M. S. and Vanden-Eijnden, E. Building normalizing flows with stochastic interpolants, 2023.\n\n---\nWe hope our response addresses your concerns. If so, we wonder if you could kindly consider raising your score? We will also be happy to answer any further questions you may have. Thank you very much!", "claims_and_evidence": "The paper claims to approach the problem of analysis discrete-time stochastic interpolants, and does provide clear assumptions and results to support the claim. There are also numerics that demonstrate the convergence rate. No claims seem problematic.", "methods_and_evaluation_criteria": "Not applicable as this is mainly a theoretical paper.", "theoretical_claims": "While I did give a careful look at statements and proof sketches, I did not check every single line of proofs. Below are my high-level questions about theoretical claims", "experimental_designs_or_analyses": "The experimental design is very limited, limited to 2D examples. Given the explicit dimension dependence in the bound, I suggest authors to provide experiments with variable $d$ (maybe Gaussian case or something similar) and let $d$ grow, to obtain a scaling result to see whether their bound is predictive of what will happen with increasing $d$.", "relation_to_broader_scientific_literature": "The paper extends the work on stochastic interpolants, particularly Albergo et al. (2023) and provides a discrete time analysis. However, my opinion in general is that given the assumption on $\\varepsilon$-accurate drift for the SDE given in the Albergo et al. (2023), I think the contribution is a bit incremental - this is a discretisation analysis in essence. Which is usually standard adapting the usual analysis methods as authors did.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Analysis seem very favourable dependence to dimension and $\\varepsilon$ accuracy.", "other_comments_or_suggestions": "1) line 149 lhs, \"Both $b(t,x)$ and $b_F(t,x)$ can be expressed as linear combinations\", clarify for reader's convenience.\n\n2) Line 383, $N$ is the number of iterations, line 375 $N(0, I_d)$ is a Gaussian, use $\\mathcal{N}$ for the density.", "questions_for_authors": "1) The authors assume in Assumption 4.2 that the drift is estimated with high accuracy. However, can authors clarify how this can be relevant to practice? We know that $b_F$ can be decomposed as the score + velocity term. For the score term, very good estimators exist from diffusion models literature. Can the same be said for the second term? Is this a practical setting?\n\nPlease mention some practical estimators for the second term after this assumption, their behaviour, whether it is easy to ensure good training of it, as in the score case.\n\n2) While the bound in Theorem 4.3 has a favourable dependence to dimension, I feel like some of this is hidden in the term $\\mathbb{E}\\|x_0 - x_1\\|^8$. Please exemplify a bound with two multivariate Gaussians - provide this expression and provide its dependence to $d$. Similar question extends to Corollary 5.2.\n\n4) What is the reason in Assumption 4.1 that you have an 8th moment assumptions, vs. 4th moments in the literature. Please give some intuition following line 190.\n\n5) Figure 1: is there any issue with $t = 0.001$. Is the estimator $\\hat{b}_F$ stable around this region? Please provide the plot around this time for the SDE.\n\n6) I suggest authors to not assume uniformly that $b_F$ is estimated $\\varepsilon$-accurate. Perhaps given the score estimators, you can provide $\\varepsilon_{score}$-accurate score and $\\varepsilon_{vel}$-accurate velocity term estimate - thus see the interplay between these two error sources and how they play out in your final bound.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KFAnKRvcnV", "reviewer": "Reviewer_s1b3", "summary": "This paper present discrete-time analysis of the stochastic interpolant framework or as known as flow models, by theorical results, this paper design a schedules for convergence acceleration.\n\n## update after rebuttal\n\nMy view has not changed, so I maintain my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! We are grateful for your constructive suggestions, which have significantly guided our improvements. Please find our responses to your comments below.\n### Methods And Evaluation Criteria\n\n> I believe the authors should explain the novelty of the Exponentially Decaying Time Schedule. Given that flow models and diffusion models are not substantially different, it appears that the authors may have merely transferred a time schedule from diffusion to flow models.\n\nA: We first would like to emphasize that our work introduces the first discrete-time convergence bound for SDE-based generative models within the stochastic interpolants framework. Theorem 4.3 provides an explicit upper bound on the estimation error, expressed in terms of step sizes $h_k$, dimension $d$, latent scale $\\gamma$, and the distance between two distributions measured by $\\mathbb{E}\\Vert x_0-x_1\\Vert^p$. This theorem establishes an error bound applicable to arbitrary time schedules, thereby offering insights into the design of schedules that minimize sample complexity. The schedule presented in Section 5 is designed based on this theorem, wherein we stipulate that $h_k$ should be proportional to $\\bar{\\gamma}_k^2$ to ensure a well-balanced discretization error.\n\nSpecifically, for the case where $\\gamma(t)=\\sqrt{at(1-t)}$, the derived schedule manifests as an exponentially decaying schedule, characterized by a reduction in step size on both ends of the interval $[0,1]$. While this schedule shares similarities with the exponentially decaying schedule employed in diffusion models, a key distinction lies in the fact that diffusion models typically decay the step size on only one side of the interval.\n\nFurthermore, it is noteworthy that for alternative choices of $\\gamma$, the optimal schedule may deviate from the above schedule.\n\n### Experimental Designs Or Analyses\n\n> Although the authors provide theoretical justification for their method’s superiority, the experiments themselves appear overly simple. I recommend conducting toy experiments on low-resolution datasets such as CIFAR-10 or ImageNet32 since training flow models on these datasets are relatively fast and computationally manageable.\n\nA: Primarily, this work constitutes a theoretical investigation, wherein we establish the first discrete-time complexity analysis for the stochastic interpolants framework. Our contributions include the derivation of an explicit error bound for the discrete-time sampler, as presented in Theorem 4.3, and the subsequent exploration of schedule design strategies aimed at minimizing sample complexity. The objective of our numerical experiments is to validate our theoretical findings.\n\nWhile we acknowledge the value of demonstrating our method's efficacy on more complex datasets, such as CIFAR-10 or ImageNet32, we must emphasize that the application of our framework to these datasets introduces a multitude of practical challenges. These challenges encompass the design of effective network architectures, the meticulous tuning of hyperparameters, and the optimization of learning algorithms. Addressing these practical considerations falls outside the primary scope of this theoretical study. However, we recognize the importance of empirical validation on standard datasets and consider it an interesting direction for future research.\n\n> Given that the authors’ theory largely transfers discrete-time analysis to flow models, it would be more convincing to present additional experiments that demonstrate the claimed ability to “design efficient schedules for convergence acceleration.”\n\nA: A core contribution of our work lies in the derivation of the inaugural theoretical error bound for distribution estimation within the stochastic interpolants framework, explicitly expressed in terms of the step sizes. Leveraging this result, we theoretically demonstrate the feasibility of designing schedules that accelerate convergence by optimizing the balance between error terms.\n\nTo empirically validate the efficacy of our schedule design methodology, we have conducted numerical experiments for both $\\gamma=\\sqrt{(1-t)t}$ (Section 6) and $\\gamma=\\sqrt{(1-t)^2t}$ (Appendix D.1), comparing the performance of our specifically designed schedules against that of the standard uniform schedule. While we acknowledge the potential for further experimentation to strengthen our claims, we consider the current numerical results as a solid validation. Furthermore, the exploration of optimal choices for $\\gamma$ in practical applications represents an intriguing avenue for future research.\n\n### Essential References Not Discussed\n\nA: Thank you for pointing them out! We will discuss them in the revision.\n\n---\nWe hope our response addresses your concerns. If so, we wonder if you could kindly consider raising your score? We will also be happy to answer any further questions you may have. Thank you very much!", "claims_and_evidence": "I think the discrete-time analysis is reasonable.", "methods_and_evaluation_criteria": "1.\tI believe the authors should explain the novelty of the Exponentially Decaying Time Schedule. Given that flow models and diffusion models are not substantially different, it appears that the authors may have merely transferred a time schedule from diffusion to flow models.\n2.\tIf that is the case, the main contribution seems to be theoretically verifying that the Exponentially Decaying Time Schedule offers certain advantages over a Uniform Schedule in flow models.", "theoretical_claims": "Theoretical claim is valid.", "experimental_designs_or_analyses": "1.\tAlthough the authors provide theoretical justification for their method’s superiority, the experiments themselves appear overly simple. I recommend conducting toy experiments on low-resolution datasets such as CIFAR-10 or ImageNet32 since training flow models on these datasets are relatively fast and computationally manageable.\n2.\tExperiments conducted solely on Gaussian data only confirm the theoretical foundations. Given that the authors’ theory largely transfers discrete-time analysis to flow models, it would be more convincing to present additional experiments that demonstrate the claimed ability to “design efficient schedules for convergence acceleration.”", "relation_to_broader_scientific_literature": "This paper relates to many applications of diffusion models.", "essential_references_not_discussed": "Flow straight and fast: Learning to generate and transfer data with rectified flow ICLR 2023\nFlow matching for generative modeling ICLR 2023", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "I believe the authors’ statement that the paper focuses on theory is valid. However, if they aim to provide an improved method, they should at least include standard experiments on datasets like CIFAR-10 to support their claims. Relying solely on simple two-dimensional datasets is not sufficient.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hnnP75ehzK", "reviewer": "Reviewer_NVAq", "summary": "This work provides a theoretical analysis of time-discretized stochastic interpolant models. Specifically, they address the problem of convergence with respect to the number of steps in the time discretization, characterizing the error in the modeled distribution with respect to the discretization scheme, the model approximation error, and the prior approximation error. This extends prior analysis focusing solely on diffusion models while remaining consistent, and addresses the effect of time discretization in particular. Motivated by their theoretical results, the authors outline a new time discretization strategy which can theoretically improve convergence of discrete-time solvers using stochastic interpolants, which they demonstrate empirically.\n\n## update after rebuttal: I believe my original score holds, as this remains a strong paper and contribution.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! We are grateful for your constructive suggestions, which have significantly guided our improvements. Please find our responses to your comments below.\n\n### Other Comments Or Suggestions:\n\n> Right Column Line 170: “initial distribution mismatch (i.e., $\\text{KL}( \\rho(t_0)\\Vert\\hat{\\rho}(t_N))$)” it should be $\\text{KL}( \\rho(t_0)\\Vert\\hat{\\rho}(t_0))$?\\\n> Right Column Lines 361-365: There seems to be a grammatical error here, part of the sentence is repeated.\\\n> Right Column Line 373: aspeccts - > aspects\n\nA: Thanks for your suggestion! We will update them in the final version.\n\n### Questions For Authors:\n\n> Is there some way to selected or design $\\gamma$ to yield efficient sampling?\n\nA: Thanks for your insightful question! Our current analysis regarding schedule design and its associated sample complexity is predicated on a fixed latent scale, $\\gamma$. In Section 5, we adopt $\\gamma(t)=\\sqrt{at(1-t)}$ due to its prevalence and natural appeal, stemming from its connection to the Brownian bridge process. However, the systematic design of $\\gamma$ to optimize sampling efficiency represents a compelling avenue for future research, potentially necessitating a synergistic approach encompassing both theoretical analysis and practical experimentation.\n\n---\nWe hope our response addresses your concerns. If so, we wonder if you could kindly consider raising your score? We will also be happy to answer any further questions you may have. Thank you very much!", "claims_and_evidence": "The primary claim made by the authors concerns the convergence of discrete-time solvers (namely, Euler-Maruyama) for stochastic interpolant models. They provide a bound on the KL divergence between the true and model target distributions, which is a function of the model approximation error, time discretization error, and prior approximation “distance”. The proof of this method is explained intuitively, with a detailed proof provided in the Appendix. This bound is then used to design an efficient time discretization schedule to ensure more rapid convergence with respect to the number of time steps. They show theoretically and empirically that their new strategy yields more efficient sampling.", "methods_and_evaluation_criteria": "While the primary focus of this work is a theoretical characterization of practical methods for computing stochastic interpolants, the authors also provide limited experimental validation of their claims. I find this evaluation very convincing, as they demonstrate the enhanced performance of their scheduling scheme as predicted by their theory. While this is demonstrated on toy datasets, the point is made very clearly.", "theoretical_claims": "The authors provide intuitive interpretations and walkthroughs of their theorems and proofs. I found these descriptions intuitive and easy to follow, and they are convincingly backed by rigorous proof.", "experimental_designs_or_analyses": "As mentioned above, I believe their limited experiments provide sufficient empirical evidence that their theory is sound. While the level of experimental evaluation is not the same as a typical practical generative modeling paper, I believe their experiments do well to demonstrate the validity of their theoretical results.", "relation_to_broader_scientific_literature": "The authors position their work within two main areas in the literature. First, their theoretical analysis focuses on stochastic interpolants related to continuous-time normalizing flows and diffusion. Such approaches have seen widespread application in high-dimensional, structured generative modeling settings (e.g., image generation). Second, they provide an analogous study of stochastic interpolants to those conducted for the convergence and error analysis of diffusion.", "essential_references_not_discussed": "I do not believe there is any missing relevant literature.", "other_strengths_and_weaknesses": "Overall, I believe this would be a very valuable contribution to the community. The authors do well to highlight the importance of considering time discretization in addition to model approximation error in modern generative modeling convergence/error analysis. Moreover, their theoretical insights provide immediate practical considerations that can be employed in stochastic interpolant samplers, as they demonstrate both theoretically and empirically that their proposed sampling scheme can yield better convergence than a simple scheme used in practice, such as uniform discretization. They provide a theoretical basis for designing SDE-based sampling schemes targeting specific error bounds.", "other_comments_or_suggestions": "Right Column Line 170: “initial distribution mismatch  (i.e., KL( ρ(t0)||ρ^(tN) ))” it should be KL( ρ(t0)||ρ^(t0) )?\n\nRight Column Lines 361-365: There seems to be a grammatical error here, part of the sentence is repeated.\n\nRight Column Line 373: aspeccts - > aspects", "questions_for_authors": "Is there some way to selected or design \\gamma to yield efficient sampling?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper conducts a convergence analsysis of discretization of finite time stochastic interpolants.
The authors further demonstrate how their theoretical results have practical implications on time-step scheduling.
All reviewers appear to agree that the paper is theoretically sound.
However, two reviewers raises conerns regarding the novelty of the work in relation to diffusion/flow models.
All reviewers appear to agree that the experimental results are sufficient to demonstrate the theoretical contribution.
However, one reviewer wanted empirical exploration beyond the theory; in particular investigation into the established bound as the dimension increases.
Another reviewer wanted more empirical validation "in the wild" such as CIFAR-10 or ImageNet32.

In a camera-ready verison I would suggest that the authors consider:

1. More clearly explain what the challenges are in transferring previous result on discretization of diffusion models to the stochastic interpolant framework.
2. Empirical investigation of the error bound in relation to the dimension.
Decision: Accept (poster)