Efficiency Ordering of Stochastic Gradient Descent
Authors: Jie Hu
Vishwaraj Doshi
Do Young Eun
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic Gradient Descent
Asymptotic Analysis
Efficiency Ordering

Abstract: We consider the stochastic gradient descent (SGD) algorithm driven by a general stochastic sequence, including i.i.d noise and random walk on an arbitrary graph, among others; and analyze it in the asymptotic sense. Specifically, we employ the notion of `efficiency ordering', a well-analyzed tool for comparing the performance of Markov Chain Monte Carlo (MCMC) samplers, for SGD algorithms in the form of Loewner ordering of covariance matrices associated with the scaled iterate errors in the long term. Using this ordering, we show that input sequences that are more efficient for MCMC sampling also lead to smaller covariance of the errors for SGD algorithms in the limit. This also suggests that an arbitrarily weighted MSE of SGD iterates in the limit becomes smaller when driven by more efficient chains. Our finding is of particular interest in applications such as decentralized optimization and swarm learning, where SGD is implemented in a random walk fashion on the underlying communication graph for cost issues and/or data privacy. We demonstrate how certain non-Markovian processes, for which typical mixing-time based non-asymptotic bounds are intractable, can outperform their Markovian counterparts in the sense of efficiency ordering for SGD. We show the utility of our method by applying it to gradient descent with shuffling and mini-batch gradient descent, reaffirming key results from existing literature under a unified framework. Empirically, we also observe efficiency ordering for variants of SGD such as accelerated SGD and Adam, open up the possibility of extending our notion of efficiency ordering to a broader family of stochastic optimization algorithms.

Efficiency Ordering of Stochastic Gradient Descent
Jie Hu
Vishwaraj 2
Do Young Eun'
Department of Electrical and Computer Engineering, North Carolina State University Data Science and Advanced Analytics, IQVIA
jhu298ncsu. edu
vishwaraj doshi@iqvia. com dyeunOncsu. edu
Abstract
We consider the stochastic gradient descent (SGD) algorithm driven by a general stochastic sequence, including i.i.d noise and random walk arbitrary graph, among others; and analyze it in the asymptotic sense. Specifically, we employ the notion of "efficiency ordering', well-analyzed tool for comparing the performance of Markov Chain Monte Carlo (MCMC) samplers, for SGD algorithms in the form of Loewner ordering of covariance matrices associated with the scaled iterate errors in the long term. Using this ordering, we show that input sequences that are more efficient for MCMC sampling also lead smaller covariance of the errors for SGD algorithms in the limit. This also suggests that an arbitrarily weighted MSE of SGD iterates in the limit becomes smaller when driven by more efficient chains. Our finding is of particular interest in applications such as decentralized optimization and swarm learning, where SGD is implemented a random walk fashion on the underlying communication graph for cost issues and/or data privacy. We demonstrate how certain non-Markovian processes, for which typical mixing- time based -on-asymptooic bounds intractable, outperform their Markovian counterparts in the sense of efficiency ordering for SGD, We show the utility of our method by applying it to gradient descent with shuffling and mini-batch gradient descent, reaffirming key results from existing literature under a unified framework. Empirically,
also observe efficiency ordering for variants of SGD such as accelerated SGD and Adam, open up the possibility of extending our notion of efficiency ordering to broader family of stochastic optimization algorithms.
Introduction
Stochastic gradient descent (SGD) is widely used in machine learning, signal processing and other engineering fields to solve the optimization problem
8" = arg min dee
f(0) A
Σ F(B,
(1)
where O C Rdd is some closed and convex set, and F(:;)) RRd >R
R. for E [m]] A { n)
smooth functions on θ not necessarily convex, such that their summation f RR - IR exhibits minimizer satisfying vf(0")=() The update rule of the iterative SGD scheme of the form
θ Proje (0, - F,F (0,, X,+1)),
(2)
where 7/2 is the step size that can be constant or diminishing as oo, Proje is projection operator the constraint set O and (Xr)r20 is some sequence taking values [n]. This sequence is often generated in a stochastic manner, and samples can be drawn from temporally independent and identically distributed (i.i.)) random variables that are either uniformly distributed over [n] [60 14], or leverage importance sampling techniques for variance reduction [2] {X1h20
'Equal contributors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

can also be constructed by repeatedly shuffling over all possible states without repetition leading to faster convergence than stochastic counterparts drawing i.i.d samples from [1]] [64] 32
Random Walk Stochastic Gradient Descent (RWSGD): Some applications observe restricted access to the state space, such as decentralized optimization 66 71 46), where communication
occurs between nodes in network to collaboratively solve the optimization problem ( For instance, disease classification in confidential clinical swarm learning 669 considers peer-to-peer networks due to the highly private nature of medical data. In such a setting, the random sequence {Xt, (r2 usually realized as a Markov chain on general graph E().E) that only samples local gradients of the nodes in A [r]] and traverses the network via edges connecting them without divulging the update history or its own gradient. The randomness of the communication path ensures that the
compromised node can not easily leak the data of its neighbors [46]
Apart from the privacy concern, such dynamics are also employed in swarm learning/optimizztion
in robotics [17 and wireless sensor networks [43] due to their low communication cost and asyn- algorithms for
chronous nature. The need for data privacy and demand for communication-efiiii
decentralized optimization has spurred the study of RWSGD algorithms in recent years [57 34 67].
with the underlying Markov chain in the form of Metropolis- Hasting random walk (MHRW) 48
Common analytical approach- Finite time bounds based mixing time:
Most of the cxisting
works analyzing iteration (2) provide so-called finite-time upper bounds on expected error in either
the objective function (f)( f(("),. where Og is some weighted average of the iterates, or its
gradient [ (O.) and are used to infer the convergence rate of the iterate sequence [57 25 67].
For diminishing step sizes in- = L with a E (0.5, 1) the upper bound on [[[ reads as
max {M, 1/ 1og((1))))
E|| V f S O
24 Here, B E (0, 1) is the second largest eigenvalue modulus (SLEM) of the underlying Markov chain's 's transition matrix and is related to its mixing time property, since smaller SLEM leads to faster mixing of the Markov chain [18] 44). On the other hand, M > is usually a quantity proportional to the local gradients evaluated at the minimizer, their upper bound. Both the gradient information and the mixing time play key role in quantifying the convergence rate derived from this upper bound, and the mixing time is especially important since it hints that convergence rate of the SGD algorithm can potentially be accelerated using faster mixing Markov chains for the input driving sequence. It has also been noted that the inherent correlation of the underlying random walk has to be addressed in any analysis concerning Markov-chain-drive driven gradient descent [67]. The mixing time technique, by capturing the rate at which the chain converges its stationary distribution 18
and similar form for (0.) f((*)] as well 667
is one way of doing so.
In addition to the afore- mentioned mixing time, another widely used metric for characterizing the second order properties of Markov chains is the asymptotic variance (AV). For any scalar valued function
Alternative approach- Asymptotic analysis and efficiency ordering:
[m]] - R, the estimator fa (g) A E s(X)), associated with an irreducible Markov chain {Xrrr20 with stationary distribution π, is the average of the samples of g(-), obtained along the chain's 'ss sample path up to time & > 0. The AV of the Markov chain, denoted by xx (g). is then defined as the the limiting variance of the estimator; that is,
(x)
A lim t. (a)( tox
For all functions g(-) satisfying Ex (gg) < 0o, the AV is associated with the Central Limit Theorem (CLT) for any Markovian kernel on a finite state space, as the variance of the normally distributed estimates in the limit [61 35 18). More formally, we have
(p)( - E (2)
dist
N(0, M(0,0x(()) (o)).
smaller AV means that fewer samples are required post mixing of the chair in order to obtain a desired accuracy- in some sense quantifying the chain's 's efficiency.
2 "One complete pass over the entire set [n] is typically called an epoch. Shuffling can refer to passing over [v]] in the same order for every epoch (single shufiling), or in a random order (random shufiling). We only need the step size to O(t but we omit the O(-) notation for simplicity. We also consider a slightly more general case, allowing for a = as well.
'Acheveed by employing bum-in period get rid of the correlation with the initial state 29

---

Both the AV and the mixing time of a Markov chain are very strongly related concept In fact, the AV has an upper bound in terms of the SLEM, which decreases as the SLEM gets smaller (chain mixes faster) [50] However, an ordering of the SLEM between two Markov chains does not imply an ordering of their AV, as we shall demonstrate later in Section | for a special case. Both of these second-order properties therefore lead to different notions of optimality; and the comparison of two chains based on their AV leads to the concept of efficiency ordering [50], where we say that a chain is more efficient than the other if it has a smaller AV, uniformly over all functions g [Tl] + IR
As mentioned earlier, the common intuition asserted by finite time bounds such as (3) is that Markov chains with smaller SLEM lead to faster conver- gence of the SGD iteration 22 to the minimizer 67 77. We put this logic to test by simulating the RWSGD algorithm with three different reversible Markov chains (w.r.t. uniform stationary distribu- tion) as the stochastic inputs the MHRW, a modifi- cation of MHRW, which is also shown in Appendix I [ to be more efficient than MHRW, and the so- called 'fastest mixing Markov chain' (FMMC) as defined in [16] as the Markov chain obtained by minimizing the SLEM over the entire class of re- versible chains for given graph topology. We employ RWSGD to minimize a quadratic objective function for two underlying graphs. The exact de- tails of the setup are deferred to Appendix [1]. and our numerical results in Figure [ show that even though the FMMC is theoretically guaranteed to have the smallest SLEM (3, for iE 21, 3}) of the three reversible chains simulated, it is the worst per- forming one with largest mean square error (MSE). Although MHRW and Modified- MMRR share the same SLEM in the lower plot of Figure they still have performance differences. This is contradic- tory to the intuition derived from 33. and could be attributed to the finite time results providing upper bounds for all times > O, which may therefore not necessarily be tight. On the other hand, the performance of the chains seem to be ordered according to their AV (a for i E {1, 2,3)) evaluated for a test function. This lends credence to developing techniques based on AV, for judging the performance of different stochastic inputs for SGD, as possible alternatives to using SLEM as the sole performance metric.
Graph Ci
0.50
0:30
0:50
P1, 00117
0:31
P2. -0.868.. oj 00131
6:25
P3, -3.7120 of -0.18
0.2
Graph 02
P1. 9: 0.500, of 0.050
P2, Pg 0.500.00 oj - 0.006
0.408.0
0.057
33
02
SGD Iteration
Figure 1: Comparison of MHRW (PI), Modified-MHRW (P2) and FMMC (P3) as stochastic inputs for RWSGD on two differ- ent graphs Gi and G2-
The asymptotic variance also appears in the CLT for stochastic approximation (SA) algorithms [T]21], though this time not directly as the variance in the limit, but as a component of the limiting covariance matrix of the scaled iterate errors. Recent works [2 [5 point out that the covariance matrix itself is of special interest, and typically contains more information than the non-asymptotic MSE bounds [51]. In the sense of SGD algorithmss, we will show in Section B that it embeds explicit information of the exact rector-valued gradient evaluated at the optimizer as well as the entire spectrum of the transition matrix; as opposed to the upper bound M of the gradients and only the second largest eigenvalue modulus commonly found in mixing time based non-asymptotic bounds. has been suggested (20 23), and also proved for the special case of linear SA (1I. that the covariance matrix emerging out of the CLT dominates as a leading term of the Enite-time MSE bounds. This also holds true for finite-time bounds on weighted MSE for any preferred weight; the weighted MSE being utilized in fields such as wireless MIMO (68] and process optimization [30]. Overall, while finite-time bounds have enjoyed great success in the literature, the potential for performance gains out of the asymptotic analysis of SGD algorithms have remained largely unexplored.
We employ asymptotic analysis to propose general framework that offers seamless connection between AV the MCMC literature with efficiency ordering and covariance matrix the SGD algorithms. Our framework can be used to design different random walk variants and also to systematically compare the existing sampling methods in the SGD iteration with diminishing step
Contributions:
$ For reversible Markov chains, the AV can be written explicitly as an increasing function of every eigenvalue of the transition matrix [18]. while the mixing time is related to the SLEM mentioned earlier.
3

---

size. not just limited to random walks. In particular, we show that any two random walks following an efficiency ordering have their covariance matrices Loewner ordered, including non- -an-Markov stochastic processes versus its Markovian counterpart, which defies any mixing-time (SLEM) based analysis. Such ordering can be harnessed into improving the accuracy of SGD iterates, which implies a reduction in the weighted MSE with arbitrary weights. Moreover, via a specific augmentation of the state space, we are able to analyze SGD for both single and random shuffling and show the efficiency of shuffling over i.i.d sampling for set of objective functions that may not satisfy "Polyak-Lojasieww
inequality'. We further extend such comparison to mini-batch SGD algorithms. Lastly, we present numerical results where the efficiency ordering via asymptotic analysis tends to hold over all time periods and input sequences with higher efficiency have smaller errors in SGD.
2 Modeling setup
We use lower case, bold-faced letters to denote vectors (v R and use upper case, bold-faced letters to denote matrices (M E Rdxd). ). || llz denotes the 1 norm for vectors or 2-norm for matrices. We use Vf(.) Jacobian matrix of vector-valued function f(-). and V²g(+) as Hessian matrix of scalar-valued function g()). We let Vog(O, (f, X) be the gradient of the scalar-valued function g(, X) with respect to 0 and omit the subscript 0 for simplicity. Loewner ordering of matrices is denote by 'Sy' such that A St B < x²
Basic notations:
B)x S for any IR The term Tr(A) denotes the trace of matrix A, and let (.), be the indicator function. We write (N0,, V) to represent multivariate Gaussian distribution with zero mean and covariance matrix V. For connected and undirected graph G(V, E) with node set V and edge set E, we use [(i) for the set of neighbors of node i E V and d _ [d1, d2, ... dn)" I for the degree vector where d; = (N))
SGD algorithm with arbitrary input sequence: We consider random walks {Xe h22 for which the limit म. - lim,-rox: Et= [xx=(() exists almost surely and is positive for all i E [m]. with [ denoting the limiting stationary distribution. This is trivially satisfied via strong law of large numbers (26] when X, for each & > 0 are i.idd random variables with distribution л over [n], and via the ergodic theorem (18) when {X, J:20 is an irreducible, aperiodic and positive recurrent (ergodic) Markov chain. Note however that this way of defining the stationary distribution π allows for the input sequence {X1)120 to be more general, possibly being non-Markov on [n]. Then, we can use to rewrite the objective in ( as
((0)
F(O,i) Ex-x [G(0, X)],
where function G( A
F(0, i) for any AE iE [m]. The generalized update rule then becomes
21,, B.t1 = Proje (0. . VG X++1))
(7)
This change of notation allows us consider input sequences having possibly non-uniform stationary distributions, and is a version of importance sampling for RWSGD schemes, as in (7]. For example, the iteration (7) with the input sequence generated from MHRW with uniform target distribution π = 1/n will reduce down to (2) with G(O, i) = F(0,0) i) for all 0 E e, i E [n]. If the input sequence is instead simple random walk on a connected graph 9(V,8) E) with V [n]] we have x d, and
G(O, 1'd F(O, i) for all 0 E O, i v nd.
Asymptotic covariance matrix. We now quickly review the multivariate CLT for Markov chains, since it is natural way to introduce the asymptotic covariance matrix, used heavily throughout the paper. For any finite, irreducible Markov chain (Xeht20 with stationary distribution π, its estimator is defined as (e( A Di g(Xx) for any vector-valued function g [n] + I Then, the ergodic theorem 18 19
states that for any initial distribution and any g(-) such that
Ex (g) = Eie(n) g(i)T, < oo, we have (e(g)
a.s. (g). Similarly to the asymptotic variance
x (g) for a scalar-valued function g(.), we can also define the asymptotic covariance matrix Ex (g) for vector-valued function g(-).
tox 1 }
Σx x (g) A lim t- Var(fx(g) = lim 1+000
. ((AA)))
(8)
'In practice, knowing up multiplicative constant is enough converge the optimal point.

---

where 4, - E (g().) - Ex (g)). The associated multivariate CLT is then given as follows.
Theorem 2.1 (Chapter
19
For any function g [ni] Rd that satisfies Ear (g²)) < oo, have
Vt (ā) (g))
dist
NO0 Ex(g))
In the next section, we will show how the the asymptotic covariance matrix Ex()) also appears as part of the CLT result for SGD algorithms.
3 Efficiency Ordering of SGD Algorithms
In this section, we present our main result concerning the performance comparison of different SGD algorithms to solve ( We first begin by stating our assumptions on the objective function and the stochastic input sequence, providing CLT result for SGD algorithms, and analyzing the covariance matrix arising therein. We then introduce the notion of efficiency ordering of Markov chains in the context of MCMC sampling, and form the connection with covariance matrices as our main result in Theorem 3.6
For the rest of this section we assume that the functions F(.,t) (possibly non-convex), the summands of the objective function in I and the input process {Xx, h12 for the SGD iteration satisfy:
(A1) The step size is given by Th- t for a E (1/2,
(A2) There exists a unique minimizer 6* in the interior of the compact set θ with Vf((0) = 0,
and matrix V f(0)) (resp. (²*( I/2) is positive definite for (1/2, 1) (resp. 1);
(A3) Gradients are bounded in the compact set θ, that is, supree SuPae[n] V [() i)](2
(A4) For every [n]]. 0 E Rd, the solution F(8,2) 2) E Rd of the Poisson equation F(0, z) E[ X.+1) Xx =| FF =) V v()) exists, and supaee) [[ z)Il2 < oc;
(A5) The functions F( i) are L-soooth for all i [n], that is, V01,0, 02 O, vi E [n]. we have ()) - (f2, i)ll2 - L| - 02112-
We then have the following CLT result for SGD algorithms.
Lemma 3.1. For iterates {fthe20 of the SGD algorithm 7 satisfying (AI)-A5), we have
0. 0", and (0. (0--0)/ Dist
N(0 Vx),
(9)
t-350
where covariance matrix Vx is the unique solution to the Lyapunov equation Ex+ VxK* O when E (0.5, 1) (resp. Ex+ + (K+ + Vx K (K+ 1)² = 0) when a == 1). Here, Σx 2 Ex(V ;))(0",)))) is the asymptotic covariance matri as in and K a (20(0)).
Additionally, for the averaged iterates (0e122 where B,
1 Or have
0g
0", and VElO. - 8*) Dist N(0, Vg),
(10)
1-000
t-
where Vx= K- -K Exx--xx(-1>> (K-1)T with the same matrices K and Σx in the non-averaged case.
Remark 3.2. Lemma 3.1 is itself a special case of the more general CLT result for SA algorithms provided in Appendix 1. and as proved in Appendix [1.
Remark 3.3. While (A2) may appear to be strict first, it can be relaxed the setting of the objective function f(-) having multiple minimizers, by leveraging more general CLT results from SA literature, such as Theorem 2.1 in 28 However, this comes at a cost of cumbersome notation, requiring conditioning of iterates converging to one of the minimizers, potentially making the mathematical parts harder to follow. We also show in Appendix C [ that (A2) no stricter than inequality popularly adopted weak assumption in recent SGD literature
the studying non-convex objective functions [36] 47 70 72).
We slightly abuse the notation and shorten Σx (VG(0", -)), that is, the asymptotic covariance matrix evaluated at VG(0", ))). to Ex for better readability. In this paper. Ex (VG(0",)) and Σx are equivalent.
5

---

Remark 3.4. Assumptions (A3) and (AS) are widely seen in the RWSGD literature
57
34 67
while (A4) is automatically satisfied for any ergodic Markov chain (see 49
2T for details),
common assumption for the stochastic noise sequence 34
25
The compactness in (A3) can also
be relaxed, given assumptions on the objective function in 37 such that the estimator 0, generated
by Markov-drive driven sequences can still be 'locked in' compact set after a sufficiently long time. L
Lemma 3.1 implicitly indicates that the asymptotic convergence rate (in distribution) for 0g 0" (resp. 0 0*) is O(v))) (resp. O(1/Vt).. While this does not necessarily translate to O (m))
convergence rate for B[] - 0']]2] (O(1/V)) for Te[|@,, - 0* [2])), has been suggested 20 23], and is in fact true for cases such as quadratic objective functions since they satisfy the linear stochastic approximation in 221, which is of the form
0 = 0. 7+1 (AO, b(X+1)))
(11)
for which the connection between finite-time MSE and covariance matrix Vx has been established 21I. This is also true for arbitrarily weighted MSE, which can be obtained as weighted sum of diagonal entries of the covariance matrices Vx and Vx-
In addition to the apparent connection to MSE, the covariance matrix plays a wider role in SGD performance. Given any vector of weights w E Rd from Lemma 3.1 we also have that the weighted sum of errors (f: 8*) converges zero almost surely, and that w (0s 0')\v" Dist
(O0 w VVV w). This means that, for sufficiently large t, we can estimate
w T (0. 8*) nw Vxx w
1 2T
e 12/22
P
a
2
such that, for instance, the 95% confidence interval for forw"O Or is approximately w 0" 22 ww Wx In other words, smaller w Vx w leads to narrower confidence interval and higher accuracy. The form w Vx w for any vector E Rdd naturally implies that Loewner ordering should come into play when concerning the performance of SGD algorithms.
To proceed, we first employ the widely used notion of efficiency ordering of Markov chains. The efficiency of different chains is compared by ordering them using their respective AV as follows.
Definition 3.5 (Efficiency Ordering [50). ). For two random walks {Xe) and {Yr) with the same stationary distribution π, we say {X, 120 is more efficient than {Yi]120. which we write as X M Y. if and only if xx (g) S of (g) for any 9 g [n] R.
We are now ready state our main result. We first extend the efficiency ordering of Markov chains by proving the equivalence of comparing their scalar-valued AVs, to comparing their asymptotic covariance matrices via Loewner ordering. We then use this extension to show that more efficient inputs (X, 120 (as in Definition 3.5) to the SGD algorithm lead to performance improvements in the form of smaller covariance matrices in the Loewner ordering sense.
Theorem 3.6. Consider the SGD tteration (7) with two random walks {xt)120 and (Y:)120 as input sequences, with the same stationary distribution n, satisfying (AI)(A5). Then,
(i) X X2EY if and only if Σx (g) Ey (g) for any vector-valued function g;
(ii) If EVE(( () S1 By (VG(0") ,)), then Vx SL Vy (V& SL Vg for the case of averaged iterates);
where function VG((",)) [n] + R2d is defined in the SGD iteration 7 Vx and V'x (resp. Vy and Vxy) are the covariance matrices from Lemma 3.1 corresponding to (Xihez (resp. (Yih22)) as the stochastic input sequence.
Theorem 3.6 enables us to provide a sense of efficiency ordering of SGD algorithmss which driven by different stochastic inputs. Since this is achieved via Loewner ordering, it also leads to smaller confidence intervals in the long run as mentioned earlier, well as potentially smaller MSI depending on the objective function.
'The mean square error can be retrieved as the trace of the covariance matrix (weighted sum of its diagonal entries in case of weighted MSE). Loosely speaking, an iterate having smaller covariance matrix in the Loewner ordering will then also have smaller MSE (weighted MSE).

---

Remark 3.7. In addition to the CLT result for SGD algorithms with diminishing step size described in Lemma [3]]] we include in Appendix E [ similar results for constant step sizes and quadratic objective functions, where the statement of Theorem 3.6 still holds.
4 Applications: Towards More Efficient SGD
In this section, we present some SGD variants and compare them in terms of efficiency ordering of SGD. Specifically, we first show that a certain class of non-Markov random walks can provide a better input sequence than its Markovian counterpart. We then analyze shuffling-baser gradient descent and compare it to the SGD with i.d input in terms of efficiency ordering for SGD algorithm. We also extend our approach to a more general mini-batch version, the discussion for which is deferred to Appendix H.3 [
The simple random walk (SRW) is popular Markov chain that has been extensively studied in the literature [62 58 29]. Several recent works have focused on the backtacktaa random walk (NBRW) on connected undirected graph g(V,E) 3 in the MCMC literature, which is an extension of SRW with the same limiting distribution π π= d/1"d d [53 5
High-Order Efficient Random Walk for SGD:
10. Intuitively speaking, NBRW is a random walk that selects one of its neighbors uniformly at random except the one it just came/transitioned from. Specifically, the NBRW {Y:):20 is a second-order non-reversible Markov chain (i.e., it is non-Markov on V = [n)) with its transition probability given by
41
38
d.-1 kj d; > 1, if 1.)
P(Y+1 j|y i, Y k)) =
(12)
otherwise.
Since the limiting distributions of NBRW and SRW are the same, NBRW can be used as the input for SGD iterations (7) with the same re-weighted local functions G( i) as that of SRW for all [n] whenever the applications call for random-walk type of inputs. Let Ey OVVV((O' -)) be the asymptotic
covariance matrix of this NBRW {Yitza as defined in (8). One of the main results in [ concerns the efficiency ordering of NBRW and SRW. They show that NBRW has smaller AV, or equivalently,
from our Theorem (36 (i), smaller asymptotic covariance in terms of Loewner ordering. Our next result forms the necessary connection between the asymptotic covariance matrix arising in the CLT result and Σy EVGV(((""))
Proposition 4.1. Consider the SGD iteration with two input sequences SRW {Xe (Xe)120 and NBRW (Y:)120 respectively. Then, both the respective estimators 0x 0 a.S. 8", and Vy St Vx, that is, NBRW is more efficient than SRW in the SGD algorithm.
(1000
By augmenting the state space, we can represent NBRW as a Markov chain Z, = (Y,1,, Y,) E V> as was done in (53] 41). This transformation then allows to build CLT for SGD iteration with [Zehcoo as the input. The subtlety here is to prove that the asymptotic covariance matrix arising out of the CLT with respected to the augmented process {2:)r 1:20 is indeed equal to
)).
This is shown by cultivating the relationship between the stationary distribution of {Z,) (Ze32o on the augmented state space V x V and (Yi)zz on the node space V, as provided in [53)
Thus, our Theorem 3.. together with the existing works on efficiency ordering of NBRW versus SRW in the MCMC literature [53] 41 enable to show that NBRW is a more efficient input sequence than SRW for the SGD iteration (7). Interestingly, it has been shown that non-backtracking walks mix faster when the underlying graph is d regular 5 In this case, faster convergence rate is also suggested by mixing time based non-a monaasympooicc bounds prevalent in RWSGD literature. However, no such results concerning mixing time and SLEM exists for NBRW on general graph. Thus, in the form of Proposition I we demonstrate the utility of our approach in settings where mixing time based comparisons are unavailable.
Shuffling versus i.idd Input Sequence: cauffling-based methods have been widely used in machine learning applications [3]. They work by repeatedly passing over the entire state space [n] without repetition, each complete pass forming an epoch. Random shuffling and single shuffling are two versions therein and differ in the order in which they pass over [n].. Random shuffling, as the name suggests, makes the pass randomly chosen order in each epoch, while single shuffling
maintains the same predetermined order (often randomly chosen once at the beginning) for all
7

---

epochs. Shuffling- based methods are known to show better empirical performance than i..d input [1], although intense theoretical analysis for shuffling-bsse
gradient descent has only emerged In what follows, we use our results from Section 3 to compare shuffling-based gradient descent to SGD with i.id input. To do so, we first analyze the asymptotic covariance matrix for shuffling-base based methods.
in recent years 666
33
64
3
32
Lemma 4.2. Let the input process {Xt)120 be single or random shuffling. Then, for any vector-
valued function g: [n] R. Σx (g) = O, where Σx (g) is defined (8)
For iid input sequence with distribution म,, the asymptotic covariance from Lemma 3.1 reduces to
Σx EVV((" A Varx (VG(0*, Xx))
(13)
following its definition in (). and thus, trivially, Ex(VG((r.-) 21 0. Lemma 4.2 shows that shuffling-basee methods are more efficient than i.idd input sequence due smaller asymptotic covariance matrix in Loewner ordering. Next, we show that they also outperform i.idd input when used for driving the input sequence of SGD algorithms.
Proposition 4.3. Consider the SGD iteration (7) with stochastic inputs single/random shuffling {Xihe2o and ii.d sampling {Yirr2o, we have 0²¹ 0% a.s.,, 8" and Vx = =0 52 Vy.
t-+00
Though it may seem so at first, Proposition 4.3 is not a simple application of Theorem 3.6 es- pecially for random shuffling because it is hard to check if random shuffling, formulated umm-inhhmooennous Markov chain, indeed satisfies (A4). To overcome this difficulty, in Appendix H I we come up with non-trivial augmentation to much higher dimensional state space ([n) [+++)) to make random shuffling a homo-hooogeseous periodic Markov chain in order to show that both single shuffling and random shuffling satisfy (A4) and thus apply Theorem 3.6
The case of shuffling versus i.id inputs is an example of a setting where the sequence with larger SLEM is more efficient than one with smaller SLEM as an input sequence to the SGD iteration 7 For quadratic objective functions that satisfy the linear SA iteration in [2I) also attains a faster convergence speed in terms of MSE than i.i.d inputs to SGD algorithms. Although some recent works provide more informative finite-time error bounds on the MSE of the objective function for shuffling-baase methods, by studying a special case of the matrix norm AM-GM inequality and proving faster convergence rate than i.i.d inputs 56 3 32), our result is not a subset of theirs. To be precise, show in Appendix C [ that our assumption (A2) the objective function is no less general than their most general setting based on the Polyak- -ojasiewwcz inequality.
Remark 4.4. Mini-batch gradient descent is another popular gradient descent variant and is widely used in the machine learning tools [2 2 55 to accelerate the learning process when compared to SGD. In Appendix H.3 ① we show how framework can be applied to study min-batch based SGD algorithms, and include the asymptotic analysis on mini-batch gradient descent with shuffling.
Besides mini-batch gradient descent, there are other SGD variants, e.g., momentum SGD, Nesterov accelerated SGD and ADAM, that have been studied in the SGD literature for non-asymptotic analysis [3,,59] [. However, asymptotic analysis on the SGD variants is not well studied in the literature, with only very recent results on the CLT for i.idd input sequences [42] g g 45). Asymptotic analysis and CLT for variants more general Markovian input sequences, which would be prerequisite for Theorem 3.6 remains an open problem. We defer the discussion on related works to Appendix I.3 [1], where also empirically test the SGD variants and find that the efficiency ordering result still holds for these SGD variants opening up the possibility for further theoretical analysis.
Numerical Experiments
In this section, we empirically validate our theoretical analysis. We select two convex objective functions as follows.
f(0) n
log(1 1og(1+exm) +exp( (xxeppp(xxxx00 ()) +))+ + 1013. f(0) - n Σ oJ (a,af +D.)0++'>
(14)
For regularard logistic regression f(0), we choose the dataset CIFAR- 10
40 where n is the
total number of data points. Here, x; E IR 108 is the vector flattened from the cropped image i with
'hhe single shuffling when realized as periodic Markov chain has SLEM = 1 (transition matrix is unitary), while the i. input sequence has SLEM = 0 (transition matrix is rank one).
8

---

shape (6, 6) and E R is the label. For sum-of-non -oo---onnneeeee functions f(0), which is based on the experiment setup in [3T 4. we generale random vectors a, b and matrices D, which ensure the invertibility of matrix -i=1 a. and Σ D; 0 (details are deferred to Appendix 1.2 []). For both experiments, we assign data point to each node on the general graph 'Dolphins' (62 nodes) [63]. We set the step size in the SGD algorithm as 1/t0.9 and use MSE E E] 8" [ to measure the relative performance of different inputs. We also employ the scaled MSE | 0" //1/7 to empirically show its relationship to the CLT result (9). Due to space constraints, additional simulation results which support our efficiency ordering result in the setting of large graphs, and non-convex functions deferred to Appendix 1.3 in [. Therein, via numerical simulations, also observe the efficiency ordering for other SGD variants such as Nesterov accelerated SGD and ADAM when comparing their iterations under efficiency ordered noise sequences.
In Figure we compare NBRW and SRW as input sequences on the graph 'Dolphins' for two objective functions in (14). We also compare uniform sampling, random shufflng and single shuffling, assuming that they can access any node on the graph each iteration. We can see Figure 2a and 2cc that NBRW always falls below SRW throughout all time periods, which indicates that NBRW tends to have smaller MSE than SRW Single and random shuffling are both better than uniform sampling in terms of smaller MSE. The oscillation of single shuffling comes from a predetermined fixed data sampling sequence, while random shuffling changes the permutation whenever traversing all nodes. Such oscillation is not visible in Figure 2c and Figure 2d because it is small on the current y-axis scale. The curves of single and random shuffling in Figure 2b and [2] fall below that of uniform sampling and still decrease in the linear rate because eventually their covariance matrices will be zero matrix, as indicated in Proposition 4.3 Figure shows that the scaled MSEs of NBRW, SRW and uniform sampling approach some constants after some time, which is consistent with the CLT result (9). The curves of NBRW are still below that of SRW, showing that the input with smaller scaled MSE tends to have higher efficiency, which supports Proposition [.1 We can see from Figure 2d that the curves NBRW, SRW are still increasing andd they have not yet entered the regime where the covariance matrix becomes the main factor. On the other hand, uniform sampling and both shuffling methods are just entering this regime.
20P
NBRW
101
SRW
101
Uniform Sampling
15:1
Single Shuttling
101
Random Shuffling
10'
NBRW
SRW
10
Uniform Sampling
Single Shuffling
11:1
Random Shuffling
SGD iteration
SGD iteration
(a) Logistic regression; (MSE)
(b) Logistic regression; (scaled MSE)
12a
NBRW
SRW
SRW
Uniform Sampling
Uniform Sampling
Random Shuttin
dam Shuffling
Single Shuffling
Single Shuffling
10
188-
ElI
12a
10f
20030
40000
C3000
30200
100000
10 SGD Iteration
SGD itoattio
(c) sum-non-convex fn.; (MSF)
(d) sum-non-convex fn.; (scaled MSE)
Figure 2: Performance comparison of different stochastic inputs on the graph 'Dolphins'.
6 Conclusion
We have introduced the notion of efficiency ordering of SGD algorithms, and shown that processes with smaller asymptotic covariance are always more efficient as input sequences for SGD algorithms. Furthermore, we numerically observe that this sense of efficiency ordering is also seen SGD variants such as Nesterov accelerated SGD and ADAM. Since the asymptotic analysis of such SGD variants not well-established under general stochastic inputs, establishing theoretical results on efficiency ordering remain open problem.

---

7 Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their constructive comments. The research was conducted while Vishwaraj Doshi was with the Operations Research Graduate Program, North Carolina State University. This work was supported in part by National Science Foundation under Grant Nos. CNS-2007423, I1S-99 and CNS-1824518.
References
[1] Efficiency ordering of stochastic gradient descent supplementary material, 2022.
[2] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pages 265-283, 2016.
[3] Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. In Proceedings of the 34th International Conference on Neural Information Processing Systems, volume 33, pages 17526-17535, 2020.
[4] Zeyuan Allen-Zhu and Yang Yuan. Improved svig for non-strongly-convex or sum-of-none convex objectives. In International conference on machine learning, pages 1080-1089. PMLR, 2016.
[5] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mathematics, 904):585-603, 2007.
[6] Mahmoud Assran and Michael Rabbat. On the convergence of nesterov's accelerated gradient method in stochastic settings. In Proceedings of the 37th International Conference on Machine Learning, pages 410-420, 2020.
[7] Ghadir Ayache and Salim El Rouayheb. Private weighted random walk stochastic gradient descent. IEEE Journal on Selected Areas Information Theory, 2(1):452-463, 2021.
[8] Anas Barakat and Pascal Bianchi. Convergence and dynamical behavior of the adam algorithm for nonconvex stochastic optimization. SIAM Journal on Optimization, 31()):244 274,, 2021.
[9] Anas Barakat, Pascal Bianchi, Walid Hachem, and Sholom Schechtman. Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance. Electronic Journal of Statistics, 15(2):3892-3947, 2021.
[10] Anna Ben-Hamou, Eyal Lubetzky, and Yuval Peres. Comparing mixing times on sparse random graphs. In Proceedings of the Twenty-Ninth Annual CCM- Symposium Discrete Algorithms, pages 1734-1740. SIAM, 2018.
[11] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
[12] Zalán Borsos, Sebastian Curi, Kfir Yehuda Levy, and Andreas Krause. Online variance reduction with mixtures. In International Conference on Machine Learning, pages 705-714. PMLR, 2019.
[13] Léon Bottou. Curiously fast convergence some stochastic gradient descent algorithms. Unpublished open problem offered to the attendance of the SLDS 2009 conference, 2009.
[14] Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pages 177-186. Springer, 2010.
[15] Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pages 421-436. Springer, 2012.
[16] Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM review, 46(4):667-689, 2004.
10

---

[17]
Manuele Brambilla, Eliseo Ferrante, Mauro Birattari, and Marco Dorigo. Swarm robotics: review from the swarm engineering perspective. Swarm Intelligence, 7(1):1-41, 2013.
[18] Pierre Brémaud. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. Springer Science & Business Media, 2013.
[19]
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. editors. Handbook of Markov Chain Monte Carlo (Ist ed.). Chapman and Hall/CRC, New York, 2011.
[20] Shuhang Chen, Adithya Devraj. Andrey Bernstein, and Sean Meyn. Accelerating optimization and reinforcement learning with quasi stochastic approximation. In 2021 American Control Conference (ACC), pages 1972, 2021.
[21] Shuhang Chen, Adithya Devraj, Ana Busic, and Sean Meyn. Explicit mean -qeare error bounds for monte-carlo and linear stochastic approximation. In International Conference Artificial Intelligence and Statittcs, pages 4173-4183. PMLR, 2020.
[22] Francois Chollet et al. Keras, 2015.
[23] Adithya M. Devraj and Sean Meyn. Q-earming with uniformly bounded variance. IEEE Transactions on Automatic Control, 2021.
[24] Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Finite-time analysis of stochastic gradient descent under markov randomness. arXiv preprint arXiv:2003.10973, 2020.
[25] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549- 1578, 2012.
[26]
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
[27] Ayoub El Hanchi and David Stephens. Adaptive importance sampling for finite-sum optimiza- tion and sampling with decreasing step-sizes. In Advances in Neural Information Processing Systems, volume 33, pages 15702-15713, 2020.
[28] Gersende Fort. Central limit theorems for stochastic approximation with controlled markov chain dynamics. ESAIM: Probability and Statistics, 19:60-80, 2015.
[29] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina Markopoulou. Practical recommenda- tions on crawling online social networks. IEEE Journal on Selected Areas in Communications, 29(9):182-11992 2011.
[30] JHF Gomes, AP Paiva, SC Costa, Pedro Paulo Balestrassi, and EJ Paiva. Weighted multivariate mean square error for processes optimization: case study on flux-cored are welding for stainless steel claddings. European Journal of Operational Research, 226(3):522 535, 2013.
[31] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-52000 5209. PMLR, 2019.
[32] Mert Gürbüüzalaaan, Asu Ozdaglar, and Pablo A Parrilo. Why random reshufting beats stochastic gradient descent. Mathematical Programming, 186(1) 1):4988444 2021.
[33] Jeff Haochen and Suvrit Sra. Random shuffling beats sgd after finite epochs. In International Conference on Machine Learning, pages 2624 2633. PMLR, 2019.
[34] Björn Johansson, Maben Rabi, and Mikael Johansson. randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Optinization, 2053):1157-11770 2010.
[35] Galin Jones. On the markov chain central limit theorem. Probability surveys, 1:299-320, 2004.
[36] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Machine Learning and Knowledge Discovery in Databases, pages 795-811. Springer, 2016.
condition. In Joint European Conference on

---

[37] Prasenjit Karmakar and Shalabh Bhatnagar. Stochastic approximation with iterate- derreddendd markov noise under verifiable conditions in compact state space with the stability of iterates not ensured. IEEF Transactions on Automatic Control, 66( (6(12)55941-5554 2021.
[38] Mark Kempton. Non-backtracking random walks and a weighted ihara's theorem. Open Journal of Discrete Mathematics, 6(4):207-22) 2016.
[39] Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In ICLR (Poster), 2015.
[40] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
[41] Chul-Ho Lee, Xin Xu, and Do Young Eun. Beyond random walk and metropolis -aatingss samplers: why you should not backtrack for unbiased graph sampling, ACM SIGMETRICS Performance evaluation review, 40(1):319-330, 2012.
[42] Jinlong Lei and Uday V Shanbhag. Variance-reduced accelerated first-order methods: Central limit theorems and confidence statements, arXiv preprint (rXiv:2006.07769 2020.
[43] Victor Lesser, Charles I. Ortiz Jr, and Milind Tambe. Distributed sensor networks: A multiagent perspective, volume 9. Springer Science Business Media, 2003.
[44] David Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[45] Tiejun Li, Tiannan Xiao, and Guoguo Yang. Revisiting the central limit theorems for the sgd-type methods. arXiv preprint arXiv:2207.11755 2022.
[46] Xianghui Mao, Kun Yuan, Yubin Hu, Yuantao Gu, Ali Sayed, and Wotao Yin. Walkman:
A communication-effciiee random-wand walk algorithm for decentralized optimization. IEEE Transactions on Signal Processing, 68:2513 2528, 2020.
[47] Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure convergence of stochastic gradient descent in non-convex problems. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 1-32, 2020.
[48] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics,
1953.
[49] Sean P Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
[50] Antonietta Mira. Ordering and improving the performance of monte carlo markov chains.
Statistical Science, pages 340-350, 2001.
[51] Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter L Bartlett, and Michael I Jordan. On linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947-2997. PMLR, 2020.
[52] Hongseok Namkoong, Aman Sinha, Steve Yadlowsky, and John C Duchi. Adaptive sampling probabilities for non-smooth optimization. In International Conference on Machine Learning, pages 2574-2583. PMLR, 2017.
[53] Radford M Neal. Improving asymptotic variance of meme estimators: Non-reversible chains are better. Technical report, Department of Statistics, University of Toronto, July 2004.
[54] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency optimization. Wilee--nterscience, 1983.
[55] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, nigh-performance deep learning library. Advances in neural information processing systems, 32:8026-8037, 2019.
12

---

[56] Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of sgd without replacement. In International Conference on Machine Learning, pages 7964-7973. PMLR, 2020.
[57] S Sundhar Ram, A Nedić, and Venugopal V Veeravalli. Incremental stochastic subgradient algorithms for convex optimization. SIAM Journal on Optimization, 20(2):9117777, 2009.
[58] Amir Hassan Rasti, Mojtaba Torkjazi, Reza Rejaie, Nick Duffield, Walter Willinger, and Daniel Stutzbach. Respondent-driver sampling for characterizing unstructured overlays. In IEEE INFOCOM 2009, pages 2701-2705. IEEE, 2009.
[59] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence adam and beyond. In International Conference Learning Representations, 2018.
[60] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[61] Gareth O Roberts and Jeffrey S Rosenthal. General state space markov chains and meme algorithms. Probability surveys, 1:20-71, 2004.
[62] Sheldon M Ross, John Kelly, Roger Sullivan, William James Perry, Donald Mercer, Ruth M Davis, Thomas Dell Washburn, Earl V Sager, Joseph B Boyce, and Vincent L Bristow. Stochastic processes, volume 2. Wiley New York, 1996.
[63] Ryan A. Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
[64] Itay Safran and Ohad Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
[65] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning, pages 3027-3036. PMLR, 2017.
[66] Ohad Shamir. Without-replacemmett sampling for stochastic gradient methods. Advances in neural information processing systems, 29:46-54, 2016.
[67] Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 9918-9927, 2018.
[68] Fanggang Wang, Xiaojun Yuan, Soung Chang Liew, and Dongning Guo. Wireless mimo switching: Weighted sum mean square error and sum rate optimization. IEEE transactions on information theory, 599))5227--531, 2013.
[69] Stefanie Warnat-Herresthll, Hartmut Schultze, Krishnaprasad Lingadahalli Shastry, Sathya- narayanan Manamohan, Saikat Mukherjee, Vishesh Garg, Ravi Sarveswara, Kristian Händler, Peter Pickkers, N Ahmad Aziz, et al. Swarm learning for decentralized and confidential clinical machine learning. Nature. 594(7862):265-227 2021.
[70] Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type. part i: Discrete time analysis. arXiv preprint 1rXiv:2105.01650 2021.
[71] Ran Xin, Shi Pu, Angelia Nedić, and Usman A Khan. A general framework for decentralized optimization with first-order methods. Proceedings of the IEEE, 108(11):1869-188) 2020.
[72] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffle sgd be better than reshuffling sgd and gd? Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 6653-4658 PMLR, Aug 2021.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No] or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proof's of all thcoretical results? [Yes] All the proof's are included in the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The details of the simulation setup are provided the supplementary material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] The citations can be found in Section 5.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "a_Vtx8nYsYQ", "reviewer": "Reviewer_1nnX", "summary": "This paper proposes an asymptotic analysis of SGD when the noise sequence is not necessarily iid but can be a Markov chain such as a random walk over an arbitrary graph. The main contribution of this work is to connect the concept of efficiency ordering (which was previously introduced in the literature to compare Markov chains with the same stationary distribution and hence compare MCMC algorithms) with an ordering of covariance matrices inherited from Central Limit Theorems controlling rescaled SGD iterates driven by Markov chain noise sequences. As a consequence, SGD algorithms can achieve smaller covariance errors when using more efficient noise sequences for MCMC sampling. As applications of this result, the paper considers decentralized optimization over a graph using high-order random walks for SGD on the one hand and (mini-batch) gradient descent with shuffling on the other hand, confirming the superiority of these mechanisms as previously noticed in the literature. The paper also notably shows how some non-Markovian processes (for which non-asymptotic analysis are not available in the literature) can outperform Markovian input sequences for SGD in terms of efficiency ordering. Numerical experiments illustrate the theoretical findings.", "questions": "1. Regarding the main contribution (Theorem 3.6), in general, is showing that the AV is small easier than controlling the asymptotic covariance from the CLT? The applications (Props. 4.1 to 4.4) seem to exploit previously known efficiency ordering from the MCMC literature and transfer them to SGD using Theorem 3.6 whereas these last results (from the MCMC literature) may not be easy to establish in general. \n\n2. The example of Fig. 1 is interesting and motivates looking at the AV as a metric for ordering instead of SLEM. However, I am wondering if one can also find an example where the converse holds, i.e. where SLEM may be more relevant if this makes sense. I understand that the point in the paper is to motivate looking at AV but commenting on the converse would also be interesting to complete the picture for the reader regarding the comparison between the asymptotic approach and its non-asymptotic counterpart. \n\n3. In the contributions, it is stated that the analysis covers non-Markovian stochastic processes beyond Markovian sequences. The example in p. 7 is a second-order Markov chain (which is non-Markov) and it is analyzed via an augmented process which is a Markov chain. Could one also use non-asymptotic analysis based on the mixing time for this same augmented process? This type of approach does not seem to be out of reach for this specific kind of non-Markovian process compared to the asymptotic approach pursued in the paper. \n\nTypos: \n- l. 188: (A2), what is a? It should rather be \\alpha defining the step size in (A1) I guess. \n- l. 364-365: what are f and g? Is it \\tilde{f} and \\hat{f} instead?", "limitations": "Limitations are not explicitly discussed by the paper (as acknowledged by the authors in the checklist in Question1. b). Some comments and questions regarding limitations of the work are discussed in the section above. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "— STRENGTHS: \n\n1. The paper states that the covariance matrices associated to two random walks following an efficiency ordering are Loewner ordered even for non-Markovian stochastic processes. This is an advantage of the asymptotic approach compared to its non-asymptotic counterpart which cannot handle the non-Markovian setting for which the mixing time is irrelevant beyond the Markovian noise setting (see a clarification question regarding this point in the next section below). Moreover, the result implies that better MCMC samplers could be used to enhance SGD thanks to the connection between AV for MCMC and covariance matrices for SGD algorithms from CLT. The paper hence establishes an interesting connection between the MCMC literature and the asymptotic covariance associated to (rescaled) SGD iterates (using the same noise sequence). \n\n2. The comparison between shuffling and iid input sequence and the use of shuffling in mini-batch gradient descent are interesting questions even in practice and prior work has observed and established some advantages of these techniques. The present work compares them using an alternative asymptotic point of view compared to the more common non-asymptotic (finite-time bounds) in the literature relying on mixing times.  \n\n3. The paper also extends prior art regarding applications. For instance, it shows that a high-order random walk (NBRW) which is non-Markov is more efficient than SRW for SGD on general graphs beyond d-regular graphs for which this was previously established using mixing times. It also confirms some known advantages of shuffling over iid sampling for SGD and addresses a class of functions (verifying (A2)) that is not covered by prior work. \n\n4. Clarity: the paper is well-written and the contributions are clearly stated. The results are sound and the paper is technically solid (I only quickly went through appendices A, C (checked the proof of the main result) and D though). \n\n— WEAKNESSES:\n\n1.  Unlike the asymptotic approach, a non-asymptotic analysis captures the dependence on constants of the problem such as the data and the graph topology in the distributed optimization setting. \n\n2. Among other experimental facts, two main elements are presented as motivation to consider asymptotic variance as a tool for the analysis. First, the paper mentions the connexion of AV with the MSE. Nevertheless, this connexion between finite-time MSE and the covariance matrix does not seem to be straightforward beyond the case of quadratic objective functions (or linear stochastic approximation) which is well understood in the literature with existing thorough non-asymptotic analysis (for e.g. [18, 45] as mentioned in the paper). Second, the paper also mentions confidence intervals: although a smaller covariance matrix indeed reduces the confidence interval length, this covariance matrix depends on the Hessian at the minimizer which is unknown. Hence, it is hard to exploit the asymptotic analysis in practice, although this may not be the main purpose of the paper regarding this confidence interval remark. \n\n3. The asymptotic analysis seems to provide little additional actionable information compared to the non-asymptotic approach. In l. 112-117, the paper mentions that the asymptotic variance provides more information than non-asymptotic MSE bounds, but is this information usable in practice? Can we leverage this additional information to improve the algorithms easily beyond the case where we already have a more efficient sequence (in the sense of the MC ordering) at hand? Also, for instance, in the paper, if the asymptotic analysis addresses a different class of functions (satisfying (A2)) which does not include PL functions (as previously addressed in the literature), it only confirms previously known facts regarding shuffling for SGD for which more informative finite-time bounds exist as stated by the paper (l. 323). \n\n4. Using Theorem 3.6 may not be easy in general, one needs to know an efficiency ordering of two sequences to transfer it to SGD. Is the problem of determining the efficiency ordering between two sequences easier than comparing the covariance matrices inherited from the CLT corresponding to SGD with the two different noise sequences? (see question in the next section)\n\n5. Technical significance: The main contribution of the paper as highlighted by the paper is Theorem 3.6. From the technical point of view, this result follows from the definition of the asymptotic variance of the Markov chain in one direction and from the well-known explicit integral form of the covariance matrix together with the stability of the Loewner ordering (Lemma D.2) for the converse (Appendix, p.6). Compared to the proof of this main result, the applications require more technical work. As acknowledged by the authors (especially in the appendix), CLTs are known in the literature, even for general stochastic approximation schemes driven by Markovian noise, of which SGD with Markov noise is a particular case. The paper relies on this prior work for the CLT. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VC2RrZb9e4", "reviewer": "Reviewer_jRx9", "summary": "The authors introduce the notion of efficiency ordering to classify stochastic algorithms.\nThey claim that some non-Markovian dynamics are more efficient that the Markovian ones for SGD.\n", "questions": "The authors should first provide evidence that their proposal is indeed an improvement for stochastic algorithms on very large graphs and non-convex functions to optimize.\n", "limitations": "Do not apply.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is unclear, and the claims seem to overstate the results in general.\nThe figures present data which are far from convincing.\nIn particular, the numerical experiment made on the Dolphins graph of 62 nodes is not meaningful.\nGiven the generality of the statement made by the authors, I would have expected much higher accuracy numerical experiments run on much larger graphs.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Qjb2_-2wdJz", "reviewer": "Reviewer_3mgL", "summary": "At each iteration, stochastic gradient descent (SGD) processes data sampled randomly from the training set. Denote this sequence of training data by $(X_t)_t$, which includes the case where $X_t$ are mini-batches. Empirical evidence by the authors suggest that the convergence of SGD is faster when the asymptotic variance (AV) of the chain $(X_t)_t$ is smaller, contrary to the commonly held belief that smaller SLEM (second largest eigenvalue modulus) lead to faster convergence of SGD. This motivates the authors to study the AV of data sampling approaches commonly employed in SGD, such as mini-batch shuffling, and define efficiency ordering on chains based on their AV (lower AV implies higher efficiency). They prove rigorously that certain non-Markovian sequences such as shuffling give better efficiency ordering than Markovian i.i.d. input sequences. They then demonstrate experimentally that the former indeed gives rise to faster converging SGD when applied to the CIFAR-10 dataset.", "questions": "- While the main body of the paper is well-written, the appendix I believe is not at the same quality and can be improved. For instance:\n   - Line 69: \"We can check the solution $\\tilde{F}(\\theta, z)$\". What are we checking?\n   - The proof of Proposition 4.1 (Appendix F) is confusing. What are the processes $X$ and $X'$? How are they related to the NBRW and SRW? While I agree with the computations in the proof, I still don't understand how it can be used to conclude that NBRW is more efficient than SRW.\n   - In Appendix G, the line \"regroup all the terms in each $k$-th epoch with length $n$\" (line 226) is difficult to understand (I do understand now, but it took a while). It may help to supplement with a diagram.\n   - What is $\\hat{\\pi}$ in the proof of Lemma H.1? How is it different from $\\pi$?\n   - I don't understand how the following line is true (Line 291-292):\n> We also note that $P(s_t, s_{t+j}) = 0$ for $j \\neq kn$ and $k \\in \\mathbb{N}$.\n\n      Please could you explain more?\n   - What do the embedded plots in figures 5a), 5b), 6a) and 6b) show?\n\n- There are several misprints peppered throughout the appendix.\n   - Line 72: I suggest phrasing \"are right and left eigenvector of P\" as \"are the right and left eigenvectors of P respectively\".\n   - Line 94-95: \"to ensure $\\theta^*$ being local minimizer\" should be \"to ensure that $\\theta^*$ is the local minimizer\".\n   - Line 226: I think \"$\\sum_{i = (k-1)n}^{kn-1} (g(X_i) - E_\\pi (g))$\" should read \"$\\sum_{i = (k-1)n}^{kn-1} (g(X_i) - E_\\pi(g)) < \\infty$\".\n   - Line 229: \"because of bounded function $g$\" should be \"because of the boundedness of function $g$\".\n   - Line 247: \"Especially, $u_m = \\hat{\\pi}$\" should be \"In particular, $u_m = \\hat{\\pi}$\"\n   - $s_6$ in line 268 should be $s_8$.\n   - $a_j^{(t)}$ in line 290 should be $A_j^{(t)}$.\n   - Appendix G: Lemma 4.2 is mislabelled as Proposition 4.2.\n\n- While the results point to new methods for improving SGD, in practice, how easy is it to compute the asymptotic variance for a given chain? Also, is efficiency ordering still valid for other stochastic optimization methods such as Adam?\n", "limitations": "The work is mostly theoretical and as far as I can see, has no potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The results in the paper give new insights into SGD. In particular, it opens up a direction to look for more efficient SGD algorithms.\n- The techniques involved in the proof are interesting and completely non-trivial. In particular, the idea of lifting non-Markovian sequences to an augmented space to make it Markovian was intriguing. The maths overall seem correct (although I do have some questions below) and fully rigorous.\n- The main body of the paper is well-written and easy to follow.\n\nWeakness:\n- While the main body of the paper is well-written, the appendix, which contains all the proofs, can be improved. I defer some of my issues in the appendix to \"Questions\".\n- Plots can be improved by:\n   - Using larger label sizes (e.g. labels in Figure 2 are almost impossible to see without zooming in. Also better to increase label sizes in figure 1. Applies also to the figures in the appendix).\n   - Improve colour-scheme by taking into consideration colorblindness. For instance, avoid red-green-blue combination (see e.g. https://davidmathlogic.com/colorblind/#%23D81B60-%231E88E5-%23FFC107-%23004D40 for more details).\n- There are a few misprints/suggestions in the text of the main body that I spotted:\n   - Line 140: $\\mathbf{M}\" \\in \\mathbb{R}^n$ should be $\\mathbf{M} \\in \\mathbb{R}^n$ (note the quotation mark)\n   - Line 268: \"From the nature of same limiting distributions\" can be phrased better. Maybe along the lines of \"Since the limiting distributions are the same\".\n   - Line 369: \"we random generate\" should be \"we randomly generate\".\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QTzyJWaiSpI", "reviewer": "Reviewer_9xiZ", "summary": "This paper studies the stochastic gradient descent algorithm as a stochastic sequence generated by a random walk on an arbitrary graph. It explores various Markov Chain Monte Carlo (MCMC) sampling techniques and proposes \"efficiency ordering\" of Markov chains. This is used to demonstrate that more efficient MCMC sampling can also lead to smaller covariances for SGD algorithms in the limit.", "questions": "- The discussion on the mini-batch gradient descent can perhaps be relegated to the Appendix which would both free up space for more appropriate and thorough descriptions on empirical analysis of the efficiency ordering and ensure that variants of SGD are handled / discussed more efficiently. For e.g. if one discusses mini-batch gradient descent, why not other variants including momentum acceleration methods and other known techniques?\n\n- The main paper does not discuss the effect of the underlying graph structure (which affects SLEM) and its impact on efficiency ordering of SGD\n\n- The paper does not have a conclusion or future work section. It lacks a discussion on potential drawbacks of the technique.\n\nMinor comments\n- 1. Asymptotic covariance matrix - definition of \\hat{mu}_t (g) -> sum_k=1 to t g(X_k) NOT X_t?\n", "limitations": "Societal impact of the work is not discussed in this paper. Furthermore, limitations of the proposed technique need further thought.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Paper is well written and presents both theoretical and empirical studies of the effect of MCMC sampling on SGD algorithms\n- It introduces the novel concept of \"efficiency ordering\" of Markov chains and its. theoretical underpinnings\n-Comparison of non-Markov random walks to their Markovian counterpart.\n\nWeakness\n- The main paper lacks sufficient details on the simulation and figures are too small for readability\n-The overall readability of the paper needs to be improved \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept