Stability and Generalization for Markov Chain Stochastic Gradient Methods
Authors: Puyu Wang
Yunwen Lei
Yiming Ying
Ding-Xuan Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: statistical learning theory
algorithmic stability
generalization analysis
stochastic gradient methods

Abstract: Recently there is a large amount of work devoted to the study of Markov chain stochastic gradient methods (MC-SGMs)  which mainly focus on their convergence analysis for solving minimization problems. In this paper, we provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems through the lens of algorithmic stability in the framework of statistical learning theory. For empirical risk minimization (ERM) problems, we establish the optimal excess population risk bounds for both smooth and non-smooth cases by introducing on-average argument stability. For minimax problems, we develop a quantitative connection between on-average argument stability and generalization error which extends the existing results for uniform stability (Lei et al., 2021). We further develop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability, which, combined with our stability results, show that the optimal generalization bounds can be attained for both smooth and non-smooth cases. To the best of our knowledge, this is the first generalization analysis of SGMs when the gradients are sampled from a Markov process.   
 

Stability and Generalization for Markov Chain Stochastic Gradient Methods
Puyu Wang' Yunwen Lei? Yiming Ying? Ding-Xuan Zhou
Liu Bie Ju Centre for Mathematical Sciences, City University of Hong Kong
2 School of Computer Science, University of Birmingham Department of Mathematics and Statistics, State University of New York Albany
School of Mathematics and Statistics, University of Sydney
puyuwang @cityy.edu..k y.lei@ hbam.ac.uk. yying@albany dingxuan. zhou sydney.edu.au
Abstract
Recently there is a large amount of work devoted to the study of Markov chain stochastic gradient methods (MC-SGMs) which mainly focus on their convergence analysis for solving minimization problems. In this paper, we provide a compre- hensive generalization analysis of MC-SGMs for both minimization and minimax problems through the lens of algorithmic stability in the framework of statistical learning theory. For empirical risk minimization (ERM) problems, we establish the optimal excess population risk bounds for both smooth and non-smooth cases by introducing on-average argument stability. For minimax problems, we develop a quantitative connection between on-average argument stability and generalization error which extends the existing results for uniform stability (38]. We further de- velop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability, which, combined with our stability results, show that the optimal generalization bounds can be attained for both smooth and non-smooth cases. To the best of our knowledge, this is the first generalization analysis of SGMs when the gradients sampled from Markov process.
Introduction
Stochastic gradient methods (SGMs) have been the workhorse behind the success many machine learning (ML) algorithms due to their simplicity and high efficiency. As opposed to the deterministic (full) gradient methods, SGMs only require a small batch of random example(s) to update the model parameters each iteration, making them amenable for solving large-scale problems.
There are mainly two notable types of SGMs which are inherent for different learning problems. In particular, stochastic gradient descent (SGD) is widely used for solving the empirical risk min- imization (ERM) problem and the theoretical convergence has been extensively studied [e.g.. 37
5, 17, 21
86). Concomitantly. the minimax problems instantiate many ML problems such as Generative Adversarial Networks (GANs) 30 AUC maximization
42
43
53,
57 73
80
82
129 45 II, and algorithmic fairness [16
41
(2 51. Stochastic gradient descent ascent (SGDA) is
an off-the-shelf algorithm for solving minimax problems. The convergence of SGDA and its variants is also widely studied in the literature [e.g.. 44
49 54 56).
On the other important front, the ultimate goal of learning is to achieve good generalization from the training data to the unknown test data. Along this line, generalization analysis of SGMs has attracted considerable attention using the algorithmic stability approach [[ 24]. In particular, stability and
generalization of SGD have been studied using the uniform argument stability [6, 7 [3] 32 36)
The corresponding author Yiming Ying.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and on-average stability [39 40 In 25 38 85], different stability and generalization measures are investigated for SGDA under both conve--concan and non-convex- wwwwee-non-coneeeeeeeeeee con-con settings. critical assumption in most of the above studies about SGD and SGDA is the i.i.d. sampling scheme where the randomly sampled mini-batch or datum at each iteration i.i.d. drawn from the given training data, guaranteeing that the stochastic gradient is an unbiased estimator of the true gradient.
Markov chain naturally appears in many important problems, such as decentralized consensus optimization, which finds applications in various areas including wireless sensor networks, smart
[3] as well as and metric learning [35] 75 76 79]. common example is distributed system in which each node stores a subset of the whole data, and one aims to train a global model based on these data. We let central node that stores all model parameters walk randomly over the system, in which case the samples are accessed according to a Markov chain. Several works studied this kind of model [3
grid implementations and distributed statistical learning 44] 14, 23 48, 50, 58
61
pairwise learning [78] which instantiates AUC maximization [11 29, 46
81
87
34
48
50
58
Markov chains also arise extensively thermodynamics, statistical mechanics dynamic systems and [59 667] In addition, it was observed in [69] [78) that SGD with Markov chain sampling
(MC-SGD) performs more efficiently than SGD with the common i.i.d. sampling scheme in various cases. Hence, studying the performance of MC-SGMs has certain theoretical and application values. The key difference from the i.i.d. sampling scheme is that the stochastic gradient at each iteration is sampled the trajectory of a Markov chain, in which the stochastic gradient estimators are neither unbiased nor independent. Recent studies [4 18 22 33 34 58, 68) overcame this technical hurdle and provided the convergence rates of MC-SGD. However, to the best of our knowledge, there is no work on the generalization performance of SGMs with Markov sampling.
Main contribution: In this paper, we provide a comprehensive study of the stability and generaliza- tion for both SGD and SGDA with Markov sampling in the framework of statistical learning theory
72
Our main contribution can be summarized as follows.
We develop stability and generalization results of MC-SGD for solving ERM problems in both smooth and non- mon-smooth cases. In particular, we show that MC-SGD can achieve competitive stability results as SGD with i.i.d. sampling scheme. By trading off the generalization and optimization errors appropriately, we establish the first-ever-knwwn excess generalization bound (11/v/) for MC-SGD where n is the size of training data. The key idea for handling Markov sampling structure of MC-SGD is to use the concept of on-average argument stability.
We first establish the connection between on-average argument stability and generalization for minimax optimization algorithms, which extends the existing work on uniform argument stability [38. We further develop stability bounds of SGDA with Markov sampling (MC-SGDA) for both smooth and non-smooth cases and obtain the nearly optimal convergence rates O(1/VT) for convex- concave problems in the form of both expectation and high probability, where T' is the number of iterations, from which its optimal population risk bound is established. Specifically, we consider several measures of generalization performance and show that the optimal population risk bounds OL1/vn) can be derived even in the non-smooth case.
To the best of our knowledge, this is the first-ever-knowe work on stability and generalization of SGD and SGDA under the Markov chain setting. Our results show that, despite the stochastic gradient estimator is biased and dependent across iterations due to the Markov sampling scheme, the general- ization performance of MC-SGD and MC-SGDA enjoys the same optimal excess generalization rates as the i.i.d. sampling setting.
Organization of the paper: We discuss the related work in Subsection I.] and formulate the problem in Section _ Section presents the stability and generalization results of MC-SGD for both smooth and non-smooth losses. Section devellop the first nearly optimal convergence rates for convex-concave problems of MC-SGDA, and show that the optimal risk bounds can be derived in both smooth and non-smooth cases. Section concludes the paper.
1.1 Related Work
In this subsection, review some further works which are closely related our paper.
Algorithmic Stability. Algorithmic stability characterizes the sensitivity of a learning algorithm when the inputs to the algorithm are slightly perturbed. The framework of algorithmic stability was established in a seminal paper [TT for the exact minimizer of the ERM problem, where the
uniform stability was established for strongly convex objective functions. Recent work 12 27 28
2

---

derived sharper generalization bounds for uniformly stable algorithms with high probability. Several other stability measures were later developed for studying the generalization of different learning algorithms including the hypothesis stability [1]], on-average stability [64], argument stability [47]
and total variation stability 71..
Stability and Generalization Analysis of SGMs. [3 established generalization error bounds of order ((1/vn) in expectation for SGD for convex and smooth problems using uniform stability, The on-average variance of stochastic gradients was used to refine the generalization analysis of SGD for non-convex problems [8). The results were improved and refined by [36] using a data-dependent notion of algorithmic stability for SGD. 39 introduced on on-average argument stability and studied the stability and generalization of SGD for general class of non- non-smooth convex losses, i.e., the gradient of the loss function is a-Hölder continuous. They also established fast generalization bounds (1//n) for smooth convex losses in a low-noise setting. The same authors also extended the analysis to the non-convex loss functions in [40]. Meanwhile, 6 addressed uniform argument stability of SGD with Lipschizz-continnn convex losses. Optimal generalization bounds were also developed for SGD
26 74 77 Stability and generalization for SGMs have been studied for pairwise learning 665 78 where the loss involves a pair of examples. In particular, [78] introduced a simple MC-SGD algorithm for pairwise learning where pairs of examples form special Markov chain f&r = (Za, 2,, 1) : t E N}. Here, 24, and 24, 1 are i.idd sampled from the training data of size n at time t and - 1, respectively. The uniform argument stability and generalization have been established (see more discussion on the difference between our work and [78] in Remark below).
in different settings 6 7
For minimax problems, 855 studied the weak generalization and strong generalization bounds in the weaely-coovxxxcoooe
setting. (25] established the optimal generalization bounds for proximal point method, while gradient descent ascent (GDA) is not guaranteed to have vanishing excess risk in convex-concave case. [38] proved that SGDA can achieve the optimal excess risk bounds of order (1/ /n) for both smooth and non-smooth problems in the convex-concave setting. They also extended their work to the nonconvex -onnooncavee problems. However, all the above studies the stability and generalization of SGD and SGDA under the assumption of the i.i.d. sampling scheme.
Convergence Analysis of MC-SGMs. The convergence analysis of SGD and its variants when the gradients are sampled from a Markov chain have been studied in different settings 1188 19 (2]
34|58 66,66] 70]. Specifically, [4 588 studied the Markov subgradient incremental methods in a
distributed system under time homogeneous and time non- non-homogeneous settings, respectively. [22 studied the convergence of stochastic mirror descent under the ergodic assumption. [69] established the convergence rate ((1/T with some E (1/2, 1) for convex problems. They also developed the convergence result for non-convex problems. In addition, decentralized SGD methods with the
gradients sampled from a non-reversible Markov chain have been studied in (68). [18] considered an accelerated ergodic Markov chain SGD for both convex and non-convex problems. 199 further
studied the convergence rates without the bounded gradient assumption. All these studies focused on the convergence analysis of MC-SGD for solving the ERM problems.
2 Problem Setting and Target of Analysis
In this section, we introduce the SGD for ERM and SGDA for solving minimax problems with Markov Chain, and describe the target of generalization analysis for both optimization algorithms.
Target of Generalization Analysis. Let W be parameter space in Rd and 'D be population distribution defined on sample space Z. Let f W x Z + [0, oo) be a loss function. In the standard framework of Statistical Learning Theory (SLT) 72), one aims to minimize the expected population risk, i.e., F(w)= := [f(]; =)], where the model parameter w belongs to W. and the expectation is taken with respect to (w..t.) 2 according to D. However, the population distribution is often unknown. Instead, we have access to a training dataset S = {2,- 2 with size n, where 2; is independently drawn from D. Then consider the following ERM problem
(Fs(w): == Σ f(w; w WEW
min
(I)
For a randomized algorithm A to solve the above problem, let A(S) be the output of algorithm A based on the dataset S. Then its statistical generalization performance (prediction ability) is measured by its excess population risk F(A(S)) - F(w"), i.e., the discrepancy between the expected risks of the model A(S) and the best model w E W. We are interested in studying the excess population risk.
3

---

Let A.. I denote the expectation w.r.t. both the randomness of data S and the internal randomness of A. To analyze the excess population error, we use the following error decomposition Es.alF(A(S)) F(w") = Es ((F())()( - Fs(A()))
+ (s.A(Fs(A(S))
Fs()")] (2)
The first term is called the generalization error of the algorithm A measuring the difference between the expected risk and empirical one, for which we will handle using stability analysis as shown soon. The second term the optimization error, which induced by running the randomized algorithm A to minimize the empirical objective. It can be estimated by tools from optimization theory.
As discussed in the introduction, many machine learning problems can be formulated as min- imax problems including adversarial learning (0), reinforcement learning [15 20 and AUC maximization [29] 46 81 87]. We are also interested in solving this type of problem. Let W and V be parameter spaces in Idd Let 'D be a population distribution defined on a sample space 2, and / W x V Z + [0, oo). We consider the minimax optimization problems: minwew maxvev { ((w, v) == Ez- (fw,vv));] In practice, we only have training dataset S= (=,,-,.. ...,,........................... )n independently drawn from DD and hence the minimax problem is reduced to the
following empirical version:
min max (Fs v) == 1 " 12
f(w.
(3)
NEW VEV
Since minimax problems involve the primal variable and dual variable, we have different measures of generalization [38, 85). For a randomized algorithm A(S) solving the problem (3), we denote the output of A as A(S) = (S)( (S)) for notation simplicity. Let E[. denote the expectation w.r.t. the randomness of both A and S. We are particularly interested in the following two metrics.
Definition (Weak Primal-Dual (PD) Risk). The weak Primal-Dual population risk of A(S), denoted by A (AA,,A)) is defined as maxvey E [AA(A (S). v)] -minwew E [[F((,,v (VS)). The corresponding (expected) weak PD empirical risk, denoted by 4mm Av), is de- fined by maxvev E. (F v)] minwew [Fsss,, Av())) (
Ammp AMw:AA) as the weak PD generalization error of the model We refer to A A ((AA,
Definition 2 (Primal Risk). The primal population and empirical risks of A(S) are respectively defined by R(AA (S)) = maxvey (Aw v), and Rs(Aw(()) = maxvev (AA (S), v). We (Sw)) as the primal generalization error of the model (S),,, and R(Aw(()) - minwew R(w) as the excess primal population risk.
refer to ((A
SGD and SGDA with Markov Sampling. One often considers SGD to solve the ERM problem [. Specifically, let W C Rdd be convex, (-ojw(() denote the projection to W, and af(w; z) denote a subgradient of f(w; z) w. Let Wo W be an initial point, and {ne } is stepsize sequence. For any E N. the update rule of SGD is given by
W: = Projw (w,-1- - n.0
(4)
where {i.} is generated from [n] = 21.2.... n with some sampling scheme. A typically sampling scheme is the uniform i.i.d. sampling, i.e., l is drawn randomly from [n] according to a uniform distribution with/without replacement.
In this paper, we are particularly interested in the case when i, [n]] is drawn from Markov Chain which is widely used in practice [3] 4 veal-valued entries. We say Markov chain {X+} } with finite state [n] and transition matrix P is time- home-hooogeneouu if, for k E N. i.j E [n]. and i i E [n]. there holds Pr(X*+1 = _] = i ....... Xx = i) Pr = X| i) = [P], Likewise, the SGDA algorithm with Markov sampling scheme is defined as follows. Specifically, let 0 and f denote the subgradients of f w.r.t. the arguments w and v, respectively. We initialize (Wo. vo) E W x V. for any E N, let (1.) is drawn from [n] according to Markov Chain. The update rule of SGDA is given by
18
22
34 66 69 70). Let P be an n x n-matrix with
Wr = Projw (W--1- - ff v;-1;; V1 (V.-1 + (w: v.
(5)
For brevity, we refer to the above algorithms as Markov chain-SGD (MC-SGD) and Markov chain- SGDA (SGDA), respectively. There are two types of randomness in MC-SGDIMC-SGDA. The first randomness is due to training dataset S which is i.i.d. from the population distribution D. The other randomness arises from the internal randomness of the MC-SGD/MC-SGDA algorithm, i.e. the randomness of the indices {ic). which is a Markov chain.

---

Remark 1. Convergence analysis mainly considers the empirical optimization gap, i.c., the dis- crepancy between (s()) and Fs(w*). Here, we are mainly interested in the generalization error which measures the prediction ability of the trained model on the test (future) data. As such, the purpose of this paper is to provide a comprehensive generalization analysis of MC-SGD and MC-SGDA in the framework of statistical learning theory. Specifically, given a finite training data S, let A(S) be the output of the MC-SGD for solving the ERM problem []. Our target is to analyze the excess population risk EE (F((S)) - F'(w"). Let A(S) (Aw (Aw(S): Av be the output of MC-SGDA for solving the empirical minimax problem ( our aim is to analyze the weak PD population risk (AAw.. Av) and the excess primal population risk R(Aw(S)) In both cases, the generalization analysis will be conducted using the algorithmic stability [T] 32) As we show soon below, the final rates are obtained through trade-offing the optimization error (convergence rate) and the generalization error (stability results).
minwew R(w).
Properties of Markov Chain. Denote the probability distribution of X₁ the non-negative row vector π. = (11(1), ( (2).... x² (n)), i.e., Pr(X; = 5) = n² (j). Further, we have Di= π (i) = 1. For the time- tome-homogeneous Markov chain, it holds x = - ==
x pp- for all & E N. Here, n² is initial distribution and p* denotes the k-th power of P. Markov chain is irreducible if, for any i.j E [n], there exists k such that [P*] > 0. That is, the Markov process can go from any state to any other state. State i E [r] is said to have period r if [Pk],,
j.i = 0 whenever le is not a multiple of and r is the greatest integer with this property. If 1 for every state i [n], then we say the Markoy chain is aperiodic. We say a Markov chain with stationary distribution II* is reversible if II (1)[Pks II [P) for all i, E [n]]
We need the following assumption for studying optimization error of MC-SGMs.
Assumption 1. Assume the Markov chain {&t) with finite state [n] is ame-homogeneous, irreducible and aperiodic. It starts from an initial distribution π.', and has transition matrix P and stationary distribution IT* with IT" (i) = = for any i [x)), i.e., limx-100 pk = I where 1,, E RR is the vector with each entry being and 1, denotes its transpose.
Remark 2. Our assumptions on Markov chains listed above are standard in the literature [8]
34
50
69
68 78 For instance, Markov chain-type SGD was proposed for pairwise learning which can apply to various learning task such as AUC maximization and bipartite ranking [1 83 87 22 46) and metric learning [35 75 76 79). This pairwise learning algorithm forms pairs of examples following special Markov chain {E. (Zi., Zig _ : t E N} where 2i, and = are i.i.d. sampled from the training data of size n at time t and - 1, respectively and, at time f. the model parameter is updated using gradient descent based on & As mentioned in Remark 3 of (78). {Er :t N) is Markov Chain satisfying all of our assumptions. Another notable example is the decentralized consensus optimization in multi-agent network, where the samples are accessed according a Markov chain and the number of states of the Markov chain equals the number of nodes in the network, which is finite. One always considers the same transition matrix P for each node and assumes the Markoy chain is irreducible and aperiodic [50]] 84
3 Results for Markov Chain SGD
In this section, we present the stability and generalization results of MC-SGD. Our analysis requires the following definition and assumptions. Let G, I. > 0 and || ||a denote the Euclidean norm.
Definition 3. We say is convex w.r.t. the first argument if, for any E Z and w, w' W, there holds f(w; 2) 2 f(w';2) + (0f(w';2), w
-w)). -
Assumption 2. Assume f is G-Lipschitz continuous, i.e., for any z E and w, w' W, there
holds (w;; 2) =(w < G|| w'll2.
Assumption 3. Assume f is L-smooth, i.e., for any e and w, w' E W. there holds f(w; 2)
f(w';=) < (w'; w w') + + w'
3.1 Stability and Generalization of MC-SGD
Let w arg minwew F(w) be the best model in W and WT = D 73 / My be the output of MC-SGD with T iterations. We will use algorithmic stability to study the generalization errors, which measures the sensitivity of the output model of an algorithm. Below we give the definition of on-average argument stability [3]].
5

---

Definition 4. (On-average argument stability) Let 5 = {z1...... .......,,,, )n and 5 = {2 .,.....,.... En be drawn
independently from D. For any i E [n], define ((1 = t Ri-1, 24, 11.1..... 2n as the set formed from S by replacing the i-th element with &, We say randomized algorithm on-average
e-argument-stable if LE S,3AA E (A(S) 1(s ||2 S
To obtain on an-average argument stability bounds of MC-SGD, our idea is to first write the stability as deterministic function according whether the different data point is selected, and then take the expectation w.r.t. the randomness of the algorithm. The detailed proofs are given Appendix [B.]]
Theorem (Stability bounds), Suppose f is convex and Assumption 2 holds. Let W = R and let A be MC-SGD with T' iterations.
(a) (Smooth case) Suppose Assumption holds and ny 2/TL. Then A is on-average e-argument- stable with c < 2G
E}=1 T/--
(b) (Non-smooth case) A is on-average t-argument-stable with e S 20 n3 1G + T/.
Remark 3. Without any assumption on Markov chain, Theorem I shows that argument stability bounds of MC-SGD are the order of (TT//n) and O OVTTT TT/ Tn/n) with a constant stepsize 17 for smooth and non-smooth losses, respectively. Both of them match the corresponding bounds for SGD with i.i.d. sampling 6 32 39 [4), which imply that stability of MC-SGD is at least not worse than that of the i.i.d. sampling case. The technical novelty here is to observe that, in the sense of on-average argument stability, we can use the calculation of E>(>>. [[a=]]] to replace that of [T, where I[ is the indicator function. This key step avoids the complicated calculations about E,A [[ Taking the uniform stability as example, we need to consider neighboring datasets differing by the i-th data, and can get Ba(l|w, willa] (n ===1 E =l)
O(n) Ej= E [PS-1] (A+)), which depends on the transition matrix P and is not easy to control. In contrast, with the on-average
stability we get stability bounds depending on E/= [/. which is always i.e., the on-average
stability allows us to ignore the effect of sampling process.
The following theorem presents generalization bounds for MC-SGD in both smooth and non-smooth cases, which directly follows from Lemma A.4 Theorem
Theorem 2 (Generalization error bounds). Suppose f is convex and Assumption 2 holds. Let W = Edd and let A be MC-SGD with T' iterations.
(a) (Smooth case) Suppose Assumption 3 holds and let nl = n S 2/L. Then there holds Es.A(F(Wr) - Fs(WT)] < 2G"Tu.
(b) (Non-smooth case) If ny = 7) then there holds (s.A(F(WT) - = OVVT=++TV 7)
3.2 Excess Population Risk of MC-SGD
In this subsection, we present excess population risk bounds for MC-SGD in both smooth and non-smooth cases. The proofs are given in Appendix B.3 We use the notation B x B if there exist universal constants C2 02
such that B < B < Cg B. Let (P) be the i-th largest eigenvalue
of the transition matrix P and X(P) = (max A2 (,), [An + 1)/2 E [1/2, 1). Let Kp be the mixing time and Cp be constant depending expressions are given in Lemma A.I We assume sup f(0; z) and | w=||2 are bounded.
P and its Jordan canonical form (detailed
Assumption 4. Assume the Markov chain {it) reversible with P PT.
Theorem 3 (Excess population risk for smooth losses). Suppose f is convex and Assumptions 7 2 3 and hold. Let W E Rd. Let A be MC-SGD with T iterations, and (w,) be produced by A with Wo 0 and ny nj S L. If we select T and n (T log())) -122, then Es.A [s.A[F(wir [[wr)] F(w") = (Tt.oo///////llgg////P
Remark 4. A term (Mon log (n)) with Mo minf /n CPn 1) appears in the excess risk bound of MC-SGD (see the proof of Theorem 3). which will be worse than /log(n)/ V when Kp p is large. Note Lemma A.I implies that this term will disappear if P is symmetric. Hence, introduce Assumption 4 to get the nearly optimal rate.

---

Theorem 4 (Excess population risk for non non-smooth losses), Suppose f. is convex and Assumptions
Ahold. Let W E R.. Let A be MC-SGD with T iterations, and (w; [w;} 1 be produced by A with fh
we select T x n² and T-4/4, then [s - F(w" = log (1)))))))
Remark 5. To estimate the excess population risk, we need the convergence rates of MC-SGD which can be found in Appendix B.2 [69 established convergence rate of (11/T1 with some q E [1/2,1] 1) under the bounded parameter domain assumption. We remove this assumption by showing [w:ll = O k= 17K) and obtain the nearly optimal convergence rate O(L/VT) with a careful choice of 1) = 1/ confidence- based bound for optimization error, which matches the bound in expectation up to a constant factor. We also provide the convergence analysis for non-convex problems in Appendix [B.2]
1/yTTog(TT.. To understand the variation of the algorithm,
present
Remark 6. Theorems 3 and show, after carefully selecting the iteration number T and stepsize 77. that the excess population risk rate (11/ (T) is achieved in both smooth and non omootho cases. Note 6 32 [3] show that the excess population risk rate (n))/n) is optimal for the i..d. sampling case. Therefore, our results for MC-SGD are also optimal since the i.i.d. sampling is special case of Markov sampling. Our results imply that despite the gradients are biased and dependent across iterations in Markov sampling, the generalization performance of SGD is competitive with the i.i.d. sampling case. Theorems also show the impact of the smoothness in achieving the optimal rate. The rate for the non-smooth case in Theorem 4 looks slightly better than the smooth case (Theorem B with logarithmic term. However, the optimal rate can be achieved with a linear gradient complexity (i.e., the total number of computing the gradient) for smooth losses, while Theorem implies that gradient complexity (n²²) is required for non-smooth losses.
Remark 7. According to Theorems 3 and 4 we can further observe how the transition matrix P affects the excess population risks. Indeed, the excess population risk rates are monotonically increasing w.r.t ((P). Particularly, the closer X(P) is to 1/2, the better the rate is. Let us consider two extreme examples. Suppose the Markov chain starts from the uniform distribution and has transition matrix P = 1, 1 MC-SGD degenerates to SGD with i.i.d. sampling in this case. The excess population risk rate ((I//n) is obtained from Theorem 4 with X(P) = 1/2. For a Markov chain moving on circle (i.e., if the chain is currently state i, then it goes to states + 1, and i with equal probability), we can verify that X(P) = O(1 - 1/n²). which implies a bad rate in this case. Remark 8. (78 proposed simple MC-SGD algorithm for pairwise learning associated with a pairwise loss f(w, 2, z²). Specifically, at iteration é, the algorithm update the model parameter as follows: W, = - T/ w f Zi, z;_., where zi, and - are i.i.d. sampled from the training data of size n. at time ( and ( - 1, respectively. In Remark 3 of [78). it was shown that {E: = (i,, 22) E [n]] x [n]] does form a time- homogenoous,, irreducible and aperiodic Markov chain. There are two key differences between our work and [78) Firstly, the work (78] used uniform stability directly due to =I = 1/n, while this term is not casy to control in our general setting (see Remark for details). To overcome this hurdle, we resort to the on-average stability and show that MC-SGD achieves the optimal excess risk rate. Secondly, the proofs there critically rely on the fact f(w,-1; Ri, 1) f(w 2,,, Zi,1 ) ((R-1) and the independence of w,-2 w.r.t. & and i- However, these specially tailored techniques for pairwise learning do not apply to the general Markov setting as we considered here.
4 Results for Markov Chain SGDA
In this section, we study the generalization analysis of MC-SGDA for minimax optimization problems. Let (Wr, Vr) be the output of MC-SGDA with T iterations, where
WT
T W n and VT
Σ n
7
(6)
We first introduce some necessary definitions and assumptions.
Definition 5. Let p 2 0 and g W x V + R. We say g is p-stoongly-oomvx--toongyyyyyoy (p-SC-SC) if, for any v E V, the function w ++ g(w, v) is p-strongly-conver and, for any w E W,
the function v + g(w, v) is p-strongly-concave. We say g is convex-concave if g is O-SC-SC.
The following two assumptions are standard 25 85
5 amounnts to saying f is Lipschitz continuous w.r.t. both and while Assumption 6 considers smoothness conditions.
7

---

Assumption 5. Assume for all w E W.v E V and E 2, 11 fw, v: G and [ v; => - G.
Assumption For any 2, assume the function (w, v) + f(w, v: is L-smooth, i.e. the following inequality holds for all w E W.v E V and E 2
[( Ow [ww[(w, v;2) Ow.((w' v2:z) 2) v; a.l(w', v
4.1 Stability and Generalization Measures
We use algorithmic stability to study the generalization of minimax learners. To this end, we first introduce the stability for minimax optimization problems.
Definition (Argument stability for minimax problems), Let S, 3 and st be defined as Definition 4 Let A be randomized algorithm and e >> O. We say A is on-average e-argument-stable for minimax problems if 1 - E [l - (5) +
S
The following theorem establishes a connection between stability and generalization. Part (a) shows that on-average argument stability implies generalization measured by the weak PD risk, while Part (b) shows that on-average argument stability guarantees a strong notion of generalization in terms of the primal risk under a strong concavity assumption. Theorem Wiil be proved in Appendix C.I.
Theorem 5 (Generalization via argument stability). Let A be randomized algorithm and O.
(a) If A is on-average c-argument-stuie stable and Assumption 3 holds, then there holds A t (Aw. Av) Amp (Aw; Av) Gc.
(b) If A is on-average t-argument-stable, the function + F(w, v) is p-strongly-comcave and Assumptions 5 66 hold, then we have Es.A R(A (S)) Rs (w (S)) S (1 + L/p)
In the following theorem develop stability bounds for MC-SGDA applied to convex-concave problems. The proof is given in Section C. of the Appendix.
Theorem 6 (Stability bounds). Assume for all z, the function (w, v) + f(w, v;2) is conver-concave.
Let W Rd and Assumption 5 hold, and let A be MC-SGDA with T iterations.
(a) (Smooth case) If A'Assuppptonn holds and Σド= ni S 1/(22²), then A is on-average e-argument stable with c S (G E3= n?) 1/2
n3) + 8/2G Σ} T1j-
(b) (Non-smooth case) A is on-average e-argument stable with é 200 2
/ 2
4V2G +4720 "
Remark For convex-concave and Lipschitz problems, the stability bound of the order Onr(VT+ T/n)) was established for SGDA with constant stepsize under the uniformly i.i.d. sampling setting. Under a further smoothness assumption, the stability bound was improved to the order of (n) [8). Our stability bounds in Theorem 6 match these results up to a constant factor and extend them to the Markov sampling case.
Remark 10. Let {(w) (i) (())) be the SGDA sequence based on S(6) The existing stability anal- (6) [3]] which crucially ysis (38 builds a recursive relationship for EA [| W. w + llv v
depends on the i.i.d. sampling property of i, E [n]]. This strategy does apply MC-SGDA since the conditional expectation over i, is in a much complex manner due to the Markov Chain sampling.
We bypass this difficulty by building recursive relationship for || ( 101 + ||v, -v:-- terms of a sequence of random variables T[ A key observation is that the effect of randomness would disappear if we consider on-average argument stability since >m [( = 1 for any t e N.
v [|2 in
We can combine the stability bounds in Theorem 0 and Theorem 5 to develop generalization bounds. We first establish weak PD risk bounds in Theorem 7 and then move on to primal population risk bounds in Theorem 8 The proofs are given in Section C.I of the Appendix.
Theorem 7 (Weak PD risk bounds). Suppose Assumption 5 holds. Assume for all z. the function (w, v) > f(w V; 2) is convex-concave. Let W IRd and {w;, vzYī=1 be produced by MC-SGDA with NT n7. Let A be defined by (S) WT and Av VT for (Wr, vr) in 6). Denote
w ggen == (Wr, VT)= - A A (WT, V.).
8

---

(a) (Smooth case) If Assumption 6 holds and Σ}= 1z 1 1/(212), then 'gen
4G (4 1)) 1/2 8v/2G² (b) (Non-smooth cuse) The weak PD risk satisfies w gen S 2V202 ( 1/22+ 2v/03 n
n
Σj= Th-
Theorem 8 (Primal risk bounds). Suppose Assumption 5 holds. Assume for all z, the function (w, v) f(w, v; 2) is convex-concave, and the function V + F(w, v) is p-strongly-concave Let W E and let {W3, "1 be produced by MC-SGDA with ni T7. Let A be defined by
(S) = Wr and A. VT for (Wr, VT) in 66. Denote ggn := Es.A ( RssWT)].
(a) (Smooth case) If Assumption 6 holds and Σラ n3 S 1/(212), then Ggon 4G²
[ n7)² + 2v2 Σ}= 75).
(b) (Non-smooth case) The primal population risk satisfies egnn L/p) 7)) 12)1222 + + - n1).
2V/00
4.2 Population Risks of MC-SGDA
Now we establish the population risk bounds for MC-SGDA. The following theorem establishes the weak PD population risk of MC-SGDA for both smooth and non-smooth problems. Let Dw and Dv be the diameters of W and V. The proof for Theorem 9 is provided in Appendix C.3
Theorem 9 (Weak PD population risk). Suppose Assumptions 7 and hold. Assume for all 2, the function (w.v)= ~ f(w, v; z) is convex-concave. Let {w Vjrzmi be produced by MC-SGDA with M = Let A be defined by Aw (S) = WT and (S) Vr for (WT, VT) in (6).
(a) (Smooth case) Let Assumption hold. IfT and x (T)) b, then A (WT, VT)
(log(n)) (//lo//////oolo///////////
(b) (Non-smooth case) If we select x n² and n x T 3, then we have
VT) =
O (1/(Vnlog(//XPP)
Remark 11. The above excess population risk bounds are obtained through the trade-off between the optimization errors (convergence analysis) and stability results of MC-SGDA. The convergence rates (()VVT) of MC-SGDA for minimax problems in both expectation and high probability are provided in Theorem C.3 and C.4 in Appendix C.2 With gradient complexity O(n), the minimax optimal excess risk bound 0 n) for SGDA with uniform sampling for smooth problems was established in (38]. We show SGDA with Markov sampling can achieve the nearly optimal bound with the same gradient complexity. For non- non-smooth problems, part (b) shows that the optimal excess risk bound can be exactly achieved with the gradient complexity ((n2).
Finally, we establish the following bounds for excess primal population risk under a strong concavity condition on v - F(w, v). which measures the performance of the primal variable. The proof for Theorem is provided in Appendix C33
Theorem 10 (Excess primal population risk). Suppose Assumptions 1 5 and 6 hold. Assume for all z, the function (w, v) + f(w, v;2) 2) is convex-concave. Assume + F(w, v) is p-strongly- concave. Let {w,, v be produced by MC-SGDA with nj = n. Let A be defined by Aw
Wr and (S) VT for (Wr, VT) in ().. If we choose T x n, x (Tlog(T))-1)) 11/2, then Es.A([((T))) - minwew R(w)= = ( (ooooo))) (oglo(///(())))
Remark 12. We show MC-SGDA attains population risk bounds of the order 0(1/vm) with linear gradient complexity O(n), which are minimax optimal up to a logarithmic factor. This implies that considering sampling with a Markov chain does not weaken the learnability. Theorems and also show the effect of P on the population risk rates, i.c., the rates get better as X(P) decreases.
Conclusion
We develop the first-ever- known stability and generalization analysis of Markov chain stochastic gradient methods for both minimization and minimax objectives. In particular, we establish the

---

optimal excess population bounds (L) for MC-SGD for both smooth and non- non-smooth cases. We also develop the first nearly optimal convergence rates ((L/VT) for convex-concave problems of MC-SGDA, and show that the optimal risk bounds O /n) can be derived even in the non- smooth case. Although the gradients from Markov sampling are biased and not independent across the iterations, we show the performance of MC-SGMs is competitive compared to SGMs with the classical i.i.d. sampling scheme. An interesting direction is to consider other variants of SGMs with variance reduction techniques and differentially private SGMs under the Markov sampling scheme.
Acknowledgement. The work described in this paper is partially done when the last author, Ding- Xuan Zhou, worked at City University of Hong Kong, supported by the Laboratory for Al-Powered Financial Technologies under the InnoHK scheme, the Research Grants Council of Hong Kong [Projects No. CityU 11308121, 12,, No. N N_CittNUCOOO 102/220 and No. C1013-21GFJ, the National Science Foundation of China [Project No. 1206 160462], and the Hong Kong Institute for Data Science The corresponding author is Yiming Ying whose work is supported by SUNY-IBM AI Alliance Research and NSF grants 210-520,,, IIS-21 10546 and
References
[1] S. Agarwal and P. Niyogi. Generalization bounds for ranking algorithms via algorithmic stability, Journal of Machine Learning Research, 10(Feb):441-477 2009.
[2] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pages 214-223. PMLR, 2017.
[3] Y. F. Atchadé, G. Fort, and E. Moulines. On perturbed proximal gradient algorithms. The
Journal of Machine Learning Research, 18(1):310-342, 2017.
[4] G. Ayache and S. El Rouayheb. Private weighted random walk stochastic gradient descent. IEEE Journal Selected Areas in Information Theory, 2(1):452-463, 2021.
[5] Bach and E. Moulines. Non-strongly-conves smooth stochastic approximation with conver- gence rate O(1/n). In Advances in Neural Information Processing Systems, pages 773-781, 2013.
[6] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Advances in Neural Information Processing Systems, 2020. [7] R. Bassily, V. Feldman, K. Talwar, and A. G. Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Prucessing Systems, pages 11279-1 1288, 2019.
[8] R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman. Algorithmic stability for adaptive data analysis. SIAM Journal on Computing, (50):377-400 2021.
[9] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford university press, 2013.
[10] O. Bousquet, S. Boucheron, and G. Lugosi. Introduction to statistical learning theory. In Summer school on machine learning, pages 169-207. Springer, 2003.
[11] O. Bousquet and A. Flisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[12] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy, Sharper bounds for uniformly stable algorithms.
In Conference on Learning Theory, pages 610-626. PMLR, 2020.
[13] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 744-753, 2018.
[14] Chen, J. Towfic, and A. H. Sayed. Dictionary learning over distributed models. IEEE Transactions on Signal Processing, 63(4):
2014.
[15] B. Dai, A. Shaw, L. Li, L. Xiao, N. He, Z. Liu. J. Chen, and L. Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Conference on Machine Learning, pages 1 1125-11333 1134, 2018
[16] E. Diana, W. Gill, M. Kearns, K. Kenthapadi, and A. Roth. Minimax group fairness: Algorithms and experiments. Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 66-76, 2021.
10

---

[17] A. Dieuleveut and F. Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statisties, 44(4):1363-1399) 2016.
[18] T. T. Doan, L. M. Nguyen, N. H. Pham, and J. Romberg. Convergence rates of acceler- ated markov gradient descent with applications in reinforcement learning. arXiv preprint arXiv:2002.022 020703,,........2 2020.
[19] T. T. Doan, L. M. Nguyen, N. H. Pham, and J. Romberg. Finite-time analysis of stochastic gradient descent under markov randomness. arXiv preprint 2003 2020. [20] S. S. Du, J. Chen, L. Li, L. Xiao, and D. Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pages 1049-1058, 2017.
[21] J. Duchi and Y. Singer. Efficient online and batch learning using forward backward splitting, In Advances in Neural Information Processing Systems, pages 495-503, 2009.
[22] Duchi, Agarwal, M. Johansson, and M. I. Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(():1549- 10781 2012.
[23] J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):592-
606, 2011.
[24] A. Elisseeff. T. Evgeniou, and M. Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79, 2005.
[25] F. Farnia and A. Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. In International Conference on Machine Learning, pages 3174-3185. PMLR,
2021.
[26] V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[27] V. Feldman and J. Vondrak. Generalization bounds for uniformly stable algorithms. In Advances in Neural Information Processing Systems, pages 9747-9757, 2018.
[28] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279. PMLR, 2019.
[29] W. Gao, R. Jin, S. Zhu, and Z. Zhou. One-pass auc optimization. In International Conference on Machine Learning, pages 906-914, 2013.
[30] I. Goodfellow, Pouget-Abadie, M. Mirza, Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 27:2672-2680, 2014.
[31] M. Hardt and Ma. Identity matters in deep learning. arXiv preprint 16Xiv: (ene::111..02111 .04231, 2016. [32] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning, pages 1225-1234. PMLR, 2016. [33] B. Johansson, M. Rabi, and M. Johansson. A simple peer-to- -ee-rtrrrrrrrreee algorithm for distributed optimization in sensor networks. In 2007 46th IEEE Conference on Decision and Control, pages 4705-4710. IEEE, 2007.
[34] B. Johansson, M. Rabi, and M. Johansson. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Oplimization, 20(3):
11 1170, 2010.
[35] B. Kulis al. Metric learning: survey. Foundations and Trends@ in Machine Learning,
5(4):287-3644 2013.
[36] I. Kuzborskij and C. Lamperr. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2820-2829, 2018
[37] G. Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer Nature, 2020.
[38] Y. Lei, Z. Yang. T. Yang, and Y. Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, 2021.
[39] Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Leurning, pages 5809-5819. PMLR, 2020. [40] Y. Lei and Y. Ying. Sharper generalization bounds for learning with gradient-domintt objective functions. In International Conference on Learning Represemations, 2020.
11

---

[41] T. Li, M. Sanjabi, A. Beirami, and V. Smith. Fair resource allocation in federated learning. arxiv preprint arXiv: 10497, 2019.
[42] X. Li and F. Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 983-992. PMLR, 2019.
[43] J. Lin and L. Rosasco. Optimal learning for multi-pass stochastic gradient methods. In Advances 2016.
in Neural Information Processing Systems, pages
[44] T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-coneawe minimax problems. In International Conference on Machine Learning, pages 6083-6093, PMLR, 2020. [45] M. Liu, Z. Yuan, Y. Ying. and T. Yang. Stochastic auc maximization with deep neural networks. arXiv preprint arXiv: 1908. 10831, 2019.
[46] M. Liu, X. Zhang, Z. Chen, X. Wang, and T. Yang. Fast stochastic AUC maximization with converrecee rate. In International Conference on Machine Learning, pages 3195-3203, 2018.
[47] T. Liu, G. Lugosi, G. Neu, and D. Tao. Algorithmic stability and hypothesis complexity. In International Conference Machine Learning, pages 2159-2167, 2017.
[48] C. G. Lopes and A. H. Sayed. Incremental adaptive strategies over distributed networks. IEEE Transactions on Signal Processing, (5(8))406444077, 2007.
[49] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint T.Eiv:1706.06000
2017.
[50] X. Mao. K. Yuan, Y. Hu, Gu, A. H. Sayed, and W. Yin. Walkman: communication-effiete
random-walk algorithm for decentralized optimization. IEEE Transactions on Signal Processing. 68:2513-2528, 2020.
[51] N. Martinez, M. Bertran, and G. Sapiro. Minimax pareto fairness: multi objective perspective. In International Conference on Machine Learning, pages 6755-6764. PMLR, 2020. [52] M. Mohri, G. Sivek, and A. T. Suresh. Agnostic federated learning. In International Conference on Machine Learning, pages 4615-4625, PMLR, 2019.
[53] A. Nedic and S. Lee. On stochastic subgradient mirror-descent algorithm with weighted averaging. SIAM Journal Optimization, 24(1))84-107, 2014.
[54] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach
to stochastic programming. SIAM Journal on Optimization, 19(4):1574-160) 2009.
[55] R. Oldenburger. Infinite powers of matrices and characteristic roots. Duke Mathematical Journal, 6(2):357-361, 1940.
[56] H. Rafique, M. Liu, Q. Lin, and Yang. Weakly-conve--come concave min-max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software,
pages 1-35, 2021.
[57] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference International Conference on Machine Learning, pages 1571-1578, 2012.
[58] S. S. Ram, A. Nedić, and V. V. Veeravalli. Incremental stochastic subgradient algorithms for convex optimization. SIAM Journal on Optimization, 20(2):691 2009.
[59] H. E. Rauch, Tung, and C. T. Stricbel. Maximum likelihood estimates of linear dynamic systems. AIAA journal, 148::14451450, 1965.
[60] R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization. 14(5):877-898, 1976.
[61] A. H. Sayed. Adaptive networks. Proceedings of the IEEE, 102(4):460 497,099994000 2014.
[62] M. Schmidt, N. Roux, and F. Bach. Convergence rates of inexact proximal-gradinn methods
for convex optimization. In Advances in Neural Information Processing Systems, 2011.
[63] S. M. Shah and K. E. Avrachenkov. Linearly convergent asynchronous distributed admm via markov sampling. arXiv preprint arXiv:1810.000 05067, 2018.
[64] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11:2635-2670. 2010.
[65] W. Shen, Z. Yang, Y. Ying, and X. Yuan. Stability and optimization error of stochastic gradient descent for pairwise learning. Analysis and Applications, pages 1-41, 2019.
12

---

[66] S. Smale and D.-X. Zhou. Online learning with markov sampling, Analysis and Applications,
7(01):87-113, 2009.
[67] P. Smyth. Hidden markov models for fault detection in dynamic systems. Pattern recognition,
27(1):149-164, 1994.
[68] T. Sun and D. Li. Decentralized markov chain gradient descent. arXiv preprint
ArXiv:1909.1022: 10238, 2019.
[69] T. Sun, Y. Sun, and W. Yin. On markov chain gradient descent. In Advances in neural
information processing systems, 2018.
[70] V. B. Tadić and A. Doucet. Asymptotic bias of stochastic gradient search. The Annals of Applied Probability, 27(6))
2017.
[71] E. Ullah, T. Mai, A. Rao, R. Rossi, and R. Arora. Machine unlearning via algorithmic stability,
arXiv preprint arXiv:2 13179, 2021.
[72] V. Vapnik. The nature of statistical learning theory. Springer science business media, 1999. [73] S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence sgd for over-parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1195-12044 1204. PMLR, 2019.
[74] P. Wang. Y. Lei, Y. Ying, and H. Zhang. Differentially private sgd with non-smooth losses. Applied and Computational Harmonic Analysis, 56:306-336, 2022.
[75] K. Q. Weinberger and L. K. Saul. Distance metric learning for large margin nearest neighbor classification. Journal of machine learning research, 10(2), 2009,
[76] E. Xing, M. Jordan, S. J. Russell, and A. Ng. Distance metric learning with application to clustering with side-information. Advances neural information processing systems, 15, 2002.
[77] Z. Yang, Y. Lei, S. Lyu, and Y. Ying. Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss. In International Conference on Artificial Intelligence and Statistics, pages 2026-2034. PMIR, 2021.
[78] Z. Yang. Y. Lei, P. Wang. T. Yang, and Y. Ying. Simple stochastic and online gradient descent algorithms for pairwise learning. Advances in Neural Information Processing Systems, 34, 2021.
[79] Y. Ying and P. Li. Distance metric learning with eigenvalue optimization. The Journal of Machine Learning Research, 13(1):1-26, 2012.
[80] Y. Ying and M. Pontil. Online gradient descent learning algorithms. Foundations of Computa- tional Mathematics, $(5):561-590 2008
[81 Y. Ying. L. Wen, and S. Lyu. Stochastic online auc maximization. Advances in neural information processing systems, 29, 2016.
[82] Y. Ying and D.-X. Zhou, Online regularized classification algorithms. IEEE Transactions on Information Theory, 52(1 ((17)77775-4888, 2006.
[83] Y. Ying and D.-X. Zhou. Online pairwise learning algorithms. Neural computation, 28(4))743-
777, 2016.
[84] S. Zeng, T. T. Doan, and J. Romberg. Finite-time analysis of decentralized stochastic approxi- mation with applications in multi-agent and multi-task learning. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2641-2646. IEEF, 2021.
[85] J. Zhang, M. Hong, M. Wang, and S. Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statistics, pages 468-576, PMLR, 2021.
[86] T. Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. International Conference on Machine Learning, pages 919-926, 2004.
[87] Zhao, S. C. Hoi, R. Jin, and T. Yang. Online AUC maximization. International Conference on Machine Learning, pages 233-240, 2011.
[88] Y. Zhou, Y. Liang, and H. Zhang. Generalization error bounds with probabilistic guarantee for SGD in nonconvex optimization. arXiv preprint arXiv: 1802:00903033 2018
Checklist
1. For all authors...
13

---

(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? [Yes]
(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 set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(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)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "uWDa8kgB0Wo", "reviewer": "Reviewer_FPYp", "summary": "The paper studies generalization ability and excess risk of a one-sample SGD with averaged iterates where selection of samples happens according to the Markovian process rather than i.i.d. The paper attacks the problem from the algorithmic stability viewpoint, namely the analysis looks at the expected excess risk (in a realizable setting) as a decomposition of the generalization error and optimization error. The generalization error is controlled by stability of such a variant of SGD (as for instance in the well-known analysis of Hardt et al.), while analysis of the optimization error relies on known results. The paper analyzes excess risk for both smooth and non-smooth convex losses under appropriate tuning of step sizes. In both cases, as one would expect, the bound is controlled by the spectral gap. The paper considers extreme cases, of the sampling process, such as i.i.d. and sample on a cycle --- at the very least in the i.i.d. case the bound seems to coincide with known results. For non-convex smooth losses the paper also does a stationary-point convergence analysis in the style of Ghadimi-Lan (presented in appendix).\n", "questions": "Since the Markov chain considered here is aperiodic, it seems that one can consider SGD without replacement as a special case. How does the excess risk rates obtained in this work compare to the known results in this more challenging SGD variant?", "limitations": "Yes, the paper discussed relevant limitation pertaining to the algorithmic stability analysis.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The stability analysis essentially follows the on Hardt et al. for SGD with a nuance regarding the sampling of SGD indices. While in the analysis of Hardt et al. one assumed a uniform sampling, in the present paper the proof introduces an indicator, which technically can work with any sampling index sampling procedure. Now, it that the key insight is a realization that averaging parameter stability over the training sample takes out the effect of sampling procedure (averaging of aforementioned indicators). As such the resulting stability bound is completely free from the effects of the Markov sampling process, i.e. the same as one would get in the i.i.d. case. Moreover, it seems that this works out not only for Makovian sampling, but *any* sampling. This seems quite surprising, and perhaps could be attributed to the in-expectation nature of the bound. This might seems as, perhaps, even trivial, but when combined with the bound optimization error it provides a rather clean method to obtain excess risk bound with Markovian SGD -- this is definitely a strength of the paper.\n\nAssumptions on the Markov chains considered here seem to be rather limiting and the paper does not discuss relevant cases/examples where do these hold, could be used (for instance, which cases in ML those cover, which cases in RL, are these realistic?). While, technical result is nice, it could be better elucidated with examples. ", "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": "skOiyKaBh0p", "reviewer": "Reviewer_4yCq", "summary": "The authors proposed a generalization analysis of MC-SGD and MC-SGDA for stability in both smooth and non-smooth problems based on statistical learning theory. The authors could establish the same generalization bound $O(1/\\sqrt{n})$ as in the i.i.d sampling scheme.", "questions": "I am not an expert in this area, but I want to hear more about why or/ and when Monte Carlo sampling is better than i.i.d sampling. Maybe Monte Carlo sampling has certain benefits under a few limited scenarios, but the study on concrete properties of such a setup seems not interesting.\n\n", "limitations": "NA", "rating": 4, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. The authors propose the first generalization performance of MC-SGD and MC-SGDA with Markov sampling and the rate is the same as the i.i.d sampling scheme.\n\n2. The relation and connection between on-average argument stability and uniform argument stability seem useful.\n\nCons: \n\n1. The reason why we should adopt Markov chain sampling is not clearly motivated. Although there is a paper cited [1], the benefits of Monte Carlo sampling are not elaborated or detailed enough, which is hard for researchers outside this community to judge why it is useful.\n\n2. The technical tools used are fairly standard and elementary and the study on the generalization performance of a concrete algorithm seems routine.\n\n[1] On Markov Chain Gradient Descent. 2018", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "jZGt4EZFzFk", "reviewer": "Reviewer_5dM2", "summary": "This paper studies the generalization performance of Markov chain stochastic gradient methods for both minimization problems and minimax optimization problems. The analysis is performed by using the method of algorithmic stability in learning theory. In particular, the paper shows that for ERM problems, MC-SGD can achieve similar stability results as SGD by introducing an on-average stability argument. The paper first studies generalization performance and then obtains bounds for the excess population risk of MC-SGD. For minimax problems, the paper extends existing results on uniform stability by relating on-average argument stability and generalization error. In particular, it obtains generalization and population bounds for MC-SGDA.  ", "questions": "1. In line 44, the only justification for using Markov chain SGMs instead of i.i.d. sampling schemes is stated as performing \"more efficiently\". I think it would be beneficial to further explain the reason for using these Markov chain methods (instead of i.i.d. schemes) in the introduction. \n\n2. The results of Section 3 hold when the parameter space $\\mathcal{W}$ is bounded and has diameter $D$, as assumed in line 260. Is it possible to handle cases when $\\mathcal{W}$ is unbounded?\n\n3. The main contributions of the paper stated in line 52 can be made as a separate paragraph or subsection to make it stand out and to be read more easily.\n\n4. Abstract: There are a large amount -->  There is a large amount ", "limitations": "The authors have adequately addressed the limitations of their work.", "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 generally well-written and well-structured. Although I am not very familiar with prior work in this research direction, it seems to me that the paper has good quality and adequate originality for publication. Related work in the literature seems to be sufficiently cited in Subsection 1.1. As mentioned in that subsection, generalization bounds for SGD with i.i.d. sampling scheme has been previously derived using the stability argument for convex and smooth losses. This paper builds upon these works to obtain interesting results for MC-SGMs.  \n\nThere are some parts of the paper that can be improved, as I mention here and below. The organization of the paper starting from line 72 can be further expanded to discuss in more detail what are the goals of each section of the paper. The reason for stating Assumption 4 in line 264 is better to be further elaborated, in particular, what \"extreme setting\" means in that context. ", "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