Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks
Authors: Jie Hu
Vishwaraj Doshi
Do Young Eun
Venue: ICLR 2024 oral (2024)
Keywords: Distributed Learning
Self-Repellent Random Walk
Token Algorithm
Central Limit Theorem
Asymptotic Analysis
Primary area: optimization
TL;DR: In distributed learning, we present SA-SRRW algorithm to prioritize lesser-visited nodes while discouraging frequently visited nodes in distributed learning, and show its performance improvement.

Abstract: We study a family of distributed stochastic optimization algorithms where gradients are sampled by a token traversing a network of agents in random-walk fashion. Typically, these random-walks are chosen to be Markov chains that asymptotically sample from a desired target distribution, and play a critical role in the convergence of the optimization iterates. In this paper, we take a novel approach by replacing the standard *linear* Markovian token by one which follows a *non-linear* Markov chain - namely the Self-Repellent Radom Walk (SRRW). Defined for any given 'base' Markov chain, the SRRW, parameterized by a positive scalar $\\alpha$, is less likely to transition to states that were highly visited in the past, thus the name. In the context of MCMC sampling on a graph, a recent breakthrough in Doshi et al. (2023) shows that the SRRW achieves $O(1/\\alpha)$ decrease in the asymptotic variance for sampling. We propose the use of a `generalized' version of the SRRW to drive token algorithms for distributed stochastic optimization in the form of stochastic approximation, termed SA-SRRW. We prove that the optimization iterate errors of the resulting SA-SRRW converge to zero almost surely and prove a central limit theorem, deriving the explicit form of the resulting asymptotic covariance matrix corresponding to iterate errors. This asymptotic covariance is always smaller than that of an algorithm driven by the base Markov chain and decreases at rate $O(1/\\alpha^2)$ - the performance benefit of using SRRW thereby *amplified* in the stochastic optimization context. Empirical results support our theoretical findings.

Published as a conference paper at ICLR 2024
ACCELERATING DISTRIBUTED STOCHASTIC OPTI- MIZATION VIA SELF-REPELLENT RANDOM WALKS
Jie Hu'!, Vishwaraj Doshi Do Young Eun' North Carolina State University. "IQVIA Inc.
(jhu29, dyeun) vishwaraj www.dooshhhhgoo wwwhi@iiii....ccooooooo
ABSTRACT
We study a family of distributed stochastic optimization algorithms where gradi- ents are sampled by token traversing network of agents in random-walk fash- ion. Typically, these random-walks are chosen to be Markov chains that asymp- totically sample from desired target distribution, and play critical role in the convergence of the optimization iterates. In this paper, we take a novel approach by replacing the standard linear Markovian token by which follows non- linear Markov chain - namely the Self- Repellett Radom Walk (SRRW). Defined for any given 'base' Markov chain, the SRRW, parameterized by positive scalar or is less likely to transition to states that were highly visited in the past, thus the name. In the context of MCMC sampling on graph, recent breakthrough in Doshi et al. (2023) shows that the SRRW achieves ((1/a) decrease in the asymp- totic variance for sampling. We propose the use of 'ggneralizedd version of the SRRW to drive token algorithms for distributed stochastic optimization in the form of stochastic approximation, termed SA-SRRW. We prove that the optimization it- erate errors of the resulting SA-SRRW converge to zero almost surely and prove central limit theorem, deriving the explicit form the resulting asymptotic covari- ance matrix corresponding iterate errors. This asymptotic covariance is always smaller than that of an algorithm driven by the base Markov chain and decreases at rate O(1/a² @²²) the performance benefit of using SRRW thereby amplified in the stochastic optimization context. Empirical results support our theoretical findings.
INTRODUCTION
Stochastic optimization algorithms solve optimization problems of the form
0" E arg min f(0), where f(O) Ex-=
Σ VEN
En.F(O, (,F(O,
(I)
OER
with the objective function f Rd IR and X taking values in a finite state space / with distri- bution μ - ju]uEN. Leveraging partial gradient information per iteration, these algorithms have been recognized for their scalability and efficiency with large datasets (Bottou et al., 2018; Even, 2023). For any given noise sequence (X,))20 N,, and step size sequence (3²) [ C RR., most stochastic optimization algorithms can be classified as stochastic approximations (SA) of the form
0n+1 = + ( Xn+1), Vn 2 O,
(2)
where, roughly speaking, H(O,i) i) contains gradient information VeP(O, i). such that 0- solves h(0) A (H stochastic gradient descent (SGD), stochastic heavy ball (SHB) (Gadat et al., 2018; Li et al., 2022), and some SGD-type algorithms employing additional auxiliary variables (Barakat et al., 2021).² These algorithms typically have the stochastic noise term X, generated by i.i.d. random variables with probability distribution μ in each iteration. In this paper, we study a stochastic optimization algorithm where the noise sequence governing access to the gradient information is generated from general stochastic processes in place of i.i.d. random variables.
ENEN (0, i) 0. Such SA iterations include the well-known
"qqual contributors.
Further illustrations of stochastic optimization algorithms of the form (2) are deferred Appendix A.

---

Published as a conference paper at ICLR 2024
This is commonly the case in distributed learning, where {X,] is (typically Markovian) random walk, and should asymptotically be able to sample the gradients from the desired probability dis- tribution μa. This is equivalent to saying that the random walker's 's empirical distribution converges to 1a almost surely (a.s.); that is, Xn nt
n+T -k= 6x
I for any initial Xo E N,, where n-000
a.s.
ôx is the delta measure whose X5 'tt entry is one, the rest being zero Such convergence is most commonly achieved by employing the Metropolis Hastings random walk (MHRW) which can be designed to sample from any targer measure μ and implemented in scalable manner (Sun al., 2018). Unsurprisingly, convergence characteristics of the employed Markov chain affect that of the SA sequence (2), and appear in both finite-time and asymptotic analyses. Finite-time bounds typ- ically involve the second largest eigenvalue in modulus (SLEM) of the Markov chain's 's transition kernel P. which is critically connected to the mixing time of a Markov chain (Levin & Peres, 2017); whereas asymptotic results such as central limit theorems (CLT) involve asymptotic covariance ma- trices that embed information regarding the entire spectrum of P, i.e., all eigenvalues as well as eigenvectors (Brémaud, 2013), which are key to understanding the sampling efficiency of a Markov chain. Thus, the choice of random walker can significantly impact the performance of (2), and sim- ply ensuring that it samples from l asymptotically is not enough to achieve optimal algorithmic performance. In this paper, we take a closer look at the distributed stochastic optimization problem through the lens of a non-linear Markov chain, known the Self Repellent Random Walk (SRRW), which was shown in Doshi et al. (2023) to achieve asymptotically minimal sampling variance for large values of a, positive scalar controlling the strength of the random walker's i self-repellence behaviour. Our proposed modification of (2) can be implemented within the settings of decentral- ized learning applications in scalable manner, while also enjoying significant performance benefit over distributed stochastic optimization algorithms driven by vanilla Markov chains.
Token Algorithms for Decentralized Learning. In decentralized learning, agents like smartphones or IoT devices, each containing a subset of data, collaboratively train models on a graph (VV E) by sharing information locally without a central server (McMahan et al., 2017). In this setup, N M agents correspond to nodes E EN, and an edge (i. E & indicates direct communication between agents and j. This decentralized approach offers several advantages compared to the traditional centralized learning setting, promoting data privacy and security by eliminating the need for raw data to be aggregated centrally and thus reducing the risk of data breach or misuse (Bottou et al., 2018; Nedic, 2020). Additionally, decentralized approaches are more scalable and can handle vast amounts of heterogeneous data from distributed agents without overwhelming a central server, alleviating concerns about single point of failure (Vogels et al., 2021).
Among decentralized learning approaches, the class of 'Token' algorithms can be expressed as stochastic approximation iterations of the type (2), wherein the sequence {X,) is realized as the sample path of a token that stochastically traverses the graph G, carrying with it the iterate 6, for any
time n 2 0 and allowing each visited node (agent) to incrementally update O,, using locally available gradient information. Token algorithms have gained popularity in recent years (Hu et al., 2022; Tri- asteyn et al., 2022; Hendrikx, 2023), and are provably more communication efficient (Even, 2023) when compared to consensus- bansen algorithms- another popular approach for solving distributed optimization problems (Boyd et al., 2006: Morral et al., 2017; Olshevsky, 2022). The construction of token algorithms means that they do not suffer from expensive costs of synchronization and com- munication that are typical of consensus-hee based approaches, where all agents (or a subset of agents selected by coordinator (Boyd et al., 2006; Wang et al., 2019)) on the graph are required to take simultaneous actions, such as communicating on the graph at each iteration. While decentralized Federated learning has indeed helped mitigate the communication overhead by processing multiple SGD iterations prior to each aggregation (Lalitha et al., 2018; Ye et al., 2022; Chellapandi et al., 2023), they still cannot overcome challenges such as synchronization and straggler issues.
Self Repellent Random Walk, As mentioned earlier, sample paths (Xa) of token algorithms are usually generated using Markov chains with l Int(E) E) as their limiting distribution. Here, Σ denotes the N N-dimensional probability simplex, with Int(E)) representing its interior. A recent work by Doshi et al. (2023) pioneers the use of non-lineat Markov chains to, in some sense, improve upon any given time-reversible Markov chain with transition kernel P whose stationary distribution is μ.
2

---

Published as a conference paper at ICLR 2024
They show that the non-linear transition kernel K[+ Int + [0. 1
given by
p1)(
Kij [x] A
Vi.jEN
(3)
EKen Pulla//us)
for any E Int(E), when simulated as self-interacting random walk (Del Moral & Miclo, 2006; Del Moral & Doucet, 2010), can achieve smaller asymptotic variance than the base Markov chain when sampling over graph G, for all a O. The argument x for the kernel K [axx is taken to be the empirical distribution X, at each time step n 2 O. For instance, if node j has been visited more often than other nodes far, the entry x; becomes larger (than target value Uz)), resulting in a smaller transition probability from i to under K[x] in (3) compared to P.y. This ensures that random walker prioritizes more seldom visited nodes in the process, and is thus "self-repellent. This effect is made more drastic by increasing o, and leads to asymptotically near-zero variance at a rate of O(1/a). Moreover, the polynomial function (z:/u4) chosen to encode self- self-repellent behaviour is shown in Doshi et al. (2023) to be the only one that allows the SRRW to inherit the so- called scale-invariance" property of the underlying Markov chain - a necessary component for the scalable implementation of random walker over large network without requiring knowledge of any graph-related global constants. Conclusively, such attributes render SRRW especially suitable for distributed optimization.
Effeet of Stochastic Noise Finite time and Asymptotic Approaches. Most contemporary token algorithms driven by Markov chains are analyzed using the finite-time bounds approach for obtain- ing insights into their convergence rates (Sun et al., 2018; Doan et al., 2019; 2020; Triasteyn et al., 2022; Hendrikx, 2023). However, as also explained in Even (2023), in most cases these bounds are overly dependent on mixing time properties of the specific Markov chain employed therein. This makes them largely ineffective in capturing the exact contribution of the underlying random walk in manner which is qualitative enough to be used for algorithm design; and performance enhance- ments are typically achieved via application of techniques such as variance reduction (Defazio al., 2014; Schmidt et al., 2017), Comeenuum/Nestero 's acceleration (Gadat et al., 2018; Li et al., 2022), adaptive step size (Kingma & Ba, 2015; Reddi et al., 2018), which work by modifying the algorithm iterations themselves, and never consider potential improvements to the stochastic input itself.
Complement to finite-time approaches, asymptotic analysis using CLT has proven to be an excellent tool to approach the design of stochastic algorithms (Hu et al., 2022; Devraj & Meyn, 2017: Morral et al., 2017; Chen et al., 2020a; Mou et al., 2020; Devraj & Meyn, 2021). Hu ct al. (2022) shows how asymptotic analysis can be used to compare the performance of SGD algorithms for various stochastic inputs using their notion of efficiency ordering, and, as mentioned in Devraj & Meyn (2017), the asymptotic benefits from minimizing the limiting covariance matrix are known to be good predictor of finite-time algorithmic performance, also observed empirically in Section 4.
From the perspective of both finite-time analysis well asymptotic analysis of token algorithms, it is now well established that employing 'better' Markov chains can enhance the performance of stochastic optimization algorithm. For instance, Markov chains with smaller SLEMS yield tighter finite-time upper bounds (Sun et al., 2018; Ayache & El Rouayheb, 2021: Even, 2023). Similarly, Markov chains with smaller asymptotic variance for MCMC sampling tasks also provide better performance, resulting in smaller covariance matrix of SGD algorithms (Hu et al., 2022). Therefore, with these breakthrough results via SRRW achieving near-zero sampling variance, it is within reason to ask: Can achieve near-zero variance in distributed stochastic optimization driven by SRRW- like tokn algorithms on any general graph?* 24 In this paper, we answer in the affirmative.
SRRW Driven Algorithm and Analysis Approach. For any ergodic time-reversible Markov chain with transition probability matrix P [PyjlEJEN and stationary distribution la E Int(E), we con- sider a general step size version of the SRRW stochastic process analysed in Doshi et al. (2023) and
"Here non- lineariy in the transition kernel implies that K[x] takes probability distribution x as the argu- ment (Andrieu et al., 2007). as opposed to the kernel being a linear operator K xx P for constant stochastic matrix P in standard (linear) Markovian setting.
"Recently, Guo et al. (2020) introduce an optimization scheme, which designs self repelleeeeee into the per- turbation of the gradient descent iterates (Jin et al., 2017: 2018; 2021) with the goal of escaping saddle points. This notion of self-repellennce is distinct from the SRRW, which is prohability kernel designed specifically for a token to sample from target distribution ja over set of nodes on an arbitrary graph.
'This near-zero sampling variance implies significantly smaller variance than even an i.i.d. sampling counterpart, while adhering to graph topological constraints of token algorithms.
3

---

Published as a conference paper at ICLR 2024
Traditional MC, e.g. MHHRW
Nonlinear ISRRW (Doshi al. 2023]
Asymptotic Covariance a
Stochastic Optimization Algorithm
High Variance
Near-Zero Variance (Our Result)
Token's trajectory (X2)220
0x+1 8,
A A- (0, 0') - N(O,
Figure I: Visualization of token algorithms using SRRW versus traditional MC in distributed learn- ing. Our CLT analysis, extended from SRRW itself distributed stochastic approximation, leads to near-zero variance for the SA iteration On Node numbers on the left denote visit counts.
use it to drive the noise sequence in (2), Our SA-SRRW algorithm is as follows:
Draw: Xn+1 ~ Kx,, [x.]
(4a)
Update:
x,-1 x,, 7 xn):
(4b)
0ut1 = 0n + (
(4c)
where {Br} and (nn) are step size sequences decreasing to zero, and K[x] is the SRRW kernel in (3). Current non-asymptotie analyses require globally Lipschitz mean field function (Chen et al., 2020b; Doan, 2021; Zeng et al., 2021; Even, 2023) and is thus inapplicable to SA-SRRW since the mean field function of the SRRW iterates (4b) is only locally Lipschitz (details deferred to Appendix B). Instead, we successfully obtain non-trivial results by taking an asymptotic CL.T-based approach analyze (4). This goes beyond just analyzing the asymptotic sampling covariance as in Doshi et al. (2023), the result therein forming a special case of ours by setting "nn 1/nn+l/((///))) and considering only (4a) and (4b), that is, in the absence of optimization iteration (4c). Specifically, we capture the effect of SRRW's hyper-paramedt parameter a on the asymptotic speed of convergence of the optimization error term On,
zero via explicit deduction of its asymptotic covariance matrix. See Figure I for illustration.
Our Contributions.
1. Given any time-reversible 'base' Markov chain with transition kernel P and stationary distribution J., we generalize first and second order convergence results of x,, to target measure l (Theorems 4.1 and 4.2 in Doshi et al., 2023) to a class of weighted empirical measures, through the use of more general step sizes "/n This includes showing that the asymptotic sampling covariance terms decrease to zero at rate O(1/a), thus quantifying the effect of self self-repellent X,- Our generalization is not for the sake thereof and is shown in Section 3 to be crucial for the design step sizes Pn. Bn. Tn-
2. Building upon the convergence results for iterates x,, analyze the algorithm (4) driven by the SRRW kernel in (3) with step sizes 3n and "n separated into three disjoint cases:
(i) 3, = o(%)), ) and we say that On is on the slower timescale compared to X,:
(ii) 8, = Yn. and we say that 6, and x,, are on the same timescale;
(iii) 7n. o(3,), and say that On is faster timescale compared to X.-
For any a 2: 0 and let k 1,2 and 3 refer to the corresponding cases (i), (ii) and (iii), show that
0 and (0, 0B)/VBn dist. N (0, V (a)).
O
(a) featuring distinct asymptotic covariance matrices (a), v() and v-(2) (a), respectively. The three matrices coincide when 0.5. Moreover, the derivation of the CLT for cases (i) and (iii,, for which (4) corresponds to two-timescale SA with controlled Markov noise, is the first of its kind and thus key technical contribution in this paper, expanded upon in Section 3.
For case (i), we show that (-(1) (a) decreases to zero (in the sense of Loewner ordering introduced in Section 2.1) as a increases, with rate O(1/a²). This especially surprising, since the asymptotic performance benefit from using the SRRW kernel with in (3), to drive the noise terms X,,, is amplified in the context of distributed learning and estimating 0*: compared to the sampling case, for which the rate is O(1/a) as mentioned earlier. For case (iii), we show that (- (a) v-(² (0) for all 2 0, implying that using the SRRW in this case provides no asymptotic benefit than the
"Sampling covariance corresponds only the empirical distribution x, (4b).
'The case is equivalent to simply running the hase Markov chain, since from (3) we have K thus hypassing the SRRW's effect and rendering all three cases nearly the same.
4

---

Published as a conference paper at ICLR 2024
original base Markov chain, and thus performs worse than (i). In summary, deduce that v(ll (02) < V (01)< Vz) ( (0)= (0)=Va vV) (a) for all 02 > an > and a 0.?
0
4. We numerically simulate our SA-SRRW algorithm on various real-world datasets, focusing on a binary classification task, to evaluate its performance across all three cases. By carefully choos- ing the function H in SA-SRRW, we test the SGD and algorithms driven by SRRW. Our findings consistently highlight the superiority of case (i) over cases (ii) and (ii) for diverse a values, even in their finite time performance. Notably, our tests validate the variance reduction a rate of (1/a²² for case (i), suggesting as the best algorithmic choice among the three cases.
PRELIMINARIES AND MODEL SETUP
In Section 2.1, we first standardize the notations used throughout the paper, and define key mathe- matical terms and quantities used in our theoretical analyses. Then, in Section 2.2, we consolidate the model assumptions of our SA-SRRW algorithm (4). We then go on to discuss our assumptions, and provide additional interpretations of our use of generalized step-sizes.
2.1 BASIC NOTATIONS AND DEFINITIONS
Vectors are denoted by lower-case bold letters, c.g., v - [eg] E IR,, and matrices by upper-case bold, e.g., M & [My]] E DDD, M- T is the transpose of the matrix inverse M The diagonal matrix Dy formed by vector v with v; as the i'th diagonal entry. Let and O denote vectors of all ones and zeros, respectively. The identity matrix is represented by I, with subscripts indicating dimensions as needed. A matrix is Hurwitz if all its eigenvalues possess strictly negative real parts. 1 denotes indicator function with condition in parentheses. We use ||- to denote both the Euclidean norm of vectors and the spectral norm of matrices. Two symmetric matrices M1, M2 follow Loewner ordering M1 <, M, if M2 M1 is positive semi cemi-definite and M1 * M2. This slightly differs from the conventional definition with St., which allows M, M
Throughout the paper, the matrix A [Prckeee and vector μ & [ulleN are used exclusively to denote an N x N-dimensional transition kernel of an ergodic Markov chain, and its stationary distribution, respectively. Without loss of generality, we assume P.j > if and only if aij > 0. Markov chains satisfying the detailed balance equation, where JuPp; Pz for all i, E N, are termed time-reversible. For such chains, we use (Ac, u:) (resp. (Ai, v:)) to denote the i'th left (resp. right) eigenpair where the eigenvalues are ordered: <1< <...< AN-1 AN =1, with uN / and vN = in N We assume eigenvectors to be normalized such that u v, = 1 for all i, and we have u, u,= D;= and u. v, = 0 for all i, E.V We direct the reader to Aldous & Fill (2002, Chapter 3.4) for detailed exposition on spectral properties of reverseversible Markov chains.
2.2 SA-SRRW: KEY ASSUMPTIONS AND DISCUSSIONS
Assumptions:
All results in our paper are proved under the following assumptions. (A1) The function RDD x N - R.D, is a continuous at every E TR&P, and there exists a positive constant such that i)) < L(1 + [[]]) for every 0 RR, e N.
(A2) Step sizes 3n and 7n follow 3, 1n=+++1-- and 7/n = =n= where a, (0.5, 1].
(A3) Roots of function h(.) are disjoint, which comprise the globally attracting set θ A 0 (h(00)=0, Vh(O*) F(--11 I Hurwitz + of the associated ordinary differential equation (ODE) for iteration (4c), given by (A4) For any Xp. E Fº x Int(E) x N, the iterate sequence [n,)n2 (resp. fx,, hnzo) is Pec..o..x -almost surely contained within a compact subset of IRD (resp. Int()))).
2
Discussions on Assumptions: Assumption Al requires H to only be locally Lipschitz albeit with linear growth, and is less stringent than the globally Lipschitz assumption prevalent in optimization literature (Li & Wai, 2022; Hendrikx, 2023; Even, 2023).
In particular, this is the reason why we advocate for a more general step size 7n = (1++)) 1) in the SRRW iterates with < 1, allowing us to choose 8n, = (n+ 11 1)-h
with b E (a, 1] to satisfy (9, o(7h.) for case (i).
5

---

Published as a conference paper at ICLR 2024
Assumption A2 is the general umbrella assumption under which cases (i), (ii) and (iii) mentioned in Section 1 are extracted by setting: (i) a < b. (ii) a = b, and (iii) a > b. Cases (i) and (iii) render ,,. x, on different timescales; the polynomial form of B,, in widely assumed in the two- timescale SA literature (Mokkadem & Pelletier, 2006; Zeng et al., 2021; Hong et al., 2023). Case (ii) characterizes the SA-SRRW algorithm (4) as a single-timescale SA with polynomially decreasing step size, and is among the most common assumptions in the SA literature (Borkar, 2022; Fort, 2015; Li al., 2023). In all three cases, the form of 7/n ensures Tn S 1 such that the SRRW iterates X,, in (4b) is within Int(E), ensuring that K xx,] is well-defined for all n 2 O.
In Assumption A3, limiting dynamics of SA iterations [0x closely follow trajectories (0()) of their associated ODE, and assuming the existence of globally stable equilibria is stan- dard (Borkar, 2022; Fort, 2015; Li et al., 2023). In optimization problems, this is equivalent to assuming the existence of at most countably many local minima.
Assumption A4 assumes almost sure boundedness of iterates 0n and x,, which common as- sumption in SA algorithms (Kushner & Yin, 2003; Chen, 2006; Borkar, 2022; Karmakar & Bhatna- gar, 2018: Li et al., 2023) for the stability of the SA iterations by ensuring the well-definiteness of all quantities involved. Stability of the weighted empirical measure Xn of the SRRW process is prac- tically ensured by studying (4b) with a truncation- based procedure (see Doshi et al., 2023, Remark 4.5 and Appendix E for a comprehensive explanation), while that for 0, is usually ensured either as a by-product of the algorithm design, or via mechanisms such as projections onto a compact subset of TR depending on the application context. We now provide additional discussions regarding the step-size assumptions and their implications on the SRRW iteration (4b).
SRRW with General Step Size: As shown in Benaim & Cloez (2015, Remark 1.1), albeit for completely different non-linear Markov kernel driving the algorithm therein, iterates x, of (4b) can also be expressed as weighted empirical measures of {X,n I22nn in the following form:
X E wi x; + woxD
In
where Wg 1, and Wi I1 k1
(5)
Σ Wi
for all n > O. For the special case when in = 1/(n+1) as in Doshi et al. (2023), we have = 1 for all 2 0 and x,, is the typical, unweighted empirical measure. For the additional case considered Yn = em and This implies that wi will increase at sub-exponential rate, giving more weight to recent visit counts and allowing it to quickly 'forget' the poor initial measure Xg and shed the correlation with the initial choice of Xo. This 'speed up" effect by setting < is guaranteed in case (i) irrespective of the choice of in Assumption A2, and in Section 3 we show how this can lead to further reduction in covariance of optimization error 0₂ = 0* in the asymptotie regime.
in our paper, when a < 1 for Yn as in assumption A2, we can approximate on & n (1("n(""((10))))
Additional assumption for case (iii): Before moving on to Section 3, we take another look at the case when 7/.. = o(3r), and replace A3 with the following, stronger assumption only for case (iii).
(A3') For any E Int(E), there exists a function p Int(E) such that || S L2 [|x() for some L2 0, Ei- [H (p(x). :)] =0 and [V (p(x), i)] (b=1) I is Hurwitz.
While Assumption A3' for case (iii) is much stronger than A3, it is not detrimental to the overall results of our paper, since case (i) is of far greater interest as impressed upon in Section 1. This is discussed further in Appendix C.
3 ASYMPTOTIC ANALYSIS OF THE SA-SRRW ALGORITHM
In this section, we provide the main results for the SA-SRRW algorithm (4). We first present the a.s. convergence and the CLT result for SRRW with generalized step size, extending the results in Doshi et al. (2023). Building upon this, present the a.s. convergence and the CLT result for the SA iterate 0n, under different settings of step sizes. We then shift our focus to the analysis of the different asymptotic covariance matrices emerging out of the CLT result, and capture the effect of and the step sizes, particularly in cases (i) and (iii), on 0, 0 via performance ordering.
Almost Sure convergence and CLT: The following result establishes first and second order conver- gence of the sequence {x,, hnzo. which represents the weighted empirical measures of the SRRW process (X,)a20 based on the update rule in (4b).

---

Published as a conference paper at ICLR 2024
Lemma 3.1. Under Assumptions AI, A2 and A4, for the SRRW iterates (4b), we have
Xn
0....
and Yn T// (xx, (e) dist.
1/2
N(0, V (x))),
where Vx(a)= Σ
N-1
1
1+ X u,u
(6)
2a(1 X,) +2 1 (a=1)
X,
Moreover, for all 02 01 > O, we have Vx(oz) <1. Vx(an) <n. Vx(0).
Lemma 3.1 shows that the SRRW iterates X, converges to the target distribution la a.s. even under the general step size 7/n (n+1) -a for (0.5, 1]. We also observe that the asymptotic covariance matrix Vx (a) decreases at rate O11/a). Lemma 3.1 aligns with Doshi et al. (2023, Theorem 4.2 and Corollary 4.3) for the special case of a 1, and is therefore more general. Critically, helps us establish our next result regarding the first-order convergence for the optimization iterate sequence {0, J220 following update rule (4c), as well as its second-order convergence result, which follows shortly after. The proofs of Lemma 3.1 and our next result, Theorem 3.2, are deferred to Appendix D. In what follows, = 1,2, and 3 refer to cases (i). (ii) and (iii) in Section 2.2, respectively. All subsequent results are proven under Assumptions Al to A4, with A3' replacing A3 only when the step sizes 3ns Yu satisfy case (iii..
Theorem 3.2. For k {1, 2, 3}, and any initial (Oo. Xo. Xo) E R XIm((E))x) XN, we have O, + 0 as n + oc for some 0* E e, Fo,, aalmost surely.
In the stochastic optimization context, the above result ensures convergence of iterates 0n to a local minimizer 0¹ Loosely speaking, the first-order convergence of x,, in Lemma 3.1 as well as that of On are closely related to the convergence of trajectories (z(t) _ (0(t).x(t)) of the (coupled) mean-field ODE, written in a matrix- form as
(H(O ( [[(())] T(((()] - x(t) E EDDN
4 ( - g(((t)
where matrix H(0) A (H,,)), HOO, N))T E IR NxD for any A E TRD Here, π|x] E Int(E) the stationary distribution of the SRRW kernel K[x] and is shown in Doshi et al. (2023) to be given by π.[x] x EjeN MiEEMMPPis(ee (xP:((;://p) (x; (1///15)))) p1)) The Jacobian matrix of (7) when evaluated at equilibria zt (0", 11) for fr E Q captures the behaviour of solutions of the mean-field in their vicinity, and plays an important role in the asymptotic covariance matrices arising out of our CLT results. We evaluate this Jacobian matrix ((a function of a > 0 to be given by
Vh(0*) -H( ( (T_+TI+- I) A JI1 J12(a)
J(a) 2 Vg(z")=
(8)
ONXD
2ap1 (a-"""aaa+1)
J21
J22(a)
The derivation of (aa is referred to Appendix 1. Here, J21 is
matrix since π
is devoid of 0. While matrix (22(a) is exactly of the form in Doshi et al. (2023, Lemma 3.4) characterize the SRRW performance, our analysis includes additional matrix J (a), which captures the effect of x(t) on ((t in the ODE (7), which translates to the influence of our generalized SRRW empirical measure x,, on the SA iterates 6,, in (4).
For notational simplicity, and without loss of generality. all our remaining results are stated while conditioning on the event that (0, 0²), }. for some 0* E O. We also adopt the shorthand notation H to represent H.))). Our main CLT result is as follows, with its proof deferred to Appendix E.
Theorem 3.3. For any 2 0, we have: (a) There exists (k) (a) for all k E {1,2,3} such that
In 1/2 0 8-)
N (i))
1/2
Im Xnn 11)
(b) For k 2, matrix ( (a)) solves the Lyapunov equation (() + (()(
[1=11 ((2) -U, where the Jacobian matrix [a) is in (8), and
N
1+
HH (FuufFF H H. u.
Un U12
U
(9)
1-
nnn
U21
U22
For k E (1,3), (a) becomes block diagonal, which is given by
(()) = ( (a)
OpeN Vx(a))
(10)
ONXD
'The Jacohian J(o) is (D+N) DD+N)= dimensional, with Ju1 DRD and (22 NXN, Following this, all matrices written in block form, such matrix U in (9), will inherit the same dimensional structure.
7

---

Published as a conference paper at ICLR 2024
where Vx(a) as in (6), and V (a) and v000 (a) can be written in the following explicit form:
(a) = So e'(Voh(o") "1= DUo(a)e ((bm1) 1)2 dt,
v (a) = So e'Voh(O') " VneeVoh dt where Uo(a)
1 1+ H' H'u,HHH
(11)
aml (a(1+
1-
For & E [1,3), SA-SRRW in (4) is two-timescale SA with controlled Markov noise. While a few works study the CLT of two-timescale SA with the stochastic imput being a martingale-difterenee (i..d.) noise (Konda & Tsitsiklis, 2004; Mokkadem & Pelletier, 2006), CLT result covering the case of controlled Markov noise (e.g., E (1,3)), a far more general setting than martingale- difference noise, is still an open problem. Thus, here prove our CLT for & {1.3} from scratch by a series of careful decompositions of the Markovian noise, ultimately into a martingale-differen term and several non-vaninn non-vanishing noise terms through repeated application of the Poisson equation (Benveniste et al., 2012: Fort, 2015). Although the form of the resulting asymptotic covariance looks similar to that for the martingale-diffeet -ifffrreeee case in (Konda & Tsitsiklis, 2004; Mokkadem & Pelletier, 2006) at first glance, they are not equivalent. Specifically, v=* captures both the effect of SRRW hyper-parameter a, as well as that of the underlying base Markov chain via eigen- pairs (X;, u,) of its transition probability matrix P in matrix U, whereas the latter only covers the martingale-differennee noise terms as a special case.
When k= = 2, that is. 3n = Yoo algorithm (4) can be regarded as single-timescale SA algorithm. In this case, we utilize the CLT in Fort (2015, Theorem 2.1) to obtain the implicit form of V (a) as shown in Theorem 3.3. However, J (1)(a) being non-zero for > 0 restricts from obtaining an explicit form for the covariance term corresponding to SA iterate errors O,, 0" On the other hand, for k E (1,3), the nature of two-timescale structure causes O,, and x,, to become asymptoti- cally independent with zero correlation terms inside (k) (a) in (10), and we can explicitly deduce ((k)
e (ax). We now take a deeper dive into a and study its effect on (kk) (ax).
Covariance Ordering of SA-SRRW: We refer the reader Appendix F for proofs of all remaining results. We begin by focusing on case (i) and capturing the impact of a on V
( (a).
Proposition 3.4. For all 0g > a1 > O, we have ( (az) < (a)) < v v (0). Furthermore, ( (a) decreases to zero at a rate of ((1/a²).
Proposition 3.4 proves monotonic reduction (in terms of Loewner ordering) of (() (ax) as a in- creases. Moreover, the decrease rate ((1/a²) surpasses the O(1 (a)) rate seen in V Vx(a) and the sampling application in Doshi et al. (2023, Corollary 4.7), and is also empirically observed in our simulation in Section 4. Suppose we consider the same SA now driven by an i.i.d. sequence {X,, with the same marginal distribution ploying SRRW (walk on a graph) with large enough a on a general graph can actually produce better SA iterates with its asymptotic covariance going down to zero, than 'hypothetical situation' where the walker is able to access any node j with probability μt from anywhere in one step (more like a random jumper). This can be seen by noting that for large time n, the scaled MSE 0 -0 [|2)/ B,, is composed of the diagonal entries of the covariance matrix Ve. which, as we discuss in detail in Appendix F.2, are decreasing in a as a consequence of the Loewner ordering Proposition 3.4. For large enough a, the scaled MSE for SA-SRRW becomes smaller than its i.i.d. counterpart, which is always a constant. Although Doshi al. (2023) alluded this for sampling applications with Var)), we broaden its horizons to distributed optimization problem with Va(a) using tokens on graphs. Our subsequent result concerns the performance comparison between cases (i) and (iii).
Then, our Proposition 3.4 asserts that a token algorithm em-
Corollary 3.5. For any a > 0, we have vi! (a) < ((3)
(a) v-()( (0).
We show that case (i) is asymptotically better than case (iii) for > O. In view of Proposition 3.4 and Corollary 3.5, the advantages of case (i) become prominent.
Further insights of O(1/a²) are tied to the two- wo-timmsccaee structure, particularly 3. = o(%) ) in case (i), which places 0, on the slow timescale so that the correlation terms Ji2(a), (22()) in the Jacobian matrix J(a) in (8) come into play. Technical details referred to Appendix F.2, where show the form of (o)
8

---

Published as a conference paper at ICLR 2024
CASE (0) - O.8, D 0.9
CASE (i): = 0.8, 0.9
10
10"
0.0035
MSE points
NSE c 1'1
10.4
30
6.0025
0.0030
glz) +1.00p +.00003
curve
SE Of
MSC ElR
0.0015
0.000 0.0000
x-22
4-22
10-1
canoiing
campiigg
0.0005
10
10
10t
10 10
10
10 10"
10
0.0 25
7.5 10.0125511.1322 20.0
Number of steps (n)
Number of steps (n)
value of
(c) Curve fitting for MSE, Figure 2: Simulation results under case (i): (a) and (b) show the performance of SGD-SRRW and
(a) SGD-S
(b) SHB-SHSRR SRRW.
SHB-SRRW for various a values. (c) shows that MSE decreases O(1/a²) speed.
CASE I6a 2...0
CASe
8 P
10.4
CAST a0 C.S.
CASZ 1itta o.
MSE :1e, 1o--51
10-1
CAse (120=1.b
CASE 00.0000
10
CASE 34is-1o-08
CASE 30 55,p-00
M5E.10.-
MSE 10..
10:7
10
367
122
10P
10
10a
10a
10f
10
10
10
10'
101
10
10
Numbbe steps
Number of steps (n)
Number stotpp (n)
(a) a 1, SGD-SRRW
(b) a 5, SGD-SRRW
(c) a 10, SGD-SRRW
Figure 3: Comparison of the performance among cases (i) (iii) for {1)..
4 SIMULATION
In this section, we simulate our SA-SRRW algorithm on the Wiki graph (Leskovec & Krevl, 2014), comprising 889 nodes and 2914 edges. We configure the SRRW's base Markov chain P as the MHRW with a uniform target distribution la = & 1. For distributed optimization, we consider
the following Le regularized binary classification problem:
mingEro {S()) & A E log [1 + 11+=00x)) yi (0 + 1101)
(12)
where {ss y:) is the ijennl dataset (with 22 features, i.e., s; E ?22 from LIBSVM (Chang & Lin, 2011), 1), and penalty parameter K 1. Each node in the Wiki graph is assigned one data point, thus 889 data points in total. We perform SRRW driven SGD (SGD-SRRW) and SRRW driven stochastic heavy ball SHH-SRRY
algorithms (see (13) in Appendix A for its algorithm).
We fix the step size 3, = (n + 1)-0.3 -0.9 for the SA iterates and adjust Yn = (n + 1)=a in the SRRW iterates to cover all three cases discussed in this paper: (i) 0.8; (ii)
1. We use mean square error (MSE), i.e., El - 0- [1]] to measure the error on the SA iterates.
0.9; (iii)
Our results presented in Figures 2 and 3, where each experiment is repeated 100 times. Figures 2a and 2b, based on WikiVote graph, highlight the consistent performance ordering across different values for both algorithms over almost all time (not just asymptotically). Notably, curves for a 2 5 outperform that of the i.i.d. sampling (in black) even under the graph constraints. Figure 2c on the smaller Dolphins graph (Rossi & Ahmed, 2015)- 62 nodes and 159 edges illustrates that the points of (a, MSE) pair arising from SGD-SRRW at time n = 10" align with a curve in the form of g(x)= = (= + to showcase O(1a²²) rates. This smaller graph allows for longer simulations to observe the asymptotic behaviour. Additionally, among the three cases examined at identical a values, Figures 3a 3c confirm that case (i) performs consistently better than the rest, underscoring its superiority in practice. Further results, including those from non-convex functions and additional datasets, are deferred to Appendix H due to space constraints.
5 CONCLUSION
In this paper, we show both theoretically and empirically that the SRRW as drop-in replacement for Markov chains can provide significant performance improvements when used for token algo- rithms, where the acceleration comes purely from the careful analysis of the stochastic input of the algorithm, without changing the optimization iteration itself. Our paper is an instance where the asymptotic analysis approach allows the design of better algorithms despite the usage of uncon- ventional noise sequences such as nonlinear Markov chains like the SRRW, for which traditional finite-time analytical approaches fall short, thus advocating their wider adoption.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
We thank the anonymous reviewers for their constructive comments, especially Reviewer DxLx for raising future directions. This work was supported part by National Science Foundation under Grant Nos. CNS-2007423 and IIS-1910749.
REFERENCES
David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available http: /tpp://www... stat berkeley. edu/ Rw/bbook html.
Christophe Andrieu, Ajay Jasra, Arnaud Doucet, and Pierre Del Moral. Non-linear markov chain monte carlo. In Esaim: Proceedings, volume 19, pp. 79-84. EDP Sciences, 2007.
Ghadir Ayache and Salim El Rouayheb. Private weighted random walk stochastic gradient descent. IEEE Journal on Selected Areas in Information Theory, 2(1):452-463, 2021.
Anas Barakat and Paseal Bianchi. Convergence and dynamical behavior of the adam algorithm for nonconvex stochastic optimization. SIAM Journal Optimization, 11(1):2442274 2021.
Anas Barakat, Pascal Bianchi, Walid Hachem, and Sholom Schechtman. Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance. Electronic Journal of Statistics, 15(2):392-3947,
2021. 2021.
M Benaim and Bertrand Cloez. A stochastic approximation approach to quasi-stationary distribu- tions on finite spaces. Electronic Communicutions in Probubility 37 (20), 1-14, 2015.
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic ap- proximations, volume 22. Springer Science & Business Media, 2012.
V.S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint: Second Edition. Texts and Readings in Mathematics. Hindustan Book Agency, 2022. ISBN 9788195196111.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311. 2018.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, (2(6))2508-2558) 2006.
Pierre Brémaud. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. Springer Science Business Media, 2013.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM trans- actions intelligent systems and technology (TIST), 2(3):1-27, 2011.
VijaySekhar Chellaboina and Wassim M Haddad. Nonlinear dynamical systems and control: A Lyapunov-based approach. Princeton University Press, 2008
Vishnu Pandi Chellapandi, Antesh Upadhyay, Abolfazl Hashemi, and Stanislaw H 7ak. On the con- vergence of decentralized federated learning under imperfect information sharing. arXiv preprint arXiv:2303. 10695, 2023.
Han-Fu Chen. Stochastic approximation and its applications, volume 64. Springer Science & Business Media, 2006.
Shuhang Chen, Adithya Devraj. Ana Busic, and Sean Meyn. Explicit mean mean-square error bounds for monte-carlo and linear stochastic approximation. In International Conference on Artificial Intelligence and Statistics, pp. 4173-4183. PMLR, 2020a.
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite- sample analysis of stochastic approximation using smooth convex envelopes. arXiv preprint arXiv:2002. 00874, 2020b.
10

---

Published as a conference paper at ICLR 2024
Zaiwei Chen, Sheng Zhang, Thinh T Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite- sample analysis nonlinear stochastic approximation with applications reinforcement learn- ing. Automatica, 146:1 10623, 2022.
Burgess Davis, On intergrability of the martingale square function. Israel Journal of Mathemal- ics, 8:187-190, 1970.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: a fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, volume 1, 2014.
Pierre Del Moral and Arnaud Doucet. Interacting markov chain monte carlo methods for solving nonlinear geesure-valued equationsl. The Annals of Applied Probability, 20(2):593-639, 2010.
Pierre Del Moral and Laurent Miclo. Seff-interacting markov chains. Stochastic Analysis and
Applications, 24(3):615-66) 2006.
Bernard Delyon. Stochastic approximation with decreasing gain: Convergence and asymptotic the- ory. Technical report, Université de Rennes, 2000.
Bernard Delyon, Marc Lavielle, and Eric Moulines. Convergence of a stochastic approximation version of the em algorithm. Annals statistics, pp. 94-128, 1999.
Adithya M Devraj and Sean P Meyn. Zap q-learning. Proceedings of the 31st International 2017.
Conference Neural Information Processing Systems, pp.
Adithya M. Devraj and Sean P. Meyn. Q-learning with uniformly bounded variance. IEEE Trans- actions Automatic Control, 2021.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 1626-1635, PMLR, 2019.
Thinh T Doan. Finite-time convergence rates of nonlinear wo--imee-seat stochastic approximation under markovian noise. arXiv preprint arXiv:2104.01622 2021.
Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Convergence rates of ac- celerated markov gradient descent with applications reinforcement learning. arXiv preprint arXiv:2002.02873, 2020.
Vishwaraj Doshi, Jie Hu, and Do Young Eun. Self-repellent random walks on general graphs- achieving minimal sampling variance via nonlinear markov chains. In International Conference on Machine Learning. PMLR, 2023.
Marie Duflo. Algorithmes stochastiques, volume 23. Springer, 1996.
Mathicu Even. Stochastic gradient descent under markovian sampling schemes. In International Conference on Machine Learning, 2023.
Gersende Fort. Central limit theorems for stochastic approximation with controlled markov chain dynamics. ESAIM: Probability and Statistics, 19:60-80, 2015.
Sébastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball. Electronic Journal of Statistics, 12:461-529, 2018
Xin Guo, Jiequn Han, Mahan Tajrobehkar, and Wenpin Tang. Escaping saddle points efficiently with occupation occupation-time-adee adde-ad perturbations. arXiv preprint Ttl::2005.04007 2020.
Hall, C.C. Heyde, 7.W. Birnbauam, and E. Lukacs. Martingale Limit Theory and Its Application.
Communication and Behavior. Elsevier Science, 2014.
Hadrien Hendrikx. A principled framework for the design and analysis of token algorithms. In
International Conference Artificial Intelligence and Statistics, pp. 470-489, PMLR, 2023.
11

---

Published as a conference paper at ICLR 2024
Mingyi Hong, Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Jie Hu, Vishwaraj Doshi, and Do Young Eun. Efficiency ordering of stochastic gradient descent. In Advances in Neural Information Processing Systems, 2022.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham Kakade, and Michael Jordan. How to escape saddle points efficiently. In International conference on machine learning, pp. 1724-1732. PMLR, 2017.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pp. 1042-1085, PMLR, 2018.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-25) 2021.
Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In Conference on Learning Theory, pp. 1944-1974. PMLR, 2019.
Prasenjit Karmakar and Shalabh Bhatnagar. Two time-scale stochastic approximation with con- trolled markov noise and off-policy temporal-difference learning. Mathematics of Operations Research, 43(1):130-13 2018.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Vijay R Konda and John N Tsitsiklis. Convergence rate of linear two-time-scale stochastic approxi- mation. The Annals of Applied Probubility, 14(2):796-819, 2004.
Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and appli- cations, volume 35. Springer Science & Business Media, 2003.
Anusha Lalitha, Shubhanshu Shekhar, Tara Javidi, and Farinaz Koushanfar. Fully decentralized federated learning. In Advances in neural information processing systems, 2018.
Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
Qiang Li and Hoi-To Wai. State dependent performative prediction with stochastic approximation. In International Conference Artificial Intelligence and Statistics, pp. 3164-3186. PMLR, 2022.
Tiejun Li, Tiannan Xiao, and Guoguo Yang. Revisiting the central limit theorems for the sgd-type methods. arXiv preprint arXiv:2207. 1155, 2022.
Xiang Li. Jiadong Liang, and Zhihua Zhang. Online statistical inference for nonlinear stochastic approximation with markovian data. arXiv preprint arXiv:2330.076690, 2023.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiieee learning of deep networks from decentrulized data. In Artificial intelli- gence and statistics, pp. 1282. PMLR, 2017.
Sean Meyn. Control systems and reinforcement learning. Cambridge University Press, 2022.
Abdelkader Mokkadem and Mariane Pelletier. The compact law of the iterated logarithm for mul- tivariate stochastic approximation algorithms. Stochastic analysis and applications, 23(1):181- 203, 2005.
12

---

Published as a conference paper at ICLR 2024
Abdelkader Mokkadem and Mariane Pelletier. Convergence rate and averaging of nonlinear two- time-scale stochastic approximation algorithms. Annals of Applied Probability, 16(3):167-1172,, 2006.
Gemma Morral, Pascal Bianchi, and Gersende Fort. Success and failure of adaptation-diffusion algorithms with decaying step size in multiagent networks. IEEE Transactions on Signal Pro- cessing, 65(11))2798 2813, 2017.
Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter Bartlett, and Michael Jordan. linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration. In Conference on Learning Theory, pp. 2947-2997. PMLR, 2020.
Angelia Nedic. Distributed gradient methods for convex machine learning problems in networks:
Distributed optimization. IEEE Signal Processing Magazine, 37(3):92-100 101, 2020.
Alex Olshevsky. Asymptotic network independence and step-size for distributed subgradient method. Jourmal of Machine Learning Research, 23(69):1-32, 2022.
Mariane Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms. Stochastic processes and their applications, 78(2):217-244, 1998.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence adam and beyond. In International Conference Learning Representations, 2018.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017.
Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. In Advances in neural information processing systems, volume 31, 2018
Aleksei Triastcyn, Matthias Reisser, and Christos Louizos. Decentralized learning with random walks and ciaimuunicaatio-fffcieeeee adaptive optimization. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022), 2022.
Thijs Vogels, Lie He, Anastasiaa Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi. Relaysum for decentralized deep learning heterogeneous data. In Advances in Neural Information Processing Systems, volume 34, pp. 28004-28015, 2021.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speed- ing up decentralized sgd via matching decomposition sampling. In 2019 Sixth Indian Control Conference (ICC), pp. 299-300. IEEE, 2019.
Vinayaka G Yaji and Shalabh Bhatnagar. Stochastic recursive inclusions in two timescales with nonadditive dependent markov noise. Mathematics of Operations Research, 4404):1405- 1444, 2020.
Hao Ye, Le Liang, and Geoffrey Ye Li. Decentralized federated learning with unreliable communi- cations. IEEE Journal of Selected Topics in Signal Processing, 16(3):487-500, 2022.
Sihan Zeng, Thinh T Doan, and Justin Romberg. A two-time-scale stochastic optimization frame- work with applications in control and reinforcement learning. arXiv preprint arXiv:2109.14756 2021.
13

---

Published as a conference paper at ICLR 2024
A EXAMPLES OF STOCHASTIC ALGORITHMS OF THE FORM (2).
In the literature of stochastic optimizations, many SGD variants have been proposed by introducing an auxiliary variable to improve convergence. what follows, we present two SGD variants with decreasing step size that can be presented in the form of (2): SHB (Gadat et al., 2018; 8:; Li et al., 2022)
and momentum saaseedtuu--beeed algorithm (Barakat et al., 2021; Barakat & Bianchi, 2021).
Vn+1 v, + VF (6,, x
00 = Bn+1 n
m = m. + ( X mmn)
ma+1 = mn + Bn+t( (VP -nt1)
n = - Vvn +
(a). SHB
(b). Momentum-based Algorithm
(13)
where 0, On. m,, n. VF(0, TRd and the square and square root in (13) (b) element- wise operators. 10
For SHB, introduce augmented variable zn and function H (Zns 1 defined follows:
Zn
On mn
E
2d
H(Z,, X
-m, VF Xn+1) mn
E IR2d.
For the general momentum-baant based algorithm, we define
(f Xa+1) )2 22 Vn VF Xn+1) mn mm,/ VV +6
Vn
mn
E 3d
H(Z,, X)
E 3R
Thus, reformulate both algorithms (13) 2n+1 Un + Bn+1 (2n, X x,+1). This aug- mentation approach was previously adopted in (Gadat et al., 2018; Barakat et al., 2021; Barakat & Bianchi. 2021; Li et al., 2022) to analyze the asymptotic performance of algorithms (13) using an i.idd sequence {X,, Jn20 Consequently, the general SA iteration (2) includes these SGD variants. However, we mainly focus on the CLT for the general SA driven by SRRW in this paper. Pursuing the explicit CLT results of these SGD variants with specific form of function H (0, X) driven by the SRRW sequence { is out the scope of this paper.
When we numerically test the SHB algorithm in Section 4, we use the exact form of (13) (a) and the stochastic sequence (X,) is now driven by the SRRW. Specifically, we consider MHRW with transition kernel P as the base Markov chain of the SRRW process, e.g..
min
if node j is the neighbor of node i,
Púj
d, dz
otherwise,
Pa =
Σ P.j.
JEN
Then, at each time step n,
Draw:
Xn+1 ~ Kx,.
Kiylx] 4 Pap(os/1y))
where
Vi,jEM,
ΣKEN Pu/22//M )
Update:
Xn-1
7n (8x.11 -xn),
0, = 0 -B+t11 1
m = m, + Ba+1 (VF(1 (0,, m.)
X,+1)
For ease of expression, we simplify the original SHB and momentum based algorithms from Gadat et al. (2018); 9); Li et al. (2022); Barakat et al. (2021); Barakat & Bianchi (2021), setting all tunable parameters to 1 and resulting in (13).
14

---

Published as a conference paper at ICLR 2024
B DISCUSSION ON MEAN FIELD FUNCTION OF SRRW ITERATES (4b)
Non-asymptotic analyses have seen extensive attention recently in both single-timescale SA litera- ture (Sun et al., 2018; Karimi et al., 2019; Chen al., 2020b; 2022) and two-timescale SA literature (Doan, 2021; Zeng et al., 2021). Specifically, single-timescale SA has the following form:
xn+1 = X, + Bn+1 [(xx Xn+1);
and function hxx) & Ex [H X)] is the mean field of function (x, Similarly, for two- timescale SA, we have the following recursions:
Xn+1 Xn + B-B+11 H (Xn, Vus Xn+1).
Yn+1 Yn + 7n+1 (2 Yns Xn+1);
where } and {7n} are on different timescales, and function (x. & (x= X)] is the mean field of function (x, y, X) for i = {1, 2). All the aforementioned works require the mean field function (xx) the single-timescale SA (or hij (x, y), h2 (/(22/ y) in the two-timescale SA) to be globally Lipschitz with Lipschitz constant T. to proceed with the derivation of finite-time bounds including the constant L.
Here, we show that the mean field function π|x] x in the SRRW iterates (4b) is not globally
Lipschitz, where π [x] is the stationary distribution of the SRRW kernel K[x defined in (3). To this end, show that each entry of Jacobian matrix of π [x]
goes unbounded because multivariate function is Lipschitz and only if it has bounded partial derivatives. Note that from Doshi et al. (2023, Proposition 2.1), for the i-th entry of π (x). we have
EjEN (2//pa) (2z/Pj)
T.(x|
(16)
TheNNjeNuee MeN (2./ (2
Then, the Jacobian matrix of the mean field function π[x] x which has been derived in Doshi al. (2023, Proof of Lemma 3.4 in Appendix B), is given as follows:
0(m, [x] x.)
2a
(EREN Pilis (I1/Ps) (aai)"((nn (#I/Pk) ""EEN (15//1²) (ak/Uk) "))
(17)
3j
(EIEN EkEN Mi Pikk (m1/w)) (#x/ ) PrP (I:/ML) T (05/H1))
ΣIEN ΣKEN 14 PiP (II/MI) (Ix/
for i,j E N, # j. and
0(T, [x]
x.4)
Oxq
2a
(EEE HiPPae (2s/Pe) (IK/UL) -02
(18)
EEEN EKEN PIP (f1/11) (xk/ (4x) -
EkeN PaP (Is/Pe) (xx/ (ckk/14)= + (z(lp/pp)) 20
EIEN EKEN Pik (21/P1) (ax/ (cL/
for i N. Since the empirical distribution Int(E), we have 24 E (0, for all i E N. For fixed i, assume 2; = Ij and as they approach zero, the terms (#z/us) -a) (t;//;) -a dominate the fraction (17) and both the numerator and the denominator of the fraction have the same order in terms of 24, Ty. Thus, we have
a [T [x] xz)) = (1)
dr,
such that the (i. (th entry of the Jacobian matrix can go unbounded as Ty - O. Consequently, π xx] is not globally Lipschitz for x Int(E)).
15

---

Published as a conference paper at ICLR 2024
C DISCUSSION ON ASSUMPTION A3'
When Yn = o(3,), iterates X. has smaller step size compared to On, thus converges 'slower' than On. From Assumption A3', On will intuitively converge some point p(x) with the current value from the iteration Xx, i.e., Ex Ex-x[x] (H())))()))))))))))))))))))))) X)] = O, while the Hurwitz condition is to ensure the stability around pxx). We can see that Assumption A. is less stringent than A3' in that it only assumes such condition when
fa such that p(1+) 0" rather than for all E Int(E.).
One special instance of Assumption A3' is by assuming the linear SA, e.g., H(O, i) = A,0 - b,_ In this case, E (px X 0 is equivalent to [x + B xxxxx [b Under the condition that for every Int Σ). matrix Bi (x] [A,] is invertible, then have
p(x) = - (E (A.)) Exwn
However, this condition is quite strict. Loosely speaking, Ex [4,] being invertible for any is similar to saying that any convex combination of {A,} is invertible. For example, if we assume [AiKeM are negative definite and they all share the same eigenbasis (u.).eg., A, Σラ= Xf
and X/ < 0 for all i N, [D]. Then, E [x] [A.] is invertible.
Another example for Assumption A3' is when H0, i) H( for all i,j E N, which implies that each agent in the distributed learning has the same local dataset collaboratively train the model. this example, p(x) = 0" such that
E
| (p(xx), h(00)=
1 16==111 1 [0=1l1== Vh(0r) +
E [x] V (V(()()),))
being Hurwitz.
2
2
D PROOF OF LEMMA 3. AND LEMMA 3.2
In this section, we demonstrate the almost sure convergence of both O,, and x,, together. This proof naturally incorporates the almost certain convergence of the SRRW iteration in Lemma 3.1, since Xn is independent of 6n (as indicated in (4)), allowing us to separate out its asymptotic results. The same reason applics to the CLT analysis of SRRW iterates and we refer the reader to Section E. for the CLT result of x,, in Lemma 3.1.
We will use different techniques for different settings of step sizes in Assumption A2. Specifically, for step sizes 7/1 = (n + 1) 1ap0-",,, Br = (n + 1) we consider the following scenarios:
Scenario
We consider case(ii): 1/2 < a = b S 1, and will apply the almost sure convergence result of the single-timescale stochastic approximation in Theorem G.8 and verify all the conditions therein.
Scenario
We consider both case(i): 1/2 < < < and case (iii): 1/2 < b< S 1. these two cases, step sizes "/, Pn decrease at different rates, thereby putting iterates X,, O, on different timescales and resulting in a two-timescake structure. We will apply the existing almost sure convergence result of the two-timescale stochastic approximation with iterate- dependent Markov chain in Yaji & Bhatnagar (2020, Theorem 4) where our SA-SRRW algorithm be regarded as special instance."
D.1 SCENARIO 1
In Scenario 1, we have 3r = "n. First, we rewrite (4)
0n+1
[ Xn
10. ōx
7n+1
(19)
Xn+1
Xx
11 Hooweeer, Yaji & Bhatnagar (2020) paper only analysed the almost sure convergence. The central limit theorem analysis remains unknown in the literature for the to-timeseaeee stochastic approximation with iterate- dependent Markov chains. Thus, our CLT analysis in Section E for this two-timescale structure with iterate- dependent Markov chain is still novel and recognized as our contrihution.
16

---

Published as a conference paper at ICLR 2024
0n X
By augmentations, we define the variable Zn
E [N and the function G(Zn, i) -
H (O.: 1) ò, -xx E [[ In addition, we define a new Markov chain {Kn in the same state
space V as SRRW sequence (Xn]n20- With slight abuse of notation, the transition kernel of {Y, } is denoted by K'Zz.]= = [[x,] and its stationary distribution r'z,,] = π [x,,). where K[x,, and
(x,) are the transition kernel and its corresponding stationary distribution of SRRW, with л [x] of
the form
T. [x|x| x
(20)
JEN
Recall that fe the fixed point, i.c., π T(p μ. and P the base Markov chain inside SRRW (see (3)), Then, the mean field
EIEN T. (0.
g(z) (x) (G(z, (
क [x -
and z" = (0', 11) for 0* E θ in Assumption A3 is the root of g(z), i.e., g(2") = 0. The augmented iteration (19) becomes
Zn+1 2n + 7n+1 G Yn+1)
(21)
with the goal of solving g(z) O. Therefore, we can treat (21) as an SA algorithm driven by a Markov chain J220 with its kernel K'[z] and stationary distribution T' T'z)]. which has been widely studied in the literature (e.g.. Delyon (2000); Benveniste et al. (2012); Fort (2015); Li et al. (2023)). In what follows, we demonstrate that for any initial point Zn = (0.. xo) E R² x Int, the SRRW iteration {x,, |n20 will almost surely converge the target distribution pe, and the SA iteration {0n Jn20 will almost surely converge to the set O.
Now verify conditions C1 C4 in Theorem G.8. Our assumption A4 is equivalent to condition CI and assumption A2 corresponds to condition C2. For condition C3, we set V (z) = - -z),, and the set S = {z" |0 E x f1), including disjoint points. For condition C4, since K'[z]. or equivalently K [x). is ergodic and time-reversible for a given z, as shown in the SRRW work Doshi et al. (2023), it automatically ensures a solution to the Poisson equation, which has been well discussed in Chen et al. (2020a, Section 2) and Benveniste et al. (2012); Meyn (2022). To show (97) and (98) in condition C4, for each given and any i E N, we need to give the explicit solution mz(1) to the Poisson equation (i) (K' (i) G(z, i) g(z) in (96). The notation (K (K),))(i is defined as follows.
(k) (i)
Σ K K,(i.))m(z..) JEN
Let G(z) A [G(z, 1).... G(z, G)2, RND.
We use [A] to denote the i-th column of matrix
A. Then, we let mz (i) such that
my (i) (IG())(K 9(z))
Σ
(K( -1'"()====111]]] x'22]1 1..0-
(22)
k=
In addition,
(K, m2 (i) Σ G(z)(("' - - 1
(23)
We can check that the m2 (1) form in (22) is indeed the solution of the above Poisson equation.
Now, by induction, we get K' 1z] 1r' [z)" (K'[z) - 1 [z) for k 2 1 and for = O,
K' [z)) 1x [2]] (K') | IT [z)
J I [2) Then,
80
my (i)
(z)
- -'22]1") - g(z)
k=0
G(z)
[''z - 1)
9(z)
(24)
k=
= [G(z)(I - K' + 1
[:4) g(z)
= -7 -g()).
JEN
17

---

Published as a conference paper at ICLR 2024
Here, (I K'zz+ [ is well defined because K'2z] is ergodic and time-reversible for any given z (proved in Doshi et al. (2023, Appendix A)). Now that both functions H i) and ò x bounded for each compact subset of IR x E by assumption AI, function G(z, 2) is also bounded within the compact subset of its domain, Thus, function mz (i) is bounded, and (97) is verified. Moreover, for fixed E A,,
CI- + +1+ [2| (i.))), JEN
(i.j) = (I - K'Z 1T' |.. = (I- K(x] 1T )
and this vector-valued function is continuous in x because K[x], T[x] are continuous. We then rewrite (24) as
mz (i) EJEN(I- K[x] + 11[xx") (t, (x. (I K K + π x P.
Σ DiEN 73 (x) T x
With continuous functions H(O,i) i), K[x], [x). have mz continuous with respect z, does (K,mg) (2).. This implies that functions my (i) and (K)m))(8 are locally Lipschitz, which satisfies (98) with (x(x) Cex for some constant Ce that depends on the compact set C. Therefore, condition C4 is checked, and we can apply Theorem G.8 to show the almost convergence result of (19), i.e., almost surely,
lim X, = μ, and lim inf | n
0-1 =
n-000
Therefore, the almost sure convergence of x, in Lemma 3.1 is also proved. This finishes the proof in Scenario 1.
D.2 SCENARIO 2
Now in this subsection, we consider the steps sizes Yn. 8n with 1/2 < a < and 1/2 < b < 1. We will frequently assumptions (B1) (B5) in Section G.3 and Theorem G.10 to prove the almost sure convergence.
D.2.1 CASE (1): 1/2 < a a<bsl
In case (i). On is on the slow timescale and x,, is on the fast timescale because iteration O,, has smaller step size than X,, making 9n converge slower than X,, Here, we consider the two-timescale SA of the form:
0 0.+1 = 0n + Bu+1 (0, Xn+1); X,+1 Xn, Nn- (8x..) x).
Now, we verify assumptions (B1) -B5) listed in Section G.3.
Assumptions (B1) and (B5) are satisfied by our assumptions A2 and A4.
Our assumption A3 shows that the function H (0, X) is continuous and differentiable w.r.t f and grows linearly with ||@]. addition, 5x x also satisfies this property. Therefore, (B2) is satisfied.
Now that the function [x] - x is independent of 0, we can set p(0) / for any O E R such that T|u] - l = 0 from Doshi al. (2023, Proposition 3.1), and
Vx(T(x) - x) x= 2au1 T oPT - (a + 1)I
from Doshi et al. (2023, Lemma 3.4). which is Hurwitz. Furthermore, p(0) = inherently
satisfies the condition [|p(0)] S [1 [[@||) for any L || Thus, conditions (i) (iii)
in (B3) are satisfied. Additionally, ΣiEN (()
DieN [x(x] h(0) such
that for 0* E θ defined in assumption A3, ΣiEN T (H("" = h())) = 0, and
Voh(O") is Hurwitz. Therefore, (B3) checked.
Assumption (B4) is verified by the nature of SRRW, i.c., its transition kernel K[x] and the corresponding stationary distribution [xx with π [1] μ..
18

---

Published as a conference paper at ICLR 2024
Consequently, assumptions (B1) (B5) are satisfied by our assumptoins A1 A4 and by Theorem G.10, we have lim,-+s0 Xx, = μl and 0, + θ almost surely.
Next, we consider 1/2 << a S 1. As discussed before, (BI), (B2), (B4) and (B5) are satisfied by our assumptions Al A4 and the properties of SRRW. The only difference for this step size setting, compared to the previous
1/2 < < b I 1, is that the roles of 0.., x,, are flipped, that is, 0, is now on the fast timescale while X, is on the slow timescale. By a much stronger Assumption A3', for any E Int(E), (i) Ex>-rxx [H((x)), X)] = O; (ii) E Ex~=[x] (p(x,, ] is Hurwitz; (iii) ||p(x)]| < L2 + |xx])_ Hence, conditions (i) (iii) in (B3) are satisfied. Moreover, have = 0, ( - x) x- being Hurwitz, as mentioned in the previous part. Therefore, (B3)
verified. Accordingly, (B1) (B5) checked by our assumptions A1, A2, A3', A4. By Theorem G.10, we have lim X and On + θ almost surely.
E PROOF OF THEOREM 3.3
This section is devoted the proof of Theorem 3.3, which also includes the proof of the CLT results for the SRRW iteration X, in Lemma 3.1. We will use different techniques depending on the step sizes in Assumption A2. Specifically, for step sizes 7n2- = (n + 1) - 3r, (n 1) we will consider three cases: case (i): 8, = o(7,); ); case (ii:: 3, = Y and case (ii): 7n = ((3)). For case (ii), we will use the existing CLT result for single-times timeselleeeaee SA in Theorem G.9. For cases (i) and
(iii,, we will construct our own CLT analysis for the two-timescale structure. We start with case (ii).
E. CASE (II): 3, = 7/n
In this part, we stick to the notations for single- timescale SA studied in Section D.I. To utilize Theorem G.9, apart from Conditions C1 C4 that have been checked in Section D.I, we still need to check conditions C5 and C6 listed in Section G.2.
Assumption A3 corresponds to condition C5. For condition C6, we need to obtain the explicit form of function Q2 to the Poisson equation defined in (96), that is,
(K)))KK,00)) (z, 1) (x
where
(2, A
Σ Ki((i.))mm
JEN
Following the similar steps in the derivation of mz(1) from (22) to (24), we have
2x(1) = Σa -
K'22 1n (='"z"") (4.5) - xf)z)m=(j).
JEN
We also know that Qz(i) and (K2Q2)(0 are continuous in for any i E N. For any in a compact set Q2 @i(i) and (K) are bounded because function mz(i) (i) bounded, Therefore, C6 is checked. By Theorem G.9, assume Z, have
0,
00
converges point z' Xn
for 0 E O μ
1/2 (z,
z
dist.
N(0, V),
(26)
where V is the solution of the following Lyapunov equation
1 Qu=ll I+ Vo(=t)T) + (1 I Vo(z")) V V+U=0,
V
(27)
2
and U = EieN Mi (mx- (1mm. (1)T (Kx- (0) (i))
19

---

Published as a conference paper at ICLR 2024
By algebraic calculations of derivative of T[x] with respect in (20), 12 rewrite Vg((z)) in terms of x, i.e.,
88 &iiE (())))
EiEy T; (x)
(a) Vg(z")
20
0(
Om 0x
80
Vh(O")
FH (PT + I)
Jn JIz(a)
2a aP (a+ 1)1
J2n
J22
where matrix H [H(0", 1),, H1O, N)JT. Then, further clarify the matrix U. Note that
Ma (i) = -G= m1 |b,
1.N = E Gl("", Xo = Σ G((')) km0
Rm
(28) where the first equality holds because [' P from the definition of SRRW kernel (3), the second equality stems from G(z") ) = g(z") = 0. and the last term a conditional expectation
the base Markov chain (X&) (with transition kernel P) conditioned on Xo i. Similarly, with mx) in the form of (23), we have
(K₂ (i)
IGG( Xx)]
Xo =
From the form 'EEN p4 inside the matrix U, the Markov chain {X is in its stationary regime from the beginning, i.e., Xx ~ pe for any he 2 0. Hence,
(
00 EiG( G(2 xxiI
x Σ
U= E
G((z. Xx)]
R=0
k=0
( k=
EE
Σ
G(zz Xx)]
G(z ,(tex)))) Xx)]
= E [G((", xo))((z",,))
G(zz, Xo)
Σ c(z"xAa
(29)
4=11
+ E
Σ k=1
G(z", Xx)
G(z", x00"
Cov(GG(z,, G(z",
[Cov(G(z", (((2"Xx)) + Cov(G(z', Xx), (()x))),
where the covariance between G(z", Xo) and G(z", Xx) for the Markov chain (X,) in the station- ary regime is Cov(G(z', Xx), (ox,,))), By Brémaud (2013, Theorem 6.3.7), it is demonstrated that U is the sampling covariance of the base Markov chain P for the test function G(z", -). More- over, Brémaud (2013, equation (6.34)) states that this sampling covariance U can be rewritten in the following form:
U Σ G(z))",,,
N-1 Σ
-ーー H
1+ 7-
H'
H
H u'u u.u
Un U21
U 12
(30)
U
where {(A, Hee is the eigenpair of the transition kernel P of the ergodic and rive-reversible base Markov chain. This completes the proof of case
One may refer Doshi al. (2023, Appendix B, Proof of Lemma 3.4) for the computation of 8m
20

---

Published as a conference paper at ICLR 2024
Remark E.1. For the CLT result (26), can look further into the asymptotic covariance matrix V as in (27). For convenience, we denote =
Vn
V12
and in the form of (30) such that
V21
V2
V V21 21
V12
[ [L 1 (+=aa=)(())))) + 2
(12
(bm1) I ((a((a)
Vu
V 22
+U = O. (31)
22
V21
For the SRRW iteration Xn. from (26) we know that 1/2 (x,, 1))
th
dist.
((0, Va). Thus, in this
remark, we want to obtain the closed form of V22. By algebraic computations of the bottom-right sub-block matrix, we have
20u11 - -(a+1 1(0=11)
(1 V2
2
+ 22 20p11 -ap"
1 10--aa11--100
[1=11
T
2
U22 0.
By using result of the closed form solution to the Lyapunov equation (c.g., Lemma G.I) and the cigendecomposition P, we have
N-1
+ A {a=1} 1- X u.u
V 22
(32)
20
1,) +2
E.2
CASE (I): B, = ((Tm)
In this part, we mainly focus on the CLT of the SA iteration O,, because the SRRW iteration x, is independent of On and its CLT result has been shown in Remark E.I.
E.
DECOMPOSITION OF SA-SRRW ITERATION (4)
We slightly abuse the math notation and define the function
h(0, x) E x (0, Σ [x
iEN
such that h00, 14) = h(0). Then, we reformulate (25)
0.+1 = On + Bat1h((B x,) + Bnt1(H((H) Xn+1) - h(6n, xx)).
(33a)
X, xx, + 7n 1 ( [x,]] -x,) Yo+i (6 (6xm.1) x(xx]).
(33b)
There exist functions (x : :N - N Ho :N + R.D satisfying the following Poisson equations
5. Txx) (x( (I)
(34a)
H 1) h0, He (Kx)),x)
(34b)
for any E RRD,x E Int(E)) and i N, where (1) & EjEN (x)l))axxj), (K₃ Ho. -
EjEN Kis [o) The existence and explicit form of the solutions 9x. Hø.x, which are contin- uous w.r.t x, O, follow the similar steps that can be found in Section D.I from (22) (24). Thus, can further decompose (33) into
0 0 =0, + 1.+1h(h0 xx) + Bx+1 (Ho.. x. (Xn+1) - (Kx, Ho. xn (XX)))
M
+ Bn+1 ((Kxa X (Xn+1) (Kx, Ho. X.. (Xn++1)
(35a)
(0.1)
+ Bn+t ((x,, Honx.. (Xx) - (Kx,_ Ho Ho (Xx+1))
(0.9)
21

---

Published as a conference paper at ICLR 2024
Xa+1 =X, + mn (x(x)) xn) + Ya+1 (9xn (Xn+1) - (Kx, 9x. (Xxn))
M
+ 7++1 ([xx, 9xn, [..,(((nn)) - [Kx, Bant I((x+1))
(35b)
7n+1 (Kx, Ben (Xx) (Kx, Be (Xn+1))
(2..2)
such that
pu+1 = 0n Bn+1hh(nn x,) + Bn+1MM MM + Bat11 B But1r (0
(36a)
Xn+1 = Xx, + 7n+1 (TT(x,) - xx,) + Pn+1M 1n+1r (x.1) 7ntir (x.2)
(36b)
We can observe that (36) differs from the expression in Konda & Tsitsiklis (2004); Mokkadem & Pelletier (2006), which studied the two-timescale SA with Martingale difference noise. Here, due to the presence of the iterate-depender Markovian noise and the application of the Poisson equation technique, we have additional non-vant non-vanishing terms r. (0.2) T' (x.2) which will be further examined in
Lemma E.2. Additionally, when we apply the Poisson equation to the Martingale difference terms M M find that there are some covariances that also non-vanishing in Lemma E.1. We will mention this again when we obtain those covariances. These extra non-zero noise terms make our analysis distinct from the previous ones since the key assumption (A4) in Mokkadem & Pelletier (2006) is not satisfied. We demonstrate that the long-term average performance of these terms can be managed so that they do not affect the final CLT result.
Analysis of Terms (0 n+1 n+1
Mxx))
Consider the filtration F, - (f0, Xo: Xo. On: Xn, X,), is evident that M m-1 M(x)) are Martingale difference sequences adapted to F,,. Then, we have
E M (M1/11) Fr
E Elex. (Xn+1 1x. (Xn+1) ( [Fn + (Kx, Gx )Xx,) ((Kx, 9x. (X,)))
(37)
Elaxa (Xn+1) (Kx, 9xn (XXn)
(Kx, 9x (XX, (E(E),( 9xx. (Xn+1)² |F
=E(x,, (Xu+1 Mo., (Xn+1) [Fa) - (Kx, Ix Ix,, (Kxx, 9xc.. (xx,)) (x,
Similarly, we have
E
( (Ar )r
Fr
x+1
(38)
(Xn+1) [Fa) (Kx, x., (Kxx, Ho (X.))
EE| fo.
and
E AM (x) (M (M) )T Frl
= [[ex (Xn+1) Ho..... (Xn+1) [FF)] - (x, (XNn) ((xx, (Xxn)
We now focus on E
M M
(M (x)
Fn
Denote by
(Kx)x) (x K. (x,x(x)oxx)))))))) -(Kx))))()))()))))))) ((KIx)))))
(39)
and let its expectation w.r. the stationary distribution Txx) be vx(x) A E (x i)], we can construct another Poisson equation, i.e.,
E
M (x) (M
n+1
(x)
)r
Fr]
Σ X.EN
xx,, (xn) M (MM )r Fr)
Vi Xn+1) 11 (xx)
= -Xn+)( - (Kx, (2((1) (Xn+1);
22

---

Published as a conference paper at ICLR 2024
for some matrix-valued function 9x A RNXN Since ys and K [X] continuous in X,
(1)
functions Vi, un are also continuous in X. Then, we can decompose (39) into
(x Xn+1)
(1 + + (Xm) vi( (Xn+1) (Kx, 9x (Xn)
U22
D
(40)
+ (Kxn, (xx) - (Kx, (X
Thus, we have
B[M n+1 n+1
(M 1 = U22 + D + +J
(41)
where J -J M
Following the similar steps above, we can decompose
M (M )7
n+1 n+11
Fn
and
[ n+1 (M Fr as
E M
(M )7 Fn U21 +D! + +J
(42a)
E
M
(M (0) )r Fr Un + D + J
(42b)
(3.0) (3,)) _ Here, we note that matrices J for 1,2,3 are in presence of the current CLT analysis of the two-timescale SA with Martingale difference noise. In addition, UI. 12 and U22 inherently include the information the underlying Markov chain
where _ = _2200) +J (2.6) and (
(with its eigenpair (A;, u,)), which is an extension of the previous works (Konda & Tsitsiklis, 2004; Mokkadem & Pelletier, 2006).
Lemma E.1. For M (04 defined in (35) and their decomposition (41) and (42), we have
Un Σ
N-1 1 n
U21
N-
Σ
1+ u H,
Un=
Σ 1=1
1+ A H" 1-x
H.
==1
(43a)
lim
D =0 a.s. for i= 1,2,33
(43b)
n-000
lim Yn
E
0, for i= 1,2,3.
(43c)
Proof. We now provide the properties of the four terms inside (41) as an example. Note that
Un Brag [V
Σ pi
Σ P(.
(1) (PP
JEN
Σ (nnnn))an() JEN
(Pqn)() (Pa
We can see that it has exactly the same structure as matrix in (27). Following the similar steps in deducing the explicit form of U from (28) to (30), we get
N Un Σ
u.u."
(44)
By the almost sure convergence result X., + l in Lemma 3.1, vi(x,) + ti (44) a.s. such that
lim D (1) 0 a.s.
Ex (La)
and lim 7n ||| Ex J (1.6) o.
We next prove that lim En
23

---

Published as a conference paper at ICLR 2024
Since {J% is Martingale difference sequence adapted to Fr. with the Burkholder inequality in
Lemma G.2 and p = 1, we show that
(1a)) Σ & -
11)]
E
Σ
(1a)) b
S CE
(45)
By assumption A4, X,, is always within some compact set Ω such that sup,, || Cn oo and for a given trajectory w of xn (w)),
Σ & 11) S C,Carava,
Tn
(46)
and the last term decreases to zero in since 1/2.
For J (1,b) we use Abel transformation and obtain
(K P (Xx-2) - -Kx-
2lll (Xx-11))
(Kxp Px (Xo) (Kx +Kx,+ (
(1) (X) is continuous in x, for Xn within a compact set & (assumption A4), it is local Lipschitz with constant La such that
Since (KxPx)
[ 22 ( (X)-1) Kx xX (x xa|xx x;= S 2L
where the last inequality arises from (4b), i.e., X2 Xx-1 = 7x -x=-1) and 1|6x, -xa-1l S because E Int(E). Also, [I(Kx, 8x0 (Xo)ll + ||(|| Pk. are upper-bounded by some
(1)
positive constant Cg. This implies that
(1.b)
$ CC + 2La
7k.
Note that
7n Σ (1,b)
S On + +L
T S Mn +
2Lg
n1
1-2a
(47)
k=1
where the last inequality from Σh-1 7
<
1-a
We observe that the last term in (47) is
decreasing zero in n because
1/2.
Note that J (1)
(1.a)
+
(1.b) b
by triangular inequality we have
12
72
Y. E
Σ
(11) &
I M
(11.A)
+ T
B1
R=1
J (1) (s)
< nn E
+ Y.
(1I
(48)
k=
J Tall 11)
(2²)
E
+ V/
Σ
B
where the second inequality comes from (45). By (46) and (47) we know that both terms in the last line of (48) uniformly bounded by constants over time that depend the set Ω. Therefore, by dominated convergence theorem, taking the limit over the last line of (48) gives
lim +0000
E
Ci
(11,A)
+
(1.88
A=1
= E
lim n=000
Ci
Σ
+7n
11
-0.
24

---

Published as a conference paper at ICLR 2024
Therefore, have
m (1)
lim In
E
Σ k
O,
200
In sum, in terms of [EMM (x)
(M (M4 [x]
n+1 | in (41), we have U11 in (44), lim (2) 0 a.s. and
limp-roo 7al
Ei= J (1)
O.
We can apply the same steps as above for the other two terms = 2,3 in (42) and obtain the results.
Analysis of Terms ra I'n
(0.1) (0.2) (x.1) (x.2)
,n
Lemma E.2. For Ian .Tn on In
(0.1) (0.2) (x.1) (x.2)
defined in (35), have the following results:
[ = (())) ol Bn), V7n
k
(0.2)
=o())
(49a)
k=1
= ol 1xx = =
V'n
Σ
=0(VT)) o(1).
(49b)
k
k=1
Proof. For I' (0.1)
note that in
(Kxa+) Ho (Xn+1) (Kx, Ho. (Xx+1))
Σ Kx (xxnj(Xxn 11lo:++11000tx0i... (i) K Kxna (Xn) (i)
JEN
(50)
Σ Tcc(10nn11 OOll + |Xa+1 xnll) JEN <NLe(Ce2nt1+ + +2m+1+++++++))
where the second last inequality is because Ki, (x.](x)Hoxxx is continuous in 0, x K K[x), which stems from continuous functions K [x] and Hø The last inequality is from update rules (4) and
(0 x.,) E Ω for some compact subset by assumption A4. Then, have (1.10 || ( of B.) because of a > 1/2 2 b/2 by assumption A2.
We let 2/ A (Kx,, Ho..x.. x.. (Xx, such that r. (0,2) V/, Mn+1. Note that Σ (0.2) 11 Vn+1, and by assumption A4, | || is upper bounded by a constant dependent on the compact set, which leads to
n
(0.2)
= T 11 - Un+ill = O(VTm) = o(1).
Similarly, we can also obtain ||r 10.0x1111 B.) and V'a
Ek 1/ (x.2)
(0(TT))=(() n
E.2.2 EFFECT OF SRRW ITERATION ON SA ITERATION
In view of the almost sure convergence results in Lemma 3.1 and Lemma 3.2, for large enough n so that both iterations O,,, Xn are close to the cquilibrium (0* 44), we can apply the Taylor expansion functions h(0, x) and π T[x]
(36) at the point (0", 14), which results
h(0, x) = h(0 14) + Voh 0" ( 8*) V (x) -0( π With matrix J(a). we have the following:
(51a)
π T|u} μ + (TT()x x) x)
+ +0|x 1=
(51b)
Jn1 Veh(O", 11) Vh(0"),
J (1) Vxh(0", 4) = - (PT + I),
(52)
(a) Vx(T((x) - -x)|x= = 2au11 -aPT (a + 1)I.
25

---

Published as a conference paper at ICLR 2024
Then, (36) becomes
0 On+1 = On + 1 - -0) +J2(())(xn 11) (1) +r) 10.11) +r + +M _
(0.2) (x.2)
(0) + )
(53a)
Xx+1 Xx + mn (J21((22(a)(xx) 11) rr(x11) + + M + )
(53b)
where 1/ = 0 1 1 21) and (x) = O x (x,,l1))..
Then, inspired by Mokkadem & Pelletier (2006), decompose iterates {x,} and {0.) into x, In
A (a) and 0n = T + R + ( Rewriting (53b) gives
R, p = 1 J22 (a) 'xx+1 xn. - (a) (x.1) + (x.2) + M + )xx))
and substituting the above equation back in (53a) gives
0. 0" 0, 0- + Bn+1 JIn 0*) +
(xx+1 - -xn)
-12(a)]22(a) (r)
(x.11) + x(x.22 + M + n/! (x))
+ ( + (0.2) + M + 1/22
+r
=1++ (0,, 0³) + | J (x - x,n)
+ B (M (12((2))222( M n-1
(1 + + // - J12(a)Iza(a) (r(x +(xx2) + n(x))),
(54)
From (54) can the iteration (0x} implicitly embeds the recursions of three sequences
ButiYat Jiaa)aaaaaaa))
xx);;
BM+1(M - Ja((()))((())
BrtilTh (0.1) +rn
(0.2)
(0) Ji2(a))=2(()> (x.11 + tr (x.2) (x0) )))-
th
Let Un A En k= 3h and A n k== mh Below we define two iterations:
( J1 10)
+ (M( J12())J2(a))
(55a)
(un un Jn BM - J12(a)J22((1 -
k=
R AnJ11 R (
Bn 7n J12(a) (x,, xn-1)
(55b)
e (ua - J1) BK JIz(a)Jz(aa) - - x)-1)
k=1
and a remaining term (0) & 0, 0"
-( R!!
Similarly, for iteration x,,, define the sequence L such that
(x) = (nn I n-
+ 7/,
M(x) n
(sn (sn-ss J2a M(()
(56)
and remaining term
A (x)
(
(57)
The decomposition of 0,, 0* and X., SA literature (Delyon, 2000; Fort, 2015).
4 in the above form is also standard in the single-timescale
Characterization of Sequences {I,!]) and (I
we set a Martingale (n)) = (2 Jaz such that
1 1/2 J1
u1J BM (1a
(((0))
x Σ
0
1/2 (n)22((a) In
e =
t=1
26

---

Published as a conference paper at ICLR 2024
Then, the Martingale difference array " % becomes
1/21/2 e (1un-u))as -11 3e (M J ( 21x
2(m) =
1/2 cen -on 22z (x) M
Y/2
and
Σ
E (Z (m) (n)
k-
(Z
2 (n) 1
A? 2,n
A
Ain
Azn
1=1
where, in view of decomposition of a and M (41) and (42), respectively,
1n, B
Σ
Beelun up)Jan
U22 U22 JJ - (U21 - + +D (2) +J
(2)
Ju (3) " (1)()))2((())
-Jn(a)Jo(()) D + - -
(58a)
A = 1/2 7m 1/2
3r 1n 2, (U21 (12(0))22(a) Unn) se))aa()))))
(58b)
As,
Yn
(U + )
(58c)
k=1
We further decompose AI, into three parts:
A
=B
(u U=(((a(a))2(aa->))
k=1
J12(a) -U12 " ww)()
+ 3
U D (nnaa)aaa)a
(D
D (2)
+ 8--1
(ue Ne H 112(()) (1
k=1
2 AA(a1 + (0) + A(c)
(59)
Here, we define Ua(a) Un(])
Un (n((in(())Dn(a))11)
(a)
+
-I Iy. By (52) and (43a) in Lemma E. we have
N-1
1 A H" u.u.T H. 1-X
Uo(a)=
Σ 1=1
(60)
(a(1 +)
Then, we have the following lemma.
Lemma E.3. For (1a) (b) ( defined in (59), we have
lim (10 = Vola), lim
[1 0,
lim
[4 = 0,
(61)
n-
n-000
where Vo(a) is the solution to the Lyapunov equation
1 1(b 12 (1-111 Ju +
A6o-12 1) T
Ve(a) + Ve(a)
J
+ Uo(a) = 0.
2
2
27

---

Published as a conference paper at ICLR 2024
Proof. First, from Lemma G.4, have for some c, T such that
| S B
D (1) + JIz(a)Jz(a)=DD3 % (Jz(a)]z2(())1) " - (I
(J
k=
(D
BRe²E 2T(un-us)
Applying Lemma G.6, together with D + 0 a.s. in Lemma E.I, gives
limsup
|| (8)
1
S C(b,p) limsup (DD (1a())uz(a) ( (In(a))aa
2 n -
-0
We now consider ||A]fal] || Set
(J
(Jz(a))22(a)1)) - JIe(a)J2((a) (J{() 7))
we can rewrite { as
1 = 8,11 elelus un u2)J (Ex Ex (e(e) -e)ln))))
k=1
By the Abel transformation, we have
1/ = Bm + 8
Relun - un) 1 um)
(62)
82 e - 1i ( -1+1))111
We know from Lemma E. that Bn + a.s. because E, = 0( Besides,
B (2 - Jx) 3x+1e (vn (x41)))
(Mn)))) = 11x BK+1 (e Jn)J Be uuajan (I e 9641J11]
I -(un (un-
for some constant C1 0 because 3n Bot1 C2 and || e- BatiJn || S C3B441. Moreover,
(un (un)) || + 11 u241))111 (
S. S3 (w)Jl + Be Belle(un-aadue -e-1Jull
-C (un uva-
Using Lemma G.7 on (62) gives
14 10)
S CCC
Σ km/
- 2(u, - 1. + 11 ||-
Applying Lemma G.6 again gives
limsup
| < C2 lim sup |3,5, || =
for some constant C > O. Finally, provide existing lemma below.
28

---

Published as a conference paper at ICLR 2024
Lemma E.4 (Mokkadem & Pelletier (2005) Lemma 4). For sequence with decreasing step size 3n (n + 1) for E (1/2, 11, Un = Σk=1 Sk. a positive semi remi-definite matrix I' and a Hurwitz matrix Q. which given by
n
B
B (u
k=1
we have
lim B 8 -T V
km
where V is the solution of the Lyapunov equation
(Q + [(b=1] 1 V
1 ((b-)) 1) Q
+ +-= 0.
2
2
Then, lim ( = Vo(a) is direct application of Lemma E.4.
We can follow the similar steps in Lemma E.3 to obtain
lim A4,a Vx(a),
where Vx(a) is in the form of (32).
The last step is to show limn->oo Ag, = O. Note that
|| A2 =0
8-1122 1/2 1- 1/2
Ba aalle (e wu Jo1 Wlllllels )zz2)2()) 1 (
k=1
=0
8n
8-1/2
1/2
nn
1/2
7 (4n uux (( -x
k=1
= 0
8
1/2 1/2
mn
BK7RE - (5x (#x-)
k=1
where the second equality is from Lemma G.4. Then, we use Lemma G.6 with = 0 to obtain
Σ Bime (s. (s)- = O(5n)
(63)
Additionally, since 3, o(Tn), have
B 1/22 1/2
8u7K 1/2 1/2,3/2 e (on = 02 = o(1)
Then, follows that limm Ag, 0. Therefore, we obtain
lim 2200
B (Z(())
(n) b(2 (2
-m) -( (Vo((a)
VV((a) vala))
Now, we turn to verifying the conditions in Theorem G.3. For some
0, we have
E 12 (n)
2(m) 12+
0
(1+ 1
32t 3 -22t))un uNT
+ +
-1++))
7k
2+ 5 -22-()2))) -2--))(snsuu)) (64)
8 + 7
29

---

Published as a conference paper at ICLR 2024
where the last equality comes from Lemma G.6. Since (64) also holds for 7 = 0, we have
Σ E
-
((m)
Fk-1| = O(1) < co.
Therefore, all the conditions in Theorem G.3 are satisfied and its application then gives
V
B
L Ln
N (0. (0.(7 Vo(a)
velaa)
2(n)
(65)
Pm
dist.
0
Furthermore, we have the following lemma about the strong convergence rate of {Lx²) and (L,)), j. Lemma E.S.
|| | 0 Bv log(un)
a.s.
(66a)
| 0 (Vrr log(8n)
a.8.
(66b)
Proof. This proof follows Pelletier (1998, Lemma 1). We only need the special case of Pelletier (1998, Lemma 1) that fits our scenario; e.g., we let the two types of step sizes therein to be the same. Specifically, we attach the following lemma.
Lemma E.6 (Pelletier (1998) Lemma 1). Consider a sequence
Ln+1 = 6 H
- Bg
R=
and {Mn} is a Martingale difference sequence adapted to the filtration FF such that, almost surely, limsup, El ||||Ma+i|| (14 S M2 and there exists T E 20, 6(2 + T) > 2, such that sup,, M[[[ / < co. Then, almost surely,
where Bn n 1/2
||
lim sup
S CM,
(67)
V Bn log(un)
where CM is a constant dependent on M.
By assumption A4, the iterates (0n, x,) are bounded within compact subset Ω. Recall the form of (( Mxx)) defined in (35), it comprises the functions Ho., (t) and (Kx, xx...., (i), which
in turn include the function H(,, i). We know that H(0, i) is bounded for 0 in some compact set
( (x)
C. Thus, for any (0,, x.. E for some compact set 22, 74 x++ are bounded and we denote
by cg and 6x as their upper bounds, i.e., E[| (() [| S ci and ([()) 7+1
[12|Fn]] S c We (x)
only need replace the upper bound in Lemma E.6 by 62 for the sequence {T!!O) (resp. en for the sequence {L
(0)
(x) }), i.c.,
|| [I
limsup sup
< (0)
(68a)
/ B, log
||
lim sup
Oxx)
(68b)
I'n log (m))
such that = =0 | Bn log(un)) a.s. and ||,((0 = 0( Tm log(sn) a.s. which completes the proof.
Note that we have x,, - 14 and Lix
(x) weakly converge to the same Gaussian distribution from Remark
E.1 and (65). Then, 7/. 11/ Axx) weakly converges zero, implying that 7,2 1/2 11/22A3 Ax(x)) converges to
zero with probability 1. Therefore, together with {rr} being strictly positive, we have
A (x) Tm) a.s.
(69)
30

---

Published as a conference paper at ICLR 2024
Characterization of Sequences {Ra) and }
We first consider the sequence { {R) We assume positive real-valued bounded sequence {wn) under the same conditions in Mokkadem & Pelletier (2006, Definition 1), i.e.,
Definition E.1. In the case b < 1,
20n + (B,)), which also implies Win
11+ o(7m).
w=+11
Wa-11
In the case = 1, there exist 0 and nondecreasing slowly varying function ((x) such that Wn n (()). When
we require function I(n) to bounded.
Since ||x, - 14|| (1)
11) by a.s. convergence result, we can assume that there exists {w²} such that |>xn 11| (w wn) Then, from (55b), we can use the Abel transformation and obtain
R = B. (12(a))22(() (x - 14) (uun=un)Jn Bi7i UUnJ (2()))))()))(()((G(()) 1))
+ e Ju
Σ (e-udh BK "ntiJn 3x+1 (z 14), k=1
where the last term on the RHS can rewritten as
Wn
(un wun))1+ B4+17 (e0k+1J11
7841 - Da
10).
Using Lemma G.6 on Wa gives |W,,, 01 -I I|||,, -+1l) O(m (n)w).) Then, follows that for some > 0,
| O (B wi, + (1e (l) 1B
vn Wn + +
(70)
with the application of Lemma G.4 to the second equality.
Then, we shift our focus on (A Specifically, we take (54), (55a), and (56) back to A!
O, - - - 12(0) and obtain
10) =(I 1n41J11)(0 -0)
+ (r 10.1) + rr (0.2) + m/ J12(a)) (x(xx)) + (xx2) + +1111)1
- antiJ111 (0) BatiJn R!
= =II+ Bnt1J11)
8*)
(71)
+ +10+1(1101 (0.1) + +
(0.2) + m/
(0) [nn((]))a)()a)1010
+ +rxx))) + xx()))
(I+ 0 (( (0) (I B1+1J11 + 0 1)) R!o)
=(1+ Bn+1J 11 + + (L R(O)))
+ +.842(1(001) + (0.2) + : ( (x.1) + (x,2) + 1/!x2 (x)))) ));
where the second equality is by taking the Taylor expansion @ In I Bnt1J11 (
Define T kk
IT (I B,J11) and by convention pn.n I. Then, we rewrite (71) as
(0)
Bx+1 (0(8E+1)4 (0) + +(34+1)41
n+1
1 kk (141
(0.1) + (0.2) n (0)
(1) + (x + m (x)))
Bk (0(B4+))I
(0)
083+1))
Denn BK+ (1 + w
(0.1)
(
Ji2(a)Joa(a) (1r
(x.1) +1) (x))
p Pknn Ba+1 (1 (0.2) - (1))
1=1
(72)
31

---

Published as a conference paper at ICLR 2024
From (72), we can indeed decompose A (t)
n+1 into parts (0)
A - where
A
(0.1)
P knn
S+11 (0(Bk+1)L ((
(73a)
S k 11 (0.1)
(0,11
(0) - J= (rk (x,1) + 1)
m
k=
A (0.2) a+l
1 k Bx+ 1 10:21
- (12(a))22(a))11)) (1)2))
(73b)
k=1
This term (0.1) shares the same recursive form as in the sequence defined in Mokkadem & Pelletier (2006, Lemma 6), which is given below.
Lemma E.7 (Mokkadem & Pelletier (2006) Lemma 6). For A in the form of (73a), assume |xx, /a|| = (ww)) and | (x) || = 06,,) for the sequences wny on defined in (E.1). Then, we have
(0.1) A n41 ( Yn wi + fn (n) + ol p(VBn)
a.s.
Since already have A!x) ol Tn) in (69), together with Lemma E.7, have
1 = 06 w + o( No 1/2) + ol (vB)) = w + ol (/n))
where the second equality comes from 0B 1/3 o(3 1/2 (B o(
We now focus on A (0.2) Define sequence
V
(0.2) -12
(74)
and we have
1/2 B +++
+ 3 (1
(0.2) -12(())02(())111)) -1((x(2))
8 81/22 1/2
4 34+1 vK-1)
n+1
8 21/4 Un + 8 8
1/2
Σ (B.4k.m Bk+1 1
where the last equality comes from the Abel transformation. Note that
1I Ba+ 1, < Bx+ pk.n Pu+1,all + (Bx. 3 Px,lll
s B | Jiall + C+8 1| Px.mll
< Cs (ux =x)T
for some constant C7, Cs > O, where the last inequality is from Lemma G.4 and || 1 Cg Px.n for some constant Cg > O that depends on eoT Then,
1/2 B-11
2 ( J12(a)J22(a) -1 (x2)))
Pn+1
1/2
n
< ||3 yxll +
3-1/2
1 - Bx+1 #x+1m /1
Br
km
(Bat1
1/2
< //3
Mnll
+ Cs
8 1-2
335 c (u. - ux //3 2/2 V.
Bn
k=
32

---

Published as a conference paper at ICLR 2024
By Lemma E.I, have
vn Vn
0 a.s. such that by Lemma G.6, it follows that
lim sup,, /18//// vn
lim limsup sup BTT12
Σ
knn B (0.2) JIz(a)Jza(a) (x:2))
1/2,
Therefore, we have
A
(0.2) n+1
Σ
D BR (0.2 (aaa (x.2) vm).
(75)
1=1
Consequently, A 77 w?)) (vBB.) almost surely.
Now we are dealing with x,, la and its related sequence wn. Note that by Lemma E.5 and (69), have almost surely,
|xx, Mlll = -(1L || I1
10 + ol mm)
(76)
= O(V log(
Thus, we can set wn = O(V in log( s,)) such that [|/2)/ in (70) can be written as
|| | O(n Vlog(sn + uu.),
and
|4 = On a- log(()) "
+ o0 (l)Bm) Br)
In view of assumption A2 and Bn = 0(7m), a/2 - < -b/ and a a- < -b, there exists a c b/2 such that almost surely,
! || = On | o(
Therefore, /,. ((((( + (0)
+ n41) 0 almost surely. This completes the proof of Scenario 2.
E.3 CASE (III): Tnn = o(B))
For 7n o(Bn), while x, is on slow timescale.
that the roles of 0n and x,, flipped, i.e., On is now fast timescale
We still decompose Xn as X, - μa (x) + (x)) where (x) A!x are defined in (56) and (57), respectively. Since x, is independent of A,, the results of (x) and A remain the same, i.e., almost surely, [(( = Ol log(s,)) from Lemma E.5 and A = olvTT) from (69). Then, we define sequences ( and ((()) follows.
(x)
( A c Ju 110) + B,
(un J1 B
(77a)
(1)0) & BnJu ((0) + (1) + H(x))
= Σ
(un uy J11 3 12J12(a) + R(x)
(77b)
Moreover, the remaining term ( A 0,
The proof outline is the same in the previous scenario:
We first show 3, (0) weakly converges to the distribution N(0, (3) (a);
We analyse ( and (((0) to ensure that these two terms decrease faster than the CLT scale
3. i.e., lim 8 1/2 ( (
k(!)) 0:
33

---

Published as a conference paper at ICLR 2024
With above two steps, we can show that 9n (0. -0") weakly converges the distribu- tion N(0 v (a).
Analysis of f.
We first focus on (0) and follow similar steps as we did when we analysed ( in the previous scenario. We set Martingale Z(n)
{2k (1)
122 such that
2(m)_ = 3n 1/2
(tn (an--u)JJnel (W
km
Then,
A, - Σ
(m) (Z 2 )21 Fr-1]
A=
Following the similar steps in (59) to decompose M (0) with (42b), we have
An 3-11 Lee un u.)J (Un1 D + + e( a
BT
ee -un) CulJJuUUUeee Uneelu--uhhh + B Σ
ffeln Delluu-s)JlD ( cunn-ue)dF
kml
(78)
(c)
A
+ 3-1 1
3 e
un us J11 (3)
(u Jf
k=
Since A (b) 1 share similar forms as Lemma E.3, we follow the same steps as the proof therein, with the application of Lemma E.1. To avoid repetition, omit the proof and directly give the following lemma.
Lemma E.S. For Ald) A An defined (78), we have
lim (a) ((3) (a), +
lim n
| 0, lim noc
|| = 0,
(79)
where v-3) (a)) is the solution to the Lyapunov equation
Jn + VJ + Un 0.
Note that here we don't have the term ( I in above lemma, compared to Lemma E.3, because in the case of o(B,), b < 1 such that (b= = 0. Then, applying Lemma G.1 to derive the closed form of v(3) (ax) gives
v (a)= =o So " Vob(0)
Thus, it follows that
lim
E
(7
m2)
7 (1)
(2
v (a).
k=1
Again, we use the Martingale CLT result in Theorem G.3 and have the following result.
7 = - 1/22((0) (0)
n-+00 N (a))
dist.
Moreover, similar to the tighter upper bound of (x) upper bound Lemma E.6 in the proof thereof, and obtain f O( Br log(u,)).
proved in Lemma E.5, we utilize the tighter
34

---

Published as a conference paper at ICLR 2024
Analysis of f
Next, we turn to the term i. in (77b), Taking the norm gives the following inequality for some constant C,T T > 0 by applying Lemma G.4,
C
e (un ux)T (a ( ||
Using Lemma G.6 gives
(un Mk) M 3x((1
(x)) || 0014,1111 +1
Thus, 3n 3/0 1/2 1 ol V o(VVn +0 (innn 0 (nggshs Since Yn o(3n), YnPn (n + 1)6-9 where b < 0. Then, there exists some >> such that b < -8 0. Together with O(vn= log(n)) o(1). Therefore, we
log(s.) O(log(n)), we have O (VinBa' log(sn)
have
1/2 R(()) O. lim 3/
Analysis of (
Lastly, let's focus on the term ( We have
(0) n+1 = put1 0- (0) - (())
n+1
On 0" + 3n+1 [1, 00) J12(a)(Xx - 11 + M1 + 10.1)
+r + +rn
(0.2) + +nm
(0)
IntiJI: ((0) n - 1n-1 (0)
n+1 - AutidI R((0 1n-1J1p(a) + R!x))
(I Bn+1J 11 (0, 0²) + Br+ (12() B1+1(1 + +r
(0.1)
(0.2) + (0)
-(I+ (I+ 0 1) R!0))
(0.1) = -I++ 11) A + 1 (x) + Bn-1 (1 + +r(0.2) + 1//
0 1
)
where the second equality is from (53a), the third equality stems from the approximation of e JJ1. Then, we again use the definition kn.n A 1T (I + J1J and reiterate the above equation as
A (
D Bk+1 (0(3k+))L (0)
((3++1)
P 11138111111(044
+ Σ
Fk (0.1) + - )
k=1
DR... B (0,2)
k=1
A (
A (0.2) a+1
n+1
where ( = Σn k=
(0.2) and
(0.1)
D B (O(Bet))L)) (0) +0(3++1)
n+1
(80)
+
p (1 + - + A1z(a)4(())
(0.1)
k=1
35

---

Published as a conference paper at ICLR 2024
For n+1. follow the same steps from (74) (75), and obtain A olvBn).
Next, we consider (0.1) n+1 and want to show that A (0.1) ol /B.). Again, we utilize Mokkadem & Pelletier (2006, Lemma 6) for Á (0.1) and adapt the notation here for the case 7nn - o(3)).
Lemma E.9. For ( in the form of (80), assume 1|0, - 0- (w))) and |Ân ( O(xx) for the sequences Wny on defined in (E.1). Then, we have
A (0.1 = -(7 + (n + of V a.s.
(81)
Now need to further analyse on and tighten its big O form, starting from ó, that can finally obtain the big O form of || ( ||. The following steps are borrowed from the ideas in Mokkadem & Pelletier (2006, Section 2.3.2).
By almost sure convergence result lim, Or 0", have n A 0 a.s. such that can first set 6, = 1, and || A (0.1) = O g w + 3m + vm) Then, we redefine
8n- = B, w + tm + onv
and notice that it still satisfies definition E. Then, reapplying this 6, form to (81) gives
? + (m + o(v7))
and by induction we have for all integers 2 1,
A (0.1)
|| = 3, wh + 1nm8,1 + o(vTo).
Since hn (bb-a)k there exists ku a/2(a b) such that hn '1 om) and
| = 0 +(v7m)
(82)
Then, as suggested in Mokkadem Pelletier (2006, Section 2.3.2), we can choose wi O( / Bn log(Un) un) + 97m which also satisfies definition E. Then,
0n, - 00 = (1 + ( + 1
=0
v 3n log((n) + V Brr log(sn)+ + (17mBr-jtt) 10m-B-111+++mm77 +m Bn log (un)
o( 3n 7x)
=0(v Bn log(un) + (mm0,11t+1)
By induction, this holds for all & 2 1 such that there exists ko, (7m (l and O
0- O(v3, log(u,)). Equivalently, wn BBn log(un). Therefore, from (82) have
1 || = 0. log(u)) + o( = o(vTm).
Together with Á (0.2) = v3,),), we have 3,, 1/2 3/2 A (0) || = o( (nn + 1) such that
lim 3 1/1 n+1 =
Thus, we have finished the proof according to the proof outline mentioned the beginning of this part.
F DISCUSSION OF COVARIANCE ORDERING OF SA-SRRW
F.1 PROOF OF PROPOSITION 3.4
For any a 0 and any vector Rd, we have
x T TV (a)x= 1- x" (Voh((0))))) 166=13
(Vohie) 118m11 1)T
x dt.
36

---

Published as a conference paper at ICLR 2024
where the first equality is from the form of V
(1) (a) in Theorem 3.3. Let å e'(Voh(0")+ ((ba)) xx
with the dependence on variable left implicit. The matrix Uo(a), given explicitly in (11) positive semi definite, since X; E (-1,1) 1) for all É (1, ..................... N - 1}. Thus, the terms y" Uo(a)y inside the integral are non-negative, and is enough to provide an ordering on y (a(y with respect to a.
For any 02 0.
y Uo(a2Y
1
1+ X,
y T H Huu,,,HH
[02(1 + A,) + +1
1- X;
1
1 X; T H H
y
(a1(1 + +
1 1 X;
1 a A
H unu Hy Hy=y²Uo(0)
where the inequalityl3 is because a[1 + X1) 0 for all E (1.... .... N) and any a >> 0. In fact, the ordering is monotone in a, and y Ua(a))y decreases at rate 1/a² as seen form its form in the equation above. This completes the proof.
F.2 DISCUSSION REGARDING PROPOSITION 3.4 AND MSE ORDERING
We can use Proposition 3.4 to show that the MSE of SA iterates of (4c) driven by SRRW eventually becomes smaller than that SA iterates when the stochastic noise is driven by i.i.d. sequence of ran- (a)c, where e; is the i'th standard basis vector." 14 These diagonal entries are the asymptotic variance corresponding to the element-wine wise iterate errors, and for large enough we have e? v-(1) (ate, 2 E[OO, /0) Pn for all E (1,.... DD). Thus, the trace of matrix v (a) approximates the scaled MSF, that is Tr(V! (1) (a)) = E, all entries of V( go to zero as a increases, they get smaller than the corresponding term for the SA algorithm with i.i.d. input for large enough a, which achieves a constant MSE in the similarly scaled limit, since the asymptotic covariance is not a function of a. Moreover, the value of a only needs to be moderately large, since the asymptotic covariance terms decrease at rate 0(1/a²) as shown in Proposition 3.4.
dom variables. The diagonal entries of (()) (a) are obtained by evaluating cf (
(a)e, E( 0*) / Bi 1/3/// for large Since
F.3 PROOF OF COROLLARY 3.5
We see that (=(3 v for all a > 0, because the form of ( (a) in Theorem 3.3 is independent of a. To prove that (a) <, v (3) (0). it is enough show that v- v-3) (0), since (122) (a) < v--) (0) from Proposition 3.4. This is easily checked by substituting = 0 in 11,
(0),
for which (0) Un Substituting in the respective forms of (-(1) (0) and v- (0) in Theorem
3.3, we get equivalence. This completes the proof.
G BACKGROUND THEORY
G.1 TECUNICAL LEMMAS
Lemma G.1 (Solution to the Lyapunov Equation). If all the eigenvalues of matrix M have negative real part, then for every positive semi-definite matrix U there exists unique positive semi-definite
The inequality may not be strict when H is low rank, however will always he for some choice of x, since not a zero matrix. Thus, the ordering derived still follows our definition of <z Section I, footnote
d-dimennioonal vector of all zeros except at the i'th position which
37

---

Published as a conference paper at ICLR 2024
matrix V satisfying the Lyapunov equation MV + VM" 0. The explicit solution V is given as
M Ue
(83)
Chellaboina & Haddad (2008, Theorem 3.16) states that for a positive definite matrix U, there exists a positive definite matrix V. The reason they focus on the positive definite matrix U is that they require the related autonomous ODE system to be asymptotically stable. However, in this paper we don't need this requirement. The same steps therein can be used prove Lemma G. and show that if U is positive semi-definite, then V in the form of (83) is unique and also positive semi-definite.
Lemma G.2 (Burkholder Inequality, Davis (1970), Hall et al. (2014) Theorem 2. 10). Given a Mar- lingale difference sequence {M,,n) for 2 1 and some positive constant Op. we have
n
7
2/2
Σ M
S CGE.E
Σ M 11?
(84)
Theorem G.3 (Martingale CLT, Delyon (2000) Theorem 30). If Martingale difference array (Xnz) satisfies the following condition: for some > 0,
2+ [1 B 0, X R
E
(85)
sup
[ c0;
(86)
and
E
Xn, n.k
FA-1] 3 V,
(87)
km
then
X
dist. NO0.
(88)
Lemma G.4 (Duflo (1996) Proposition 3.1.2), For Hurwitz matrix H, there exist some positive
constants C, b such that for any n,
He S -bn bn
(89)
Lemma G.5 (Fort (2015) Lemma 5.8). For a Hurwitz, matrix A, denote by -r, r >> 0, the largest real part of its eigenvalues. Let positive sequence {in} such that lim, In 0. Then for any 0 < r' < r, there exists a positive constant C such that for any k < n,
II
[ + 7/ A)
S CCe C'E Eja0%
(90)
Lemma G.6 (Fort (2015) Lemma 5.9, Mokkadem & Pelletier (2006) Lemma 10). Let {in be
positive sequence such that lim, 7n = 0 and Σn Yi = 0c. Let ((n, n 2 0} be a nonnegative sequence. Then, for b > 0, p 2
limsup sup In" lim
p+l - Tek S T
1
supe
(91)
C(b,p)
k=1
for some constant C(b,p) O.
When O and define positive sequence {wa} satisfying wn 1/w1, = 1 + o(T,). we have
((wa), (o(ww),
if = O(w,),
nke bb
E4 Bee
(92)
en o(wn).
1=1
Lemma G.7 (Fort (2015) Lemma 5.10). For any matrices A, B,C,
|ABAT
CBC < || C[I] (1) All + [(CT)).
(93)
38

---

Published as a conference paper at ICLR 2024
G.2 ASYMPTOTIC RESULTS OF LINGLE-TIMESCEE SA
Consider the stochastic approximation in the form of
Zn+1 Zn + In+1 G(zn, Xn+1).
(94)
Let K₂ be the transition kernel of the underlying Markov chain {Xn] with stationary distribu- tion æ=z) such that g(z) _ [xx [G(z, X)] with domain O C IR.. Define an operator K for any function f N + R such that
(K (k+f((0) (t),(,
(95)
JEN
Assume that
C1. W.p.1, the closure {zn] is a compact subset of O.
C2. Yo >u/n", E (1/2, 1).
C3. Function g is continuous on O and there exists a non-negative C'l function w and a compact set K. C such that
Vw(22) 9(2) S 0 for all E O and Vw(z)" < 0f 2 & K:;
the set S _ {= Vw(z)" g(2) = 0} is such that w(S) has an empty interior; C4. For every there exists solution m, :N - Fd for the following Poisson equation
m² (i) m= (i) = G(2, i) -((=)
(96)
for any i E N; for any compact set C C O,
sup [I(K_ m= (+)]l + || (i) < 00 =EC,iEN
(97)
and there exist continuous function de, (0) such that for any 2, 2, E C,
sup
(I{,m))(i) (k (+)l S Φc ieN
==Il).
(98)
C5. Denote by- the largest real part of the eigenvalues of the Jacobian matrix Vg(2*) and assume r (==1)
C6. For every z, there exists solution Qz :N + Raxd for the following Poisson equation
Q2(1) - (k=Q=)()) = F(z, E)~m(=) (F(,,)))
(99)
for any E N, where
F(z, A
mz m=(mm= (i) (K=m))
(100)
jeN
For any compact set C C O,
sup
[1)((1) + II(K2Q=)(01 < <0
(101)
zEC.iEN'
and there exist p. Cc 0, such that for any 2, z' E C,
sup (((=Q=)()) (K= (+)l S -cllz =/1P.. REV
(102)
Theorem G.8 (Delyon et al. (1999) Theorem 2). Consider (94) and assume C1 C4. Then, w.p. lim sup,, d( ((zn, S) 0.
Theorem G.9 (Fort (2015) Theorem 2.1 & Proposition 4.1). Consider (94) and assume CI - C6.
Then, given the condition that 2n converges to one point z E S, we have
In 1/2 2²) dist. N(0, V),
(103)
2=000
where
(0=1) I+ Vo( + ((b=1) I+ Vo(z") V V+--0,
(104)
2
2
and
U
Σ VEN
Mi (1)m² (1) m (m) (1)7))
(105)
39

---

Published as a conference paper at ICLR 2024
G.3 ASYMPTOTIC RESULTS OF TWO-TIMESCALE SA
For the two-timescale SA with iterate-dependent Markov chain, we have the following iterations:
Zn++1 Zn ++BB 1 (Zas Yu Xn+1);
(106a)
Yn+1 = Yn + -n+1 (2(Z : Yn: Nn: Xn+1), with the goal of finding the root (x", such that
(106b)
(z , = (Gi XX] 0, 92(z', -x-= (G2(", y"" x)]] 0. (107)
We present here a simplified version of the assumptions for single-valued functions G1, G2 that are necessary for the almost sure convergence result in Yaji & Bhatnagar (2020, Theorem 4). The original assumptions are intended for more general set-valued functions G1, G2.
(B1) The step sizes Bn, _ n and Yn - n n= where 0.5 <a <a<<a<b <bss..
(B2) Assume the function Gı y, X) is continuous and differentiable with respect to z. y. There exists positive constant L1 such that ||G (z, X)] S [1 + ||||| + Iyll) for every z Rd, , E R X E N. The same condition holds for the function G2 as well.
(B3) Assume there exists function p IR Hd such that the following three properties hold: (i) [|{())]| < L2 + ||z]]) for some positive constant L2; (ii) the ODE y = 92(2. y) has globally asymptotically stable equilibrium {(z) such that 92(z, p(z)) 0. Additionally,
let ń (z) _ 9i (z, p(z)), there exists a set of disjoint roots A - {z" =z((z") = 0}, which is the set of globally asymptotically stable equilibria of the ODE à = 91 (z).
(B4) {Xn Jn20 is an iterate-dependent Markov process in finite state space M. For every n 0, P(Xn+1 = -jlzm Ym: Xm. I m S n) P(Xn+1 j zn. Ya, Xn i) Pi [.n. ynl. where the transition kernel P(z. y| is continuous in y. and the Markov chain generated by P(z. y| is ergodic so that admits a stationary distribution π yz. and π (z",, .((2)) μ..
(B5) sup MuPn2o(12z |. + |ly II) < 0o a.s.
Yaji & Bhatnagar (2020) included assumptions AI A9 and All for the following Theorem 1.10. We briefly show the correspondence of our assumptions (B1) - (B5) and theirs: (B1) with A5, (B2) with A1 and A2, (B3) with A9 and A11, (B4) with A3 and A4, and (B5) with A8. Given that our two-timescale SA framework (106) excludes additional noises (setting them to zero), A6 and A7 therein are inherently met.
Theorem G.10 (Yaji & Bhatnagar (2020) Theorem 4). Under Assumptions (BI) (B5), iterations (a,yy) in (106) almost surely converge to a set of roots, i.e., (z) + +U (z", p((z)) a.s.
H ADDITIONAL SIMULATION RESULTS
H.1 BINARY CLASSIFICATION ON ADDITIONAL DATASETS
In this part, we perform the binary classification task in Section 4 additional datasets, i.e.. a9a (with 123 features) and splice (with 60 features) from LIBSVM (Chang & Lin, 2011). Figure 4 provides the performance ordering of different a values, and we empirically demonstrate that the curves with 2 5 still outperform the i.id. counterpart. Additionally, Figure 5 compare cases (i) (iii) under both a9a and splice datasets, and case (i) consistently perform the best.
H.2 NON-CONVEX LINEAR REGRESSION
We further test SGD-SGGDD-RRR SRRW and SIB-SRRW algorithms with a non-convex function to demonstrate the efficiency of our SA-SRRW algorithm beyond the convex setting. In this task, we simulate the following linear regression problem in Khaled & Richtárik (2023) with non-convex regularization
N ( +
d
03
min OER4
f(0)
A N
(108)
0
+1
1=1
40

---

Published as a conference paper at ICLR 2024
CASE (i): a 0.8, b 0.9
CASE (i): a 0.8, b 0.9
10A
= 0|0, 0 1
10
MSE El 1-12
10a
MHRW (a 0) a=1
MHRW
10-1
Q'1 1
MSE
g=5
a=
a=
Q 10
10-1
a 20
sampling
M.d. sampling
10
2
102
10a
104
10a
10a
10a
10a
Number of steps (n)
Number steps (n)
(a) SGD-SRRW. a9a
(b) SGD-SRRW, splice
Figure 4: Simulation results with various values in a9a and splice datasets.
10
10a
MSE E -0'
A [0, -0
MSE #18.. -P'T
10-1
20
CAST [00 0.8.
CABE -0 2.5
CASE 0.
CASt 112e 6.9.000...mm
CASE 04,
CASE 010 1.000
10
10'
10a
10"
10a
10
10a
10'
16
Numbar of steps (n)
Number of stops (n)
Number of steps (n)
(a) 5, SRRW, a9a
(b) 10, SGD-SRRW, a9a
(c) 20, SGD-SRRW, a9a
10a
MSE F00,100
10a
110,
MSE FTe.
10-1
10
CASE: (/sa
(ilia
0.5.
5.9
10
CASE (0:a b5
CASE -.8.b
CARE c10 1.0=0.0
CASE 1.b-
10.
10a
10a
10a
10*
100
10
10'
10a
Number of steps (n)
Number steps
Number of stops (n)
(d) 5, SGD-SRRW, splice
10, SGD-SRRW, splice
(f) a 20, SGD-SRRW, splice
Figure 5: Performance comparison among cases (i) (iii) for a datasets.
{5, 10, 20} in a9a and splice
where the loss function (0) =IsT vell 2 and x = 1, with the data points ((s,, y:) hew from the ijenn/ dataset of LIBVIM (Chang & Lin, 1). We still perform the optimization over the wikiVote graph, done in Section 4.
The numerical results for the non-convex linear regression taks are presented in Figures and 7, where each experiment is repeated 100 times. Figures 6a and 6b show that the performance ordering across difffrent a values is still preserved for both algorithms over almost all time, and curves for a 2 outperform that of the i.i.d. sampling (in black) under the graph topological constraints. Additionally, among the three cases examined at identical values, Figures 7a 7c confirm that case (i) performs consistently better than the other two cases, implying that case (i) can even become the best choice for non-convex distributed optimization tasks.
41

---

Published as a conference paper at ICLR 2024
CASE (i): a 0.8, b 0.9
CASE (i): == 0.
10
10-1
MSE El0n 1
MHRW 0)
MSE F10,
MHRW (a
a=1
10
am1
10
0=5
a 5
a 10
a= 20
sampling
10
l..dd sampling
102
10
10a
10a
102
10a
Number of steps (n)
Number of steps (n)
(a) SGD-SRRW
(b) SHB-SRRW
Figure 6: Simulation results for non-convex linear regression under case (i) with various values.
10-1
10-1
(10-a -10000
MSE [10. B
MSE =1
MSE F
10
10-1
CAGE =08,0=00
b-0.
10a
10a
10f
10a
10
10a
10
10
10'
10*
10
Number of steps (n)
Number of steps (n)
Number of steps (n)
5, SGD-SRRW
10. SGD-SRRW
(c)
20, SGD-SRRW
Figure 7: Performance comparison among cases (i) (iii) for non-convex regression.
42


Reviews:
[{"review_id": "IbKNdu8Khy", "reviewer": "Reviewer_XrEW", "summary": "This paper introduces a new distributed stochastic optimization algorithm, where the random walk guiding the sampling of gradients across the network uses Self-Repellent Random Walk (SRRW), a recently introduced family of nonlinear Markov chain. For MCMC sampling on a graph, SRRW has been shown to achieve a $O(1/\\alpha)$ decrease in the asymptotic variance [Doshi et al, ICML 2023], where $\\alpha$ is a hyperparameter of the chain; roughly speaking, given any base Markov chain, SRRW works by preferring transitions to states that were less visited in the past, and the larger the $\\alpha$, the stronger this preference. Building on this insight, the authors in this paper use SRRW as the \"token\" gradient sampler in a distributed stochastic optimization setting.", "questions": "There are some questions that I hope the authors can address.\n1) Could the authors comment a little bit more on the stability of the iterates? This is assumed to always hold, but as the authors point out, practical tricks are required to ensure this, in which case the theoretical analysis might also need tweaks.\n2) Are there any tradeoffs in picking $\\alpha$? Should $\\alpha$ always be as large as possible, or will that affect other aspects of the algorithm, e.g. stability?\n3) While the analysis is on asymptotic covariance, could the authors comment on the likely finite-time convergence rate behavior of their SRRW-SA algorithm, and whether improvements (due to the SRRW) can be also shown in terms of finite-time convergence rates?\n4) The authors suggest that $\\beta_n = o(\\gamma_n)$ is the best step-size choice if a $O(1/\\alpha^2)$ decay rate in the asymptotic covariance is desired. However, if faster convergence is to be desired, a larger learning rate (i.e. larger $\\beta_n$) should always be picked, i.e. we would want to pick the maximal possible step-size required by the assumptions in the paper, i.e. $\\beta_n = O(1/n^{0.5+\\epsilon})$ for some $\\epsilon > 0$ as close to 0 as possible, in which case $\\gamma_n$ can at best match the step-size of $\\beta_n$, meaning that we can only get $O(1/\\alpha)$ in the asymtotic covariance decay again. Could the authors comment on this possible issue?\n5) It would be nice if the authors provided some intuition as to why the $\\beta_n = o(\\gamma_n)$ step-size ratio can yield the $O(1/\\alpha^2)$ rate. Moreover, it would be nice if the authors spelled out precisely the dependence on the difference between the step-size exponents in their asymptotic rates (i.e. if  $\\beta_n = n^{-b}$ and $\\alpha_n = n^{-a}$, how the rate actually depends on the difference between $a$ and $b$). If this difference does not affect the asymptotic rate, it would be nice to provide insight into how this difference might play out in practice.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contributions are as follows. Very interestingly, the authors show that given the \"right\" step-size setting (i.e. when the step-size for the optimization parameter $\\theta_n$, $\\beta_n$, is $o(\\gamma_n)$, where $\\gamma_n$ is the step-size for the update of the weighted empirical distribution $x_n$), the asymptotic variance of the $\\theta_n$ (defined as $\\frac{\\theta_n - \\theta^*}{\\sqrt{\\beta_n}}$) actually decays with the rate $O(1/\\alpha^2),$ which is better than the $ O(1/\\alpha)$decay rate for the (un)weighted empirical distribution $x_n$ in [Doshi et al., 2013]. An important result the authors show is that the asymptotic step-size ratio between $\\beta_n$ and $\\gamma_n$ is key; when $\\gamma_n = \\beta_n$ or wheren $\\gamma_n = o(\\beta_n)$, the asymptotic variance is only $O(1/\\alpha)$. The key technical tool that achieves this is a novel analysis of two-time scale SA with controlled Markov noise. The theoretical results are also well-supported by simulation results.\n\nOverall, this is a well-written paper and the idea of adding SRRW to distributed stochastic optimization is nice. In addition, the theoretical result about the influence of step-size ratio on the asymptotical covariance decay rate is also very interesting.", "weaknesses": "see questions below:", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FmHK5reZac", "reviewer": "Reviewer_MZm1", "summary": "The present paper consider a family of stochastic algorithms of the following form. There exists a finite space $\\mathcal{N}$ and some kind of \"random walk\" $\\{X_n\\}_{n\\in\\N}$ over this set. One then takes $\\theta_0\\in\\mathbb{R}^d$ and a function $H:\\mathbb{R}^d\\times \\mathcal{N}\\to \\mathbb{R}^d$ and sets \n\n$$\\theta_{n+1} = \\theta_n + \\beta_n\\,H(\\theta_n,X_n).$$\n\nOne particular example is when $X_n\\sim \\mu$ and $H(\\theta,i) = -\\nabla f(\\theta,i)$ for some $f$. Then the above is basically a form of stochastic gradient descent for the function\n\n$$F(\\theta) :=\\sum_i \\mu_i\\,f(\\theta,i).$$\n\nThe authors say that $X_n$ may be thought of as a \"token\", so they are considering token distributed optimization methods. \n\nThe authors are especially interested in the case where $X_n$ is a stochastic process called \"self-repellent random walk\". Basically, this kind of RW have asymptotic distribution $\\mu$, but they are designed to be less likely to jump to states that have already been visited many times. A recent paper by Doshi et al. showed that such random walks lead to smaller-variance Monte Carlo estimates of expectations with respect to $\\mu$. In fact, the variance in this case decreases like $\\alpha^{-1}$, where $\\alpha>0$ measures the amount of self-repulsion. \n\nThe present paper builds on this to show a remarkable result. Namely, under suitable conditions, $\\theta_n$ converges to a fixed point $\\theta_*$ (in expectation) of the iteration, and $\\theta_n - \\theta_*$ has variance decrease when $\\alpha$ grows. In fact, the variance goes down like $1/\\alpha^2$ for large $\\alpha$. In particular, this implies that self-repellent walks are \"even better\" for optimization or fixed point computations than for Monte-Carlo integration. However, this main result requires on tuning $\\beta_n$ to be smaller than a parameter describing the rate of change of the \"self-repulsion measure\". In fact, the authors show that, when this is not the case, it may be that a large $\\alpha$ will not help at all. The paper's proofs build on Doshi et al and rely on stochastic approximation methods.", "questions": "I only have one very open ended question: is there any hope of getting finite sample bounds?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper describes a surprising phenomenon -- even considering the paper by Doshi et al. It gives precise asymptotic results. Their small simulation study observe gains in finite time. The paper is very clear and convincing.", "weaknesses": "All results are asymptotic. It is not clear (theoretically) whether there are gains for finite time, before eg. the token can visit most elements of $\\mathcal{N}$. The analysis requires some *a priori* assumptions about the ODE invoked for stochastic approximation. The analysis is heavily indebted to Doshi et al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gGSxCp1x1J", "reviewer": "Reviewer_81Sf", "summary": "This paper deals with distributed stochastic optimization, with tokens sampled by self-repelling Markov chain. The authors proved the law of large numbers and central limit theorem for the optimization iterate errors, which are refinements of recent work of Doshi et al. The proposed algorithm achieves $1/\\alpha^2$-rate, and the theoretical results are corroborated by the empircal study.", "questions": "See the Weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper studies rigorously a distributed stochastic optimization using self-repelling random walks. The paper is well-written, and I enjoyed reading it. I have also checked most theoretical results, and they appear to be correct. The rate $1/\\alpha^2$ also appears to be new.", "weaknesses": "The paper is mostly motivated by the recent progress of Dochi et al., and it is not clear what is the \"main\" novelty of this paper compared to the previous work (fundamentally). It seems to me that most results are refinements of Dochi et al. (while I agree that the setting is slightly different.) The authors may add a paragraph to highlight the main \"technical\" novelty of this paper. \n\nAlso the parameter $\\alpha$ measures the \"heaviness\" of the self-repelling random walk, which is basically a hyper-parameter. It seems to be a bit strange to quantify the errors using $Poly(1/\\alpha)$ (provided that one sends $\\alpha \\to \\infty$ and I do have concerns on the real application in this regime). Also the idea of using self-repelling random walk to accelerate optimization is not new, see https://arxiv.org/abs/2005.04507 (in which it was shown to outperform many existing algorithms.) The authors may think of citing the work and some references therein.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zoaIb1mXn0", "reviewer": "Reviewer_DxLx", "summary": "This paper studied a family of distributed stochastic optimization algorithms where gradients\nare sampled by a token traversing a network of agents using the Self-Repellent Radom Walk (SRRW).\n\nThis paper generalized the previous SRRW by introducing an additional iterate to update the empirical distribution so the resulting algorithm shares a similar pattern with the two-time-scale stochastic approximation (SA).\n\nThe author then provides some theoretical understanding of the proposed algorithm, including \n- (1) almost surely convergence of two iterates \n- (2) central limit theorem (CLT) of parameter $\\theta_n$ \n- (3) order analysis on the asymptotic variance matrices for three different time-scales choices.", "questions": "1. Under the paragraph below (3), the author tries to explain why SRRW gets its name. More specifically, they said `` if node $j$ has been visited more often, so far, the entry $x_j$ becomes larger (than target value $\\mu_j$ )’’. I didn’t understand the logic behind it. If node $j$ has been visited more often, I think $x_j$, as the coordinate of a distribution vector, should be close to $\\mu_j$. I can’t tell whether $x_j$ is larger than $\\mu_j$ or not.  However, I acknowledge that the nonlinear kernel in (3) would encourage the algorithm to visit the states that are less visited, based on its expression.\n\n2. The newly introduced iterate in (4b) generalizes the original algorithm and allows us to treat the resulting algorithm as a two-time-scale SA. However, I didn’t see much motivation to introduce the new iterate. Could the author elaborate more on the motivation?\n\n3. If we set $\\alpha=\\infty$, from (6), the variance matrix would be zero. Could I say, in this case, $x_n$ actually converges to $\\mu$ at a faster rate than $\\gamma_n$ so that the CLT degenerates to zero? How to explain the intuition behind it? \n\n4. From the simulation, it seems the larger $\\alpha$, the faster convergence. Is there any suggestion for a practical choice of $\\alpha$?\n\n5. If the $\\alpha$ is also updated, for example, we use $\\alpha_t$ at the iterate $t$ that increases at a carefully selected rate in advance (or perhaps could be updated using a third iterate). Can we accelerate the convergence rate of $\\theta_n$ so that its mean square error is faster than $\\beta_n$?\n\nI will increase my point to 8 if most of my questions are addressed.\n\n------------------------------------ Post rebuttal --------------\n\nThanks for the authors' clarification.  Most of my concerns and questions are well addressed, so I increase my point to 8.\nHowever, there are still two points I don't agree with the author.\n\nOne point I disagree with is that I think when $\\alpha \\to \\infty$, the kernel (3) is still well defined.\nIn this case, I think $K_{ij}(x) = 1$ if and only if $x_j/\\mu_j = \\arg\\min_{l} x_l/\\mu_l $.\nAs you can see, this kernel is reduced to a deterministic transition. \nI guess this reduction makes the system no longer random so that the CLT degenerates.\nOne property of this generation is that the variance matrix would converge to zero.\nThis actually is a good property from my perspective because it means that one could get a convergence rate faster than the step size.\n\nLet's do a simpler thought experiment. Let $X_t \\sim \\sqrt{\\beta_t} \\cdot N(0, c_t )$.\nIf the variance $c_t$ is non-zero (so that $c_t \\to 1$ w.l.o.g.), then the MSE of $X_t$ is dominated by the variance and is of order $\\beta_t$. \nIf the variance is (nearly) zero (say $c_t \\to 0$), then the MSE is dominated by a higher-order term and we have $E |X_t|^2$ converge faster than $\\beta_t$.\n\nBack to this paper, I guess the counterpart of $c_t$ in this paper is $1/\\alpha$. So, if we let $\\alpha \\to \\infty$, we would have $c_t \\to 0$. This is the reason why I ask whether increasing $\\alpha$ would fasten the convergence. The author's response works only when the optimal $\\alpha^{\\star}$ exists and is finite. However, the particular case I am interested in is when $\\alpha^{\\star} = \\infty$.\nI think that exploring the case where  $\\alpha^{\\star} = \\infty$ detailedly is worth a more detailed examination. \nIt is fine not to discuss this in this paper.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and solid. I like reading the paper.\n\nThe paper contains rich theoretical analysis, which investigates deeply about the properties of proposed methods. The acceleration effect of the proposed method is indeed new and interesting (at least to me).\n\nMost of the proof in the appendix seems to be correct, but I didn’t check very carefully.\n\nThe simulation validates the theoretical finding in the paper.", "weaknesses": "A concern in my mind is that the paper assumes $X$ takes values in a finite state space. \nThe decentralized optimization where only a single agent is active each time is a particular example.\nAre there any other examples where $X$ takes finite value?\n\nIn my opinion, for a general SA method, the randomness or the noise could be various. \nNote that the Poisson method used in the proof is not limited to discrete randomness.\nIs it possible to extend the analysis to a more general setting where $X$ could be a continuous random variable?\nIf not, where is the main difficulty?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)