The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize
Authors: Dongyan Lucy Huo
Yixuan Zhang
Yudong Chen
Qiaomin Xie
Venue: NeurIPS 2024 spotlight (2024)
Keywords: stochastic approximation
nonlinearity
Markov chain
weak convergence
Wasserstein metric
asymptotic bias
Richardson-Romberg extrapolation
Polyak-Ruppert averaging
Primary area: optimization

Abstract: In this work, we investigate stochastic approximation (SA) with Markovian data and nonlinear updates under constant stepsize $\alpha>0$. Existing work has primarily focused on either i.i.d. data or linear update rules. We take a new perspective and carefully examine the simultaneous presence of Markovian dependency of data and nonlinear update rules, delineating how the interplay between these two structures leads to complications that are not captured by prior techniques. By leveraging the smoothness and recurrence properties of the SA updates, we develop a fine-grained analysis of the correlation between the SA iterates $\theta_k$ and Markovian data $x_k$. This enables us to overcome the obstacles in existing analysis and establish for the first time the weak convergence of the joint process $(x_k, \theta_k)$. Furthermore, we present a precise characterization of the asymptotic bias of the SA iterates, given by $\mathbb{E}[\theta_\infty]-\theta^\ast=\alpha(b_\textup{m}+b_\textup{n}+b_\textup{c})+\mathcal{O}(\alpha^{3/2})$. Here, $b_\textup{m}$ is associated with the Markovian noise, $b_\textup{n}$ is tied to the nonlinearity of the SA operator, and notably, $b_\textup{c}$ represents a multiplicative interaction between the Markovian noise and the nonlinearity of the operator, which is absent in previous works. As a by-product of our analysis, we derive finite-time bounds on higher moment $\mathbb{E}[||\theta_k-\theta^\ast||^{2p}]$ and present non-asymptotic geometric convergence rates for the iterates, along with a Central Limit Theorem.

The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize
Dongyan Lucy Huo' Yixuan Zhang²
Yudong Chen² Qiaomin Xie
CCorelll University University of Wisconsin-Madison
dh6228cornell edu (ychang2554, yudong chen, qiaomin iemmmiiniiieie....eee.eee..eeeee celsevevscceoo edu
Abstract
In this work, we investigate stochastic approximation (SA) with Markovian data and nonlinear updates under constant stepsize 0. Existing work has primarily focused on either i.i.d. data or linear update rules. We take a new perspective and carefully examine the simultaneous presence of Markovian dependency of data and nonlinear update rules, delineating how the interplay between these two structures leads complications that are not captured by prior techniques. By leveraging the smoothness and recurrence properties of the SA updates, we develop a fine-graines analysis of the correlation between the SA iterates 6g and Markovian data zg. This enables us to overcome the obstacles in existing analysis and establish for the first time the weak convergence of the joint process (ær,, 0g) 1:20 Furthermore, we present a precise characterization of the asymptotic bias of the SA iterates, given by [E[0_] - 0 = a(bm + bn + be) + ((a3/2). Here, bm is associated with the Markovian noise, b, is tied the nonlinearity of the SA operator, and notably, be represents multiplicative interaction between the Markovian noise and the nonlinearity the operator, which is absent in previous works. As a by- by-product of our analysis, we derive finite-time bounds on higher moment [E[[ 6" [[20]] and present non-asymptotic geometric convergence rates for the iterates, along with a Central Limit Theorem.
1 Introduction
Stochastic Approximation (SA) is an iterative scheme for solving fixed-point equations using noisy observations. Its application spans various domains including stochastic control [9, 40], reinforcement learning (RI) [4, 62) and stochastic optimization [43]. A typical SA algorithm takes the form 0x+11 = (z, (g+ ark) where (Irx) )x20 represents the underlying noisy data sequence and 0 constant stepsize. The goal of SA is to approximate the target solution 6" that solves E [9(", x)] = 0. with π being the stationary distribution of the stochastic process (æı)420-
SA subsumes many important algorithms. A prime example is stochastic gradient descent (SGD) for minimizing function (()) given noisy estimates g(0, x) of its gradient. Linear SA schemes include SGD for quadratic objective functions, as well as various RL algorithms such as linear TD-Leaming (in which g is not the gradient of any function and standard SGD results do not apply).
Of particular interest to us are SA updates given by nonlinear function g(0, .r) example is learning Generalized Linear Model (GLM) y Rs a(2 0) with a nonlinear mean function IR + R. A power approach, developed in [19, 36, 37, 64], uses a surrogate loss function, where the corresponding SGD update takes the form 0x+1 02 + a(or ( ! 0s) yk Wkk where Ty (wk, His is the observed covariate- response pair. Common choices of a include the identity map for linear regression, the sigmoid function for logistic regression, as well as Rectified Linear Unit (ReLU) and its various smoothed versions (e.g., ELU and SoftPlus) for ReLU regression [7, 18, 19, 30, 36].
One motivating
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Furthermore, we are interested in the setting where the data sequence (x4))20 forms a Markov chain, going beyond the common i..dd data setting. The Markovian model captures wide range of SA problems in machine learning where stochastic data exhibit serial dependence [5, 33, 38, 53].
Classical work SA focuses on diminishing stepsizes [10, 58]. Constant stepsize schemes have recently gained popularity due to easy parameter tuning, fast initial convergence, and robust empirical performance. Non-asymptotic error bounds have been obtained for constant stepsize SA [17, 60]. Recent work further provides fine-grained characterization of the distributional and steady-state behaviors of the iterates [20, 33, 45, 67, 69]. Two recurring themes in these results are weak convergence of the distribution of 0₂ and the presence of an asymptotic bias B[0x0] 8" x a. both having important implications for iterate averaging. bias reduction and statistical inference [34].
Note that most previous work studied the nonlinear update setting and Markovian data setting separately-eeg. in [20, 67] for nonlinear SGD with i.i.d. data, and in [33, 34] for Markovian linear SA. The linearity or i.i.d. assumptions imposed in these prior works are restrictive, especially in the face of modern machinecreinfforcmment learning paradigms where nonlinear models are the norm and dependent data is common. Moreover, the absence of prior work dealing with Markovian nonlinear SA is not merely an overlook as argued below, this setting significantly more challenging.
Our Contributions In this work, we study constant-stepsize SA with both Markovian data and nonlinear update. In Section 3. we clucidate the new challenges that arise from the simultancous presence of these two structures, which break key steps in previous analyses of the i.idd or linear setting. Due to the interaction between these two structures, establishing weak convergence is far from obvious, and the asymptotic bias exhibits new behaviors. Consequently, analyzing the nonlinear Markovian setting requires more than simply combining previous techniques.
To address the above confounding complication, we exploit the smoothness and recurrence structures of the SA update, thereby developing fine-grained analysis of the correlation of the parameter Og and data Ty.- This allows us to establish for the first time the weak convergence of the joint process (Jr,, 02) to unique invariant distribution, represented by the limiting random variable (Iee, 0. As by-product of our analysis, we derive finite- time bounds on E[]|@ - (11r_.. the 2p-th moments of the errors, generalizing the results in [17, 20, 60] to higher moments and to the nonlinear Markovian setting. In addition, we prove a Central Limit Theorem (CLT) for averaged iterates.
Moreover, we show that nonlinearity and Markovian structure contribute in multiplicative way to the asymptotic bias of the SA iterates. We obtain the following bias characterization: TE(O(2) 0" abm + bn + 6c) + (((TT,))) )8/2), We provide explicit expressions for the vectors bm bn, b,, which are independent of a. 6m represents the bias component due to Markovian data (quantified by the mixing property of 2x)), and bn the bias due to the nonlinearity of g (quantified by the second derivative g²). Importantly, we identify the compound term be, which is absent in both nonlinear SA with i.i.d. data and linear SA with Markovian data. We explore the algorithmic implications of the above results on SehaardonnRooberr (RR) extrapolation [31]. We show that PR averaging reduces the variance but not the bias. whereas RR extrapolation eliminates the leading bias term a(bm + bn + be), reducing the asymptotic bias to higher order of a.
(PR) averaging [35, 56, 59] and
Related Work Postponing a detailed literature review to Section 6, here we remark the recent works most relevant to ours [1, 44, 45, 46), all studying Markovian nonlinear SA. The authors of [1] present an upper bound for the PR-averaged iterates and, similar to our results, demonstrate the effectiveness of RR-extrapolation in reducing bias, but lack weak convergence result for last iterates. In [44], the authors suggest adopting the ordinary differential equation framework to prove weak convergence of iterates and derive an upper bound for the asymptotic bias, which contrasts with our equality characterization with a closed-form solution for the leading-ordet bias. In [45], the authors prove weak convergence of (x,, 0z) using coupling, but only in the linear setting, not for nonlinear SA. In the latter setting, their weak convergence analysis is thwarted by challenges similar to what we elucidate in Section 3, the interplay between nonlinearity and Markovian data leading to "double recursions." The coupling technique differs as well: we couple two processes by sharing data x, = x/ while in [45], they initialize two processes with different Zg and zgg and analyze the stopping time when 0, = Or. Moreover, they only present an upper bound for asymptotic bias, while ours presents a fine-grained characterization in Theorem 4.6 necessary for justifying RR- RR-extrapolation Lastly, the paper [46] discusses stepsize selection and its impact on the asymptotic statistics of PR-averaged SA with both constant and diminishing stepsizes.
2

---

Notations The Euclidean norm is denoted by || |l. The notation "u & v" represents the tensor product between vectors u and v, and "uSk" denotes the k-th tensor power of vector u. The ball with radius B is (B)) := {0 E R |00| S 33. [(z) denotes the distribution of a random vector and Var(z) its covariance matrix. Let (2(R be the space of square gquare-integrabl distributions on Rd and P2 (X' x R24 be the space of distributions & on X' x R with qquare-integrabl second marginal on RR. The W between two probability measures μ and v in P2((2)) is defined 0'
[()) μ. C(0) = v), where I[(H,, v) is the set of all couplings between μ and v. Extending to X' x Rd, we define the metric d d(2z,, 0), (a', .)))
as W2(H, v) = inf (e((r)) { (B[I)
((11)) >
/I x') + 0 0' 0²12, and denote by W2 the extended Wasserstein-2 distance w.r.t. d.
The lowercase letter and its derivatives co. co. etc. denote universal numerical constants, whose value may change from line to line. We use = s(0o, 0", Mi L, R) and its derivatives to denote quantities (scalars, vectors, or matrices) that are independent of the stepsize a and the iteration index k, but may depend on the initialization fy. SA primitives 8", 14 and L. and the coefficient R for the geometric mixing rate of (zx) in Assumption I, As we are primarily interested in dependence on a and k, we adopt the following big- O notation: II (h(a, k)) if holds that [[ S s ||h(a, ki]l-
2 Problem Setup and Preliminaries
Let (22))22 be a Markov chain on a general state space X. Consider the following projected stochastic approximation (SA) iteration:
I B(g) [o a(g(O(") m.) + (6+1((())))
#+1
(2.1)
where g : R2d x X Rdd is a deterministic function, (6x)22 are i.i.d. zero-mean random fields, > 0 is constant stepsize, and (0) := arg ming: =lls || - 0l] is the projection operator. We shall omit the superseript (a) in 0g when the dependence on a is clear from the context. In this work, we also consider the projection-fiee free variant of the iteration 12.1) with 3 co.
We denote by π the stationary distribution of the Markov chain (2x) and define the shorthand g(t) = E, [g, 22), where [- denotes the expectation with respect to x ~ S. The algorithm (2.1) computes an estimation of the target vector 8" that solves the steady-state equation E, Eg(g(O, x) ] = 0.
Our general goal is to characterize the relationship between the iterate Gg and the target solution 0*.
In the following, we state the assumptions needed for our main results. For a more detailed discussion of the assumptions, we refer readers to Appendix B.
Assumption (Uniform Ergodicity). (2z))22 a uniformly ergodic Markov chain on a countable state space (X, B()) with transition kernel P and a unique stationary distribution n. That is, there exist constants r E [0, 1) and R > 0 such that (( - -|/TV S. Rrr Vx E X.
The countable state space ensures separability under the 1(x #x) x'} metric, necessary for constructing a valid coupling in the invariance proof and establishing a well-defined P* for bias characterization. We keep the notation general allow future extensions to general state space and broader applicability of our results. All irreducible, aperiodic, and finite state space Markov chains are uniformly ergodic. The uniform ergodicity assumption is common in prior work on SA with Markovian noise [6, 21, 24, 33, 48]. Relaxing this uniform ergodicity assumption, in the style of [45, 52, 60] is possible but orthogonal to our focus, and thus we do not pursue this direction in this work.
We allow the chain (#x) to be arbitrarily initialized rather than from the stationary distribution т. An important quantity is the mixing time of the Markov chain, defined as follows.
Definition 2.1. For 10, the e-mixing time of (zk) denoted by T 2 1, is defined as min k Z 1 sup=ex || (z, - S e).
Under Assumption 1, the e-mixing time satisfies S. K log for all E (0, 1), where K > is independent of e. In the sequel, unless otherwise specified, we always choose c = a and let 7 = T.
The following assumptions on the nonlinear function g in (2.1) is standard in the literature [17, 20, 32, 45, 48]. A wide family of g functions satisfies these assumptions, with the Tegrreuuariiedd logistic regression of GLM being standard example.
3

---

Assumption 2 (Differentiability and Linear Growth). For each I E X, the function g(6,x) x) is three times continuously differentiable
with uniformly bounded first to third derivatives, i.e.
SupeeR= [g x||| < +o0 for i 1,2.3 3. x E X. Moreover, there exists a constant I1 > 0 such that (1)llg()(0 (0, (0', S for all 0,0 0 E Rd, i 0,1,2 and x E X, and (2)
[I)( & for all x E E
The linear growth condition in Assumption 2 implies that g(0, is L1 -ipischeiitz w.r.t. 0 uniformly
in x. When is a linear function, i.e. g(0,z) x)) = A(x)0 + b(xx) this assumption is satisfied with supsex || Aa:)ll
oo and su [|b(z=]] < oc, which are commonly assumed for linear SA. The above assumption immediately implies that the growth rate of || and [gg] will be at most linear in 0,
ie.. (19(0, x> S (1 0 + 1) and [[)())]| S ( 0' +'1 1).
Assumption 3 (Strong Monotonicity). There exists μ 0 such that (0-8. g(0)) < - 0' 12 v0, 0' E IR.. Consequently, the target equation ō(0) = 0 has a unique solution 6"
When is a gradient field, Assumption 3 is equivalent to strong convexity. For notational simplicity, we assume the strong monotonicity parameter satisfies μ S 1 r, where is the convergence factor in Assumption 1. For general μ., our results remain valid with μ replaced by min(u, 1 -r..
1-=1 We next consider the noise. Denote by Fx the filtration generated by (2x, Oc, Ee+ 1 U (xx:0x) Assumption 4 (Noise Sequence). Lel E ln be given. The noise sequence (Ex)R2) a collection of i..dd random fields satisfying the following conditions with L2g > 0:
Ei5x+1(0) =0 and [1(3)) 2m] S L2pp - 00 + 1), AO V
(2.2)
Define C(0) = (0) 2 and assume that (()) at least twice differentiable. There also exist Me, k 2 0 such that for Rd,, we have max; (0]] S M + 110 - 0²1)%²)
In the sequel, we set L = L1 + L2. and without loss of generality, we assume L 2 1.
When p L, the second inequality in (2.2) only requires linear growth expectation. which relaxes the almost sure linear growth condition in [17]. The constraint on the covariance matrix C(O) is lenient and satisfied in most regular enough settings, as shown in [20].
3 Analytical Challenges and Techniques
In this section, we claborate on the challenges and techniques in proving the above results.
Previous work has established weak convergence of (æx, 0x) separately for nonlinear SA with i.i.d. data, and for Markovian linear SA. The high-level approaches used in two representative prior works can be summarized as follows. The work [20] on nonlinear SGD leverages local linearization of g through Taylor expansion. The work [33] on Markovian linear SA exploits the mixing property of the Markovian noise to regain approximate independence, particularly between 24 and fx- for sufficiently large It is tempting to expect that nonlinear SA can be analyzed by combining these two approaches. Perhaps surprisingly, such a simple combination would not work due to the interplay between nonlinearity and Markovian structures.
To demonstrate this challenge, let us seek establish weak convergence in the Wasserstein dis- tance 22 via forward coupling [29], an approach employed by both [20, 33] as well as others [25]. Specifically, we consider two SA iterate sequences (o(") )20 and (oL²) ):20 from different initializa- tions e/ and 0/" coupled by sharing the data sequence (zx (zz)kzo: k++ = a + ag(t)") , zx) and
g|2| k+1 = 0/21 + =ag(0
21 .x).. To establish convergence in W2, we consider the difference sequence
Wk+1 == k+ k+1 wr a(s(0 ax) s(0 ),,)
(3.1)
and it suffices to prove Wi converges to 0 in mean square: [ 112] S p B |2] for p < 1. With this goal in mind and following the idea from [20], one may first linearize the night-hand side of the difference dynamic 13.1) and obtain the approximation
Wh+1 wi + ag' (0/2)
Ix w.
(3.2)
4

---

Next, to analyze the drift of the Lyapunov function Bi]lw>|1 and handle the Markovian noise (xx), we use the conditioning technique from [33]. We condition on the information of T steps before, denoted by F == o ((00" ofd) .x) t & k - r). Ignoring higher-order terms and assuming a one-dimensional problem for simplicity, we obtain that
B|]lw]+1 [1 E
IF (1 + 20n' (0) mx)) [r
E wk- 12 + 2nl (0( Ik) F
(3.3)
where we use W2 R wk-7 for small a (this argument, which is made precise in [33, 60), essentially exploits the fact that 24 evolves faster than 0x).
To prove dynamic (3.3) converges, it boils down to showing the "gain matrix" E[g (( xxk) FR- is negative/Hurwitz To further simplify, we assume k is large that the chain (2k) is distributed per its stationary distribution π, in which case the gain matrix simplifies to Ez [9' (0l0 =0)
Analyzing this gain matrix is where our analysis diverges from previous work. If the SA update were linear, i.c., g(0, z) A(z) then the gain Big'(0 x x0)) = E,, [A(=x)]] would be independent of e/21 and its Hurwitz property is a standard and necessary condition for proving convergence of linear SA. the data sequence (ar) were i...d, then 0% would be independent of z& and hence the gain becomes EElg (0 =xx)) )] = E [E zo 110 = Hig' (e ] with g(-) := Exwn ig(,,)),, where the Hurwitz property again follows from standard assumptions on ÿ.
However, both arguments fail for the Markovian nonlinear setting. Common assumptions for nonlinear SA only ensure Hurwitz Ez (0, =0] given 0. This does not imply the desired Hurwitz 10 ). precisely owing to the simultaneous presence of (i) the dependence of g' on both 6x and go (due to nonlinearity) and (ii) the correlation between 0xx and go (due to Markovian).
Our Approach We overcome this challenge by carefully analyzing the properties of the above dependence and correlation. Therefore, for sufficiently large т, we further decompose (3.3) as
E| +1 =
E -k-
12 (1+ 2 g (6) 2l
2x)) [R--11)]
E || 1-2cx 2cx 10 vx) Fn-r]]
+ +2 [E] (E[g'(0 .xx) o'(0R__,
xn) 1))=
2Eig' - 11 Hurwiix
< |BBllluk 113]
aiE |E (wx-r. (0o xx) 0(0.2 mk) g(0 h0 In) + xni) F [F
(g(o!") .xx) g(0 .xx) for t k, and obtain the second term in the last inequality. Next, we propose employing two different Taylor expansions to prove that of higher orders of a. We first apply the Taylor expansion g(0!") xxx)-
where we approximate wg A Wk-7, wig' (agg(e!)) .x)
|| ( (I] + TarT)). where Ti = min( [[0@[ "I 110 Il. - 110 1o0__110 + 1. When 0 and e|2 are not close to each order, i.e. when ||wx||| is large, is not necessarily of higher order. Therefore, we consider second type of Taylor expansion on g(e!") .x2)
g(0 .rx) and ((( 2k) -0 - FA). However, this only achieves
and g(0 xx)) _(0 24). The intuition for the second type of Taylor expansion is to analyze and bound by the small distance between Afd and 0f2 for j E (1, even when ||wx|| || is large. This achieves
Simultancously applying the two Taylor expansions will yield ||wx||erT] (l/wwell + arTi). ar][ Finally, we overcome this challenge by carefully analyzing the boundness of Ti; see Theorem 4.1 and its proof.
In parallel to the above coupling approach, we also explore an alternative approach by verifying the joint Markov chain (Ik,, 0%) satisfies certain irreducibility and Lyapunov drift conditions, which in turn imply the chain is ergodic. To apply this approach, we exploit additional properties of the SA noise, namely miniorization, which satisfied in many applications where additional randomness injected to the SA update. While the high level strategy of this approach is well developed [23, 50],
5

---

carrying out the analysis of each step is technically involved. In particular, we need to translate the minorization property the noise to the irreducibility the joint chain (zx, 0x)) which is nontrivial in the presence of Markovian noise and nonlinearity.
4
Main Results
4.1 Weak Convergence of Projected SA
Our first main result proves the ergodicity of the joint process (Iy, 0x)220 of the projected SA (2.1).
Theorem 4.1 (Ergodicity of Projected SA). Suppose that Assumption 1-4 (p 1) hold. The projected SA (2.1) is applied with radius parameter 21|0*|| S 3 co. For stepsize a > that satisfies the constraint aTa S [040+968]]33 the Markov chain (Ix, 0g 02)220 converges to a unique
stationary distribution Fa. E P2 x )R Let Va == =[(00) be the second marginal of Vo For k 2 2T. it holds that
W² W2(C(Ok), W2(C(TX; 0x), S aau) s00, 0" 1,, T., R)-
Theorem 4.1 generalizes prior weak convergence results for constant stepsize SA/SGD either under ii.d. noise [20, 67] or linear update [33, 45]. Our stepsize condition aTa S n/L² coincides with [33, 60] linear SA, special case of our setting.
The proof of Theorem 4.1 highlights the stabilizing effect of the projection operation (2.1). This effect, together with the smoothness of update function controls how the Markovian correlation propagates through the nonlinear update, allowing us to overcome the challenges discussed in Section 3. It is unclear whether our proof, which is based on Markov chain coupling, can be fully generalized to SA without projection. Nevertheless, we show that such a generalization is possible for a sub-family of nonlinear SA where g possesses the additional structure termed "asymptotic linearity", which satisfied by, e.g., SGD applied to certain settings of logistic regression. For a formal statement of this result and proof, refer the readers to Appendix E.
As by-product of our analysis, we establish the following non-asymptotic 2p-th moment bound on the стrоr 0₂ 0r Let 0c+1/2 == 0, + a(g(E,, xz) - E++1 (0.) denote the pre-projection iterate.
Proposition 4.2. Consider (0z)k20 of iteration (2.1) with 3 [2]|0]]] II, oo). Let Assumption 1-4(2p)
hold. If stepsize satisfies aT, S Cpli, with co S 1, the following holds for all k 2 Ta.
E E| [ 0" |20| S
E[[ 1/2 8" |120] S cp.1 (1-1(11app))) ++1 [ E[ | t, P.s L, p)-
Proposition 4.2 implies that B|| - 0" 11 & (aT) P for sufficiently large k. generalizing the results of [17, 20, 60] higher moments and the nonlinear Markovian setting. Notably, this result holds even without the projection operation in the SA update (2. i.e., 3 xo. Furthermore, Proposition 4.2 can be used derive high-probability tail bounds using the Markov inequality.
4.2 Weak Convergence without Projection
Parallel the coupling approach, we consider an alternative approach for establishing weak conver- gence via verifying irreducibility, positive Harris recurrence, and V-uniform ergodicity [50] of the Markov chain (zg,0s). This approach applies to nonlinear SA even without projection. To verify irreducibility, we exploit the following additional noise structure.
Assumption 5 (Noise Minorization). For each 0 E TRdd, the distribution of the random variable & (0), denoted by Ço, can be decomposed as Ço {1,9 + Ç2.0, where the measure Ç1,0 has density, denoted by po, which satisfies infeec Po (t) > 0 for any bounded set C and any IR...
A similar assumption is considered in [5. 67]. This assumption is mild and satisfied by any continuous random field supported on Rd Introducing such (small) continuous noise is often part of the algorithm design for inducing privacy [2, 22] exploration [28, 55]. Without Assumption 5, the chain may fail to be irreducible even when the other assumptions are satisfied; see [33] for a counterexample.
Under Assumption 5, we obtain the following ergodicity result paralleling Theorem 4.

---

Theorem 4.3 (Ergodicity of SA Minorization). Suppose that Assumption 1-3, Assumption 4(p 1), and Assumption hold. For stepsize a 0 that satisfies the constraint LT, < C2ps, the Markov chain (xx; 0x x20 of (2.1) with B = oo is V-uniformly ergodic with Lyapunov function V(x, 0) |10 112 112 - and unique stationary distribution Va E E x Rd). Moreover, defining the -nnomm ||~|| == [v(dz)|V(x)) we have
[[r,, 0k) - Pa Pally S xsp; Yi 0o) E X Rd 4k 0,
(4.1)
where the constants p (0,1) and (0, oo) may depend on a.
4.3 Non-Asymptotic Convergence Rate and Central Limit Theorem
In the sequel, let (Ioo, ) denote the random vector whose law is the stationary distribution Po given in Theorem 4.1. As a corollary, we have geometric convergence for the first 2 moments of 0g- Corollary 4.4 (Non-Asymptotic Convergence Rate). Under the setting of Theorem 4.1, for any initialization of 0o E Rd we have
|| [x] E(A())] S (1 - aau) s' 300,, 11, I., R), and
| E E(o ( Til (1 aqu) s0(0,, 0" 11, L, R)-
Moreover, the convergence rate established in Theorem 4.1 fast enough that we can use it to prove a Central Limit Theorem for the average iterates.
Corollary 4.5 (Central Limit Theorem). Under the setting of Theorem 4.1, as h oo we have
1 k-1 (0. B(0x=)) = (0, ) where E(a) = lim IE [E VE
k-1 (0z B(O 82
Establishing the CLT sets the stage for using the SA iterates for statistical inference tasks such as confidence interval estimation. We discuss this in greater detail in Section 4.4 after characterizing the asymptotic bias, another important ingredient for using SA for inference.
4.4 Bias Characterization
In this subsection, we characterize the asymptotic bias E[O[o)] - 0" Understanding the bias structure has important algorithmic implications for bias reduction, which we explore in Section 4.5, as well as for more efficient statistical inference and confidence interval estimation [34].
Theorem 4.6 (Bias Characterization). Suppose Assumptions 1-4(p 3) hold. For each stepsize satisfying orT I.2 C3J5, the following holds for some vector b independent of a
Eiglal1 0 = ab ((TTa)
(4.2)
More specifically, the leading bias can be decomposed as bm + bn + bes where
bm - (o El('0))))E x (000 2x))),)))) xx))
(4.3)
b. (g((0)) Elg(0 x ) 882 (
(4.4)
b. (1((0)))'""000)4 Eigg( xxx 2 h(0" xxx )1 E(h(O" xxo) ) & 9(0", )1)
(4.5)
with A = (d((0))0++
and h , (1 (1 -1)p=-1)((a [I, de' (0 ,x'),
with the kernel P being regular conditional probability on X that satisfies Jn π. (dz) P(z, C* Sc T(dy) (y, B). all B, C B(X).
We defer the detailed proof to Appendix I. A few remarks are in order. First, we emphasize that (4.2) essentially equality, indicating non-zero bias of order whenever b of 0 (up higher order terms). Notably, the Polyak-Rupped averaging of the iterates cannot eliminate this bias. Note that the bias expansion in (4.2) applies to both weakly converged projected and non-projected SA. Our analysis shows that compared with the non projected SA, the projection operator induces an extra bias term of the order O(a²73). which is negligible relative the main terms in in (4.2).
More importantly, Theorem 4.6 provides an explicit expression the leading bias, which decomposes into three components: the Markovian part, the nonlinearity contribution, and compound term,
7

---

which is unique in nonlinear Markovian SA. Specifically, dm in (4.3) is associated with the Markovian multiplicative noise, where the matrix _ II in the h function determines the mixing time of the data sequence (Ir )x2.).2. The term bn in (4.4) is linked to nonlinearity, as reflected by the Hessian term g0))" = Flgg (0", _, which quantifies the nonlinearity of g and is equal to zero in the case of a linear g. Lastly, bg in (4.5) is the compound term, due to its dependence on both the Markov noise (/ function) and the nonlinearity measure g". In particular, we note the following two special cases: (1) When 9 is linear function, g"(0") = O. Hence, bn bc O, and bm recovers the result in [33]; (2) When (zx) is i.i.d. sampled from the stationary distribution n, we have h(0", x(0*,=)== = 0 Vr E X, for P P = II. As such, 6m b. O, recovering the result in [20]. The presence of the compound term be suggests that as the SA structure becomes more nonlinear and the underlying Markov chain mixes more slowly, the impact on the bias is multiplicative rather than simply additive, a surprising phenomenon not unveiled in previous studies. It is possible to improve the residual order from 3/22) to O(a²) with a more refined characterization of the asymptotic second moment =x 0*) s by following similar strategy as our current approach. We leave this refinement out of the scope of the current paper.
4.5 Algorithmic Implications
We examine the practical implications of our weak convergence and bias characterization results, particularly for this subsection, we focus on the dependence on the stepsize a and iteration index k. and make use of the big-O notation from Section Recall that b is the bias vector defined in Theorem 4.6.
(PR) tail averaging and Richardson-Romberg (RR) extrapolation. In
PR averaging [56, 59] is a classical approach for reducing the variance and accelerating the convergence of SA. Here we consider the tail-averaging variant of PR averaging, defined as kkp.k == k- Σ Or, for k 2 kn, with a user-specified burn-in period ko 2 0 (a common choice is ko = k/2). The following corollary, proved in Appendix J, provides a non-asymptotic bound on the mean squared error (MSE) for the averaged iterates 0kg
Corollary 4.7 (Tail Averaging). Under the setting of Theorem 4.6, the tail tail-averaged iterates satisfy the following bounds for all k > ko + 2T and ku N Ta + cu Lora
log
(KOO 1- = a a²|lbb1 +060 (aT)
+ +0
Ta ko
)
+0 (1 (1-a4)) 84//
a (k ko)
Ti: asymptootic squared bias
T2: variance
Ts: optimizztiion
Corollary 4.7 shows that the MSE can be decomposed into three terms and elucidates how these terms depend on at k, and other problem parameters. particular, the term Ti corresponds to the asymptotic squared bias || 1*1 which is not affected by averaging. The term T2 is associated with the variance Var( which decays at rate 1 due to averaging. Lastly, the term oo 11 which decays geometrically in ky thanks the
T3 represents the optimization error |B0 * use of a constant stepsize a and the tail-averaging procedure.
Note that averaging does not affect the bias of order a. With the precise bias characterization in Theorem 4.6, we can order-wise reduce the bias to O(a3/2) by employing the RR extrapolation
technique [61]. Let kg.k and g(2a) denote the tail-averaged iterates using two stepsizes a and 2a
g(o)
with the same data (Ix)k20- The RR extrapolated iterates are defined as 0/ = 20(0)) ((am)
kg.k k.
Corollary 4.8 (RR-Extrapolation). Under the setting of Theorem 4.6, the RR- RR-extrapolated iterates satisfy the following bounds for all k > Ko + 2Ta and kn 2 Ta + au
log (ct.).
o (1 (1-ou))bof ho/2
0-11]] = ((ara)))) 0 1 k )m) E B[10kon k -
a (k - ko)
Backed by the CLT in Corollary 4.5, the iterates of constant-stepsine SA can be used to construct confidence intervals of 0*. For i.i.d. data or linear SA, this approach has been explored in [34, 47, 66, 67] along with an appropriate variance estimator [26, 66]. In our Markovian nonlinear setting, where the iterates are biased, it crucial to use RR extrapolation for bias reduction. Once the bias is accounted for, the power of using constant stepsizes reveals itself as it leads to rapid mixing and
8

---

low correlation of the iterates. Together, they lead to efficient confidence interval estimation schemes using nonlinear Markovian SA; see the empirical results in [34] showing its efficacy. In contrast, the classical diminishing stepsize paradigm often suffers from high correlation [13] and in turn inaccurate variance estimation, resulting in unsatisfactory coverage probability with finite data [34].
4.6 Implications for Learning GLM
Generalized linear models (GLM) extend linear regression to the model - 0*), where W is the covariate, Y the response variable, and is called the mean function. For any monotone (and potentially nonlinear) o, the powerful framework developed in [19, 36, 37, 64] allows one to formulate the estimation of 0* as minimizing an appropriate convex (surrogate) loss function. Applying SGD to this loss leads to a nonlinear SA update, to which our results are applicable. Below we discuss their applications in two concrete examples of GLMs.
Logistic Regression Logistic regression uses a sigmoid mean function (xx) 1+exp(-a) (=) Suppose the covariate we is sequentially sampled from uniformly ergodic Markov chain with bounded state space W C TRd, and conditioned on wi the response yk is Bernoulli distributed with parameter (1 + exp(-w) g 0*) j)- SGD applied to the Iz-regularized negative log-likelihood function takes the form of the SA update 0x+1 = 02 + ag((k, I&), where Ty = (Wk. Me) E W {0, 1} and g(Ok, 22)) = - w/. w (o(( 0%) - yk) 20g. For simplicity, we do not consider & E-perturbation, i.e.. Ex+1 (0x) O. It easy to verify that this g is strongly monotone and sufficiently smooth with most linear growth in [0). hence satisfying Assumption 1-3. Therefore, all the results in Sections 4.1-4.5
apply logistic regression with constant stepsizes and Markovian data.
Smooth ReLU Regression The mean function a can be interpreted as playing a similar role as the activation function in neural networks. Widely adopted is ReLU activation (xx) max(0, (0, xx) as well as its various smooth approximations [7, 30]. The problem of learning 0* in this setting, sometimes called ReLU Regression, has been studied in the last decade and recently regained attention [19, 36, 37, 64). Unlike linear or logistic regression, the least squares and maximum likelihood formulation associated with such nonlinear mean functions is non-convex. Nevertheless, the convex surrogate loss framework in [19, 64] still applies. As an example, we focus on the SoftPlus activation (x) log(1 + exp(xx))/c )/t with a temperature parameter c > 0 [30]. With Lerreullarization the resulting SGD iteration is 0x+1 0₂ a(w, (: log(1 exp(1we 9x)) yk) + A0x), where the evariate-responss pair (0s, xx) is before. This problem can again be cast nonlinear SA with strongly monotone and smooth g, satisfying Assumptions 1-3. All results in Sections 4.154.5 apply.
Numerical Experiments
In this section, we provide numerical experiment results to verify our theoretical results. We run SGD on L2 L2-regularized logistic regression with Markovian data and constant stepsizes, where the covariate I2 E 1 is sequentially sampled from an autoregressive (AR) model of order 1; specifically, Tt-1 = 0.9x; + S1+1 with Ge i.i.d. following N (0, 1), and the stationary distribution Too ~ N(0, (1-11 )). The binary dependent variable y is sampled from (ermoulli(1/(1+ees) xx))) xz))
with wt = 1. The regularized parameter is set to À = 0.0001.'
To examine the asymptotic bias, we run the experiment for an episode length of 10?, with Markovian data as well as i.i.d. data sampled from (O, 1/(1 - 0.9²)). We plot the errors (distance to 0*) the PR averaged iterates and the RR extrapolated iterates, for different stepsizes a. Figure (a)) verifies the presence of an asymptotic bias approximately proportional to the stepsize a, and illustrates the effectiveness of RR extrapolation in reducing this bias. In Figure 1(b), we compare the bias under Markovian data (Ir+1 ~ P(- P()(z))) and i.i.d. data (x, ~ Ioo). Interestingly, Figure 1(b) reveals that Markovian data does not necessarily lead to larger bias than i.i.d. data. This is consistent with our theory, as the three bias terms by, by,, be may have opposite signs leading to cancellation. This result suggests that in the presence of nonlinearity, one should not avoid Markovian data simply for the sake of reducing bias. Rather, RR extrapolation may be more effective for bias reduction.
'The experiments were conducted on two sockets of Intel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz with 566Gb of RAM. Implementation details and code are available at https: //g /gthttb...bt....g com hucpyhoooodog/////// nonlinear sa- bias.

---

0-5 10 T3
Moy
(a) This plot shows the errors of PR-averaged iter- ates and RR-extrapolated iterates, all generated using Markovian data.
(h) This plot compares the errors under Markovian data (ir, P({[x,-)) and iid data (ar x), where all other settings are same.
Figure 1: Experiment results illustrate the properties of asymptotic bias.
To verify the CLT in Corollary 4.5, repeat the experiment 1000 times with episode length of 10th and stepsize a 0.8. We compute the PR averaged iterates and plot the histogram and the quantile-quantile (QQ) plot in Figure 2 in Appendix C. The close alignment between the histogram and the normal curve Figure 2(a) and the linearity of the points along the 45-degre reference line in the QQ plot in Figure 2(b) confirm that the empirical distribution follows normal distribution.
6 Related Work
General SA and SGD. SA and SGD can be traced back to the seminal work of [58]. Classical work assumes a diminishing stepsize sequence, and has shown almost sure asymptotic convergence to 8" [8, 58]. Subsequent works propose the iterate averaging technique, now known as Polyak- Ruppert (PR) averaging, reduce variance and accelerate convergence [56, 59], and also establish Central Limit Theorem for the asymptotic normality of the averaged iterates [57]. The asymptotic convergence theory SA and SGD is well developed and extensively addressed in many exemplary textbooks, see [3, 40, 65]. There are also recent works studying the non-asymptotic convergence with diminishing stepsizes [12, 14]. The recent work [15] establishes the high probability bound on the estimation error of contractive SA with diminishing stepsize.
SA and SGD with Constant Stepsizes. There has been increasing interest studying SA with constant stepsize. Many works in this line provide non-asymptotic upper bounds on mean squared eтror (MSE) ( 0" [3]. Works in [25, 42, 51] study linear SA (LSA) under i.i.d. data. Recent works extend the analysis of the MSE to LSA with Markovian data, such as [24, 52, 60]. There are also works providing upper bounds of MSE for general contractive SA with Markovian noise [14, 17].
In addition to non-asymptotic guarantees, some works focus on the asymptotic behavior of SA iterates. loses the almost sure convergence
Recent works have shown that when using constant stepsize, guarantee in the diminishing stepsize sequence regime, and at best can achieve distributional con- vergence, as demonstrated in [16, 20, 25, 33, 66, 67, 69]. The presence of asymptotic bias is also recurring theme in recent literature, with precise characterization given in [20] for strongly-convex SGD with i.i.d. data and in [33] for LSA with Markovian data. Works in [34, 51, 66, 67, 69] also establish Central Limit Theorems for averaged SA iterates with constant stepsizes.
7 Conclusion
provide the first weak convergence and steady-state analysis for constant-stepsize SA with both nonlinear update and Markovian data. Our analysis elucidates the compound effect of nonlinearity and memory, which leads to new analytical challenges and behaviors. A limitation of our results the use of projection step the noise minorization assumption. Whether they can be removed is worth investigating. Other future directions include refining the dimension dependence our results, as well as theoretical investigation of statistical inference.
10

---

Acknowledgement Y. Chen is partially supported by National Science Foundation (NSF) grants and NSF CCF-2233152. Y. Zhang and Q. Xie are supported in part by NSF grants CNS-1955997, EPCN-2339794 and EPCN-2433546. Y. Zhang is also supported in part by NSF Award DMS-2023239.
References
[1] Sebastian Allmeier and Nicolas Gast. Computing the bias of constant-step stochastic approxi- mation with Markovian noise, 2024. 2, 16
[2] Borja Balle and Yu- Xu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Jennifer Dy and Andreas Krause, editors, Pro- ceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 394-403. PMLR, 10-15 Jul 2018. 6
[3] Albert Benveniste, Michel Metivier. and Pierre Priouret. Adaptive Algorithms and Stochastic Approximations. Springer Berlin Heidelberg, 1st edition, 1990. 10
[4] Dimitri P. Bertsekas. Reinforcement learning and Optimal Control. Athena Scientific, Belmont, Massachusetts, USA, 2019. 1
[5] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with Markovian noise: from acceleration to variational inequalities, 2023. 2,
[6] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Operations Research, 69(3):950 973,, May 2021. 16
[7] Koushik Biswas, Sandeep Kumar, Shilpak Banerjee, and Ashish Kumar Pandey. Smooth maximum unit: Smooth activation function for deep networks using smoothing maximum technique. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 784-793, 2022. 1,
[8] Julius R. Blum, Approximation methods which converge with probability one. The Annals of Mathematical Statistics, 25(2):382 386, 1954. 10
[9] Vivek S. Borkar. Stochastic Approximation: Dynamical Systems Viewpoint. Hindustan Book Agency Gurgaon, 2008
[10] Vivek S. Borkar and Sean P. Meyn. The O.D.E. method for convergence of stochastic approxi- mation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):4474469, Jan 2000. 2
[11] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends Machine Learning, 8(3-4):231-33 -3577, November 2015. 16
[12] Siddharth Chandak, Vivek S. Borkar, and Parth Dodhia. Concentration of contractive stochastic
approximation and reinforcement learning. Stochastic Systems, Jul 2022. 10
[13] Xi Chen, Jason D Lee, Xin Tonng, and Yichen Zhang. Statistical inference for model parameters
in stochastic gradient descent. Annals of Statistics,
2020. 9
[14] Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A Lya- punov theory for finite-sample guarantees of Markovian stochastic approximation. Operations Research, 2023. 10
[15] Zaiwei Chen. Siva Theja Maguluri, and Martin Zubeldia. Concentration contractive stochastic approximation: Additive and multiplicative noise. arXiv preprint arXiv:2303.15570, 2023, 10
[16] Zaiwei Chen, Shancong Mou, and Siva Theja Maguluri. Stationary behavior of constant stepsize sgd type algorithms: An asymptotic characterization. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1), 02 2022. 10

---

[17] Zaiwei Chen, Sheng Zhang, Thinh T. Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite-sample analysis of nonlinear stochastic approximation with upplications in reinforcement learning. Automatica, 146: 1 10623, 2022. 2, 3, 4, 6, 10, 18, 34
[18] Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (ELUss) 2016.
[19] Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, and Mahdi Soltanolkotabi. Approximation schemes for ReLU regression. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1452-1485. PMLR, 09-12 Jul 2020. 1,
[20] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3):1343 1382, 2020. 2, 3, 4, 6, 8, 10, 16
[21] Jing Dong and Xin T. Tong. Stochastic gradient descent with dependent data for offline reinforcement learning, 2022.
[22] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian Differential Privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 02 2022.
[23] Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier. Markov Chains. Springer Cham, 1st edition, 2018. 5
[24] Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Finite-time high- probability bounds for Ropper-Ruppert averaged iterates of linear stochastic approximation, 2022. 3, 10
[25] 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, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 30063-30074, Curran Associates, Inc., 2021. 4, 10
[26] James M. Flegal and Galin L. Jones. Batch means and spectral variance estimators in Markov chain Monte Carlo. The Annals of Statistics, 38(2):1034 1070, 2010. 8
[27] Gerald B. Folland. Real analysis: modern techniques and their applications. Wiley, New York, 2nd ed. edition, 1999. 16
[28] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration, 2019.
[29] Sergey G. Foss and Richard I.. Tweedie. Perfect simulation and backward coupling. Communi- cations in Statistics. Stochastic Models, 14(1-2):187-22) 1998. 4
[30] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 315-323, Fort Lauderdale, FL, USA, 11-13 Apr 2011.
PMLR. 1,9 9
[31] F B Hildebrand. Introduction to numerical analysis. Dover Books on Mathematics. Dover Publications, Mineola, NY, 2 edition, June 1987. 2
[32] Yu-Guan Hsieh, Franck Tutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the conver- gence of single-call stochastic extra-gradient methods. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Process- ing Systems, volume 32. Curran Associates, Inc., 2019. 3
12

---

[33] Dongyan (Lucy) Huo, Yudong Chen, and Qiaomin Xie. Bias and extrapolation in Markovian linear stochastic approximation with constant stepsizes. Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 81-82, 2023. 2, 3, 4, 5, 6, 8, 10, 45, 55, 56
[34] Dongyan (Lucy) Huo, Yudong Chen, and Qiaomin Xie. Effectiveness of constant stepsize in Markovian LSA and statistical inference, 2023. 2, 7, 8, 9, 10
[35] Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: dini-batching averaging, and model misspecification. Journal of Machine Learning Research, 18(223): -22, 2018. 2
[36] Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of gener- alized linear and single index models with isotonic regression. In J. Shawe- Taylor. R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. 1,9
[37] Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT, 2009. 1,9
[38] Kyurae Kim, Jisu Oh, Jacob Gardner, Adji Bousso Dieng, and Hongseok Kim. Markov chain score ascent: A unifying framework of variational inference with markovian gradients. In S. Koyejo. S. Mohamed. A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 144802-34811 Curran Associates, Inc., 2022. 2
[39] Harold Kushner. Stochastic approximation: a survey. WIREs Computational Statistics, 2(1):87- 96, 2010. 16
[40] Harold J. Kushner and G. George Yin. Stochastic Approximation and Recursive Algorithms and Applications. Stochastic Modelling and Applied Probability. Springer, New York, NY, USA, 2nd edition, 2003. 1, 10
[41] Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach to obtaining an o(1/t) convergence rate for the projected stochastic subgradient method, 2012.
[42] Chandrashekar Lakshminarayanan and Csaba Szepesvári. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty- Evest International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1347-1355, PMLR, 09-11 Apr 2018. 10
[43] Guanghui Lan. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
[44] Caio Kalil Lauand and Sean Meyn. Bias in stochastic approximation cannot be eliminated with averaging. 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-4, 2022. 2
[45] Caio Kalil Lauand and Sean Meyn. The curse of memory in stochastic approximation, In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 7803-7809, 2023. 2, 6, 16
[46] Caio Kalil Lauand and Sean Meyn. Revisiting step-size assumptions in stochastic approximation, 2024.7
[47] Tianyang Li, Liu Liu, Anastasios Kyrillidis, and Constantine Caramanis. Statistical inference using SGD. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018.
[48] Xiang Li, Jiadong Liang, and Zhihua Zhang. Online statistical inference for nonlinear stochastic approximation with Markovian data, 2023.
[49] Michael Maxwell and Michael Woodroofe, Central limit theorems for additive functionals of Markov chains. The Annals of Probability, 28(2):713 724, 2000. 39
13

---

[50] Sean P. Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 2nd edition, 2009. 5, 6, 40, 44,
45
[51] Wenlong Mou, Chris Junchi Li, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jor- dan. On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2947-2997. PMLR, 09-12 Jul 2020. 10
[52] 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):4 1-1153,, March 2024. 3, 10
[53] Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regression with Markovian data: Fundamental limits and algorithms. In H. Larochelle, M. Ran- zato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 16666-16676. Curran Associates, Inc., 2020. 2
[54] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, (444):1574-609 2009. 16
[55] Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y. Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. In International Conference on Learning Representations, 2018. 6
[56] Boris T. Polyak. New stochastic approximation type procedures. Automation and Remote Control, 51(7):98-107, Jul 1990. 2, 8, 10
[57] Boris T. Polyak and Anatoli B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838-855, Jul 1992. 10
[58] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400 - 407, 1951. 2, 10
[59] David Ruppert. Efficient estimations from a slowly convergent Robbins-Monro process. Tech- nical report, Cornell University, February 1988. 2, 8, 10
[60] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Proceedings of the Thirty-Second Conference on Learning Theory, vol- ume 99 of Proceedings of Machine Learning Research, pages 2803-2830. PMLR, 25-28 Jun 2019. 2, 3, 5, 6, 10, 18
[61] Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. Springer, New York, NY,
USA, 3rd edition, 2002. 8
[62] Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018. 1
[63] Cédric Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wis- senschaften. Springer Berlin Heidelberg, 2009. 30, 39, 40
[64] Puqian Wang, Nikos Zarifis, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning a single neuron via sharpness. arXiv preprint 2rX7v22306.07892, 2023. 1,9
[65] Stephen Wright and Benjamin Recht. Optimization for Data Analysis. Cambridge University Press, 2022. 10
[66] Chuhan Xie and Zhihua Zhang. statistical online inference approach in averaged stochastic approximation. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 8998-9009. Curran Associates, Inc.. 2022. 8, 10
14

---

[67] Lu Yu, Krishnakumar Balasubramanian. Stanislav Volgushev. and Murat A. Erdogdu. An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias. In Advances in Neural Information Processing Systems, volume 34, pages 4234 4248. Curran
Associates, Inc., 2021. 2, 6, 8, 10
[68] Yixuan Zhang, Dongyan (Lucy) Huo, Yudong Chen, and Qiaomin Xie. Prelimit coupling and steady-state convergence of constant-stepsize nonsmooth contractive SA. In Abstracts of the 2024 ACM SIGMETRICS/FFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRISSFERFORNANCE '24, page 35-36, New York, NY, USA, 2024. Association for Computing Machinery. 16
[69] Yixuan Zhang and Qiaomin Xie. Constant stepsize Q-learning: Distributional convergence, bias and extrapolation. Reinforcement Learning Journal,
2024. 10
15

---

A
Additional Notations
General Probability We write T1 22 | if random variables and are conditionally independent given 23-
Recall that we define the metric d((2, 0), ()) [[ 0-1 for the space X xR Thus, for ji and D in P2 x Rd), ) the Wasserstein-2 distance w.r.t. d computed as
W2(a, = inf [B + + x7 + 110 0111) [((x, = p. [((',, (((x''0)) 8)) = }
General State Space Markov Chains Throughout the paper, we assume that X' is a Borel space, Let P denote the transition kernel. We call ा the stationary distribution of P if it satisfies Sx (dxx) B) = (B). for B E B(x). Define the z-weighted inner product (f.)) = fx (dx))
Let (²) = {f [[f]ll=(=) < oc} denote the corresponding Hilbert space of IR -alued, square- integrable and measurable functions on X. For an operator T: (m) - T,2 (,r).. its operator norm is defined as [[T]le (-)) |[T The transition kernel is bounded linear operator
and the induced norm [l = ((f. (PF.))
on (T). particular with norm || [P]])= Also, we define the kemnelooperator (1
by
Throughout the paper, we assume that is Borel space. Let P denote the transition kernel. We call i the stationary distribution of P if it satisfies fx π P(r, B) = x (B), for B E B(X). There exists kernel P regular conditional probability that satisfies SA π (ds) B) Tddy) A), for A, B ((x) [27, Chapter 21.4, Theorem 19], and pa defines the probability law for the time-reversed chain of (2x))20.
B Additional Discussion on Assumptions
In this section, we provide a more detailed discussion of the assumptions taken in this work.
Projection and Minorization Projection steps have longstanding presence in SA literature for tractability in convergence theory, seen in many analyses of SGD [6, 11, 39, 41, 54]. Although not an algorithmic proposal, this additional projection step does not incur much computational cost in practice, it only involves rescaling the iterates, and the projection radius can be estimated priori. Before our work, no studies had proven weak convergence for non-linear SA with Markovian data and constant stepsize, with or without the projection. Thus, result is the first to prove detailed weak convergence in this setting. Nonetheless, we provide an alternative proof of weak convergence in Theorem 4.3 using the Drift and Minorization technique, which does not require projection.
Differentiability The differentiability condition of the SA update operator g in Assumption ensures controlled evolution of the iterates 0. This differentiabilityy assumption supports third-order Taylor expansion of g with a bounded remainder, which is crucial for both analyzing the A term in the convergence proof as discussed in Section 3 and for bias characterization. Moreover, some form of differentiability assumption is standard in SA literature, such as [1, 20, 45], particularly when one seeks fine-grad ane-grained characterization of the iterates' distributional property. Such an assumption is satisfied by many GLMs, such as logistic regression and Poisson regression. When is not differentiable, the bias of SA iterates behaves drastically different [68], which is beyond the scope of this paper.
Strong Monotonicity The strong monotonicity assumption common in SA literature. Together with smoothness, it allows us to establish geometric distributional convergence. While some GLMs by themselves do not satisfy this condition, (equivalently, weight decay) to ensure strong convexity and improve statistical performance. It is standard calculation that one can appropriately choose the regularization parameter to derive tight results for non-strongly-conver functions.
a common practice to apply Iggregllarizztion
16

---

C Additional Plots
In this section, we present the plots from numerical experiments in Section that verify the Central Limit Theorem (CLT) in Corollary 4.5. In these plots, we plot the centered and scaled PR-averaged
iterates, i.e, vT 0 - 0.)) ) where @(k) (Ei=10 01) /T with T 100 is the PR-averaged iterates for the 1c-th repeat.
40
Thevetical Quaniile
(a) Histogram of Centered and Scaled PR-Averaged Iterates with Fitted Normal Density. This histogram displays the distribution the PR-averaged iterates from the experiment. Overlaid on the histogram is a fitted normal density curve. The close alignment in- dicates that the empirical distribution of the iterates closely follows the normal distribution.
(b) QQ Plot of Centered and Sealed PR-Averaged Iterates. This QQ plot compares the empirical dis- tribution of PR-averaged iterates from the Lz- regularized logistic regression experiment with the theoretical normal distribution. The linearity of the points along the 45-degree reference line indicates that the empirical distribution closely follows the normal distribution.
Figure 2: Experiment results to verify the Central Limit Theorem.
D Proof of Pilot Results (Proposition 4.2)
In this section, we prove the pilot result, namely Proposition 4.2. We prove the desired moments for = oc, i.e. without any projection. is easy to see that when the projection radius 3 E [2][0*]) [|. oo),
B| 0" 20) s [B[100+1/22 - (*'))))
where 0/41/2 denotes the iterate before projection. The term on the right hand side can be further bounded by the moment bounds for iteration without projection. Therefore, it suffices for us to prove the respective moment bounds without any projection.
Given Assumption 4 hold for 2p-th moment, with p 1, we prove the moment bound in Proposi- tion 4.2 for n with 1 < n S by induction.
D.1 Base Case
In this section, we prove the base case of Proposition 4.2, i.e., with 1. The base case gives the desired mean squared error (MSE) convergence bound, which will subsequently be used in the proof of weak convergence.
We start by noting the following decomposition,
18[10++1 0t [13] || - (1]
(fx 0" (( 2x = (
20 0r, ((,, xx) g + (0 000(((=))
+ + xx )11 + [01])
It is easy to see that under Assumption 3. we have
(0x 00 .()))))) (0x 0-, g(0x) }(0")) <uull0 00112.
(D.I)
17

---

Additionally, under Assumption 2 and 4, we have the following upper bound
a² (B(lllo(0 Tn + BU|GA+ (0+))
- a² (13E((10: 0*1 + 1)91 12 - -0"11 + 1)91+
$ 22 (1] 0- 11)
(D.2)
Therefore, the key to analyze the remaining inner product (0x- 0r, g((,,, ((x)))
Consider the following decomposition
(8x- 00000""00000 g((6%,, xx) g(0x)) (0x 0 - r. g0k: 02m) g(t)))
(D.3)
+ (0x- 0" g (kk r, 22) g (8
(D.4)
(Ok- - 0º ((k,, Tx) g(0 0- Ikk)
(D.5)
(0k- 0", ((0)) - g(0k=r)
(D.6)
Hence, need some upper bound on ||0g 0x-r
We next note the following technical Lemma, which is adapted from [17, 60] for the updated unbounded i.i.d. noise assumption in Assumption 4. The proof of the technical Lemma is delayed to Appendix D.1.1.
Lemma D.1. For 16ar (AL3))), have
[| - 0z~ F S 2aT L|10 0-l + 20T
(D.7)
[[ 02 || S 4or [.R F* + 40. I,
(D.8)
0| 02-7 |1 s 7 2100 0-112 72
(D.9)
01 O 11 S 32a 2,
3202 3
(D.10)
Given (D.10), we additionally note that
- -
+ = B|| [[]10==+ F-|1
< 2 B[l10 0% 16-111 + Elll0 0 1- +1
< 2 <2(32 2 02 0" +1) E11 0" 001 [R +1
S (TE 0r [ 1).
(D.11)
We next use the above four technical inequalities analyze the four terms in (D.3)-(D.4).
To bound (D.3), we first note that
(0, 0x-r. g(kk, xx) g(0x)) FR
[ - 8x-7 21 1b - 8*1l + Fx]
1A8
2L 0x - - 1 F B[([10 - 1+ [
2L 22L 33
0 1
< 1. - 1
where (i) holds for the Cauchy- Schwwrzz inequality and (ii) holds for (D.10).
To bound (D.4), we next note that
E (0x-r 8", ( xx) -00
(1 H¹ Elg(Ok- (..0 24)
g(A -- F
< 110=T 0*1 ig( (K- 24. - g( F
|| - 801l [aI([| 00 + +)
< 2aL 20 0- +1)
18

---

8aL(EI 8 F SuT LL (B - [k + 1),
where (ii) holds due to the mixing property of Markov chain (zx)x20 and (iv) holds for (D.11).
To bound (D.5), we have
[0 0" g0k: xb) - g(0k Fx))
10ck- - 0r, Blg (0( rx) -00 k-r -, Tk Fb
L||Ok- 0-11 ElllO 14--111=k--
1| 0- 200 [([l OK~ - 0- + 1)
K 4aT ( (1 - 1-1 + 1)
16ar 1 (E[[)) - 0- F +1,
where (v) holds for (D.7) and (vi) holds for (D.11).
Lastly, to bound (D.6), we apply the similar technique used in bounding the third term in (D.5) and obtain a similar result
|B|00--- 0", (00s) g(0. ((0k-r)) [(0===)) 16ar (E[] 0' 1).
Combining all analyses above, we have
[2 (Oz= - 0²), g(k, rxk) - g(0x))
< 2a(116a + 8aT L2 + 32aT L (1E10 - 1P1F
$ 11 0" 1R 1).
(D.12)
Hence, making use of (D.1), (D.2), and (D.12), obtain the following
[|[10++1 - 0" 11 - R[| 0
s -- - 01 112a 1 (E[l - 8 011[ +1)
+ 2n² (F - -01])
S +1
- 1- 1 + 1
(, 0- 1 + 11.2
Therefore, when we have a satisfying the constraint, i.e, LT < C2.1/4, we obtain
B[102+1 - 0 0-1 (1 - a1) 8*112]Fa_r]] 1140
Recursively, we get
0[ 001335 (1- ( 0 0011 11
/
11
< 2(1 ap))
[BII10 1-] + E1 -6619))
/
Elll0, -8-19]+ + 1) + 11
< 2(1 ap) k-
[B||60 0- || + -a²
4
E 1- + 122aTL2
< 4(1 ap)
Lastly, we note that
(ii)
2 2,
(D.13)
atи
1 arL
where (i) holds by the Bernoulli inequality, that (1 + x) 2 rz for x 2 -1 and 2 1; (ii) holds
for μ S. L: (ii) holds for aTL < p/((14L) < 1
19

---

Hence, for h 2 T, we have
L
0 0013] c2, - app)*100 0¹1 + 2
/
for C2 and 2g22 some universal constants. As such, we have completed the proof of base case for Proposition 4.2.
D.1.1 Proof of Lemma D.1
In this section, we provide the proofs of the four technical inequalities in Lemma D.I.
Proof of (D.7).
El - 0z-rlllFk-p S 20t 2aTL/ 0* + 204
Proof. Note that
k-1
10x 0k-
Σ
10041- - 9cll.
t=k-
so we start with analyzing |10c+1 0:|l-
||0++1
0*1 - 10: 0* S | 0z|l = a a0lll9(0...)))) x2) 1
S a [ (f,, x:4) )l ( (0:) S a (100 -1
+ 1) allle++(00))
10 0 < (1 + aZ4) 01 0-
-
a/ + (0)))+
Recall that we assume
E 1/11 < L2(11011 + 1).
then we have for - k:
1 (Om)] - [1 E
E| (100 + Fx-ll
0 - 0ell [x-r| S 1|
-
B|||0=11 FR-r| < (1 + Ba) - 0 11 aL.
Hence, for E n T.
n-1
E 1 l* [| S (1+ -1 11 + aL Σ (1 + aL)
=11+ab)110+--- 0*l + ((1 + +aL)" 1).
We next note that
(1 + x = llg((1+2) S -v < 1 + 2xy, xy E [0.1/2].
Hence, at this stage, if we require ar < (4L) < 1/4, we have the following upper bound Therefore, for 0 <n T.
(1 (1+ (1 aL)
2 22
E E - [ < (1 + 2n L)] 8*1l || + 2aT L.
2 -- 00 + L.
As such, we have
E 0 0g-r||
Bill0++1 8, Fx
tm T-
h-1
< aL Σ
B[l[0 0" 1|[Fx= + ar
1=
< at L( - 0-1 + 22 + atL
2or [. 0 + 22T L,
and prove the desired inequality.
20

---

Proof of (D.8).
B| - 08--1l-Fk-2 S 4arLE f F + 40. L.
Proof. We prove this inequality based on the claim that have just shown,
0 0 [|] 2aTL 0'1 + 20r L.
We simply note that
110
0-1 = |B[ k- Fk
< 0 - 0 11 F B1|0 - FR
Hence,
E| - - _ 2a 2a [ 8x- [R + Bi10, 0" F[++++++]++ +1)
(1 2ar L 1) - [k- & 2a LaTLE - Fk + 2
Therefore, we obtain
B||10, (ll=1l1Fam-1 4aTLEII10; F*11F 4arL.
Proof of (D.9).
E| 0 FR 32 0- + 32a2+212.
Proof. To analyze B[|[A]-
0z 0 we consider the following attempt.
11 S
B[10++1 [x
= Q²T
Σ
(C]lo(0,,==)]1 + (B)11) 1(11:10-.2)
k
S TT
Σ
+
t=k-
< TL2
B[([|0: - -0 + 1)
< 4a 2 TL2
El[l; - + 22?
-=
Next, we study - 10100-0'113120 0+112 We start with the following, for h: - S 6 <
0 8- Fx
= [|[[ - 0" 1 [ + 20 - .-, z.)) a xz) + (0.)
< [ - 0r 13 + 2a² | (1
E[ 8' (1lg 2z) 1
We note that
21 0"
< 2 =
< 2 2V
0-| + 1))
2 2 - 0-11111--11221000000-- -0-11 F(
21

---

- - + 1).
Substituting the above inequality back, we obtain
B|]10+11 - Fi
< B|[|0: 0- 1 2 01 + 4aLBII10, 0'1 4aL
Σ 2.2 [ 0 1/
+ (4a2 4aL))
We further recall that
4 I 4aL(aTL) aL,
and hence we obtain the following upper bound
B[110+11 [- s 5aZ)E(110 0-11215a-r] 50
Then, recursively, for 0 S we have
R-1
-0 (1 10+ 1-11 + 5 Σ + 5a
As such, under the assumption that 4 < p/(4)) < 1/4, then for 1s S k; we have
B[|10, 0 [1 (1 10a7 |)_ 0-11² + 10a7
$ 2| 1 -10TLL
Combining all the analyses above, have
R-
O O 11 5 4a LL2
- +
2
t=
< 4a 2 22 - 0-1 1| 100TLL
+ 2
<
1- 802
Proof of (D.10).
0 04-r11 2 - +
32a2+212.
Proof. This inequality simply extends the result from (D.9).i.e.,
0 0
12 < 8a 0011 802
We first note that
1|0- -B]100-
$ 2 0---111 F 2E [
Hence,
E[[[ Oz 01-r112|FF
- 02
- 10
(1 (1-16a² 2 2 O 3| < 2 L3 8" 11 8a 222
Again, under the assumption that 16aT 2 < 144, we can conclude that
E| 02-r11 [[ < 32a Blll02 0 324 32a
22

---

D.2
Induction Step
In this step, assume that the moment bound in Proposition 4.2 has been proven for k S we now proceed to show that the desired moment convergence holds for with 2 < S p.
We start with the following decomposition of |0 1
| 1
(10+
-01 2a<00 0", (9(0,, + (0x)) + a (19(0k, + (0+1()))))))
(. 10s- -011 (2c((n 00013 0", 0000(00,0000)00000000000000001,, mn) (o<))) (al))) + Ex+ (Ox)]l
n
f. ++++==
We note the following cases.
== =l= In this case, the summand is simply ||0g 1|
2. When i = 1, and 0. In this case, the summand is of order i.c., a2n 0" g00;; mR) + E (n) )} 1 0 1|2(n-1)) We can further compose it as
(na - 00, g(0 mR.) + (0x)) - 1 ((m)2(1-1)
2na 0² g(00, g(0x)) + Ec+1 (0x)) 0 (1(())11)
+ 2na 0- g(xx)))))))))))))))( 10 0- 10 (a)
T2
Note that, when (Ir) is i.i.d. or from martingale noise sequence, we have
B = 0.
However, when (zx) Markovian, the above equality then does not hold and Ti requires a careful analysis. Nonetheless, under the strong monotonicity assumption, we have
To -naup 0x 12
3. For the remaining terms, we see that they are of higher orders of a. Therefore, when is selected sufficiently small, these terms do not raise concern.
Therefore, to prove the desired moment bound, we spend the remaining section analyzing Ti- Immediately, we note that
E [ 2na - 0", 0000000; xk) -g(x))
0-112(m-111
= 2na 0", g(0x g(0x)) 1r (m( Fx
Ti
Subsequently, we focus on analyzing TV.
We start with the following decomposition of TV.
[ga x4) g(0k), 0x 00)1 - |0| 2
2 2na|lg(00=-1, vk) g(0 10_- 0- 2
(D.14)
2na [na]]g(02, g(0 xx)1
0 2
(D.15)
+ 2na (na((](0kkr) - g(0x) | ||| 0 - 8" 1- 12m-1
(D.16)
+ 2nailgg(Ox, mx) g(Ax)) I| ||0 00 11
(1 0102 - 0/
(D.17)
12nallg(O,,, xx) g(Ox)) ||0--- 0'1| (110s 0 1 110 0 (2)
(D.18)
We note the following technical lemma, which will offer significant help in the analysis of Tİ. We postpone the proof of the lemma to the end of this subsection.
23

---

Lemma D.2. For Cn S (/L22) where en denotes some constant dependent the migent- 2n, we have
B[100 06--112 ,
2m 1,2h (1000===== 1- + 1).
Following the lemma, we observe that natural consequence is for any m 2n, we have
El| 0k_ [[ - [B1 - 0 (Fx=r)) 2n
$ (n 2m 20 I 2 (10x- 1-11 2m + +)) 2
S am 7 m (100--+ - 0- 10 + +1)
where we use the inequality a" 6 > (a + b)l for a, b > 0. p E (0, 1) to obtain the final incquality.
Now, we are ready to analyze (D.14)-(D118). Firstly, for (D.14), we make use of the mixing assumption of T, and have that
E|[(D.14)| 2na [oal0kx-+ 1- E 2x)
2na² 1|0k=r 0" || 22- (11 h- 0- || + 1)
S 2na 2 1/0=- 0" 2m + 2na 2 L| - 0* 1
S 3na 2 Ok- - 0" 11th + nox L||0k= 0 00122(=-1)
where we make use of the inequality 2/x/| - x² + x² to obtain the final step.
Next, we proceed to analyze (D.15). It is easy to see that [[[D.15)|
2nall6x-> 8* 1- ' E (0x, 0b) -
2nal 0- 11- | 0 - |6- Fk
S 2nal 1-1220-1 (2 L( 00 -- 0- + 1)
S 4 - -1|100=== - 1|2n + 4na? 2 -.| - 0-1 2m
$ 6 1 - 11 + 2na² 2 T 0- 1(112(1-1)
The term in (D.16) can be analyzed in similar fashion the (D.15). For (D.17), we first derive the following
[[((D.1))(F=-
< 2naE 2L [10p- -0 +))1100 - -0= 11102- - 0-1 1-1 F
|1100k Ok--rl 0 11 1 [[ + 4. 02
Ox
0l--11
F
T.
Tb
We next analyze the two terms To and T. respectively. Starting with Ta. we have 4no [E( 0x-111100 8r 11122-111
(D.19)
< 4naLIE |10 0x-rll |10p 0k-rll 11 + 110 -01) 2n-1
[Fa-r]
(D.20)
< 22 22(n-11) (nne-))naaT.B( 0z 1(100 - 0z_ 112 + 110k- 8r 1| [F
(D.21)
naL
[|[|Ox - 0x- 2m [F +1| +110k= - 00111 00||2n-BB|100 B1110
0p- F FR-r]
(D.22)
by Lemma D.2
4" no.. C, 2n, 1, 2 (10p- 0-112n + 1) + 110,- 0+ 1|2--11 (2arT 1=(00= 60 +))+
$2arL
(D.23)
< La 4l0x 8-122m + 207TI10k--88 1 + c, 22 1
(D.24)
S 4" naLL 50eT (50TL1100 - -0-12" + ar aT (m1))(n-1) + c, 2 - - 20 22m-1)
(D.25)
24

---

For To, we have
AnaLEillk 0x-11110x 011)2(011)1 k-
< <naLLE 110 Ok-r (10x= - 0x- + 1100-- 001) 2(n-1)
F
<22n-1 1no - 0k-1 0g - OK -1 + 110 - 0- p1122(n-1) F
/|(mm-1)
22m--nnal
Ell10s - 02- 22 11 F +110k=7 - 011)((n11)((11 - 0x- F
by Lemma D.2
S 222 nall Cn-10 20 2n-11 222-11 (110= - 1)
S2arL
+ +100-- 0- 0-112in-1(2aTTLL/
0-1 + 1))
I -22n-Inall naL 4a 40T 1 -0 + 20 6a 01112(111) 2n 12
< n (2aTL]10s= 1-122m 4at L| 0-112(1-1) Cn- a 2 1
Combining the analyses of the two terms, we get the following upper bound to (D.17)
E| (((().1))
naL 5at La0 0-1120 aT LT 0'112(m-1)_ cg 2n 221-1
+ 22 naL 2aTL|0kk= 0-l 1|m + 4aT 8" 10112(0-1) + cn-1a 2n 1--1,22 -22-1 2
22m naT. (120T 0* 12m + 6a7 L1 0 12)12(1-1) + 1 2 2 1, 221-1)
Lastly, we analyze (D.18). We first make use of the mean-value theorem, with E 10, 1]. we have
10 0-l 2-=1 1) |0 0 (())))11))
|00g 0 || 2(n 1)] 0²) + (1 a)) - )2n-3
|00 02 - || 2((n 1) -k--)) Ok- 00 1-122--3
< 2 (n- 1) - Ou- /1 (10s- O2- 2 + 1m-22-33
Substituting the above upper bound back into (D.18), we obtain B[)
< 22 In(n 1)aL[10==> 18
E (110k- - 8*11 + +1)1 - 0kk--ll 0 -0x-- 12m-1 2m + -10
8- (p)2m-33) 15
< 220-1 nn - 1)aL
(10k~ 111 08- || - F + 110 8- 12 - 0x_r| 1| 2n F
+ 110 - 08||L111000000 02 0p- 2| [ + |10 -
02 O2 - 11? F
+ 1102-r - 8 2 E[| 02 0 ||| [ + |10 - 1m 22 21 0 02 - [k
< 222n-1 n(n l)aL CLTTTI100-- - 8r 101 + Cn- L 8" 1-)12(n-2 2m + Cn 1- 2n 2n- 1
Combining the analyses above, have the following bound for Tı.
||
E |10
+ + 2 1122 - 0-1| 1(112(0-1) + cn,3a 2 1,20
S
25

---

where Cn,1, Cr and CN,3 are some constants that depend on n.
Additionally, we note that
| 0 112m B|ll0-- - 0* 10 |
[10g - 8 8x-- + 110x - -8 2n [r
2dt 2Bll0 0x 11- 1 22n 1 0 1F
c, , I, 2n (10 12112n + +1) + 2 1 001 ~2m [
Therefore, for sufficiently small at L < u/ L), we have
(1 a 2n 122m ||0k- 8" 11 S 11 8" 1: F + a 2m 2 I 1,2n
2m L 2m 10x 1'1 < Bl1l0 - 0-1 [ + 2c, a 7
As such, for sufficiently small a, have Bl[Ti|| [RRr)]
S 2 Cc. 0-112m Fi-r] am 22 2 [
+ 2n,20 2
Cn-1 02 0- 2 FR- + cn aa 1(2 ((n-1)) + 1 2
= 10 2 TL 0- F + 20 2 L22 - 0-112(n-1) + Cn Gn 2n 20 , 1,20.
Hence, up til this point, we have obtained
[[] 11 Fk
$ (1- 20-2maa)) ||10; - 0" 11 [
+ " - 11 [ + 2 LL 0 101 Fx- + Gn,3a 2n 2n 10,22211p 2
(1 2nar( (. 0- Fk-z)
+ T - 0-
+ Cn, 3a 2n 2n 2n
Following the induction hypothesis, when & is sufficiently large, we have
E| 0"
S ea-1a"=1p s(0o, H.).
Substituting the above upper bound back into analysis of the 2n-th moment bound, we obtain
01 8 1 S (1 - 2na( LT) -0-0--0000000 12122
+ a a+ 1 122c,. Ca cn I 1, + Cn,30 2", 20- 1,2m.
Subsequently, if we set a sufficiently small, such that LTL² < Cn 1,
obtain
E|ll0++1 0-1 0-1121 & (1 ap) 0r [a + ant1,"dh2 s(0o, L, H),
where s(0,, L, μ1) is some constant that may depend on the initialization dn and the problem primitives μ and L but independent a.
Recursively, we get
ElllA - 11 < (1 -ap) k- - 2" + a a² s(Oo. L. 14).
Lastly, we recall that
B1|00, - 0* 1*
22n E|10, 0 || 2n1 2 22m 1m
< Gr,1 a 2m 2m (E 0. - 11 1) + 2 - 12
G. G,, B1 0r 2 + 2 2n 20 2m
Substituting back, obtain for sufficiently large k; [1 0 ||am] < (1 a - 0 2m] 20 L. H).
As such, we have proven the desired n-th moment bound.
26

---

D.2.1 Proof of Lemma D.2
We now come back to Lemma D.2 and provide the complete proof.
Proof.
The proof follows similar strategy as (D.9) and (D.10) in Section D.I.I.
We start with the following relaxation and obtain that
1 0 0x-r 10 Fx $ 110+1- 8c1l) 2n [Fa-T] -bel)
< <
11 [
2n 2n-1
(4) + (0+)( Fk-=]
l=k-
< 22 a
22 2n-1
(1ll:(00. (1)) (
< 222-1
a 2 2n-1
[]"B[(110: 0- 1)) 1 (B8[1 0 0-]] 1)2m)
< 2 2n 2m
Bl[10, 0-112-11= [x + 2 20 2m 2n 2,
Next, order to obtain a bound on |10, - 0-112n, we study the following term.
B 0[+1 - 0-1120 [T F EE (110 Bell + 11: - 001) 2n
[R
2n
2n
B1|l
00-1 - 0. 11 - 0+ 2m 1
i
1=0
2n
El|10, - 0-112m [ + Σ
a (EElll(O,, + Ex+ Ee+1 0-112--0100
Note that
(ll,g(0,, xx) + Ee+1 (0.) - 0" 2m
2 E (10(0t.. x;)II' + (0.01(0001)))))) 110 1
= - E
(((l9((2, 21' + ||
< L'E (11e, 00 + 1)²a F
< 22 22 [E]10=
0" 11F + +1
Substituting back, we obtain
> ((llg0(, + E.+) -1
2n
< 22(nn1))
a I [[ 8 8+11FF=71++1
i=1
22 (00-11)(B (E|l10, 0" 111 20L(1 + 22 2n
27

---

S 14m--aa aL [11|0 8" [|| + +1)
Consolidating the terms, have
01110++1 0 F ( aa)) [0110 (E110, 0 0-11F +1)
Recursively, for 0 S T, we have
E||| 6 0 -110 (1+ 11) 44 aL
(1 + 42m aL)
1=0
(1 aaL -0 + + 12n-1al)
Then, for
22 aTL S 1//4 < 1/4 1
we have for k Sts k.
0 10112n 2M F
(1 + 20n 2---21n1 aT
1-112n n 24n 24n-laTL aTL
k| 0" 2 + 2 aT
Finally, we have
E| O2- [R < (2n-1 0x , 2n 2n
B[[10, 0-112m [F + 22n-1a= 2n 2
(=
2 az 20 2m
2210 - 20112n + 22
s 2n 20
11:2-- 0-1 +
As such, we have completed the proof.
E Proof of Theorem 4.1
In this section, we prove the weak convergence result in Theorem 4.1. In fact, the proof of the projected SA weak convergence result can be seen as special case of unprojected SA with the asymptotic linearity condition, which we have briefly discussed in Section 4. Therefore, the proof proceeds the following two subsections. First, we formally define the asymptotic linearity condition and present our weak convergence result for unprojected SA under this additional assumption. Next, we relate this result for unprojected SA to projected SA and specialize the proof to obtain Theorem 4.1.
F.1 Asymptotic Linearity
In this subsection, we formally introduce the asymptotic linearity condition. which is crucial for establishing weak convergence in the context of unprojected SA (5 20). Additionally, we explore the implications of this condition.
Assumption (Asymptotic Linearity). The noise sequence (Ek)az1 is a collection of i.i.d. random fields satisfying the following conditions: (1) [E[E++ FR) 0, (2) there exists constant La such that & is Li-Lipschitz, i.e.. (0) - (0)) La 0 0 0' for all 0,0' E Rdd and (3)
(0)]( < Lz.
Moreover, there exists a function G(-) X' - R ddd such that given >> define
ò(e) min {ō: 11g' (0, x) G(=))| < Vx x and v0 (0: ||l|| 2 8)}.
and we have lim,-o cδ(e)
The first part of Assumption 6 states that the random field grows at most linearly in 0. The second part of Assumption 6 implies that g' (0, x)) converges to a limit G(x) when ||0]| - oc for all E X, which shows the asymptotic linearity of g(0, 2). Furthermore, Assumption 6 also requires how fast
28

---

g'(0, x) converges to G(z). A sufficient condition under which the second part of Assumption 6 holds that there exists w > 0 such that ||0]| (0, - G(x)ll < co for v0 e IR and æ E X' We can verify that to ensure lg/ (6, x) G(=)ll < e, we can set ||0| E ((c-IT=) which can ensure cō(c) E O(e+==) - 0 O. This sufficient condition implies that g' (0, uniformly converge G(z) with convergence rate of 0(110 )=) By definition, we conclude that the structure of linear SA is also asymptotic linear. Besides that, the 1-dimensional logistic regression also satisfies
Assumption 6, For I-dimensional logistic regression, we have g(0, x. 3) = (Ite-t - 1) XO,
where (x,y) y) presents the data. Therefore, have 20, y) (I+e-1r)z À and g((0, 20, v) uniformly converges to À with geometric convergence rate, thereby satisfies the Assumption 6.
23c-00
E.2 Proof Under Assumption 6
With the asymptotic linearity condition now formally defined, we proceed to prove the weak conver- gence for unprojected SA. For convenient reference, we state the theorem below.
Theorem E.1 (Ergodicity of SA Asymptotic Linearity). Suppose that Assumption I-Assumption 4 hold. Additionally, assume 6. For stepsize a > 0 that satisfies the constraint aT, < min (e2t, Kp). with 02 formalized in Proposition 4.2 and Ky. defined in (E.1), the Markov chain (Ik 0l k22 converges unique stationary distribution Va P2(x x R..).
Moreover, there exist Ky > and some universal constant d' such that
c8(c) S dn,, Ye S Kkp
(E.1)
We Va = _(0.o) be the second marginal of Voo For k 2 2Tc it holds that
(2(C(Oa): - W2( 0x), D.) S (1 - a/) s(0o, L, 11).
(E.2)
The proof of Theorem E.1 consists of two major steps. Firstly, assume that ze n, and show that (Ite, 22) converges to a unique limiting invariant distribution. Next, we relax the assumption of To r æ, and prove that for arbitrary initialization (zo. 0o) E X' Rd, the Markov chain will converge to the same limit.
Step Initialization with xgg ~ w. To prove the convergence of the Markov chain, we consider the following coupling construction. We have pair of Markov chains (æx, 0001 )e20 and (IR, 0 )x20 sharing the same underlying process and noise, i.e., (I Ek+1) i.e.
0 05' + a(g(o!", xK) Ex+1 (0 (o!1)).
(E.3)
0 1+1 ofa + a(s(0 mx) ) Ex+ (0 ).
We assume that the initial iterates of' and 0!² may depend on each other and on vp. but are
independent of subsequent (Ix) given no. For the iterates difference of!! db2 we have the following Proposition E.2, whose proof is given at the end of this subsection.
Proposition E.2. Vk 2 r and at S min( P
SUSL , 44), we have
'2] E||le] - 0% 19 4(1 pa)* E[|0!! 0/-² 112.
where Ky 0 and cō(e) < His Ve S Kip-
By Proposition E.2 and the definition of W₂ and W3, have
w3 (c(O 2(0()))
W2 [( 004 ) [( ( 0
(i)
(F.4)
4(1 n -
"!.2 0,22 113]
where (i) and (ii) hold by the definition of W2 and W2 and (iii) holds by applying Proposition E.2.
29

---

Note that equation (E.4) always holds for any joint distribution of initial iterates (2o. 00 00²)). Recall
that P represents the transition kernel for the time-reversed Markov chain of { 1220 and the initial distribution of zo is assumed to be mixed already. Given a specific 20. we sample 2-1 from
(* zo). Additionally, we use e to denote the random varible that satisfies 00 _ 8! and is independent of {rx Finally, we set 08 as
00 0 ala(x-1, 0 Eo(0
By the property of time-reversed Markov chain, we have far h=211 $ fash220- Given that
a| d 8f" and el3 is independent with { we can prove (x of - (zu+1, 00 k 1 O. We thus have for all T:
0 for
W2 (c [xx 0/.)) L 1 (00-1, o(tt)) = W3 (c Ik 0%²)) L 2k o(²))
- 4(1 f BBlll0! 0, 172,
where (i) holds by inequality (E.4). Then, we have
W3 (c (kk 0 L (1x42,
t0
W2 (c ok, 0/4") 2 (1xt1, + 4E1110" - - 2 na)*
0=
k=0
<00.
Consequently, {I(,,, 0%²1 1220 forms Cauchy sequence w.I.. the metric W2. Since the space P2(X' x IEd) endowed with W2 is a Polish space, every Cauchy sequence converges [63, Theorem 6.18]. Furthermore, convergence in Wasserstein 2-distance also implies weak convergence [63, Theorem 6.9]. Therefore, we conclude that the sequence (C(I,, 0( ))220 converges weakly to limit distribution á E P2 Rd).
Now that we have established the existence of a limiting distribution, we next proceed show the uniqueness. We prove this by contradiction. Note that we currently assume that πτ, hence to show that the limit (I 0x ) unique, we only need to show that the limit is independent of the initial distribution of fo. which can be correlated to Zo.
Consider two Markov chains (IRK 0k)220 and (rr,0% K2)2,. sharing (Ii (x+1))))))))) ()21))20 but with arbitrary initialization of Og and l. For the sake of contradiction, we assume that (ro, 6o) = (Toe, Ooc) and (zo, 0%) (Ioo, 0'x) respectively. Then, by the triangle inequality, we have that
W2 (Io.s 0xc) (Ioc, (2x)) 02m)
< W3 (Io0, Ooo) (KK, (2x,, - Wz (1z,, (2x, 0%)) + W. ((TAA 0%),, (2oc, 02m))
0.
As such, we have shown that the limit ø is unique.
Lastly, we prove that invariant. Suppose that we initialize the joint process its limit, i.e.. (xo, 0b) ~ D. We first apply the triangle inequality, and we obtain
We (m1, 11), (xo, (w): Bu)) s Wz (x1,61) 01). (#4411, 0x+1)) + ( (zo, Bu))
Clearly, as ls + co, W/ (I*+1, 0x+1), (zo, 0o)) 0. To bound We (z), 0z), (II+1. 0k+1)) we need the following lemma.
Lemma E.3. Consider two copies of the SA trajectory, where C(x0,00) = and L(x 0g) is allowed to be arbitrary.
(()),)))) W2 [(x1, 01), L(a,, 01)) S P1 W3 ((ro, Oo), C(2b 6/)) + P2 W3 (((( Oo), L(z6, 8)).
30

---

where
P1: + 2(1 + aT.)² + 16a2 <0 and P2 = 16a I
B[1[0]14]] < 00
are independent of C( 0)).
Proof. Consider the following coupling between the two processes (#x: 00)x20 and (1 8220
W2 [( 0o), (l/o 8%) E (xu, m/)) + |10b 6113
and
0k+1
1 or
Ak 0.
Then, it is clear that
W3 [(x2, (1) & E du((,,, + 110 - 113
Recall the metric = (2r # n and hence, we have
0(0g - g(0, x/)) + do (0)(0 g(00. z()))
Therefore, it is easy to that
01 - 0j = 0o - 0 + (0 mn) - g(0 -11)) + (0) (16))
= 0o 6 + 000 mo) F g(0n. 1/1) 3(0, =()) + a(E1 (0o) (i())
= Go 6 + alg(O, =n) - g(%, x))) + (0)) - ((6))
+ ado (g) g(0n, z6)),
whence
110 0'1l - aT.) Ø11 odo( vo) g(0,, =b)'l
$ + a
81 ado(2 20) 2L([] + 1).
As such, we see that
B(do(x1,21) + |10, 0/112] S R[do ro: m6)] + 2(1 + aT) B1100, 611
+ 16a L Eldo(=), (1060] +1)].
Next, make of Cauchy-Sehwarz inequallit and obtain
Eido(=), mo) |10.|13 < /Bldo(a's mo)) Rag-n [110o114]
Because Assumption 6 implies Assumption 4(p 2), by Proposition 4.2 and Fatou's lemma, have
Bl (1*1"]] < lim inf El| 0₂ 0 11 co, k
which implies [1 < co. Hence, the desired inequality follows through.
By Lemma E.3, we can set Laah, 0%) C(rk. 0x), then
W3 (L 01). C(xx+1, 1)) S P1 W2 (ū, Lla,, 0x)) + P2V W3 (D. C(x,, 0k)).
Therefore, W3 (mi, 01) C(xx+1, 0c)1)) - 0 as k - 0, which implies W; (z), 01), (xo, 0n)
0. As such, we have proved the joint sequence (.x 02 k= converges weakly to the unique invariant distribution & E P2 x IR.). As result, (#, h22 converges weakly to E (RR)), where is the second marginal ş over Id.
Lastly, before proceeding to the next step, in which we remove the assumption Zp we first derive the convergence rate of (0x}az) under Zo ~ и as presented in the following lemma. This lemma will help us to establish the convergence rate without 2g
31

---

Lemma E.4. Under 20 ~ Assumption 1-4 and 6 and the same setting as Proposition E.2,
W3 (C((s)) < W (C(wE, 0z), Po) S 16(1 - waa* (EE [100] 0-]]]] + <2.2)
Proof. Let us consider the coupled processes defined as equation (E.3). Suppose that the initial
iterate (ro, of²) follows the stationary distribution v, thus [(xx, 0g² and (( for all k 2 O. By equation (E.4), we have for all k 2 T
w2 (c(O ). = W (c(el"), )(
(((e))
- W (((r,s ob2)), L(rkk 0%21)
< 4(1 - pa)*==B1100 08/-13 [|]]
(E.5)
x 8(1 - wa)* kー (E [105" 00
+ [110 - 0-117)
< 16(1 - wa)** tM
(E |10| - 0-1(3)
+ E |1000 - 0- IPT)
where we make use of the derivation in (D.13) to obtain the last inequality. We note that
E E1 - 0-11²] < lim inf k-500
B[|0; - 0 112] S 22 aTL2/H S 62.2
the last incquality holds for min( 90872 7)). Therefore, we prove the desired inequality
W2 (c(el")..)) I 16(1 pa)* [ [10]" 0112] + t222)
Step 2: Arbitrary Initialization for (zo, 0o)- In this step, remove the assumption of zo
needed in the previous step. We need the following lemma to prove our result.
Lemma E.5. Consider two trajectories (Ik, 0z)220 and (a's, 8% k2) Suppose that 9, = 8/ x IT and no is initialized from some arbitrary distribution that satisfies [[(z)) - π k||TV = e. Then for k T, we have
W2(C(an, On), (lr,,, 0R) < 5 (402
'pll0 0-] 20,
2
+1) 1/2
/
Proof. We consider the following coupling between two joint processes (Ix, Ox )22 and (x'e, 8%) k2) We first apply the maximal coupling xu and an such that
Pr(oo # 26) = [| - ((16)llv= =c
For the case To = zh, we can couple the two Markov chains fau and fak such that
Ik t vk 2 O.
Under this coupling, we have 0g = l% Vk 2 O.
For the case un A x/g, we let the two processes (I2, On 0z) and (1/ 02)621 evolve independently. Given the above coupling, we first observe that
W2(C(T, 0x), C(rh, 0%)) = (CW 0c), C(rk, , 0% ()) p = =f = x/6)
+ E 0k), L(r (%)) 1000 # 2'6 P(ro # x'6)
= <E(We(C(FR, 0k), C(rr/ 2 0% [F # 2'1-
The second equality holds since E[W2(C(xxx 0x), [(xx, 8()) In = m11 = 0 and P(zo + x²) = c.
Next, we note the following upper bound of the Wasserstein distance.
(C( 0z), L(rk, 02)) = inf 1 + +62 + 1 [12
32

---

S 1+ 11+2(E111,,
0-111).
Making use of Proposition 4.2, we have
(2(C( 0s), (ark 0%))
1,2
2202, (1 a4) B1110, 0 [2] B1100
-0-13)
+ 402,200 +
L
<4c2, (1- 0- 1-] 202
+ 1,
1
where the second inequality holds for 0g- = 8 by assumption.
Note that the above upper bound to the Wasserstein distance is independent of the choice of (zo, 2/)). Hence, we can conclude that
W2( 0z), ((rk, 0%)) = (E[W2((C( 0x), C(r 0% ()) + m/}
<e(402,1 a1p) axp) Blll0 0 0-1 202
L
+
1/2
/
We complete the proof of the lemma.
By Lemma E,5, we see that when Zy is close to its stationary distribution n, 6g would not deviate too much from 8/ if it were initialized from the stationary distribution.
Now we consider a joint process (aTR, 0z k220 with arbitrary initialization. By the property of uniform ergodicity of (r*))20. we know that [(rx)) x |Tv I R Choose time tu 2 We construct a second Markov chain (2/ k22,, with the following properties: (1) x ~ and is
maximally coupled to Iike i.e., (1 (((,,) || = P( # x and (2) 0% = Oko- Under this construction, for to + J. have (C 0z), 2) (C2( 0n), [(r/: 0%)) + W2 0,),
L 1/2
<R [4c2,1(1 - (app)* h- E[ - 8" || + 402,2
+1)
+ 16(1 - ax)) tta E [1]0,, - 8" 11] + d22).
where the last inequality follows from Lemma E.4 and Lemma E.5.
For each & with to 2 r, set to t/2. From the above inequality, we obtain that W2(C(x,, 0c),
2 + +1) 1/2
<R 4422, (1 / 0-113] + 402
16611- - aap) (1 [1000 - 11' + c222)
+ +16(1
<Rp (4c2, a1-/11//12 (8(1 - a11) B(1 1- + 02220T
122
I
1/2
+
402,207
+
11
P
0220T + +16(1 ap) (8((1-a))) aa))a - 0" 1131 ca2ar L2
+ c2.2)
< <max(r; /// s00, 0*, ,1, L., R)
<(1 - ((1a4)))/2 s 8" μ. L, R)
where s(0p, L, ,1) denote some constant that depends on the initialization of 0o and problem primitives L, n. but independent of stepsize and iteration index Last inequality holds because μ < 1 and a - 9081. < 1.
Therefore, as t + oc, we obtain that W2(C(rk. 04), D) + 0, which implies that the Markov chain (my, k2) with arbitrary initailization converges the same D. As such, we have proved the desired weak convergence result without the assumption on 2g ~ т initialization.
Additionally, we obtain the following convergence rate. For any initialization (zo, 0n) E X x RRd we have
W2(C(0.).p) S W2(C(xx, 0,), s (1 -aa))/22 s.0).L,H).
33

---

E.2.1 Proof of Proposition E.2
First, we present the following lemma that is similar to [17, Lemma 2.3].
Lemma E.6. For any k < l2 satisfying a<(2 k1) - SL. the following six inequalities hold:
|0
22
8/
kk
k1
+ 0 < SaL k1) 0
|10 22
0
k1 + 00
< SaL(k2
ky 010 2
10
1/11 SaL(k2 A1) (10 + 1)
|0
1/ = SaI(k2 A)) (16!") + 1)
[0]]] 2 < 8aL(k2 k1) (1022) +1
100 0 < Sa 12) (10 + +1)
Proof. Consider the coupling given by equation (E.3), by Assumption 2 and 6, we have
|1001 k++1 - 0//1
|10 - 0z2 - |10 0 0f + 1
= =0 .x) + (0 9(65- .xk) - (
s 2a 1
Given k, < k2, for Vt [ki, k2], since + $ et for Vo E R. we have
[-1
110!"
0.90 < II (1+ 2aL 110 e
f=1
$ (xxp(2a(2)) kn L 0!81
①
2 (1 4a - kn 1 1
22110/4 0
where (i) holds for e" 11 2r Vx E [0. 5 and ae kn) S 1
SL
Then, we have
100 k2
0 5 |00_1
0.2 0.41 0f-1 4a k1)T.10[ -091
Therefore, following alk2 kn) S
st. we have
1
|0 [1] 0
+ a!21 s 4a hn T.] 0 8|21
1:2
kz
s 4a L1) [1 609 @!!
110!! e!!
110 o 041 + 0
4a
An L.10
Then, by rearranging the terms, we have
||0|1 ef9 إ!ا + 0 < 8a(k2 k2 L110
2
thereby we have proved the first two inequalities of Lemma E.6.
By Assumption 2 and and [17, Lemma 2.3]. we can prove the last four inequalities and we omit the details here.
Now, we are ready to prove Proposition E.2. We start with the following decomposition. By equation (E.3), we first have
B|||o[] k-1
[1]
0241 [13] =E
[10
0k4 + a (o(oh) xx) - g xx) + (o+1(!!!) (0+1(0=1)) [Pa]
34

---

=E [10 110112]
2a [00)) 0.. ge
xxx) .xx g(0 xx))
21
+ a TE [1 mxk g(0 x.) + E (0 Ex+1 (0
T2
For T2, by Assumption 2 and 6, we have
T2 S 2 |10
0
We denote E(, zx) = g(. g() to be the noise function. Then, by Assumption 2, we conclude that <(;, 2x. is 2L-Lipschitz continuous. Therefore, Ti1 can be rewritten as:
Ti = E [0]] =00 ..) =(0 =m>)|| , + E [00]] -0 "/l.o(oh)) -((0))))))))
For E [0/") 0 _ g(0 )>} by Assumption 3, have
[of of o(off)) - ((08")>) s uulE [1001] - -0f/112
2 x t s )). For E [00_0 - , ,xx) =(0) mmmi
Let Fx ==
we have
E
00
11 0 =0 .x) - =(0(=) x
(o!)) 0 =(0) 11 .xx) =((l_) mxa) Fr-r]]
E
E
(ol"
de0 e00 1070 mx)) =00 -,- xk)) Fk--]
E
E
(T²)
0 0l 0/- =00 _ T xk) =(0 x- xb,)
E
(Tt)
[o])
[] 0 c(0 .kk) =00 r4) c(0 -, Rx) + =(0 xxk)
E
We assume at S 8L
1. For T3. by definition of mixing time т, we obtain
T3 = E E 10 k- - 0/2 k- c0 xx)
=00 xw))
2] k- Lk kk-7
|10|| - 0,2 k-rrl [1
I L0
[100] - 0f2111 + 4aLE 11001
0 0!! + 0|21
< 4aLE
< (4aL + 256a 2 |1o!| 1|]
where the last inequality holds by Lemma E.6.
For T4, obtain
T4 s E
|0/1
0,20
ال1 k-r + 0001 [111= R (b__ - -(0 #x)l
<(0
< 16aT L 2 [10 0.²1 1110
|1 k- - 0,21
(1 + 128 " L |io!1 162
Below, we bound term by two different Taylor expansions. One the one hand, there exist \ A2 E [0, such that lig 01 (1 21)0(= h = 120 + (1 >a)0 and
=1()]" 1]
0|21 2x
xx (( x²²) (h+
-(اااح01 )))1
=((0 0ل21 e' e'hherr 2x. (0(") 0 الاl + 0
35

---

+ 10th 0 (6 (1, - = - [(0))
$1607 _/
0 (c'(hs mx)) - E' Tx) - -,
(E.6)
< 166rr 12110
0. 0 -2 1/ - h4-F1
x $6aar 12110 02]
of 11 2
+ |00 0 110
hx--1l
(E.7)
$16aT [1 - 0/2112 + 2 0010(1000-0000 -
+ |1 0f_ + 110 k-r 0
$16aT <16aTL>|100 1'110 - 1/21 + 2011 0221022 - -0_1 - SaT 4(10
+ 1) + S L110 0
(E.8)
<16aT - 1/ 20 - || (3110 (
0 SaT
+ +) = (Bound1).
where note that choosing the second iterates for triangle inequality in equation (E.7) and choosing 0l for bounding 0% 0.0_ k- in equation (E.8) are both symmetric, which implies that we can replace
the o!.1 in term A with arbitrary one in {0] af! 0001 6
On the other hand, there exist λI, A2 E [0, 1] such that ps: 02 + (1 -1) k 9h 12
(1 1- and
<10 0 ee(pp, Ix) (0) - of"h - ('n, (0) - -0_-110 k--))
<((0_]) of. é' (p (pk.Ix)(0 [0 - of + /
(E.9)
+ (0_) 0f1 (dxpp, xx)) - -6' -E'(gN, ='(nn,=)))
of-
$16ar $16a7T??110
o 2T.11["" o Illpe - *x 111
00
<16a7/?1100
1 16a7 =f I1lpa qu |1
2 k
+ 1),
(E.
where adding and subtracting the second iterates in equation (E.7) and choosing 0 for bounding 0101
d00 in equation (E.8) are both symmetric. We have
1ppx qull || (0 0(2) + (1 X1)( 0 + (π1 22) - -0,21 (2 + SaTL) o 8aTL(10)) + 1)
s <3110=" - of Sar ((10 || 1
Therefore, we obtain
$16ar 1.² 11 1
+ +2 0!21 ! 0 || + 80T L L(110 || +
SOTT L(110, +1) = (Bound2),
and we can replace the 0/2 in term B and C' with arbitrary one in k0= By (Bound1) and (Bound2), we have Bound2)
a/0 k-. 0
<
< 1.0rL2 - ef + 48ar 1.2 (2(00))))) ||+
Below, we discuss the upper bound for by three cases.
Case 1: If one of 10tL Tu! o has norm that less than 40ar27, where we define 12 = T.22, without loss of generality, we assume ||0[ < 48,712. Multiply 1(100(11 450r12) to both sides of the above inequality, and we have
[(10 k S 48ar
36

---

(16aT - 122 2 + 48a L _ (1(0)) + 1)) [(11[))) I 48ar1=)
<(64 + 1925mr12)aT L 210 1/
where we can replace the of in the left hand of the above inequality with an arbitrary one in (0/_ of" 0f l by the similar argument under (Bound1) and (Bound2).
Case 2: If | 21 ef_11 obtain
10 2 || = _ 2 11 + 1100 S 3100 0,² 1|-
Therefore, by definition of and Lemma E.6, we obtain
[1(00_ S 2 o(211)
$ 20 - 1(10@ _f_ + -1 - 2 -1
< 166TTL2 0% [[[I 1(100
* _0 [0 s 2 1
- 8000 2 0 ||
Case 3: If all four variables in | |لاl
) have norm larger than 46 12, and 100
)
2 2|10 !] 0,20 2/ we obtain
k
|
| || = || 4 + (1 - 11)0/²11 2 ||0|"11 - 110 00 2
2 26
2
|| 7 = || [1]
+ (1 - >2)
|10 ! -110 0/-1111
2 80712 - (1 + 80 1)10 - 0(.1
8
where (i) holds by choosing at S Tez Therefore, we have ||aal| 2 80712 and |l 2 80T12. Therefore, by equation (E.6) and Assumption 6, we obtain
(Case 3)
16a. L 1
o(21
+ 1102" 11
of" (1e'( - G(æx)]l + ||E (6(hh_,, G(*x))l)
<18aT 2'11022 0[21 112
Therefore, obtain
E
E
<BI
1[[ 10 --
11| 8wT12)] E || [ I Sarla)]
+ E 11(1((())))) 11 x- 80T12)] + E|| (1
2 || - 8ar12)]
El [[Case 3)] < (354 + 7686 L3 -0(² 112].
+ E [1110 < 2
0 [I)
By Assumption 6, there exists K2 > 0 such that cō(e) <
# for Ve S kn. By the above bounds, 3072
when ar < min (4 Ke) where we specify the constant c < 1 later, we obtain
E E k+1 - 0 11
< (1 +1+ 2a(-u+ 4aL 2560 12802 + 78447 _ 7688 7688 4a2l²) Eile!!!! of
1 + a+ 1568ar 25 + 15368 15360 + 551a + 4L2) ( of
< 1 + (u((-2222222 + 1568c 256c + 2
+ 524c)
11 11
37

---

<(1 - 1 0/21113
where the last inequality holds by choosing Therefore, for k 2 7 and ar I min( #
1696
Ku 7
we have
90622:
B| k of |3] - (1 - wa)
0 - ||
< 2(1 - - 00 12 + |10!0 0.0
00- - 00
$ 2(1 -a) =B110 00 11
x 4(1 ua)x =B1100"" - 0," 13).
E.3
Proof of Projected SA
Now, we specialize the proof of Theorem E.1 to the projected SA iterates. We consider the same coupling:
0
k+ 0g +a(g(0)) .26) + (o())
0 B
0/3 k+1
0 + (a(( k mxe) + (o
e II B())
[0l2
k++1
*++
We first need to verify that Proposition E.2 holds for projected SA. By the non-expansion property of Il (())) with respect to
|| |l. we obtain the following inequality:
1000 1 A+1
110
0221 < 10041 - k+y 1 10 0,2
22
which implies Lemma E.6 still holds for projected SA. For Proposition E.2, we can notice that the iterates of projected SA will always satisfy Case with a finite bound 33 and we do not need to discuss Cases and 3.
Therefore, when at S. min(
cu 2
where we specify the constant < 1 later, we obtain
5L
E Bi|le!
[1] k+1 - ||9 11
1 + a + (160 + 963)) 256a2 a²(8L + 512a2>3 + 4L2) E110!" -
< (1 + app (-2 + (160 + 963)c 256c + 524c)) @| - 1|
=(1 - -1-- |110 0 12..
where we set 9404963
Therefore, Vk: 2 7 and oT (940+963)
we have
E
2 12] 4(1 -a))==B1110)) 0 [12]
Then, still by the non-expansion II 1(3) with respect || Il. the rest of the proof simply follows the same proof for non-projected SA. As such, we have proven Theorem 4.1.
F Proof of Corollary 4.4
In this section, we present the proof of Corollary 4.4.
Recall that by Theorem 4.3, we obtain for k 2 2T,
W3 [C(0k), va) s (1 -a)) s(0,, 0-, u, L, R).
38

---

By [63, Theorem 4.1], there exists a coupling between 8g and 3o such that
W va) E[[10= xx
Applying Jensen's 's inequality twice, we obtain that
||] - 20]l - [Ei 0 Ill) = Ei - 60 [1 S (1 - axt) s(bb, M, R).
We thus have for all k 2 2T,
||][ [0 - |1 o0l IlI (1 2/2 5'000. 0r . L.
For the second moment, we first note that
E 0 - 0
[[[ 0e (Ox 02)) 0z B (0x - 0 + B((;; - -000
[[E O (0p 000) T]l 00 (0x 00) "Ill + |E[[(> 0x )0_1
< E 0| 0z |l + 21 1110 0z |I]
< El oo |ll + 2VEB110ss 1 a0 ||]
(F.I)
where we apply
obtain the last inequality.
Meanwhile, we have
E 10x Oz 0z 12] (1 au)* s(0o, 0" M4, L, Rt) and E |10 [1]] O(1)
Substituting the above bounds into the right-hand side of inequality (F.1) yields
[0 [1 s (1 422 s"(0,, 0" n. R).
G Proof of Corollary 4.5
In this section, we prove the CLT result.
Proof. Consider the following centered test function h X 12d IR defined
h( 0) = E[]0o]]
To prove that the CLT for function h, need verify the Maxwell-Woodroofe Woodroofe condition [49], ie..
Σ
3/2
Q'h
<0.
L2(D)
n=1
1=0
where Q denotes the transition kernel of the joint Markov chain. If we show the following
ΣΣ
1 = =(n")
Q'h
(G.1)
L2(D)
t=
with r E 1/2), then the
condition is verified, as
3/2
Σ
Q'h
Σ
3/2 < 0o.
LO(D)
We now proceed to prove the desired order (G.1). For sufficiently large n 2 2T., we observe
a-1
#-1
Σ
Q'h
Eo
Σ
Es 1'Il22
L2(D)
t=
2r.
EollQ'h h|22 + n
Σ E,
QQhill2-
T
39

---

We now show that both terms T1 and T22 are of order ( with respect to the parameter n.
For T1, since is transition kernel, its upper bounded as
IQ] (P(4) operator norm equals 1. Hence, Ti can be
Ti Ta Ta x) Ta Tr(Var(0>>)) C1,
where the last inequality follows from Tr(Var(0>>)) I or established in (H.44 and ar - 0 by Definition 2.1.
Before proceeding to analyze the summation in T2, we first recall (E.2), that for 2 2Ta
W2 (C 0c), O(1 ap))
which holds for any (x,0) E x R Hence, by the property of Wasserstein distance [63], there always exists coupling that attains the optimality, i.e.,
[10: 0 6u(x * x²)] O(1( ((11)))))
Br((z,9)).))
Making use of this relationship, we can therefore bound T2.
To = Σ EC 1Q' S
11
Eo 1ollQ'h = =0 (I (1-11-p))12 =0(1,
1
t=Ta
t=Ta
where the last (-) is asymptotic in n. Combining the analysis of T, and T2, we have shown the desired order in (G.1). Therefore, the Maxwell-Woodrre condition has been verified and establish the CLT for averaged nonlinear iterates with constant stepsize and Markovian data.
H Proofs under Minorization Condition
When assuming the perturbed continuous noise condition in Assumption 5, one takes the alterna- tive route to prove weak convergence. This is achieved by establishing the satisfaction of both a minorization condition and drift condition. In this section, we prove the weak convergence result in Theorem 4.3 by following this alternative approach. The subsequent corollaries of weak convergence, namely the non-asymptotic convergence rate in Corollary 4.4 and the Central Limit Theorem (CL.T) in Corollary 4.5, also hold, and we will provide the proofs for these results as well.
H.1 Proof Theorem 4.3
In this section, prove the weak convergence under Assumption 5(a). The proof consists of two major steps. Firstly, built upon the MSE convergence established in Proposition 4.2, we derive multi-state drift condition. Subsequently. we show that under the minorization condition, the Markov chain is (Ik; 0x)x20 is ipirreduuibll. Then, follow [50, Theorem 19.1.3], we can conclude that the Markov chain (I', 0k 2220 is geometrically ergodic.
For completeness, include the Theorem 1.. from [50] below.
Theorem H.1. Suppose that & is up-irreducible chain on X, and let n(x) be a measurable function from X Z.. The chain is geometrically ergodic if is aperiodic and there exists some petite set C, nonnegative function V 2 and bounded on C, and positive constants X < 1 and b satisfying
f pptt) dy) S (v blc(()).
(H.I)
note that the function n(x) can be interpreted as the number of steps we must wait, starting from any æ, for the drift to become negative.
Step Deriving the Drift Condition Given the iteration step
0xt1 02 + alg(O,, xx) + E++1 (0x)),
we have already shown the following convergence rate on the MSE in Proposition 4.2, that
L
0 00 < C2.1 (1 ap) 0- + 02,20
40

---

Inspired by the MSE convergence bound, we define the Lyapunov function : R + [1, oo]
Vix, 0) 10 - 01 + 1.
(H.2)
Therefore, the major goal in this step is to obtain the desired drift condition as shown in (H.1).
Therefore, from the above MSE convergence rate, we first obtain that
L2 Q²V 0n) S 02,1(1 - (up)"V(so 00) + 02 at + 1.
(H.3)
Consider minst 2 c2 and 1}. Then, set 1) 8(1 apj) 02 '2 aT + 1, and consider the following bounded sublevel set,
1-n and
2
Ce = {0: (110 - 1-1 + +1 I m/3).
From (H.3), derive that
("ro 0o) - V (wo. 0o) S (BV (0) + ml c (1)),,0), where C X' Ce. Rewriting the above Lyapunov drift condition, with b m/(1 B). we obtain
Q* 0o) (1 B) (V(o,, 0o) + blc blc((0, Bo))
Setting such that A 1 3, we have
Q* 0o) S X (V 0o) + b1 c10 (0))
which gives the desired multi-step drift condition.
Step 2: Proving the Minorization Condition Now that we have established the desired multi-step drift condition, remains for us to show that Ö is accessible, small, and aperiodic.
Under this setup of (f) in Assumption 5(a), it is straightforward to verify the accessibility of Ć.
For any (x, 0) E X' x Idd we have
Q((x,0). C* (P((''00) X (ee(()x)))
{ J JorECa aapo
- 8'-- ( -g(=-,,000 g(s;,)) a0 > O.
1
(0' Col(x, 0))
As such, we have shown that Ö is accessible.
Assuming C' is small, we can directly conclude aperiodicity following the definition of period of an accessible small set, d(C') = g.c.d. n E N infaec ("(x,C) > 0
Therefore, what remains to show is that Ō is small. For (a. 0) E C and Ā E B(X) x ((Rd)) we define the following projection sets,
A₂ = {0 E RdI (z, 8) E A} and A fx A}.
Therefore,
("" f(LAM ((( , P((0m: 0m) E AI( 0m-1) = (m)) (((m-1))) 6(1x209m==
...PP((1, 01) = d(x(())())))1 ,01)) 0o) (xr, 01)
S p00)))= c(Xxxo))
P((am, 0m) E Al( 0m = (m) 100m)) f(mm-1)))
... ...P(( 01) = (( (x0) 0o) = =(x,0) ())
= -Kaat,, 0000))0 E(X'xCa)
(
P(zm da'l da'l ( ( 1m E (2 9m-1) (m g(mm
41

---

P(zm-1 - 2m-2 (P a0(m-1) (2m 2m (z(m-2), glm--1)))
P(21 = -dx01/10 = x))((1
=d)(0===== = (d 81) = (z,
Pm -I dæ' (am-1 = x PP (mm-1 dx (m 2 = 2/m-2))- ... ..P(z) dr x)
= -WEX EX
(hory lkm1 EO
P(lm (2mmmm,,,mm)) (m(m-1), g(m-1)))
P( d0(m-)) (2 (.,0m=)) = (m Of (mm))))))
... P.) - d000 0o) - (x. (x,0))
Next, for (z, 0) E C, we observe that
d( - -000--0 (x) (xr, 0))
P(O+- d0 ((10-1,00-11)) - (x,))))(x)0)))))))))))) =
-z,00) (0)
a
1
O 0
g(z, 0) do
a Po
a
0 g(z, 0) 0)) a0'
inf iECe
pa
We next recall the linear growth assumption in Assumption 2 that || 0)1 - L([|0] + 1). Hence, given 0 E Ce. Yx X, we have
||0 ag(x 0)ll s ||o| allg(z,
0) < (1+ a +1)
< (1 + aL.) (v M/B+ |10 + 1) - B,
for some bounded value B.
We now define the measure st on Rd as (A) J in SorArce inl deco Pe (
)o=
do'
Hence, it is easy to see that ş (Cg) = 0. Moreover, we note the following property of measure 5t. Claim 1. For A C Ce and X(A) > 0. ct(A) > 0, where denotes the Lebesgue measure.
We delay the proof to the end. Taking the claim as true, derive that
fore Pfmm E A2 mm- (m (lm=
1mm1 ECG
P(Om-1 (1 () 11 9m-2) (m)) (.(m-2),8(m-21)) flmm-11)) ... ..(( = (z0
(0) = (x, 0))
= =Somese Joim-N1ECo (m (a 0m-1) = (m-) g(mm-1)))
1 Amm-2
P(6m-1 = dd (00m-11(2m0)) 100 fm 0m-2) = (m-) 2) glmm (00mm-))(mm2))))))
P(O2 = -d((2) 01) = ((1), = d 00) = (x, 0))
((m) - 0(m g( g(m dd(m))
inf Pa a icCa
((m) 100m-1EC
f J
P(Om-1 d0(m-1) -dgm-1) (2 0m-2))
2 = (m(m-2) glm-
42

---

SenFeco
P(02 = (x) 81) = (x(1), 0()) (P(1)) = c0(20)(x00. 80) = (x. 8))
inf (2,6)E Ed
1 inf Po J0mm-1)ECo at bECо
A(m) - A
g(ā, 8) dg(m)
a
P(Om-1 = dd(m (0 (I 0m- = mm glm- 2)1)
Jomm-21EGe
(zo, P(O2 a0(2) (x1, (2), (x (00)))())(( -00 (x0, 0o)
0))
1
f(m)) -2) (1m))-2 dd(m)
inf
inf Pb BECs
18mm-1)ECe ad
P(0m- d0(m-1)) (3m 0m = (m 00m
(0mmm))0(m-)))) o(m-2))))
m0m 2C0
1
=(02= d0(2) (x11 (x1
= (z) ((())))((0) = -d0(2) (ro, O0) (3r, 0))
JoNECo
/
2 (Arr)
P( = d0(m ( 0m- = (m-)) (m(m-2),
[pmm
9im- (1m-2)
P(O2 - ((0==0(2)(4x)) 01) = , = a0l'' 0o) = (2x, 0))
((1))))P((
JAWECe
2 (CC)))))
Therefore, by combining all the analyses, we obtain
QT ((,,
2 [ JEE Jaalo
P( dz' [m-m1 2(m- ((m-11))(EmmT dm(mm1) Fm-2 (mm-2)
18 EX
P(x = dx = x)
(Jrr (0m Pi(m E Av (1mm 0m-1) = (m- (6mm-11)
Juul EC
P(0m-1=d0(mn) = dd(m-1) 2, 2m- = (m flmm21)))
... .(. do(2) 0o) (z.
2c((Co) m-
<((Arr)
NEX
P( = dr' dr'( (11m1 = (m-1)) ... P(r1 dd = x))
-x
2 25(()) Ixe
((Ar)))(ddr))
=c. x (A),
where ç = st (Ca) and @ 5 being the unique induced product measure on X' x Rdd
As such, we have proven that C is (m, ø x <t) -mmall, and hence (6m, & st)-pettte, and subsequently shown that (Ix, 0% k20 is geometrically ergodic.
43

---

By [50, Theorem 16.0.1 (iv)), we can further conclude that the geometrically ergodic (0),2)) is also V V-uniformly ergodic with the same as defined in (H.2). Therefore, we have the following convergence rate in the V-norm (r,,, Ok), -Va -Fally I kpp, where k and p implicitly depend on the stepsize a.
Lastly, we provide the proof of Claim 1.
Proof. We first recall that for any set B S Rd such that X(B) O, where À refers to the Lebesgue measure, then for 0 E Ce. we know that JteB Po(()dl 2 SteB infoece pe (()dt > Moreover, for given (translation) Ra and A E Ce. we have
J pa - z))dt
[ JHEB=Z pa((')dt 2 Jeen-z0E DEC
- inf po > 0.
Following the properties stated above, we define l(()) SEEB infoec po z)dí, and it is easy to verify that h(z) is continuous function. Hence, for bounded set D, we have inf h(2) > O. Subsequently, we define the measure <t induced by h and we verify that
(A) = inf I ||
inf po 2)dt > 0. BEC
IrEAnO
H.2 Proof Corollary 4.4
As shown in the previous section, the joint process (æx, 0k)k20 is V-uniformly ergodic and hence also exhibits a geometric non-asymptotic convergence rate under the V-weighted norm. Subsequently, this corresponds to version of Corollary 4.4 resulting in a different set of convergence rate coefficients. Thus, we restate Corollary 4.4 in the context of the minorization setting and provide the proof below.
Corollary H.2 (Nom-Asymptotic Convergence Rate). For any initialization of 0u IRd, under the setting of Theorem 4.3, we have | S x.pp L,p,, and | (8))) S k. s" L, p)),
where & and p are defined in (4.1) and implicitly depend on a.
Proof. For V-uniformly ergodic Markov chain (æx, 02 22) when functions f X' Rdd - R2 is
dominated by the Lyapunov function, i.e., || < V, enjoys the following convergence property,
fx0" 9o) fll s xp" (9)).
Consider test function f(0,x) = 0 0* It is easy to see that || S V. Hence, we obtain
[|E[0,]] ||00=]| = 110h 0) //ll S <p"
Next, consider f'(x: = (0 (0 0T) Clearly, | S V. Therefore,
[|E 0") (0, 0T) 10 (0 07) TI I V (0o). For the LHS, we have
[[, 0* (0, T - (0 - 0r (0xx - T
= || - EE0000
E(O, - 00) - 0 O'Ei(O, 0zx) TII
2 |E El0 0 0
2||[ 020 00
Subsequently,
| - E T.11 11 S (2 + 11)xp
The above results imply the convergence of the first two moments. Moreover, we conclude that Var(fx))
Var(A 8*) < E1 - 0" 10
lim E[[10 0-11 z ar.
t
Additionally,
El 0-111 < =11
0 0013
(H.4)
44

---

H.3 Proof of Corollary 4.5
After establishing the V-uniform ergodicity the joint process (zg, 8k)k20 the central limit theorem for averaged iterates follows as a straightforward consequence.
Proof. For any test function it has the following CLT results,
IR Fd that satisfies ||A||2 V, by Theorem 17.0.1 [50].
R
(he - Blhool)] = 110,
t=0
Therefore, consider (1,, 0) 0 - 0" it is easy to see that |1:112 I V, and hence we naturally obtain
the desired CLT result, v > (0, - E[0xx)) = (0, E(a)) as h + 0o.
I Proof of Theorem 4.6
We now provide the proof of Theorem 4.6 on characterizing the asymptotic bias of nonlinear SA.
L11 BAR and Prelininaries
The proof utilizes the basic adjoint relationship (BAR) approach to study the stationary distribution
EE. [Pp((P [)) 0,
via carefully designed test functions h. We refer readers to [33] for the derivation of the following
properties Markovian SA stationarity,
[[ E S}
Too] [xr) E[110x0+1 E SS Ioo+))(x),
(I.1)
Too (x) Effoc+1 Foo+
(1.2)
EI(02) 02
xxx)(x) = EE((0++1) 02 Ix+1](())
(1.3)
Following the Borel state space assumption in [0xc ) 10000 x) induce regular conditional probability measure, which we denote as 0(, = x), and hence (I.1) can be reformulated as
10 S x) 5(0xc+1 S, z).
Before proceeding to the proof, we introduce the following shorthands and notations. For x E X,
z (x) [0 - 0t) 00)000/00 x],
(x) == 2, (x) nı
Following the differentiability assumption of g in Assumption and we can apply Taylor expansion to and we note the following notation residuals.
g(0, x)) g(00, x) + o' (0" x0 0*) "00 (0 0-)02 R2(0,v)
(1.4)
=g(0", x)) + o' (0" z0) 0*) (0,
(L.5)
By Assumption 3 and results from Proposition 4.2 and 4.2, we note that the residual R₂ (0, x) satisfies
(0, 1'"1" < +00.
BER
Hence, we have
|R, xo )1l (2(3)) S 1 - 8" ||] = (((a))//2) 2,3,33
Lastly, we denote
g(0)= = Ex~- (g (0,x),
(2( = Ex-, (0, (0,
g (0) = Ez- (0, x)],
g2 (1) (0) = Ex~z [(g (0, x))
(0) := Ex<
We are now ready to present our proof. The proof consists of two major steps. For the complexity of this problem, we first set aside the projection constraint and focus on the BAR analysis, and we shall present the asymptotic bias characterization without the projection step. The analysis in this step thus shall work for the minorization proof technique as well. Then, in the second step, we elaborate on the impact brought along by the projection analysis and conclude proof.
45

---

I.2 Step 1: Bias Characterization without Projection
I.2.1
Step 1: First Moment Analysis
Consider test function h (z, 0) 0* Therefore, we first have
[lg((0x, (1 + (0x))))(0w)))
g00++1 0*] E 00
which immediately implies that
0 Elg(0x xz00 )}
(1.6)
Substituting the Taylor expansion (I.4) back into (I.6), we have
E(g(0", + Elg' (0*, To0 (0 - 0*)] - ス R 2000 -
sool
2
=0x 0²) 1 Blg (0 )-) + ((ar)3/1)
(1.7)
where we make use of [ =x]] g(0") = 0 by definition and the order or (oc
((ar))//2) to obtain the second equality.
Next, we proceed to analyze the two terms in (I.7). For the first term, we have
Elg' (0" ) (0xc 0²)] = Elg' (0", Inx )=1 (Ioa) E[g' (0" = )01 (2 + (8") - -0%.
(I.8)
We now move on to analyze the second term, and obtain
E[g" (0", (0x) - 0-)02) = E0'"( xx0) (1
Ef"" xx 0o (x (0)) 8*) 0z)021
(I.9)
Hence, substituting (I.8) and (I.9) back into (I.7), we reorganize the terms and arrive at
10000 - 0*] = -
Big (0" )6 (f
(I.10)
(l"" (0" x =x00) g - 88)021))
(I.11)
+ ((ar))312)
To obtain a refined characterization of the asymptotic bias, we carefully analyze the remaining three terms (I..0)((..I), We focus on each term in the next three sections respectively.
1.2.2 Step 2: Second Moment Analysis
We start with analyzing [0( 0*) in this section.
Following the BAR approach, we consider the test function (22 0) (0 0')02 and obtain
[00o++1 0 [0x 0"
Ex0+
E( 0*)02) + a² (E] Fox 82 E ((( 0)
+ a(E[g(0 2.0) 2 (0xc - 0¹) + E( - 8²) 3 g(0.g. Txx)]) )]).
Simplifying the above expression, we have
= a(E((g(f=,, (0 0²) g(oc xxo)] Elg (0o Foo) @ (fx 0*)))
B[(Eoo+1 (fx))
(I.12)
We adopt a similar approach in analyzing the above relationship that contains g(f.c, xx)) as in the previous step. We make use of the Taylor expansion of 6* but at lower order. We substitute the Taylor expansion (I.5) into (1.12) and obtain
0 =EE(g(00 xxo0 + g (0", 10x 0²) R2 02 + (
46

---

xx) + (6
(fx - 8-
+B[(Ox - (g(0) 100 -0) R2 20. cco)]
WE]((0 moo) @ (0x ())) B[00> 0²) @ g(0 [oo)
(1.13)
+ #00) (0 (*)) @ (0 0¹) Ei f*) @ (g (0* x0x - 8*)]
(L.14)
+ (0=x
(') 8))) 22)
(L.15)
+ alElg(00, (0' xoo 10 -0))] a (0" xx 0²)) @ -00 xx0)]]
(1.16)
+ BBB Too) @ (0 0)) + [[ - 0²) @ R2 TT))
+ alB((o(0" )x0)) |2 + [F[(( (0x)) 82 O()rr).
Therefore, proceed to analyze the terms in (1.13) Starting with the terms in (I.13), we have
Eig(0" ( @ (0 00)] = Elg(( Too) @ (T)o + T21)]
Elg((0 xmx) 2 0d((2())] + (10(00,,za0) @E 0*]
[Flg(0, xoo) 20 61
Similarly,
B[(0>> - 0*) @ xzx)]= = (16)
@ "0000 xx]]]
Next, for the terms in (l.14), we have
Bi(g' (0", xI, (0 - )) @ (0x0 - 0¹] = Blg' (0", x (0x - 80)
= Elg' (0" = (02( + x22)
Elyy (0", Nxx (1) (0) 07)
Similarly,
El(00> -0) 00 (s'(0"==x)000 (0x - 0*))] = B[02(( (0", xx))]] + Bl(0x - 00)8219())07)
Moving on to the second term in (I.15)
El(y' (0", (0xx 02)) = Elg' (0", ) 2') (0= [IxO
Elg' (0", .x> ) (xxx) + T22)g' (0 _xoo
= Elg' Elg'(0", - 02 (000)) (0" xx)ه + 3 (1) [[(0>> 02)
Last, for the terms in (1.16)
Elg(0", xoo) & (g' (0", xxx) (0xx -0))] Elg(O" Ixx) 2 (g' _r0) (01 (xxz) (21))) ))
Elg((0, xxx) @ (g' (0" 2c )81 (Icz
Elg(0" xx 8 (g'
x xz )10 Tool)]
Similarly,
((' (00) - 07)) @ g(0"
xxx] = El(g' (00=0(000==0)00 (1=z )) 2 g(0" xx=]]
+ EE((g' (0", Zoo E(0x xx0l) @ g xxx)).
Lastly, by second order Taylor expansion around 0* of C(f (1(5))+1(00))))) 2 we have
C(0x) = -(0)
0*] +* (1,R)(000))
where (0) satisfies supper {
[112((0)11(1000 - 111 + 110 -1) < 00.
47

---

Substituting the above analyses of the terms and consolidating the terms, we obtain
(1 [(0 87)
+ (1xx g(0 xx,)]
Ely' (B, ]x]]
(e xx a (E (6" x E rool @ g(f", Tc]]
a ( xxc (g' Jxc 2 Txll] (L.17)
(0 (0,, @ 10xc 1' Efx 8*) R2 Too + aC 0*1 ())
By far, observe that the remaining terms all contain 51 and 62. Therefore, conclude analysis of E[ 8*) yz2 at this step and leave the analysis of 61 and 82 to the next section.
1.2.3 Step 3: Analysis of the d-System
In this section, we analyze and 82.
Analysis of d1. Starting with 81, we first consider the following recursive relationship induced by (1.2).
E[000+11 - 000+0 = s) s]= / P'((,,d''E(0oo-11 001 = 8,00000 81
P' 0 ag(( =sy
R
@
f P'(s,ds') 0x - 0" + a 90 xxx) g'(0" xxx) - -0") + R2(0x 1000 = 87)
(" 0x -r0 |
+ / (s do') (((0 ,') ,
s') 10 = s0 &J++ERR((
( co, Ioo )0o = s1).
where in (i) we make use of the update rule in (2.1), Elcoo+1 ( x0x0 = 0 and conditional independence To0+1 IL Oze Zoc. Next, we substitute the Taylor expansion (I.5) to obtain (ii).
Writing with notation shorthands and 8, we have
(s) / (s((s)ds))(((s))
(I.18)
+ t J P's (s((0)s)) ((())))))))))))))))))))))))
= =s]).
If we apply π to both sides of (1.18), we obtain
/ x (ds)) (s.)))))))))))))) (s)()((()) 8') + o (0" 8)))(s')) + (R 8')|=x== = =s]) O.
Analyzing the three terms closely, we observe that
/ (dss) / (s ss) = g00 s') (s,s)) -(00))
=a(do')
I r(ds) / P' (8)))))) = (E
48

---

f (dss) / P" (I'( 80) = [0 tool!,
and hence we first obtain
Egg (0" +
2co 0.
(I.19)
We now subtract 22 on both sides of (1.18), and obtain
(s) / Pe ('(s,ds')(((s')
d'((s (9(s))))(9(000,0)) ((00,, 58) + g0 (s)) 80 -00 =s)
+ a
n
(P"(s, (o55)--((de)) )(d5'))((s) (s')
+ ( (oadd)))7((ss) =(db') (0(0", + ()))))))())) + (00 = s1).
Consolidating the terms, we have
(I (I-P* P {s)
=a / P" (s. - (ds')) (ol0r, (000,'')=1('') BiRggOO = 81). (1.20)
We next note the following properties,
[E[ x = = s|](2(()) - =x.1
(1 & B[100x - 1- ((aT)= = 0(1).
Therefore, first conclude that (]]] O(a).
Subsequently, from (I.19). we can derive that
0 Elg' (0" tx )21 (+x=)) EB [xc]]
E[g' (0" (zx E - 8*] (8020000: Roo]]
E 0*] (g (0)) Elg' (0- (1 + (0 N: 2x00)))
(I.21)
Hence, together with the relationship between ò and 21, we have
21 81 (0*) Elg' + 18) [oool
(1.22)
Lastly, we substitute (I.22) back into (I.20) and obtain
(T p (s)
Pa (s,,'''' T(ds') 9(0 m(d5)))((0r
(" ds') ) =(ds') (00" 5s) (20))) Elg'(0 x (00, 11006 (Isoo)
+
P ("s =(d6') g/ (0 (8) (') (0()) - ' EE (foc, [x0)]
a
ds')) - =((d')) No. = s1) = .8) O(a²T),
+
R.
where
((8",))= = =( p +++10 II] ---))110 1P M) (8) = - (T p + I1) - - (s) ds' (8" s¹)
(8)=
49

---

Therefore, for the terms that involve 51, we can conclude that
Big(0", (ix) 2 81 (xx) = a. + O(a²T) and [1x) 0 [x(* aM + O(a²r),
(60" = av' Oaa
(1.23)
where M and are independent of a.
Note that (1.23) together with (I.21) implies that
El0x 0*] = =v()) + O(ar).
Analysis of dg. For 22, we first note that
E[x -
- -- - =0()==(((a7))) (((a))))
and hence this implies that
[ = O(at).
Next, following (I.3), we obtain the following recursive recursive
[[ )0) 82 1oo+1 = =1 / pd P' ( ds) - 07) Foo+1 = [0001
-00000 =
@
/ p (s((' - 0r + alg(0>o: [oc) + 18) =]
( / (s('s'ss)E(1 - 07)88/x== =s]
+ a² (s)( 05) =s] / Pr (b)) =s]
+a / pr((s: ds) (E[(00 (F)() 8*) g(0 2) + Elg(( @ (fx - 8r) (T) sl
where in (i) we make of the update rule in (2.1) and conditional independence Jo011 1l Oxc loc. Next, we substitute the Taylor expansion (I.5) to obtain (ii).
Writing with 22 shorthand, we have
=2(d)) - (1 =a(d)=/p((( ds)=2(s)
aa² / pr((', dssssss))B((o(( I0 a / (* dss) (0xx))) =s]
a / pr(s', ds)
E[(0> ds)
8r) g(oac 5)(=> = s) + Big(O 8) @ (0xc - 2Z = sl)
Making of the relationship (P-- 11)22 (P* II)d2, we have
82(8") / (''(s' (adds)-((ie (8(())
+a² / dssssd))E((((( 8)) =s [() =s]
+a / (s)(s 00)00(00 3) = s) E[g(000 8) (0 - -0") = sl)
[E[(0>
Hence,
(1 P- +1)82(()))))
=a caf (sss [[( 0²) 8 g(0,., s) = s) + B[g 8) 3 (0x - 1200 = s]
+ +o² =02/P((),05) (5 socc + EE(( (2 ss
[[g(((
50

---

To analyze the above system of d2, we make use of the Taylor expansion of g(0cc s) and Eoc (0cc).
Starting with the first term, we have
Ei - )*) 2 g(d 2000 =
= E (0x 0-) 2 00(0 8) g0(0 00x0 - -0)) + R2(0 8) x =
=x((s) 8 g(0 5) + (5)g (0 5) El - 0*) @ R2(0, 5) 10o = 5)
-(61())- - (g (0)) Elg (0' axe 60 (xoc)) + E| T ]oo11] 8 g(0",
+ =2))))' (0", .) + 00 - 0*) @ R2 (0, 8) 1 s].
Similarly, we have the following relationship for the second term,
B0g 8) (0xc 0 |1 =]
+ EB[ &xeol) (0 g000" 8) @ (s)()) (g (Elg'(00 ,00 )01 (20o)) g00 8) (8) (0, 8) s (0x 0²) 1x s).
Next, we proceed to analyze the third term. Ei,g(t>,, s)) 82 xx =
82 = B [[(000 8) + "0'(0", s0 -0) R2(0 5) 1oo =
Bi(g(0" 8)) 02 Jo = =]+ +f (0 0))) = s)
+ [lg((" 8) 2 (0" (0 =))) = s|
E((g (0" <) -b") )) s 6(0",))<==> = s]
+ Elo(0",s)) @ (2,0 =x = s] E()o((0 s) @ g(0", 5) xo = s)
+ El(g'(0", (0", (0 f)) @ R2 3x s]
+ E[R2(0xx, 8) @ ( (0' 8) 00x 0²) |x=x s] + R22 8)) 12.00 =]]
Lastly, for the noise term, derive that
(00)))+((00)) 02 Too = s) = EI(Ex=+1 (0*) +
xx = b) = =s].
Leveraging on the respective orders, we can conclude that
| O()²r).
Therefore, for mommedtmoment cross-terms, we have the following orders
Elg' (0*, 2:0 (xro)) O(a²r) and E((2(*xx)) (0", xxo) = =
(0" (0"," = ==xx 0
(I.24)
1,2.4 Step 4: Bias Characterization
Finally, we are ready to consolidate the above analyses and conclude the characterization of the asymptotic bias.
We recall that we have already shown the following expansion of the asymptotic bias E - -0'
(8)) (El''(8 (10" 1 (10 - )
+ (((a)33/2)
By our analyses above, we have shown that
alI P II) -I' -I) +0
Hence, we derive that
Elg' (0", ( (0", x10 p* +11+ -11 -1)) (Ioo)) O(a²r).
51

---

For the second term, we simply use the order shown in (I.24).
Lastly, substitute our analyses of 61 and 62 into the expansion of MSE (1.17) and derive that
(gth) & (f - 87)
agj((0)) + (l (0*)) 6
+ + xx)) @ (I P + -P* ll (= +aB[(I- P + II) (P- - M) (1oo) @ g(0 ; + O(a²r).
Therefore, combining all the analyses, have shown the bias characterization in Theorem 4.6,
Ei0x
8"
(0") (0", Jex "(000 [xx]]
+a (0)) 32((0) (B((Ex++1(0))) (8)
+
Elg( (0)(00))
xo0 @ h("0, ااححد ) + Elh(O" xoo) g(0
اx))) ,x00rxxx)))
(((a))/22)
where
A = (0)) 1 ( 100 8)) (I p' P'+ -Tgoo- (s)
ds' (T pM -D "o"))(0"
-
Therefore, we see that assuming weak convergence without projection, the bias admits a leading term of order a. We emphasize that the expansion holds as equality, rather than an upper bound.
I.3 Step 2: Impact of Projection on Bias
Now, proceed analyze the impact of having the additional projection step the asymptotic bias characterization. the following, we use the shorthand 1/+1/2 to denote the iterate we obtain before the projection step, i.e.,
01+1/2 0₂ + a (g(0,, 21) + (x+1(0)) and θ.+1 = 1I (
Therefore, we see that our analysis from Step can be understood as the analysis for 0x/1
Starting with the first moment analysis with test function h2 (I, 0) - 8", have
E 10000 0*]
1 10000+11/2 0*] + B - 0x011/2]
10 0-] + a (00 Blex++ (0x))) + B00 6 0x41/22
which implies that
E(0x011 0xc11/2l = Elg (0",
2zc) - -0)] 2 E00 (00 -8) 0
(I.25)
Therefore, turn focus to analyzing E00x0+1 0 0xc 1/2].
El0xc+1 1/22
BB(000+1 0 -00+112)1(( 0'1l < [}] + 02001/ 0- > 81
=E[(0o+11 - 1/2+
81 2 3}}.
where we note that when |//+1/2 8*l < B implies that ||0/11/2| ll < 3 | < 2,3 and hence
0x--1 f,41/2 in this case. To analyze the remaining term, we use Hölder's inequality and obtain
[i - Oxx 110
- 8* 2 *|1l
< E /P (1101 0²) -
(0.0+1/2 0*) > [1 0- 2 8}]
52

---

211 0 (P] - 0*1 2 B)) 1/9
Setting p and q 6/5, and making use of the property that B01100+11/2 0-11 (((a)))) from Proposition 4.2, we have
E 110 .- (P(1 11 2 R)) 5/6
x (aT)3/6
3/6
1
2 (aT)²
Hence, we can conclude that
El0 -0041/l ((
Substituting this order information back into (I.25), we can see that [0 1/0+1/2 O(a²r)). Recall that (loog(1/a)) and hence can assimilate this residual order from projection into the existing (((aT) (((a)))/)) residual term.
For the remaining terms, we follow the existing analysis in Section 1.2.1 and again obtain
El0xx 0*] = (00 Blg'(0" (0", s0 )0x)) (x
2 { ((")) - -09)02))
+ (((TT)33/3)
Now, we proceed to analyze [0x (0x - )²) and examine the impact of projection. Consider test function (xx 0) (0 0r) 02
e2 and follow similar strategy as the first moment analysis, we have
[(0000+1 -00)02) o[(000+1/2 0-) + EI(0 0-)02 (0xo+1/2 0-) 0
B[(O~x 0d) 00) a² (B[(g(0xx: xxx) 02] + 1 1)
+ (1 2oo) 2 (0x - 0¹)] + [B[( 0*) @ g(0 xooo
+ B[(Oxo+1 00)00 (0x+ 0") 8
Hence, by reorganizing the terms, have
1 02) (0x+11/2 87)
= [[ Ioo )) 82 + E[(5 o0([50+11 (0xc)
(fx xx @ (f 0r)] + (fxc 8¹) @ xx0)),)
Therefore, we turn our focus to analyzing [= - 02) (0 - 82) Similar as the first moment analysis, have
E Ef000+1 8-)02 x0 82)
E[(((00+1 - 8*) (0 1/2 8r) 02 [1] (|0 0-1 2 B)).
To analyze the on the right-hand side, again make of Hölder's inequality and obtain
[E[ - 02 (0x 0r) 0-)00) | - 8* 2 &H1l
< <BV/111(00++ 02) (0 0² 100 [1] 0- 2 81
< 2|21/[[1000111 0- 20 (P( 0*1 B)) 1/0
Setting 3 and q 3/2, and making use of the property that |B|1000 0- (((ar)²) from Proposition 4.2, we have
E 1/3 //13 0t 10 0- 2 2/) < ( 0 2/3
x (a7)3
Hence, we can conclude that
E[00--1 - -2- 100))22(0001//22 - ((ar))))
53

---

From the analyses above, we can also conclude that
|B|00++1 - -00 L2(x) (((aT) [0[(00++1- - 0-) (000-112 - 0r)
0-) 02 ==))) =
Therefore, combining the analyses above, we see that the projection only introduces error terms of order (aa²7)). Hence, combining the analysis from Section 1.2.1, can conclude the same desired order that
B(A 8*] = ob + (((a))//3)
Additional Insights on TA and RR
In this section, we present more detailed results that characterize the first and second moment of Polayk-Ruppert (PR) tail-averaged iterates and Kichardson-Romber (RR) extrapolated iterates.
The following corollary provides non-asymptotic characterization for the first two moments of PR tail-averaged iterates Oko.k-
Corollary J.1 (Tail Averaging). Under the setting of Theorem 4.6, the tail-averaged iterates satisfy the following bounds for k > ko + 2r and kin 2 + ap
log
(atm):
[1 0044 (U--au)a
Bl0 No. -07 = ab + (((aTa) )312)
and
(J.1)
alk - ki)) -ko)
0-) = a²bb" + +0(a (aTa)3/2) + o Ta
(1 (1- aql)
E2 (0la) ka.k
ko.k - (0)(
+
k- tio
a (k ko) ?
(J.2)
With this result, taking the trace on both sides of (J.2) recovers Corollary 4.7.
Proof.
First, we have
E (((a) Ko.k
07) = [0x]] 0³) + 1: ko k=ko
(0. 0z)
By Corollary 4.4, we obtain
[[O, E[Axo]l $ (1 op)o s' I,, 1.)
Hence, it follows that
Σ t=ko
E.. 102 020)
5
|E [0.] B[000]]
t=ko
< s' (fo. L, 1u) (1 (1-a44) 4g
1
/(1 app)
to 2
< s'o, L. -1-au)
aq))
ax
Together with Theorem 4.6, we have
0r ab (((Ta)33/2) +0 ((1 ko/2
(())
kg.k
{a(k
a(k - Ko)
thereby finishing the proof of the first moment.
54

---

To bound the second moment of the tail-averaged iterate, we follow the proof technique in [33, Section A.6.2] We notice that
01o0 ko.k
8*)
(8ho) - 04) )
(())
E [0oo] + TE [0co] -0+) (0)(o//))
(BL.) - [00o + +B [0 0')
=E
ko.k
E
ko.k
- E [80ll)
(8/o0 ko.
E (100ol)
+ (88 - E [0xe]) (E) [0 - -00)
21
72
+
(E [0xm] - 0²) (Olo) Eggh - E [0xel)
+ +E (E [0so] - 03) (B [0x0] 07)
(B
23
T4
For T2, have
k-1
T2 k ko
Σ t==ko
E 10 0001
[B[020) - T²)
=0 ( a4))ka/2 ((-aa))aa))
(ab + (((TT)) = ( /0/2
aak: ki)
(k: ko)
The term T3 is similar to T2 and obeys the same bound.
For Tr, have
T4 = (ob
+ (((aTa) = a²66" + + 5/2))
For Tú, have
T
Σ
k-
(0: - [[0x0) ))
k-1
Σ
(0. (0c-BBp E[0==))] ]
(k: Ko) 2
ko
t=
k k-1
E [0, R((xcl) (0. - E[(0x))] ]
(1.3)
(k: ko)²
2
E [(00 B((x<l) (0: B[000l)) |]
+
(J.4)
(k: ko)
1=1+1
E [00 (0: B(00o0)
+
(J.5)
(ks - ko)
(= 1=t+1
By Corollary 4.4 and Proposition 4.2 we have
E (0. - [) (0: B[Oco)) 7]
= (B[0,0]] - E[Oxot 7] ([ -- E|O 7)
(B [0x T] E(O00 J [0.1 - 2T [0000 7))
= =(B [0,0]] -E 0x 7) + Var (0x)) E[0,- Ox 1 T -- -E 0xx)
-o (11oa4)² + ara).
where we bound Var (0zo) with ((TTa) by Proposition 4.2 and Fatou's 's lemma.
55

---

Then, for (I.3), we have
Σ
(1--a1) anj) + taaa)
(1.3)
(k: - ku)
k=
0
(1 (1- + +0
aTa
(k Ko) 2
k: knn
t=ka
ko/2
=
0Ta
+
a (k: ko) )
k ko
We restate the following claim, whose proof closely resembles Claim 4 in [33].
Claim 2. Fort 2 +
+ ap ara
log
and 2 t + 2Ta we have
(E[(00-11000)) 11((())) (0: (E((())) "] O ((aTa) (11-a)) )
Then, by [33, Claim 4], we have term (J.4) 0 (k Similarly, we have term (J.5)= (
Therefore, we have
)
apt) Ti == a (k ko)
Ta ko
(J.6)
By adding Ti-T4 together, obtain
E (1
Roo. - 0²) (0h%) - 0
=a bi² + O(a (ATa) )//2))//+))))) + (1-api)ko/2 ko//
(k: - 1o)
(1 aa)) ko/2
Ta
+
a - ho)
k k-
(aTa)3/2) =a 20T + +0(a (aTa) )3/2) + 0
0
Ta
+ (1 ap))ko/2
k k ko a ak - 1o)
Next, we present the following corollary formalizes the aon-asymptotic characterization for the first two moments of the RR-extrapolated iterate 0hoo)
Corollary J.2 (Richardson-Romilll Romberg Extrapolation). Under the setting of Theorem 4.6, the RR
extrapolated iterates with stepsizes a and 2o satisfy the following bounds for all Ko + 2T. and kn 2 Ta + ax
log
( (11-ay -aj)/o/2 )1)
00 ((aTa)) 33/2) + +0 book
and
(J.7)
a(k kio)
(1 aap) kol2
E [(0o ko.k
+ - 0r (0ho,k - (00) (((Ta))))
Ta +
(J.8)
k ko
a (k ko)
Proof. By equation (J.1), we obtain
E
0 (()
8" =E 20(0)) [[2n)] kg.k
0" =2E g((a) .r
-E
[g(20) kag. 6"
ko.k
(1 (1-apt)
asp) (a/))/// /t/0222
+ O =2 ab + (((TTa)313
a(k: - Ko)
(1- (1-2ap1) 22a1)/k0/2 ko/2
2ab + +0((2022)) )3/2) 0
a(k: ko)
=0((aTa)3/3) +0 (1 (LL-au)ho/
aik - ko)
56

---

Let u1 = 000)
(
u2 = ((20)
[/20) and 2
0000
0
ko.k
ka.k
With these notations, O.O. - 00 = 201 - U2 + u. We then have the following bound
(ala)) Ko.
84) (8hor
- 00)) '
< 22 1/2 + vil
No.k
33E 222 1| + 3E /wel + 3|1011
By equation (I.6), we have
(E U1u =0 ( (11 lajj))////2 (11-a
E [ - Tr
+ Ta
(k: ko)
ko
Similarly, we have
( (1 k0/2
E l| U2 112 =0
(k: ( ki)
+ k ki
T2a
By Theorem 4.6, we have ||u|β2 = =0(TTa)))) Combining these bounds, we have
(1 [1- (1-ap))b0/ h0/2
B [0 (Oko,
- -00 (((ara))) (()(araa)++0 -0(--
Ta
ko
a (k: ko)
57

---

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:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope. The main results are elaborately discussed in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 or
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 the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged 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.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
58

---

Justification:
The assumptions for this paper are stated in Section 2 and Section 4, with more detailed discussion provided in Appendix B. Complete proofs detailed in Appen- dices D-J.
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 referenced in the statement of any theorems.
The proof' can either appear 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 or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: 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)?
Answer: [Yes]
Justification:
The experiment details are fully described in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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 large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS 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 new model architecture, the paper should describe the architecture clearly and fully.
(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).
(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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
59

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is publicly available at htttps://ggiie htg.ttttbb.cco/lccyyoooooonaaaaa nonlinear- sa- bias.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. cctpublic//eeeccccccccccccccecct habbiccggiidss//// /Coo//eoeeeeeeeee wwwtuubmmsssioni seiissolisiyyy 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) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experiment details are fully described in Section
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 provided either with the code, 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: [Yes]
Justification: Given the experiment set-up, bars omitted for the convergence plots in Figure 1, because the focus is on the asymptotic bias, to which Polyak-Rupper averaged iterates converge almost surely. As the bias approaches its limit, variability decreases, making error bars unnecessary.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
60

---

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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-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 show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain 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 on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computation resources are disclosed in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount 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: htnpa:////euriiee neerrps....pp//
lins?
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
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 (c.g.. if there 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 societal impacts of the work performed?
Answer: [No]
Justification: This paper is theoretical and has potential negative social impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
61

---

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 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 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 or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
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
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, 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.
62

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s 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: This 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
63

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
64


Reviews:
[{"review_id": "kgvE8YQMv7", "reviewer": "Reviewer_3y4U", "summary": "This paper investigates stochastic approximation (SA) with Markovian data and nonlinear updates under constant stepsize, and establishes the weak convergence of the joint process $(x_t, \\theta_t)$. It also presents a precise characterization of the asymptotic bias of the SA iterates.", "questions": "1. About Assump. 3: for many GLMs, we actually do not have strong convexity. I feel this assumption is a bit strong. \n2. Page 4, line 147: is the notation superscript \"\\cross 2\" defined anywhere? I assume this denotes the outer product of a vector. \n3. Similar to Assump. 3, Assump. 4 should be justified further as well.", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find this paper well-written. The analysis appears to be correct (although details are not checked). Also, both the literature review and motivation are very clear. It seems to me that this paper has solved a challenging problem, caused by Markovian data and nonlinear updates.", "weaknesses": "I find the presentation of this paper a bit technical for people that are not very familiar with this area. In addition, perhaps some numerical experiments should be performed to better illustrate the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below.\n\n**Comment: Numerical experiments.**\n\nWe thank the reviewer for the suggestion. We conduct a set of experiments, running SGD on $L_2$-regularized logistic regression with Markovian data, to verify our theoretical results: the existence of bias, bias reduction via Richardson-Romberg (RR) extrapolation, and the central limit theorem (CLT) of Polyak-Ruppert (PR) averaged iterates. Using $L_2$-regularized logistic regression also demonstrates the practicality of our results in the context of generalized linear models (GLMs). For a more detailed discussion and the experiment results, please refer to the **global rebuttal** and the figures in the one-page PDF.\nWe will add the numerical experiments in the revised paper.\n\n**Comment: Discussion on Assumption 3 on strong convexity/monotonicity.**\n\nWe thank the reviewer for raising this point, and we refer the reviewer to the **global rebuttal** for clarification on the strong convexity/monotonicity assumption. \n\n**Comment: the $\\otimes$ notation.**\n\nWe use \"$u\\otimes v$'' to denote the tensor product of the two vectors $u$ and $v$, and \"$u^{\\otimes k}$\" to denote the $k$-th tensor power of vector $u$. When $k=2$, it is simply the outer product of $M$. We thank the reviewer for pointing this out, and we will add this definition to the paper.\n\n**Comment: Discussion on Assumption 4 on the noise sequence.**\n\nWe would like to further clarify Assumption 4, in which we assume the existence of the $2p$ moment of the noise sequence. We note that it is standard in the SA literature to assume the existence of the $2p$ moment of the noise sequence to control the $2p$ moment of the limiting random variable, as seen in [18,53,60] (cited in our submission). Moreover, we believe that this assumption is necessary; without a finite $2p$ moment for the noise sequence, the limiting random variable $\\theta_\\infty$ might not have a finite $2p$ moment. For example, consider the simple case  $\\theta_{t+1}=\\theta_t-\\alpha(\\theta_t-w_t)$, with $\\theta_0=0$ and iid noise $w_t$. Note that we have $\\theta_T=\\alpha\\sum_{t=0}^{T-1}(1-\\alpha)^{T-t}w_t$. Therefore, it is easy to see that if the noise sequence does not have a finite $2p$ moment, $\\theta_\\infty$ would not have a finite $2p$ moment.", "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": "9JpgErR7aI", "reviewer": "Reviewer_o1Ug", "summary": "This paper considers a nonlinear stochastic approximation (SA) problem with Markov noise (MC). It is assumed that the MC is uniformly geometrically ergodic. Instead of the standard iterative procedure, a projection onto a bounded set is additionally introduced (the latter can be relaxed under the additional assumption of the existence of a positive density). Under these assumptions the authors manage to write a decomposition that characterizes the bias. At the same time, they manage to identify three factors influencing the bias: the factor of MC, the factor of nonlinearity of the procedure, and the factor of interaction between MC and nonlinearity. In addition, bounds for the Polyak-Ruppert averaging and the Richardson Romberg procedure are given.", "questions": "Could you please comment on the fact that there is no dependence between stepsize and number of iterates in the Polyak Ruppert avaraging?", "limitations": "-", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Decomposition that characterizes the bias with explicit dependence on MC, non-linearity and interactions between MC and non-linearity.", "weaknesses": "It would be good to obtain:\n- high probability bounds instead of the MSE\n- remove additional projection step and assumption on the density (it could be useful to consider convergence in the weighted W distance instead of V norm)\n-  explicit dependence on the asymptotic variance of MC in the $O(\\tau/(k - k_0))$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below. In what follows, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references, with bibliographic information given at the end of this response.\n\n**Comment: High probability bounds instead of MSE.**\n\nWe are grateful to the reviewer for this suggestion. We believe that we can derive high probability bounds by applying the Markov inequality to our Proposition 4.2 (convergence of $E\\|\\theta_k-\\theta^*\\|^{2p}$). Our bias characterization allows these bounds to be further tightened. If one would like to prove exponential tail bounds, stronger assumptions on the noise sequence, such as having exponential tails, are necessary as shown in [a] for iid data.\n\n**Comment: Discussion on projection and Assumption 5 on minorization.**\n\nWe address this comment in the **global rebuttal**, as it is an important point. \n\n**Comment: Discussion on explicit dependence on variance of Markov chain.**\n\nWe thank the reviewer for raising this point. We believe that it is straightforward to extend our results to characterize the dependence on the variance of the Markovian noise in the second moment of Polyak-Ruppert (PR) averaged iterates. We conjecture that by quantifying the variance introduced by the Markovian noise under an additional assumption that $\\|g(\\theta,x)-g(\\theta,y)\\|\\leq \\sigma_d$ for any $x,y\\in\\mathcal{X}$ and $\\theta\\in R^d$ (similar assumption in [46]), the explicit dependence of $\\sigma$ would be $O(\\sigma_d^2\\tau_\\alpha/(k-k_0))$.\n\n**Comment: Discussion on dependence between stepsize and number of iterates.**\n\nWe thank the reviewer for bringing up this question. Our result allows for independent choices of stepsize $\\alpha$ and the number of iterates $k$, provided that $\\alpha$ is sufficiently small and $k$ sufficiently large. The first two terms of the second moment bound of the PR averaged iterates do not depend on the number of iterates, which verifies the presence of asymptotic bias with a leading term proportional to the stepsize $\\alpha$. The remaining two terms depend on the number of iterates and will vanish as the number of iterates increases $k\\to\\infty$. The third term corresponds to the asymptotic variance and decays at the rate of $1/k$, and the fourth term corresponds to the optimization error. Our result also allows for optimizing the stepsize $\\alpha$ if the number of iterates $k$ is known a priori. Suppose $k$ is fixed and $k_0=k/2$, the optimized $\\alpha$ is obtained by balancing the first $\\alpha^2$ term and the last $(1-\\alpha\\mu)^{k_0/2}/(\\alpha (k-k_0)^2)$ term. The optimized order is $\\alpha = O(k^{-2/3})$, which matches the order in [46], and, to the best of our knowledge, provides the tightest dependence for Markovian linear SA with constant stepsize. We would appreciate it if the reviewer could clarify any remaining questions to ensure our response fully addresses the question on the dependence between stepsize $\\alpha$ and the number of iterates $k$ in the PR-averaging bound.\n\nReferences:\n\n[a] I. Merad and S. Gaïffas. Convergence and concentration properties of constant step-size SGD through Markov chains. 2023.", "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": "dgUtleCIWS", "reviewer": "Reviewer_gRG8", "summary": "The present paper obtains a representation for the asymptotic bias of constant step-size nonlinear stochastic approximation with Markovian noise. In particular, this characterization makes the hindering effect of memory and nonlinearity explicit in terms of the algorithm's performance. Moreover, the authors establish ergodicity of the parameter-noise joint process (with and without projection of estimates), obtain finite-time bounds on L_p moments of the estimation error and establish a central limit theorem for the constant gain algorithm. Finally, a bias attenuation technique based upon the Richardson-Romberg extrapolation is proposed for the nonlinear algorithm.", "questions": "-\tCould the authors clarify if assuming strong monotonicity and uniform boundedness of g and its Lipschitz constant over x are indeed needed for the result in Thm. 4.6? I can see their importance for finite-time bounds, but if there are needed for the asymptotic bias bound, I believe that the authors should mention the employment of stronger assumptions when comparing their work with previous research on asymptotic results.\n\n-\tI am not sure I understand what the authors mean by ``fine-grained’’  when talking about the result in Thm. 4.6. Upon further inspection, it seems that equation (4.2) is an extension of the result in [40] for nonlinear recursions: it consists a representation for the dominant bias term plus an upper bound as in this previous work. Is the fine-grained part related to the upper bound for \\alpha?\n\n-\tI might have missed this in the text, but could the authors clarify if the results in Sections 4.3 and 4.5 require projection?", "limitations": "The authors addressed the limitations in their work through a clear list of assumptions and discussions after presenting the main results.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The contributions and assumptions are clearly identified. To the best of the reviewer's knowledge, the results are novel and exciting: it is great to see the hindering effect caused by the interplay between memory and nonlinearity in SA.\n\nThis paper is well written, but could use some polishing. \n\nI did not have enough time to review all proofs in detail, but the analysis seems correct.", "weaknesses": "One of the weaknesses of this paper is the fact that no numerical experiments are provided to illustrate any of the main results. Although a discussion on how the theory fits within Generalized Linear Models is given before the conclusions, I encourage the authors to include a simple toy example to illustrate some of their main results such as the CLT or the bias attenuation technique.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below. In the following, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references, with bibliographic information given at the end of this reply.\n\n**Comment: numerical experiments.**\n\nWe thank the reviewer for the suggestion. We include numerical experiments in the **global rebuttal** to demonstrate our results. In particular, we conducted two sets of experiments using $L_2$-regularized logistic regression with Markovian data to verify our theoretical results: the existence of bias and its attenuation via Richardson-Romberg (RR) extrapolation, and the central limit theorem (CLT) of Polyak-Ruppert (PR) averaged iterates. Using $L_2$-regularized logistic regression in the experiment also demonstrates the practicality of our results in the context of generalized linear models (GLMs). We will add the numerical experiments in the revised paper.\n\n\n**Comment: Clarification of Assumption 3 (boundedness and smoothness of $g$) and Assumption 4 (strong monotonicity) for Theorem 4.6.**\n\nWe thank the reviewer for raising this point. For discussions on strong convexity and Lipschitz smoothness in proving weak convergence, we refer the reviewer to the global rebuttal. Here, we discuss the role of these two assumptions in bias characterization.\n\nThe key technique in bias characterization is Taylor expansion around $\\theta^\\ast$. The strong monotonicity and Lipschitz smoothness together ensures that $E\\|\\theta_\\infty-\\theta^*\\|^{2p}$ is of order $O((\\alpha\\tau)^p)$, which subsequently controls the order of the residual term in Taylor expansion. Moreover, the algebraic manipulation in bias characterization involves the inversion of $\\bar{g}'(\\theta^*)$ (in the context of SGD, this is equivalent to the Hessian of the objective function). Therefore, the strong monotonicity (convexity) ensures the validity of this inversion.\n\nWe believe that we could potentially relax the strong monotonicity assumption to Hurwitz $\\bar{g}'(\\theta^\\ast)$ to ensure the validity of such a matrix inversion. It is unclear what our approach would imply if we only have a positive semi-definite (not full-rank) $\\bar{g}'(\\theta^*)$. We conjecture that the joint process would still converge, but the bias may exhibit drastically different behaviors that we do not yet fully understand. This conjecture is based on [a], where the SA update is strongly convex and Lipschitz-smooth but non-differentiable at $\\theta^*$. [a] shows that the bias admits a very different behavior, with the leading term scaling with $\\sqrt{\\alpha}$ instead of $\\alpha$. Therefore, we currently do not have a clear conjecture for this case without the strong monotonicity assumption at $\\theta^*$.\n\n\n**Comment: \"Fine-grained\" characterization of bias in Theorem 4.6.**\n\nWe clarify how our bias characterization (4.2) -- (4.5) in Theorem 4.6 differs from the result (8) in [40]. We first remark that characterization in [40] is an \\textbf{upper bound} ($\\limsup$) on the averaged iterate's bias, not the asymptotic bias of the limiting random variable $E[\\theta_\\infty]-\\theta^*$, since [40] does not prove weak convergence for general SA. Additionally, the result in [40] only shows that the leading term of bias is of $\\alpha$-order. In contrast, we provide a closed-form expression in (4.2) -- (4.5) for the leading term of bias, which is computable if the underlying Markovian noise is known or can be approximated. Moreover, we show that the leading term can be decomposed into three components: Markovian noise $b_m$, non-linearity $b_n$, and the compound effect $b_c$, which cannot be implied from [40]. Therefore, our result is a more \"fine-grained\" characterization.\n\n\n**Comment: Clarification on projection for results in Section 4.3/4.5.**\n\nWe thank the reviewer for raising this point. The results in Section 4.3 (non-asymptotic result) and 4.5 (CLT), as well as 4.4 (asymptotic bias characterization), are follow-up results to the weak convergence results in Sections 4.1 and 4.2 (weak convergence with or without projection). In obtaining these follow-up results, projection for uniform boundedness of iterates $\\theta_t$ is not required. If we have weak convergence without projection, these results subsequently do not require projection. For discussions on removing the projection and minorization noise assumption, please refer to the **global rebuttal**.\n\nReferences:\n\n[a] Y. Zhang, D. L. Huo, Y. Chen, Q. Xie. Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA. 2024.", "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": "2zLPNn2YNV", "reviewer": "Reviewer_9yxV", "summary": "This paper studies constant step-size stochastic approximation algorithms with Markovian noise. It is known that in this case, the error of a stochastic does not vanish asymptotically, even when consider averaging. This is \\theta_n has a bias.  Previous work have show how to study the bias of such algorithm for linear stochastic approximation. In this paper, the authors tackle the more challenging case of non-linear stochastic approximation. Most of the paper is devoted to proving that the bias is of order O(\\alpha). Some discussion on the applicability of results is presented.", "questions": "There are some questions / comments in the limit that would deserve some comments from the authors.\n\nThe Markovian noise (x_k) is assumed exogeneous (it does not depend on \\theta). For some application (like Q-learning with a navigating policy derived from \\theta), this would not be satisfied. Could this assumption be lifted?\n\nThe next order term is a O(\\alpha^{3/2}): is it the sharpest bound or could O(\\alpha^2) be obtained?", "limitations": "The limitation of the assumptions (see \"weaknesses\") should be better discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a characterization of the bias under the challenging setting of Markovian noise plus non-linear drifts.\n\nThe analysis is asymptotically tight as the step size \\alpha converges to 0, i.e., the expression for the bias is not a bound but an equality plus smaller order terms.\n\nThe implications of the results are discussed.", "weaknesses": "Most of the assumptions needed to obtain the results are relatively mild but two conditions are quite strong:\n1. strong monotonicity (A3)\n2. Smoothness (A2)\nI think that the paper should discuss in more details these assumption and highlight that they are really limiting the applicability of the result.\n\nThe assumption developed in part 4.2 to avoid assuming that the iterates are bounded seems quite strong, not verified in many practical cases (for instance any instance of stochastic gradient descent where the noise has a finite support would not satisfy this assumption), and very artificial (is the only purpose of this assumption to\n\nThe paper is extremely long (54 pages including proofs and references). To me, this says that there is either too much content or that the results are too diluted. As a result, the paper is very technical and hard to read. There should be more effort to make the paper more readable. Some suggestions:\n- consider a slightly less general setting\n- avoid considering sub-cases (like section 4.2) that are a bit orthogoal to the paper\n\nThe practical applications of the results are unclear. Some potential applications are presented in Section 4.5 / 4.6 but there are no experiments or simulations to confirm that this actually work (these sections are interesting, though).\n\nThere is a lot of papers on the subject. This can be seen as a good sign (this is an active area of research), but at the same time, it is hard for me to really assess the novelty of the results. Note that there are some (recent) papers that seem related to these work and that might be cited. This last point is not a weakness since some of them are extremely recent (available online after the submission deadline):\n- Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise. S Allmeier, N Gast (2024)\n- Bias in Stochastic Approximation Cannot Be Eliminated With Averaging, Caio Kalil Lauand, Sean P. Meyn (2022)\n- Revisiting Step-Size Assumptions in Stochastic Approximation. Caio Kalil Lauand, Sean Meyn (2024)\nA comparison with these papers might be useful (even of this is not mandatory for the two 2024 papers).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the strengths and contribution of our paper, and for the constructive comments. Below we provide our responses to the comments. In the following, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc.\nfor new references, with bibliographic information given at the end of this reply.\n\n**Comment: Discussion on the limitation of Assumption 2 (smoothness) and Assumption 3 (strong convexity/monotonicity).**\n\nWe thank the reviewer for raising this point. We refer the reviewer to the **global rebuttal** for additional discussion on the smoothness and strong convexity/monotonicity assumptions. \n\n**Comment: Discussion on Assumption 5 on noise minorization.**\n\nWe address this comment in the **global rebuttal**, as it is an important point. \n\n**Comment: paper structure and presentation**\n\nWe thank the reviewer for their feedback on the paper's structure. We will incorporate the suggestions in the revision to make our paper more succinct. \n\n**Comment: practical application and numerical experiments.**\n\nWe thank the reviewer for the constructive comment. We briefly remark on the practical application of our results. As discussed in Section 4.6, many GLMs satisfy the conditions of our results. Our theory suggests that by running SGD with two stepsizes in parallel and tracking the PR-averaged iterates for each, we can use RR-extrapolation to obtain a reduced-bias estimate. Additionally, we can construct confidence intervals under our CLT guarantee.\n\nWe also include numerical experiments in the **global rebuttal** to demonstrate our results. Specifically, we performed a set of experiments with $L_2$-regularized logistic regression with Markovian data to support our theoretical findings: the presence of bias and its reduction through Richardson-Romberg (RR) extrapolation, as well as the central limit theorem (CLT) of Polyak-Ruppert (PR) averaged iterates. Employing $L_2$-regularized logistic regression in these experiments also showcases the practical applicability of our results within the scope of generalized linear models (GLMs). We will add the numerical experiments in the revised paper.\n\n\n**Comment: Additional reference.**\n\nWe thank the reviewer for pointing out the additional related works. All three works examine general (non-linear) SA under Markovian noise with a constant stepsize. Both [b] and our work prove weak convergence, but with different techniques. [b] provides an **upper bound** for the asymptotic bias, while we offer an equality and closed-form solution for the leading-order bias. [a] presents an upper bound for the PR-averaged iterates and, similar to our results, demonstrates the effectiveness of RR-extrapolation in reducing bias. Besides constant stepsize, [c] also explores diminishing stepsizes and examines the impact of the stepsize decay rate on the asymptotic statistics of PR-averaged SA. We will discuss these related works in our revised literature review.\n\n**Comment: Assumption on exogenous Markovian noise.**\n\nWe acknowledge that our current model of Markovian noise does not account for dependence on $\\theta$. In fact, the very recent work (pointed out by the reviewer) [a] considers the Markovian model that incorporates such dependence. We are confident that our work can be extended to adopt a similar modeling approach for the Markovian noise and achieve comparable results. \n\n**Comment: Tighter higher order in the bias.**\n\nWe agree with the reviewer's comment that $O(\\alpha^{3/2})$ might not be the tightest next order in the bias characterization, and we believe that $O(\\alpha^2)$ can be obtained. Improving the next highest order to $O(\\alpha^2)$ requires a more refined characterization of the asymptotic second order $E[(\\theta_\\infty-\\theta^*)^{\\otimes2}]$ by following a similar strategy as our current approach. Thus, we leave this refinement out of the scope of the current paper. We conjecture that, with appropriate assumptions on smoothness and noise moment, we can prove refined characterizations of higher orders of $E[(\\theta_\\infty-\\theta^*)^{\\otimes p}]$, and subsequently we obtain $E[\\theta_\\infty]=\\theta^*+\\sum_{n=1}^m\\alpha^nb_n+O(\\alpha^{n+1})$.\n\n\n\nReferences:\n\n[a] S. Allmeier and N. Gast. Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise. 2024.\n\n[b] C. K. Lauand and S. Meyn. Bias in Stochastic Approximation Cannot Be Eliminated With Averaging. 2022.\n\n[c] C. K. Lauand and S. Meyn. Revisiting Step-Size Assumptions in Stochastic Approximation. 2024.", "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 all reviewers for their insightful feedback. In this global rebuttal, we discuss smoothness, strong monotonicity, the use of projection, and the minorization assumption of the noise sequence. We also supplement our theoretical results with a set of numerical experiments, with results in the one-page PDF.

In what follows, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references with bibliographic information given at the end of this response.

**Differentiability and strong monotonicity:** In proving weak convergence, we assume that the stochastic approximation (SA) update operator $g$ is sufficiently smooth (three-times differentiable) and strongly monotone (for SGD this implies strong convexity of the objective function). This ensures controlled evolution of the iterates with Markovian/correlated data. The differentiability supports a Taylor series expansion of $g$ up to the second order with a bounded remainder, crucial for analyzing the $\spadesuit$ term in the convergence proof in Section 3 and for bias characterization where Taylor expansion around $\theta^\ast$ is the key technique. Some form of differentiability assumption is standard in SA literature, such as [18,40,a], particularly when one seeks a fine-grained characterization of the iterates' distributional property beyond MSE bounds. Such an assumption is satisfied by many GLMs, such as logistic regression and Poisson regression. When $g$ is not differentiable, SA behavior can differ significantly (even with iid data) [g], which is beyond our scope.

The strong monotonicity assumption is common in SA literature. Together with smoothness, it allows us to establish geometric distributional convergence. While some GLMs by themselves do not satisfy this condition, applying $L_2$-regularization (equivalently, weight decay) ensures strong convexity and improves statistical performance. It is a standard calculation that one can appropriately choose the regularization parameter to derive tight results for non-strongly-convex functions.
We believe that it is possible to relax the strong monotonicity assumption to weaker conditions, Hurwitz $\bar{g}'(\theta^\ast)$ [a,40], or even to non-convex problems satisfying structural properties like dissipativity or generalized Polyak-Lojasiewicz (PL) inequality [60]. 

**Projection and minorization:** Projection steps have a longstanding presence in SA literature for tractability in convergence theory, as seen in many analyses of SGD [b,c,d,e,5]. Although not an algorithmic proposal, this additional projection step does not incur much computational cost in practice, as it only involves rescaling the iterates, and the projection radius can be estimated a priori. Before our work, no studies had proven weak convergence for non-linear SA with Markovian data and constant stepsize, with or without the projection. Thus, our result is valuable, as it is the first to prove detailed weak convergence in this setting.

In Theorem 4.3, we provide an alternative proof of weak convergence using the Drift and Minorization technique, which does not require a projection. We acknowledge that the minorization assumption is not satisfied by some noise models, but argue that it is easily met by adding a small noise with a continuous distribution, a common practice for promoting exploration and privacy. 

In addition, it is possible to extend our current results and prove weak convergence without the minorization noise or the projection. This can be achieved by employing the established Drift and Contraction technique [f]. As discussed in Section 3, when $\|\theta_{k-\tau}^{[1]}-\theta^*\|^2+\|\theta_{k-\tau}^{[2]}-\theta^\ast\|^2$ is too large, obtaining a contraction in $E\|\theta_k^{[1]}-\theta_k^{[2]}\|^2$ may not be feasible. In this case, the drift and contraction technique suggests using the drift of $E\|\theta_k-\theta^*\|^2$ in Proposition 4.2 to carefully balance the distance $E\|\theta_k^{[1]}-\theta_k^{[2]}\|^2\lesssim (E\|\theta_k^{[1]}-\theta_k^{[2]}\|^2)^r(E\|\theta_k^{[1]}-\theta^*\|^2+E\|\theta_k^{[2]}-\theta^*\|^2)^{1-r}$ and obtain a contraction.

**Numerical experiments:** We run SGD on $L_2$-regularized logistic regression with constant step sizes, without projection. Figure 1 confirms the Central Limit Theorem (CLT) result for averaged iterates. Figure 2(a) verifies the presence of an asymptotic bias approximately proportional to the stepsize $\alpha$, and illustrates the effectiveness of Richardson-Romberg (RR) extrapolation in reducing this bias. We also compare the bias under Markovian data ($x_{t+1}\sim P(\cdot|x_t)$) and iid data ($x_t\sim\pi$) in Figure 2(b). Interestingly, Figure 2(b) reveals that Markovian data does not necessarily lead to a larger bias than iid data. This is consistent with our theory, as the three bias terms $b_m,b_n,b_c$ may have opposite signs leading to cancellation. This result suggests that in the presence of nonlinearity, one should not avoid Markovian data simply for the sake of reducing bias. Rather, RR extrapolation may be more effective for bias reduction.


References:

[a] S. Allmeier and N. Gast. Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise. 2024.

[b] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust Stochastic Approximation Approach to Stochastic Programming. 2009.

[c] H. Kushner. Stochastic approximation: a survey. 2010.

[d] S. Lacoste-Julien, M. Schmidt, and F. Bach. A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient. 2012.

[e] S. Bubeck. Convex Optimization: Algorithms and Complexity. 2015.

[f] Q. Qin and J. P. Hobert. Geometric convergence bounds for Markov chains in Wasserstein distance based on generalized drift and contraction conditions. 2022.

[g] Y. Zhang, D. L. Huo, Y. Chen, Q. Xie. Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA. 2024.

Meta-review: The reviewers were in unanimous agreement that the paper solves a challenging problem caused by Markovian data and nonlinear updates. Also the interplay between memory and nonlinearity in stochastic approximations is particularly striking and good for the community to know. A clear accept.
Decision: Accept (spotlight)