Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation
Authors: Marina Sheshukova
Denis Belomestny
Alain Oliviero Durmus
Eric Moulines
Alexey Naumov
Sergey Samsonov
Venue: ICLR 2025 Poster (2025)
Keywords: Stochastic first-order optimization
Richardson-Romberg extrapolation
Polyak-Ruppert averaging
Primary area: optimization

Abstract: We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works  suggested to combine the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation to reduce the asymptotic bias of SGD at the expense of a mild increase of the variance. We significantly extend previous results by providing an  expansion of the mean-squared error of the resulting estimator with respect to the number of iterations $n$. We show that the root mean-squared error can be decomposed into the sum of two terms: a leading one of order $\mathcal{O}(n^{-1/2})$ with  explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order $\mathcal{O}(n^{-3/4})$, where the power $3/4$ is best known. We also extend this result to the higher-order moment bounds. Our analysis relies on the properties of the SGD iterates viewed as a time-homogeneous Markov chain. In particular, we establish that this chain is geometrically ergodic with respect to a suitably defined weighted Wasserstein semimetric.

Published as a conference paper at ICLR 2025
NONASYMPTOTIC ANALYSIS OF STOCHASTIC GRA- DIENT DESCENT WITH THE RICHARDSON-ROMBENT EXTRAPOLATION
Marina Sheshukova Denis Belomestny221
Alain Durmus
Eric Moulines
Alexey Naumov1.6 Sergey Samsonov!
HSE University DDissuurg-Essen University CMAP, UMR 7641, Ecole Polytechnique MMohamed Bin Zayed University of AI
Skolkovo Institute of Science and Technology
Steklov Mathematical Institute Russian Academy of Sciences
fmsheshukova, anaumov, svs www.smmssooo)onoo.oo.oo.oo (asoov))hherru ru durmus, eric moulinesssssee...... /epolytechnique...... edu denis menis.belomee wyw.omeetteeuuiiiieeee......
ABSTRACT
We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with constant step size. Previous works suggested to combine the dure with the Richardson-Romberg extrapolation to reduce the asymptotic bias of SGD at the expense of mild increase of the variance. We significantly extend pre- vious results by providing expansion of the mean-squared error of the resulting estimator with respect to the number of iterations n. We show that the root mean- squared error can be decomposed into the sum of two terms: a leading one of order Onn with explicit dependence on minimax-optimal asymptotic covariance matrix, and second-order term of order On -/1),, where the power 3/4 is best known. We also extend this result to the higher-order moment bounds. Our anal- ysis relies on the properties of the SGD iterates viewed as time-homogeneous Markov chain. particular, we establish that this chain geometrically ergodic with respect to suitably defined weighted Wasserstein semimetric.
averaging proce-
INTRODUCTION
Stochastic gradient methods are a fundamental approach for solving wide range of optimization problems, with broad range of applications including generative modeling (Goodfellow et al., 2014; 2016), empirical risk minimization (Van der Vaart, 2000), and reinforcement learning (Sutton & Barto, 2018; Schulman al., 2015; Mnih et al., 2015). These methods solve the stochastic minimization problem
min f()), DE
(s(0) = Eçar, (F)(EE)))
where & is a random variable with distribution IPg, and the gradient V of the function f can be accessed only through (unbiased) noisy estimates F.. Throughout this paper, we consider strongly convex minimization problems admitting unique solution 6* Arguably the simplest and one of the most widely used approaches to solve (1) is the stochastic gradient descent (SGD). This algorithm constructs the sequence of updates
0 = 7 (( &o Rd
where (TR are step sizes, either diminishing or constant, and {ER]KEN is an i.i.d. sequence with distribution IPg. The algorithm (2) can be viewed as special instance of the Robbins-Monro procedure (Robbins & Monro, 1951). While the SGD algorithm remains one the core algorithms in statistical inference, its performance e.g., momentum (Qian, 1999), averaging (Ruppert, 1988; Polyak & Juditsky, 1992), or variance reduction (Defazio et al., 2014; Nguyen al., 2017). In particular, the celebrated
be enhanced by means of additional techniques that use

---

Published as a conference paper at ICLR 2025
algorithm proceeds with trajectory- averaging of the estimates
1 n
0 Ono.n
OR
k=ng +1
for some 7gg > O. is known (Polyak & Juditsky, 1992; Fort, 2015), that under appropriate assump- tions on and Ykk the sequence of estimates (fng. hnE
hnEN is asymptotically normal, that is,
Vn(Bno.n 8*) - N(0, -0000
(4)
where 3 denotes the convergence in distribution and N(0, Ex) denotes the zero-mean Gaussian distribution with covariance matrix Ex.. which is asymptotically optimal, see Fort (2015) for discussion. On the other hand, quantitative counterparts of (4) rely on the root mean squared error (root-MSE) bounds of the form
E! 11/21100m.n 0013 VTTE C(S + n²/2+6 + R( - 0" 1l.
(5)
1/2
Here R( -0 l* n) is remainder term which reflects the dependence upon initial condition, C(f. d) some eestanceddepenent constant and O. There are many studies establishing (5) for Polyak-Ruppert averaged SGD under various model assumptions, including Moulines & Bach (2011); Gadat & Panloup (2023). particular, Li et al. (2022) derived the bound (5) with the rate 6 = 1/4, which is the best known among first-order methods, but their results apply to modified two-timescale algorithm with multiple restarts (Root-SGD). In our work, we show that the same upper bound is achieved by simple modification of the estimate Ong.n based on Richardson- Romberg extrapolation. The main contributions of the current paper are as follows:
We show that version of SGD algorithm with constant step size, Sopypattpppertttt averag- ing, and Richardson Romberg extrapolation lead to the root-MSE bound (5) with 1/4 when applied strongly convex minimization problems. We obtain this result by leverag- ing the analysis of iterates of the constant step-size SGD as a Markov chain. is important note that this result is obtained for fixed step size 7 of order 1/ /nn with n being a total number of iterations. This result requires that the number of samples n is known priori to optimize the step size 7.
We generalize the above result and obtain high-order moment bounds on the error. Select- ing the constant step size 7 = 1/,n, we obtain for 2 bounds the form
E E/([100 0-11²) Cop 1/2 TT C(f.d,p) + R(110, 0 n,,,,
(6)
1/2
3//4
where Co is a universal constant, and 0 is a counterpart of Ono.n when using Bichardson-Romblee extrapolation, see related definitions in Section 4. Our proof is based on a novel version of the Rosenthal inequality, which might be of independent interest.
The rest of the paper is organized as follows. We provide a literature review on the non con-asymptotic analysis of the SGD algorithm and its modifications, with an emphasis on constant step-size SGD procedure in Section 2. Next, we analyze constant step-size SGD by
and the Richardson-Rombee treating it as a Markov chain and study the properties of the in Section 3. In Section 4, we analyze the properties of Richardson-Romiee averaged estimator (3) to Dolyak-Ruppert averaged SGD and derive bounds for the second-order and higher-order moments of the error.
extrapolation applied
Notations and definitions. For 0,, 01..... .,0g being the iterates stochastic first-order method, we denote Fxx = (b,, fI....,0g. Let (Z, dz) be complete separable metric space equipped with its Borel o-algebra Z. We call a function c Z x Z + R. a distance-like function, it is symmetric, lower semi-continuous and c(r,y) y) 0 if and only if x y. and there exists q N such that (z v) < c(x, y). We denote by (E the set of couplings of probability measures & and g', that is, a set of probability measures on (Z² 2 such that for any II E 8 (C. {') and any A E holds [T x A) (A( and IT(A Z) {(A). We define the Wasserstein semimetric associated to the distance-like function ),,
(E Izzz e(2,2')iL c(z,z/)I((d2,d) de)) Wc(E.5') inf [-
2

---

Published as a conference paper at ICLR 2025
Note that 5 is not necessarily distance, as it may fail to satisfy the triangle inequal- ity. In the particular case of Z = R2, and cp(2, y) = I| yll'. I.y E R", p 2 1. we use a short notation for Wp(5,5') defined by pp(. = (E,E.. For 2, E IR de- note by 2 @ the tensor product of z and y and by 299k the k-th tensor power of x. In ad- dition, for a function f : Rdd + IR we denote by 5²0( the k-th differential of ʃ. that is 8²1 I1 80,, For any tensor M E (R4))((-11, we define {² E R by the relation (())() = Eipmnnan M S V ((0),, 1.6 where / E (1,
v [(0)
d.. Also
for any tensor M E (R2))((-1)) we define ||M]| = sup x' ='
E Mr
For
two sequences fan and fonN we write On X b,, if there an absolute constant e > O, such that an S cb, for any E N. Throughout this paper we use en for an absolute constant, which values may vary from line to line.
2 LITERATURE REVIEW
Constant step-size SGD has been widely studied the literature. Its bias and MSE were studied for strongly convex problems in (Dieuleveut al., 2020), for both the last iterate and the Polyak- Ruppert averaging. Yu et al. (2021) studied the bias and the asymptotic normality of the last iterate of SGD for non-convex problems under the Lojaaak-ooasiwiizzzz condition and its generalizations. Vlatakis-Gkaragkonn et al. (2024) considered constant step-size methods for solving variational inequalities, focusing on characterizing the bias and establishing asymptotic normality. Merad & Gaïffas (2023) studied the convergence of constant step-size SGD iterates in W, distance, 2 1, and provided concentration bounds for both On and 6ng.-- Moulines & Bach (201 1) derived the of strongly convex functions f. Gadat & Panloup
root-MSE bound (5) with 5 1/6 for the (2023) derived an MSE counterpart to (5) of the form
Elli@ng. 0* [13] TrE
C(I.d) n--a
with 3 1/4, translating to the root-MSE bound (5) with 8 = 1/8. Li et al. (2022) suggested the Root-SGD algorithm combining the ideas of the two-timescale stochastic approximation and multi- ple restarts, establishing a counterpart of (5) with 8 = 1/4. The recent series of papers (Huo al., 2023; Zhang & Xie, 2024; Zhang et al., 2024) investigated stochastic approximation algorithms with both i.i.d. and Markovian data and constant step sizes. The authors proposed precise characteriza- tion of the bias together with an MSE bounds after applying the Richardson- Rombbrrg correction. At the same time, these works only considered the 2-nd moment of the error and did not aim identify the leading term of the MSE bound, which aligns with the CLT covariance matrix Exe.
Richardson-Rombeerg (RR) extrapolation a technique used to improve the accuracy of numerical approximations (Hildebrand, 1987), such as those from numerical differentiation or integration. It involves using approximations with different step sizes and then extrapolating to reduce the error, typically by removing the leading term in the error expansion. The one-step RR extrapolation was introduced to reduce the discretization error induced by an Euler scheme to simulate stochastic differential equation in Talay & Tubaro (1990), and later generalized for non-smooth functions in Bally& & Talay (1996). This technique was extended using multistep discretizations in Pagès (2007). RR extrapolation have been applied to Stochastic Gradient Descent (SGD) methods in Durmus al. (2016), Merad & Gaiffas (2023) and Huo et al. (2024a), to improve convergence and reduce error in optimization problems, particularly when dealing with noisy or high-variance gradient estimates. Recent papers (Allmeier & Gast, 2024: Zhang & Xie, 2024; Huo et al., 2024a; Kwon et al., 2024) consider applications of RR to different stochastic approximation problems with constant step-size, including Q-learning, and single- and two-timescale stochastic approximation.
3. FINITE-TIME ANALYSIS OF THE SGD DYNAMICS FOR STRONGLY CONVEX MINIMIZATION PROBLEMS
3.1 GEOMETRIC ERGODICITY OF SGD ITERATES
We consider the following assumption on the function f in the minimization problem (1).
3

---

Published as a conference paper at ICLR 2025
A1. The function f is continuously differentiable and p-sttrongyy convex on R., that is, there exists a constant μ > 0, such that for any 8, H' E IR", holds that
(V 2 1 01 S f(0) ( -
(8)
A2. The function f is 4 times continuously differentiable and Lm-stooth on R that is, there is constant L2 2 O, such that for any 0, 6' E R
I f(6')l S L2 110 - 11
(9)
Moreover, f has bounded 3-rd and 4-th derivatives, that is, there exist L3, L4 2 0 such that
V f()1l - L, for E {3,4].
(10)
We aim to solve the problem (1) using SGD with constant step size, starting from initial distribution v. That is, for & 2 0 and a step size y 2 0, we consider the following recurrent scheme
< FF Ek++1,, 06² = 0o ~ ~
(11)
k+I
where {Ex JENN is a sequence satisfying the following condition.
A3 (p). {ErTkEn is sequence of independent and identically distributed (i.i.d.) random variables with distribution Pe,, such that & and Og are independent and for any Rd it holds that E [V
f
Moreover, there exists Tp. such that [l/" [(IP]] - Tp. and for any q .,...,P' holds with some I, O that for any 01, 02 TR.
10: -
- (f2))), 01 02) Eq (F()..)) - VF (12)
Assumption Ap) generalizes the well-knowd L--co-coercivity assumption, see Dieuleveut et al. (2020). A sufficient condition which allows for A3(p) is to assume that F(O,E) is Pç-a.s. convex with respect to 0 E udd For ease of notation, set
L max(L1, L,, Lg,L4))
(13)
and trace only dependence upon L in our subsequent bounds. In this paper focus the conver- gence to 8 of the Polyak-Ruppert averaging estimator defined for any n 2 0,
2n
g(7)
0(7)
(14)
n2
k=n+1
Many previous studies instead consider J(,)) иーno Ek=mo+1 907) rather than 0,?)) where 2 no + and no denotes burn-in period. However, when the sample size n is sufficiently large, the choice of the optimal burn-in size affects the leading terms in the MSE bound of 0 -6" only by a constant factor. Therefore, we focus on (14), or equivalently, use 2n observations and set no n.
Properties of (o()) TREN viewed as a Markov chain. Under assumptions A1, A2 and A A3(2), the sequence {0()) JAEN defined by the relation (11) is time-homogeneous Markov chain with the
Markov kernel
/ 1A - -VF(
(0,
0 E Rd, A E B(R"),
(15)
where B(Rd) is a Borel o-field of Rdd In Dieuleveut et al. (2020) it has been established that, under the stated assumptions, Q₂ admits unique invariant distribution Ty, if y is small enough. Previous studies, such as Diculeveut et al. (2020) or Merad & Gaïffas (2023). studied the convergence of the distributions of {e{7) TENN nT in the p- p-Wasserstein distance Wp. p. p 1, associated with the Fuclidean distance in Rdd Our main results require switch to the non-standard distance-like function, which defined under A1 and A3(2) as follows:
c(0,0') = 110 0'll (10- 1100-011
2 2//22222
0*11 + +10' 0-1
0,0º ERd
(16)
Vp
Here the constants 72 and are given in A3(2) and A1, respectively. This distance-like function is designed to analyze (o("))eet under Al and A3(2). In particular, it depends on the step size y and 8*. Our first main result establishes geometric ergodicity of the Markov kernel Q2 with respect to the distance-like function from (16).
4

---

YT2 Published as a conference paper at ICLR 2025
Proposition 1. Assume AI, A2, and A3()). Then for any 7 (0: (2L)),, the Markov kernll Q defined in (15) admits a unique invariant distribution n... Moreover, Q2 is geometrically ergodic with respect to the cost function e, that is, for any initial distribution v on R and l E N,
We(v mT) S 4(1/2))/mli)) W Woly, kn),
(17)
where m(7) = [2 log 4/(1)))
Discussion. The proof of Proposition 1 is provided in Appendix A. Properties of the invariant distribution T.y were previously studied in literature, see e.g. Dieuleveut et al. (2020). It particular, it is known (Dieuleveut al., 2020, Lemma 13), that the 2-nd moment of Tyy scales linearly with y
J| 110
(d0) x 2
(18)
This bound yields, using Lyapunov's 's inequality, that
x 10 - 00=, (d0)) -
At the same time, expectation of the cost function c(0, 0*) scales linearly with the step size y:
[ 6'
YT2
S
(19)
The property (19) is crucial to obtain tighter (with respect to the step size 7) error bounds for the Richargson-Romberg estimator, as well as in the Rosenthal inequality for additive functional of (of") Jeen derived in Proposition 8. Precisely, the additional /7 factor obtained in (19) would allow us to obtain sharper bounds on the remainder terms in Theorem 6. Next, we analyze the error 052) l where 052) is distributed according the stationary distribution Ty. To this end, consider the following condition.
C1 (p). There exist constants Diast.p: Estep.p 2 2 depending only on p, such that for any step size E (0, (I) and any initial distribution it holds that
E2/ k - 1-1] s - (1-7p)**E3) = [110- - 0" [P'] + Dlast 7Tp/
(20)
Moreover, for the stationary distribution Ty holds that
E2/P [110(]] - 0 [P]] < Diast TTpp
TTp p.
(21)
important to note that C1 is not independent from the preceding assumptions A1 A3(p). In particular, Dieuleveut et al. (2020, Lemma 13) establishes that, under A1,A2, and A3(p), the bound (21) holds for y E (0, LL(L Cstep.p)] with some constants Diest.p and Cstep.p depending only upon p. Unfortunately, it is difficult to obtain precise dependence of Catep.p and D Dt p. and to obtain (21) with precise numerical constants. Existing studies (Gadat & Panloup, 2023; Merad & Gaiffas, 2023) either use different set of assumptions or do not explicitly characterize their dependence on That is why we prefer to state (p) as a separate assumption. In the subsequent bounds we use CI(p) together with A 1, and A 3p), tracking the dependence of our bounds upon Cstep.p and Diast.p- We leave the derivation of C1(p) with precise constants Diast.p: Cstep.p as an interesting direction for future research.
Under assumption CI, we control the fluctuations of & around 0-, However, unless f is quadratic, is known that fg. OT,, (d0) + 0*. In the next proposition, we quantify this bias under under weaker assumptions than those in Dieuleveut al. (2020, Theorem 4).
Proposition 2. Assume AI, A2, A3(6), and CI(6). Then there exist such A E Rd. A2 E Rdxd not depending upon 7,, that for any 7 E (0, 1/(I. Cstep.a)], it holds
0
0 (d0) 8* + +7 + B/73/22
(22)
3d
/ (0 100-))00 82)82m, n. (d0) = 7 ~2 + B/2
Σ =
(23)
_ad
5

---

Published as a conference paper at ICLR 2025
LDD 2pr12
Here B1 Ed and B3 IRdxdd satisfy ||:||| S +, +
|| S C2 where C defined in (52) is constant independent of Moreover, for any initial distribution Rd, it holds that
E = 8* + y + 8/2 + R2 -8", ,),,)
(24)
where
(2o 8r, 7. n
1777(++1//2
(E 1- v/
(25)
The proof is provided in Appendix A. Results of this type are known in the literature for stochastic approximation algorithms, see e.g. Huo et al. (2024b) and Allmeier & Gast (2024). The additive term A₁ vanishes when the function f is quadratic, see (Moulines & Bach, 2011).
3.2 ANALYSIS OF THE POLYAK-RUPPERT AVERAGED ESTIMATOR 0670
In this section, we analyze the finite-sample properties of the estimator 0%²h) from (14). The analysis based on techniques previously used in Moulines & Bach (2011), as well as in the analysis of the Polyak-Ruppert averaged LSA (Linear Stochastic Approximation) algorithms, see Mou et al.
(2020); Durmus et al. (2024). Below we derive the key representation for the error a( 8", following Moulines & Bach (2011). Define the k-th step noise level at the point 0 E R by:
Ex (0) = (F Ex) - Vf(0),
(26)
and form
( is martingalc- sequence w.r.t. (Fi)Ren. Then the recurrence (11) takes
((7) 1+1 8"
= =
~V[((()) =+++1((
(27)
We set
(0) V (0)) (0 - -0),, where H = 42 E Raad
(28)
We obtain from (27) with simple algebra that
( # 0*) = - 0522 k+1
- Ex+1 ( 77 (0()))
(29)
Taking average of (29) for k n + 1 2n, we arrive at the final representation:
H' (0 - 0*)
8
(7) A"
2n 0"
Σ
2n
Ex+
(0 (3))
1
Σ
2n
(30)
7n
nn n
n k=n+1
k=n+1
We further introduce the covariance matrix of (0*) measured at the optimal point 0*, that is. (31)
Σ Eq +)))
Note that ΣS does not depend on the step size y and is related to the asymptotically optimal co- variance matrix of the
averaged iterates Ø(7), see Fort (2015). Precisely, under assumptions A1-A3, the asymptotic covariance matrix Exc from (4) is given by
Ex (H* - (H")-
(32)
We state our subsequent results in terms of H (0 0*) and its Richardson- Romberg adjusted counterpart. One can switch to the corresponding results for d!?) f at the price of the factor [|[H') I|, which affects the non-leading terms. In our first result below, we establish the root MSE bound on the error of the -uppert averaged estimator (14).
Theorem 3. Assume AI, A2, A3(6), and C1(6). Then for any E (0, 1/ Cstep. n E N, and estimates (14) satisfies
initial distribution 1 on Rd, the sequence of
VI
C2 + +C
1/2 ni/2 + R2(nn y, 1100 - - (33)
E/ H' +
Vn
71/2n
where the constants C2 C. are defined in Appendix B (see equation (66)), and
R2(n, 7, 1100 - 0011) co(1 (n
1)/2
E/2 [110 - 11
7u
Co L(1 - 7p)=+1
2 001]
2n7y4
where Co is an absolute (numerical) constant.

---

Published as a conference paper at ICLR 2025
The version of Theorem 3 with explicit constants together with the proof is provided in Appendix B, see Theorem 15. Note that the result of Theorem 3 is valid for arbitrary E (0, 1/(L Cstep.6)]. At the same time, this bound can be optimized over step size of the form = n - -, 3 E (0, 1).
3/2 it holds setting Corollary 4. Under the assumptions of Theorem 3, provided that n 2 (L Cseep,)) Y 2/3 that
VT C(T,, 1/2
E 0')13
+
n2/3 + +R2(n, 1/n2/3, 2/3 -100 - 1),
(34)
where the expression for C(L, pu) can be traced from Appendix B, eq. (66).
Corollary 4 implies that, if is known in advance and ? = n 2/3 then 0%77) satisfies (5) with 5 1/6. A closer inspection of the sum (30) reveals that Ex,, [n(( is of order and we can not expect to provide a better bound for the term E22n -k=n+1 n((%) compared to the one coming from Minkowski's inequality. Thus, this is the bias of the stationary distribution, which does not allows us to improve scaling of the second-order term w.r.t. the sample size nt
In case of deterministic problems ex (0) 0 for any l: and 0, and C1(p) is satisfied for any p 2 2 with Dasst.p O. such setting. x O, and the remainder terms are proportional Diast.p with p 2, 4. or 6, and also vanishes. Therefore, Theorem 3 provides exponential convergence bounds, which are embedded the remainder term. Previous studies in (Moulines & Bach, 2011) provides the bound of the same order (2/3) for the second-order term of the root-MSE bound of SGD algorithm with methods. The recent work by Li al. (2022) shows that the best known second-order error term in the bound (34) is of order (n/44/ and can be achieved by the Root-SGD algorithm. In the next section we mirror this bound using the constant step-size SGD algorithm combined with the CathardsonRRobbere extrapolation technique.
averaging. This rate is known to be suboptimal for first-order
RICHARDSON SHARDDSON-ROMBEGG ROMBERG EXTRAPOLATION
Our analysis presented in Theorem 3 was based on the summation by parts formula (30) and Taylor expansion of the gradient V f() in the neighborhood of 6", yielding the remainder quantity 17(0). It
important to notice that
J (10) (d0) + 0, Rd
(35)
which prevents us from using larger step size in the optimized bound (34). In this section we show that Richardson Romberr extrapolation technique is sufficient to significantly reduce the bias asso- ciated with v))) and improve the second-order term in the MSE bound (34). Instead of considering
single SGD trajectory {0(-)) keN, and then relying on the tail auil-averaged estimator ((?7) we construct two parallel chains based on the same sequence (5x)ENN
2n
0/2 = =0(² - -VF(( .E4t1),
g(7)
n
k=n+1
(36)
2n
0 ( = 0(22)) 27 2( ,6+1), ((2^)
(7)
k=n+1
Based on d(?) and (* defined above, we construct the Richardson estimator:
((RR) == 20( - 0(2-)
(37)
Note that it is possible to use different sources of randomness (Ev JAEn and (&L JAEN when construct-
ing the sequences (e(*)) JAN and )0(2))) |KEN respectively. At the same time, it is possible show the benefits of using the same sequence of random variables (Ex heN in (36). Indeed, consider the
decomposition (30) and further expand the term 10) defined in (28) as
n(0) (0)) + G(B),
where we have defined the following vector- vector-valued functions:
1 (
(0) = vd (0 02
a(0)
eV 1(10 +(1 -1)0)dt) (0-00) (38)
2
7

---

Published as a conference paper at ICLR 2025
We further rewrite the decomposition (30) as
H HO
8*)
0l7)
n+1
0
0
2n+11
(1)
0
1
Σ
2n
Ek41 (8*)
yn
7
n
k=n+1
2n
2n
1
(0 -Ex+1(0))
((((T)
G(
(39)
k=
k=n+1
k=n+1
In the decomposition (39), the linear term W n =n Lk=++1 Ek+1 (0r) does not depend upon y. Moreover, when setting the step size y = cyn - with an appropriate 3 E (0, 1), we can show that the moments of all other terms except for W in the r.h.s. of (39) are small (see Theorem for more details). Hence, using the same sequence {E*]keN of noise variables (36) yields an estimator @R such that its leading component of the variance still equals W. Hence, using the Richardson- Romberg procedure increases only the second-order (w.r.t n) components of the variance. At the same time, using different random sequences {Ex JKEN and keN for 0(7) and 0(2") increases the leading component of the MSE by a constant factor. Hence, is preferable to use synchronous noise construction in (36). Proposition 2 implies the following improved bound on the bias of RR
Proposition 5. Assume AI, A2, A3(6), and CI(6). Then, for any Y (0, 1/(L. Cs), and any initial distribution on Rd, it holds that
E, 0 RR) 0r
1- + R3(00 0* ,,,,
(40)
where B3 E Rdd is vector such that B3ll p
c +
and
2/²/2 [2(60 8* 7.7)) S 7p(1 1)/2
(E2/2
0+|1]]
+
viTz /p
The proof of Proposition is provided in Appendix A. This result is simple consequence of Propo- sition 5, since the linear in y component of the bias 7A, from (24) cancels out when computing estimate 0%
@(RR) We are now ready formulate the main result for the Richardson-Rominee
Theorem 6. Assume AI, A2, A3 and C1 Then for any 7 10, Catep.6) A 2/(11 L)), initial distribution and n E N, the Richardson-Romberg Romberg estimator (( defined in (37) satisfies
TT
CRR,I7 1/2
CRR.2
CRR,AY n/2
E/2 H (8((R))) 0'
1/2 +
+ //R 3/2 +
1/2
71/2n
Ra Rn 7, 110 - 0 ()))),
where the constants CRR,1 to CRR,4 4 are defined in Appendix C (equation (74)), and
R1 7, 1,,100 1*1 L(1 (1)(2+
npp
D Diast,
E2/211100 + 0-11-- + +E/2 0-++++
with co being an absolute constant.
Proof of Theorem 6 is provided in Appendix C. Similarly to Theorem 3, we can optimize the above bound setting 7 depending upon n.
Corollary 7. Under the assumptions of Theorem 6, provided that n 2 (C V 111/2)2, it holds
setting = n. -1/ that
VT 1/2
C(L,H) n3/1
E//2 H ( - 0+)1
+
+ Ra(nn 1/vn, 1100 1),,,
(41)
where the expression for C(T., 11) can be traced from Appendix C, eq. (74).
8

---

Published as a conference paper at ICLR 2025
Discussion. Note that the result of Corollary 7 is counterpart of (5) with 8 1/4. This decay rate of the second order term is the same as for the Root-SGD algorithm of Li et al. (2022). At the same time, we highlight that the assumptions of Theorem 6 are stronger compared to the ones imposed by Li et al. (2022). In particular, in A2 we require that f is times continuously differentiable and uniformly bounded. At the same time, Li et al. (2022) impose Lipschitz continuity of the Hessian of f. Our proof of Theorem 6 essentially relies on the 4-th order Taylor expansion, and it is not clear, if this assumption can be relaxed. We leave further investigations of this question for future research.
Now we generalize the previous result for the p-th moment bounds with p 2 2. The key technical element of our proof for the p-th moment bound is the following statement, which can be viewed as a version of Rosenthal's 's inequality (Rosenthal, 1970; Pinelis, 1994).
Proposition 8. Let p 2 2 and assume AI, A2, A3(2p). and C((2p). Then ub defined in (38) and any 7 E (0, 1/(L 2p)p, it holds that
L D 2p / nY
E
Σ (v(0 - ( S A==
(42)
13/2
Discussion. Proof of Proposition 8 is provided in Appendix D.I. It is important to acknowl- edge that there are numerous Rosenthal-type inequalities for dependent sequences in the literature. Proposition 8 can be viewed an analogue to the classical Rosenthal inequality for strongly mixing sequences, see (Rio, 2017, Theorem 6.3). However, it should be emphasized that the Markov chain (of") JEEN is geometrically ergodic under the assumptions A A1-A3(p) only in sense of the weighted Wasserstein semi-metric W C"( with cost function defined in (16). As a result, the sequence (o(²)
Jeen JEEN does not necessarily satisfy strong mixing conditions. Bounds similar to (42) have been explored in (Durmus et al., 2023), but in Proposition we obtain the bound with tighter dependence of the right-hand side upon 7. Below provide the p-th moment bound together with corollary for the step size 7 optimized w.r.t. n.
Theorem 9. Let p 2 2 and assume A A2, A3(3p), and C((3)). Then for any step size Y (0, 1L 3p) A p/(44 32 L)}, initial distribution v, and n E N, the estimator ( defined in (37) satisfies
CIV Tr 1/12 1/2 n/2
CnR,5 CRR,6T1/2 1/1/2
E//111 H' H' (BLRR) - -0) S
+
+ CRR,
n1/2
(43)
CRR,S n where C1 = 60c and C2 60 are absolute constants from the Pinelis version of Rosenthal in- equality (Pinelis, 1994, Theorem 4. I), and pprooll-sspecteeeee constants CRR.5 to CRR,S are defined in Appendix D (equation (100)), and
c2PTр n
+ Rs(n, 7, -010)
Rn, 1100 (1000-00)) (I) = (1 (1)))++1//22CC///0 (E//p(1100 (1:00-00117) (E/0-[10000011] -11++//////111 [116 0" 11]0 1.L/ -0" (1(]))])
Here constant Cj.p can be traced from Appendix D, eq. (101).
Corollary 10. Under the assumptions of Theorem 9, provided that n 2 L (Cstep.30 34.3% 3//p)²
holds setting = n 1/2 that
8'ISTS CLV TTETp'/
C(L,HL,) + Rs(n, 1/V7, 1|0 (*1),, (44)
EL/P H' (A(RR)-
+
n/222
n3/1
where the expression for C(L, p)P) can be traced from from
Appendix D, eg. (100).
Discussion. Proof of Theorem 9 is provided in Appendix D. Note that the result above is direct generalization of Theorem 6, which reveals the same scaling of the step size 7 with respect to n. To the best of our knowledge, this is the first analysis of a first-order method, which provides a p-th moment bound with p > and the second-order term of order O(n -3/4) while keeping the precise leading term related to the asymptotically optimal covariance matrix Σz Such results were previously obtained for the setting of linear stochastic approximation (LSA), see Mou et al. (2020); Durmus et al. (2024). Thus, Richardson- convex minimization problems allows to mimic the p-th moment error bounds that were previously obtained the LSA setting.
extrapolation applied to the strongly

---

Published as a conference paper at ICLR 2025
BichardsonnRRoment error
Richardson- error, rescaled
10a3
10
6x100
Rescaled MSE
10"4
MSE
4x100-
RR error, rescaled
30
RR error without leading term rescaled n
3x
RR error
2x10P
RR error without leading term in
10.9
10a
10a
10
10a
102
20
10f
10f
Number of iterations
Number iterations
Figure 1: Left picture:
Richardson-Romber experimental error with and without the leading term k=n+1 (0*)( Right picture: same errors after rescaling by n and n respectively.
NUMERICAL RESULTS
In this section we illustrate numerically the scale of the second-order terms in equation (41) in Corollary 7. We show that, for particular minimization problem, setting n -1/2, we achieve the scaling of the second-ordes terms in root-MSE bounds of order O(n Onn44/4) We consider the problem
min ʃ(0), S(0) = 8 + cos cos AER
with the stochastic gradient oracles (F, <) given by VF(O.E) sin + and ~ (0, 1). This example satisfies the assumptions AI, A2, (3)) with any 2 2. We select different sam-
ple sizes n, choose 7 1/vn, and construct the associated estimates 0% and 0(2²), Detailed description of the experimental setting is provided in Appendix E. Then for each n we compute the Bechardson-Rombeng estimates (RR) from (36) alongside with its versions without the leading term in n, i.c. @!RR) + n
2 - 1k+1(0"). We provide first the plot for ||@(RR) 1²1 and [ + -1 2n I Ek+1 ( - 112 averaged over M = 320 parallel runs, in Figure On the
same figure we also provide the plots for rescaled enrors
[ 0" 112 and n 3/22 (0 0" + +n Σ Ein
2n
k=m+1 Sk+ (0*))1
also averaged over M parallel runs. The corresponding plot indicates that the proper scaling of the squared norm of the remainder part is 3/2 that is, the corresponding term in root-MSE bound for E// (1 0" [[²] scales as O(n -3/4), as predicted by Corollary
6 CONCLUSION
In this paper, we study the non-asymptotic error bounds for the Richardson-Romberd estimator built upon the Polpak-Ruppert averaged SGD iterates with a constant step size. particular, under an appropriate choice of step size, depending on the total number of iterations root-MSE bound admits both sharp leading term, which aligns with the hinimax-optimal co- variance matrix, and second-order term of order Onn which is the best known rate among first-order methods. Future research directions include, firstly, generalizing the proposed algorithm the setting of dependent noise sequences {Ex ]En]keN in the stochastic gradients (1). Another natural
the corresponding
question is to study the properties of (RR) under relaxed assumptions f. In particular, it would be interesting to remove additional smoothness assumptions on f (bounded 3-rd and 4-th derivatives), and to relax the strong convexity condition AI. One more research direction is to quantify a relation between the parameter 6 in (5) and convergence rates in (4), following the approach suggested in Shao & Zhang (2022).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
The work of M. Sheshukova, D. Belomestny, A. Naumov, and S. Samsonov was prepared within the framework of the HSE University Basic Research Program. The work of E. Moulines has been 10107)006)))), Views and opinions
partly funded by the European Union expressed are however those of the author(s) only and do not necessarily reflect those of the Euro- pean Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Sebastian Allmeier and Nicolas Gast. Computing the Bias of Constant-step Stochas- tic Approximation with Markovian Noise. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural In- formation Processing Systems, volume 37, pp- 137873-137902. Curran Associates, Inc., 2024. URL https://proceedii: 6ccd333533
neurips. cc c//ccc/////eeee
file/
6cd353- -Paper Conference. pdf.
V. Bally and D. Talay. The law of the euler scheme for stochastic differential equations. Probability Theory and Related Fields, 104(1):43-60, 1996. doi: 10.1007/BF01333800. URL https: /////i/ooo////////// orw.ii.org/..... / / BF 01 01303802.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural infor- mation processing systems, 27, 2014.
Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3): 1382, 2020. doi: 10. 10.12118 2214/1--AOS A0S1850. URL https: htt./oooooorroo.eo. wwopioorg/1...0 1214 / 9 AOS1 850.
R. Douc, Moulines, P. Priouret, and Soulier. Markov chains. Springer Series in Operations Research and Financial Engineering. Springer, 2018. ISBN 978-3-3 978-3-319-9770344
Alain Durmus, Umut Simsekli, Eric Moulines, Roland Badeau, and Gaël Richard. Stochastic Gradi- ent Richardson Rombbergn Markov Chain Monte Carlo. Advances in neural information processing systems, 29, 2016
Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, and Marina Sheshukova. Rosenthal-type type inequalities for linear statisties of Markov chains. arXiv preprint arXiv:2303.05838, 2023.
Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Finite-time high probabbbbyy bounds for Polyak-Rupper averaged iterates of linear stochastic approximation. Mathematics of Operations Research, 2024.
Gersende Fort. Central limit theorems for stochastic approximation with controlled markov chain dynamics. ESAIM: Probability and Statistics, 19:60-80. 2015.
Sébastien Gadat and Fabien Panloup. Optimal non-asymptotic analysis of the Ruppert-Polyak averaging stochastic algorithm. Stochastic Processes and their Applications, 156:312-348, 2023. ISSN 0304-4149, doi: http://wo..or///0000/////p....p0 1.002. URL https: www. sciencedirect com/ wtt.///w...cce..eeeeee. /ttp///////rrrreaa///////////2//
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems (NIPS), 2014.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cambridge, MA, USA, 2016. http: wtwp:///wwwwtt/t http:://wwwweeeeee www.w/ddeplerrinngooo.o org.
Francis Begnaud Hildebrand. Introduction numerical analysis. Courier Corporation, 1987.

---

Published as a conference paper at ICLR 2025
Dongyan Huo, Yudong Chen, and Qiaomin Xie. Bias and extrapolation in Markovian linear stochas- tic approximation with constant stepsizes. Abstract Proceedings of the 2023 ACM SIGMET. RICS International Conference Measurement and Modeling of Computer Systems, pp. 81-82, 2023.
Dongyan Lucy Huo, Yudong Chen, and Qiaomin Xie. Effectiveness of constant stepsize in marko- vian Isa and statistical inference. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20447-20455, 2024a.
Dongyan Lucy Huo, Yixuan Zhang, Yudong Chen, and Qiaomin Xie. The collusion of memory and nonlinearity in stochastic approximation with constant stepsize. In A. Globerson, L. Mackey, D. Belgrave. A. Fan, U. Paquet, Tomczak, and C. Zhang (eds.). Advances Neural Information Processing Systems, volume 37, pp. 2 21699-21762. Curran Associates, Inc., 2024b.
Jeongyeol Kwon, Luke Dotson, Yudong Chen, and Qiaomin Xie. Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way. arXiv preprint arXiv:2410. 13067, 2024.
Chris Junchi Li, Wenlong Mou, Martin Wainwright, and Michael Jordan. Root-sgd: Sharp nonasymptotics and asymptotic efficiency in single algorithm. Po-Ling Loh Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 909-981. PMLR, 02-05 Jul 2022. URL
httpss//proceedingg.. mlr www....ppes/vve. 78/ 11 www.ia.atttiie
Ibrahim Merad and Stéphane Gaiffas. Convergence and concentration properties of constant step- size sgd through markov chains. arXiv preprint arXiv:2306.. 1497, 2023.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 ((78744))55995533 2015.
Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter Bartlett, and Michael Jordan. On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. In Conference on Learning Theory, pp. 2947-2997. PMLR, 2020.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč, Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning. pp. 2613-26211 PMLR, 2017.
A. Osekowski. Sharp Martingale and Semimartingale Inequalities. Monografie Matematyczne 72. Birkhäuser Basel, edition, 2012. ISBN 30344003699,9783334800030
Gilles Pagès. Multi-step Richardson-Romleee
Extrapolation: Remarks on Variance Control and Complexity. Monte Carlo Methods and Applications, 13(1):37-70, 2007. doi: 1oi:10.1515/
MCMA.2007.005 URL httph:tt//// htt///oooooggg////////o 1tt.0..11111MMMM.
/ttp://.....r/11.01115///c.... 2007. 2007.003.
Iosif Pinelis. Optimum Bounds for the Distributions of Martingales in Banach Spaces. The Annals of Probability, 22( 1706, 1994. doi: (..121//ap/1117688877777 URL httpt:s/://doi
org/
org/10.1 1214 aap//1/69/11777
Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838-855, 1992.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12 (1):145-151, 1999.
Emmanuel Rio. Asymptotic Theory of Weakly Dependent Random Processes, volume 80. 2017. ISBN 12----622-54222-1 doi: 11007/978-3-662-54222
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
12

---

htt.:oooppeeeeeeeeetttttoooooooe Published as a conference paper at ICLR 2025
Haskell P. Rosenthal. On the subspaces of L" (p 2) spanned by sequences of independent random variables. Israel Math., 8:273-303, 303, 1970. ISSN 0021-2172. doi: 10.1007/BF02777156. URL 100700002701/1555555555
/ttp::://do..ooo
David Ruppert. Efficient estimations from slowly convergent Robbins-Monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
Qi-Man Shao and Zhuo-Song Zhang. Berry- bounds for multivariate nonlinear statistics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli, 28(3):
2022.
Richard Sutton and Andrew G. Barto, Reinforcement Leaminng An Introduction. The MIT Press, second edition, 2018. URL
2nd.
html.
Denis Talay and Luciano Tubaro. Expansion of the global error for numerical schemes solving stochastic differential equations. Stochastic Analysis and Applications, 8(4):483- 509, 1990. doi: 10. 11.1800076669999000220000 07362999008809220
URL https://aci. /tt.:////1..or111100000///
Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
Emmanouil Vasileios Vlatakis- Gkaragkounis, Angeliki Giannou, Yudong Chen, and Qiaomin Xie. Stochastic methods in variational inequalities: Ergodicity, bias and refinements. In International Conference on Artificial Intelligence and Stutistics, pp. 4123-4131. PMIR, 2024.
Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat Erdogdu. An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias. Advances in Neural Information Processing Systems, 34:4234 4248, 2021.
Yixuan Zhang and Qiaomin Xie. Constant stepsize q-learning: Distributional convergence, bias and extrapolation. arXiv preprint arXiv:2401.13884, 2024.
Yixuan Zhang, Dongyan Huo, Yudong Chen, and Qiaomin Xie. Prelimit coupling and steady-state convergence of constant-stepsize nonsmooth contractive SA. arXiv preprint 1xXiv:2303.088.3 2024. URL battps://arae wtwpi//.wgggab/////////////
13

---

Published as a conference paper at ICLR 2025
A PROOF OF PROPOSITION 1, PROPOSITION 2, AND PROPOSITION 5
Throughout this appendix we use co for an absolute constant, which values may vary from line to line. In addition, when the upper index of o5²)) 0(2>) is omitted, we assume the result applies to iterations of o(.). The corresponding results for 0(2)) can be obtained by substituting 27 instead of 7. We provide some additional definitions related to the Markov kernels and kernel couplings. particularly useful when considering convergence in Wasserstein semimetric. Detailed exposition can be found in (Douc et al., 2018, Chapter 20).
Let Q(z, A) be a Markov kernel on (Z, 2). A Markov kernel K on (Z², 262 is called kernel coupling of (Q, Q) (that is, of Q with itself), if for all (z,z') z') E Z and A E 2, ((2,, ), A x Z) Qzz and K[(z, z'), Z x A) Q(2', A). If K is a kernel coupling of (Q, Q). then for all n E N, K" is kernel coupling of (Q", Q*)) and for any II (E) IIK" is a coupling of ('Q").
Moreover, it holds that
< / 22"((222)11 (d(dd')))
Wo(EQ",E'Q")
(45)
Jzz
see (Douc et al., 2018, Corollary 20.1.4). For any probability measure II on (Z² 202) we denote by Fk and EX the probability and the expectation on the canonical space ((Z2)M, (z coN) such that
the canonical process { ((Zm; 7%,,,, n E N) is a Markov chain with initial probability and Markov kernel K. We write EK_ instead EK
To prove Proposition we need the following auxiliary lemma about the last iterate of SGD algo- rithm. It can be found in (Dieuleveut et al., 2020, Lemma 10), but we provide its proof here for completeness.
Lemma 11. Assume AI, A2, and A3(2). Then for any E (0: 12TL) and any k, E N it holds that
2//2
E E//21| 8 11 s (1 (1- - 6-l +
(46)
1//2
Proof.
Using the recurrence (11), we get
01+10=111 - 0 [1 = El110 - - (V
= =E|1 1-
O2 0*) + 7² / F(K, 1111))
Applying A3),), we get
E[|10x+1 - 0* [1 S 00 - 11
(v/())) -
- (V/))),))))))))) 0 + 2 VF
Since (0*) 0, using A3(2), we obtain
Ex+11 Il [| = E[IVV 1x+1) VF(0", ,x+1) + E (0*)
< LLL(V - Vf(0"), 0z - -0*) + +2T22
Using A1, A2, and the fact that 7 < 1/(2L), we get
E[ - 0* [[ I (1 (1 - Tl 0- + 27 < - (11-11) 001 + 2y272
Hence, applying tower property for conditional expectations, we obtain
11100++-0110 (+1] < (1- - -1) + Σ (1 11-717 nu)² S (1-714) - -8- 12+ 2
1
1=0
A.1 1 PROOF OF PROPOSITION 1
Consider the synchronous coupling construction defined by the recursions
g{>)) k+1 = e(7) -VF(( EE41), of²² = E Rd g(?)
(47)
1++1 = g()) -7VF(00 ,E41), 067) Ø E Rdd
14

---

Published as a conference paper at ICLR 2025
The pair (0 )EEN defines Markov chain with the Markov kernel (5 which is cou- pling kernel of (Q,, Q2). From now on we omit an upper index (>) and write simply (0k, On Ke)N
Applying now (2),, we get for S 1/ L that
0 k+ 0 11 Fbl El O2 - (VV(O,,
V - = 100 - 12 + - Vl - V. [x+1)11111))
27 V f((x) V ffx)), 0%)
(11774)106 0x
(48)
- L L/2) 111- Similarly, for a cost where in the last inequality we additionally used 2 function e defined in (16), we get using Hölder's and Minkowski's inequalities, that for any E N
(1(00tr,0tt)))) E2/21110++ 1 -
23/2
1| - 0 +
11
Combining the above inequalities and applying Lemma 11, we obtain
25/2 1/2
(/100trr,4++)0000 $ (1 -//))/31100 - 0x ((1 - 71000 - -0-1 + -1:0 01 +
11
$ 2( //1)"//2((( 0%))
for any r I m(7) - and 2(1 (1)1-)))m()/) < 1/2. Hence, applying the result of (Douc et al., 2018, Theorem 20.3.4), obtain that the Markov kernel Q, admits a unique invariant distribution Ty. Applying (45), we get
Note that 2(1 r/2 <
We(vO n,) s 2(1/2) W (M, TT).
(49)
It remains to note that (1/2)1k/m(>1) < 2m122) and the statement follows.
A.2 PROOF OF PROPOSITION 2
We first prove (22) and (23) and introduce some additional notations. Under Al -A3(2, we define matrix-valued function C(0) Rd -> Rdd
c(I) (0)
(50)
The result below is essentially based appropriate modification of the bounds presented in Dieuleveut et al. (2020, Lemma 18). A careful inspection of its proof reveals that we do not need additional assumptions C(O), instead use Lemma 14.
Lemma 12. Assume A1, A2, A3(6), and CI(6). Then, for any 7 E 10, Cstep.. C)t it holds
0, 0- - -1
+ 2/2
(51)
where B, is defined in (22), C(0) is defined in (50), and B E IRd satisfies BBll S 1, + with
L
3/2
lutt
2/5/2
=== VL2
((1
L' Diast.2 Dasst 1r3/2
L / Diast,2
T2 +
3/2
1ast,676
1/2 D2
Last,
(52)
Catep.6l1
Vi
3/13/2
442 step.6
Moreover,
Σ, = TTC(O") + 3/2
(53)
where the operator T R Rdxd defined by the relation
vec (TA) = (H* &I - vec vec (A)
for any matrix A E RRd and Bg Rddxd is matrix, such that BBll
C1-
15

---

Published as a conference paper at ICLR 2025
Proof. Let (0())) JNEN be recurrence defined in (11) with initial distribution On TTy. Recall that Oo is independent from the noise variables (Ex)a211 First, applying a third-order Taylor expansion of f(0) around 8*, we obtain
V (8
+ + +1/2)
G(0).
(54)
where ((0) has form
G(() = 2 (So
AV f(t0) + (1 - t)0) (1-t)) dt (0 - 01)03
Thus, using A2,
L4 10 0010.
|G(()]| - 2
Integrating (54) with respect to Ty. we get
1 (0 (0) (T,)))
/ (d))
H' (0, - --) +) Moreover, using Cl(6), we have
(55)
3/2
3/2
(d0) S 5/0/2 last,5
(56)
Rd
2/13/2
Now we provide an explicit expression for the covariance matrix
E E, [ Ja (0 (00-))227,,(d8))
(57)
Using the recurrence (11), we obtain that
0 - 0" = -I- - 8*) (E1( (m)())
where the function 17(-) defined in (28). Hence, taking second moment w.r.t ny from both sides, get that
E, -1= (I-, + 72 / (()) +22 / (n(8))]32T,
(0-
(0)0(0 0-) H*)] (d0))). (58)
In the above equation C(O) defined (50), and we additionally used that ((c) = 0. Using Taylor's expansion with integral remainder together with A2 and CI
21 / (n(0)) n. (d0)1lF -² I. Dias. 7 Rd
412
L LD2/2
Tll / [[T -0-100000--000000000 + (()) - (T- (d0))] S 5//2
last. TO
3/13/2
Jdd
Moreover, (50) together with C1(6) imply that
S C(0)T, C((') 1/2
where B E idddd satisfies ||]||| solution to the matrix equation
< C2. Using (58) together with C1(6), we obtain that Σ, is a
H +E, H* H E, H* -C(0") B/73/22
(59)
where
LD 3/2
1/2 D2
6
last,
|B p S C2
(60)
2/13/2
4,12 step.6
16

---

Published as a conference paper at ICLR 2025
The matrix equation (59) can be written using vectorization operation
vee (Ix) 7(H SI+ H' -y H" & H H vec (C((*))
+ 7 3/2 (I - @ vee
vec (B')
Applying Lemma 13(c), obtain that
(H* @l 11r (1" DD
where E & xd is a matrix which satisfies
|D|| S LTL/
Thus,
(En)) >HH H' vec (C(0*)) + ( vee (C((*))
+ 3/2 ( &I+I H' -H & H²) voc (B")
We define the matrix B2 such that
vec (B2) = (D/v) vee (C(8*) + (H' &I - 8H) vcc (B')
(61)
Hence, using A3, (60), and Lemma 13, we get
vec (B2) |I |B2 || < |B2
$ |D/ /DI vcc (C(O*)) |1 + II(H* &I+IS -y H & "H'
L LD
3/2
1/2/2 D 4
1
6
+
C2 +
1
2
3/3/2
4,12
C3/2
step.6
Vn2
1 Ristt 14 LD 6ast,6
C2
CSteep.61
2/132
3/2 2/22 Step.6
where in the last inequality we use that y S 1/LL Cstep.6). Combining the above bounds in (55), we arrive at the expansion formula (51).
Lemma 13. Assume Al and A2. Then for any (0, (O,1//LCstan 6s it holds
(a) All eigenvalues d i (l....,, ..) of the matrix H @1 + 18 H & H* satisfy
2p 7 /2) < ' 2L(1 7p/2);
(b) [[ 0I+I0H 3 11 1/2;
(c) In addition,
(H* 81 - H 8H H = (H* 01+10H")-1 + D where |D]| LTL/u.
Proof. Assumption guarantees that the symmetric matrix H* is positive-definite Let U....., Ud E dd and A 2 d2 2 ... Aa p be its eigenvectors and eigenvalues, re- spectively. Then we notice that
H' TT - & H' H' @(I (2/2) (T (I- H' H'
Hence, the latter operator is also diagonalizable in the orthogonal basis u; @ uj E Ed with the respective eigenvalues being equal to A, - (x/2)A,) (1 (n/2)A,). Hence, we obtain the first
part of lemma (a). To prove (b) it remains to note that for < 1/ holds (2u(1 - - L/)2)) < 1/2. Set now
S H øl +181 H Ex
(62)
R = H' Ø H E 2xd
17

---

Published as a conference paper at ICLR 2025
Then it is easy to observe that
- + s-1 y (RS-1)
k=1
provided that y R| < 1. Sice R and S are diagonalizable in the same orthogonal basis {u, & Ushisijaa with the eigenvalues X; and X; + >j. respectively, the condition | < holds provided that y < 2/ L. Hence, for 7 & 1/ L, it holds that
(H' &T TT H
H & H (HH (T+ D,
where D E xd satisfies
RS- |D| 2 || - I
We now state an auxiliary lemma about the function C(0) from (50). Lemma 14. Assume AI, A2, A3(2), and CI(2). Then, for any 7 E (0, 1/(L 2)te it holds
Jz C(0) (d0) - C(0')ll 3 //2
where the constant C2 is given by
L Dast.22
L / lust..2
C₂ =
2
(63)
11/2
V
Proof. Recall that
ei(0) = -
Hence, using the definition of C(0) in (50), get, with 0 Rdd, that
- = -100--0( - =
(e) (0 (00))
Using A3(2), we obtain
(0) - ei L(V/(0)))))))) V)(00), 0*) -VV(- ( 2
1 - 0+11².
Hence, combining the previous inequalities and using Hölder's inequality, we obtain for any 0 e IRd that
[[C()) c(0"))( - L 110 1- + L2 0*
Applying now (2),), we obtain
|| f
< / |[(()) s L jRd
D 2
D
+ To L
We conclude the proof by using the fact that ryu <
Now prove (24). We synchronous coupling construction defined by the pair of recursions:
a 0g VV F(Ok, Ex+1),
0g
u 0, - 7 (F
8 ~ TT.
Recall that the corresponding coupling kernel is denoted as (.,)).
Then we obtain
E, [m]] 8*
E, [0g 0z] n-
Ex,, 10x 0*)
k=n-1
2n
Kg E,
10g 0x] + (0,, - 07)
k=n+1
18

---

Published as a conference paper at ICLR 2025
Using (48) and Cl(2), obtain
I E
[0x
0x]l - (1
1100 0ol 131/1///2
-2212))
S (1 - (1- -//))////)/))))111
8-113] +
V/
Summing the above bounds for from n + 1 to 2m, we obtain (24).
A.3 PROOF OF PROPOSITION 5
Note that
E, E. - = 22, 0*] Eu - 0-}.
Applying (24), we obtain
L
T.
1ast.6 T0
|E (R) n
8'11 - ( (
C1 +
3/2 + R3(00 - ,,,0,,,,0 ,,,)). n),
(64)
241512
/
where
(1
(E./2(100 0-|]]] + VTT2
[ 8,,,
m)1l m,,
(65)
myH
v/
and the statement follows.
B PROOF OF THEOREM 3
Theorem 15 (Version of Theorem with explicit constants). Assume AI, A2, A3(6), and CI(6).
Then for any Y E (0, 1/L Gstep.6]l. n E N. and initial distribution v on R the sequence of estimates (14) satisfies
TH
C2 11/2n
C47
E//211 (T - 0-))
+
+ C3y + n//2 + R2(n, 10000 - 0)))),
Vn
where we have set
L last,
C2 = =2 22
1/2
C3 = 0o
C. = co LD 22
(66)
2p
and the remainder term Rn, 7s 1100 (1) is given by
Cu L(1 (m+) 1)/2
R2 7, 110 111
1 [1160 - 1-
Yp
L Lco 7p))+ 2n0yu
E//2[110, 0* (67)
Proof. Throughout the proof we omit upper index (7) both for the elements of the sequence
{of JeEN and Polyak- averaged estimates g(2)) Instead, we write simply Os and o,, re- spectively. Summing the recurrence (30), we obtain that
(0, -0-)
Op+1
0*
02n+1 0*
1 2n
Σ kmn+1
(0x)
1 2n
Σ n(Ox).
(68)
yn
mn
k=n+1
Applying the 3-rd order Taylor expansion with integral remainder, we get that
v(((2) (0x - 00) + ( f(10 + (1- t))x) dt (0s 02)
where v3)(-) Rddddd, Using A2, thus obtain that
[[((1))] < 2 Lg |0 11112_
19

---

Published as a conference paper at ICLR 2025
Applying Minkowski's inequality to the decomposition (33) and to the last term therein, get
2/ 11 - 00
E/ 110m-111110000 0
2n
1/ H (O. 0')13
+
E1/2
Σ
ek+1 (0x))
yn
7/1
k=n+1
Ly
2n
/ [ 0- 11]
+
2n
k=
Applying Cl),), we obtain that for 7 E (0; 1/(L Catep.2)] )] it holds that
277
0 - 10 $ (1 >2) E. [100 0" [12]
(69)
Moreover, from 7 E (0; I/. Cstep.4) holds that
D 4
E// 0- || S (1 - "/) 10 1011
(70)
Combining Lemma 16 with previous inequalities, we obtain
2/21 H (On - 0-)113
T
D 1/2
1ast.2 T2
L Diast, 1T
1/2/211/2 LD 1/2
last,2
27 1/2
vn
7 1/22
2p
(1 (u-tu)(nt11/2
L
L(1 -
+
E//2 [1100
E2/2 [1100 [1]
7n
11
nyp
and the result follows.
Below we provide an auxiliary lemma used in the proof of Theorem 3. Lemma 16. Assume AI, A2, A3(2), and C1(2). Then for any 7 E (0; 1/ (L Cstep.2)] and any n. E N,
it holds
LD
L(1 7p) 7p) (1+1)/2
E/all Σ k=++1
-K+ (x++
last.2V 2
E -0 11]
1/2
7/4
(71)
Moreover, p 2 2, and assume AI, A2, A3(p), and Cl(p). Then for any (0: Catep.p)] and n holds that
L LD 1/2
last.pV TpPTT
E//(1l Σ
(Ex+1(0x) - Ex+1 (0)))0)))
1/2
k=n+1
(72)
L p(1 (
E3/P11100 0" [P']
1/2
Since {Ex+1(0k) - (0+1(0")} is a martingale-differeet sequence with respect to Fk. we have
Proof.
2n [ Σ
2n
(#k+ (0))
Σ
E, [1(EE422((h)) Ex+1 E
k=n+1
k=n+1
where (4+1(0') = F ((ttt uses the same noise variable Ek+1 as F(Ak, Ex+1). Note that
Ex (fx) - Ex+ (0) (. FF Ex+1)ll
- -2E, (VV 1)+ - v
(0())) V {(())))] -VV
Using A2, A3(2), and taking conditional expectation with respect Fr, we obtain
E, [[ll|==110p0 - Ek+1
10*) -
< (L((((0))) - (f()), 02 8*) [V -V((0-)
< I. 11 11)
20

---

Published as a conference paper at ICLR 2025
Thus, obtain that
2n Elll
2n
Σ (0x+1(0R) E Amn+1
s L?
Σ A=
E - 1*1
and the statement (71) follows from the assumption C2).. In order to prove (72), we apply
Burkholder's inequality Osekowski (2012, Theorem 8.6) and obtain
2n
2n
(0x+ Ex++ Ex+1 1 - pE!/1 I(
Σ k=
|ER+1 - Ex+1 (0))
k=
2n
p(
Σ
E2/0 (1xx11(0))0) Ek+ 1++1(00)1P1) 1/2
kmn+1
2n
p
Σ
( 1/2
k=++1
2
LD
last.p V MipT
1/2
T.p(1 - -pp)(n+11122 E//11100 - 1%),
1/
11/271/2
where in (a) we have additionally used Cl))).
C PROOF OF THEOREM 6
Within this section we often use the definition of the function 3b: Rd + Rd from (38):
(0) (1/2) f(0)) 02)02
(73)
Theorem 17 (Version of Theorem with explicit constants). Assume AI, A2, A3(6), and CI Then for any y E (0, 1/ Cstep,s) (2/(11 initial distribution v, and N, the tichardson-Rombeer
estimator 0 @RRR defined in (37) satisfies
TrE
12R
CRR.2
+ CRR CRR.47 n 1/2
H 0'119
+
1/2
1/2
1/2n
Ra (n, y, 1,010- - 1))
where have set
LD 1/2
coD 1/2
1/2 last,2 T2
CoD T
Co
last,2
CRR,1
CRR,2
113/2
1r//
112/2
(74)
LD/222
3/2
1ast,6
co Dasss T
CRR,3 =
+ +C,
CRR,4
1/3/2
1
C is defined in (52), and the remainder term R4 7. |10. - (1) is given by
Ra(n, (1,,,,1100 001l)) Co L(1
(11)22
nyp
2 0011 [10] + E/ 8- + --1191
(75)
4
Proof. Using the recursion (30), we obtain that
H (OLRR) 0-)) = 2(0 - 0*)
((0 - 8*)
g
0*
(227) Ar
n+1
+
7
7m
2ym
2m
2m
2n
22x+1 (0(3)) Ek+1
10
(27)
1
[20(((17)) - 17( (22)
(76)
k=nt1
k=n+1
21

---

Published as a conference paper at ICLR 2025
Therefore, applying Minkowski's inequality to the decomposition (76), we obtain for any initial distribution v/ that
1 1 |// H ( 0-)1
Σ
Ek+ Ek+1 (0
2 00 12]
2
E
-3
n
yn
7n
k=++1
Ti
2/22110
(27)
-0
1//211002211 0-1131
2yn
n+1
2pm
T3
2n
+ E III
Σ
(00)) - -
k=++1
1 2//2111 |||
2n
Ek+ (0f21) Sk+ (0*))
||2 (v)) 22 x2
k=n+1
To
Tb
2 2 2
Σ
m(O
JT, (1,))
-/
n22 -22 (b)
n
n
k=
Now we upper bound the terms in the right-hand side of the above bound separately. First, we note that
T
Ti
vn
Using C2),), we get
- (p)
D Dl.c2.02 72 /2 1/2
To + T3 x
E1/211100 1- +
7
Applying Lemma 16, we get
1/2
1/2 last.
2
1/272
L(1 - 714) (x+1)/2
T4 + Ts S
E E4/2[1106 - 0" 112].
1/2
14y
Now we proceed with the term To- Applying the recurrence (11), we obtain that
0f 0 (I 7 (0!") 0*) 781 (0( (06 )0(0)²))
(77)
Thus, taking expectation w.r.t. T.y in both sides above, we get
(0, 8*) Ex, [n(obT)]] m.,(1) + +G)
where G(0) defined in (38) and writes as
G( ( ( + (1 -1-18 t)0 dt (0 04y03
Hence, applying A2 together with Proposition 2, obtain that To = [|2 (1²) - (2)(1)) S 3/2 Finally, using Lemma 21, Lemma 20, and Lemma 18, we obtain that
(78)
Diast,1 L YT3
+ Diast,1 L/
3/2/22 1 2
3/2 3/2
T7 <
un-/2
1//2
13/2
L(1 - 71)(n+1)/2
D 4TT
E//2 0-119) (/1))E///110
0-11"-
nyμ
Combining the bounds above completes the proof.
22

---

Published as a conference paper at ICLR 2025
Below provide some auxiliary technical lemmas.
Lemma 18. Assume Al, A2, A3(4), and C1(4). Then for any ry E (0; 1L Stto and any n E N holds
2m
Diast,4 La 17á
Diast L3 72/372
(.))))
2
+
(79)
Jm 1/2
n3/2n2112
1=++1
Proof. Using the fact that ny is stationary distribution, we obtain that
2m
E [II
Σ (v((n)) (000))=x(v(111)) (b)}1 = nE*, (1l:((0)) -T
k=++1
n-1
k)E,, [(v)(0)) (())))(((()))))))))))()))))))) n., (v:))
Using the Markov property,
inequaaltyy Proposition 1, and Lemma 22, we obtain
Ex, (vv(()) - n., -r
((v(0)))))))))) -T, T., (v)) (0) - T. (+:)]
(80)
2 (1/2) (m()) Lg E.,, [11)(00) - (+36l / c( (1)].
where in (a) we additionally used the fact that
W Woddoo: TT,) = / c(Do. (0).
Using C4),, we get
L3 Diast, 2
Ea, (l)) TT,1 < E,, (1000011))1111 L3E,,,
= 1110o 011141
(81)
m2
and, using C2) and (4), we get
ʃ 2 200, dd (1) (On)
(82)
$ / 110 -012 (100. 801l + 1100 8* +
23/2g11222
(0)dTT (8o)
(83)
11/22
1 (116 8- 1
2TZ
1|0 (11))
(110-
0* + |100 00 (() (0)
(84)
4
D Distt,17 27 D 22 72
D 2
2A
(85)
n2
n22
Using (81), (82), and Cauchy-Schwartz inequality for (80), we obtain
(x,(00) n., (1))) (1)(k)) - T., (+)) S (1/2)//m(>) Lg D a T1
42
Combining the inequalities above and using that m(7)) = [2 Log 1 7/
log 4+1 7/4
we get
2u
Diast, L3 224
D Dinst, Li 72
1/2
n -
Σ (v((0)) - -., (1)))11 <
12
122
1=
D Disst,1 La TTá
Diast, L3 11/2
um
1/2 1/2
n3/221112
23

---

Published as a conference paper at ICLR 2025
Lemma 19. Assume AI, A2, A3(4). Then for any (0; n. and any & N it holds that
E[ - -0x+ [R] 3 (1 - 11)) - 0z(1"
(86)
Moreover, let p 2 2 and assume A2, and A3(2p) Then for any 7 E (0, 3:3PL
A2,
P
and any
holds that
E[l[0x+1 - 02++1 20 F = (1 - 1,)0 10.11
(87)
Proof.
Recall that the sequences {0s} and {6s JEEN are defined by the recurrences
x 82 (EF(1),E4+))
8g 0 R
(88)
0 0g VVF C0t:)))
0o = 0 e RR
(89)
Expanding the brackets, we obtain that
| 0x+1ll* ||0 - 0xl1 4 + [VF 1
VF (k+1))l
+ (VF Ex+1) (0 11, - 022²
+ 2 F Ek+1) VF((A, Ex+1 11 0x1l
(VF Ck+1) (0x. 1k+1) ),0; -0x)1(0; 0 21
- -47 (VF((R Ex+1) V / (0,, 1x+1), 0r 02) V 1' (' Ex+1) VOO0
Using A3(4) and
inequality, we get
- Ex 1)1 - L (V)(O)) - V'(Oe), On On) 110 0
E((V (0+ - || 041191Fa s (()) V/(O2), On - 0x) - 0 11
[x)9|Ful & ((v) vf(()), 0x Aa)1 0x 8 11
(OVF(Os.E+1))) - VF(00, 02) 0al19[Fa] = (V))))) v.((),, Ox - 02) - 0A11
Similarly,
E(VF VF(O,, 02 - - Ex+1) - - Ex 111
< <L (f(()), 8x - 0x) 0x112
Combining all inequalities above, we obtain
E[][0++1 1 10 1= (4h 7 L 2,2 -
Vf(()), 0n)1022 12
Using Al and since 1 - 33 1.3 /4 3 2 - 11y L/4, we get
E[I|0x+1 0.+ [1
5 (1 47/(1 11y 14) |0, 0x
$ < - 27/4(1 - 11 L L/)) |0 0e
Since 11/ 1/2 < 2/( we complete the proof.
For simplicity of proof for second part of lemma we define dx+1 |10x+1 12till- Then we have
E| Ep +++
[x]
E - (.(VF(O....t)) - (F(00. -0)) - Ex+1) - (++1))11++
Σ p!
6 222
i4j+f-p (0...p
Now we bound each term in the sum above.
1. First, for p.j 0, the corresponding term in the is equal to 6
24

---

Published as a conference paper at ICLR 2025
2. Second, for = p- - 1,1= O. we have
((L-2)(VE(O (Ox, Ex+1) On O2)))) = - (V/(())) -0x)
3. Third, for / 2 1 j 2 2 we Cauchy-Schwane inequality and get
Ex+1) (2T(VF(0R, Ex+1) - v F( (k+1), 0x [V V (A)-)))
I 2 2+
23 6% FV (k+1) F. Ex+1)1
Moreover using A3(2)), we get
E 22 (02, (k+1) V F[(0s, Ex+
Ex+1 2(1
- 2 22p 21 (Vf (0x) - (f(()), 02 -8x)
Combining all inequalities above, we obtain
E1 k++1 [u) $ "
2py (V ff(0)), 02)
p! 2'75+21 2 (vf(0.) - vf((k), 02 - 02)66002
+
Zi!!!!
i+j+-=p
(U.... 2+2122
Since 7 S 3P4L.
P we have
E [ S b% - -VV((())))) - -V))(()))((()))))))))) - 06))02r-
remains to apply A1 together with an elementary bound (1 --pp)) S (1 7p)P.
Lemma 20. Assume AI, A2, A3(4), and CI(4). Then for any 7 (0:1/(4 (L Cst any N and initial distribution v it holds
2n
2n
n
Σ (v(0p) T (n
Σ
(v(0p))
(0,,)-,,))11)) (+)31111
1mmot1
Amn+1
Lg (1+122))
D Dlast, 4
E2/2
0" 111
nyp
Proof. Using the synchronous coupling construction defined in (47) and the corresponding coupling kernel Ky, we obtain that
E//111 Σ (v(Ok) - - (+)3]1 -
(EX,,,
Σ
(v(On)
- (+)))11))1
kmn+1
(90)
2n (0(0)) (+))))
2n
III
Σ
(b(0%)) - -10.))1111
kmn+1
kmn+1
Applying Minkowski's incquality to the last term and using Lemma 22, we get
2n
(EK>
Σ
(bb(t)) - (b (11)))
(E (1( ((4))1111122
kmm41
kmn+11
2n
L3
k m. (0x,
1/2
2
k=n+1
Using Hölder's and Minkowski's inequality and applying Lemma 19, (69) and (70), we obtain (E (0,, 1/2
+ [100 0+11+ + 72/2 < (EKs, O/ 02 (E2" 1110, 0-11-1
11/22"
D 1ost, 4
1/2TT
2//222
< -1/)///2
11100 - 0oll (1) $1100 0" 1
11/
1/2
(iastt
$ (1 -/1////2
+
EL/2
0-11²²
/
25

---

Published as a conference paper at ICLR 2025
Combining all inequalities above, get
Σ (M10))- La(1 mm 1)/2
2n
Diast, 4774
(E
III
11/211000 - -011+]]
7/
k=n+1
Substituting the last inequality into (90) we complete the proof.
Lemma 21. Assume AI, A2, A3(6), and CI(6). Then for any E (0; 1/LL Cstop, n E N, and initial distribution v, it holds that
2n
1 E1/2
In(0x) TT n
1b((s) [+)))
k=++1
k=n+1
(1 - 700 71) (x+1)/2
L4 D 3/2
last, _- 2/
E//2 0" 111 +
n7/4
3/33/2
(91)
Proof. Applying the 4-rd order Taylor expansion with integral remainder, we get that
(fo S(10 + (1- -1)0) dt (0 - (0-07)03
( (b) +
(92)
and using A2, we obtain
(1/2)II (J," AV4 "5 ft6 + +(1 (1-t))) dt (0- (0-07 0 - L4 110 11s.
(93)
Therefore, combining (92), A2, and applying Minkowski's inequality, we get
2n
2n
E/2 Σ [lr(0x)) nr (1b) < 2
Σ k=
[1x(0s)) - Thy (+))
k=n+1
L
Σ
E
0-11%) (94)
6 k=++1
Applying C1(6) for the last term of (94), get
T DD
lust.6" 3/227
3/2
E//2 Σ lln(Ok) n. (b)) S /
Σ [1x())) (+)))
13/2
kmm+1
kmn+1
(95)
L.4 (1 - 71)33(++))11))
1 10
1 [1 7/133/2
In remains to notice that (1 7//3322 (1 7y1), and the statement follows.
We conclude this section with technical statement on the properties of the function & from (73).
Lemma 22. Let vb-)) be a function defined in (73). Then for any 8 E Rd, it holds that
(})(() ((('))l < Le c(0,0')
Proof. For simplicity, let us denote T 3 f(*). Hence,
(1x(() w'0')ll < マ [T(0 02 - T(0' - -
(96)
Note that
Σ =K ETsaas
|1 v)ll
|T|
sup |T=||||81111 000
sup sup- #000
|| |
||]|||
2000
sup
||y| ||
(97)
26

---

Published as a conference paper at ICLR 2025
where t(x, 1. Therefore, for any x, R it holds that
[z v)ll
| 12ll |T]
(98)
We denote T2 Ty Then
Σ Tom yils) E Tiin yi)az + (xx y1)91)) 1.j
Uk
Tonn(os - y1)org + Tisu(os- - -i)yys 1
(99)
where the first inequality is true since Tiys Tjix by definition of T. Combining (98) and (C) and using triangle inequality, we obtain
|| (|all + l1vll) < |T - wll (1 + lvll + 2V2T2V7
||l|| s
v/I
We complete the proof setting x = 0",y = 0' 0*
D PROOF OF THEOREM
Theorem 23 (Version Theorem with explicit constants). Letp 2 2 and assume A1, A2, A3(3p), and C1(3p). Then for any (0. 1/LL Catep.3p) p/(4- 3" L)), initial distribution v, and n E N, the estimator g RR)) defined in (37) satisfies
E//1|| H* (Ø(RR) 0'' CLV Tr 1/2 1/2
C2PTp
+
CRR,
+
1/2
+ CRR,773 3/2
n 1/2
1-11/p
1/2
n/2
CRR,
+ Rs Rs (n, 110 0" 1)),
n
where we have set
coD 1/2
1//2 Inst.p To
L L
1/2 1/2
last.p
Cp L last, PT
CRn,5 =
CRR.6
11/2
1/2
3/2
(100)
(G,
L/3 3/2
CRIL7 cu C1
last,3p
T3p
CHR.S =
Cp T. Diast T2p
3/2
42
C is defined in (52), and the remainder term Rz(n, 7. ||0u 1*1)) is given by
Rs (n, 7, 7.1100 11) co(1 ()))(++))/²
I.p(1 7111 (n+1/22
1/1(1100-00 1+]
E//[[100- - 11)
# 11/2,1122
7m2
co [.( (1)((+1)))
D Dinst.2p 7Tpp
en L( - 714 13/2)n
E./P[1100 - 0011200 +
E. [1 -011
7
71
(101)
27

---

Published as a conference paper at ICLR 2025
Proof. Using the decomposition (76), we obtain that for any p 2 2, it holds that
2n
E//1[| H (0...)
0-)
Ek+1 (0))
- E
00
+ yn
E
11/10000 - --
7
k=++1
1
(27) 1-] + ym
1
E |11
[ 1-1
m
Ta
1 E
sk+ (0( 6k-1 (0*)
Æ=n-1 1
T4
2n
1 E/
S sk+ 10 (0(221) Ek+ (0*) + 1| (1+) T2y (2))
11
To
2n
2n
EV
((B(T)) - (+))1 + EV/p111
>
( - T2y (15)
72
R=n+1 1
k=n+1
1 2n
E (/(() IP +
Σ k==+1
k=n-1
Now we upper bounds the terms above separately. Applying first the Pinelis version of Rosenthal inequality (Pinelis, 1994, Theorem 4.1) together with A3(p), we obtain that
5 CI Tr E/p!/2
C2PTp
1/2
11-1/p
Applying Cl(p) (which implied by C1(3p)), we obtain that
D Disst.p7 Tp
(1 - (x)(2+))22
T2 + Ta
E./2 0 1p].
111/217112 1/2
7m
Applying Lemma 16 (see the bound (72)), get that
LD2 1 1/ppTp
+ Lp(1- - (1)(n+1)/2
T4 + Ts S
E1/0(100 - 1-))).
1/22
12/2g1/21
Using the bounds (77) and (78), we obtain
To S C/73/2
Applying Proposition 8, we get
Dinst.200 201 1/2
I Disst. Tp
EE/P Σ
((( n. (1)
13/2 1/2
μ n
k=n+1
Using this bound and Lemma 24, we obtain that
L Diast D.astt22pP3, 2prp2, 1/2
L D.astt Tp
L(1 711) (n+11/2
Diast 2p 2p
T7
EL/1[100 00 p01120]+
1/2
12n
Yun
Finally, applying the definition of G(O) in (38) together with (3p), we obtain that
L 3/2
last.3p 7
3/2_3 3
I.
2n
Ts
(1 7p) (3/2k / [110- 111
3//2
n
k=
I. D.2 3/2
last. 3p
7
3/2
T.(1
(3/(3
E!/r [110 0* [132]
3/2
7/
To complete the proof it remains combine the bounds for Ti to Ts.
28

---

Published as a conference paper at ICLR 2025
D.1 PROOF OF PROPOSITION 8
In the proof below we use the notation
(0) ()))) (v))
We proceed with the blocking technique. Indeed, let us set the parameter
log
m = mm())
=
(102)
7/
Our choice of parameter m(7) is due to Proposition 1. For notation conciseness write it simply as m, dropping its dependence upon 7.. Using Minkowski's inequality, we obtain that
n-1
In/mJ mm-1
E
(0.))
< (
((x))| + m (1+((1)11
(103)
K=
Now we consider the Poisson equation, associated with QT and function v that is,
9m (0) - Q"7 9m (0) = (0).
(104)
The function
9m 9m)
QttTh 5(0)
(105)
k=
well-defined under the assumptions A1, A2, A3(2p), and C2p).. Moreover, Im is a solution of the Poisson equation (104). Define q == (n/m]. then we have
(b.O)= Σ
Bmr:
with Bm.
Σ (m (fmm+r) - Q" Im (0km+r)) k=
(106)
K=
r=0
Using Minkowski's inequality, we get from (103), that
El/P Σ J(PIPP < mE [I
Σ fm (6km) - Q" Im (0 11m) [P]] + 2mE 1/p (1166)1)))))
k=1
(107)
Now upper bound both terms of (107) separately. Under assumption A2, and applying C1(2p), we get
E4 [10(011)
- [10. - 0+1 S
I. T. Diast.22
(108)
24
To proceed with the first term, we apply Burkholder's inequality (Osekowski, 2012, Theorem 8.6), and obtain that
E [II
{y (0am) - O7, Im (0 ()m)) [P]]
1=
$ pP1/ /P (gm (Okm) - Q,, Im (0(k-1)mm) 13)p/22 (109)
Applying now Minkowski's inequality again, get
2/P
(0km) - Q.T gm (0 ((k-1)))) 113) < (E2/pl [1l (gm (0km) - Q"" 9m (0kk-1)m)) [[']
S (2/p(11 (0))) - gm (0n)lP))
2 2/ (1)
29

---

Published as a conference paper at ICLR 2025
It remains upper bound the moment E gm (P)) In order to do this, first that due to the duality theorem (Douc et al., 2018, Theorem 20.1.2.), we get that for any l E N,
1Q77*((B) xy (+))]
1Qth (u e()) T. (u e))l
sup
- La Wo (Ty) 2
s (1 (eee)))WW(bir Wo(60,mT))
where the last inequality is due to Proposition 1. Hence, applying the definition of (0 (105), we obtain that
20
[llgmm (90)1PP
[IQ km (0)11) S 2L
Σ (1/2))
((W)) [[Wa(ōp, ,}}}]
k=U
k=U
To control the latter term, we simply apply the definition of W Wo(00, sT.y) together with (2p)), we get
and a cost function c(O, 0')
E//P [[W (60, TT}}²] &
100 10- 1110 (1
(10-0* 110' - 0
8 T (dd))=
1/p
V/
// 100 88 (d0)
1/201) (100-01)
0*ll 110' 0-
T2v? vp
2p
Th (dd)) 1/2p
2pp
Combining now the bounds above in (109), we get that
2ppt La 7
{gm (0km) Q7 Im (6 (s- 1)m3 ||
(110)
and, hence, substituting into (103), we get
2pp L.g 7 r
T. D. Dastt, 22 y
E ((.))P]]
(111)
2/1
Now the statement follows from the definition of m = m(7) in (102) and [n/m] S n/m.
D.2 VERSION OF PROPOSITION 8 FOR ARBITRARY INITIAL DISTRIBUTION v.
In order to prove Theorem 23, need a generalization of Proposition 8 for arbitrary initial distri- bution v. The following result holds:
Lemma 24. Let {0())) JeEN and {o( JEEN be defined by the synchronous coupling construction
(47), where of Thy and o(²) v. Then, under ussumptions of Proposition 8, for any 7 e (0.1/(LCstep.6)], N and initial distribution v, it holds that
2n
2n
E//P1I
(w(0l2) - (0)HPP]] & E
Σ
(w(0(()) -
k=n+1
k=n+1
Lo 7/1) (1) (x+1)//2
Diast, 2p T
El/P(1106)) 0+ (111 +
7/4
/
where co is an absolute constant.
Proof. We consider the synchronous coupling contraction defined in (47) and denote by K,, the corresponding coupling kernel. Hence, we have
(1k(k)) (()))P (EKg
(v((k)) (1))))))) 1/2
k=n+1
2n
2n
< 11/2
Σ {v)(x)) - - (+)))) + (EK,
Σ
(b((2)) - ((
k=n+1
k=
30

---

Published as a conference paper at ICLR 2025
It remains to bound the last term in the inequality above. Applying Minkowski's inequality together with Lemma 22, we get
E
Σ (v(O)) - -(0)))11
2n
1/D
S Σ
Lg
2n
Eky P.t
(0k, 0x))
k=
k=n+1
Using Hölder's and Minkowski's inequalities together with Cl(2p) and Lemma 19, we obtain that (E (0k, 0x)1) 1/p
23/27/12222
$ (E [1|0% - 2 1/22))
( (E 1/())))
110 8" aa + E. E2/02) 11 1-
11
2D 1/2
23/2 2/1/ 71/2T2p
(1 - //))//((E,,, 1110 - 20 1/(2m) 11/22)) (E. (E!/(2P) 1110 - --1 +
last.2p
T2P
# 1/2
(Diast.2 Y + 1 112
< (1 - 7/)
Combining all inequalities above, we get
2n
1/8 x (0(0+)-
Ia (1+
D 1nstt,2p 7T
EKK EuyRy
E. E// 1110
7p
A=-+---11
and the statement follows.
E EXPERIMENTAL DETAILS
We recall the error representation (39), and obtain with simple algebra:
2n
0(7) 0+
0*
H
+
Σ
EK+1
2n+1
7n
m
k=R+1
(Ek+1 (0(7)) (x+1(00))
1
(8
1
G(O
(112)
n
n
k=n+1
k=n+1
Under A3(6), the statistics
2m
Ik=+t1 (0*) is sum of independent random variables, and
2n
2n n 'Ell
TrEx
(0))
k=n+1
Hence, in order to the rate of the second-order terms in (41), it is enough find the de- cay rate of the right-hand side in (112). We select different sample sizes n 250 x 2 where k 0, ...... 14, and run the SGD procedure (2) based the constant step sizes y and 2y, selecting 7 1/V Then we construct the associated estimates A(?) and ((22), We conduct M 320 inde- pendent parallel runs to approximate the expectations. Code reproduce experiments is provided at https://github..cm. www.///aaaoooooo/icccaaaaaaaaa httpa///wccccccooooooooeeeeeeeee
31


Reviews:
[{"review_id": "CzBhY3MabZ", "reviewer": "Reviewer_8ENV", "summary": "The paper investigates the convergence of stochastic gradient descent (SGD) for strongly convex and smooth problems. Concretely, using the mean squared distance as the performance metric, the author proves that the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation technique can achieve the optimal convergence rate for both the leading and higher-order terms.", "questions": "See **Weaknesses** part.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors provide interesting results on SGD with Richardson-Romberg extrapolation.\n2. I also appreciate the authors' honest discussion of their stronger assumption compared to the previous works, e.g., the higher-order smoothness. \n3. Moreover, the writing is easy to follow.", "weaknesses": "Since I am not very familiar with related works of the Richardson-Romberg extrapolation, the author could feel free to point out anything wrong in my following question.\n\n1. Could the authors provide more discussion on C1? Especially, when can (20) hold?\n\n2. The paper studies the convergence in expectation, is it possible to establish the high-probability convergence result with the same rate for both leading and higher-order terms?\n\n3. One point I found is that when the stochastic problem degenerates into the deterministic problem, the current rate cannot recover the well-known linear convergence result. Could the authors make some statement on this point?\n\n4. Another thing I am interested in is that the leading term $O(n^{-1/2})$ seems not to be infected by the stepsize (even if without the Richardson-Romberg extrapolation), which seems very different from the existing analysis of SGD for the same problem. Could the authors elaborate more on this fact?", "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": "WRzbWRJPq9", "reviewer": "Reviewer_UgHP", "summary": "The paper considers the minimization of an objective function through unbiased estimates of its gradients. It brings tools from the theory of Markov chains to the study of stochastic gradient descent, showing that, under suitable assumptions, the Richardson-Romberg extrapolation achieves the optimal non-asymptotic risk bound (proved by Li et al. 2022 for the Root-SGD algorithm). Extensions to the p-th moment bound are also provided.", "questions": "Could the authors provide a geometric interpretation for the definition of $c(\\theta, \\theta')$, and the ensuing geometric ergodicity of the SGD iterates with respect to $W_c$? Also, are the authors aware of other contexts were such non-standard distance-like functions have been used, which could be cited in the paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper interprets SGD updates with constant step sizes as an homogenous Markov chain, and uses a trick from numerical analysis to show that the difference of the average processes obtained for step sizes $\\gamma$ and $2\\gamma$ (defined in eq. (37)) will converge to a point that is closer to the optimum (as shown by Dieuleveut et al. 2018).", "weaknesses": "The paper could use some more polishing in its presentation:\n* The geometric ergodicity of the sequence of updates is a crucial aspect, yet is not defined in the preliminaries. It would also be valuable to add an intuitive explanations for how this fact would be used to derive the risk bounds. \n* $D_{{\\rm last}, 2}$ used eq. (19) in line 222 is not defined.\n* In line 480, the beginning of the sentence should be \"Directions ...\"\n* The authors should also make explicit the fact that the number of samples, $n$, needs to be known a priori to optimize the step size $\\gamma$.", "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": "VCOOxTKJVx", "reviewer": "Reviewer_LgiJ", "summary": "The authors provide convergence analysis of both the Polyak-Ruppert averaged SGD (PR-SGD) and the Richardson-Romberg extrapolated SGD (RR-SGD) by a two-term expansion of the quantity $ \\mathbb E^{1/2}[ || \\hat \\theta - \\theta^* ||^2  ]$, a quantitative refinement of asymptotic normality. They show that RR-SGD achieves the same rate as PR-SGD which is known to be optimal.", "questions": "1. The extensive use of $\\lesssim$ is rather confusing and potentially undermining in the paper. For example, in Corollaries 4 and 7, are there multiplicative constants suppressed on the leading $n^{-1/2} \\sqrt{ \\operatorname{tr} \\Sigma }$ terms? \n\n* If there are: (1) these corollaries do not match in sharpness the existing results, and provide little insight into how RR-SGD compares to PR-SGD as the latter is favorable exactly because of its Cramer-Rao-type optimality in the leading term. \n(2) is it possible to spell out and compare the explicit leading terms?\n\n* If there are not, I wonder why $ \\lesssim$ instead of $\\le$ is used.\n\nGiven how the notation $\\lesssim$ is defined in Line 118 I'm afraid the former is the case, right?\n\nEither way, the authors might want to say a few words on what terms/constants are being suppressed at least for presentation purposes.\n\n\n----\n\n\n2. Along the same line, we know that (considering decreasing step sizes for the moment --- you might be able to work back and forth between these two regimes) with PR-SGD the asymptotic normal distribution one can prove for\n$\\sqrt{t} (\\widehat{\\theta}_{t}^{\\mathsf{avg}} - \\theta^*)$\nhas a variance that matches the Cramer-Rao lower bound, \nwhich happens for any step sizes $ \\gamma_t \\propto t^{-w}$ where $w\\in[1/2, 1]$.  Whereas for SGD without averaging, the asymptotic normality takes the form of \n\n$t^{w - 1/2} ( \\widehat{\\theta}_{t} - \\theta^* ) $ where $w$ is the decay rate of step sizes defined above. Even in the $ w= 1 $ case, one gets a variance that's strictly larger than Cramer-Rao (hence than that of the iterate average). When $ w<1 $ this is a strictly slower rate of convergence. \n\nLong story short, PR averaging accelerates the optimization via a \"removal of the step size effect\". Is it the case that RR has a similar effect without averaging?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-motivated and well-written. In particular, the last-iterate bound for RR-SGD, despite some issues raised below, is novel.", "weaknesses": "See Questions", "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": "2aTamXvqqU", "reviewer": "Reviewer_s57H", "summary": "The paper contains an analysis of one-pass SGD on stochastic objective functions:\n\n$$\\min\\_{\\theta \\in \\mathbb{R}^d} f(\\theta), \\quad \\nabla f(\\theta)=\\mathrm{E}\\_{\\xi \\sim \\mathbb{P}_{\\xi}}[\\nabla F(\\theta, \\xi)],$$\n\nThis is run with constant step-size $\\gamma \\asymp 1/\\sqrt{n}$ with $n$ the number of samples,  and it is shown that $p$-th moments satisfy a bound\n\n$$\\mathrm{E}^{1 / p}\\left[\\left\\|\\bar{\\theta}\\_n^{(R R)}-\\theta^{\\star}\\right\\|^p\\right] \\leq \\frac{C p^{1 / 2} \\sqrt{\\operatorname{Tr} \\Sigma_{\\infty}}}{n^{1 / 2}}+\\frac{C(f, d, p)}{n^{3 / 4}}+\\mathcal{R}\\left(\\left\\|\\theta_0-\\theta^{\\star}\\right\\|, n, p\\right),$$\n\nHere \n* $\\bar{\\theta}\\_n^{(R R)}$ is the ``Richardson-Romburg'' estimator for reducing lower order terms (specifically achieving the $n^{3/4}$ correction.\n* $\\mathcal{R}$ is an error term that controls the dependence on initial condition.\n\nThis improves the correction term in existing work from $n^{1/2+\\delta}$ to $n^{3/4}$.", "questions": "1) As stated: can the authors show that they can realize this n^{3/4} correction term in an experiment, (the setup should be such that I can reproduce it and, the 3/4 fit cleanly on a log-log plot)?  \n\n2) The optimality of the 3/4 is asserted multiple places, but it is nowhere displayed.  What construction demonstrates the non-improvability of the 3/4?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This improves an existing bound in various ways, both in the sense of\n(1) achieving moment bounds and\n(2) improving the rate of the correction term from $n^{1/2+\\delta}$ to $n^{3/4}$, which is claimed as optimal.\n\nIt does it using the method of the `Richardson-Romberg' extrapolation.  \n\nFor more common Polyak-Ruppert averaging, it also achieves the same rate provided the minimization is strongly convex.", "weaknesses": "1) This paper performs a detailed mathematical analysis of a correction term to the behavior of SGD on fixed problems.  It is hard to imagine important practical conclusions of this -- we are talking about improving subleading correction terms in an _asymptotic_ setting when the number of samples overwhelms all the important problem-dependent constants in a stochastic optimization context.  And yes, I use the term _asymptotic_ intentionally: the $n$ in this problem has to overwhelm constants which are _quite clearly_ not effective, and only once that happens will the subleading terms will have improved dependence.   The authors have _not_ attempted to demonstrate that there are settings where this theorem is experimentally realizable, nor honestly, do I think it would be reasonable to expect them to do so (if they can show their 3/4-power in an experiment, I'd retract this and happily ``eat crow'').\n\n2) The 3/4 power seems to be the essential point of this story.  It is asserted at multiple places that the 3/4 is optimal, but there is no clear construction.  There is a citation to another paper (Li et al), which considers a different algorithm.  If the example from that other paper works, it should be either displayed or precisely cited here (it was not possible to find it in a quick perusal).", "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)