Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
Authors: Sergey Samsonov
Eric Moulines
Qi-Man Shao
Zhuo-Song Zhang
Alexey Naumov
Venue: NeurIPS 2024 poster (2024)
Keywords: Linear Stochastic Approximation
Normal Approximation
Bootstrap Validity
Primary area: probabilistic_methods
TL;DR: We prove rates of normal approximation for the iterates of the linear stochastic approximation algorithm and non-asymptotic guarantees for constructing confidence intervals with multiplier bootstrap

Abstract: In this paper, we obtain the Berry–Esseen bound for multivariate normal approximation for the Polyak-Ruppert averaged iterates of the linear stochastic approximation (LSA) algorithm with decreasing step size. Moreover, we prove the non-asymptotic validity of the confidence intervals for parameter estimation with LSA based on multiplier bootstrap. This procedure updates the LSA estimate together with a set of randomly perturbed LSA estimates upon the arrival of subsequent observations. We illustrate our findings in the setting of temporal difference learning with linear function approximation.

Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
Sergey Samsonov HSE University svsamsonov @se.rr
Eric Moulines Ecole Polytechnique, MBUZAI
Qi-Man Shao
Department of Statistics and Data Science, Shenzhen International Center of Mathematics, Southern University of Science and Technology
Zhuo-Song Zhang
Alexey Naumov
Department of Statistics and Data Science, Shenzhen International Center Mathematics, Southern University of Science and Technology
HSE University,
Steklov Mathematical Institute of Russian Academy of Sciences
Abstract
In this paper, we obtain the Berry-Esseen bound for multivariate normal approxima- tion for the Polyak-Rupper averaged iterates of the linear stochastic approximation (LSA) algorithm with decreasing step size. Moreover, we prove the non-asymptotic validity of the confidence intervals for parameter estimation with LSS based on multiplier bootstrap. This procedure updates the LSA estimate together with set randomly perturbed LSA estimates upon the arrival of subsequent observations. We illustrate our findings in the setting of temporal difference learning with linear function approximation.
1 Introduction
Stochastic approximation (SA) methods are central component for solving various optimization
problems that arise in machine learning 33 266,, empirical risk minimization [72] and reinforcement
learning 42
67
There is vast number of contributions in the literature, which cover both
asymptotic 48 (33 and non-asymptotic 45 S 36) properties of the SA estimates. The primarily
important property among the asymptotic ones of the SA estimates is their asymptotic normality [53]. which is important due its role constructing (asymptotic) confidence intervals and hypothesis testing [7]]. However, a natural question of the rate of convergence in the appropriate central limit theorems (CLT) is not well addressed in literature even in the relatively simple setting of the linear stochastic approximation (LSA) 21
34
Alternatively, confidence sets for SA algorithms be constructed in non-asymptotic manner based
on concentration inequalities [4]. These bounds are often regarded as loose [60], yielding suboptimal performance of the statistical procedures based the latter estimates (28) In contrast, for statistical inference procedures based on independent and identically distributed (i.i.d.) observations, such as M-estimators 77I, there is machinery of non-parametric methods for constructing confidence sets with the bootstrap [19] (58). This approach is accompanied with theoretical guarantees, showing the non-asymptotic validity the bootstrap-basse confidence intervals for parameters linear regression [64] and statistical tests [2]. Extending theoretical guarantees to non-classical situation with online learning algorithms encounters serious problems, essentially related to the problem of obtaining rate of convergence in the corresponding CLTs. At the same time, many phenomena arising in the analysis of nonlinear SA algorithms already appear in the analysis of LSA problems.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The LSA procedure aims to find an approximate solution for the linear system A b with unique solution 6* based on a sequence of observations ((A( / Here A Z - Rdxd and b + _º are measurable functions and (Zx KEN is a sequence of noise variables taking values in some measurable space (Z, 2) with distribution и satisfying [=]] A and (x(((z)) We focus on the setting of independent and identically distributed (i.i.d.) observations {Zx JENN. With sequence of decreasing step sizes (ax kEE and the starting point 8g E R we consider the estimates (0n JNEN given by
b.
2n 1
0₂ = 0 ak (A()))())))))))) -b(z))))) 121, On =
0k 2 1.
(1)
k=
Here, we have fixed the size of the burn-in period (see, e.g., 16 to - n. Provided that large enough, the burn-in size affects only a constant factor the subsequent bounds. The sequence {0x JKEN corresponds to the standard LSA iterates, while {on corresponds to the Volyak-Ruppen (PR) averaged iterates [59 [53. It is known that 6,, is asymptotically normal with a minimax-optimal covariance matrix (see 53 and 23 for discussion). Specifically, under appropriate
technical conditions on the step sizes {at} } and noisy observations (Zx)))) it holds that
vū(0,, 0-) 4 NO Eoo)
where Eg is the asymptotic covariance matrix defined later in Section 3.1 There is long list of contributions to the -onasyypiooiic analysis of fg. particularly [43] and [16], which study moment and Bernstein-type concentration bounds for vni(0n f*). Unfortunately, such bounds do not imply Berry-Esseen type inequalities for vn(0, - 0*), that is, they do not allow us to control the quantity
Conv Pn
sup (EC)nv(Rd))
P(Vn(e, +*) E - E
(2)
where Conv(R refers to the set of convex sets in Rd. While the Berry-Esseen bounds are popular subject of study in probability theory, starting from the classical work (20), most results are obtained for sums of random variables martingale difference sequences [52 8 We can only mention few results for SA algorithms, see Section 2 for more details. This paper aims to provide the latter bounds for the specific setting of the LSA procedure. Our primary contribution is twofold:
We establish BerryEsseen bound for accuracy of normal approximation of the distribution of Polyak- averaged LSA iterates with a polynomially decreasing step size. Our results suggest that the best rate of normal approximation, in the sense of (2), is of order -1/4 up to logarithmic factors in n, where n denotes the number of samples. Interestingly, this rate is achieved with an aggressive step size, 0g = cp/ / kt. Our proof technique follows the Berry-Esseen bounds for nonlinear statistics provided in (63).
We provide non-asymptotic confidence bounds for the distribution of the PR-averaged statistic (n(O,, 0*) using the multiplier bootstrap procedure. In particular, our bounds imply that the quantiles of the exact distribution of vn(00, 6*) can be approximated at a rate of n 11/4, where is the number of samples used in the procedure, provided that n is sufficiently large (see A44 for exact conditions). To the best of our knowledge, this is the first non asymptotic bound on the accuracy of bootstrap approximation in SA algorithms. We apply the proposed methodology to the temporal difference learning (TD) algorithm for policy evaluation in reinforcement learning.
The rest of the paper is organized as follows. In Section 2 we provide a literature review on the non-asymptotic analysis of the LSA algorithm and bootstrap methods. Next, in Section 3 we analyze the convergence rate of Polyak-Ruppert averaged LSA iterates to the normal distribution. In Section 4 we discuss the multiplier bootstrap approach for LSA and establish bounds the accuracy of approximating the quantiles of the true distribution. Finally, we apply our findings to TD learning and present numerical illustrations in Section
Notations. For matrix A E Idd we denote by ||A|| its operator norm. For symmetric matrix Q Q= TT > 0, Q E Rdxd and x E Idd we define the corresponding norm ||اا| = v Qz, and define the respective matrix Q-norm of the matrix B e gddd by | = sup, || /Blll// For sequences a, and bn we write an S bn if there exist a constant e > 0 such that a, I cbn for >>000 O. For simplicity we state the main results of the paper up constant factors.
2

---

2
Related works
Among contributions to the analysis of the LSA algorithm, we should mention the papers [53 These works investigate the asymptotic properties of the LSA estimates (such as asymptotic normality and almost sure convergence) under i.i.d. and Markov noise. con-asymptotic results for the LSA and PR-au PR-averaged LSA estimates were obtained in [55] 47 7 35 44],
where MSE bounds were established, and in 4s T7 [6], which provided high probabboba error bounds. The latter results enable the construction of Bernstein-type confidence intervals for the error On, 0*. Unfortunately, the corresponding bounds typically depend on unknown problem properties of (T). related to the
design matrix A and the noise variables A (, :, b( Za. ). For this reason, applying these ervor bounds
in practice is complicated. Furthermore, concentration bounds for the LSA error [43 17 [6] do not imply convergence rates of the rescaled enror (O, 0*) to the normal distribution in Wasserstein or Kolmogorov distance. Non-asymptotic convergence rates were previously studied in (2] using the Stein method, but the resulting rate corresponds to a smoothed Wasserstein distance. Recent work [65 investigates convergence rates to the normal distribution in Wasserstein distance for LSA with Markovian observations. Both papers yield bounds that are less tight with respect to their dependence on trajectory length n than those presented in the present work, see a detailed comparison after
Theorem 2
popular method for constructing confidence intervals the context of parametric estimation is based on the bootstrap approach (I19). Its analysis has attracted many contributions, in particular series of papers [12] and [13] that validate a bootstrap procedure for a test based on the maximum of a large number of statistics. Their study shows a close relationship between bootstrap validity results, Gaussian comparison and anticoncentration bounds for rectangular sets. The papers [64] and [77 investigate the applicability of likelihood based statisties for finite samples and large parameter dimensions under possible m misspecification. The important step in proving bootstrap validity again based Gaussian comparison and anticoncentration bounds, but now for spherical sets. The
bootstrap procedure for spectral projectors of covariance matrices is discussed in [46) and [31] The
authors follow the same steps prove the validity of the bootstrap.
Extending the classical bootstrap approach to online learning algorithms is a challenge. For example, the iterates {0k JEN determined by (1) are not necessarily stored in memory, which makes the classical bootstrap inapplicable. This problem can be solved by performing randomly perturbed updates of the online procedure, as proposed in 22 for the iterates of the Stochastic Gradient Descent (SGD) algorithm. The authors in [56] used the same procedure for the case of Markov noise and policy evaluation algorithms in reinforcement learning, but in both papers the authors only consider the asymptotic validity. In our paper we use the same multiplier bootstrap approach (see Section 4 but we provide an explicit error bound for the bootstrap approximation of the distribution of the statistics vn -
or various estimates of the asymptotic covariance matrix [73 to construct the confidence intervals for 0*. The latter approach can be based on the plug-in estimators (39), batch mean estimators [1]] or in combination with the multiplier bootstrap approach [74]. However, the theoretical guarantees for mentioned methods remain purely asymptotic.
In addition to the bootstrap approach, one can also use the pivotal statistics 33 40
3 Accuracy of normal approximation for LSA
We first study the rate of normal approximation for the tail-averaged LSA procedure. When there is no risk of ambiguity, we use simply the notations A₁ = A AZxx and bą = b(Z)). Starting from the definition I we get with elementary transformations that
0 0" = (I- 0r Ax) --0) 8t) - CAEK
where we have set E7 = =(x) with
e(=) = - b(=), ( - A, 6(2)= b())
Here the random variable e( (Zx) can be viewed a noise, measured at the optimal point 0*. We now assume the following technical conditions:
11. Sequence (7x YENN is a sequence of i.i.d. random variables defined on a probability space
(R, F, P) with distribution
3

---

A2. Jz (z))dT(()) = A and Jz b(2)dT())2 b, with the matrix - A being Hurwitz. Moreover, || = suPsez ||=()]] < toc, and the mapping + A(2) is bounded, that is,
C
sup [A V sup [=)]l 80.
(4)
=EZ
Moreover, for the noise covariance matrix
Eg = (2=)
(5)
holds that its smallest eigenvalue is bounded away from 0, that is,
Amin = Amin [Ee) > 0.
(6)
is possible to change 4 to the moment-type bound as was previously considered in 43 and [16., see the detailed discussion after Theorem The fact that the matrix - A is Hurwitz implies that the linear system AO has a unique solution 0*, Moreover, this fact sufficient to show that the matrix I- - a is a contraction in appropriate matrix Q-norm for small enough >> O. Precisely, the following result holds:
Proposition 1. Let A be a Hurwitz matrix. Then for any PT > I, there exists a unique matrix
Q = Q > I. satisfying the Lyapunov equation A AQQ+ QA P. Moreover setting
a
Amin 2|1
and
O
Anqll
Amin A 1Q11
Amia
where KQ Amax(Q)) Amin (Q), it holds for any a E [0, aooo] that oa S 1/2, and
|| |1 al3 < aa
(8)
The proof of Proposition[] iss provided in Appendix D.I Note that it is possible to set P = I as in [8]. yet it is possible that other choices of P could be more beneficial for particular applications. Now consider an assumption on the step sizes 04 and number of observations n:
A3. The step sizes {aw has a form Og = co/k", where y E [1/2; 1) and co E (0; (0 A a A
- 7)}. Moreover, assume that 2 d, and
Pang C²
ify 1/2, 8-11~1
(L+Hog logn a(1 2222) 2--7
(2/2)
200
log
a(29
eco (1-(2
The main aim of lower bounding is ensure that the number of observations is large enough in order that the LSA error related to the choice initial condition 0g- - 0* becomes small.
3.1 Central limit theorem for Polyak-Rupperi averaged LSA iterates.
It is known that the assumptions A guarantee that the CLT applies the iterates of 0,, namely,
vn(O,, 0*) 4 NO, Exe),
(10)
where the asymptotic covariance matrix E. has a form
Σx ===A-'AAA-
(11)
and Σg is defined in (5). This result can be found for example in 53 and 23 We are interested in the Berry-Esseen Esseen type bound for the rate of convergence [T0), that we aim bound p Coon defined in (2) w.r.t. the available sample size n. We control Pn based on randomized multivariate concentration inequality. Below we briefly state its setting and required definitions. Let XI...., .x, be independent random variables taking values in X and = T(,,,..,,,. be a general d-dimensional statistics such that = W + D, where
Couv using method from 63
n
W Σ
Ee
D:= D(X
X,) = W,
(12)

---

& = (Xe) and he X' R is a Borel measurable function. Here the statistics D can be non-linear and is treated as an error term, which is "small" compared W in an appropriate sense. Assume that
El{e] = 0 and Et= E = la- Let Y Y, = >i= = [ | Then, with ry NO0 Ta),
sup (R))
P(( E -(( E A)I S 259d 22 W DII
Σ t=1
[]] (13)
where D(() = D 11....,x-11,, , X2, Xe+1...... x,) and X is an independent copy of X₁. This
result is due 63 Theorem 2.1]. One modify the bound (13) for the setting when
E = > 0. This result due to [63 Corollary 2.3]. Following the construction we set T = (nA 0*) and consider it as a nonlinear statistic of i.i.d. random variables ...... Zen, which drive the LSA dynamics (T). We can exactly represent T as sum of linear (W)
and non-linear parts (D), where
2n
1 On 0+
1
Pnn
0
W
ck+1.
D =
(Ax A)(0 07))
vn
an
Vni
Q2n
k=n+1
2n
(0=-1 - 0²)
O
k=n+1
The proof of this result can be bound in Proposition To obtain bound for the approximation
accuracy in (2) using the bound (13). we need to upper bound ()) )1 and Eljl D-
D(OI] []] The first result below provides a second moment bound on D:
Theorem 1. Assume A
A2 and A3
Then we obtain the following error bound:
Vooleello
Cu CA
1/2 [Z)... Zzn) [| S
Vaco
(21-2)/2
V1 -217/2
Cpan 1-y
+ VRQ A exp
1100- -
2(1 -
where S stands for inequality up to an absolute constant, and A A1 CA, is polynomial function defined in Appendix
A.3 eq. (29).
The proof of Theorem D is provided in Appendix
A.3 Now it remains to upper bound the term
E[[[D - D] which is done in Appendix B.1 using the synchronous coupling methods [10] Combining these bounds, we obtain the following theorem:
Theorem 2. Assume A7 A2 and A3
Then the following bound holds:
Pn
Conv
d//2||=11a
X 2/2 /n
Amin
1
(11-21/2
C1
n2//
C2
Amin
A2
expo
2(1 2(1-7) 110 1 (14)
Cuan!
where A2 Az(n, a, CA. Er, cu) is a polynomial function defined in (35). and constants C1, C2.
depending upon a, CA. RQ: Er, Co, are defined in Appendix B eq.
(36)
The proof of Theorem 2 is provided in Appendix B Note that the assumption A requires that a e(z)) almost sure bounded. is strong assumption, but can be partially relaxed. Following the stability of matrix products technique, used in [17 Proposition 3], it is possible to consider the setting when the random variable A (Zi)l has only finite number of moments. In particular, we expect that assuming finite third moment of || (Z1)) ]| and [|e(Z]) is sufficient to obtain counterpart to Theorem I However, this generalization requires non- son-trivial technical work on generalizing the stability of matrix products result (see Corollary in Appendix
Note that the bound of Theorem 2 predicts the optimal error of normal approximation for Polyak- Ruppert averaged estimates of order n 1/4 which achieved with the aggressive step size ag /o, that is, when setting 7 1/2 in (14. In this case we obtain the optimized bound
C3
d lell
A exp( -uaa
Couv Pn
1100 6*1|
(15)
Amin 1/4
A 3/22
Amin
where C3 Cz(a, CA, KQ, TF //=/)o)) is provided in (36)
5

---

Discussion. Our proof technique of Theorem reveals an interesting feature: fastest rate of convergence in the convex distance poonn corresponds to the learning rate schedule that admits the fastest decay of the second-order term in the MSE bound for remainder statistics D (see Theorem I Results similar to the one of Theorem 2 have been recently obtained in the literature in [G5] and learning (see
2 The author in [65] considers the LSA problem specified to the temporal-differenn
Section 5) with Markov noise and obtains convergence rate in Wasserstein distance of order n 1/4, which corresponds to the "optimal" step size schedule 0r = co/1.3/4 Using the bound of [49] eq. (3) (see also section 2 in [57]). this result yield a suboptimal bound of order n 11/8 for the convex distance Pm Couuy Such an upper bound may be loose for some classes of distributions, but it is not clear if in particular setting of LSA the bound of [65] could imply scaling of order n -1/4 for Pr (oony At the same time, in case of XI,..., Xn forming a Markov chain in (12 there is no available counterpart of the bound (3). Generalizing (13) is interesting research direction that would allow to obtain a counterpart of Theorem 2 in case of Markovian dynamics. Similarly, the result of [2] holds for much stronger metrics, which controls the convergence of moments of twice differentiable functions. We provide additional details about connections between this metric and oo in Appendix B.2 At the same time, the authors in [2 cover the non-linear setting of PR-averaged iterates of stochastic gradient descent algorithm under strong convexity.
The leading (with respect to n) terms of the bound from Theorem 7 have an implicit dependence on the problem dimension d due to the presence of Xmin- Yet the result of Theorem I can be improved in a sense of dependence in dimension if one is interested not in the rates of convergence for vn(On - 0)), but in the projected iterated /nll (0n -0)) for some II E RRxx m S. d. If this the case, one may apply (13) for the class Convm m -Conv(RR)) of convex sets in R and obtain,
Remark 1.
setting step size ag co/ s//kk Vk, and ((I)
-I1 that
C4
m 11/311 + A2e-
Conv Pn
+
1100
1*
1/4in
2 vn
Amin
and the constant C. = CC(la, CA, KQ, Tr I!!! .|1sllo)) is provided in (36).
Remark 2. Results similar to Theorem [ can be obtained not only for the Polyak- Ruppert averaged
estimator On, but also for the last iterate On In particular, is known (see e.g. (231), that the last iterate error On - O* is also asymptotically normal:
0" NO, Einst)
where the covariance matrix Etast is different from E.s. In such a case Eistt can be found as solution to appropriate Lyapumov equation, see 123]. Then, we expect that it is possible to use the perturbation eetioosiinnanni approach from [ together with randomized concentration inequalities [63] (see 13), in order to obtain the Berry-Fsseen bound
(P(0 E BB) - -P last E B) z Van
sup (ECov(()()
We leave the detailed derivation for future work.
4 Multiplier bootstrap for LSA
In order to perform statistical inference with the Ruppakt estimator 9n, we propose an online bootstrap resampling procedure, which recursively updates the LSA estimate as well as a large number of randomly perturbed LSA estimates, upon the arrival of each data point. The suggested procedure follows the one outlined in (22]. It has the following advantages: it does not rely on the asymptotic distribution of the error Vn((,, - 0*), does not require to know the moments of Vn((O, 0*) or its asymptotic covariance matrix Ex.. and does not involve any data splitting.
We state the suggested procedure as follows. Let W = [We)isese) be a set of i.i.d. random variables, independent of 2 = {Zehieesms with E[W1] = 1 and Var[Wi] = 1. We write, respectively. طوا = P(-| 2 and IE = E(- for the corresponding conditional probability and expectation. In parallel with procedure ( that generates {0 and 0n,, we generate M independent samples (wh..... w.n). ). < l S M distributed W and recursively update M randomly perturbed LSA estimates, that is.
ab. k-1 Wm (A (Zx b- b b(2))). k n 1, @b. = On
(16)
@b.l_ 1s = n -1 2n gb.t n n21 12.
2k=n

---

We use a short notation 8% for 0%. The key idea of the procedure (6 is that the "Bootstrap Bootstrap-world" world" distribution (that is, the one conditional on g²n) of the perturbed samples vn 0n) ) is close to
the distribution of the quantity of interest, that is, vn(O,, 0*). Precisely, the main result of this section will show that the quantity
sup Conyv(RR))
(V 0n) E))B B) PP(T - 0*) B)I
(17)
is small. Although analytic expression for ( (vnil0 0n) E B) is not available. one can approximate it from numerical simulations according to (T6) by generating sufficiently large number M of perturbed trajectories. Standard arguments, see e.g. [62] Section 5.1] suggest that the accuracy of Monte-Carlo approximation is of order M-1/2 To analyze the suggested procedure, we shall impose an additional assumption on the trajectory length n.
A4, Assumption
A3 holds with 7 = 1/2, and co S 11((CA kge). Moreover, setting
h(2) = [(
(152-11
4CA 1/2
2
(1 2 (2n4))²
(18)
[V2-1)a
holds that
co and / are
co(1vC2)
coa C2 V V_
(19)
h(m)
((2211)
Tog
a
ara
Moreover, we assume that for Amin defined in 66 it holds that
|E logn + 8(] + 12 log
Amin 2 8||E|1
(20)
19 simply states that v (n)) is sufficiently large, since h(n) scales as log" n. We discuss the assumption A4 in more details in the proof scheme. Now we formulate the main result of this section. We analyze only the setting of polynomially decaying step size with
Note that the new bound
7 = 1/2, since decay rate of (17) essentially depends on the approximation rate of Theorem 2 with the fastest rate achieved when = 1/2. For other learning rates the decay rate of right-hand side in Theorem 3 will be slower. For simplicity, we do not trace the dependence of the bound below on the parameter Co.
Theorem 3. Assume 77
A2
A3 with = 1/2, and A4 Then with IP -probability at least 1 - 6/n n it
holds that
C V1)(1 + 11e112 log
IPa (V - -n)) B) 10--PCC P(Vin(On - 0*) B)I
sup (EConv(RA))
5/2 Amiinte//4
Vd
||
(1 + 1| /min)) log Venin
Voga
A Age- 2ae/22o2)
1100
8*
Vn
3/2 auin
/n
Amiin
where Ag Aa(n, a, CA, I[elllo) ) is polynomial function defined in Appendix
C
eq. (46)
The proof of Theorem 3 is based on the Gaussian approximation performed both in the "real" world and bootstrap world together with an appropriate Gaussian comparison inequality. The main steps of the proof are illustrated by the following scheme:
Real world:
Vn 0*)
Gaussian approximation. Th.
E~ N0 Eee)
Gaussian comparison, Theorem
Bootstrap world: VnA (7)- - 0m) Gaussian approx. in Bootstrap world. Th. 4
In the above scheme we have denoted by Σe = n - TEeT the sample covariance matrix approximating Σ.. Gaussian approximation for the true distribution of AnA (B,, 8*) follows from Theorem 2 Proof Gaussian approximation in the Bootstrap world Theorem 4 also based on the inequality (13), but is more complicated and involves the expansion analysis of the LSS error from [.] This technique allows to separate the LSA error into different scales with respect to the step sizes {ax). see Appendix C.4 for details. However, this technique requires to impose additional
7

---

assumption Ag eq. (9). Proof of the Gaussian comparison part of Theorem 5 is based on Pinsker's s inequality and matrix Bernstein inequality, The latter result requires that n large enough to ensure that minimal eigenvalue of X is close to Amin- justifying the assumption A4 eq. (20). Detailed proof if provided Appendix
Discussion. We emphasize that the Gaussian approximation result of Theorem 2 (with Bootstrap world generalization in Theorem 4 a key result to prove the above bootstrap validity. This argument was missing in the earlier works studying confidence intervals for stochastic optimization algorithms 7 14,, where the authors considered procedures to estimate Eoo in (II). They combine non- asymptotic bounds on the accuracy of recovering Σx with only asymptotic validity of the resulting confidence intervals. We expect that our proof technique for Theorem 2 can used provide similar non-asymptotic validity results for outlined approaches for constructing confidence intervals based on the estimation of the asymptotic covariance matrix.
Corollary 1. (Set of Euclidean balls or ellipsoids) Suppose that we are interested in estimating quantile of a given order a E (0, 1) and some matrix B E Raxd, that is, the quantity
La = infft > O: P[Vni| 0') 2 a).
We define its counterpart in the Bootstrap world, t2g as
t. = inf 0: P B(0: 0.)1 2 t) sa).
Note that th is defines with respect the bootstrap measure, therefore, it depends on the data z This bootstrap critical value 12 is applied in the Bootstrap world to build the confidence set
E(a) - 10 E Rd V - 0,) S (2)
Theorem 3 justiftees this construction and evaluate the coverage probability of the true value 0* by this set. It states that
P(O" & E(())) -0)1 >2))>1)))000 12)
with the error of order nndern-1/4 in the right-hand side. Although an analytic expression for th is not available, one can approximate it by generating large number M of independent samples of Wn and computing from them the empirical distribution function of /nl| - O,)] following (16).
Remark 3. natural question that arises after Theorem 3 is whether it is possible to prove similar bounds for the iterates of first-order stochastic optimization algorithms. There are several MSE bounds for corresponding algorithums with explicit dependence on the step size ay; see, see,for example, 145 Sy. Therefore, we expect that it is possible to obtain a counterpart to Theorem [ At the same time, for general first-order stochastic optimization algorithms, unlike LSA, there are no counterparts to the precise error expansions of [T]. Thus, proving the counterpart of T'hhormm 3 in this setting is more challenging. Similarly, we emphasize that generalizations of the procedure (16) to cases where [k keN are dependent, for example, form Markov chain, are complicated. The approach of (63)
is not directly applicable in this setting, and appropriate generalization of 13) is a separate and challenging research direction.
5
Applications to the TD learning and numerical results
We illustrate findings for the setting of temporal difference (TD) learning algorithm (66 67 for policy evaluation in RL. asmmtsympt error bounds for this algorithm attracted lot of contributions
[6 30 51 38). At the same time, confidence intervals for TD were studied in [22 56 only in terms of their asymptotic validity. In the TD algorithm we consider a discounted MDP (Markov Decision Process) given by tuple AS, Pr,, 7). Here S and A stand for state and action spaces, and 7 E (0, 1) is a discount factor. Assume that S is a complete metric space with metric ds and Borel o-lagebra B(S). P stands for the transition kernel P(B]s, a). which determines the probability of moving from state s to a set B E B(S) when action a is performed. Reward function r: A [0, 1] is assumed to be deterministic. Policy π(: (-(ss is the distribution over action space A corresponding to agent's 's action preferences in state E S. We aim to estimate value function
43
cc
(TT(s)
Ar (sk. ax) 0s)
k=
8

---

where ag ~ x(-ss)) and 84+1 ~ P(-|sk: ax) for any & E N. Define the transition kernel under x, (B(()s) - SA P(B]s, a)a(da)s),
(21)
which corresponds to the 1-step transition probability from state s to a set B E B(S). The state space S here be arbitrary. It is a common option to consider the linear function approximation for (s),,, defined for s E S, 0 E R", and a feature mapping pp: S R as (s) = yp (s)6. Here is the dimension of feature space. Our goal is find parameter 0* which is defined as a unique solution to the projected Bellman equation, see [70]. We denote by the invariant distribution over
the state space S induced by P* (-Is) in 21 We define the design matrix Eup as
i = Ey(p(s))((s) T] gdxd
(22)
Consider the following assumptions on the generative mechanism and on the feature mapping (p()): TD1. Tuples (s, a, s') are generated with s ~ p. a T--ss), s' P(-ss.).. TD Matrix En is non-degenerate with the minimal eigenvalue Amin (2i) > 0. Moreover, the feature mapping (+)) satisfies supses [|(((s)] S
In the setting of linear function approximation the estimation of V (*)(s) reduces to estimating 0* E Rdd, which can done via the LSA procedure. Here, the k-th step randomness given by the tuple Z (sk, ag. 5%) ). Then, the corresponding LSA update can be written as
== = - (A,
(23)
where A& and by are given, respectively, by
A ((s)) - (
by = ((sx)r(ss,,
We provide the expressions for the corresponding system matrix A E[Aa] and the right-hand
side b in Appendix E. We verify that assumption holds and, furthermore, we provide a tighter counterpart to the result of Proposition [ This result closely follows [51] and [61].
Proposition Lei {0]ken be a sequence of TD updates generated by 23 under TD and TD2 Then this update scheme satisfies assumplion A2 with
CA = 2(1 + 7), || = 2(1 + (1100 +1),
moreover, one can check that || - 2 - 1 aa with
(1 7mm (Ei))
(xx0 = (1- +
that is, Proposition hollss with Q II
Proof of Proposition is provided in Appendix E Since all the assumptions in AZ are fulfilled, we can verify tightness of the bound Theorem for different learning rate schedules ag in (23).
Numerical results. Efficiency of the multiplier bootstrap approach (16) to the problems of con-
structing confidence sets in online algorithms has been demonstrated in the works 22 and [56] We aim to illustrate the tightness of our bounds for normal approximation outlined in Theorem in the setting of TD learning with linear function approximation. To this end, we consider the classical Garnet problem (3). in the simplified version proposed by [25]. This problem is characterized by the number of states N₁. number of actions a, and branching factor 6 (i.c. the number of neighbors of each state in the MDP). We set these values to N, = 10, a = 2 and b = 3, and aim to evaluate the value function of the randomly generated policy x (-Is). Details on the way the policy is set can be found in Appendix [F] We consider the problem of policy evaluation in this MDP using the TD learning algorithm with identity feature mapping, that is, x(s) = e, (that is, s-th coordinate vector) for E {1, .1,..., N.). We run the procedure (23 with the learning rates ag co/ k2 and different powers 7 E {0.5, 0.65, 0.7). For each of the experiments we aim to estimate the supremum
A supses @V 0- x) P( 7/l x))
(24)
7 ~ .V(O, IN.), and show that this supremum scales as n 1/4 when = 1/2 and admits slower
decay for other powers of y. We approximate true probability P(]]: 1/2 ml < xx) by the corresponding empirical probabilities based on sample of size M > n. Second, for n E (1600.... 1638400), where next sample size is twice larger than the previous one, we generate N = 6553600 trajectories of TD algorithm and approximate the distribution of Vn|l0, - I*1l based on the corresponding empirical distribution. We report our results in Figure [ showing that the smallest values of A,, correspond to the step size schedule 7 1/2, moreover, the decay rate 1/4 seems to be tight, otherwise one should expect further decay of 1/44 Additional simulations are provided in Appendix

---

7-
0,8
D. Y 0.50
-.... D.. = 0.65
0.70
0.6
10"
0.4
3-
PR error, y = 0.50
0.2
10a1
n n2 0.50
2-
PR error, 0.65
n nm Y 0.65
PR error, y 0.70
n D.. Y 0.70
0.0
104
105
10a
10a
10a
104
105
10
(a)
(b)
(c)
Figure 1: Subfigure (a): Rescaled enror vnl0a, 0* averaged over N independent TD trajectories for different trajectory lengths n. Subfigure (b): approximate quantity A, from (4 for different
powers y and n. Subfigure (c): An. rescaled by a factor 1/4, predicted by Theorem
6 Conclusion
In this paper, we have established, to the best of our knowledge, the first fully non-asymptotic confidence bounds for parameter estimation in the LSA algorithm using the multiplier bootstrap. This result based on a novel Berry-Essedd bound for the is of independent interest. Our paper suggests several interesting directions for further research. First, our Berry-Esseen bounds are obtained using the randomized concentration inequality [63], and would be valuable generalize this approach to the setting of Markov chains. Second, it natural to extend our results to the first-order gradient methods, both for stochastic optimization and variational inequalities. Third, it becomes possible prove the fully non-asymptotic validity of confidence intervals obtained with plug-in techniques or other estimators of the asymptotic covariance matrix of On. These could then be compared with the multiplier bootstrap confidence intervals in terms of their dependence on problem dimension d and other instance-dependen quantities.
averaged LSA iterates, which
Acknowledgement
The work of S. Samsonov and A. Naumov was prepared within the framework of the HSE University Basic Research Program. The work of E. Moulines has been partly funded by the European Union DIC-222-SSY--OCEAN-IOOUO 601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The work of Q.-M. Shao is partially supported by National Nature Science Foundation of China NSFC 12031005 and Shenzhen Outstanding Talents Training Fund, China. The work of 7.-S. Zhang is partially supported National Nature Science Foundation of China NSFC 12301 183 and National Nature Science Found for Excellent Young Scientists Fund. This research supported in part through computational resources of HPC facilities HSE University (33]
10

---

References
[1] Rafik Aguech, Eric Moulines, and Pierre Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization, 39(3):872-899 2000.
[2] Andreas Anastasiou, Krishnakumar Balasubramanian, and Murat A. Erdogdu. Normal ap- proximation for stochastic gradient descent via non-asymptotic rates of martingale CLTT In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Shirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 115-137.
PMLR, 25-28 Jun 2019.
[3] TW Archibald, KIM McKinnon, and LC Thomas. On the generation of markov decision processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
[4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
[5] Bach and Moulines. Non-strongly-convex smooth stochastic approximation with con- vergence rate o(1nn). In J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[6] A. Benveniste, M. Métivier, and P. Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[7] Bhandari, D. Russo, and R. Singal. finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pages 1691-1692, 2018.
[8] E. Bolthausen. Exact Convergence Rates in Some Martingale Central Limit Theorems. The Annals of Probability, 10(3):672 6888, 1982.
[9] Vivek S Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008
[10] Nicolas Brosse, Alain Durmus, and Eric Moulines. The promises and pitfalls of stochastic gradient langevin dynamics. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[11] Xi Chen, Jason D. Lee, Xin T. Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics, 48(1):251 - 273, 2020.
[12] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. Ann. Statist., 41(6):2786-22) 2013.
[13] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Central limit theorems and bootstrap in high dimensions. Ann. Probab., 45(4):2309-255 2352, 2017.
[14] G. Dalal, Balazs Szorenyi, and G. Thoppe. A tale of two-timescale reinforcement learning with the tightest finite-time bound. arXiv preprint 191.00171 2019.
[15] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-115 2012.
[16) Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Finite-time high- probability bounds for Polyak-Rupper averaged iterates of linear stochastic approximation. Mathematics of Operations Research, 2024.
[17] Alain Durmus, Eric Moulines. Alexey Naumov, Sergey Samsonov, Kevin Scaman, and Hoi-To Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. In M. Ranzato, A. Beygelzimer, K. Nguyen, P. S. Liang, J. W. Vaughan, and Y. Dauphin, editors, Advances Neural Information Processing Systems, volume 34, pages 30063-30074. Curran Associates, Inc., 2021.

---

[18] Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, and Hoi-To Wai. On the stability of random matrix product with markovian noise: Application linear stochastic approximation and td learning. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theary, volume 134 of Proceedings of Machine Learning Research, pages 1711-1752. PMLR, 15-19 Aug 2021.
[19] Bradley Efron. Bootstrap methods: another look at the jackknife. In Breakthroughs in statistics: Methodology and distribution, pages 569-593, Springer. 1992.
[20] Carl-Gustav Esseen. Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law. Acta Mathematica, 77(none): 125, 1945.
[21] E. Eweda and O. Macchi. Quadratic mean and almost-sure convergence of unbounded stochastic approximation algorithms with correlated observations. Ann. Inst. H. Poincaré Sect. (N.S.), 19(3):235-255, 1983.
[22] Yixin Fang, Jinfeng Xu, and Lei Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research, 19(78):1-21, 2018.
[23] G. Fort. Central limit theorems for stochastic approximation with controlled Markov chain dynamics. ESAIM: PS, 19:60-80, 2015.
[24] Robert E Gaunt and Siqi Li. Bounding Kolmogorov distances through Wasserstein and related integral probability metrics. Journal of Mathematical Analysis and Applications, (22(1)) 2023.
[25] Matthieu Geist, Bruno Scherrer, et al. Off-policy learning with eligibility traces: a survey. Mach. Learn. Res., 15(1):289-333 2014.
[26] Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cambridge, MA, USA, 2016. http::/www. deooeeanaeaa.. org
[27] Friedrich Götze, Alexey Naumov, Vladimir Spokoiny, and Vladimir Ulyanov. Large ball probabilities, Gaussian comparison and anti-concentration. Bernoulli, 25(4A):2538-2566 25633, 2019.
[28] Botao Hao. Yasin Abbasi Yadkori, Zheng Wen, and Guang Cheng. Bootstrapping upper confidence bound. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[29] De Huang, Jonathan Niles Joel A Tropp, and Rachel Ward. Matrix concentration for products. Foundations of Computational Mathematics, pages 1-33, 2021.
[30] Dongyan Huo, Yudong Chen, and Qiaomin Xie. Bias and extrapolation in markovian linear stochastic approximation with constant stepsizes. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 81-82, 2023.
[31] Moritz Jirak and Martin Wahl. Quantitative limit theorems and bootstrap approximations for empirical spectral projectors. Probability Theory and Related Fields, (90(1):119-17) 2024.
[32] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14X2. 2014.
[33] PS Kostenetskiy, RA Chulkevich, and VI Kozyrev. Hpc resources of the higher school of economics. In Journal of Physics: Conference Series, volume 1740, page 012050. IOP Publishing, 2021.
[34] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
[35] C. Lakshminarayanan and C. Szepesvari. Linear stochastic approximation: How far does con- stant step-size and iterate averaging go? International Conference on Artificial Intelligence and Statistics, pages 1347-1355, 2018.
12

---

[36] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1-2):365-397) 2012.
[37] Sokbae Lee, Yuan Liao, Myung Hwan Seo, and Youngki Shin. Fast inference for quantile regression with tens of millions of observations. Journal of Econometrics, page 105673, 2024.
[38] Gen Li, Weichen Wu, Yuejie Chi, Cong Ma, Alessandro Rinaldo, and Yuting Wei. High- probability sample complexities for policy evaluation with linear function approximation. IEEE Transactions on Information Theory. 70(8):5969-5999 2024.
[39] Xiang Li, Jiadong Liang, Xiangyu Chang, and Zhihua Zhang. Statistical estimation and online inference via local sgd. In Po-Ling Loh and Maxim Raginsky, editors. Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1613-1661. PMLR, 02-05 Jul 2022.
[40] Xiang Li, Jiadong Liang, and Zhihua Zhang. Online statistical inference for nonlinear stochastic approximation with Markovian data, arXiv preprint urXiv:2302.07690 2023.
[41] Xiang Li, Wenhao Yang. Jiadong Liang. Zhihua Zhang, and Michael I Jordan. A statistical analysis of Polyak-Ruppert averaged Q-learning. In International Conference on Artificial Intelligence and Statistics, pages 2207-2261. PMLR, 2023.
[42] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529-333 2015.
[43] Wenlong Mou, Chris Junehi Li, Martin J Wainwright, Peter L Bartlett, and Michael Jor- dan. On linear stochastic approximation: Fine-graine Polyak-Ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947-2997. PMLR, 2020.
[44] Wenlong Mou, Ashwin Pananjady, Martin J Wainwright, and Peter L. Bartlett. Optimal and instance-dependent guarantees for markovian linear stochastic approximation. Mathematical Statistics and Learning, 7(1):41-153, 2024.
[45] Eric Moulines and Francis Bach. -on-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances in neural information processing systems, 24:451-459, 2011.
[46] Alexey Naumov, Vladimir Spokoiny, and Vladimir Ulyanov. Bootstrap confidence sets for spectral projectors of sample covariance. Probab. Theory Related Fields, 1790-1):109111112, 2019.
[47] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochas- tic approximation approach to stochastic programming. SIAM Journal optimization, 1944)1577-1109, 2009.
[48] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[49] Ivan Nourdin, Giovanni Peccati, and Xiaochuan Yang. Multivariate normal approximation on the wiener space: new bounds in the convex distance. Journal Theoretical Probubility, 55(3):2020-2037, 2022.
[50] A. Osekowski. Sharp Martingale and Semimartingale Inequalities. Monografie Matematyczne 72. Birkhäuser Basel, edition, 2012.
[51] Gandharv Patil, LA Prashanth, Dheeraj Nagaraj, and Doina Precup. Finite time analysis of tem- poral difference learning with linear function approximation: Tail averaging and regularisation. In International Conference on Artificial Intelligence and Statistics, pages 5438-5445 PMLR,
2023.
13

---

[52] V. Petrov. Sums of Independent Random Variables. Ergebnisse der Mathematik und ihrer Grenzgebiete. 2. Folge. Springer Berlin Heidelberg, 1975.
[53] Boris T Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal control and optimization, 30(4):838-88)) 855, 1992.
[54] A. S. Poznyak. Advanced Mathematical Tools for Automatic Control Engineers: Deterministic Techniques. Elsevier, Oxford, 2008.
[55] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571-1578, 2012.
[56] Pratik Ramprasad, Yuantong Li, Zhuoran Yang, Zhaoran Wang, Will Wei Sun, and Guang Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. J. Amer. Statist. Assoc., 1186544) 2023.
[57] Nathan Ross. Fundamentals of Stein's method. Probability Surveys, 8(none):210- - 293, 2011.
[58] Donald B Rubin. The bayesian bootstrap. The annals of statistics, pages 130-134, 1981.
[59] David Ruppert. Efficient estimations from slowly convergent robbins-monro process. Techni- cal report, Cornell University Operations Research and Industrial Engincering, 1988.
[60] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics 2014.
of Operations Research,
[61] Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, and Eric Moulines. Improved High- Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability, In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4511-4547, PMLR, 30 Jun-03 Jul 2024.
[62] Jun Shao. Mathematical statistics. Springer Science & Business Media, 2003.
[63] Qi-Man Shao and Zhuo-Song Zhang. Berry-Esseen bounds for multivariate nonlinear statis- tics with applications to M-estimators and stochastic gradient descent algorithms. Bernoulli, 1548-115488 2022.
[64] Vladimir Spokoiny and Mayya Zhilova. Bootstrap confidence sets under model misspecification. The Annals of Statistics, 43(6):2653 26755, 2015.
[65] Srikant. Rates of convergence in the central limit theorem for markov chains, with application to TD learming. arXiv preprint arXiv:2401.15711 2024.
[66] R. S Sutton. Learning to predict by the methods of temporal differences. Machine learning. 3(1):9 44, 1988.
[67] R. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[68] Joel A. Tropp. Freedman's incquality for matrix martingales. Electron. Commun. Probab., 16:262-270, 2011.
[69] Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trendy@ in Machine Learning, 8(1-2):1-230, 2015.
[70] N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5)6674-690, May 1997.
[71] A. W. Van Der Vaart and J. A. Wellner. Weak convergence and empirical processes. Springer Series in Statisties, 1996.
[72] Vladimir Vapnik, The nature of statistical learning theory. Springer science business media, 2013.
14

---

[73] Xi Chen Wanrong Zhu and Wei Biao Wu. Online Covariance Matrix Estimation in Stochastic Gradient Descent. Journal of the American Statistical Association, 118(541):393-400 404, 2023.
[74] Yanjie Zhong, Todd Kuffner, and Soumendra Lahiri. Online Bootstrap Inference with Noncon- vex Stochastic Gradient Descent Estimator. arXiv preprint arXiv:2306.02205 2023.
[75] Vladimir Mikhailovich Zolotarev. Probability metrics. Theory of Probability & Its Applications, 28(2):278-300 1984.
15

---

A Proofs for accuracy of normal approximation
A.1 Expansion of the error of LSA equipped with the Polyak-Ruppert averaging Proposition The following expansion holds:
2n
1
0,
8"
1
vnA (O, - -07) =-
Vn
On
0g2n
kma+11
11
W
2m
2n
(0
(A
0*)
(0k-1 8*)
(25)
vn
ax
ak-1
k=n+1
R=n+1
Da
D4
Proof. We use the recurrence 3 and rewrite it as
0k - 0" = ax 8¹) - az (A+ - A) - 0*) - Cx.E
The previous equation implies, after algebraic manipulation and division by Ork, that
0x 0"
0x
0 (A A)(0k11 - 0*) Ek
A(Ok11 0*)
O
a
Taking average for is from n + 2n and multiplying by vn, we obtain (25
A.2 Bounding the error of the LSA algorithm last iterate
We begin with of technical lemma on the behavior the last iterate O₂ of the LSA procedure given in ① We aim to show that [ - 0" [P]] scales as Var, provided that is large enough. This result is classical and appears in number of papers, e.g. [7, 43 17 We provide the proof here completeness. Our analysis of the bootstrap procedure and the last iterate error of LSA procedure based on the error expansion technique from
[]] also [16). Namely, to perform the expansion, we decompose the LSA iterates 0g defined in (I) into transient and fluctuation terms:
O₂ a((r)) + @(1)
where we have defined the quantities
k agT J
ãtth = -i - 03,, 0th
Σ j=l
(26)
setting
T mikk [I--aA(Z
m, k E N,m k. with the convention Pmnkk -I,m= > k. (27)
The dependence of I mekk upon the stepsizes (az) is implicit in (77 Here the quantity o(tr) is the transient component of the error, which determines the at which the initial error A f is forgotten. The term (ff)) corresponds to the fluctuation component of the error and is determined by the oscillations of the last iterate 0₂ around 0*
Proposition 4. Assume AT A2 and A
Then for any where n satisfies 9 it holds for
2 < p < lo that
4e, R
Bd/ - -0-1pp] V (a(22)
Σ az 110
0*
Vak.
Va
16

---

Proof. Expanding the decomposition 26 we obtain that
E 1 - [la] - E /// L. (0o 0" +1 1E
ay ,
(28)
and bound both terms separately. Since the sample size satisfies (see equation (71). that for 2 S p x log n² it holds
we get applying Corollary
E E/r[[] (0. 8r) 80 E Veqeeppl - (a/2) Σ
az 010 - 8*1l
Now proceed with the second term in 28 and Lemma with = a/4, we obtain that
Applying Burholder's inequality (50) Theorem 8.6]
p/2 1/2
(En= 0z I ++ 112)
B Σ j=1
J s
s
B2/p
1/2
E 1=ر ( [1T")+==))11))
Sp p
1/2
$ /Vroollello
(1
are
4
E=j+1
40 4evhiollelloP
V
Va
Corollary 2. Under assumptions of Proposition 4 it holds that
1
POk [n, 2n 1]: 110g 0- 2 g(k, 110 - 0*1l, - n
where we have defined
8e² v [Rol=|la> log
g(k, |10. 8" 11, n) /niQo (a/p) Σ at 110 0'l
Vax
Proof. We first note that Lemma Iimples, setting 8 1/n2, that for every fixed k E Imx: 2n
1),
802
kQ log n
1
P |10x 0*1 Rage exp ( (a/2)
Σ a 1160 0-
va s
a
n2
Application of the union bound concludes the proof.
We conclude this part with simple consequence of Markov's 's inequality. Lemma 1. Fix (0, 1/e2) and let Y be positive random variable, such that Et/P[yP] < C1 + Cap
for any < p < log (1/8). Then holds with probability at least 1 5, that Y eC1 + eC2 log (1/8).
Proof. Applying Markov's inequality, for any t 2 0 we get that
E E
< (C1 + C2p)
P(Y 2 t)
t
t
Now set p log (1/8), cC1 cC2 log (1/6), and aim to check that
(C1 C2 log (1/8) log (1/8)
(eC') eC2 log (1/ log (1/5) 6
Taking logarithms from both sides, the latter inequality is equivalent
C1 + C2 log (1/6) < log 8
log (1/8) log e(Ci + C2 log (1/5))
which turns into exact equality.
17

---

A.3 Proof of Theorem 1
We first define explicitly the remainder term outlined in the statement of Theorem
n²-1//2
CA
27-31/2 3/2
(n a, Co,
(29)
co n2 12/2-//2 Vcoa
Vcoa
aco
Proof. Since both terms in the right-hand side of the error bound of Proposition scales linearly with y /KQ, for simplicity we do not trace it in the subsequent bounds (i.e. assume Ko 1), and then keep
the required scaling with si only in the final bounds. The decomposition (25) is key element of
our proof and allows to treat different error sources D1 D2 separately. For the last iterate we have, using Proposition that
I Va van + exp (aa/2)
E [100 - -01133 S
aF 1100 - 0-1
t=1
|
Va Vann + exp { -(a/2)
2n
E [1/2[1122 13] x
at
1100 0-11
8=1
Thus, using that Dk= Ork ca(n'-111) and cp S - we obtain that
||
1271/2
coan
EV2 [1D
110 1100-001 00
exp
Vacgn!l 11/2
00
2(1
||
n221/2
(2a(2n) 1 1-7 y
E1/2 |221 2
+
exp
|100 - -0
Vacon( 3/2 1/2
co
Now we proceed with D3- Since it is a sum of a martingale-differenee sequence w.r.t. F2 aZze l S k),, we get using Proposition 4 that
2n-1
x
E11
0" 11]
71
2n
|
ak
C
Σ
2n
cxp
k
ai
1:0 - 1-12
n
a
k=
k=n+1
t=1
|
C
n
2n
Okk
exp
Of
a4 cxp
aa
Σ at
110b
0-
n
a
na'20
k=
k=n+1
t=++1
$1
cD C2 |1 +
C²
Coan 1
5
agaa exp
1100
11
7)1
1 1-9
where we additionally used that S & 1/a due to Lemma
3 Now it remains to bound the term DA
from the representation (25). Using Minkowski's 's inequality and Proposition 4 we get that
(1
1
1
///2 [ 11
E1/2 [ 0-||3]
VT
Ork
ak-1
2n-1
I1ll (k* (k- 1)7)
vax
cova
2n-1
(k7 - (k - 1) exps
- -(a/2) Σ
110g 0-
cov
k=n
8=1
|
2n
n 27/2
coant-7
exp
1100 -0"11
/ /aco /
11-7//2
ac
2(1 - 7)
||=||oc
2/22
cyan 1
/ (acon(1-71/2
+
acg
exp
2(1 7) |100 - 0-
18

---

Here in (a) we additionally used that k? - (k 1)7 S k' together with Lemma 3
Combining the
estimates above yields the result of Theorem !
We conclude this section with some technical lemmas.
Lemma 2 (Lemma
Let 0 and (ow))220 a non-increasing sequence such that
0o < 1/b. Then
n+1
n+1
1 II 1=1
n+1
Σ aj
II (1 ((b)) 1=
oub)
b
Proof. The proof of this statement is given in 18] we provide it here for completeness. Let us denote Ujm+1
m+1 (1 11--ap arb). Then, for ,I,...,, 1]. Uj+l:++1 Ujm+1 box boz
Hence,
n+1
x+1
1 n+1
Σ
ag II (1- axb)
Σ
Uf+1m+1 Ujm-1) b-1 u1m+1),
1m5+1
j=l
and the statement follows.
Lemma 3 (Modified Lemma
18).. Let and let ar = co/E7, 7 E [1/2; 1), such that
co S 1/b. Then for any n satisfying
27
1/(1-))
n 11-7
27(1 -7)
2
2
and
2
(30)
cob
1 1+ log(n)
cob(1 - (1/2)1
and any l 2 n, it holds that
Σ
II 8=1+1
(1 - axb) S (4/6)an+1
Proof. From elementary algebra, we obtain that
Co
co((1 1/8)7 - (e+1)
Co ?
Oi 0'411
(1+1)²
(l 1)7 t
(31)
where we used the fact that (1+ + x)"² < 1 ya for 7 [1/2; 1) and [0, 1]. Hence,
at
1 1 + 7
at+1
p
Thus we obtain that, since & 2 n,
k+1
k+1
k+1
k+1
(1 - a,b) = az+1
aj
Ot-1
(1 - (1-a,b)
{=1+1
j=1
{=j+1
1o+
k+1
1 7
< 01
(1 arb)
[-1
1=1
(=j+1
k+1
k+1
k+1
< 0.41
Oj exp
exp
arb
exp
Σ
e-1
exp
Σ
arb
{=j+1
(=j+1
(=n+]
(=n+1
k+1
k+1
< aa4t
Σ
aj
exp
Σ
exp
ar
exp
Σ
arb
2
1=1
(=j+1
t=j+1
8=++1
In the last identity used the fact that, since n satisfies (30). it holds for l > n/2 that
arb/2
(32)
19

---

We will now prove that for j S n 1, it holds
Σ (b/2)
Σ
Σ
(33)
(=j+1
E=j+1
directly follows from j I [n/2]] Note first that
For j 2 n//2, the bound
33
We now turn to the proof of
33 for
n
Σ Emj+1
S (log(n) +1)
2
On the other hand, we get
m+1
dr
(1)
(j + 1)²
Σ
Ł=j+1
j+l
x7
7
Comparing the above bounds, to ensure that 33 holds, it is enough check that
cab
7(1 + log (n)) <
2(1 - 7) (n 1- (n=27 ())
(34)
Note that 34
guaranteed by
30 Using that e < x/2 for x E [0, 1]. we obtain that
A+1
k+1
k+1
k++1
Σ
a
II (1 - arb) s as+1
Σ
aj
exp
-(b/2)
Σ
az
/=1
ビ-jt1
j=1
t=j+1
k+1
k+1
S ak+1
aj
(1 (b/4)ar)
j=1
(=/+1
S (4/6) ax-1
where the last inequality follows from Lemma
B Proof of Theorem 2
We first define explicitly the remainder term outlined in the statement of Theorem 2
A2(n, a, CA, Tr Ec, co) = xQ (VTEEAA, + EC v1)
(35)
aco
and constants CI, C2, Ca, C. from Theorem 2 optimized bound [5). and Remark
respectively:
C VKollElloo VTF
Ko M. + +CA / TT kl))))
Vaco
C2 Vkollellx VT CA
+NQ CA V Tr Ee (1E)loo + TF CAlls)oo)
Vaco(1 7)
(36)
C3 Kolco CA CA
VI) T Ee (1eello + VTFE + CA (1eloo)
aco
(T) C2 Kelco CA VIJV Tr
E
(lEll + V To TE
CA ||=||x)
aCo
To complete the proof we only need to combine apply (13) with
13
with the bounds of Theorem |
Note that we
E3 Vn
Thus, for T, defined
we have
|| n 1/2
r, <
20

---

Applying the Cauchy-Schwartz inequaalll we get
VnollEllo 00 I
co Ca
n(1 +
Vaco
vI -I-7it iin0/2
Chan 1
Tr V exp
1100
1-
2(1 7)
Now it remains to bound the last term in 13). Using the Cauchy-Schwart inequality and Lemma we obtain that
2n
2n-1 1 |||
1/2g
|| - 11 - n 1/22 -
11 D - -
72
1=
1
KQ (Tr + CA v Tr TE
KQ CA v TE (1 + VT + CA 1|=1
ocon -7
nT/2
KOV (CA v1)
coant-y
exp
1100 1100 00
600
22 7)
and the statement follows from
63
Corollary 2.3].
B.1 Proof of auxiliary lemmas for Theorem 2
Our proof of Theorem
based on the key lemma below, which allows us to bound /1/2[||
D (2] for i E (n + 1 ...... 2n}.
Lemma 4. Assume A A2 and A3 Then
E D D 13 Ni
VF + CA |Elloo) n2-1/22
oco
+ Xi CA (Ilello + V + CA ||E||00)
n2 l
21) 7-12
coant-y
exp
|100 1
aco
2(1
Proof. Since both terms in the right-hand side of the error bound of Proposition 4 scales linearly with /iq. for simplicity we do not trace it in the subsequent bounds (i.e. assume KiQ 1), and then keep the required scaling with KQ only in the final bounds. Consider the sequences of noise variables
(ZI.... Z Z,, 7s+1,-.. Zonn) and (Z,,... 7,-1, Zi, 7..,....; 72a))
which differ only in position i, n + 1 sis 2n, with Z being an independent copy of Z,. Consider the associated SA processes
02 Op-1 on (A - b(Zx)) k
Oo 0o E Rdd
(37)
0
(1) k-1 - or (V(:)) b(V))), 1
0
0g E TRdd
where Yx Zu for + i and Y; Zy. From the above representations we easily observe that O2- = ( for hs < i, moreover,
0, 05 as (c(((())) - (2) b(Z,)
(38)
=a,(A(Z) A(Z)) -a =
where E; = =(Zi) and & = E(Z)). Representation (38) implics, together with Proposition and Co a. that
- || S a; / TrE. CA |||| 0 + CA
3/2 + exp
1
i-1
E
Σ
ajj 1100 - 8*1l
Va
)=1
(39)
S <ai(VTrE, TrE + CA (Ellax) t CA expp
ag
1100
00'1
21

---

Moreover, for any j > i one observes, expanding 37 that
0j 0 = II
(1 au 00A(22))
(40)
k=#+1
We use the above representations to estimate 1 11]. Using Minkowski's inequality,
E 19 Σ 11 1
(41)
and bound the respective differences separately. Recall that here D1 D4 are defined in 25 and D -D! are their respective counterparts with Z, substituted with Z First we note that the term D1 D for any + 1 S i 2n. Next, using 44 and (39 we get
[ - D 12]
1
[1
E
02n
v /202n
2n
E222 [I] II
(1 - an -..A))))) - 1
218
a,(v + CA [|
Σ csp
exp
Vnaan
k=i+1
ai CA Via-
exp
a Σ
2n
as
110 - 1-1
2
k=1
In the inequality (a) above we additionally used the stability of matrix product introduced from
Corollary 4 Summing the above inequality for i = n - 1 to 2n and applying Lemma 2 we get
2n
VTFE, CA 1E
CA
[1 - 1S
exp(
ak 1100
0*1
avn022
aynaza
1=++1
k=1
TTE + CA ||=|| 1/-1/2
CAn
coan -aan--7
exp
1100
00
(42)
aco
aco
2(1 7)
Now we proceed with the difference D3 - D Using
we get
2n
D3 - D.S0
1 1 (A. A1)0--1-0) + Vn
Σ (Ax - A)(0x-1-0)))) (/22))
k=1+1
The expression above is sum of martingale difference terms w.r.t. filtration F =oZZ, Ze, S k). Hence, we get, using (40) and Proposition
maffingale-difference that
C² E E 111
C2
D 100
Σ
2
(43)
n
k=++1
2 11 +
C²
1100 - 112
i-1
exp
-a Σ
az)
na
n
1=l
C2 +
2n
Ell
Σ
expf -a Σ az)
n
k=it1
1=
22

---

Using now the bound
39
we obtain that
Bi|10 0.00 [2]
Σ
03}
k=i+1
j=i+1
2n
k-1
S Sa (Tr Ex + C 1|:13c)
exp( a Σ
+ a. 1 - 0-12
1100
Σ
expl a
aij
k=++1
j=1+1
k=++1
1=1
2 af 0gn
2n
k-1
a
C
C2 A 1100 - 8-12
2n
k-1
(Tr + C2 11=133)
ag expl -a
Σ
ag) +
Σ
as
cxp(
-a
Σ as)
agn
R=++1
s=+t1
k=
(a) of E C |lo
of
C
i-1
110. - 0- expl -a
aイ}
a022
0022
j=1
In the above formula in (a) we additionally used that, since a,a S 1/2,
2n
A-1
S L. expl az) dr
On
expl -a
Σ jmi+1
ag) as)
(44)
A=/+1
Hence, combining everything in (43). and using additionally that a; S a, we get
B 11/21| - -D
CA
|I
055( TT Egg + CA [ellbx)
Vna
Vazg
CA vn
1
a CA Vadza
a expl
Σ
i-1
1-
2
j=1
Summing the above inequality for i n + 1 to 2n, and using that ag = co/k3, 1,,,,
get
2n
2n
Vai voont 1/22
ai
2 V
Va2n
im++1
imn41
and, hence, using again a₂ S a, we get
2n
E 11/211Ds- 11
1=+11
CA voi Va
(Ilellc + TrE, + Callello) n + + (CA v1) 0*11
2n
i-1
a expf
Σ
a²}
naan
2 j=1
1=++1
CA /co Va
(leelie + TrE + CAllells) n n²="" +
n² n- (CA
8*1
Chan 1-7
exp
aCg
2(1 - 7)
where for the last identity we used the fact that or = =o/k"" and difference D2 - Note first that, proceeding as in (31) we get
(44) It remains to upper bound the
7
0ak ak W k 1 a
(k- - 1)1-7
Using now the definition of D4 in
25
we have that
B1/21114 - 119
II
2n
(0k-1-
1
1
[|a]
V11
Okk
k=++1
2n
k-1
<
1
|
0(00p91
Σ
expf
a
Σ
o3}
vn
ak
ak-1
2
k=
j=i+1
23

---

Hence, using the bound (39 and taking sum for = n2 + 1 to 2n,
E 1
-
VIFΣ.
CA Callol
2n
2n
1
1
exp
a
Σ
k-1
as}
Vn
ak
aK-1
1=
k=
j=
CA 1100 0'
2n
04
2n
exp
a 2
k-1
ag
Ok--
+=++1
1=1-1
j=1
Changing now the summation order, we obtain that
2n
2n
k-1
2n
Σ
a2
>
1
1 ak-1
exp
a3)
Σ
ag
ak
*=++1
k=++1
1=
k=
1
On+1
Orn
a022
Hence, combining the above bounds, we get
2n
11 D1 - 19 VI +
CA ||E100
2n
Σ
E
+
Σ
B1/21111 - 119
(45)
Vnaazn
i=++1
1=n+1
TF + CA ||
C1 1/2
Chan 1 7
7-1/2
exp
1100 0'
aco
aco
2(1 - 7)
It remains now to combine
and
45 in
and use that co S a.
B.2 Relations between Couv and integral probability metrics
In this section we closely follow the exposition outlined in [24]. Consider two Re-valued random
variables X and Y. Then the integral probability metric [75] associated with the class of functions H. {h: Rd RR E[X()]] 00, E[](Y)] < oo is defined as
dx(X,Y) sup [X)] B[h(Y)]
MCH
Different choices of H induce different metrics, in particular, mention the following:
Hx {1 {1zsus
(u),..., Ud) Rd} Conv(RR))
Homm [1ees
Hw {h: .R. + R.
||b]lrap I 1}
Hmm] {h : IRd
+ R.
-m-1 is Lipschitz with |/l] S 1, 1 1 S m]
where Conv(Rd) refers to the set of convex sets in Rd. |1lllzip = sup,,y quantity (hly is defined as
[
and the
@ch(u) hhl by Ef1...... ou, Ous, 1lac
max
In other words, for E N, the class H|ml corresponds to the functions with bounded derivatives up to the (m - 1)-th order. The class Hg induces the Kolmogorov distance between distributions 775, class Hcom induces the metric Pn Couv defined in (2) which the main object of studies in the current paper. Class Hw induces the celebrated Wasserstein distance, and classes H[m) induce
smoothed Wasserstein distances. We will denote the respective metrics by dk P Conv dw, and [(m]. respectively. Then, obviously,
dx(X, Pn
Conv (X,Y)
for any random vectors X and Y. Other relations are more involved. When Y is a multivariate normal vector, it is known (see e.g. (49 that
Conv (X,Y) (X,
Pn
24

---

where the constant C' in the above inequality depends on the covariance matrix of vector Y. This inequality justifies comparison of our bounds of 2 with the result of [65]. The authors in considered integral probability metric d(2) and obtained rate of convergence
C1 d2g) (VT(O, Y) < Vn
where Y (0, 2, and C1 in the above inequality stands for constant depending upon problem dimension d' and other instance-dependent parameters from A Applying the result [24 Proposition 2.6] yields
dx dx(vn(0,, - 8) (d(a(V/((O,, 0)) 1/3 2 n/6
Thus, the result of [2 implies rate of convergence of vn(0,, 0*) to normal law NO, Esx) of order n-166 in sense of Kolmogorov distance dx- Our result of Theorem 2 implies the respective rate of order n 1/1, n-1/1, At the same time, it is not clear if Pn
Conv can be directly related to d(g].
C Bootstrap validity proof
C.1 Proof of Theorem
We first define explicitly the remainder term A3 outlined the statement of Theorem 3 that is,
3/2 An(n, a, CA [|=|l=)) "Q (C* VI)llell 1/4 Vlogn
(46)
33/2
In the above bounds we do not trace the precise dependence on the constant cu from the definition of the step size. We now define the following sets, with the convention ag = co/VE:
k oe 0*1l
Q
vk: E (n, 2n 1]: 100 - 00 2 Vaiee expeexxp-= - a
Σ 2 8=1
(47)
8e² VKoll=llo log
+
Va
(1 aaj
02
n1 + 1 S m S k < 2n:
|Tmak S Viiee
jmm
log(n)
4(1 ||e1120/ /03) log(n)
Q
1//12/b 1/2 I|| < 4||=||
on
n
2n Σ k=
8CA Vige* 2 Vlg n S
Q4
Vl E [n, 2n 11]
(Ax A)
6 +CCA VRoe
Vaas
vh E [1;n], Vm (n, 2n M]
Σ
or(A; A)llo 2C VFQ
Σ (=m+1
of log log(2n*)
(=++1
Ee log(n)
4(IEE + || log(n)
26
Ezll < 4||=|lo0
73
Then, due to Corollary we have that P(2,) 2 1 1. Similarly, due to Corollary 5 ((2)) 1 The bounds IP();))) and IP(22) follows from Lemma 5 and Lemma 6 respectively. Similarly, Proposition 7 iiplies that P(2))) 2 1. Hence, based on the sets above, we can construct
x-
P 2 n Ω2 n g O 22 n m 0
25

---

such that P(Qn) 2 1- All further on. we restrict ourselves to the event Qg. Restricting to this event, we obtain that, with Minkowski's inequality.
PP (vn(0, 0n) B) - IP(Vn((,, 0*) E By
sup BEConv
(V - 0,) E B) -PO(5 B)
sup (EConv(Rd)
[P(E B3 (5* B)
sup (RC)
[P - 0*) B) P(E E B)
sup (EConv(Rd)
where we set 5 N/ A T. -
Ei= and { N/O, >,) where Ex
A A Now we control the first supremum using Theorem second one using Theorem 5 and third with Theorem
Lemma 5. Assume
with y = 1/2, and A4 Then
P(22)) 1/n.
Proof. The proof follows directly from the matrix Bernstein inequality, e.g. [69]
We note that
||= Ee 21 1/2 - 1ll s 1 + | 11
and
2n ||
BI E3E ( T - -1) s 1/22-/11
k=++1
Lemma 6. Assume A 22 A3 with 7 = =1/2, and A44 Then
((24 2 1 1
Proof. Denote
X = (A+ A)
and let Fa.4+ = o[2,,+11 < j < k) 1+ k < 2n. Then E| F = 0. Let
Se Ek=e+1 Xg. Note that on f22, quadratic variation of S be controlled
2x
2n
Var := max([
Σ
EX
FR 1.11111111
Σ
B[X, X
k-1
4nie C2
S xaee* C²
Σ II (1
axr//4²² <
k=t-1j=t41
Furthermore, on f2
| S ViQe CA
II (1 aay/4) s Vige² CA. j=t-1
It remains to apply the Freedman inequality for matrix-values martingales (68 and use the union bound over E [n, 2n - 1].
Lemma 7. Assume A
A A with & = 1/2, and 4 Then
P(S)s) > 1 1/n.
26

---

Proof.
We first fix h E [1; m E [n, 2n hl, and consider the random variable
Tn
Σ
ac(Ac
-A)l
1=
Then we control its variance as
m++h Σ
mi+h A) 1
mi-h
max(I)
[A
Σ {=++1
af (A, A)JI) S C
Σ
o
|=++1
(=++1
moreover, ||(, (O(A,-A)TI C Applying now the matrix Bernstein inequality 66 obtain that with probability at least 1 - 1/n2, we have
m++h Σ {=M+1
azvlog (2n 0m+11 CA log (2n'd) S 2C
m
Tn S CA
Σ E=++1
a log (2m*).
In the last line here we used that d < n. Rest of the proof follows by taking union bound over h and m together with || S Ko || valid for any matrix B RRdxdd
Lemma 8. Assume A7
with 7 = 1/2. and A Then
P(22)) 1/n.
Proof. It is easy to check that [le2e] -Eell < |E + 1| Moreover,
Var
(ELE) Σ2)² S n|| |ell.
remains to apply the matrix Bernstein inequality together with the bound n 2 d from A3
C.2 Rate of Gaussian approximation in the bootstrap world
The main result of this section is the following theorem.
Theorem 4. Assume A 2 3 with 7 =1/2, and A4
Then, conditionally on the event No the
following error bound holds:
/
KQ
3/2
VI)Il= log n
Pb 00) E B) -P'(E" B)
sup BEConv(Rd)
3/2 A Vn
2
-/4
KQ
(C*)
Mogn
exp
Σ
12
a3)) 0*11,
3/2 Amin
where ęb AN(00A--127. and uo n En E
Proof. Since both terms in the right-hand side of the error bound of Proposition Accaees linearly with /RQ. for simplicity we do not trace it in the subsequent bounds (i.e. assume KQ 1), and then keep the required scaling with so only in the final bounds. Recall first that the quantities 0 and Og defined in (16). We start from the following decomposition:
- 02 (I (1 -0001-00-111 -0k-1) (aa)-as(uu auwwxxu - A) -- 0x-1)) -1---awwwee 1) (0. (0,
27

---

Taking average for & from n + to 2n, we get after multiplying by vn that
2n
6
1
82n
(O, - -0n)
(wk-
1)
+
Vn
On
Or2n
kmn+1
D2
W
2n
2n.
(wk - A)Aa 10 k-1 - 07)+
(0h-1
0k-1)
O2
ax
OKk-1
k=
k=
D3
D2
2n
(Ax
A) -0--1)
(48)
kmn+1
D3
The formula 48
resembles the key representation 7 == ( - 6n) = WD + Db, where
D DJ +.....+D) D
(49)
and D D are defined in 48 Now aim to apply the result of 663
11 B) (gb e B)1 S 259 + 2E [1| |
sup (EConv(Rd))
+2
E El D - DIb (50)
(=++1
where Er= Vn (w 1) We finish the proof by the application of the formula 50
In order to bound the quantities | and (b)i)( we apply the respective results of Proposition inequality together with
and Proposition [ respectively. Namely, applying the Proposition 5 get that on the event Go it holds
~O(CA VI)Il= V Tr L log
Eb[|| < (E* (E'1)
1/2 (1
x
11/4
3/2 n
|
VI) CC*
(CA v1)/logn
exp
coay
ni
110
0-1
Va
Vna
2
Similarly, applying Minkowski's ' incquality and Proposition 6 we obtain that
E
&& (bb,)) S [1<
[19) 1/2
Σ
[E
1)b0))
3/2 KQ (C
VI) logn
Ko
1el1 C
Vlog
exp
a
a
110 - 0'
1/4
a²
2/2
j=1
Now remains to combine the bounds above 50).
Proposition 5. Assume A7 A
with 7 1/2, and A4
Then, conditionally the event Qa. the
following error bound holds:
E ( W2n, Zi ..... Zan) 313] 1/2 (CA V1)llE/loo log
n1/10052
KQ
3/2
(C*
v/)n
(CA Vna
v1)ylon
exp
Coa ni
110 - 0-1
Va
2
where S stands for inequality up absolute constant.
Proof of Proposition 5 is provided below in Appendix
The lemma below a direct counterpart
of Lemma 4
28

---

Proposition 6. Assume A7
A2
A
with y 1/2. and A Then, conditionally on the event So, the
following error bound holds:
2n
(CA V1)lle
Jelloo CA
Σ 1=++1
00 1/4
logn
a3/2
a²
(C) v1)n
Vlgg
exp
ag |160 8*1
03/2
C.6 Lemma 9. For any on the set Ggg the following inequality holds:
Proof of Proposition is provided below in Appendix
ag
& C
11 0
+ C k II a0l1-aa//42210.. -
Proof. A direct application of Lemma 11 with L 0 yields that
C
E 10 1x]13]
(1+
C II
1-11
Now to complete the proof it remains to notice that CA 2 a.
Lemma 10. For any matrix valued sequences (Un)nEN. (Vn)neN and for any M N. holds that:
M
M
M
M
k-1
II
U
V
Σ
II -
Vi - -v U,.
j=1
C,3 Gaussian comparison inequality
Theorem 5. Assume A7 and A2 Then on the set Q2
dlogg 4vd(1+ + | =12= log
P(E B) (5b e B)I = 4122 1/2 /2
sup (EC)
12
Proof. We will use the following inequality
[I - -N S
/ 1-12 -1]
(51)
Applying (5I) we obtain
Vd
sup (RC)
IP(E B) pb E B)ll
S
Σ 1/2 12>05 1/2
-I]--
2
remains to apply definition of Z23.
C.4 Auxiliary technical results.
For the analysis of the difference term 6 6% we use the perturbation expansion technique introduced in [1, see also [16] Within this approach, we represent the fluctuation component of the error ((!))
defined in (26 as
(( = -(()) + H
where the latter terms are defined by the following pair of recursions
f(()) (I 0r A) _ an,)
j(O) 0
(52)
H())) = (I -I- (I-a,A(2,,) (0) a, A (2, J(1
H 0
29

---

Moreover, it is known that for L 2 1 the term Ha) can be further decomposed as follows:
1 - Σ J 1
+ H
Here the terms e and H(() are given by the following recurrences:
_ = (I - an A) _ - a,,((Zn)) ( = (I - a, A ) H - a. AZ,))
J0 = 0,
(53)
HO 0
The expansion depth L here controls the desired approximation accuracy. Informally, one can 11 [|²] z on (6+1)/2 and similarly | H [|]]
show that ( expansion, we prove the following lemma:
an ((+1)/2 Using the outlined
Lemma 11. Assume A7
with 7 = 1/2, and A
Then for any k 2 n and L E N the following
decomposition holds:
0h 0g = J
Ibd
+ 1.
(54)
k
z=1
where
1b.
Σ
an(wr 1)
t=++1
Jbl
ae(we - 1)r 1N bij- je [1.4]
im++1
Hb.
Σ
aelwe- - 1e
(55)
i=++1
and the quantities εe are defined as
E Ar(Or-1 - ee.
Moreover, the event Ωo.
1 A
C2i+2
- II aa,/44)/00000 - 0-1/2, j [0 (56)
at+1
j=1
ag
I++1
A
2(L+1)
1
(((+1))
11000///30800 0112
(57)
x++3
j=1
Proof. We start from the decomposition
0 - = (1 - A,w 02-1) ar (wx - 1)Ex.
(58)
Expanding the recurrence above till A = n, and using the fact that 0h = On. we get running the recurrence (58). that
0 02 Σ arlw; 1)T 1
Hence, proceeding in 52 we obtain the representation
f(b.0) (I - A+ l(b.D) ax(w 1)
J(b.0) 0.
1 (b.0) (1-aguAA) (b.0) - (wx - 1) 1) (b.0)
11 (b,0) 0.
30

---

It is easy to check that _/b + (r(b.u) 02 - 0z. Similarly, with further expansion of Hk along
the lines (53). we arrive at the decomposition (54). Since wy for l = n + 1.... 2n are i.dd. we get using the definition of the events 22 and f2g, that the event Ωo:
avelee| log"
| - || + C expl
-a
Σ
a 0-122
A-1
are aeIle|le log" n
11111100 + C II (1
2 - 0-112
(59)
j=1
f-1 1110 + C
(1 aox, /2x, - 0-112
j=1
where for the last bound we have additionally used that ag log n/a a S 1 for é 2 n. The latter bound guaranteed by A4 Hence, using the bound (59) together with the definition of Jb.0. we obtain that
E 1911 = Σ
aflleetuedll
= Σ (Aeeeee(Aeele-11- - 0*) + +z)lll
1=1+1
t=t+1
< || l
Σ o2 II (1 - aaj/4)2 + C
Σ oz II - aa; aox; 14) 0*1/
8=n-1
j=(+1
8=++1
+ ||el33. C2 log" n Σ
II (1 aa,/ /4)
8=n+1
j=f+1
| 02
h (1 aa,/44//100. 11 + aglle C2 log" n
C log
II
a²
j=1
|
2 ak
C2 II (1
aa,/ /4)111/ - 12
a
j=1
where we additionally used the fact that is E [m: 2m] and n satisfies A4 has form
Assume now that the bound
on k bbj-1
I og +
E
||3]
C2i (aaaaa//4)8 1-122.
a
Then, using the martingale property of Jod we write that
[b] =
1 boj
1=n+1
&
s 122 C2i
k
k
k
(1 - /4) + G21+2 Σ
of II an, 14) - 0-112
a²
8=
j=
En++1 j=1
1 C2i
C2]+2
an, /)) 0+12,
a+tl
/=1
31

---

and thus the bound (56) is proved. Moreover, using 55 and Minkowski's inequality, we obtain that
(10111412-11111 < CA
Σ
2+1 (2 (191))111)))1)
t=++1
(2+3)/211
|Elloo CA
2 CA
II (1 - aa;/4)
alL+1)/2 (=#+1
j=t+1
h
Σ + C
C++1
ai II (1--ac (1=-aa/ 0
t=
j=1
(L+1)/2
char1 ||
k
2 ak
+ C+++1 vk
- aaa4aa,, - 0-11
a (L433/2
1=1
and 57 follows.
C.5 Proof of Proposition 5
Recall that the quantity Do is defined in (49). Since 0% = On. we conclude that DJ = 0. To estimate other terms will use the main error decomposition outlined in Lemma [1 that is, the expansion
0 0 = Σ Jo + Hb.
applied with different L 0. To bound D3 we take L 0 and obtain
||e 2
2n
Eb
H
1+
a1, - 10112
a
2n
== a/n
C2 a²
2n C
i
n
aa
h/3/4)3/100 11
To estimate D3 we note that
2n
D
(wn
- -00) = DŽ,1 + D2.2
k=n+1
where we have set, respectively,
2n
Db
Σ
(wk (0Ax 0k-1),
Vn
k=n+1
2n
(w)-
1) - 8*)
3,2
k=n+1
follows from Lemma that on the event 9g it holds
C2
2n
E
112]
Σ
E
- 1
π
k=n-1
||
C2 1+
2n C
Σ
II (1 1-1
kmn+1
1=1
C2 ||
2
C² vn
1
+
exp
-coav'n 1000mm111000 1-1
a/n
a²
32

---

Moreover, on the set Gg it holds (since So S Ω2)). that
[I 3.2
E
1
(0x
112
71
1==+1
C
2n
R exp(
x1 0100 - -0-12+ + axlle log" n
k=
t=1
C
at 1100 07112+ + CA || 1l log 2 n
2n Σ k=
exp(
-a
Σ
na02n
na
C2 expo
C2 |1 log n -coavn (100 -0
ayn
avn
Combining the above bounds, we get
E"[| 1= 11 |1 +
=0111 +
CA IE log" (1 (++
C
C Vn expo -caava 100 0-112.
avn
a
Now we proceed with the term DJ. Applying Minkowski's inequality, we get
D 2
{EE*) [11011
Oz- 11
0kk
ak-1
k=
2n
v
[+
CA a
+ CA Vk II (1 a0a-aaa/4444000 - 0-11
Vk
Va
k=n+1
j=1
||
CA
A
2n
$
1+
(1 aaa//44/000000 0-
1/11
Va
k=
|| Va
CA
Chayn
1+
CA exp
|10g - 8*1
n
It remains to upper bound the term Dg. Using the decomposition, suggested by Lemma
11 with
== 2, we get that
D3 = 1
Σ k=
2n
(Ax
- -2--1) -
2n (A - Aj
k=n+1
DE.
2n
2n
(Ag
A)
b.1
(Ax
k-1
b,2
(Ax
A)
k=n+1
k=n+1
D8,2
D
D5,4
Here we have to consider expansion until b.2 since dealing with the latter term (outlined as DE, in the above expansion) is possible only with Minkowski's inequality. Now we consider the summands D DE separately. Consider first the term D3,1. Changing the summation order, we obtain
D
(A A)
Σ (=++1
arlw:- 1)1 118-+1
k=n+1
2n-1
2n (As A) Es
Ore vel - 1)
E=++1
1=
33

---

Then on the event So we get, since fo S S2,, and using that satisfies Ag
2n
(Ax - 1-- 11l log n
(60)
a0k
-=
Combining the above bound together with the one provided by 59 we obtain that
|1
2n
Or log r
2n-1
Ore log n
E-1
E
DE
11
Σ
(1 a2./22 112
8=++1
+=
||
log n
C2 log n a²n
exp
111110-0011
Vna
/=1
Similarly, for the term D we get, changing the order of summation, that
2n-1
ae(we- - ac(we-1) 1)(
2n.
D
Σ
Σ
(Ax
A) AcJ
5.2
1=
Hence, using the bound (60) together with (56). we get
Db
11
2n
Oee log n
CA
CellE|
+
C2
II (1 aaaaaa//43/// - -001))
8-1
8=
j=1
log n
2n
C4 logn
2n-1
8-1
II - aa)aa 1-
og +
ag
na²
na
b=++1
j=1
Iell
log n
C4 log
exp (a/22)
a3) 1:0 - 0-112.
n
na
j=1
We proceed with D5 We change the summation order and proceed exactly as with D Indeed,
2n-1
-1) -
2n
Db 5.3
Σ
an(we -
Σ
(Ax
A) AcJ
(=n+1
k=
and
1 2n
Or log n
a C2
D
Eb Db
5,3
115
C²
+ Cd
(1 ra;/4422100 0-112
a²
8=n+1
j=1
C² I| logn 3
C logn na
n
expl sxpf-(a/22 (a/2)
Σ
a } 110 1¹112
It remains to upper bound DP Proceeding as above, we change the summation order, and obtain
Db. Vn i=++1
ar(we
Σ (A
8 AAJt-
R=
34

---

Applying Minkowski's 's inequality, we get
(E (
0
E
2
2+1:k-1 11
(E 119)
k=
2
2n
k-1
| CA
exp(
a
Σ
8/2
b 1
k=t+1
j=t+1
2n-1
2n-1
k-1
Σ
a2
Σ
exp
Σ
ag | 11000 - 1'1
8=
k=t+1
j=1
C |1
C
Vra5/2
a₂
3/2
Vna
exp (
aj
a3)110 0'1
b=++1
C
||0
C Vna
exp
13)1000 - 0-1
n 5//2
Now the result follows from the representation D
(49) and combinations of the above bounds for D7
C.6 Proof of Proposition 6
Consider the sequences of weights
(W1, -i-1, Wiy W W2n) and (wi..... -1, wh, Wi+1
W2n)
(61)
which differs only in position i, n + 1 S sis < 2n, with wo being an independent copy of wa Consider the associated SA processes
8 = 0 - aw (A b(Zx)} k 1, 0 = E R2
(62)
(b.5) h-1 w
(9) (A(Z))) (b,4) b(Zx)} k2n+1, ((b.1) 0n Rd
where _ = We for l + and w w/. Respective random variables Db and (b.i)) are based on the first and second sequences from respectively, and constructed according the equation 48). From the above representations we easily observe that 0 = o(b,)) for < i, moreover.
gb g(b..) = az (w; w (A(Z)))b - b(Z,)}
0z (w; w/) (A::)) - -1-1) - b(%,))
a, (Z)()(Z)))(-= -0,11 + +
where & = e(2) and o = =(2)). From the above representation we get, applying Lemma 9 and
59) that
110b -
$ 0x CA (R 110. - 1/1 + + CA |&ll
(63)
3/2
1ello Cº
a. CA ||= +
a:
+ (C2 v1)vi II (1 /4,/ 0
3/2
==1
aillElloo Ca
+ (C& vIli oa, 0-
1=1
where for the last line we have additionally assumed that as S for i n. Moreover, for any j > one observes, expanding 622.. that
83 - 00.0)
(I owwn A.,)A(Zz)) Rmi+1
II
(000))0000000 0.0.0) Th 12 (0) g(0.)))
35

---

Thus, similarly to we obtain that
DB 116111111111 & EE DJ |31)1//2
and bound the respective differences separately. By the construction of the process above, we note that Di ((b.)) Proceeding further, and using the equation (48), we obtain that
[E || 1b.0 13/11/2
1
111) 1/2
Vnazn
1
T [11 (+1122111) 111] 1/2 (E [E 0/0.00 |11}]
1/2
Vnazn
aallelloo C2
2n
(OVVII Vnaza
2n
exp f -
Σ j=it1
a;}
exp -
- j=1
a3 100 - 0-
Vniign
Thus, taking sum for i from n + to 2n, and applying Lemma 2 we get that
a:1|51loo CA
DE D/ 13)301 S
expf
Σ 1-4+1
a3}
Vnaina
2n
(Ca VILV
2n
expl
a Σ
ag
1100
0"
Vnazn
4
1=
j=1
| C
(CR V1)n
2n Σ
exp(
a3)
0*11
/n022a2
02n
j=1
11//
C2
(CA
V1)n
expl
Σ
ag 11100 8-1l
||
C2
(CA V1)m 3/4
exp
-
Σ
ag
} 110
0- (64)
Here in the last line above we used a particular form a = co/ Vk, and relied on the bound
2n
3/4
exp
a
Σ a3} 11.
jmn+1
which is guaranteed by the lower bound on the trajectory length n of the form
n
log n
2(V2 1)aco
Now we proceed with D3 Dbb,.), Using its definition in
The latter condition is guaranteed by A4 we get
48
2n
D3- (b,i)
1
(w: ( - 8*) +
1
(wk - (0 (b.i)
k=++1
Since the latter term is a martingale-ddifferenee, we obtain that
C2
C
2n
Eb[l D
- 1 -07
E
0(b,50 [2]
n
k=it1
22
C2
E 0110p - +
14-1 1-
E El x-
0 0/009113
k=it1
2
C 2n
19ll - 0 11-11 +
0
1- +
E -
00000)
n
n
k=
36

---

Hence we obtain, using
63
together with the definition of S2,, that
|E C*
a--1lellee C log C
D3
1|.001199
$
04
+
exp(
-a E at 0100 - 0-1
na
on
C +
1
C
2n
k-1
+ (C) v1)a
II - an. /4) 8¹11
Σ
expl
Σ a²}
a
2
==1
1=i+1
j=it1
71
(65)
Considering the latter term in the sum, we obtain
aellell
C
(CA vIJi
Ti
Σ On expl
af} +
Σ
expl
aj31100
0-12
n02n
2
k=H+1
j=1+1
k=i+1
j=1
(C
VIJi
expl
a
1 110 1-1
0jj
na
70022
2
j=l
Thus, summing the equations
665 for from n + to 2n, we obtain that
2n
2n Σ
0
E
C
Var-ille|loe
CA logn
Vaileel>o CA Vna3/2
Σ
E
D3
11)22/2
Vna3/2
v an
i=n+
C V1
2n
exp
a Σ
}
110
-0
2
1=++1
t=1
8
VI)I|s|l
1/4
log
+
C
A
vI
exp
a Σ
as
110 - 0*
a3/2
2
t=1
(66)
Using now the definition of D1 in 48) and Minkowski's inequality, we write
2n
(1
k-1
D
[ - 11600)111111
Σ
exp(
Σ
az}
Vn
a
4
A=i+1
j=1+1
ai/lello0 C2
2n
k-1
Σ
ak exp
Σ a;}
Vna
4
k=i+1
j=it1
(C² vI)Vi
Σ ag exp
Σ
aj } 1100 0-
Vn
k=i+1
1=1
0slle|1oc C2
(C2 VINE
exp
Σ
aj }100 11100 - 0-1
Vna²
Vna
==1
Thus, taking sum for from n + to 2n, we get
2n
asllelloc C²
2n
i 2 j=1
D1 1 12
Σ
exp
a 10 0
Vna²
Vna
i=nt1
|
C2
(Ca vI)
a n Σ
+
exp
a } 00
0+11
(67)
a²
a²
j=1
37

---

Similarly, with the definition of D in
48 we write
2n
2n
(As A)r + 1 } (0 -(000))
D3
D ((000)
(A&
A)
Σ
Vn k=i+1
vn
A=i+1
(A A)T
(09 -(0.0))
T2
2n
A) - P (09 010.0)
(Ax
k=i+1
Now we bound the terms T2 and T3 separately. Indeed, for the term T2 we get, applying the definition of the set Q4 that
C log n aaa
E
x
C log"n) n) E² [011 0.6.00113
n
C2 log
1b110 glb.1) ||2]
2
nea;
In the above bounds we have used that ag S alogn For the term T3 we get, applying Lemma 10 that for any vector Rdd.
2n
2n
R-1 1
Σ (Ax
(T) 1+1--1 Pi-1h-
(Ax 1a 1)A,I 2
11122-12 V
k=1-1
k=i+1
1=it1
2n-1
) Acl A it1e-11
aelw: 1)
Σ
(Ax A)TesIa
k=(+1
From the above representation obtain, using the definition of the set Q4. that
S
C2
2n-1
af
2
C2 log
+ C2 log²n
n)
exp
a
Σ
8-1
as
}
- -0.00013
acp
j=+t1
C4
2n
Oee
log
exp
Σ
6-1
aj
E 1100 - (1.6
a
4
j=it1
C4 n
logn
11.
Combining the above bounds, we obtain that
C logn
(1
C2
1 D3 - 11
Reb 1110
-0/b0011
+
03
C9 log n naca
01.00)121
38

---

where we have additionally used that a, sa/C3, Thus, using the upper bound 66
we obtain that
2n
IIII (b:00 13132//2
1m++1
2n
CA Vlgg a: C
2n
CA Cavlog n
Σ
(C
vIvv -
/0://4)1000- 1*1l
Va,an
a
Vajan
im++1
im++1
j=1
C |E|10
1/4 Vlogn
23/2
+ (C V1) Vlg
2n
a exp
a3) expl-22
Σ II (1- (1-00//4))1000 0'1 j=n+1
a al/2022
3/2
aj
2n
1=1
imn+1
C T6 S
n 1/4 Vlog++ +
(CA VI V1)m3/A/oogg
Vlg
n
exp
a
a3b1100 - 00
(68)
2/2
2/2
4
j=1
Now it remains to combine the bounds outlined above in 664. follows.
666
67
and (68)
and the statement
D Proof of stability of random matrix product
D.1 Proof of Proposition]]
1
The fact that there exists unique matrix Q, such that the following Lyapunov equation holds:
A T + QA =
(69)
follows directly from 54 Lemma 9.1, P. 140]. In order to show the second part of the statement, we
note that for any non-zero vector J E Rdd we have
(A) Q(I aA)a x Qx
(A (ATQ +QAJæ
2²2 T A QQA
a
x. TQQ
xT Qx
Px
x A ATQAA
a x Qu
x Qu
< Amin())
||
+ a²
|QQ1
Amin (Q)
- aa
where we
1 Amin (P)
a Amax (Q)
and used the fact that a S az.. where a is defined in 77
D.2 Proofs for auxiliary results products of random matrix
In order to bound the moment B[] - 0* [[P], we first prove a stability results on the products of random matrices I mek arising in the I.SA recursion. Towards this aim we first introduce some notations and definitions. For a matrix B E Idddd we denote by (o+( its singular values.
For 2 1, the Shatten q-norm of B is denoted by |Bl,, = (Σin (BB) For q. 2 and random matrix X we write ||X
[|]||||
Our proof technique is based on the stability
u.p
results arising in [29]. see also 16
Lemma 12 (Proposition 15 in [6).. Let (Yr) be an independent sequence and P be positive
definite matrix. Assume that for each E. N there exist me E (0, 1) and og > such that | Y e) e)l? S
1 - me and YY: - E S σg almost surely. Define Z = I Y.
for k 2 1 and
starting from Zo Then, for any S q S p and k 2
&
12 p.g 1z
I EP II (1 me + (p 1) 2-122221222 1/2112 p.g
12..
(70)
{=1
39

---

where we recall that Kp (P) (P).
Now we aim to bound I' m defined in 27) using Lemma 12
We identify the latter with Im Ye.
where Y,
Ag é 1, and Yo
Applying the bound (8). get ||[[y]]|
||| - a 12 S 1 - aag. Further, assumption A implies that almost surely,
,
E|Y/lll = 0z A Allo I oee/ CA bqoe.
Therefore, (70) holds with me aag and oe baae. As ||[||p d we obtain the following corollary.
Corollary 3. Assume A and 2 Then, any ar E [0, aool. 2 S q S p. and 1 S m S k, holds
k aad (p 1)02a2)
B1/9
[| mik 19 S [T makk llp.s I VKQdu/
II (1
t=
where Oloo was defined in and bQ
KR CA.
Corollary 4. Assume holds that
and
Then for any 2 5 S log n, and any 2 n, 1 m S kr
E U mi [1] s / -(a/2)
af
(71)
t=m
where Oo is defined in Moreover,
V
[|[ mikk [1 S vaQe
aci
(72)
Proof. We first apply the result of Corollary setting bq = /ni CA. that
Indeed, for 2 and any 2 q S p. it holds,
B [|I m= VFQd=/P
(1 aa4 + (p- 1))38))))
t=m
S
V /9 exp
ar + (p 1)63 a
Σ at
Amm
mm
Note that, setting p- = log n, and provided that n satisfies
we easily obtain that, for 2 n/2,
(log (logn)bza < aor/2.
(73)
Hence, for m 2 n//, we have
E [[] mikk [1]] S VFiee
ar)
t=m
and the statement follows. Suppose that n/2. In such case have, applying (73). that
B// [|[ m:k [19] 5 /
ar + (logn)b2 2)
Σ
or
t=m
az + (log m)bg
Σ
((a/2)
Σ at (74)
a
exp
t=n+1
and we need bound the first term in the product. We first consider as = co 1 inequalities
1/2 and use the
n
dx
^ (fre) dr dr)
x ))= (1+ + log m m 1m1)
n m) (log
+
-
(75)
t=m
m
x
40

---

and
1 dæ
Σ
2(vn - vm).
(76)
VI
t=m
Thus, it is enough satisfy the constraint
(3 logn - m) - acoo (i -vm)
Since m < n/2, it is enough to ensure that
(1 + log n (log & acolVn v nn/2)
or, equivalently,
(1 + log n) log
a - (/1))/v2)
which is granted by A3 Combining the above bounds in (74). we obtain that the lemma's statement
(71) holds for the step size o = cu/e1/2. Similarly, for a = cu/ with y E (1/2; 1), we get for
m n22 that
E [ mirk 199] ViQe exp( - Σ at)
t=
since the relation inequality
73 holds, Similarly, for < n/2,, the desired upper bound would follow from the
dæ
(m 1y 24
1
22
22
27 -
24
t=
m
together with an inequality
(log n )1
S (1 (11/2)--7)
27 -1
The latter inequality can be re-written as
n
200b2
logn
- (1/2)
which is also granted by A3 Combining the above inequalities implies that (71 holds for ae Co/ lr
The bound (72) can be immediately obtained from (71) using the fact that c < 1 x 1 for x E []:
Corollary 5. Under conditions of Corvllary 4 it holds with P probability at least 1 1/n² that
mackl |l I Vriqe" exp exp ((a/2)
Σ at
t=m
and
ady 4
[aack
S V
t=
Proof. It is sufficient choose 2 2 and use Markov's inequality together with the union bound.
Proposition 7. Assume A A A3 holds for any n S m < 2n, that
with 7 1/2, and A4
Then on the Ds defined in 47
[E 1:k 11313
3/2 9/8
Σ
tiQ
exp
a
t=m-1
41

---

Proof. Our proof relies on the auxiliary result of Lemma 13 below together with the blocking technique. Indeed, let represent
- Nh +r,
where r < h and à = h(n) is a block size defined in (18). of bootstrap weights Wm++,.-- WKk,
Then we obtain, using the independence
Wk, that
[E** + 11 m
- [B r
15k 11 1/)1//2
N
m+1+ 1) iu 111l 1/2 (EbiIr
m+1+ Nock [12]]
kk
==1
S VFQ exp
ae
[
m+1+N 121] 1/2
exp
Oe
Emm++1+ Nack
In the last inequality we applied Lemma 13 to each of the blocks of length h in the first bound. remains upper bound the residual terms. Since the remainder block has length less then h, we have due to 8T (which holds according to A/4), that
exp
Or S exp
aooo a }
S e//8
1 Nack
where the last inequality is due to Proposition
I
Next,
& II
E I
m+ m++1 N4. 1111
1/2
S KQ
E III a A.)
I'm m 1- Nhik
k
S KQ
II
E [E + are well 13/2131/2
Amm 1- Nhik
S KQ
II
EE* + Bor/we/| CA + C2
t=m-1- 1-Nhck
Since
E
well
S
E [wya
S
E
W 2 + Var wa = v2.
we get from previous bound
1/2
II
(1 2V CA +2a 1/2
KQ
8=m Com-I-NA -Nick
V2CA
Σ
au S Kgee coh/ snee,
Ki exp
4=m+++Nick
where in the last line we additionally used (19)
Lemma 13. Assume
A 2
A3 with 1/2, and A4
On the set Os defined in 47 it holds for
h(n) defined in 18) and any m E [n; 2n h1. that
m++h
1/2 m+1m+th [1@1]
a
Σ
< exp
a8
f=m++1
Proof. Recall that we the notation Eb[] E(. 2 where z (Zi...,, Zzn) the random variables used in the construction of the iterates {OA Jskksn in [I].
Let h N be block length, which value will be determined later, and consider product
Tb
II (I aeweAe)
(77)
m-+ Lom
8=m+1
42

---

Expanding the product of matrices 77
we obtain
m++h
m
m+a
D mim+t =
Σ
A
S R
Σ Ł=++1
a.
Σ Em++1
oz(A, A) - R, (78)
8=
where S == ===mmm Ore(Wi- 1) A is linear statistics in {we) 1m+h the higher-order terms in the products
t=m++==+1 and the remainder R. collects
R
(-1)
Σ
Il
aig Wi, Aie
a=1
with If = ((1...... E {m +
h2 iq <...
< i.). We first consider the contracting
part matrix Q-norm. Indeed, applying (8). we obtain that
m+th
m +h
og S
8=m+1
<=m+1
Σm+h provided that h is such a manner that Lt=m+1 Oe I aso. where doo defined in 7 Hence, we get from the above inequality that for any u E Rd it holds that
m-+h
m+th
Σ
acA le (a/2)
Σ
Emm++11
Now we need to estimate the remainders in the representation 788
On the set S2 it holds that
m++ f
m+th
Σ
ar A)la 22CA VRQu
Σ
af log(2n").
ビ=
1=++1
Moreover, is straightforward to check that
m+th
E
[||| S CA KQ
Σ
8=
In order to bound the remainder term R. we note that
h
h-2 h
E
R [
h
a (2 (2CA)'K) 1/2 s (2Ca)
Σ
) (2+1)(
r/2
== (r
2=2
122 (2 P
m
exp 20m+1 CA KQ
1/21
2 (A))CA)ng0
m
2
To complete the proof remains to set the parameter in such a way that we can guarantee
CA VEQ
m+th
Σ a3
(1 +
a am41 /22 C2
koe
m-th
Σ aE
(79)
E=m++1
f=m+1
keeping at the same time the constraint
m4+h
Σ
ae
0.00
(80)
t=++1
Recall that ar ca/ Vt. Thus, using the bounds
75 and 76). obtain that
au (Vm + h Vm +12 2
aco (vm +h h- /m).
(81)
43

---

and
m++h
m+th
Σ
o
Σ
T
S c (log (m + h) - log m))
(82)
{=++1
8=++1
Hence, taking into account bound
81
and
(82 and
S 1. m.
the inequality
79
would follow from the
m+1
CA FRv log(m + h) log(m)
1 + 2 log((2)))
coh?
CA
kige
(V
a h m))
2m
2
(83)
Since log (1+2) S x for x 2 0 and cu C koO S 1, the latter inequality is satisfied if
CA FiQ
Vh
1+ 2 log((n2))
+
2m I
h
a
5mm vm)
Vm
2
Now we use one more lower bound
Ml /m(v3 12 - 1)h (V2 1)h
Vm m + ht m
mmmmlI+t h/m
Vm
which follows from an elementary inequality VI+ 1+ (V2 1)a, valid for S x S 1. Hence, 833 would from the inequality
Th 1+ 2 log (2n")
h2
al a(v2 1)h
RQ CA
+
(84)
2m
2 m
Setting h is such manner that
h
a(v
1)
m
2
inequality
84 would follow from
Vh
S a(v2 - 1)h
CA VEQ Vm
1 2log(2n*)
4/m
The latter inequality is satisfied, if the block size h satisfies
1/2 2 RiQ (V2 1)a
4 4CA
h >
(1 + 2 log (2n*))²
Thus, setting (nn) as in (18 all previous inequalities will be fulfilled, provided that
A(n)
a(v2-1)
vn
2
coh(n)
v/n
Here last inequality follows from (80) and the following simple bounds, where use that m 2 and VI+ x 5 1 + +x//2 2/2:
ath
n- dx S
20olVn h - vn) = chh
a <
Σ
a Co
Σ
VI
V
1=
t=
Now
78
implies that
m++h
E T
m+
+
1111 1/2
< (a/4)
Σ (=m+1
and the statement follows from an elementary inequality S e²
44

---

E Applications to the TD learning
Recall that the temporal difference learning algorithm in the LSA's setting can be written as
Os 0k-1 -as(An0s-1 bb), -ba))
(85)
where A and by are given by
A (
(86)
by ((s))T(SK) ax)
Recall that our aim is to estimate the agent's value function
V (8) = E ( ax) 0x)]80 [800]]]]]
where op (-15kk), and 8k+1 P(-(sk ag), for any k E N. We define the transition kernel under policy π
p (B|s) fA ((
(87)
which corresponds the 1-step transition probability from state to a set B B(S). We denote by
the invariant distribution over the state space S induced by the transition kernel (= (s) in (87). In
this case the TD learning updates (85) correspond the approximate solution of the deterministic system A b, where have set, respectively,
A E E (t (())) r
(88)
b E B (ew.
E.1 Proof of Proposition
2
first need to check that the matrix + A where is defined (88) is positive-definite. In order to show this fact closely follow the exposition of [61 Lemma 18] and [51] Lemma 5]. Define a random matrix A as an independent copy of A from (86), that is,
= (+)))((()))))))))))))))))))))))) - >ppss))
where μl, and s' (+(s). With the definition A, we get that
+ T = ((s)((((s) - -(p((((()>)(6))))))))))))))))()) T + {v(()) - (p)))
= 2p(s)p(s)) - ((p(s)((s') ((0)))((s)) (2 (2))) rp(ss) ((()))
where used an elementary inequality uv + vu T (wu + vvu valid for any u, U. Rd Hence, with the definition of Sp in 222. we get
A+A E A A 2(1 7)2
(89)
set P Á + A in the right-hand side of the Lyapunov equation 69. Obviously, Q = is solution to the corresponding Lyapunov equation
Hence, Á T is positive-definite, and
T + -A Á
Moreover, applying 61 Lemma 18], we obtain
A T A < E A A 3 71+7)
(90)
Hence, we get for a S (1--7) (111))/(1++++ and applying
89 and (90) that
((-AA)((1oal)
= T a(A A) 0 A A
= I 2a(1 - 7)Σ3 + a + 2
3 I a(1 - 7)
3 - (1-a(11 - -1)))))) Mumin (E
Hence, the bound ( holds with (1 Ammin (2ip) and ax - (1-1)/(11 +
45

---

Experimental details for the TD learning
Here we provide some details on numerical experiments. Code run experiments provided in htttp:://gihubb. ccmm//sssaasooov/ootttttttt
For the considered Garnet problem we choose the policy in the following way. For any a E A, we
((()
{(|ss)
Σ AA U
where the U.(d) are independent random variables following uniform distribution U(0, 1]. Here assume that each action a E A can be selected at any state ......,,g],, We generate an instance of Garnet problem with mentioned parameters, and find analytically the true parameter 0* In order to estimate the supremum
A sup P( P nl S <z)
(0, IN.,, and show that this supremum scales as n for other powers y. We first approximate true probability P( /2 7l I .x) by the corresponding empirical probabilities based on sample of size M >> We fix M = 5 10". We choose trajectory lengths
1/4 1/4 when 7 = 1/2 and admits slower decay
E (1000, 3200, 6400, 12800, 25600, 51200, 102400, 204800, 409600, 819200, 1638400).
fix the length of burn-in period rig = 102400. and generate N = 6553600 independent trajectories starting the fixed point 0g N= We set the learning rate schedule as ag co/k k* and try different 4.0. Unfortunately, even the chosen order of trajectory length
values 7 E (0.5, 0.65, 0.7), and n seems to be insufficient in order to significantly distinguish, for cxample, between 7 0.5 and y 0.65. However, learning rate schedule with faster decay performs worse in terms of An. Note that the current experiment is already rather computationally intense for artificial problem and takes about 12 hours of compute Core i9 10920x processor with 12 cores with 3.7 GHz.
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Main results are, respectively, the ones of Theorem 2 and Theorem S their
statements complete and supported by the proofs in the Appendix section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our setting related to the LSA problem, and not more general non-linear stochastic optimisation problems. We highlight the potential gener- alizations of Theorem 2 to the non-linear setting and discuss why generalizing Theorem might be more challenging. We also discuss the limitation related i.i.d. observations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
47

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All our theoretical results are provided with references to assumptions, that are stated Section and Section 4 All results are given with proofs, that are correctly referenced for each theorem and corollary.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Numerical results are stated with a complete description of the environments that are used, as well the precise sets of hyperparameters that used. The code (in Python) is provided as supplementary with the paper. making easy for one to reproduce our numerical experiments. At the same time, tracing the second-order terms in the normal approximation is computationally involved and can take sufficiently large amount of time.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
48

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: All code is open source, link github repository is included.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc cc/
for more details.
While we encourage the release code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
praps.cc//ubllicguuddee Coape///ooeSSbummiee www.iissssooooooo swt.:ooiiisiooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The algorithm used in the numerical experiments are exactly the algorithms described in the paper. The Garnet environements are given with the parameters used for generation, and with reference to the original problem.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Unfortunately, error bars for computing the second-order terms in normal approximation are quite computationally intense, moreover, tracing the terms of order 1/1 requires quick increase of trajectory length
49

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If eπror bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All necessary information to reproduce experiments is provided in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httt://nnuiippp http///uris..pppplllie.eeeee ccc/
Answer: [Yes]
Justification: This paper is of purely theoretical nature, and the proposed methods do not deal with sensitive attributes that could induce unfairness or privacy issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
50

---

Answer: [NA]
This paper is of purely theoretical nature. We do not foresee any societal harm from the proof of non-asymptotic bootstrap validity and normal approximation bounds in Kolmogorov distance.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Not applicable: existing assets used.
Guidelines:
The answer NA means that the paper does not existing assets.
51

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pattasets.paperssst.. paperswi thcode. com/ datasets
has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Not applicable: paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not applicable: paper does involve crowdsourcing nor research on human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
52

---

Not applicable: paper does not involve crowdsourcing nor research on human subjects.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "dlNgq6TNOB", "reviewer": "Reviewer_DkFj", "summary": "## Overview\n\nLet $Z, Z_1, \\dots, Z_n$ be i.i.d. random elements with a common distribution $\\pi$ over $\\mathbf{Z}$. Given $A : \\mathbf{Z} \\to \\mathbb{R}^{d\\times d}$ and $b : \\mathbf{Z} \\to \\mathbb{R}^d$, the goal of the LSA procedure is to find the unique solution $\\theta^\\star$ of\n$$\\mathbb{E}\\left(A(Z)\\theta^\\star - b(Z)\\right) = 0. $$\n\nGiven a decreasing sequence of step sizes $\\alpha_k$ and a starting point $\\theta_0$, the standard LSA is given by\n$$\\theta_k = \\theta_{k-1} - \\alpha_k(A(Z_k)\\theta_{k-1} - b(Z_k)) $$\nand the Polyak-Ruppert averaged LSA is given by\n$$\\overline{\\theta_n} = \\frac{1}{n} \\sum_{k=n}^{2n-1} \\theta_k. $$\n\nThe authors provide Berry-Essen-type bounds for the Gaussian approximation of $\\sqrt{n} \\left( \\overline{\\theta_n} - \\theta^\\star \\right)$ and for the corresponding multiplicative bootstrap process. Namely, for the Gaussian approximation result they upper bound the quantity\n$$\\rho_n = \\sup_\\text{B convex} \\left| \\mathbb{P}\\left( \\sqrt{n} \\left( \\overline{\\theta_n} - \\theta^\\star \\right) \\in B \\right) - \\mathbb{P}\\left( \\Sigma_\\infty^\\frac{1}{2} \\eta \\in B \\right)\\right| $$\nwhere $\\eta \\sim \\mathcal{N}(0,I_d)$. And for the bootstrap approximation result they upper bound\n$$\\rho_n^b = \\sup_\\text{B convex} \\left| \\mathbb{P}\\left( \\left.\\sqrt{n} \\left( \\overline{\\theta_n^b} - \\overline{\\theta_n} \\right) \\in B \\right| Z_1, \\dots, Z_{2n} \\right) - \\mathbb{P}\\left( \\sqrt{n} \\left( \\overline{\\theta_n} - \\theta^\\star \\right) \\in B \\right)\\right| $$\nwhere $\\overline{\\theta_n^b}$ are obtained from a multiplier bootstrap process. It is interesting to notice that this multiplier process can be evaluated online without keeping a history in memory.\n\n## Overall proof arguments\n\nTo provide the Gaussian approximation result the authors write\n$$\\theta_n - \\theta^\\star = (I - \\alpha_n A(Z_n))(\\theta_{n-1} - \\theta^\\star) - \\alpha_n \\varepsilon(Z_n) $$\nwhere\n$$\\varepsilon(z) = A(z)\\theta^\\star - b(z). $$\n\nThe authors observe that $\\varepsilon(Z_n)$ can be viewed as a noise, which is assumed to be bounded. Meanwhile, the operator $ I - \\alpha_n A(Z_n) $ is a random perturbation around $ I - \\alpha_n \\mathbb{E}A(Z) $, which is shown to act as a contraction in an appropriate norm, provided that $-\\mathbb{E}A(Z)$ is Hurwitz. Thus, when one take the PR average the noise is expected to behave as the sum of i.i.d. noises and the contraction term must shrink. This is formally done writing the PR average in the form of Theorem 2.1 [reference 60 of the paper] and bounding the terms given by the latter theorem.\n\nThe proof the bootstrap approximation result follows the standard practice in this literature:\n- First, conditionally on the sample, a Gaussian approximation is obtained relating the bootstrap to a Gaussian with its covariance.\n- Second, a Gaussian comparison theorem relates the latter Gaussian with the desired Gaussian, with some concentration results being used to bound their difference in high probability.\n\n## Main claims and observations\n\nThe authors show that taking a step size of order $\\frac{1}{\\sqrt{k}}$ yields the best possible convergence rate in their bounds. They provide empirical evidence that this rate is optimal.\nThey also claim to be the first ones to fully provide a non-asymptotic bootstrap approximation result.", "questions": "Some observations:\n- Line 54 has a typo in \"Berry-Essee\".\n- In Equation (15) the $\\ell$ can be removed from $\\theta_{k}^{b,\\ell}$ to enhance clarity. It is only used to explain that to evaluate the probability in practice one must run several samples of the bootstrap process.\n- Line 263 has a typo in \"date\".\n- The Equation after line 303 is using $\\phi$ instead of $\\varphi$.\n- Line 307 asks for a sequence of \"TD(0) updates\", what does the \"(0)\" stands for?\n- Figure 1 lacks x and y labels. The legend can also be improved for clarity.", "limitations": "The authors adequately addressed the limitations and the potential impact of their work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper seems to be the first to provide non-asymptotic Gaussian and bootstrap approximation bounds for LSA. Their assumptions are quite mild and are in line with the ones made in similar papers in other domains. For instance, assumption A.2 is similar in nature to the boundness assumptions and the strong-covariance assumption made in [A]. The paper is mathematically sound and poses interesting research directions. I'm particularly curious about the convergence rate of $n^{-\\frac{1}{4}}$ suggested by their theoretical results and supported by their experiment. The proposed application to policy evaluation in RL is also interesting. Finally, I point out that the code on the supplementary material was easy to reproduce.\n\n[A] Chernozhukov, Victor, Denis Chetverikov, and Yuta Koike. \"Nearly optimal central limit theorem and bootstrap approximations in high dimensions.\" The Annals of Applied Probability 33.3 (2023): 2374-2425.", "weaknesses": "The main claim of the paper is that their bounds suggest an optimal convergence rate of $n^{-\\frac{1}{4}}$ when taking $\\alpha_k = \\frac{c}{\\sqrt{k}}$. The bottleneck of this convergence rate comes from an application of Cauchy-Schwarz inequality, the boundness of $\\varepsilon$ and the MSE bound on $D$ given by Theorem 1. Meanwhile, the authors also provide experimental evidence that this convergence rate is indeed optimal (although not considering gamma values below 0.5 in Figures 1 or 3). A counter-example or a deeper discussion on this convergence rate would be beneficial to the paper: is it an artifact of the proof or is there reason to believe it cannot be improved?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the referee DkFj for the work and for the positive feedback! Next, we answer the issues raised.\n\n**Bottleneck of the convergence rate and counter-example or a deeper discussion on this convergence rate** \nThis is indeed a very important question. First of all, the analysis of Theorems 1-3 can be adjusted for the whole range of step sizes $\\alpha _k = c_0 / k^{\\gamma}, \\quad \\gamma \\in (0,1)$. The only modification would affect lower bounds on step size $n$ in the assumptions $A2$ and $A3$, respectively. There is a reason to believe that the moment bound of Theorem~1 is sharp, that is, the best possible bound on $\\mathsf{E}^{1/2}[\\|\\|D\\|\\|^2]$ is of order $n^{-1/4}$ when setting $\\gamma = 1/2$. The corresponding lower bound on moments of the remainder (in $n$) terms can be found for the setting of strongly convex optimization in [Li et al, 2022]. We expect that this result can be generalized for the LSA setting as well. However, the tightness of the moment of Theorem 1 bound does not directly imply the tightness of the bounds of Kolmogorov distance $\\rho_n^{\\text{(Conv)}}$. It is hard to say if the cross-correlation terms appearing between the linear statistics $W$ and non-linear statistics $D$ in the bound (13) are sharp. See also the general discussion on this topic.\n\nWe leave further exploration of this question as a promising direction for a future work.\n\n**Typos and misprints** \nWe thank the referee for careful reading of the manuscript and will fix the raised issues in the revised version of the paper. We will also re-generate Figure $1$ with longer trajectories and change legend as suggested by the referee in order to improve readability.\n\n\n**Line 307 asks for a sequence of \"TD(0) updates\", what does the \"(0)\" stands for?** \nIn general one can perform a policy evaluation using the whole family of TD($\\lambda$) algorithms, where $\\lambda \\in [0,1]$. One can find the details in the paper [Tsitsiklis and Van Roy, 1996]. However, when we choose an instance of the algorithm with parameter $\\lambda > 0$, corresponding dynamics of parameter updates $(\\theta_k)_{k \\geq 0\\} $ becomes non-Markovian. TD($0$) is arguably the most popular algorithm of this family, and the only one which falls directly into the stochastic approximation paradigm. \n\nReferences:\n[Li et al, 2022] Li, C.J., Mou, W., Wainwright, M. and Jordan, M., 2022, June. Root-sgd: Sharp nonasymptotics and asymptotic efficiency in a single algorithm. In Conference on Learning Theory (pp. 909-981). PMLR.\n\n[Tsitsiklis and Van Roy, 1996] Tsitsiklis, John, and Benjamin Van Roy. \"Analysis of temporal-diffference learning with function approximation.\" Advances in neural information processing systems 9 (1996).", "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": "hg7nSYTiXp", "reviewer": "Reviewer_ew5L", "summary": "The present paper studies linear stochastic approximation with martingale difference noise and diminishing step-sizes. The authors obtain Berry-Esseen bounds for the parameter sequence with Polyak-Ruppert averaging as well as a generalization of finite-time bounds for estimation confidence intervals for parameters in LSA. The obtained Berry-Esseen bounds are illustrated by a TD learning numerical example.", "questions": "- Could the authors clarify if using Polyak Ruppert averaging is necessary to obtain such a Berry-Esseen bound? It would be exciting to see bounds for unaveraged estimates as well.\n\n-Could the authors  run  the experiment  supporting figure (c) for longer to see if the curve with \\gamma = 1/2 willnot continue to go upwards eventually?", "limitations": "The authors clearly identified the limitations of their results through a clear list of assumptions", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "To the best of the reviewer's knowledge, both of the contributions are novel. In particular, I believe that this is the first Berry-Esseen bound type bound to be obtained for general linear SA, which is is exciting to see.\n\nThe assumptions, contributions and approach to analysis are objectively identified. The authors also did a great job in providing discussions/remarks/intuition for their results.\n\nThe paper is well-written but some proofreading is recommended.", "weaknesses": "Although the authors did a good job in outlining the scope and contributions of the paper, the analysis and main text are hard to follow given the number of symbols and equations. It is easy for a reader to get lost/distracted midway and it is very hard to keep track of the definitions of each of the terms \n\nI understand that this is an issue with theory papers like this, but would encourage the authors to move unnecessary terms or inequalities to the appendix (e.g. (9) in A3. The exact lower bound adds very little in the main text in my opinion. Its definition could have been postponed to the Appendix.)\n\nThe numerical experiments are also weak since many of the plots are not related to the contributions of the paper itself. Plot c seems to be the only one directly related to the theorems of the paper, but it still does not illustrate the theory that well. Maybe including a plot of C k^{-1/4}  to plot (b) where C is a constant for comparison could help in inferring convergence rates.\n\nAlso, there is a mistake in the label of Figure 1. Subfigure (b) is mentioned twice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the referee ew5L for careful reading of the manuscript and valuable suggestions for presentation improvement. Next, we answer the issues raised.\n\n**The analysis and main text are hard to follow**\nIndeed, there are technical details in the main text that complicates reading, yet we were willing to be precise and state exact lower bounds on sample size $n$, especially in $A3$ and $A4$. In the revised version we will modify eq. $9$ and eq. $17$, switching to $\\mathcal{O}$ - notation, and move precise bounds to appendix, as was suggested. \n\n**The numerical experiments are also weak since many of the plots are not related to the contributions of the paper itself** \nWe respectfully disagree with the referee - the figure (a) explains, why step sizes $\\alpha _k = c_0 / k^{\\gamma}$, $\\gamma > 1/2$ are less preferrable. In this case the plot (a) illustrates slow convergence of the rescaled error $\\sqrt{n}(\\bar{\\theta}_n - \\theta^*)$, which is the reason which explains slow convergence of the respective rescaled approximation errors on subfigures (b) and (c). For the new plot (see the attached PDF file veasible for all referees) we included the expression $n^{1/4} \\Delta_n$ with and without logarithmic scaling. Thus we expect that this quantity converges to a constant when $\\gamma = 1/2$ and grows with $n$ when $\\gamma > 1/2$. We will also consider running longer experiments, as for now we have included a figure with one more observation (added point corresponding to $n = 3 276 800$ observations). \n\n**Could the authors clarify if using Polyak Ruppert averaging is necessary to obtain such a Berry-Esseen bound?**\nNo, in principle it is not necessary, but the result will be slightly different in this case. It is known that (see e.g. [Fort, 2015]), that the corresponding CLT for the last iterate can be written as\n$$\n\\frac{\\theta_k - \\theta^*}{\\sqrt{\\alpha_k}} \\to \\mathcal{N}(0,\\Sigma_{\\text{last}}),\n$$\nwhere the covariance matrix $\\Sigma_{\\text{last}}$ is different from $\\Sigma_{\\infty}$. Then, using the perturbation-expansion technique from [Aguech et al, 2000], we write that \n$$\n\\theta_n - \\theta^* = \\tilde{\\theta_n}^{(tr)} + J_{n}^{(0)} + H_{n}^{(0)},\n$$\nwhere $\\tilde{\\theta_n}^{(tr)} = \\Gamma_{1:n}(\\theta_0 - \\theta^*), \\quad \\Gamma_{1:n} =  \\prod_{i=1}^{n} (I - \\alpha_{i} A(Z_i) ) $ is the transient component of the error, \n$$\nJ_{n}^{(0)} = -\\sum_{j=1}^{n}\\alpha_j (I - \\alpha_j \\bar{A})^{n-j} \\epsilon(Z_j) \n$$\nis the leading (with respect to step size) component of the error and $H_{n}^{(0)}$ is a remainder term. Thus, using the argument from the current submission, $\\tilde{\\theta_n}^{(tr)}$ is exponentially small in $n$, $J_{n}^{(0)}$ is the linear statistics in $\\epsilon(Z_j)$ that guaranttes asymptotic normality after re-normalization, and $H_{n}^{(0)}$ is the remainder term. It can be shown that \n$$\n\\mathsf{E}^{1/2}[\\|J_{n}^{(0)}\\|^{2}] \\lesssim \\sqrt{\\alpha_n}, \\quad \\mathsf{E}^{1/2}[\\|H_{n}^{(0)}\\|^{2}] \\lesssim \\alpha_n.\n$$\nThus, applying similar technique of randomized concentration inequalities (formula 13 in the current submission), we will obtain the Berry-Esseen bound for $\\frac{\\theta_n - \\theta^*}{\\sqrt{\\alpha_n}}$, which should scale as $\\sqrt{\\alpha_n}$.\n\n**Typos in figure labelling** \nThanks, we will correct this typo and will perform additional proofreading for the revised version of the paper.\n\n**References:**\n\n[Aguech et al, 2000] Rafik Aguech, Eric Moulines, and Pierre Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM Journal on Control and Optimization, 39(3):872–899, 2000.\n\n[Fort, 2015] Central limit theorems for stochastic approximation with controlled Markov chain\n411 dynamics. ESAIM: PS, 19:60–80, 2015.", "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": "gLGGZYdq0A", "reviewer": "Reviewer_uNZU", "summary": "The paper presents advancements in the theoretical understanding of the linear stochastic approximation (LSA) algorithm. \n\nIt establishes the Berry–Esseen bound for the normal approximation of Polyak-Ruppert averaged iterates, achieving an optimal rate with an aggressive step size of $\\alpha_k \\approx k^{-1/2}$. Additionally, it demonstrates the non-asymptotic validity of confidence intervals using a novel multiplier bootstrap procedure, marking a first in this domain. \n\nThe practical utility of these theoretical results is showcased through applications in temporal difference (TD) learning for reinforcement learning.", "questions": "See the Limitations.", "limitations": "1. **Missing References on Statistical Inference**: Statistical inference for nonlinear stochastic approximation has been considered by [1*] and [2*], which is highly related to this manuscript but hasn’t been cited. Note that [1*] provides a Berry-Esseen-like bound for the whole trajectory rather than the averaged iterates. These references could be cited after [36] in line 116.\n     - [1*] Li, Xiang, Jiadong Liang, and Zhihua Zhang. \"Online statistical inference for nonlinear stochastic approximation with Markovian data.\" arXiv preprint arXiv:2302.07690 (2023).\n     - [2*] Li, Xiang, et al. \"A statistical analysis of Polyak-Ruppert averaged Q-learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\n2. **Assumption on Bounded $\\epsilon(z)$**: Theorem 1 requires that $\\epsilon(z)$ is uniformly bounded, which is a strong condition. Is it possible to relax this condition to a weaker one, such as $\\epsilon(z)$ only having a finite order of moments (such as the fourth order moment or smaller)?\n\n3. **Tightness of Derived Upper Bounds**: The paper provides upper bounds, but it would be insightful to discuss the tightness of these bounds. Are there any thoughts or conjectures regarding potential lower bounds?\n\n#### Minor Corrections:\n\n1. **Figure 1**: The last subfigure should be labeled as (c).", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Theoretical Advancements**: The paper makes theoretical contributions by establishing the Berry–Esseen bound for the normal approximation of Polyak-Ruppert averaged iterates. Though some previous works have done this in special cases before, this work differs from them in providing a tighter bound.\n\n2. **Good Clarity:** The paper is easy to follow and well-written. The proof seems correct (not checked very carefully).", "weaknesses": "1. **Strong Assumptions**: The requirement that $\\epsilon(z)$ is uniformly bounded is a strong assumption that might limit the applicability of the results. Relaxing this condition to weaker ones, such as finite moments, could enhance the paper's generality.\n\n2. **Missing References**: There are some missing references, see the limitations.\n\n3. **Discussion on Lower Bounds**: The paper focuses on deriving upper bounds but lacks a discussion on the tightness and potential lower bounds. Addressing this aspect could provide a more comprehensive understanding of the bounds' efficacy and limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the referee uNZU for careful reading of the manuscript and raising interesting questions. Next, we answer the issues raised.\n\n**Missing References on Statistical Inference** \nWe thank the referee for provided references and will add them to the revised version of the paper. \n\n**Strong Assumptions: assumption on Bounded $\\varepsilon(z)$**\nIndeed, the assumption of bounded $\\varepsilon(z)$ is strong, but can be partially relaxed. Following the stablity of matrix products technique, used in [Proposition 3][Durmus et al, 2021], we can generalize the moment bound for products of random matrices (Corollary 4) for the setting when the random variable $\\|\\|A(Z) - \\bar{A}\\|\\|$ has only finite number of moments.\nIn particular, finite $3$rd moment of $\\|\\|A(Z) - \\bar{A}\\|\\|$ (which implies naturally that $\\|\\|\\varepsilon(z)\\|\\|$ also admits only a finite $3$rd moment) is sufficient to obtain the first main result of the paper on the Berry-Esseen inequality (Theorem $2$). However, it will be not sufficient to prove the boostrap validity (Theorem $3$), since this result requires high-probability bounds on the product of random matrices $\\Gamma_{m:k}$. Yet there are two settings when we can generalize our results without the assumption concerning bounded $\\|\\|\\varepsilon(z)\\|\\|$:\n\n1. Random matrix $A(Z)$ is almost sure bounded, but $\\|\\|\\varepsilon(z)\\|\\|$ is sub-gaussian, or, more generally, for any $p \\geq 2$ it holds that\n$$\n\\mathsf{E}^{1/p}[\\|\\| \\varepsilon(z)\\|\\|^p] \\leq C_{\\varepsilon} p^{\\beta}\\,,\n$$\nfor some $\\beta \\geq 1/2$. In such a case, we can generalize our bootstrap validity along the lines of the current proof;\n\n2. The random variable $\\|\\|A(Z) - \\bar{A}\\|\\|$ is sub-Gaussian, and $\\|\\|\\varepsilon(z)\\|\\|$ is sub-Gaussian. In such a case, using the high-probability bounds outlined in [Proposition 3][Durmus et al, 2021], we can have a counterpart of Theorem $3$ up to additional powers of $\\log{n}$.\n\\end{enumerate}\nWe will add the discussion above the the revised version of the paper. \n\n**Tightness of Derived Upper Bounds**\nIndeed, it is a very interesting question to obtain the mathching lower bounds that can illustrate the fact that the rate $n^{-1/4}$ is indeed sharp. See the reply for all referees for details on lower bounds.\n\n\n**Minor Corrections**\nThanks, we will correct this typo and will perform additional proofreading for the revised version of the paper.", "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:
We thank the reviewers for their thorough feedback. We are pleased that reviewers deemed our contributions to the Berry-Esseen bounds for Polyak-Ruppert averaged LSA and non-asymptotic bootstrap validity as new. 

The general question, which was raised by the referees **DkFj** and **uNZU** is related to the tightness of our bounds and availability of certain lower bounds. We do not have a formal proof for the tightness of our bounds and highlight that it is an excellent research question. First of all, we believe that the moment bound on the remainder term $\|D\|$ in Theorem 1 is sharp in terms of its dependence in $n$, since similar results can be traced for the setting of strongly convex optimization in [Li et al, 2022]. However, the tightness of the moment of Theorem 1 bound does not directly imply the tightness of the bounds of Kolmogorov distance $\rho_n^{\text{(Conv)}}$. Second, the key bound (13) in our analysis writes as 
$$
\sup_{A \in Conv(\mathbb{R}^d)} | \mathbb{P}(T \in A) - \mathbb{P}(\eta \in A)| \leq 259 d^{1/2} \Upsilon + 2 \mathsf{E}[\|W\| \|D\|] + 2 \sum_{\ell=1}^n \mathsf{E}[\|\xi_\ell\| \|D - D^{(\ell)}\|]\,.
$$
where $W$ and $D$ are the leading (linear) and remainder part of our considered non-linear statistics. It is shown in [Chen and Shao, 2007], Section 4, that the $3$rd term in the above sum can not be removed. However, it is less clear if the same reasoning applies to the correlation term $2 \mathsf{E}[\|W\| \|D\|]$. At the same time, it is this term which explains the $n^{-1/4}$ scaling of the final bound. However, there is another evidence which suggests that $n^{-1/4}$ is a correct order. We can write the statistics of interest $T = n^{1/2} \bar{A} (\bar{\theta_n} - \theta^*)$ within the particular decomposition 
$$
T = \frac{1}{\sqrt{n}} \sum_{k=n}^{2n-1} \epsilon_{k+1} + \frac{1}{\sqrt{n}}\sum_{k=n+1}^{2n}(A_k - \bar{A}) (\theta_{k-1} - \theta^*) + R
$$
Here $R$ contains remainder terms of non-linear statistics $D$, which are of smaller order in $n$. The first two terms in the above sum forms a martingale with respect to the natural filtration, and it is known that typical Berry-Esseen rate in martingale CLT is $n^{-1/4}$, see e.g. 
[Bolthausen, 1982]. At the same time, the counterexample of Bolthausen has a special structure, which not necessarily falls into the structure of the leading terms above. To conslude, further investigations of lower bounds are needed, but available (incomplete) evidence from both moment point of view and martingale CLT suggests that $n^{-1/4}$ should be optimal.

We also attach a pdf file with slightly increased number of observations $n$ as suggested by the referee **ew5L**. We increased maximal number of observations by a factor of $2$ (till $3276800$) and added scaling of Kolmogorov distance by $n^{1/4}$ without logarithmic scaling of the $y$-axis to better highlight scaling of our approximation rate.

 We address the other more specific concerns directly in the rebuttal to each reviews.

**References:**

[Chen and Shao, 2007] Chen, L. H. and Shao, Q.-M. (2007). Normal approximation for nonlinear statistics using a concentration inequality approach. Bernoulli 13(2) 581–599.
[Bolthausen, 1982] Bolthausen, E. Exact convergence rates in some martingale central limit theorems. The Annals of Probability, pp.672-688, 1982.

Meta-review: The present paper proves normal approximation (CLT) and validity of a bootstrap procedure for the law of the Polyak-Ruppert averaged iterates of linear stochastic approximation (LSA). Their main results have n^{-1/4} convergence rates (up to polylogs and dimension-dependent terms) under reasonable assumptions. Intriguingly, the authors suggest that the magnitude of the error in their CLT might be optimal. 

The paper was generally well-received by the reviewers, with scores 5, 6 and 7. The issues raised in the revision period do not seem significant, and can be resolved in the final version. In that connection, I would encourage the authors to add their remarks on weaker assumptions to the text (cf. the response to reviewer uNZU). 

Overall, I believe the paper deserves to be accepted: the quantitative CLT is quite interesting, and the bootstrap results seem to be new.
Decision: Accept (poster)