Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting
Authors: Aleksei Ustimenko
Aleksandr Beznosikov
Venue: ICLR 2024 poster (2024)
Keywords: markov chains
diffusion processes
Primary area: optimization
TL;DR: Approximating General Markov Chains by Diffusion Processes without assuming Gaussian noise.

Abstract: In this work, we consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Stochastic Differential Equation. The chain we study is a unified framework for theoretical analysis. It comes with almost arbitrary isotropic and state-dependent  noise instead of normal and state-independent one as in most related papers. Moreover, in our chain the drift and diffusion coefficient can be inexact in order to cover wide range of applications as Stochastic Gradient Langevin Dynamics, sampling, Stochastic Gradient Descent or Stochastic Gradient Boosting. We prove the bound in $\mathcal{W}_{2}$-distance between the laws of our Ito chain and corresponding differential equation. These results improve or cover most of the known estimates. And for some particular cases, our analysis is the first.

Published as a conference paper at ICLR 2024
ITO DIFFUSION APPROXIMATION OF UNIVERSAL ITO CHAINS FOR SAMPLING, OPTIMIZATION AND BooST- ING
Aleksei Ustimenko
Aleksandr Beznosikov
ShareChat
Innopolis University, Skoltech, RANEPA, Yandex
aleksei uut imenkol sharechtsareccatt.co co
anbeznosikov gmaii gmail.
ABSTRACT
In this work, we consider rather general and broad class of Markov chains, Ito chains, that look like Muler-Maryama discretization of some Stochastic Differential Equation. The chain we study is unified framework for theoretical analysis. It comes with almost arbitrary isotropic and state-dependent noise instead of normal and inte--indeeendent and diffusion coefficient can be incxact in order to cover wide range of applications Stochastic Gradient Langevin Dynamics, sampling, Stochastic Gradient Descent or Stochastic Gradient Boosting. We prove the bound in Wy-distance between the laws of our Ito chain and corresponding differential equation. These results improve or cover most of the known estimates. And for some particular cases, our analysis is the first.
in most related papers. Morcover, in our chain the drift
INTRODUCTION
The connection between diffusion processes and homogeneous Markov chains has been investigated for long time (Skorokhod 1963). If we need to approximate the given diffusion by some homoge- neous Markov chain, it is easy to realize because we are free to construct the chain nicely, meaning that can choose terms and properties of MC, e.g., it was shown in (Raginsky al. 2017). However, often the inverse problem arises, namely, we have the priori given chain, and the goal is to study
the corresponding diffusion approximation. This task is an increasingly popular and hot research topic. Indeed, it is used to investigate different sampling techniques (Orvieto & Lucchi 2018), to describe the behavior of optimization methods (Raginsky et al., 2017) and to understand the convergence of boosting algorithms (Ustimenko & Prokhorenkoval (021)) From practical experience, the given Markov chain may not have good properties that are easy to analyze in theory. Thus, the aim of our work is to study when diffusion approximation holds for as broad as the possible class of homogeneous Markov chains, i.e., we want to consider the maximally general chain and place the broadest possible assumptions it whilst obtaining diffusion approximation guarantee.
The key and most popular MC is tangevin-bbseer (Raginsky et al. 2017 Dalalyan 2017 Cheng
et al. 2018, Erdogdu al. 2018 Durmus & Moulines] 2019 Orvieto & Lucchi 2018 Cheng et al. 2020) (which corresponds to Langevin diffusion). Such a chain is found in most existing works. In this paper, we propose more general Ito chain:
X = X2 + (b(x))) 5k) + V (o(Xx) + Ax)cx(X))
where X₁ E Rdd is the state of the chain the moment & > R is the stepsize, b Rdd - Rd is the main part in the drift of the chain (e.g., for Langevin MC. b V where f is some potential), 5 E Rd is the deterministic bias of the drift (Dalalyan & Karagulyan 2019) (e.g., such bias occurs if we use smoothing techniques (Chatterji et al. 2020) for Langevin dynamics, or gradient-free method instead of gradient based in optimization (Duchi et al. 2015). or a special modification of boosting (Ustimenko & Prokhorenkoval 2021)), parameter takes values between 0 and (e.g., for SGD case
1, for sampling case 7 = 0), the whole expression / 1 (a + A)c is responsible for generally non- non-Gauee Gan-Gasssian noise, depending the current state of our chain. In this case, Fd dddd is called the covariance coefficient, A E [dddd" the covariance shift and e Rd + Rd the noise function.

---

Published as a conference paper at ICLR 2024
Next, let consider the following Ito diffusion:
d2 b( (Zz)dt + Vn (Z.)dW.
(2)
with Brownian motion W,. This is the diffusion for which we obtain bounds on the discretization error with equation IT
1.1 OUR CONTRIBUTION AND RELATED WORKS
Explanation of our contribution can be divided into three parts: 1) the universality of the chain equa- tion [ 2) rather weak and broad assumptions on the chain's s terms, 3) guarantees on the discretization D
emror between equation
and equation in the Wy-distance.
Unified framework. The Ito chain equation I incorporates a variety of practical approaches and In particular, equation can be used to describe:
techniques see Table T
Dynamics. Primarily, chain equation is suitable for analyzing Langevin Dynamies, which have wide range of applications. Here we note the classical results in sampling (Ma et al. 2019)]
Chatterji et al. [2200] Dalalyan 2017] Durmus et al. 2019) Durmus & Moulines 2019), continuous
optimization (Gelfand et al. 1992), as well modern and hot techniques in generative models (Gidel
itt al. 2018).
SGD and beyond. The use of equation
[ iss also rather popular way to study the behavior of stochastic optimization methods. In particular, one can highlight papers on SGD (Robbins & Monro 1951
Ankirchner & Perko 2021
Orvieto & Lucchi 2018 Hu al. 2017) analysis via diffusions, well
as works (Bhardwaj 2019 Kim et al. (020) about diffusions for popular and famous modifications
1951). RMSProp (Tieleman et al.) 2012) and Adam (Kingma & Ba 2014). Moreover, equation | can be used to describe stochastic methods not only for minimization but for saddle point problems (Facchinei & Pang 2003) Ben-
of the original SGD: SGD with momentum RRobbins& & Monro
et al. 2009 Juditsky et al. 2011 Gidel et al. 2018): minx maxy f(X, and fixed point problems
(Bailion et al. 1978): F(X
Gradient Boosting. Moreover, Gradient Boosting algorithms, in particular, the original one from (Friedman 200T), and the Langevin- boosting proposed in (Ustimenko & Prokhorenkova 2021) can be written in the form equation
Table 1: Matching different methods and frameworks with the parameters of the Ito chain equation and Assumption
GLD
-Fu/1K0)
$00. Sctang nus jac
VEM
V a (1mm( - V
SULDD (enoota
Va(f(X)) JIXA -g3
Opint
[- Du/(M (a), Fy/0,,
50-17 Belesc long
(PAA) Av
0
5A Iudie ax uns
80
JIXA) e
Covc
y Conck)
Ditarko Prbli edura
asuza that the tozo naliptiad by vanoi, Lo. we can like as lagas as we doise when cacelltic evaull approsmnatinn cose (%
Vidembac Proloodoon
P. P.J(0
(/Dww(P)
difloiss
is uuy consuit Suctuats Approieaatin srles soleo If(x) is
sGiil detmed orgiial paper him tynare
add adlection sigeestes
rerginal, ie. proceted in stgiial pope: caus, mach conficients appear we dittibation boxs paper.
Wide assumptions and results. We consider the most general and practical setting for equation
|
see Table Next, we give more details on each of the columns of Table (cooparrc criteria):
Non-normality of noise. The central and widely used assumption about noise in analyses of MC satisfying equation (e.g., Langevin- -aaee) is that has normal distribution (Raginsky al.
2017 Dalalyan 2017 Cheng et al., 2018 Durmus & Moulines, 2019 Ma et al.) 2019 Feng et al. 2019 Orvieto & [ucchi][2118 Chatterii et al. 20200 Xie et al. 2021). However, practice suggests otherwise. For example, stochastic gradient noise in the training of neural networks is not Gaussian for classical and small models (Simsekli et al. 2019). as well as for modern and large transformers (Zhang et al., 2020). Therefore, in some papers the SDE approximations for SGD (Li et al.) 2019a b) et al. 2017 [Cenn et al. 2020). we assume that the noise in our Ito chain equation is non-Gaussian Assumption
2

---

Published as a conference paper at ICLR 2024
Dependence of the noise the current state. Most of the papers Langevin MCMC assume that the
noise is independent the current state (Raginsky et al. 2017: Erdogdu et [0l.220188 Dalalyan 2017] Chatterji et al., 2020: Feng al. 1019iiOrvieto & Lucchi 2018: Xie et al. 2021 However, let's talk primarily about SGD analysis. This assumption is often unmet because the noise in stochastic gradient depend strongly the current weights of the model, c.g., how close we are to the optimal weights. Therefore, we consider the state-dependent noise in our chain equation TT However, our chain, we require that the diffusion coefficient is strictly non-singular and its minimal eigenvalue is lower bounded uniformly from zero (uniformly elliptic, see (Baldi & Baldi 2017). p. 308), which is limitation of our work compared to the analysis done in (Li et al. 2019a).
Cheng et al. 2018 Durmus & Moulines 2019: Ma et al. 20191Chatterii
Table Comparison of the theoretical setups and results on Markov chains and diffusions analysis.
Noise
Generator, 6(-)
Reference
Distribution
Dependence
Non-convex
Non-discipative
Non-uniformil elliptic
W/
Raginsky et al
2017
N+8G
X
Dalalyan
N
Cheng
2018
N
x
/
Erdogdu et al.
2018
N18G
/
/
x
x
x
Moulines,
2019
Ma al
2019
N
x
7
Li al
2019b
N
/
8
Chatlertji et
N
8
Feng ct
2019
|| & const a.s.
x
x
Orvieto & Locchi, 2018
N
x
1
Ankirchner
2021
N
/
Hu et al.
2017
x
1
x
x
x
Xic et al.
2021
N
x
x
U Ustimenno Prokhorenkowa
Mixture
/
/
Cheng et al.
2020
N+5G
v
x
x
x
2019
K||e|l $ const.
Ours
B|d||*
Without convexity and dissipativity assumptions. Note also that often, when dealing with Langevin
MC, the authors consider the convex/monotone setup (Dalalyan) 2017 Erdogdu al. 2018 Durmus Moulines] 2019 Li et al., 2019b Chatterji al. 2020 Xie et al. 2021), which is possible and relevant, but at the same time restricted. This is primarily because large number of practical problems probbeems (including ML problems) are non-convex: neural networks (Goodfellow et al. 2016), adversarial
training (Goodfellow et al. 2014), games (Hazan al.) 2017), problems with specific losses (Nguyen & [anner|[2113 and many others examples. However, even those works (Raginsky et al.) 2017 Cheng et al. 2018 Ma al. 2019 Feng et al.) 2019 Orvieto Lucchi 2018) Ankircher Perko 2021 Hu et al. 2017| Ustimenko & Prokhorenkova 2021]Chheng et al., 2020) which consider the non-convex case make under the dissipativity assumption (see for example, A.3 from (Cheng et al.
2020)). This assumption means non-convexity inside some ball and strong convexity outside the ball. However, not always fulfilled for practical problems and is primarily needed to simplify the analysis.
Here, in addition to examples of non-convex MI problems, we can mention already classic examples of the use of stochastic processes in applied problems (Øksendal & Øksendal (2003). Even the simplest processes of these are not dissipative. For example, one of the best-known stochastic processes, the Ornstein-Uhlenbeck process, can be introduced using the diffusion equation 2 dZ, +odW
wit a;, σ > 0. This process has been known for almost a century (Uhlenbeck & Ornstein, 1930). and has both classical applications and completely new ones, e.g., in machine learning (Lillicrap jet al. 2013) Blanc et al. 2020).. In our analysis, we do not need assumptions about either convexity dissipativity (formally, for chain equation T
we should talk not about non-convexity/non-
3

---

Published as a conference paper at ICLR 2024
dissipativity, but about non-monotonicity of (-b) because, unlike the Langevin MC, we do not assume that b= f) see Assumption
W2 convergence. In our work, give a bound the discretization error in the Wy-distance. This is a common criterion in many works (Raginsky et al., 2017] Dalalyan 2017 Erdogdu et al. 20188) Li 2019b Ma al. 2019). However, in the meantime, the main competitive paper (Cheng et al. 2020 gives weaker guarantees, namely, the distance is measured in Wi First of all, note that from the W2 bound follows the Wi. The converse is not true. Thus Wi-distance can be used when in equation] is a gradient of some potential/loss function f. and this potential is quadratic growth (e.g.. MSE) see Lemma 6 from (Raginsky et 2017). turn, W1 cannot be used for such potentials.
et al.
Edwards 2011)
Best and new rates. We provide explicit bound between the laws of Xx and Zio in W2-distance for almost arbitrary noise:
(7 + 1) + xo) + + B) xo) (2()(()), c(Zx))) = - where 0 = min {a: {a:
4
with Xo [(Gaussian noise). a and are parameters from Assumption |
is from the chain
equation 1 Specific values for a, 3 and in different cases can be found in Table Using this table, it is possible obtain convergence guarantees for the major cases see Table 3
For SGLD, our bounds are the best in the existing literature. In particular, they coincide with the re- sults for the general Muler-Maryane discretization with normal noise- a subset of chains from the fam- ily equation [ For non-Gaussian noise, our results are first in the literature.
Table 3: Comparison of guarantees on dis- cretization error in work with the literature.
Reference
Muzellec et al.
2020
O )
Gaussian
Ours
O )
SGD with Gaussann noise was considered in (Cheng et a 2020), the authors give guarantees in use W2. Our guarantee in W1- distances is (n =), which is better than (11²) in (Cheng et al. 2020).
any
Ours
O(1
W1 distance,
Cheng al.
2020
O(r
Gaussian
SGD
Ours
0
Cheng
2020 i
O(rk) )
In the case of SGD and SGLB (Ustimenko & Prokhorenkova 202T), our work is the first to get estimates on discretization error both cases of noise.
any
Ours
O(nt) )
any
Ours
0(1 )
any
Ours
O(7 )
2 PROBLEM SETUP AND ASSUMPTIONS
W: distance
We consider the chain equation 1 and the diffusion equation with Xo = ultimate goal is to produce upper bound on WA (4(X)), after denotes the distribution of random vector.
Zn vo E IRd Our
for all l: E N, where L here and
We assume that learning rate 77 (0, 1] and 7 E {0, 1} (see Table for details). In the literature (especially on optimization), it is common to assume that the learning rate depends on the properties of f (in our case 6), e.g., typically that 77 ~ L-1, where is a Lipschitz constant of V.. Meanwhile, we can always renormalize the original problem to guarantee assumptions concerning the terms of the chain equation
(0: 1]. Next, let us list the
Assumption 1. There exists some constants Mo 2 0. M1 2 0, M 2 O. 0o IN
0.
01 I 0,
00,3 E [0, 1] (see also Table for special cases) such that the drift b is Mo-Lipschitz, i.e. for x x' E IRd
[[(()) b(x')l Moll=-z'|I-
For particular cases of optimization problems: minimization, and saddle point problems, this assump- tion means that the corresponding target functions have Lipschitz gradients, i.e., are smooth. Hence, we do not need other assumptions, such as the monotonicity of b or, in particular, the convexity of b f.
the biased drift 8 is bounded, i.e. for all ls 122 20 (1 + +|xxa(??)
[
Mf
4

---

Published as a conference paper at ICLR 2024
the noise function is unbiased, has unit covariance, and "the central limit theorem" holds for it, i.e., for all x E IR,, l 2 0 and $ z
E,E (2) Oa:
E.E (x) Ia, (N((,, &
Σ (n(x))) S M²n1²
In the general case, noise can be arbitrary within the assumption "the central limit theorem," " which holds in particular for all noises that have uniformly bounded the fourth moment Blles, (x)) see (Bonis 2020). We also define Xo if the the noise ek is Gaussian, otherwise Xo note that in the first case M. 0.
the covariance coefficient is symmetric, positive definite, uniformly elliptic, bounded and Mo- Lipschitz, i.e. for all x, E Rd
oila 2 (2) = o o=(x)) 2 oola,
(x) (z(")))) Mb 2'11
the covariance shift A is symmetric and bounded, i... for all k: 2
(1+ A = A.. (T S (1 [x
Let also introduce the following notation for convenience: M max {M1 [|6(02)ll²) 2 max MM. do?} } + 31 MP. One can note that such M > 0 gives
[16(x))] + Ir (o(xx)o"
+ ||02|| Ir (A S M² M22 (M*(1++|xxl1))
Moreover, we define the bound on the initial vector zn. RS max(1; ||=0|| Meanwhile, do not assume the existence of some X s.t. X₁ + X because, in the general non -on-dissipative case, the chain equation I
can diverge, i.e., | + 00.
MAIN RESULTS
3.1
CHAIN APPROXIMATION BY WINDOW COUPLING
The first thing to look into is the non-Gaussian noise. In this section, we construct a new auxiliary chain with Gaussian noise that approximates S-subsampled initial dynamic equation I The idea behind this approach that we can use the central limit theorem for the noise function (Assumption D. and note that by collecting reasonably large S-batch, we can approximate our non-Gaussian noise by Gaussian.
We define - esk+i(x). Since for e "the central limit theorem" " holds (Assumption using this new "batched" e, we can introduce
(V5 (]())) I. (N Sta), ((c(())).
where II, is an optimal coupling for Wy-distance. In fact, ( has no closed form, but it is an auxiliary object, and we need only that it exists (by definition of W2) (Cavalletti & Huesmann 2015). The only fact we strongly need follows from definitions of çhe and of optimal coupling we know that c. ~ AO La). We need such ç to introduce the coupled chain (Y ), which is closed to the chain X The natural idea to construct is
YX 7(++1)
x + bY
Vin a (V (Xst),
(3)
coupling vin moise
where we additionally define subsampled learning rate 7 = SSy. The essence of this trick is quite simple non- non-Gaussian noise is subtracted from the original chain equation I and replaced by Gaussian CLT approximation. This idea can show itself perfectly in the case of a f--strongly monotone operator (-b) (which corresponds to strong convexity and strong dissipativity in the case b - -V)):
(b(X)= - b(Y), X) 2 x||x 1l2. In particular, it is easy to bound (Y,X) and (Xss) with
monotonicity:
5
E 7(+11 - x
XX
=
Y (b( +
X
X (ssttt) +...|1²
5

---

Published as a conference paper at ICLR 2024
E mb(( nk) Xsh T)b(Xss) +...|p Elj X 1| 2,) b(Xsk), Vi Xss) +...
(1 دو -ssk +....
If we choose 7) < p0',, then we have a geometric convergence. It allows us to obtain the bound on the difference that does not diverge in time. But this idea does not work in our setting because nothing like (strong) wwt.ooonniciyyooveeiiyyyissppiii
required to hold. Without such a term, those two chains mainly diverge from each other in general, as no structure pulls them closer to each other. This
issue can be alleviated. We need to add one more term. In particular, we inject 7/ [xsk
Y with
some constant L, > 0 (which we define later) into equation Thus, instead of equation we define the coupled chain Y zjk using arbitrary fixed constant L 2 0:
YX T(++1) = rja: + Tjb(Y mi
( T/e ICh (Xsk)
LY -sk Tp
(4)
Window coupling
This additional coupling effectively emulates
E Y m(++1) -X((+1))l2
E , + nL
Xsk Y +... Xsk +... .12
E F X
21y ( (skk
VeX Vix
Nss)
I (1 (1-27/ 27 Y Xsk = +....
(5)
Xss) is straightforward: in order force Y and Xss to be close to each other we "forget" a portion of Y and replace it with a portion of Ssk- Normal noise appearing in Y makes the distribution of Y "regular" and Ly like Le-regularization for Y-X which additionally imposes regularity on Y-X which was absent X 7js:
X Physical interpretation of the additional term (Y 7pt
7/ term acts
5j. due to the non-Gause Gaussian noise and absence of the regularization.
On the other hand, the purpose of introducing YX is to create a Gaussian chain that approximates the ti ) at first glance destroys the normality of Y We original non- Non-Gaussian X₁. But Ln Xss) suggest to look at Window coupling (T
nk Xss) as a biased part of drift. Then the noise in the Y remains Gaussian. Nevertheless, this will give us additional problems in the future that will have to be solved.
Even though reasoning equation gives the basic idea of convergence of TE lot under the dot sign, and these missing terms can have a bad effect. In particular, if we try bound x Y || then we would immediately obtain divergence since the expected squared norm of Xx can be unbounded (as we noted in Section ().iionn)...... Such a norm appears multiplicative bias-related and covariance-related terms (e.g., ö and A in Assumption D.. This suggests that if we temper the dif- ference E. X Y 2 on the bound of the worst-case norm R²(()) 2 max {1; max X }. then we effectively cancel out terms with E| s and obtain "uniform" in knj < t bound for any fixed horizon
Xssk ||
we hide a
0.
Lemma 1. Let Assumption 7 holds. If 2 1 + Mo + M + 2MB + +M² + M2M? and Sn S 1, then for any t > 0:
E Sk - YX 1|2
17 T (1 Xo)
AS max The St
TTk
0
1,20
(1-x0)+ +T
122(1)
where R2(1) 2 max (1: max TEI|Xx11 11
Here and after, in the main part, we use O-notation to hide constants that do not depend on 7), k
and for simplicity. The full statements are given in Appendix. Since the chain YX is artificially introduced by us, can vary S. in particular, optimize the estimate from Lemma
Corollary 1. Under the conditions of Lemma 1 holds that:
If we lake S - (1 xo) + Xo 1, then
1-2
S < <0 (7)0) with 0 = min {a: ( 1)(1 + xo) + (7 + B) - xo)
4

---

Published as a conference paper at ICLR 2024
3.2 NAIVE INTERPOLATION OF THE APPROXIMATION
As mentioned earlier, if we put (X Y Y to biased drift, we can look at the chain equation as a chain with Gaussian noise, i.e. we can rewrite equation Tin the same form as equation |
V 1))+1)
Y + ((((( (2tk) VI
where we introduce Site (X
ajke
For a chain with Gaussian noise, there are well-known tricks for relating them to some diffusion process driven by the Brownian motion process W,. In most of the works, e.g., (Raginsky al. 2017), on Langevin processes from Table one embeds process with Gaussian noise into diffusion without any hesitation due to normality of the noise, which allows one to think that the noises are increments of the Brownian motion process W, and intermediate points are obtained through naive mid-point interpolation (e.g., by replacing 7j with òt for òt E [0, 77 allows to define Y +5)) Since
ch NOaa Ia), we consider c V (W(++))7 Wn,))- One can also complete the notation for gr = - 9i/viin for all (before we defined it only for = s74t with integer k). Then we can define the following diffusion:
dY, = (b(Y)) + (gt + g g)) ( + E))
with new notation 9f =b(Y b((())))))) b(Y)) and Σ o (./.)) (Y)).
The diffusion Y, has a "ladder" drift (since b(V,) + (o² + _ changes only in t = loy), thereby Y, mimicks the chain Y-X. If there were no noise terms in the diffusion and in the chain, dY, would fully coincide with Y Nevertheless, we have noise components, and in diffusion, it is provided by the Brownian process W, and is continuous in time, unlike the Gaussian, but "discrete" noise term in Y (depending on ) We need to estimate the differences in these noises. This is the idea of estimating the difference between V-X and dY, We follow a similar path of proving as (Raginsky et al. 2017), but we also consider that we now face non-dissipativity. In particular, the next Temma gives a bound that includes 1(2(krr), which is not the case of (Raginsky et al. 2017).
Lemma 2. Let Assumption hoold. Then for any k No:
Y E|| (0/(mT Y.
O (
sup kgkn
where R (km)) 2 max [1;
max x
From the definition of W2, we immediately have.
Corollary 2. Under the conditions of Lemma 2 for any time horizon t = kn 2 0 it holds:
(()o))) ((V)) S sup kgky
X B/m
vill = O (2
At this point, we linked the initial chain X₂ to the auxiliary chain You.. and then the chain Yςς the diffusion Y. However, the diffusion Y, differs from the target diffusion Z, we aim for. Therefore, we are left link diffusions Y, and Z, we will spend the following three subsections on this.
3.3 COVARIANCE CORRECTED INTERPOLATION
The problem with the relation of Y, and Z, lies primarily in the fact that these two diffusions have different covariance coefficients (Yi + Σ;) and (Z,)). In that case, the Girsanov theorem states that diffusions with different covariances are singular each other. Meanwhile, if the covariance coefficients are the same, then the Girsanov theorem (Liptser & Shiryaev] 200T) gives more optimistic answer to the possibilities of connecting such diffusions. Then our goal now to deal with y; in Y,.
is proposed to build another auxiliary diffusion. We want the problems of the covariance coefficient in Y, to move elsewhere, e.g., to drift, in the new chain Z We have already done a similar trick with the coupling of X and Y in Section 3.1 Then let us consider the following diffusion:
dzy = (b(z))= - )t + L. )dt + (Z) JdW,
Window coupling
7

---

Published as a conference paper at ICLR 2024
where L1 will define later. This coupling helps to eliminate not only Σ; but also gf- The basic idea that Σ; and 9i are differences of a and b, respectively. At the same time, a and are Lipschitz, which means that we can bound Σn and of via the norm of the argument difference. Therefore, if we choose Ln large enough, we compensate bounds on Mn and g. In particular, the following statement holds.
Lemma 3. Let Assumption Cacimpttioonohooe Tholds. Thenfor L1 2 2Mo + 4MMn" and any time horizon -nn 2
(((C())), 6 sup
Y 1// - Ye
From Lemma we immediately have.
Corollary 3. Let Assumption 7 holds. Then for any time horizon kn 0:
(C(Y))) R7
where 122 (km) 2 max {1; [1; E 113)
To complete the proof, remains to relate two diffusions Ze and z in terms of W2.
3.4 ENTROPY BOUND FOR DIFFUSION APPROXIMATION
With the introduction of the new notation G ge Li(2 Yt), one can rewrite 2 follows:
az. (b(Z)) ddt )t Vi Jaw.
At the moment, the only difference between Z, and 2 is the presence of G in the drift of 2 Finally, when the correlation coefficients are equal, we are close to using the Girsanov thcorem (Liptser & Shiryaev| 200T). However, its classical version requires that both diffusions are Markovian. Unfortunately, this is not case because of G... In particular, J. (part of G;) was defined in Section 5 as follows: gitk = L(Xs* ) for & E No and 9//7) for all others 2 0. It turns out that for t + km), of depends on the nearest reference point [t/r]] 17. which immediately violates the Markovian property. The same problem arises in (Raginsky et al. 2017). The way out of this issue is to prove new version of the Girsanov theorem. The paper (Raginsky et al. (017)) considers the dissipative case where additionally a(-) is constant and independent of the current state. We have even more general and complex versions of the Girsanov theorem without dissipativity and for state-dependent (-)).
Theorem (One-time Girsanov formula for mixed Ito/adapted coefficients). Assume that (Gt) )220 is (W,) 22oo-apteee process with an integratable by 2 O second moment. Consider two SDES ran using two independent Brownian processes:
dZ, b(Z,)dt Gedt + (Zi)dW,
dz; = ((Z
+ o dWW,
Let do be the minimal possible eigenvalue of (xx). Then we have that for any time horizon 2 0 the following bound holds:
D Dcs(((2r)) S op / E||G,|| < 00.
The result of Theorem 1 is worse than the classical version, which is predictably the price of generalization. This theorem be considered stand-alone contribution of the paper. Let us apply it to our case with Z, and Z.Y
Corollary 4. Let Assumption 7 holds. Then for any time horizon = =npl 2 0:
DKL [I o (11 kme
- Oknn
where 9 min { (
8

---

Published as a conference paper at ICLR 2024
3.5 EXPONENTIAL INTEGRABILITY
At the moment, our modification of the Girsanov theorem gives the estimates on the relation between Zay and 2 only in terms of KI-diivegeecce. Meanwhile, our ultimate goal to bound the W22- distance. Therefore, we need connect the estimates for KL-divergence and Wy-distance. Let us use the auxiliary result from (Bolley & Villani 2005) to solve this issue. In more details, for two distributions P1 and P2. we have
W2(p1,02) S Cw(pz) ( (Der)((ill)))) + DRL (pa (p2) (DKK
6
where Cw (P2) 0 relates entropy DKL ( l|pa) with (2(...2): The main challenge here is find or a slightly more general result with p2 - ((.)) for all & 2 O. Related results are available in the literature (Raginsky et al. 2017). but were obtained in special cases: under dissipative conditions and with specthc " equal to 0. The challenge of finding C2p in the non-dissipative case for arbitrary y is solved the next theorem.
the bound on the constant Cp()2) with p2 = (2 for all
Lemma 4. Let Assumption 7 holds. Then for any time horizon 2 0:
Cw (()
The presence of factor n7 for y # 0 is not only novel but also crucial. In the previous section, already encountered this n7. In the final estimate, these two factors will cancel each other out.
3.6 FINAL RESULT
remains combine all the results obtained above. particular, we require Corollaries ! 2 3 and
4 as well as Lemma 4
It is important to note that in Corollary | S= 1 (1 Xo) + Xo 2 has
already been chosen, it needs to be substituted to other results.
Theorem 2. Let Assumption
7 holl. Then for all k E No:
(I(((x)), (1 (k')) ((Wm)) + (
where 0 = min {a; (x+))((+))))+++)1111
4
All (exponentially) growing factors in Theorem depend only horizon T > kn,, which is assumed to be fixed a priory. Thus, if we consider convergence on the interval E [0, 7]. then those factors are essentially constants, independent from 17 Though, compared to the work on SGLD (Raginsky et al. 2017) that relies on dissipativity assumption, those constants grow exponentially, which limits the applicability of the results for such problems as sampling from the invariant measure. Since our results do not rely on dissipativity/coovxxiy assumptions, having exponential dependence on the horizon unavoidable the general case (Alfonsi et al. 2014). Putting the horizon T fixed, find estimates for the
obtain that Wy (C(X)), ((Z,,,) O (17 + +n8+2 From this, different cases from Table [ As an example:
Corollary 5 (SGD with Gaussian noise). Under the conditions of Theorem if Xo y 2 1, then 0 = 1 and
= O (12
4 CONCLUSION
This work considers broad class of Markov chains, Ito chains. Moreover, we introduce the most general assumptions on the terms of our Ito chain. particular, we assume that the noise can be almost arbitrary but not independent and normal. In this setting, estimate W/2 between the chain and the corresponding diffusion. Our estimates cover a large variety of special cases: in some cases replicating the state-of-the art results, in others improving them, and in some cases being pioneering.
ACKNOWLEDGMENTS
This research of A. Beznosikov has been supported by The Analytical Center for the Gov- ermment of the Russian Federation (Agreement No. 70-2021-00143 dd. 01.11.2021, IGK 00000DD33332155000000

---

Published as a conference paper at ICLR 2024
REFERENCES
Aurélien Alfonsi, Benjamin Jourdain, and Arturo Kohatsu- -igg.. Optimal transport bounds between the time-mamee marginals of multidimensional diffusion and its euler scheme. Electronic Journal of Probability, 20:1-31, 2014.
Stefan Ankirchner and Stefan Perko. Approximating Stochastic Gradient Descent with diffusions: error expansions and impact of learning rate schedules. working paper or preprint, October 2021. URL https:://aaaa archives ouvertes. fr/hal 03262396
JB Bailion, Ronald Bruck, and Simeon Reich. On the asymptotic behavior of nonexpansive mappings and semigroups in banach spaces. 1978.
Paolo Baldi and Paolo Baldi. Stochastic calculus. Springer, 2017.
Normand J. Beaudry and Renato Renner. An intuitive proof of the data processing inequality, 2012.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton university press, 2009.
Chandrasekaran Anirudh Bhardwaj. Adaptively preconditioned stochastic gradient langevin dynamics. arXiv preprint
2019.
Imre Bihari. A generalization of a lemma of bellman and its application to uniqueness problems of differential equations. Acta Mathematica Hungarica, 7(1):81-94, 1956.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process. In Jacob Abernethy and Shiv- ani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 483-514 PMLR, 09-12 Jul 2020. URL
wgs. ml wwt..m.......s.sllmmmmmmm http:///v////bmmmaaaa html
François Bolley and Cédric Villani. Weighted csiszár-kullback-pissee inequalities and applications to transportation inequalities. Annales de la Faculté des Sciences de Toulouse, 14:331-352, 2005.
Thomas Bonis. Stein's 's method for normal approximation in wasserstein distances with application to the multivariate central limit theorem. Probability Theory and Related Fields, 17803-)):877866, 2020.
Fabio Cavalletti and Martin Huesmann. Existence and uniqueness optimal transport maps. Annales de l'Institut Henri Poincaré C, Analyse non linéaire, 326 2015. ISSN 0294-1449. doi: http://cciioeearaaaaaaa/////////
2015.
URL
Niladri Chatterji, Jelena Diakonikolas, Michael Jordan, and Peter Bartlett. Langevin monte carlo without smoothness. In International Conference on Artificial Intelligence and Stutistics, pp.
1716-1726. PMLR, 2020.
Xiang Cheng, Niladri S Chatterji, Yasin Abbasi-Yadkori, Yadkori, Peter L Bartlett, and Michael I Jor- dan. Sharp convergence rates for langevin dynamics in the nonconvex setting. arXiv preprint arXiv:1805.01644 2018.
Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan. Stochastic gradient and langevin processes. In International Conference on Machine Learning, pp. 1810-1819. PMLR, 2020.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log lon-cene densities. Journal of the Royal Statistical Society: Seriey B (Statistical Methodology). 79(3): 651-676. 2017.
Arnak S. Dalalyan and Avetik Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applications, (29 5311. 2019. ISSN 0304-4149. doi: http:://oi..rr///0.............. 7/ w/www. sww.eeddeeeeddc.c rect. com/ htt.::/......coaoooooooaoaaaaaaa
URL https
10

---

Published as a conference paper at ICLR 2024
Vladimir Fedorovich Dem yanov and Aleksandr Borisovich Pevnyi. Numerical methods for finding saddle points. USSR Computational Mathematics and Mathematical Physics, 12(5):11-52, 1972.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(S):2788-280) 2015.
Alain Durmus and Eric Moulines. nigh-dimensional bayesian inference via the unadjusted langevin algorithm. Bernoulli, 25(4A))2854-288) 2019.
Alain Durmus, Szymon Majewski, and Blažej Miasojedow. Analysis of langevin monte carlo via convex optimization. The Journal of Machine Learning Research, 20(1):266--271, 2019.
SM Edmonds. Lebesgue integration and measure, by alan j. weir. pp xii, 281. 5 40 cloth, 23 40 paper. 1973 (cambridge university press). The Mathematical Gazette, 61(415):74-7,, 1977.
D.A. Edwards. On the kantorovich-rubinstcii theorem. Expositioness Mathematicae, 2984))387- 00..201111.000000000 106.005, URL https 398, 2011. ISSN 0723-0869. doi: wttp:///cceeeeeee.....aaa///////
www. www.:ssieneeeiiieeoooooo rect com/
Murat A Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with discretized diffusions. Advances in Neural Information Processing Systems, 31, 2018.
Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Comple- mentarity Problems. Springer Series in Operations Research. Springer, 2003.
Yuanyuan Feng, Tingran Gao, Lei Li, Jian-Guo Liu, and Yulong Lu. Uniform-in-time weak error analysis for stochastic gradient descent algorithms via diffusion approximation, 2019. URL
aattps://arxiin org/ abs 00635
Jerome H. Friedman. Greedy function approximation: gradient boosting machine. The Annals of Statistics, 29(5):1189 1232, 2001. doi: 10.1214/as/1011223455. URL
10. 1t.11//200/1013220035
Saul B. Gelfand, Peter C. Doerschuk, and Mohamed Nahhas-Mohandes. Theory and application of annealing algorithms for continuous optimization. In Proceedings of the 24th Conference on Winter Simulation, WSC '92, pp. 494 499, New York, NY, USA, 1992. Association for Computing Machinery. ISBN 0780307984. doi: 10.1145/167293.167407 URL /tttp:::///...rr///
#145/167293.161
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations, 2018.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. 2016.
Ian J. Goodfellow, Jean Pouget-Abadie. Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks, 2014.
István Gyöngy. Mimicking the one-dimensional marginal distributions of processes having itô differential. Probability theory and related fields, (144):001-516, 1986.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization in non-convex games. In International Conference on Machine Learning, pp. 1433-1441. PMLR, 2017.
Wenging Hu, Chris Junchi Li, Lei Li, and Jian-Guo Liu. On the diffusion approximation of nonconvex wttp://or/ab///o/oo
stochastic gradient descent, 2017. URL httpss:::///txtxi htt.:c/pp.//ar....oorr///////// 07562
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with
stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Sehwan Kim, Qifan Song, and Faming Liang. Stochastic gradient langevin dynamics algorithms with adaptive drifts. arXiv preprint arXiv:2009.09533. 2020.

---

Published as a conference paper at ICLR 2024
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Qianxiao Li, Cheng Tai, and Weinan. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. The Journal of Machine Learning Research, 20 (1):1474-1520, 2019a.
Xuechen Li, Yi Wu, Lester Mackey, and Murat Erdogdu. Stochastic runge-kutta accelerates langevin monte carlo and beyond. Advances in neural information processing systems, 32, 2019h, 9b.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 5599009999 2015.
Robert S. Liptser and Albert N. Shiryaev. Nonnegative Supermartingales and Martingales, and the Girsanov Theorem, pp. 219-249 2492 Springer Berlin Heidelberg. Berlin, Heidelberg, 2001. ISBN 978- URL /ttp:///0.//...000.....0...0
1-662-13003-88 doi: 10. 10.1007/978-3 --00/9978.3-66113344---
978-3-662-133
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 1 116(42):0088122885) 2019.
Boris Muzellec, Kanji Sato, Mathurin Massias, and Taiji Suzuki. Dimension-free convergence rates for gradient langevin dynamics in rkhs. arXiv preprint arXiv:2003.00306, 2020.
Tan Nguyen and Scott Sanner. Algorithms for direct 0-1 loss optimization in binary classification. In International Conference on Machine Learning, pp. 1085-1093, PMLR, 2013.
Bernt Øksendal and Bernt Øksendal. Stochastic Differential Equations. Springer, 2003.
Antonio Orvieto and Aurelien Lucchi. Continuous-time models for stochastic optimization algorithms, 2018. URL httppsss//axii..rrrgg.../// wwt.://wwwwr..bbb...oooo.o 02565
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. Conference on Learning Theory, pp. 1674-1703. PMLR, 2017.
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Math- ematical Statistics, 22(3):400 407, 1951. doi: 10.2214/omm/11177299566 URL https
7/doi. wwwoorgg............oooo 1214 aoms 11777295886
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference Machine Learning. pp. 5827-5837.
PMLR, 2019.
Anatolii Volodimirovich Skorokhod. A limit theorem for homogeneous markov chains. Theory of Probability & Its Applications, 8(1):61-70, 1963.
Tijmen Tieleman, Geoffrey Hinton, al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
G. E. Uhlenbeck and L. S. Omstein. On the theory of the brownian motion. Phys. Rev., 36:823 841, Sep 1930. doi: 10.1103//hysRev.36.222 URL http:///hhh...ap..rro//////0.110 httpp//.ooo//////.11//0.00 PhysRev. 36.666 823
Aleksei Ustimenko and Liudmila Prokhorenkova. Sglb: Stochastic gradient langevin boosting. In
Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 10487-10496. PMLR, 18- html
24 Jul 2021. URL. htt.:htttt://ppooeeeeeeoee http....ttttttt:///r/reeee ngs m w.w.mmrr..... www..peeesss.///ssstsssseees wttp://ttmmmmmaammmmmmmam http:r/.ree/////////////eneeonia
Zeke Xie, Issei Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference
Learning Representations, 2021. URL /tttps://operrviiii net ftr.mm/rrmmm/mmmmmommmmooo d==Xxck
ici YGo
12

---

Published as a conference paper at ICLR 2024
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 11111538831133,, 2020.
13

---

Published as a conference paper at ICLR 2024
A PRELIMINARIES
Primary we are going to work with Wasserstein-2 distance that would be defined a few lines later. Wasserstein-2 distance metricize topology of weak convergence plus the convergence the second moments which are desirable properties for an algorithm to have and allow us to consider func- tions that grow at most quadratically compared to uniformly bounded we considered just weak convergence without second moments done in the original SGLB paper.
Now let's define the metric. Denote by
[V, p) {dz1,,, d=z) { r(dx1,) = p / x(..)z)) v
the set of possible couplings of measures p(dx) and v(dx). Then define:
Wa(u, ,1) =
inf +EIl(pu))
Ex 01 - 3/2
Wasserstein-2 distance between measures v(dr) and p(dz). The unique coupling achieving the infinum we would denote as т. = II, (v,
The following tautological statement would be useful when dealing with the Wasserstein-2 metrie: Statement 1. Assume that
given two random variables I1 v2 Iu defined on common probability space with measure n, then Wasserstein-2 distance between v and is bounded by Tog-distance between in and 12:
W2(1, S
Ex |1 x2
Moreover, we are going to use Kullback-Liebner divergence DKL (H|(k) between measures v and such that < μ (absolute continious). In that case by Random-Nikodys theorem there exists j--measurable mapping du that non-negative j-almost everywhere such that E du = and
du
E E, (f d for any bounded measurable f. The mapping du derivative of with respect to μ.. Having du we define Kullback-Liebner divergence
de is called Radom-Nikodym
de du
du de log du 2 0
DKL. (vllu) A Ey log
= suppa du du
The following statement is known as data-pna processing inequality:
Statement 2. (DPI; Data processing inequality, see Beaudry & Renner (202)) Let T we some u-measurable mapping and v & measures. Let T+ e u(T (.)) - push-forward measure under mapping T. Then we have an inequality:
DKL (T [ (KL(U))
kn) and L(Z, : kn) for certain diffusion processes (Xt)120 and (Zi)22 with the same diffusion coefficient (to ensure absolute continuity since otherwise the measures are mutually singular due Girsanov theorem) so that Radom-Nykodyy derivative exists and henceforth DKL (1) (4) < cp. As push-forward map I we consider ((Zz)o0ssH)) Zun Then T is m-masuurable with the property T lt L(Xx,) and
We are going to apply DPI J L(X,
therefore we obtain:
DKL ((X),)))) S (v|lp)
DPI can be trivially proved: consider minimal r-algebra generated by pre-image of the given a- algebra under mapping T'. We denote such o-algebra Fr. After noting that T4v < T if < we consider mm-aauurable random-variabe B(dk Fr). Then di
TTæn exists and d2
F()
aT&
p-llmost everywhere. Then conditional Jensen inequality applied to KL implies DPI. In the work we going deal with a wide range of sequences in the form:
r S 101 ()rr)r 1102
14

---

Published as a conference paper at ICLR 2024
with ro 0, < non 1 and 02 2 0. Iterating such sequence immediately yields the formula:
mk S (1 - 101-1p0 11- 1 02 "2
01 01 1
Clearly, in order for the bound be sound one needs 02 01 The following theorem plays significant role in the proofs of our main results:
Theorem 3. (Girsanov, see Theorems 12.1, 12.2 on p. 368-370 in Baldi Baldi (017)) Assume that we are given two SDEs in Hto form:
dXi, (x L)dl oe ()d,,
for E {1,2] and where Wt is standart Wiener process valued in Rd. Denote by μ4i L(Xi, 0 I t t T) for some fixed T > 0. Assume that functions be(x, t), (x,t)) are Lipshitz continious in x of (x, 1) 2 or almost everywhere in x for some constant or > 0 and for every t [0, T). Then #2 & μn and only if o (z,t) = (2(x,t) (æx almost everywhere in Rd
and (2,
vt(0 & t 1 T) and the Radom-Nykod derivative is given by:
du2
= c (r(()))))))
du
Where we denote Ab(a, t) & {alæ (((i,,t)--(eee (b2(Irt) - b1, t)) and:
(X) & / (Ab(X,, s), dW,)) / Ab(X, 8) ds
Io Matringale
where X (Xt)ast any vector valued continuous path defined over [0, t].
Moreover, the following result due to Gyöngy (1866) would be needed within Girsanov theorem:
Theorem 4. (Gyongy Gyöngy (1886) Assume that we are given the following SDE:
dx, = B,dt + o,dW,
where (Bt) (dt))20 are some predictable w.r.t (Wt)120 processes. Let (Xt)ezo be solution. Then ((x:) ((X,)vt 2 0 where (Xi) solution Ito SDE:
ax. = g gxx, t)dt + o6 (K,, where g(x,t) A B(B, x)) and (zx & E X, = x))
We also consider the following construction: for a chain (Xx) in the form:
X = X BB + NOa, no Ia) Ia)
where (Ba)KEz_ is (Xx)kez, -predictable, we define the process X,;
dX, = -- B,dt + odW;
where B, A Ex=o Bg Bgllejnk. Then we obtain that:
C(Xx: E 24) = ((X(k)) k E 2.).
Combining with the result due to Gyongy we, moreover, obtain:
((X.) L(X,) 0,
where (Xx)120 satisfies Ito SDE:
dx, = -E X,)dt odW,,
We call such processes (X,) 1)2 and (Xt)220 as interpolation of the chain (Xı)kez, into the con- tinious process. The core idea of interpolation is to obtain a bound on DKL between the chain' law and some other chain' law by interpolating them into continuous processes Ito form (recall that (Xx))2n is in Ito SDE form) and then by using Girsanov theorem followed by DPI to switchback to the chains.
15

---

Published as a conference paper at ICLR 2024
Theorem 5. (Deterministic Bihari--aSall inequality Bihari (1566). Let H be constant, xxt) 2 0 0a càdlág function for t 2 and A(t) 2 0 a dec-asscgg function càdlāg function with A(0) =
Let w(xx) > 0 for x: > 0 be continuous non-decreasing function on 12 Let (()) = Sc ,ो. dr for some C O. If function z(t) satisfies:
x(1)= [' w(z(())dA(() + HVI E [0,
for some T Dadd H > 0 and (H) + A(t) is in domain of W- then:
x(() - W (W( + A())VL E [0,
B MISSING PROOFS
B.1 USEFUL LEMMAS
Lemma 5. Let Assumption
7 hollds. Then for any k No:
1+ 1+ B| S ekk + ||00ll)) a (km),
where C' = 1 -8(1+M²)
Proof. Using the definition of equation
we get
[ 2| || 1| (x,) + +n + (ox))
(xx) (2n))) (X.)
where & = 2n (0 (Xx) +x)
Xx + (b(x))) + 6g)).. With unbiasedness of e (X²)).
we have that IE X 0. The other terms can be bounded with Assumption and notation of M
(from Section 2 as follows:
[b((x) + 6x 2 S 22 + (M
(x+t) + +L) (Xa) I| & 2M + |
(9)
(X,, (Xx) + 6x) S 2 (1xx|12 + (1b(x)) + +x1l3) s (1+ (1 (xx)))
It gives the next estimate:
1 E X 2 +1+ X 2| + ( + 1x12
+n - (Xx) 27 6(X)) 5k)
+1+
+ 2n) (1+ 2² (1+ + Xx11)
Running the recursion with C = + + +n), we obtain:
1 E|Xx11 < (1+ + Cn) 8 (1 + || lo log(1++m) (1+ ||x0112) S ckm (1+1oo0)))))
Using that 17 S we get that 2(1 22 17x + +n) - 8(1 + M2). It finishes the proof.
Lemma 6. Let Assumption
7 hholds. Then for any k, i No. S N (such that i < S):
X X X5 < Cnin(1 + sx
where C" = 1222 (C+1)s( and C from Lemma
Proof. Similarly to Lemma we obtain:
|Xsk+i41 1 = X||Ssttitt X (Xstts xst)ll
= -|| X 12 + + 1 (1 + 0suttll 11
+ + (x(xu++)) + ASk ess+))
16

---

Published as a conference paper at ICLR 2024
+ 2m (Xx++*+ Xsk. b(Xsk+i) + dsk+i) Esk+is
where Esk+i = 1 (1 ((oo((((s)))) Xsk+t) + AsktI)EsKti X + 1y ((ss++4) + dgs+s)).
With unbiasedness of esi+ii X Ssk+i), we have that Elşsk+i ess+i X sk+ti) = O. Now, using the bound equation 9
taking the conditional expectation and applying Lemma for X Xskti,
Xsk, we deduce:
[ss+i+1 Xsx [sx
=B|| - X [ss] + / + d5k+s [
+y B[(( ASRH))ESHH) (Xx) 11 Xsa]
+ 2n ( - Xsk. b(Xs++s) + 85k+s) + B[ssk+s| Xss]
5(1 + 7) E || Xsxll 2 + (n) + 1/ b (sk+s) + 65k+s 122 [sx
Ask+s) X (Xskta) ||² |xsa
+ Bllo
<(1 + n)) Xsk 1 X
+ 2t + 1/ +7 M/ (1 + [|||X (1((s(
(1 + [| - ssx {sk]
+ 2(7 + , + 1/ 2 Cin (1 ||xsx11)).
Recursively expanding the bound we obtain:
E [[| Xsk [|
Σ (1 + 2MM cin (1) 1 17 17)) + || 1²)
j=0
2M + + 17 (C+ [xsxl3).
With i < S and n S 1, we get
B[||sstii - Xsull Xsa] & (C+1)Sn (1
Remark 1. In Lemma and after we use that S - - (1 - Xo) + Xu. then Sn== 2 311- Xo)
143
Xoл S 1. and the result of Lemma [6] can be rewritten immediately as
Xsk+s Xs* 11 X s C'in(1 + ||x
where C² 12M2 and C C= + M 8(1
B.2 PROOFS OF LEMMAS
Lemma 7 (Lemma] any > 0:
Let Assumption 7 holds. If 2 1+ 10M3 7L < 1 and Sn 1, then for
X|| -YX 12((1)
(1 ( 11 7
A
C"
(1 xo) +
max SK'S
S
where (t) 2 max {1; max { and C" = 2 (3MfeC + +3330' " + 4Mfe + 48M3 C+ + M3) where the constants C,C" C" are defined in Lemmas To aands) respectively.
Proof. Let us consider the difference between yx (conditional on X and get:
7(++1) and X {5(K+1), square it, take the expectation
E X 1)++1) Xs(k+1) 11 Xsx]
7 +
$
(b(Xstt)) -b(Yx)) + +8sx+1) / Xsk
=(1 -11-77)
|| np
X
Xsk
S2
0=0
17

---

Published as a conference paper at ICLR 2024
S-1
+ - Lajh
E
Xsk: 5 (b((5x+t)) - -((T))) + dsx+i)) [sk]
+ [||
1
Σ (o(Ss*+)) Asst)) - 152 (Xsx) Xsx
VS ==0
<((1 LT)) + +7(11
LT))
E A
Xskli Xsxll Xsa)
+ 7 + 7711 - LT)
S-1
(b(Xs*+)) - - + dsx+t)) 19 xxxx
52
[1|
1 VS
(o((su+)) + (Xstt)ss (Y (Xsx)
[|xa]]
(10)
In the first step, we also used the unbiasedness of (sk++((ss-+) (in the same way as in Lemmas 5 6). this makes all inner products with 65k+1 (X (K4) equal to in the expectation. the second step, we use that 7 < 1. We start with bounding the last term. One can make the following estimate with Assumption and Lemmas
8-1
Σ
(o(Xs)))) + (SHH)))) (Xs=))) Xsa]
E
VS ==0
8-1
1
A Ast-rssttxXs4ttt| Xst]
41
+ 4E
0
x
1
ESk 10n-i(Xs) (Xss) - -x ["xss]]
+ +4E
(o - -o1
&e (Xsu) |1² [sx
Next, we use that for i E (ESK+s (Xs++)), Besut (X [sk] and get
(X Ssk+ [sRR
8 1
(o(Ss++i) + Ask +sst - Le ce (X (Xsu))|(Xxs)
VS
1=0
E (ss X
S-1
+ Σ
E ||||
- a (Xx)))ss)
8-1
VS Σ EskHi(Xsk) c6 (X (|
+ 4E [Xsx)(
+ -o [ss]].
Assumption gives
1 VS
$
- (Xss) | Xsx
E
(o(Ss-i)) (X4+)))
4 8
1 X Xs*+s| 11x
2a
S 1=0
18

---

Published as a conference paper at ICLR 2024
4 8-1
+
Σ
Xs - xsx112|Xss)
5 1=0
+ Ado
[||
1
(Xs+) 2x
(Xsx))
[xx]
VS
+ +4M
Xss - Y
where for the last term, we used the following chain of identifies derived from Assumption I and noting that ((o e& (x(x))) 0, -00-:-/cccoo---0000000----------
(x()))
Mg -- =
4
[ - - - |
- ((())
1 +(() f (z)')) ((((((())((((")))) |
ml((((s)
(110) cu(z))
+
2
- -((x))
2
+o)))() || Bl( - (odd))(()))) +<())))))))((()))))))))))))))))) |
2
4
4
[ ((z))) a(r')) || + - = (<x'))) + +x((1))) 2
2 o(x')(()))))))))))))) - Bl((((()) alx')) (zx')))
>
Taking into account that 5 (Xss) is an optimal coupling (Section 3.1 we can estimate
Dio E5R+i(Xsu) c (xs)) by Assumption
$-1
(o(Xs + Ass+ ( - (Xxx) |2 Xsk
E
Σ
VS 0=0
8-1
Mf 2a 7 (1 + E X s [|x
1=0
$
M [[ Xsk+i - Xsal12|X0 [8a]
4
M² 4M²
Xst XXX
5
With Lemmas 5
one can obtain
(X(Sst))) + +AsHt))sS
c5 (Xss) ||xss)
[SS]
VS
4 S-1
4 S-1
Mfn 20 y (1+ 1) +
Σ
MR 12M2
22M2211+11000 (011))90)) + sxxxx
5 1=0
s
1=0
+
M?n + 4MIE
Xst
[sk]
5
19

---

Published as a conference paper at ICLR 2024
<4M 2 (Xsxll9)) + 48M ( + ||xsx(l))
AdoiM3r + +4MBB ||| Xs*t - -xxx' Xst
5
(C++)) + Ado7M{? ( (1p0-1 +n 17 -xx) (1 (1+ ||xsx
S (MMPeCs)
S
+
4MB
Xsk - x
Here we also used that Me = if Xo = 0. Taking into account Sn S 1, we can deal with e eSn S e::
S-1
Σ
(o(Ss++))
AsA 2 (X
|xxs]]
[Sk]
VS
$ (MMf + 48M + 4do (1pa-) + + ( -101100 x0) (1
[xsxll))
S
+
+4M3 Xsk Y
(11)
For the drift related terms we also use Assumption lnd then Lemmas 6
8-1
E
Σ
(b(Xsu+)) - -b(r)))))) + 6sk+ Xss]
1=0
8-1
E ((Xs++)) - b((x)) + 5sx+e) 19 [xx]]
<
<5
E 3110s2++111 +316((xx+++)) -00--b(4 b(xss))1 +3)(((/))) b(Y;)) )11² X
5-1
<5
Σ
(3 20 (1 + EE X|s+ + 3II
1=0
+ +35 M3 \ssk Y
<8 Σ
2
Cin (1 + |x + 3M s(Xs)
i=0
+ +55 Mτ Ksk Y 1
<S
CSn + 3M (Xx=l) +35 20 e 13
333 M - -xsxll"
Taking into account Sn < 1, we can deal with CSn < e
S-1 E
Σ
(( - (3M の
(b(Xs - + 6sk+il) Xsh [
1=0
|X 35 ME - Xsall2.
(12)
Combining equation T0 with equation TT and equation 12
we obtain:
E 1(++1)
113 < 2L7 + 1-72² + 17 ( X
+ +(7² + 7 LT)) L3M 20 3M + (|x
+ + + + - LT)) 3M Xs
87 (1 [xo Xo)
+ mm -4 (MRe + M2 C+1 + do? 7,200 +
(1 + ||x
S
+ アフ7 -M36 X - Y
20

---

Published as a conference paper at ICLR 2024
<11 - -1 -1- 3 - -M 1 - X
(3Mee +3MBC' + +AMGC + 4 + 4dla M2)
17 2 X0)
1/20 + 11 1j + क/ + + ワリ +
(1+ + [|x
S
With 1 1 Ly S 1 and 1) = Sn S 1, we get
Y 1) X X [)s
22 (3MPE +3M,C' +MMf + +48MAM2 4do7
11 18 (1 -x00) (1+ (xxxxl1) 1
20 + s
Definition of (t) finishes the proof.
Lemma 8 (Lemma) 2
Let Assumption
1 holds. Then for any k E No:
sup
E
Y [p/T]T
Yall² C27 R² (k7))
kkkn
where R² (ke) 2 max {1; max E 133 and C2 S 4(L( + M2) (1 (1+30") (1+ (==1)001)) (for
the definitions of I, and C" see Lemma
Proof. For [t/T|n + we write:
Yi ||
E
Y.X
266 L'El| Kit/ii - X 226 + 217 +
X
1t/0// 13)
<228=M + 4MM
(28 + 4M4
Xums|1²
<MMPSM 2n )1 + ||:00| 13 + (Sn(
L
+1) + 277²)
max E Y X
XA. 11)
M2
Sp
< <(2212 + Mm + 2M (11 ||00|| d
E B
X 12)
max ty
Lemma 9 (Lemma 3, Let Assumption hoods. Then for I1 2 2Mo + 4Mo'7 and any time horizon t kn 0:
B E - -2,11² S sup E Y Yr 1|
(E(C),,), s
r'tt
Proof. Consider process Qi Yv Z Note that Qo Od- We have the following SDE for the process Q;
dQ, = LiQ,dt + (b(Y (1/m))) - b(z)) d) + 22 (1/m))) o(2)' )aw, = - L1Qidt + (b(Y;) - ((Zz))) + (6(Y b(Y)) )dW, + (Y (Y)))
+ (Y)) - )
Now, by applying Itô lemma (see Theorem 8. p. 220 and Remark 9.1 on p. 257 in Baldi & Baldi 2017 ) to f(x) = x² we obtain the following bound on the process 112
112e11 < //² (- +
6(Y2) b(z))) + 4r tr (((())) - -o(2) )²
+2 - b(x)))1 + Lr
&
21

---

Published as a conference paper at ICLR 2024
XX $ $ (1-21, + 2M 4M1 (2Mo + 4M6nn))
xil() Ec. ///7]7
where &. = /21 So (2Qr. (o (t/m]o) ( (Z)) (wW,)
Next, by noting that Eo = and & by it's definition is martingale process we have ES, (see
Remark 9.2 p. 264 in Baldi & Baldi (2077) and, thus, by taking expectation E| Qel? we arrive the following bound:
E 1112
S $ ((-21 2Mo + +M (2M4 + 4M
Yxx (1/T/T
- Yı 111
|'" (1221 MM 4M23))) (2M + 4M
y
< / (1-2L) 2M + 4M (2Mo + (alppp)uuupp
Ye 1=)c)c
10 /
Recall that we can choose L1 arbitrary in the definition of zi We want to make sure that 2L1
2M +4M3n² < O. In that case, will obtain that 1||
2L,
(2M, (2M+++MM7")
2M 1M su
Y
Te' /
Yu || To simplify the bound, we are going to require (2
2. -M5"' S 1. Thus, by considering
Li such that -2 + 2M + 4M < (2M + 4)3,") the lemma implies due to the fact that (C(C), ((Z)) E z Q.1??
B.3 PROOF OF THEOREM 1
The proof idea relies on multiple applications of Theorem 4 to get a process for which the classic Girsanov theoremBJolds To apply the theorem 3 we must ensure that the final process is Markovian
diffusion, for which the Novikov type condition Eela [T(Z..0)] ds < co holds. While 4 will give us Markovian property, to get the Novikov condition, we are going build sequence of intermediate processes using stopping time т, = T A in f.6 || Zz )| dt 2 r?} and then we are going to select subsequence Tn To do the former, we will prove the following Lemma first.
which in the limit will upper bound DKL for the original process Zt.
Lemma 10. Assume that Zi...., Zk.... is a sequence of random variables converging in law the random variable Zo and such that '5; A aC(Z.) for some measure μ vi E 10.)....). Moreover we assume that DKL (Eah4) (n) soVi E (0, 1...) uniformly and that measure μ is non-singular with respect to standard Lebesgue measure on Fdd. Then it holds:
dy.
(EL(EuH((m)) I sup DKL. (kxPEEulll <0
k21
Proof. Let's define the following unity partition system Pa, = (1m2" (m (m+ m
n2", E No u { ((, oc)) For each density & we define
(,(( = Σ 1A En (Ex(AA))
20
((A)
AEP
I (Ex) is essentially finite-sum approximation of Lebesgue integral of Ex. Let e<n Ex An (i,,(E n... We have:
LA E (ES"1A))
1 E, (55"MAA))
Ep (1ES" -E(
T. (A
Σ
Σ AEP,
1
m(A)
n(A)
m(A)
AEP
AEP.
Consider taking subsequence kn such that [E, - < (()" Since & is convergent in law to Eo have that E convergent weakly to een l oc, hence for each and for each A
22

---

Published as a conference paper at ICLR 2024
Pn, there exists A large enough so that Vk 2 A we have E ( Since Pn is finite we can define kn = maXAeP, Ain,A < co, which satisfies [E ((Sr. -ED -0 1 2-"x(AA for all A E Pa-
50 ([A))))))))) 22 =2"x(A))
Thus, we have:
E2 (So
Σ
1
2
m(A)
AEPa
Moreover, observe that 50
ExEP, S LA since Pr, is unity partition. We have almost surely:
Ey (56 (55"1A) IAA)
Σ AEPa
1A
S
Σ AEP
B (less sup co- ess inf Eo (
& max A "n
((A)
A
A
where A ess S 5o eCn ess inf 5 By definition of Pr we have that A AhD $2- which by combining both inequalities implies almost surely:
50th 2 n+1 - (S..E. 5 + 2- S (
Note that (1 1, therefore, by dominated convergence theorem Edmonds 1977
with Data Processing inequality 2 DRL. (Tx. (Tn,E,, ( I DEL (Sx., / 11)
we obtain
supx21 DKL (ExM/ (p) 2 lim DKL (plla) DKL (EopAl/a)) which finishes the proof.
By applying Theorem 4 we obtain the process (Z,)120 that has the same one- time marginals as the process (Zi)
Proof of Theorem 7
dz, (b(Z,) + Bgi Ze o
Denote by ((, & B(gil /1 = z)) We have that DRU( = DKL(F(ZT)((((7)) Consider defining processes Z for 2 0 as:
dzp = (b(z)) + (2 1)) + o (Z))dW,
where we define the following progressively measurable process (, 1) 1 is stopping time, i.e. {r, = t} is me-measurable vt 0. Moreover, we have the following property Z,leer, 2 lecr, holding almost surely. Moreover, T, + T as - due to the continuity of probability which implics that 27 + Z,Vt E [0 holding almost surely + co. And, finally, [
1.6' || g gZz (f 1). Denote by T, T A inf=2o(_" Ila(Z..)) 2 r2). Clearly that
eraj
we can rewrite 7, (ZT,)) t s((2 11l <イ²) ((Z
[itcr,)(Z1,, t).
By applying Theorem 4 again the process )r20 we obtain the process (Z)) that has the same time marginals:
dz, + (Z, = Z,)dt (Z,)da,
Denote by Jr (2, = (ZT, = r) and by WT W.+ o (Z, d)s Consider process Zi in the probability space where W is Wiener process and satisfies:
dz, b( 22 dt + a (Z))dW;
Let pT A L(Z; : 5555 T) which is independent from r. Let of 2 L(Z, S1ST). T). Note
that the Novikov condition holds Eel (.))) ds < " -, < XV > 0. Then by
applying the Theorem to Zr and Zi we obtain the following sequence of inequalities:
DKL (vt(lPT)
Girsanov,
[o,) ( (Z,,)
Operator norm
S T
E
gr [Z,, t)){2at dt
Same marginals.
-2
E (Z 1)l
Jensen,
1
-2
T
El|g, (2) D)IBatt
0
23

---

Published as a conference paper at ICLR 2024
Due definition of Tv.
Fr
E g. (Z, f)ll
Due definition J.. 27
-2
"r
E (Z t) l
00
00
j
S
Tand |1.11 11
00
-2
IE g Ze, /
de
Same marginals, f
00
-2
R g Zz. 0| dt
Fe. 11 5 Bl
IR: 90 ||
By ussumption
0
002
where we use Jensen inequality as |E 2|2 S EII- 11? whenever expression inside of || || was obtained from application of Theorem y and use property of the same Theorem 4 that one-time marginals coincide for processes that we obtain from applying it, which implies equality of expectations.
Then we have that Vr 2 0 the following uniform majorization condition holds DKL (uF (1T) S
To 2 Jo El|st|| ds < co. By Data Processing inequality 2
we have DRL. (2(()) ((Z+)) S
DRL.
( (T)) Using the fact that ((Z7) ((Z)) obtain majorization condition:
/. E||g:|| ds <ss< co
DKL(E(ZE) S DKL (1 0o - By noting ((27) + ((Zr) as + cc and DKL ( (E(Zr)) < <0 by Lemma 10 we obtain:
DKL. (A(r))))) S suup DKL. (C( (C(ZZ)) 50 %/" E 1 ds xc
r20
Finally, using property ((Zr) [(ZT) obtain the desired:
DxL. (c(Z))) S o0 -/-
{[" S/" E||g
B.4
PROOF OF LEMMA 4
Proof. Recall
Chy (C(Z.))
min log B exp (₂ + all =1( z1l") a>0,zER<
To prove that bound we consider the following ODE with z(0) .o:
de b(=(t))
dt
Using it as 2 t xtt) and a + a(t)
Mae -22tt for m 2 Mo E) we consider process Ado7y7
S, = ptt Z,) for ptt, = ==00)|=-2(01= Note that
a;p= at) 2 =()) 2m|l2 - (tt)))))(((( z).
By applying Itô lemma (see Theorem 8.1, p. 220 and Remark 9.1 on p. 257 in Baldi & Baldi (007)) to S, = ptt, Z,) and taking expectation, we obtain the equation:
dEs, = E. (aup(1, Ze) + Ap(t,, Zo) dl,
where we used the fact that (dW,, W.) = 0 to eliminate all terms with dW, (see Remark 9.2 on 264 in Baldi & Baldi (2017). Substituting there definition of yp we obtain:
dE,((, Z,) (/tp::/:hhhhhh..a...mmm/oooo--/d
- 21) -
(Z))) (((,,,)) )
Simplifying yiplids
dEp(1, 2,) = =B(a((( - 2mll= - =(0)))))
24

---

Published as a conference paper at ICLR 2024
TT ()T((o(2))2a((t44 + da)(t) -2) - 2)) )))) (00()))) g(t, Zi)
Since (x) & a la we bound the last term a Zr 24 11 Thus, by choosing 2 Mo(1 + +) ) we can ensure that 2a(t)m 2 a (t)ddo]]] =1 and, therefore, to upper bound all
p(t, Z,) S dof Z.). Which in turn allows us reduce the estimate of w(t) Eea(t) 2. -=(2()) to deterministic Bihari-LaSalle inequality 5
quadratic terms by zero, leaving contribution only from term 2a( (o(Z))))
w(t)= [ w(t)dA(t) + +1,
where we denoted as A(t) 1:00=1--0 (SiMae (1 (1-e 22m)) = 0, 0, / Mi gives us bound
as - +00.
Using
w(1) S exp (( (oiMoe, (1 - e --==))))) S exp
o oiMo
m
m
Finally, we obtain (C(2))
< 177
doi (o (2 + r+-)) by noting that OW (E(Z)) S Mo
log (e2 (()) पt. + proof.
and substituting formulas for w(t) and a(t), which concludes the
a(t)
Remark 2. Constant > can be chosen arbitrarily. smaller values lead to tighter asymptotic behavior, while larger values lead tighter constants on finite horizon T. For simplicity, we choose 8 == 1. Therefore, we have that
2d Mo
Cw([(Z)) S 1 Mot
Remark 3. This result aligned up to constant multipliers with the result of Remark 10.4 on p. 319 in Baldi & Baldi (017). However, there is explicit expression for some constants or proof of it in Baldi & Baldi 2017). Nevertheless, they claim that a = a(t) can be selected arbitrarily as long
$ < e (as in result) for arbitrarily small O. What's important here is that the order of growth e ((T)) is the same, and the scaling factor O O(}) which extremely important for the main result of our work, without which we won't be able to cover the case of 7 = 1. While it may be interesting to derive the sharpest bound regarding exponential growth, we assume that horizon T is fixed in our work. Therefore, the bound and order of the bound in Lemma 4 are sharp up to constant multipliers.
as 2Toī This is slightly better asymottically for T -
Moreover, in Baldi & Baldi (2017), this similar result is claimed be true under the assumption of uniform ellipticity and uniformly bounded diffusion coefficient (i.c., 0 < S (xx) S 01 < coVa) which is aligned with the Assumption
B.5 PROOF OF THEOREM
To prove the Theorem, we first will apply Theorem | to obtain the bound for the very last step in upper bounding, i.e., between z and Z.- Since that theorem gives bound on DKI. we are going to use transportation bound (Eq. to obtain the bound on Wz. After that, we have bounds between all subsequent pairs of processes that have built: Xsk: Y Ynk., Zy Zw Thus, triangle inequality allows us to upper bound W2 (C(Xx)),(ZZe)) subsequent process.
by the sum bounds between each
Corollary 6.
We have that for time horizon t = 1p 2 0 the following bound holds:
DKL. (EL,( Sn Cakn (180 + 17 TB (1 xo) + +7
where C3 < 2112C" (see Lemma 7 for the definition of C",, Lemma 8 for the definitions of L and C2 and Lemma Sfor r the definition of T.).
25

---

Published as a conference paper at ICLR 2024
Proof. Recall that Z has the following SDE:
az (b(Z)) Gt + Vi JdW,
where G. (1/()) ((mn)) Tn - -Y.). By applying Theorem 1 to 2 and Zz we obtain the following:
2
L E G
DKL (C(Z))) [(()))) -
07
2
kn
E [X ((/T)))) 12,2 - xx)
00
1f
Jo
kn
( (/ - -
13B1ZY- - xill²)at
00 Jo
By using Lemma
3
we obtain the bound:
DKL (F(2)))
((2n)) (((z))))))(
2
(L
p/mm - X 1 Lisup /./ - -xlli)a
10
2km
El X Lisupice, (s) Y. )11))
(L'supicun
Next, by using Lemmas] 1 [aand] 2 we bound both terms to obtain:
2k1 (2n2((e))C" (1pa + x (1 (1-x0) ((n) 177002 2
(rL(((ZZ)))((Zz))) v
S
Finally, by noting that 17 s Xo)
+
T7 + we obtain the desired result.
Proof of Theorem 2 Let's introduce constant 2 + 10 (1 (1- Sn (appears first in Lemmal Xo 1 iff ex is Gaussian (see Assumption[]), We want to produce bound on W2 L Zyne To do so we consider k' Sk i, < and rewrite as:
(((C(X))
W2(C(XH), ((Xsk)) (W,(()))))
We note that L2 norm between random variables upper bounds Wasserstein-2 distance between their distributions by definition of the metric. Therefore, the first term is bounded by Lemma
W2(C(Xx),, ((Xss) < c' s br
To bound the second one, we consider the following trick:
(()))))
Wa(C(Xss) (W.C) ((Y,t)) W22(E(y , + W2(C(2) c(Znx))
The first term is bounded by Lemma 7
W,(C(Xss) (())) S C"R(k'))
where C" is defined in Lemma 7. The second one can be bounded by Lemma 8 as
W2 W2(C(Y ((Y,w)) < (2() R(K')) S C2R(K')8
The third one by Lemma D and then by Lemma by the same upper bound exactly as the second one. To bound the last one we use entropy bound on Wy (equation 6
W2 ((Z)ar)) & (w(C(Z)) (D (C(Z)) || + D (E(Z)) (E(2))))| (I
and by using Corollary with Lemma 4 and Remark 2 bound it as:
Wa (a(C( (
26

---

Published as a conference paper at ICLR 2024
2d
3
Mo
2d
(
$
Mo
Finally, obtain the bound between W,(C(X)) by summing up those bounds and simplifying:
((2xa))
(k Mok'n + Rkk))) + + +Co(k')) MoM
Mo (km)) +54,
where C4
2d
σ1 5.
C.
C" + 202. Co
(2td Mo 0. and R(k'n) 5
Mr
C4(M+1jE'0 /1 + | by Lemma 5
Recall that 20 +
S xo) + St,, thus, to eliminate S set S n - (1
Xo) + Xo- Observe that Sn = 2 (1 Xo) + Xo7 I 1. Moreover, by defining 0
min aa; (ott))+Hooo ). from Corollary we have that å S 3n220. Substituting and
re-arranging the constants yields the final expression the form:
We (x(((()), o(1 (k') mp + (k'n) =e o(k ownn +p
where constants depend only on defined in Assumption |
27


Reviews:
[{"review_id": "KKIhDAoE0J", "reviewer": "Reviewer_i2Nt", "summary": "This paper considers a general class of Markov chains called Ito chains that cover a wide range of applications including sampling, optimization, and boosting. The paper provides bounds for the approximation error in W_2 distance between such Ito chains and the corresponding stochastic differential equation (which can then be used to study the Markov chain). In several applications, the bounds improve upon previous results or are completely new.", "questions": "It would be nice if the author(s) could comment on whether Assumption 1 in Section 2 is typically satisfied/easy to verify in applications.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results in this paper provide novel and general bounds on the approximation error for Ito chains using the corresponding stochastic differential equation. The results cover a broad range of applications in sampling, optimization, and boosting (for example, SGLD, SGD, and Stochastic Gradient Boosting) and are novel in several such applications (for example, the results cover almost arbitrary isotropic and state-dependent noise). The proof involves several new ideas and the presentation is quite clear.", "weaknesses": "It would be nice if the author(s) could comment on whether Assumption 1 in Section 2 is typically satisfied/easy to verify in applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "U71fEFMw6l", "reviewer": "Reviewer_RRnG", "summary": "This paper studies a broad class of Markov chains called Ito chains, which allows for almost arbitrary isotropic and state-dependent noise instead of normal and state-independent one. The paper analyzes the coupling between Ito chains and its anagolous SDEs, and provides an upper bound for $\\mathcal{W}_2$ distance between laws of the two. Their results cover many of the known estimates. In particular, some techniques such as Window Coupling and an augmented version of Girsanov's Theorem are of independent interest.", "questions": "The window coupling seems to be among the crucial parts in this paper. Could authors explain if this is first proposed by this paper, or already appears in literature? It is best to provide some references.\n\nThe paper gives better bounds for SGD with Gaussian/non-Gaussian cases [1]. Could authors compare the theoretical techniques used in two papers and explain where do such improvements probably come from?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The originality is high. The authors study a quite general class of Markov chains and analyze the upper bound between SDE, which is also a popular research area.\nClarity: the clarity is good. The paper sequentially introduces several auxiliary SDEs/Markov chains to eventually bridge the gap between the processes of interest: $X_k$ and $Z_t$. The motivation of each proposed auxiliary processes are clearly stated and is easy to follow for readers.\nSignificance: The theoretical contribution is quite good for this area. The authors consider non-Gaussian and state-dependent chains which is not so deeply investigated in literature. The window coupling and \"modified\" Girsanov theorem may be of independent interest.", "weaknesses": "There are some mistakes and typos in proofs:\n - In Appendix, the equations in the middle of page.18 (the one after (10)), a noise matrix $\\sigma(Y_{\\bar{\\eta}k}^S)$ before $\\zeta_k^S(X_{Sk})$ is missing. The same issue appears in most of the later equations in this proof.\n - In the same equation, the last two terms have a wrong scaling w.r.t. $S$. Specifically, they should be $4\\mathbb{E}\\left[\\left\\|\\frac{1}{\\sqrt{S}}\\sum_{i=1}^{S-1} \\sigma(X_{Sk}) (\\epsilon_{Sk+i} - \\frac{1}{\\sqrt{S}}\\zeta_k^S(X_{Sk})) \\right\\|^2\\right]$ and $4\\mathbb{E}\\left[\\left\\| \n\\sum_{i=0}^{S-1}(\\sigma(X_{Sk}) - \\sigma(Y_{\\bar{\\eta}k}^X)) \\zeta_k^S(X_{Sk}) \\right\\|^2\\right]$. Consequently, some following terms should be multiplied by $S^2$ or so. (It seems not to affect the final upper bound, though. It is better to still check the whole roadmap of proofs.)\n - I wonder how the last term in the top equation on page.19 is derived ($4M_0\\|X_{Sk}-Y_{\\bar{\\eta}k}^X\\|^2$). It seems merely using Assumption 1 (4) is not enough. Or maybe there should be some additional assumptions?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "T8BuBBZAWM", "reviewer": "Reviewer_4gNA", "summary": "This work considers a rather general and broad class of Markov chains,\nIto chains that look like Euler-Maryama discretization of some Stochastic\nDifferential Equation. However, I am not fully convinced of the importance of this work.", "questions": "None", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "This paper studies a rather general and broad class of Markov chains and studies the convergence rates.", "weaknesses": "1. The theoretical results do not provide any new insight to the community.\n2. The analysis is based on standard techniques.\n3. The paper lacks a empirical study to verify the theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (poster)