Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
Authors: Alain Durmus
Eric Moulines
Alexey Naumov
Sergey Samsonov
Kevin Scaman
Hoi To Wai
Venue: NeurIPS 2021 Poster (2021)
Keywords: Concentration for products of random matrices
Bernstein-type bounds for Linear Stochastic Approximation
fine-grained analysis of Linear Stochastic Approximation
non-asymptotic analysis of Linear Stochastic Approximation

Abstract: This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of a linear system $\bar{A}\theta = \bar{b}$ for which $\bar{A}$ and $\bar{b}$ can only be accessed through random estimates $\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$.  Our analysis is based on new results regarding moments and high probability bounds for products of matrices which are shown to be tight. We derive high probability bounds on the performance of LSA under weaker conditions on the sequence $\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$ than previous works. However, in contrast, we establish polynomial concentration bounds with order depending on the stepsize. We show that our conclusions cannot be improved  without additional assumptions on the sequence of random matrices $\{{\bf A}_n: n \in \mathbb{N}^*\}$, and in particular that no Gaussian or exponential high probability bounds can hold.  Finally, we pay a particular attention to establishing  bounds with sharp order with respect to the number of iterations and the stepsize and  whose leading terms contain the covariance matrices appearing in the central limit theorems.

Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
Alain Durmus
Université Paris-Saclay, ENS Paris-Saclay, CNRS,
Centre Borelli, F-91190 Gif-sur- svettee France alain. durmus@ens--arrs--acll.
Eric Moulines
Alexey Naumov
Sergey Samsonov HSE University
Ecole Polytechnique and HSE University eric.
HSE University anaumovChse.ru
edu
svsamsonov@hse. ru
Kevin Scaman
Hoi-To Wai
INRIA and ENS, PSL University kevin. www.an@inria.....m
The Chinese University of Hong Kong htwai@se cuhk. edu hk
Abstract
This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of linear system AO b for which A and b can only be accessed through random estimates {(An, b,) E N*). Our analysis is based on new results regarding moments and high probability bounds for products of matrices which are shown be tight. We derive high probability bounds on the performance of LSA under weaker conditions on the sequence {(A,, b,,)
No) than previous works. However, in contrast, we establish polynomial concentration bounds with order depending on the stepsize. We show that our conclusions cannot be improved without additional assumptions on the sequence of random matrices {A, E N }. and in particular that no Gaussian or exponential high probability bounds can hold. Finally, we pay particular attention to establishing bounds with sharp order with respect to the number iterations and the stepsize and whose leading terms contain the covariance matrices appearing in the central limit theorems.
Introduction
This paper provides a detailed analysis of Linear Stochastic Approximation (LSSA) schemes which aim at finding solution 6* for linear system of the form Áo = b. In particular, we analyze LSA with fixed stepsize by the recursion
which consists in defining sequence of estimates (0, n E N) for d*
Ont1 = 0,, aa(AA+10 - bn+1). n E
(I)
where {(A,, bw) E N*) is sequence of i.i.d. random variables used as proxy for À E dddd and E Rdd which are typically unknown. This class of algorithms and the corresponding setting have long history and important applications in signal processing such channel equalization and echo cancellation [3, 23]. has renewed interests in machine learning and computational statistics especially for least-square estimation and Reinforcement learning (RL) [4, 37]. The recursion (1) has already been studied in depth in several works which derive asymptotic [33, 23, 6, 3] and non-asymptotie [35, 27, 2, 20, 21, 5, 24, 36, 10, 13] guarantees.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, in most cases, there is a consistent gap between these two types of analyses. While asymptotic analysis gives important insights on the qualitative convergence of (1) based on statistical key quantities of the problem on hand, they do not provide finite-time convergence, or high probability bounds, necessary to obtain non-asymptotic confidence sets, see [28, 11] and the references therein. On the other hand, non-asymptotic studies are in general too coarse and lose significant statistical information in their derivation. Further, their upper bounds are generally loose when used in predicting the actual performance of LSA. We aim at filling this gap and provide conditions on {(An, b,) : n E ] ensuring tight high probability bounds on the sequence (On n E N).
This problem has been addressed in several contributions but at the expense of strong conditions on the sequence { (A,, b,. : E N*). [14] provided concentration bounds for non-linear stochastic algorithms under a Sobolee condition which turns out to be hard to verify for most applications except for the Suler-Maruyant discretization scheme applied to Stochastic Differential Equation. [29] derived concentration inequalities but assuming that the innovations in (1) are uniformly bounded. Another popular, yet restrictive condition (see [25]) is that for any n E and 0 E RRd, the matrix- vector products (A, A)) are sub-Gaussian with parameter not depending
and 0. In contrast, we aim at giving simple and mild conditions ensuring high probability bounds. More precisely, one of our key contributions (Theorem 1) is to show that under mild conditions on the sequence {(A,, b,) : n E ], for any 5 E (0, 1), n E N and u E gd-1
TP |u (On, - 00)| s sevā (Vu VVuTuu Eu + Va)
V log (1)
+ c Pa
21-5,
(2)
where P. E (0, 1). > 0 is constant independent of n, ar 6, and po - (1/1). In the above, E is the unique solution of the Lyapunov equation which naturally appears in central limit theorems for LSA with diminishing stepsize [cf. (26)]. In addition, we show that the bound we get is tight with respect to and 5 in the case where we only assume that [E[A]] we provide counterexamples illustrating that for a fixed stepsize a and under the conditions that we consider, logarithmic dependence in 1/8 cannot hold in (2) but only a polynomial one. Regarding the dependence with respect to a, we extend [30] and show that for a small enough, {6,, : N} admits a unique stationary distribution Ta and establish central limit theorem for this family of distribution as a 4 0 at rate va and with asymptotic covariance matrix Σ appearing in (2).
-A is Hurwitz. Indeed,
Finally, our proofs rely on a new analysis of product of matrices which extends the recent work in [18). In particular, we establish conditions ensuring uniform bounds in n of the p-th moments of Y, YY, where (Y, n E N²) is sequence of independent matrices whose expected values have spectral radius strictly less than 1. In comparison to existing results, the main challenge addressed is that the random matrices { (Y,
E N*} are not required to be almost surely symmetric.
The paper is organized as follows. Section 2 formally discusses the assumptions LSA for analysis. Section presents the moment bound for product of random matrices. Using this result, Section 4 shows the high probability concentration inequality (2) and Section 5 shows the tightness of the bounds by deriving a central limit theorem for LSA.
Notations Denote N = N \ (0) and N_ = Z N Let E N and Q be a symmetric positive definite d x d matrix. For x E Rdd we denote || = fx T Qa For brevity, we set ||az|| = ||=|| We denote ||Alll |a | |xll, and the subscriptless norm ||||| ||]r is the standard spectral norm. We denote the condition number of Q as Ki = X (Q))max(() (Q). For B E ddd we denote by (B)) its singular values. For p 2 1, the Schatten p-norm is denoted by ||B|, = OE (B)) For p.g 2 1 and random matrix X, we write || 1
We denote gd {x R=||==|| = =}. Let A AN be d-dimensional matrices. We denote Ih_ A = Ay... ... A, if S j and with the convention IP= A L4 i > j. We say that centered random variable (r.v.) X is Lub-Gaussian with variance factor 6² and we denote X E SG(a²) if for all À E R. log 1X < X2 /2. We define the Wasserstein distance of order 2 between two probability measure j and y on IR. as (2 v) infçen((w.)) Fgau ||x - d v). where I( v) is the set of probability measures 2d ((R)")) with marginals μ and respectively. Denote by P2 (Rd) the set of all probability measures on ad with finite second moment.

---

2 Linear Stochastic Approximation: Setting and Assumptions
Consider the LSA recursion (1) with a deterministic initial point 8g. We require the following main assumption in this paper:
AI. ((An;bn)) ba) is an ii.d sequence satisfying the following conditions.
(i) [[bi]] = and there exists Cs > O such that, for any E S u (b] -)) E
(ii) There exists CA > such that ||A S Ca almost surely.
(iii) The matrix - = I[(A is Hurwitz, i.e. for any eigenvalue X of A, Re(A) > 0.
Both conditions A 1-))). (ii) are standard in analysis of LSA, e.g., in [12, 36, 26]. For example, the assumption on the sub-Gause Sab--Gussiantty of b is used in [12] and is relaxed from [36], the almost sure boundedness of A is also used [12, 36). Meanwhile, A(iii)) guarantees the existence of unique solution 0* to AO = b. It is sufficient and necessary condition for the solution of the ordinary
differential equation 0,- = -AO, to converge exponentially to 0" [19, Lemma 4.1.2]. The same kind of result holds for the discrete system 0a+1 - 0% -a
Proposition 1. Assume that - is a Hurwitz matrix. Then there exists a unique positive definite matrix Q satisfying the Lyapunov equation A Q QÁ = I. In addition, setting
a a= --1Q--112 /2, and 0. = =1/2)11A1((1QQ11"
(3)
then for any a E [0, (to)) we get || - aA113 S 1- - aa. If in addition a I ||Q!| then 1 - aa 2 1/2.
This result is well known but its proof can be found in Appendix B.1 for completeness. The above proposition implies that the discrete system converges exponentially as |10 S VkQ(1- aq aa)"//2|00 for (0, a3))
The aim of this paper is to derive high probability bounds on u {0,, - 0-} } for any n E N. u E S Below, we present counterexample show that under only A1, if a > 0 is fixed, then there exists p > 0 such that -im Ei||e, 8" [|]] = too for 2 p. As a corollary, it is impossible to obtain any exponential high probability bounds for {110, 0*| n E N).
Example 1. Consider (1) with d = 1 taking b,, = O for any n E No and (A, : n mnnE n*) an i.idd sequence of biased Rademacher r.v.s with parameter QA E (1/2,
with probability 9A with probability 1 qA
A (-1
(4)
This choice is associated with 6* 0 and corresponds to the recursion: 8, 11 aAx)6o. for some 9o # O. For any 2 and a E (0, 1). we have by definition,
E |100,, P] (1 (1- a)" + g1) + +0)""10111"
Using the lower bounds (1 - a) 2 1 - ap and (1 + a) 2 21+ap+ 1)a2/2 /2, we get for any p 2 1 and 10, 1).
E 11 2 f1 pal(22A 1 (p- 1)a(1 9x) /x)/213"18011
If E (0, 1) is fixed, then for any > Pa.a = 1 + 2(24A - 1)/(a(1 qa)), we have +00. On the other hand, if a (0, 20, - 1)/ qA)). then lim, [[02] O. Therefore {0n : n E N} converges in distribution to the Dirac measure which corresponds the unique stationary distribution of this sequence as a Markov chain. In such a case, this distribution admit p moments for any 2 0.
limp-+to E 110
However, this result is specific to this particular case and does not hold if only Al holds. Consider (On : n E N} defined by (1) with (An n E No} given in (4) and {b,, n E N'} be an i.i.d. sequence of zero-mean Gaussian random variables with unit variance independent of {A, : n E J. We show in Appendix B.2 that there exists 0:2,00 such that for any a E (0. az the Markov chain (0,, for any E (0, 022 there exists Pa 2 1 such that Jg 10 = +o0 for any p 2 Pa-
N) admits unique invariant distribution no for any
0. Further,
is, however, possible to obtain any p-th moment uniform bound for (100, 0*1 n E N) by strengthening Al-(ii) to:
3

---

A2. There exist à E. (0, 1). 0ec > 0 and positive definite d-dimensional matrix Q such that almost surely, for any a E (0, d ||[ aAille lll ao.
Conditions similar A2 are considered in [9] for the analysis of SA schemes with decreasing stepsize. For example, A2 holds in the case of regularized linear regression. We take A = λI + a;aj for some > and under the assumption that ||a||| bounded almost surely. The LSA recursion (1) approximates the solution to (MI + EBaaaa [ 1)0 b, which admits a unique solution.
On the other hand, examples where A2 does not hold are common. For instance, we may consider TD(0) learning with linear function approximation. For Markov Reward Process with X as the state space, P. X x X' + [0, 1] as the transition probability, R. - IR as the reward function, and y (0, 1) discount factor, TD(0) learning is described as in (1) with
An (6xx))( T0²x))) b, R(Z)))(z)))
(5)
where : X + d is feature map. A typical setting is when En is drawn from the stationary distribution of and z', ~ P(z,:") .). It is easy to verify A1 provided that [[Ø(z) R(x) are bounded for all x E X [38]. However, A2 is violated An is only rank-one.
Our next endeavor is to establish moment estimates on the product below:
T (a) mom
mm (I aAi)
m. E N", m S n.
(6)
We also define its expected value as Gla = E[[ Yain = (I - aA)"-m+i To motivate, we observe that the above product naturally appears after re-centering the LSA recursion (I). For any N
On 0* (T a.A.. (0,- }0} + aEn
b b (A, A30-
An easy induction implies that
On - 0 0
+ 0(0)) 0ht) r(a) 100 0*} 0 = ay=
(() 1+
(8)
The decomposition (8) highlights the two sources of error in the estimation f by {0, : N} which will be separately tackled: (ō(t) n E N} corresponds to the transient (or bias) term and (0th) n E N} to the fluctuation term. Both errors are controlled by the product of matrices I (a) mons
therehy motivating the study of the moment bound on r(la I:n as we present next.
3 Moment and High-probability Bounds for Products of Random Matrices
Recall from Proposition 1 that the norm of the expected value Gla) = ETT(A decays exponentially with n as || &
We expect a similar phenomenon for the moment bound of ||P(a)]] Precisely, in this section, we show that if p is fixed, then there exists 0p,00 > 0 such that for any a E (0, ap. the p-th moment of r(a) decays exponentially with n m.
We present the main technical result on the product of general random matrices as follows, whose proof is based on the framework introduced in [18].
Proposition 2. Let (Y, E [} be an independent sequence and P be positive definite matrix. Assume that for each E N there exist my E (0, 1) and ae > O such that | ell S 1 me and |Y, Y | S de almost surely. Define Z, = Il Y, Y Zn for n 2 and starting
from Zo. Then, for any < S and n 2 1,
Z 112 p-g
< KP II
me m (p-1011100
(9)
E=1
where we recall that Kp
1 (P) (P))max(P).
Proof of Proposition 2. Let 2 < S p. Consider the following decomposition Z,, = Y, Y, (Y, EY,Y,)),,,- + E n Zn- Therefore, we obtain for any n E N,
fz( An + Bn, A. fp((Y, Z)),))Zmm B, f>(

---

where fp -Rdxd + Raxd is defined for any B E Raxd by fr(B) P1/ BP-1/2
Since
E[A, [,]] 0, [18, Proposition 4.3] (see Proposition 10 in Appendix C) implies that
|)r(Z.)) < |Bmlpp.. + (p 1)ll A lp.
(10)
It remains to bound the two terms the right hand side. To this end, use [17, Theorem 6.20] which implies that for any Bi, B2 E Idd
|| B B2llp.. I B1 B2llp.
(11)
As result and using that for any B Rddd ||a| [B)) and I|,, - B|Y,llll S on we get
|| A An = (E [lʃ ,
S (E [|Y,, EY.)) 1/4 sonlfr((2nnllll
(12)
Similarly, applying | Y || I 1 mh
BB, 12.0
[|| R
11)))
2/9 S (11-ma)lfeeZnn-l
$ E
Y
(13)
Combining (12) and (13) in (10) yields for any N || p. S (1 mn (p ()o I I (1 mn (p 11 1| The proof is then completed
upon using (11) which implics that || = ||P 1/2 fp (Z,) p1/2| Il. S (kPllfp(Z.)))
n
In order to bound ((0] im using Proposition 2, we identify the latter with Y, -- -,, As - is Hurwitz, applying Proposition yields [|E[Y]]|3 1-(ii) ensures that almost surely,
ai S 1 Further, A
Y BE allA, Allo S 20v/ CA haa
Therefore, (9) holds with my = aa and og = bQa. As |||| = d/,,, we obtain the following corollary. Corollary 1. Assume (ii(..)(iii). Then, for any a E [0, az). 2 2 q S p. and N, |
Bt/9
< [irlallleg VRQd aa + (p 1)62
(14)
where Ooco was defined in (3), and bq 2 Ca.
Note that Corollary 1 shows sup MEN E ||||||a
too for any a E (0, apool where
ap, axe A a (26
(15)
This kind of condition relating the choice of with the required order p is necessary as illustrated in
Example 1. Corollary 1 further leads to the high high-probability bound:
Corollary 2. Assume Aliii.)-(ii). Then, for any E (0,0 where ago was defined in (3), 8 E (0, and n E N, with probability least 8.
|| (a) S RFQ exp
- - a² 22tzg))22+ bba 2n
h lmlog(d/5)
Proof. The result follows from combining Corollary 1 with and Lemma 1 in Appendix C applied with A log(r)) +an
n2/2 and C po 2, p1 +oo.
The result in Corollary 2 is tight with respect to 6, as illustrated via the following example that continues from Example 1.
5

---

Example (Continuation of Example 1), Consider (0, : E N} defined by (1) with {A, n E N
given (4) and bn for any n E No. Define
1 |1 1 a
(a) 9. log
-log(1 a), 0g suplā > 0: Pg(a) 0, Va E (0, (16)
Note that (a) ~ a(2qA= - 1) as a L Therefore since qA > 1/2, {a > 0 (a > for any a E (), + 1 and ag is well-defined. Consider also (.(a) = Py log [[1 + a)/(1 - a)]. Then, we show in Appendix C that for any 8 E (c-2mpola),11 1) and g E (e (o-mg((o/((x(tteea "log(n),11 1))
(1+0*
n 1lo((118)
P On 2 exp -pg(aa) + log
5ō, (17)
1 0
1
2
(1+a)
log(n)
P
8n 2 exp -Po(a))+ log
m (og) log(1/)) +
25. (18)
2
The bounds (17), (18) show that the tail distribution associated with 0n behaves as a log log-normal one. If & follows zero-mean Gaussian distribution with unit variance, then easy computation shows that for any >> 0, Pe 2 1) (2na²)-11/² log (t) exp(-(202)-1 as L + co. Therefore, to have P 2 tá) S 8 for a small 5 > the scalar ts has to be of order cxp(o / log(1/6)).
We conclude the section with a complementary result of Corollary /that does not require A Al-ii):: Proposition 3. Assume A Al(ii)), ||A All SG(C'A) for some some C'A 0. Then, for any (0,
where aooo was defined in (3), 2 S q S p. and n E N.
1 || Mrrfel |1
< | Til ll S vFQd/P(11 aa + q(p 1)(66))
(19)
where 6/2 =2/KRQ C'A
The proof is similar to that of Proposition and can be found in Appendix C.
Finite-time High-probabilityy Bounds for LSA
Relying on the results established in Section 3 and the decomposition (8), we derive high probability bounds on ut {on. 0*} for any n E N and u E g where (0n n E N) is defined in (1).
We begin our study with the transient term ((tr) defined in (8). Observe that Proposition 4. Assume A and let pu 2 2. Then, for any n E N a E (0, ccp. where po is defined in (15). u E gd-1 and E (0, 1) is holds with probability at least 1 that
|u Tu (Oo 0*)l S VRQut l0x/4))1000-- 0 1'110-1/00
where a was defined in (3).
The proof of the above statement is given in Appendix 1. Proposition 4 only provides polynomial high probability bound with respect 8. This is due to the fact that only polynomial moments of ||ا| up to a maximal order are uniformly bounded in the number of iterations n.
We now turn to the fluctuation term (( defined in (8). Note that under A1, the sequence fsn defined in (7) is i...d. From this observation and following [13], we consider the decomposition
N)
g(tl) = a Σ (()) jtim = J(a.0) + H(a.))
(20)
where (()(a.0) 11 (((00))
N} are defined by induction for n 2 0 as:
f(a,0) =(T -I-aA) J( aEnt1,
f(.00) 0,
Jf
(21)
H (a.0)
n+1 = -(-aAn)) (a.0) a a(AntI - A)J(a.))
((000) 0.

---

The latter recurrence can be written as
J(a.0) = Σ
Glo)
HimEE H(O.0) = -a
Σ
(a) (Aj - -A)J
j+lm
1=1
==1
Note that -. is a linear statisties of the random variables {ez j E {l...., n}} which are centered and i.idd. under A I. Next, we show that J(a.0) is the leading term as the stepsize 0. Denote for any No and 0, the covariance matrix of J! as
E = -Cov(J
(22)
We obtain the following statement which is proven in Appendix D.2: Proposition 5. Assume A1. Then for any n Nº, a E (0, aool, where ae is defined in (3), u E gd-1 and 8 E (0, 1), it holds with probability at least 1 - 6,
_(a DIV T Ee log(2/6) + av log(L/(aa))) (22(6))
(23)
where D1 = 6043 and D2 is defined in (49).
We analyze further the covariance associated with J. fla.0) and its dependence with respect to and a. First, note that for any a E (0, a2,c0). {E, n E Nº} converges to a as n - oo where is the unique solution the Ricatti equation
n = a Ei= G Eg Gis
AΣ +"A A aAΣ"A" A Eg with Σg B[sıe]]
(24)
Notice that we focus on the cases where E. is full-rank. Using Proposition 1, we obtain that for any O.
E - S a
G |[ S aa "KQ E. [| aa)"
(25)
k>n
We now give an expansion of E with respect to a. It is well-known that as 4 O, Ed converges to Σ, the unique solution of the Lyapunov equation (see [34, Lemma 9.1])
AΣ
ΣA Σ
(26)
Our next result, whose proof given Appendix D.3, states the convergence of E to Σ is the order of the stepsize Proposition 6. Assume that A Al-(iii) holds. Then, for any a E (0, aso), where ano is defined in (3),
- Elle aa -a- |AEA I
ll
where Ed and E are defined in (24) and (26) respectively and is given in (3).
The last step in bounding ((41) to consider H!(..), We proceed similarly to (21) and consider
the decomposition H H(aa0) f(al)) + H(a.)) where ((J.a H(a.)) : n E N) are defined by
induction for 2 0 as:
slad)) = (I- aA)) (a.1) al a(Ant1 A) H (a.1)
foo.)) 0,
(27)
n+1 = =[I (T-aA, n+ H (a.1) a(Ant) A) A)
H(a.1) 0
In our next results, whose proof is given in Appendix D.4, we bound each term of this decomposition separately.
Proposition 7. Assume Al and let po 2 2. Then, for any E N, a E (0, (pp, where 0o is defined in (15), 5d-1 and E (0, 1/2), with probability least 25, it holds
h ((o.)) < aD log (1/5). lu [TH(o.))) D-apf5-1/10
(28)
where D3 and D4 are given (57) and (60), respectively.
Now are ready to combine the previous bounds and to state the main result of this section.
7

---

Theorem 1. Assume A and let po 2 2. Then, for any n N, a E (0, pc).))) where apo,20 is defined in (15), u gd-1 and E (0, 1/4), with probability at least - 45, it holds
a 1122/u |a (O.. 0') < Di Div (u u) (2/0) + 12 (a. 8) + (1 aa/4) A 1 (a,
(29)
where 2x is the unique solution of (24), D 30 defined in (3),
(a. (eD; log (1/6) + Log log l2/0)) + Dapão 1//00-11/v. 1/10
(30)
A (a, Di Diva- Ee log (2/6) + /n /ro |10 - 0 11 -1/2 5//0//111000 1/10 where EQ and Eg are defined (3) and (24) respectively.
Proof. The proof follows from the decomposition
'On 07) u T 1:m (0o 8*) + u J(a.0) + u J(a.1) + H(a,1)
where J/a00) 1 and 1)) defined in (21)-(27), the union bound and Proposition 4, Propo- sition 5, (25) and Proposition 7.
We now discuss the high probability bound (29). First, the term A (a, (a,,)) 6), and in particular the initial condition vanishes exponentially fast in the number of iterations n. In addition, (a, 6) and (ax 8) are of order 8-1/po as + 0 and therefore (29) provides polynomial high probability bounds on LSA. However, this conclusion expected as illustrated in Example Finally, the discussion of (29) with respect to a is postponed to the next section.
Under A2 we can provide better bound for H (0.1)
Proposition 8. Assume AI and A2, Then, for any E N, E (0, a.o ū.x), where aso is defined in (3), u g and 8 E (0, 1/2). with probability at least 1 26, it holds
u T [ < eD log? |u H [ < eD log (1)8))
(31)
where D3 and D5 are given in (57) and (61) respectively:
As result, we can establish exponential high probability bounds with respect to 5.
Theorem 2. Assume A and A 2. Then, for any n E N, a E (0, 060 A âxc) E gd-1 and
5 E (0, 1/4), with probability at least 1 - 46, it holds
-1/ u (0)- DIV (u E' log(2/8) a 1/2 (2) (a, (1
(a.
where D1 6033o//33 xx is solution of (24).
( 8) = eD3 + Ds) log (1/6) + log log( D2
(32)
A (a, D1 v a x E. log (2/6) + x 1/2 0 0-||a=" 1112
where Eg is defined in (24).
Proof. The proof follows the lines of Theorem with Proposition 8 used instead of Proposition
5 Optimality of the derived bounds with respect to a: analysis of (On)nEN as Markoy chain
In this section, we study the sequence {0,, n N} defined in (1) as Markov chain. This perspective will allow us to show that the bounds that we derived in Theorem I are near Bear-Berstein high probability bounds with respect to the stepsize a. Denote by R. the Markov kernel associated with (0,, E N). First, we show that if a is small enough then R. is geometrically ergodic with respect the Wasserstein distance of order denoted by W2 and give a representation of its stationary distribution as infinite sum.
8

---

Theorem 3. Assume AI. Then, for any E a2,0 where 02 is defined in (15), Ra admits unique stationary distribution Ta E P2(R2) and for any E N,
2 (ōg Ta) S kod(l - aa/2)" [ 110 00- 01 a
(33)
Further, if (AA,, by) k E N-} as (A1, b1), then the following limit exists almost surely and in I.² and has distribution Na:
} is any sequence of i..d. random variables with the same distribution
0
lim ola.t) 0 = カ n
0(a.t) a
TE:0 - aI. aA.).
(34)
12
k=
i=k
The proof is postponed to Appendix F.1. Based on Theorem 1, we easily get concentration bounds for the family of distributions {T
(0, d22,0 around 6*
Theorem 4. Assume Al I and let pa 2 2. Then, for any a E op..o))) where a' is defined in (15), u E gd-1 and 8 E (0, /4), with probability at least 1 - 46, il holds
(0 0 Di Div(u" Eu} log(2/6) + a (2 (a"1(11111E22 IAAA 11 + (a,
(35)
where E is the unique solution of (26), DI /0/3e4/3, a is defined in (3), and (a, 6) in (30).
Proof. The proof follows from Theorem 1, the Portmanteau theorem [22, Theorem 13.16), and the fact that convergence in W2 implies weak convergence.
Our results is only polynomial in ō and we cannot expect improving this dependency as illustrated in Example for fixed a. The leading term in (35)
0s /Dr Euj. In our next result,
(eL))))e we establish a central limit theorem for the family (0 (00((000..))) where Σ plays the role of the asymptotic covariance matrix. As result, (35) is a Bernstein-type high probability bound with respect to and therefore (35) is sharp. Define for any E (0, 02,00
g( = a012 -
-0"}.
(36)
Theorem 5. Assume A Then, the family (0 : a (0. co. converges in law as a 4 to zero-mean Gaussian random variable with covariance matrix Σ defined by (26).
Note that this result was established [30, Theorem 1] for general stochastic approximation schemes but under stronger conditions on the sequence {En n E ]*.. In particular, it is assumed that the distribution of 1 admits a density with respect to the Lebesgue measure. We relax this condition and provide a new proof for this result. In particular, our strategy to establish Theorem 5 is to consider the decomposition (20) of (0, Define {J (_(a..) n E ] by
NJ with 0g since in such case 0₂ offl) for any n E N.
j(a,z) a Σ GR:DEK-1, G = [I (1-aAA) k=n
(37)
ē=k
Note that for any n N, g/ has the same distribution as g!a) starting from 6u 0 and _!a.0)
as ) In contrast to J/a00) f(a,+) admits limit in 2 and almost surely denoted by j(a.t)
Then, we get for any u E sd-1, a (0, a2.00.. bounded and Lipschitz function f R + R. with Lipschitz constant smaller than 1, by the Lebesgue dominated convergence theorem
El (TT0 [() (a 1/2 J(a,
lim [a 1/2 [o( - 0y)1 - Elf(a -122 11/22" -(a,+)
lim E[f(a-1/2 [0(0)= 11] - Elf(a 1/2 J(a.0)) < lim -1/2 H(a.0)
n
Using the decomposition H. (a.00) 1! 1 + (a.1)) where (J (!! N} are defined
in (27) and plugging the bounds provided by Proposition 11 and Proposition 12 in Appendix D.4 shows that
sup [E[ ((a++))) Eif(a - 1/2 f(a++) = 0.
00
a-1

---

Therefore by the Cramer Wold device and the Portmanteau theorem [22, Theorem 13.16], Theorem follows from the next result.
Proposition 9. Assume AI. Then, for any S {a-1/2u Jo (0, (0,02,00)) converges in distribution the zero-mean Gaussian distribution with variance u. Eu where E is given in (26).
The proof is postponed to Appendix F.2.
Conclusion
In this paper, we provided novel non-asymptotic analysis of L.SA algorithms with fixed stepsize. For any 8 E (0, 1), we obtain bounds on the sequence {110, 0' NJ that holds with probability tight with respect the stepsize, and we show that such high probability bounds for LSA necessarily have polynomial dependency in ô, leading to 'heavy-tail' phenomena. Importantly, our results do not require the matrices A., to be symmetric but only Hurwitz, which enables one to apply them various scenarios such reinforcement learning. Future work includes extending our high probability bounds to a larger panel of random noise, e.g., with heavy tailed distribution, Markovian dependency, well Polyak-Ruppert averaging and nonlinear SA.
least 8. The bounds are proven
Acknowledgement
This work partly supported by ANR-I9-CHIA "SCAI" and CUHK Direct Grant #4055113 13. The publication was partly supported by the grant for research centers in the field of Al provided by the Analytical Center for the Government of the Russian Federation (ACRF) accordance with the agreement on the provision of subsidies (identifier of the agreement 000000D733311P500000 the agreement with HSE University No. 70-2021-00139, Part of this work has been carried under the auspice of the Lagrange Center in Mathematics and Computing.
and
10

---

References
[1] R. B. Ash. Information theory. Tracts in Pure & Applied Mathematics. John Wiley & Sons Inc,
1966. ISBN 047700345999780470044444
[2] F. Bach and E. Moulines. Non-strooglyy-conex smooth stochastic approximation with con- vergence rate o o(1/n). In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Cur- ran Associates, Inc., 2013. URL https://proceedingg wttppreeeeenn.nnnniiiniirreeeeee ott.Faaaaaa00400000000000001111.
pdf.
[3] A. Benveniste, M. Métivier, and P. Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[4] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and distributed computation: numerical methods. 2003.
[5] 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.
[6] V. S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008
[7] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3 2212311,,,20 2018.
[8] S. Boucheron, G. Lugosi, and Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
[9] S. Chandak and V. S. Borkar. Concentration of contractive stochastic approximation and reinforcement learning. arXiv:2106. 14308, 2021.
[10] S. Chen, A. Devraj, A. Busic, and S. Meyn. Explicit mean-square error bounds for monte-carlo and linear stochastic approximation. In International Conference on Artificial Intelligence and Statistics, pages 4173 4183. PMLR, 2020.
[11] X. Chen, J. D. Lee, X. T. Tong, Y. Zhang, et al. Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics, 48(1):251-222 2020.
[12] G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor. Finite sample analyses for TD(0) with function approximation. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[13] A. Durmus, E. Moulines, A. Naumov, S. Samsonov, and H.-T. Wai. On the stability of random matrix product with Markovian noise: Application to linear stochastic approxima- tion and TD learning. In M. Belkin and S. Kpotufe, editors, Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1711-1752. PMLR, 15-19 Aug 2021. URL https: https:://ppoceeee pto.//eeoccceeeeee/oe mlr, .aress///// 1134/durmus2la..1
[14] N. Frikha, S. Menozzi, et al. Concentration bounds for stochastic approximations. Electronic Communications in Probubility, 17, 2012.
[15] S. Guo, F. Qi, and H. M. Srivastava. Necessary and sufficient conditions for classes of functions to be logarithmically completely monotonic. Integral Transforms and Special Functions, 18(1 1):819 9269992262222 2007. doi: 10.1080/10554460005558888 org/10. 1080 106226667061118833
URL https://doi.
[16] P. Hall and C. Heyde. Martingale Limit Theory and Its Application. Academic Press, 1980.
[17] Hiai and D. Petz. Introduction to Matrix Analysis and Applications. Universitext. Springer International Publishing. 2014. ISBN 9783319041559
[18] D. Huang, J. Neees-Weed, J. A. Tropp, and R. Ward. Matrix concentration for products. arXiv preprint arXiv:2003.0544 054377, 2020.
[19] B. Jacob and H. Zwart. Linear
Systems Infinite-dimensioone Spaces. Number 223 in Operator Theory: Advances and Applications. Springer, 2012. ISBN 978-3- 0348-0398-4. doi: 10. (1077978-330044-009330
10.1007/978.3--348--999
[20] P. Jain,, S. M. Kakade, R. Kidambi, P. Netrapalli, and A. Sidford. Accelerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, pages 545-604. PMI.R 2018.
11

---

[21] P. Jain, D. Nagaraj, and P. Netrapalli. Making the last iterate of sgd information theoretically optimal. In A. Beygelzimer and D. Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1752-1755, Phoenix, USA, 25-28 Jun 2019. PMLR.
[22] A. Klenke. Probability Theory: A Comprehensive Course. Universitext. Spriigge London, 2013. ISBN 9781447153603.
[23] H. Kushner and G. G. Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
[24] C. Lakshminarayanan and C. Szepesvari. Linear stochastic approximation: How far does con- stant step-size and iterate averaging go? In A. Storkey and F. Perez-Cruz, editors, Proceedings of the Twenty-Firs International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1347-1355. PMLR, 2018.
[25] G. Lan. First-order and Stochastic Optimization Methods for Machine Learning. 01 2020. ISBN 978-3-030-39567-4, doi: 10. (1007/9788-3-03--39566
[26] O. Macchi and E. Eweda. Second-order convergence analysis of stochastic adaptive linear filtering. IEEE Transactions Automatic Control, 28(1)766-85, 1983.
[27] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach
to stochastic programming. SIAM Journal on optimization, 19(4):1574-1099, 2009.
[28] Y. Nesterov and J.-P. Vial. Confidence level solutions for stochastic programming. Automatica,
4466):1559-1568, 2008.
[29] B. Pepin. Concentration inequalities for additive functionals: A martingale approach. Stochastic Processes and their Applications, 135:103-138, 2021.
[30] G. Pflug.
Stochastic Minimization with Constant Step-Size: Asymptotic Laws. SIAM Journal on Control and Optimization, 24(4):655-666, 1986. doi: 10.1137/0324039. URL https:
//doi. argoi.org/10 wrg/10../1.. /11770032409.
[31] I. Pinelis. An Approach to Inequalities for the Distributions of Dimeensoe-Di Martingales, pages 128-134. Birkhäuser Boston, Boston, MA, 1992. ISBN 978-1-4612-0367744 doi: 10.
1007/978-1-4612-000 1-4612-0367-4 URL https: org/ 10. 011107/9978-11441-03337-78
[32] I. Pinelis.
Optimum Bounds for the Distributions of Martingales in Banach Spaces. The Annals of Probability, 22(():1679 1706, 1994. doi: 10. 10.1214/00p11176684777 URL https:
/ aooii.org/10 /214/a/pp/1////// /t////////11118777777
[33] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging, SIAM journal control and optimization, 30(4):838 855, 1992.
[34] A. S. Poznyak. Advanced Mathematical Tools for Automatic Control Engineers: Deterministic Techniques. Elsevier, Oxford, 2008
[35] A. Rakhlin, O. Shamir, and K. 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.
[36] R. Srikant and L. Ying. Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning. In Conference on Learning Theory, 2019.
[37] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning,
(1):9444, Aug 1988. ISSN 1573-0565. doi: 10. 10.100//BF001 15009.
[38] J. N. Tsitsiklis and B. Van Roy. An analysis of cemporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5))674-660, May 1997. ISSN
3334-3303. doi: 10. 1099909998800 5580744.
[39] C. Villani. Optimal transport: : old and new. Grundlehren der mathematischen Wissenschaften. Springer, Berlin, 2009. ISBN 978 778-3-540-71049-3
12


Reviews:
[{"review_id": "t4BK0X4Tdmq", "reviewer": "Reviewer_kP8y", "summary": "The paper provides a non-asymptotic analysis for linear stochastic approximation algorithms. Polynomial concentration bounds with order depending on the stepsize are derived under weaker conditions than previous works. The paper also shows that logarithmic dependence on probability $\\delta$ is not possible.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The main contribution of the paper is:\n\n1. Under mild conditions on the sequence of $A_n, b_n$, the paper provides non-asymptotic bound for the approximation error with polynomial dependence on $1/\\delta$ and near optimal dependence on the step size. \n\n2. Counterexamples are provided illustrating that the logarithmic dependence in $1/\\delta$ cannot hold. \n\n3. The optimality of the term $\\sqrt{\\alpha}$ is shown via a central limit theorem for the family of stationary distribution for $\\{\\theta_n\\}.\n\nOverall, I believe this paper is a nice complement to the literature of linear stochastic approximation. My questions are summarized as below:\n\n1. Example 1 is concluded with the impossibility to obtain exponential high probability bounds for $||\\theta_n-\\theta^*||$. Does this naturally suggest the impossibility to obtain exponential high probability bounds for $u^\\top(\\theta_n-\\theta^*)$ for some fixed $u$? This seems correct to me. But it would be great to make it explicit in the paper.\n\n2. Following-up the first point, is it possible to derive reasonable upper bounds for the term $||\\theta_n-\\theta^*||$ instead of $u^\\top(\\theta_n-\\theta^*)$? Simple union bound seems to introduce exponential dimension dependence. I'm curious whether this is the best one can do or not.  \n\n3. Is the asymptotic covariance matrix $\\Sigma$ in Equation (2) guaranteed to be full rank and well-conditioned? If not, in the degenerate case when $u^\\top \\Sigma u$ is approximately 0, is the dependence w.r.t $\\alpha$ still tight?\n\n**Update based on the author response:\n\nThanks for the detailed reply. I'm satisfied with the responses to the comments and remain my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "lgJlllCNAOu", "reviewer": "Reviewer_9FBX", "summary": "This paper performs a non-asymptotic analysis for the linear stochastic approximation (LSA) algorithm, with bounds given in the form of Eq. (2). This paper shows the tightness of their bounds by examples. ", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The LSA algorithm is significant in machine learning. I am generally unfamiliar with the related work, but I think this paper makes a good technical contribution to the study of LSA. \n\nThe proof is written formally, but the intuition is unclear to me. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "### Limitations\n\n1. The paper claims tightness by showing a CLT-like statement. However, this seems only justifying the variance term in the main result (see, e.g., the $\\sqrt{u^\\top \\Sigma u}$ term in Eq. 2), but not the constant term (e.g., $\\delta^{-\\frac{1}{p_0}}$ in Eq. 2), while the latter term is of more interest. \n\n\n### Societal Impact\n\nThe paper is mainly theoretical, and I don't see any potential negative societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "ZN_nPMY8rtM", "reviewer": "Reviewer_eosb", "summary": "This paper provides high probability concentration bounds for linear stochastic approximation algorithms using constant stepsize under weaker assumptions. The key novelty is to derive tight moment bounds for the product of random matrices. The polynomial concentration bounds were shown to be tight. Since linear SA was widely used in application, the results are of broader interest to the NeurIPS community.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Although this paper is theoretical and highly technical, it is well-organized to convey the main idea.\n\n(line 25): $Q$-learning cannot be modeled by a linear stochastic approximation algorithm since it involves a max operator.\n\nOften in applications such as reinforcement learning, the samples $\\{(A_n,b_n)\\}$ are not i.i.d.. For example, in TD-learning with synchronous update, the corresponding samples form a martingale difference sequence. In TD-learning with asynchronous update,  the corresponding samples form a Markov chain. It may be an interesting future direction to extend the high probability bounds in this paper to these more general settings.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No Societal Impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "YdwpIWiPXV", "reviewer": "Reviewer_jZ9d", "summary": "The paper studies the problem of analyzing linear stochastic approximation (LSA) algorithms which are used to obtain an approximate solution of a linear system $ A \\theta = b$, where $A$ and $b$ are observed through random variables $\\{ (A_1,b_``1), (A_2,b_2),\\cdots \\}$. The analysis relies on new results regarding moments and high probability bounds for matrix products under weak conditions with polynomial concentration with the order depending on the step-size $\\alpha$, which diverges from results in prior work. At this level of generality, the authors show that polynomial tails cannot be improved in the worst case. The concentration bounds are in terms of covariance matrices appearing in central limit theorems of the matrix products under appropriate scaling limits.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper considers the classical problem of analyzing LSA algorithms which have gained renewed interest in modern applications such as least squares (and ridge) regression, reinforcement learning (such as TD(0) learning) among other areas. Convergence results are established for these algorithms with a fixed stepsize under a set of assumptions more general than those considered in prior work. Indeed to the best of my knowledge, this is the first paper to establish convergence properties with non-subgaussian tails under a wide family of assumptions. I think this paper is a fine contribution to the theory of analysis of LSA algorithms. However, I think it would help the interpretability of the results if more instantiations of these results are provided for relevant applications (ridge regression / TD(0) learning, etc.).\n\n- Under assumption A.1, it would help to include a remark as to how concretely show how this assumption compares with that in prior works.\n\n- Line 120: $\\mathcal{X}$ notation is incorrect. Line 134: The terminology suggesting that the matrix $G^{(\\alpha)}_{1:n}$ decays with $n$ is mathematically imprecise. \n\n- Concerning the discussion on TD(0) learning under linear function approximation: is there any intuition how the current results can be extended to the case when $x_n$ is not sampled from the stationary distribution but equals $x_{n-1}'$. More generally, when the i.i.d.ness assumptions fail, but a martingale structure is retained, is there any intuition as to whether such bounds still hold true? For the purpose of the exposition (and comparison), it may help to instantiate the proved results in the context of TD(0) learning to compare with known results here.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, I believe the authors have adequately addressed the limitations of their work, and future work to be done. ", "review_text": "", "extra_scores": {"ethical_concerns": "None, to the best of my knowledge", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "XmBCTX5tpht", "reviewer": "Reviewer_kUS1", "summary": "The authors analyze the convergence of the linear stochastic approximation (LSA) algorithms with fixed stepsize. They establish a high probability convergence result on how the algorithms estimate compares to the true value of the linear system. They also analyze the stationary distribution of the algorithms iterates. They show that their results are theoretically tight. Their key lemma is a result on bounding the expected value of the norm of products of random matrices, which may be of independent interest.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper seems very interesting mathematically but is difficult to understand in its current form. I believe that the paper needs to be rewritten for clarity.\n\nPros:\n\nThe paper presents tight results on the convergence of the LSA algorithm with minimal assumptions. The techniques used seem interesting and deep, such as the technical lemma used to bound the norm of the mean of a product of random matrices.\n\nCons:\n\nI believe the clarity of the paper needs to be improve before it is accepted for publication.\n\nThe first clarity issue is that the authors do not go into detail on how their results compare and complement previous results on LSA convergence. The authors mention a long list of related papers but simply mention that they are weak. For example, how do the results compare to Theorem 1 of [23]? Can this work provide a high probability version Theorem 1?\n\nThe second clarity issue is that to understand the main theorems, the reader needs to understand a large number of symbols defined throughout the text (which are themselves defined with a large number of symbols). The authors should improve the discussion around the main theorems including intuition on the important terms or present simplified theorems to help the reader understand the main claim of the theorems.\n\nFurther questions:\n\nOften the mean $\\bar{\\theta} = \\frac{1}{n}\\sum_{i=1}^n\\theta_i$ is used as the estimate of the true parameters $\\theta^*$ due to the natural variation of the iterates. Does this work say anything about the estimate $\\bar{\\theta}$? Since there is a natural variation of the iterates $\\theta_i$ around the true parameters $\\theta^*$ the mean should be a better estimate of the true parameters.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This was not discussed but I believe it is not needed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "SAf_1-UJWvQ", "reviewer": "Reviewer_Sbz9", "summary": "This paper studies the finite-time analysis of linear stochastic approximation algorithms driven by IID noise and fixed stepsize. New analysis based on new results on moments and high probability bounds for products of random matrices. High probability bounds on the LSA iterates are derived under weaker assumptions on the random samples than existing works. The bounds have also been shown tight with the assumptions made and some additional results on the concentration error bounds are also discussed. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Finite-sample analysis of stochastic approximation algorithms has been studied in a number of works, recently motivated by e.g., analysis of reinforcement learning algorithms dealing with Markov decision processes. This paper revisits the linear stochastic approximation algorithms and analyzes its finite-time performance using recent results in concentration equalities and moments bounds. Although the analysis is new, and the high probability bound improves upon the existing one, the submission falls in several aspects. First, there are a number of related works analyzing the finite-time error bounds of different stochastic approximation algorithms and, yet they were not discussed in the submission, so it is difficult to judge the novelty and significance of the results. For example,  [a] Gugan Thoppe, Vivek Borkar (2019) A Concentration Bound for Stochastic Approximation via Alekseev’s Formula. Stochastic Systems 9(1):1-26. [b] Borkar, V. S. . \"A concentration bound for contractive stochastic approximation.\" Systems & Control Letters 153.1(2021):104947.\nSecond, how important is the improvement? Does the analysis carry over to other stochastic approximation algorithms driven by e.g., Markovian noise in reinforcement learning applications? And how about nonlinear stochastic approximation algorithms? Third, it would be great if the authors also provide numerical tests validating the improvement as well as the practical usefulness of the results. \n\nThe paper is mostly clear and easy to follow, althoug with a bit heavy notation. Some were used before they were defined. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "More recent works on (non)linear stochastic approximation analysis shall be discussed; and provide also numerical simulations validating the improved error bounds. ", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "7JvombQzWK", "reviewer": "Reviewer_Pfgj", "summary": "The paper offers a non-asymptotic analysis of the linear stochastic approximation algorithm with fixed step-size, where the solution to the linear system $\\bar{A} \\theta = \\bar{b}$ is approximated iteratively. While prior literature has considered asymptotic and non-asymptotic bounds, the main contribution of this work is the improved quality of non-asymptotic bound for LSA performance, yielding more meaningful finite-time confidence sets. The authors consider a set of mild assumptions on the coefficients, under which they prove high probability bounds on the approximation error. The analysis is based on a new analysis of product of random matrices, with further extension to random matrices with Hurwitz mean but not necessarily symmetric a.s. The authors further discuss the tightness of the resulted polynomial bound with respect to error probability $\\delta$ through a clean (counter-)example (Example 1), and the sharpness with respect to the step-size through derivation of a central limit theorem.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is well-written and organized, with clear and consistent notations. The structure of having a standalone section (Sec 3) on product bound of matrices followed by its application to LSA (Sec 4) and discussion of tightness (Sec 4-5) seems natural and easy to follow. A minor suggestion is to be more explicit when discussing tightness (e.g. L60-61: “Section 5 shows the tightness of the bounds”) since more than one variables are considered.\n\nThe concentration results proven in the paper are nontrivial and clearly improve upon previously known analysis (asymptotic or non-asymptotic) in the sense that the assumptions are weak and that the bound itself is tight. Though, I would hope for a more substantial discussion of the statements (L32-34) “non-asymptotic studies are in general too coarse and lose significant statistical information in their derivation”, especially when claiming “their upper bounds are generally loose when used in predicting the actual performance of LSA.”\n\nWhile the proof technique isn’t a most novel one mathematically in my opinion, the details are sound and well-presented and I believe the main claims are all correct. The main technical tool relates Huang et al’s recent paper on matrix concentration for products. The idea of handling the error term by splitting it into bias and variance terms is nice albeit standard and the actual proofs are clearly nontrivial to carry out.\n\n### Other comments/suggestions:\n\nI like the recurrent use of Example 1 to demonstrate tightness of the polynomial bound, a very clean example. This could be a trivial point, but I would appreciate some intuition for Assumption A2 as the additional condition for exponential high probability bounds. In particular, as is illustrated by the few examples in Section 2, A2 holds in many natural cases but not others, and I would love to have a conceptual understanding of which cases may admit an exponential bound vs polynomial. \n\nIn the discussion of tightness in Section 5, I didn’t completely get how the paragraph L271-275 discussing Eqn (36) on the limit $\\theta_\\infty^\\alpha$ implies the optimality of the finite-time bound (or does it not and is simply a standalone result?). I could be missing something obvious, but perhaps some additional interpretations around Theorem 5 and (36) can be helpful.\n\nI would also love to see a discussion of implications and take-away message of the results, advancing it further from a mostly mathematical result. E.g., what are some insights behind the necessity of Assumption 2? How can the results improve current practice/knowledge when applied to reinforcement learning for example?\n\n### Note:\nI may not be familiar enough with some pieces of related work. I have checked some of the proofs carefully but not all.\n\n### Typos spotted:\nL69-70: probabilities measure -> probability measures\n\nL113: definite positive -> positive definite\n\nL120: \\mathcal{X} -> \\mathsf{X}\n\nL268: in $\\mathsf{D}_1$ definition, $e^{2/3}$ -> $e^{4/3}$ I believe, in consistency with other occurrences\n\nL286: functions -> function\n\nL490: are an independent -> are independent\n\nL498: remains take -> remains to take\n\nL520: first term RHS in the equation below: missing an $\\alpha$ subscript\n\nL556: first “=” in equation below should be \\le", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The theoretical limitations are discussed. N/A for negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a non-asymptotic analysis of linear stochastic approximation algorithms. It shows interesting concentration bounds and certain bounds are not achievable. The majority of the reviewers agree that the analysis is interesting, and provides new results to the literature. I have read the paper carefully and also the discussions between the authors and the reviewers, and agree with the majority of the reviewers. One reviewer pointed out that its connections to other papers are not made clear and pointed out some future directions to work on, and the authors have responded to these particular points. I do agree that the current form of the paper has not addressed fully these interesting new directions, but it has crossed the threshold. 
Decision: Accept (Poster)