Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm
Authors: Miaoxi Zhu
Li Shen
Bo Du
Dacheng Tao
Venue: NeurIPS 2023 poster (2023)
Keywords: decentralized algorithm
minimax problem
algorithmic stability
generalization analysis
TL;DR: This paper provides a comprehensive generalization analysis for decentralized-SGDA using the approach of algorithmic stability.

Abstract: The growing size of available data has attracted increasing interest in solving minimax problems in a decentralized manner for various machine learning tasks. Previous theoretical research has primarily focused on the convergence rate and communication complexity of decentralized minimax algorithms, with little attention given to their generalization. In this paper, we investigate the primal-dual generalization bound of the decentralized stochastic gradient descent ascent (D-SGDA) algorithm using the approach of algorithmic stability under both convex-concave and nonconvex-nonconcave settings. Our theory refines the algorithmic stability in a decentralized manner and demonstrates that the decentralized structure does not destroy the stability and generalization of D-SGDA, implying that it can generalize as well as the vanilla SGDA in certain situations. Our results analyze the impact of different topologies on the generalization bound of the D-SGDA algorithm beyond trivial factors such as sample sizes, learning rates, and iterations. We also evaluate the optimization error and balance it with the generalization gap to obtain the optimal population risk of D-SGDA in the convex-concave setting. Additionally, we perform several numerical experiments which validate our theoretical findings.

Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm
Miaoxi Zhu Li Shen Bo Du Dacheng Tao
1 School of Computer Science, National Engineering Research Center for Multimedia Software, Institute of Artificial Intelligence and Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University, China 2 JD Explore Academy, China 3 The University of Sydney, Australia {zhumx, dubo)@whii @whu. edu.cn, {mathshenli dacheng taw.egmaaaiiiaaa. com
Abstract
The growing size of available data has attracted increasing interest in solving minimax problems in decentralized manner for various machine learning tasks. Previous theoretical research has primarily focused on the convergence rate and communication complexity of decentralized minimax algorithms, with little atten- tion given to their generalization. eralization bound of the decentralized stochastic gradient descent ascent (D-SGDA) algorithm using the approach of algorithmic stability under both convex-concave and nonconvex-nonee -onconcave settings. Our theory refines the algorithmic stability in decentralized manner and demonstrates that the decentralized structure does not destroy the stability and generalization of D-SGDA, implying that it can generalize as well as the vanilla SGDA certain situations. Our results analyze the impact different topologies on the generalization bound of the D-SGDA algorithm beyond trivial factors such as sample sizes, learning rates, and iterations. We also evaluate the optimization eπгоr and balance it with the generalization gap to obtain the optimal population risk of D-SGDA in the convex-concave setting. Additionally, perform several numerical experiments which validate our theoretical findings.
this paper, investigate the primal-dual gen-
Introduction
Minimax problems have shown extensive applications machine learning, such as adversarial robustness [26, 16), GAN [11], the zero-sum game [27], multi-agent reinforcement learning [33], AUC maximization [41]. Alongside this, as the use of large-scale models has become widespread, distributed learning algorithms have emerged as a noteworthy approach for handling massive amounts of data and model parameters [5, 1]. Without a parameter server [20] aggregating all data from each local agent, decentralized algorithms that do not rely on the central structure can be advantageous when network bandwidth low or latency is high, and they can also protect data privacy(21]. J. this work, consider the following decentralized minimax stochastic optimization problems:
70
min max F(x, v) = m > Fl v) 2EX yEy
Eg
(1 vi
(I)
where m denotes the number of agents, F; is the local loss function, &, represents local data stored on agent i, and X' C Rd= y C Rdv, Note that the data distributions D; may differ across the agents.
The most straightforward algorithm for solving the above stochastic minimax optimization problem apply Stochastic Gradient Descent Ascent (SGDA) [14, 22] in a decentralized manner, named
"Coreesooning authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table Main results on different cases: SC-SC, C-C, and NC-NC represent woongly-oovee--tttooglyoocese strongly-coneave.
convex-concave, and Donconyex-nonconeewvy respciicy O means it contains the logarithmic function. C2 is constant concerning about the spectral gap 1- different topology which is defined in Thm. 2. T represents iterations. L is Lipschitz constant. represents the strong convexity and strong concavity parameter. a denotes the sample size in each node. m denotes the number of nodes and 0 < S 1 is configurable constant.
Cases
Measure
Bound
strong/weak primal-dual generalization gap
Ö
Cj Tz#a
(Thm. 2]
SC-SC
n
strong/weak primal-dual population risk
C2
[Thm. 3]
muin
7
weak primal-dual generalization gap
+
[Thm. 4]
C-C
r
weak primal-dual population risk
Thm. 5]
(1-1)7
3
NC-NC
weak primal- dual generalization gap
o )
riz
[Thm. 6]
D-SGDA, Many algorithms [36, 7, 10, 43, 35, 38, 25, 12, 24, 34. 2] have been proposed to solve
Problem (1). As for the theoretical part, they mainly focus on analyzing the convergence behavior and communication complexity of their proposed algorithms. Due the inaccessibility of the data distribution D;, they approximate the expectation value by averaged sum on the training dataset = (S....,, S with local samples Êiu, stored in local dataset S, = (EA,,
m
min max Fs(w; v), with Es y) =EX DEy
Fs, (
(2)
However, it is insufficient to evaluate the stochastic algorithm not to consider the generalization performance, which is roughly the gap between Eq. (1) and Eq. (2). Generally speaking, saddle point of Fs (z, y) may not be the optimal solution of min maxy F F( y). As result, the model learned by Eq. (2) may not perform well on the test dataset. In fact, the generalization gap is a crucial criterion for us to foresee the performance of the trained model on the unknown dataset. Furthermore, it is quite necessary for us to make a trade-off between the optimization error and the generalization gap to obtain models with optimal population risk (see Eq. (1)).
Concerning the stability and generalization of the minimax problem, several works [19, 30, 9, 924 have studied the generalization gap and population risk of some algorithms, including SGDA, SGDmax, PPM, and AGDA. However, these results cannot be directly extended to the decentralized case due to the additional communication step during the training process. Intuitively, the number of nodes and communication topology decentralized training may exert a potential influence on the model's generalizability. Note that even for the decentralized minimization problem, the generalization and stability of decentralized SGD are adversely affected by an extra non- non-vsiihinn term [32]. and the stability usually suffers from constant term X [44], compared to vanilla SGD. Building upon these findings, we argue that is worthy to investigate the generalization and stability of D-SGDA for decentralized minimax problems, where there do exist more newly unveiled problems.
To mitigate this theoretical deficiency, we present the first comprehensive analysis of the stability and generalization of D-SGDA for the decentralized minimax problem in this paper. Specifically, we develop a refined stability analysis in a decentralized manner and derive the generalization gap and population risk for D-SGDA under different settings. The main theoretical results are summarized in Table And our main contributions are summarized as follows:
First work on the stability and generalization of D-SGDA for decentralized minimax problem. We extend the concepts of algorithmic stability, which includes argument stability and weak stability, to the decentralized setting. And we establish a universal connection between argument stability and different measures of generalization gap in the framework of decentralization. We propose subtle technique to distribute the "different" samples in the neighboring datasets among agents by methods of permutation and combination.
New theoretical results. Our theoretical results reveal that decentralized structure does not hurt the stability and generalizability of D-SGDA compared with SGDA and explain how topology of the communication network influences the performance in segely--ovvex-sronngge

---

convex-concave and nonconvex nonconcave conditions (see Table 1,2). We also evaluate the optimization error and leverage with generalization gap to obtain the optimal population risk. Experiments. We provide several numerical experiments on AUC maximization (C-C) and adver- sarial learning (NC-NC) in which we vary different factors to support our theoretical findings. The preliminary experimental results align with our theoretical insights.
Nonconvex-noneomeace
2
Related Work
Decentralized minimax problem. Existing works mainly focus on improving the convergence rate and communication complexity. Liu et al. [23] propose DPOSG, which is firstly applied in case of nonconvex-nonconeayy i.e., GAN training, and they prove O(c-12) computational complexity and (loo((//c) communication complexity on the busiest node. Xian et al. [36] propose DM-HSGD with convergence rate of ( and Chen et al. [7] propose DREAM with communication rounds of (/xx"=////I X2) in nonconvex-stronge sttongly-connant condition. Chen et al. [6] propose SPIDER- GDA and achieve stochastic first-order oracle of ((n + (oogg under two-sided PL condition. Rogozin et al. [31] propose a Mirror-prox based algorithm with O(e-t) communica- tion complexity in C-C setting. Huang [15], Luo and Ye [25] accelerates by variance reduction. Beznosikov al. [3] considers time-varying networks with heterogeneous data, Kovalev et al. [18] provides a rigorous complexity for decentralized variational inequalities.
Stability and generalization. There mainly two approaches to investigating the generalization: algorithm-indepeedent generalization, which is also called uniform convergence generalization, and algorithn-dependent generalization respectively. Where the former may degrade to a vacuous conclu- sion in [28] and we adopt the latter method in our paper which can better explain the generalization behavior of detailed algorithm. Bousquet and Elisseeff [4] come up with algorithmic stability, Elisseeff et al. [8] extend the concept to randomized algorithms. Hardt et al. [13] further develop the framework by connecting algorithmic stability with the generalization gap. Sun al. [32] and Zhu et al. [44] extend the generalization and stability analysis to D-SGD. In the minimax problem. Zhang al. [42] focus on argument stability and prove (1/nn) weak and strong generalization bounds for the SC-SC condition; Farnia and Ozdaglar [9] analyze the uniform stability and generalization gap GDA. GDmax, and PPM (proximal point method) in the case of NC-NC and Lei et al. [19] summarize the connection between different measures of stability and generalization gap and further probabbbbbbiltty results. Xing et [37] specify the generalization gap for adversarial training and Yang et al. [39] investigate the sability-basee generalization of SGDA with differential privacy constraints. Ozdaglar et al. [30] propose a new metric to better evaluate the generalization performance even in the case when the existing metric fails.
develop the corresponding
3 Problem Formulation
In this section, we provide the necessary assumptions, notations, terminologies of population risk, generalization gap, and algorithmic stability in decentralized minimax problems.
3.1 Basic Assumptions
Notations. We use bold lower case to denote vectors and bold upper case to denote matrices. || I|2 means &g norm for vectors and || || means Frobinius norm for matrices, and we will omit the subscript when the type of norm is clear from the context. 11, E R² denotes the all-one vector and Xx(+) represents the i-th largest eigenvalue of a matrix. [ni] == 21.,,..., n..
Assumption 1 (Lipschitz continuous). Each local function fa is differentiable and there exists G > 0 that fa is G-Lipschitz continuous with respect to both and y on any given sample E,, i.e.,
x ).
(x E.) f((a', v.::) S
y V
Assumption (Lipschitz smooth). Each local function fa is differentiable and there exists that fú is L-Lipschitz smooth with respect to both æ and on any given sample & i...
V=fia, Es) Vali(a', g I
)l
s
- x' v
)
Vyfi(m, Pufi(er'u''Es
3

---

Definition 1 Convexity-Concaviigy For each local loss function fx y: Er), we say that fi is Me Ms-Stonngly convex on for any given y and on any given sample &.. there holds:
ft'a', y: 2 f1 v. + Vafi( 5.).)" (æ' - x) + Mrr || - ==I2, M 2 O, Vax x'.
2
we say that f. is My Strongly concave on if for any given æ and on any given sample É.. there holds:
fa y (.)= S f, + (.. - y) Me lly y y 14 2 0, Vy.y'.
We can call it is convex w.r.t. a when j 0 and concave w.r.t. y when Pa 0. Remark 1. Assumptions about the Lipschitz continuity and smoothness are commonly used in the context of decentralized minimax optimization problems [42, 9, 32].
3.2 Decentralized Stochastic Gradient Descent Ascent (D-SGDA)
In decentralized setting, each node will exchange information alternatively and represent the communication network between nodes as G -VV.E), which is a connected graph with node set {1,2, m) and edge set S x V. Specifically, (i,1) E & indicates that agent I can receive information from agent and therefore we symbolize the in and out neighbors as (i) & {l E V, (1, E E} and (Nou( (i) A {I E V. (i, E E respectively. In an undirected graph, there is no consideration about the order, thus (i, E implies (1, and the in and our neighbors are identical which we will abbreviate as N for brief. In our work, we focus on undirected graphs. The communication graph is associated with an adjacency matrix, which is also called a mixing matrix, W [wرy]] E Rmmxm. It implies the connection between m agents that wij > 0 if and only if (j,1) E &, otherwise Wij O. And there are some basic assumptions about the mixing matrix which is commonly used in decentralized settings [17, 21, 23, 32].
Assumption 3 (Mixing matrix). We assume the mixing matrix W = [wa]] E [0, 1|mmx defined on the graph G (V,E) is symmetric doubly stochastic matrix, which holds the property that W W and W1. m = m, 1. W = T Besides, we assume X = max (22) Pm (W)I E (0,
For symmetric doubly stochastic matrix, W holds the property that: A 1. For different topologies, X + 1 implies the sparsity while À - 0 implies the complete connection. Nedić et al. [29] and Ying et al. [40] list upper bounds for the spectral gap communication network. More knowledge on decentralized optimization is placed in Appendix A.
the commonly
In this paper, we study the decentralized minimax problem solved via D-SGDA (see Algorithm I). We use the superscript to de- note the 1-th iteration and the subscript to denote the i-th local agent. During iteration, each client first computes its local gradient approximation by V (n v²: (c) and V Vyfi( y!: (o)) respectively where (i) is randomly chosen from [n]. Then each client communicates with its neighbor Aii) and updates by SGDA.
Algorithm 1 D-SGDA
Initialize: x.- = 0: y. = 0, 1,...,
for t 1,2, , do
x .+1 = Px
wask - Max V Vafilai al: Ensse)) kEMS)
Σ
41 = Py
Wil y nue V Vi vi: Ensee)
kEN(s)
end for Output: x² m Ei x:: y¹ m Em vov
3.3 Generalization Gap
In a sense, we obtain the result by minimaxing the empirical one F's in Eq. (2), which differs from the population one F in Eq. (1). So we can not guarantee the same performance on the unknown distribution as on the training dataset. And therefore the gap between the empirical one and the population one reflects the ability of generalization. Unlike the standard learning theory which only contains a single variable that can directly define the population risk and empirical risk by the objective [nnction[]]. Owing to the structure of minimax, there are different methods to define the population and empirical risk as concluded in [19]. where primal-dual measure starts from the idea of duality gap in optimization. And we first introduce two types of population risks as follows.
Definition 2 (Population risk). For a randomized model (æc, y), we define the population risk as:
1. Weak primal-duat dual population risk: A (x, 3) supy'ey E[F y')] inf [[F((', [[)]

---

2. Strong primal-dua population risk: (z y) = Elsup yyyy F(x, v²) - inf F(w', ,)).
Here the expectation is taken over the randomness of the model. By replacing function F with function Fss (see Eq. (2)) in Def. 2 when considering the empirical risk, we obtain the corresponding weak primal-dual empirical risk A (ar y) supy'E> Ey E[ y')l in E[Fs(x', y)] and strong primal-dual empirical risk Ag (z, y) = El Fa y inf Fs(x', y)] respectively. Subtracting the empirical risk from population risk, we can define the generalization gap as follows.
Definition 3 (Generalization gap). For a randomized model (ar, y), we define the corresponding generalization gap as:
1. Weak primal-dual generalization gap: 'gen (a., v) A (x. (m)
2. Strong primal-dual generalization gap: égen (z. -x; (xx y) (z
Remark 2. Notice that we revise the name as generalization gap to avoid misunderstanding since ggneralization error" usually refers to the empirical risk in learning theory (see [4]). Our primal target (see Problem (1)) is to obtain small population risk (Def. 2) which can be considered as a summation like A" y) ggn (I, y) A (at y). where generalization gap reflects how well the model generalizes and empirical risk reflects the optimization performance. The strong primal-dual risk is stronger than the weak one due to A ((z y) S A A*(x; y) according to Jensen's 's inequality. But in some cases, it is sufficient to bound weak primal-dual population risk such as the MDP [42].
3.4 Algorithmic Stability
Inspired by [13] that the generalization gap of an e-stable algorithm can be bounded by e. And this connection between stability and generalization for minimax problem furthermore established in [19]. For a randomized algorithm A solving the problem (2), we use A(S) = (A) (y)) to denote the output of applying algorithm A on dataset S [Si,..., S. Let Es and EA denote taking expectation on the randomness of the algorithm A and the dataset S respectively. Sometimes we omit the subseript as E[.] when is clear from the context. Next, we first refine the definitions of algorithmic stability in decentralized manner and then provide a connection between algorithmic stability and generalization gap in the framework of decentralization.
Definition 4 (Decentralized neighboring dataset). We call S' the decentralized neighbor- ing datasets when there are at most one different sample each local dataset, where S = (S1, S...,,,,,mm. S' = SS.........
and each S, and S differs by at most one sample. Definition (Decentralized algorithmic stability). For a randomized algorithm A, we say:
1. A is e-argument stable if there holds for any neighboring datasets S,S':
(
- Aa(S")
Aa(S) Ay(5) A,(
EA
Se.
2. is e-weakly stable if there holds for any neighboring datasets S'
supl sup EA(((((() v': f(A((() y + sup Exlf ( ((l:))))( Sc. é <LVE
x'E
where & e (E,,,.,, denotes sample index with & D; and f(x e) - E f1 25
And we further specify the stability error e02 (A) and exiia (A) respectively.
Remark 3. The definition of neighboring datasets in the decentralized setting can degenerate to the traditional neighboring datasets where there is at most single different sample between S and S'. And the refined concepts of algorithmic stability are also fit for classic stability without decentralization in [19]. These facts validate that our definitions above are well-defined. Notice that the argument stability can imply weak stability because of the property of Lipschitz continuity (see Assumption 1). Specifically speaking, when algorithm A is e-argument stable, then is /2Gie- stable. So we will mainly focus the argument stability in the rest part.
Theorem (Connection). For an e-argument stable decentralized algorithum A, under Assumption
1, we have the following different measures of generalization gap:
a. Weak primal primal-dual dual generalization gap: egen (An, (y,)) S V2GG.
b. Strong nimmal-dull generulization gap holds under extra Assumption 2 when Ss is SCp
Egen Ay) < &G /2
212
where μ 2 mix py}-
5

---

Remark 4. The complete proof is provided in Appendix D. We establish the connection between argument stability and a different measure of generalization gap under different constraints, where weak primal-dual generalization gap does not require any convexity or concavity in part a. and strong primal-dual generalization gap requires both strong convexity and strong concavity in part b.. And this connection is not limited to the single decentralized algorithm D-SGDA, but a universal connection for decentralized minimax algorithms. Actually weak stability is sufficient to prove the weak primal-dual generalization gap in part that when algorithm A is e-weakly stable, we have gen (Az A,(S)) S. E. And the theorem implies that once we have access to the stability
EA.s th error, we can derive the generalization gap an accompanying result.
4 Theoretical Results on D-SGDA
In this section, we study algorithmic stability and generalization bound in SC-SC, C-C, and NC-NC settings in Sec 4.1, Sec 4.2 and See 4.3, respectively. Due to the space limitation, the proofs are placed in the Appendix E, F. G respectively.
4.1 Results on Strongly- Saanvex-Stronly-Connae Case
Below, we first characterize the argument stability with fixed and decaying learning rates, respectively. Theorem 2 (Argument Stability). Under Assumption 1,2,3 when each ft is Pa Strongyy convex and My My-strongly concave, we have the argument stability bound for D-SGDA (denoted as A):
2G T-1
T-1
Lp
T
T-1
Lμe
arg Sta
Th
mar
II Ts
mén
H4GL
mor Mk
Ts
max A-1-
II J=
min
L+u
L+u
0=
+++
0=0
where 1/
natua max (1,,, J. 1/t mnin(1a,t Ny / = min (pn (mm py Furthermore, Ltf ( (2( m0a0 a. fixed learning rates, sto eng (A) S 2G
n
b. for decaying learning rates with Th mp m((+1) and mpaa "((+1)=: C 1, we have:
arg (A)
2G
T-1
Σ
1
4GL T-1 u2T Lin
Cx
pmT LiH K=0 (k 1)a-
Lia
(k+ 1)aT
L ke
where Cx A
(k/e)" 20
2"
X)
Aln
x
Remark 5. (i) Bound analysis and comparison. For case a. w.wh fixed learning rates, the argument stability is bounded by 0 + ). which can reach O( (T- + + when ~ 7. For case b. with decaying learning rates, we should require 2c 2
L. +1 otherwise the bound can tend to infinity, then LtH 4GLCs 1.TTT
we have sta (A) < M(1
20 Ti-c
L205L/(2p)H1 +In 712= Both can be 20 Li
bounded by Õ(TH n
Co with Ô containing the logarithmic function into consideration, which
T F.
matches the corresponding results for SGDA (see Thm.2.(c) in [19]) except an extra multiplication factor Cx: 0 (1+ + )) with decaying learning rates and N the total sample size. (ii) Factor influence. It is apparent that a smaller stability bound is achieved with larger sample size n, and smaller learning rates 17 (which is associated with larger 7). And notice that the decaying learning rates may slightly underperform than the fixed one, it is easy to explain that at the beginning decaying learning rates are too large and therefore result in weaker stability. The influence of these factors is consistent with vanilla SGDA. (iii) Effect of topology. So the major difference lies in C') and the (k/e))
number of nodes m. For CA
An + A when À 1, it is bounded by O (x)
-1
2
A[nn FF
and when À + 0, Cλ bounded by O( x Tyc). We list some common topology with estimated value of À along with the upper bound of Cx in Table 2. We can conclude that topology with denser connection (larger spectral gap 1 - X) will have a smaller stability error, i.e., be more stable. In extreme conditions, the fully connected network will behave as well as vanilla SGDA, and the stability error of the disconnected network will diverge. Furthermore, under the same topology, fewer nodes will result in better stability.

---

Generalization gap. According to Thm. 1, we can directly derive the weak and strong primal- generalization gap of D-SGDA as v2Ge arg and G /V2 + 212 ang the same analysis as stability in above Remark 5.
H² sto respectively. Therefore, we hold
Next, we will first derive the optimization error and then provide the population risk by decomposition A (x, y) = 'gen! (2, y) + ( y)- Population risk is an important evaluation for the performance of stochas- tic learning algorithm, which will evaluate how our model obtained by training dataset behave over the whole distribution. Notice that we will use the average output instead of the last iterate in analyzing the optimiza- tion errors. We denote that:
Table 2: À value of different topology. Here means the tra term will disappear and N/A means the term will diverge.
Topology
A(400)
Cx
T-X
fully connected
exponential
(In
(Inm)
T+
grid
(m m)
(m In
ring
((1))
O(m²)
(mm))
star
m²
O(m²)
O(m))
disconnected
N/A
N/A
-1= ta
-1= "
T Pave
x
Vove
Et=
Ei= M/y,t
Theorem 3 (Strong primal-dual population risk). Under Assumption 1,2.3, when each fi is MC MySC, we have the strong primal-duat population risk as follows, where my & max Ny Mi niin & min Ty,s μ min My and (x Vave) is defined in Eq. (3):
a. for fixed learning rates,
2L A (1 T aver yove) S /
L+ 2nn
Ta
+2
(2G
Tyminn Lu
1-1
n 2(C² + Cyy
2
+ + G2 + 4(Cr + Cy)GLnn
1-A
VT
b. for decaying learning rates that ni ni
p(t+1] and 1/t mae
with c 1 and 2c² L. +1, Mi+ty
L+p
A (2 yove)
s SG12+ 2G(Co+Cp),
2+
212
2G
T
AGLCs
12c/L/(Ltu> + In 12001/44H11
12
1n(1 - c+ L+u
L
2c
b-
L
L+H
G² 1+ T
1 10#1
AGLCN(Ga+Cy) (1 (1+h7)]l=1)
1cs1 +.T.)
VT
2μ
T
(1-c)T'c
T
pT
Remark By Jensen's 's inequality (see Remark 2), we can conclude that weak primal-dual population risk also satisfies the conclusions above. (i) Bound analysis and comparison. For fixed learning rates, it is interesting to see that we should choose 1) 1/VT to get the optimal population risk of O + (-)))) although when 17 ~ 1/T we can get optimal generalization performance but the optimization error will not converge. While for the decaying learning rates, the population risk bound is O(T!-e/n Cx/Tminn &. 1 which matches the corresponding results for SGDA (see Thm.3.(c) in [19]) of OIn N/N when n 7min + (ii) Topology influence. We omit the trivial factor influence analysis here (or see Remark 5). And the effect topology is captured I-X
quantitatively by C) and 1 which have been discussed in Remark 5 and Table 2.
4.2 Results on Convex- Concave Case
In this section, we provide the argument stability and weak primal-dual population risk of D-SGDA algorithm for the NC-NC condition in the following theorems with proof in Appendix F. Theorem 4 (Argument Stability). Under Assumption 1,2,3, when each f. is convex-concave, have the argument stability bound for D-SGDA (denoted as A):
2G T
T-1
k-1
Sta (A)
<
m
max
4GL
M
mar
1/
mox k-1-s
n
7

---

Remark 7. (i) Bound analysis and comparison. When there is no strong convexity or strong concavity, we can no longer choose the decaying learning rates, otherwise the argument stability error may not converge. For fixed learning rates, cat is upper bounded by O slightly looser than SC-SC condition. While we can still choose 1I 1 /TT to obtain optimal result ( + (I-ATT ). Besides, compared with the corresponding result for SGDA (see Thm.2.(b) in [19])
T a + 1--)), which is
of OCK VT )R) we can approach it when 77 1/T8/4 and n. ~ T3/4. (ii) Topology influence. In C-C condition, the effect of topology on the stability is quantified by I-x which has been discussed Table 2. And we can conclude that denser topology is more stable and fewer nodes will increase stability under the same topology.
1
Generalization gap. Thm. implies gap holds with the same quantitative analysis as stability above. Analogously we can present the weak primal-dual population risk in the following theorem.
< (2G So the generalization
Theorem 5 (Weak primal-dual population risk). Under Assumption 1,2,3. when each fi C- C, we have the weak primal-dual population risk as follows, where Th & max Th
ne & min Wy l1 = min Hyy. and (w Vave) is defined in Eq. (3):
A A" (a Vave) S V2G 2er 4GLLinmaz)2 1-
C2 C2
) 21pminT
4(C, Ly)
2(Cr. + G2
+ rj max G
1-X
VT
Remark 8. The weak primal- population risk attains optimal of O T +
177 when
choose T7 m7min 1/T Note that select 77 1/T to obtain optimal generalization performance (see Remark 7), but the optimization error will diverge in that case. Compared with the result of SGDA: O(N11/2) (see Tbb.3.(b) [19]), our result can approach it by 1/2 T//
Then the effect of topology and number of nodes the population risk is reflected by I-x which has been discussed in Remark 5 and Table 2.
4.3 Results on Nonconvex-Nonconeenn Case
In this section, present the weak stability and weak primal-dual generalization gap of D-SGDA algorithm for the NC-NC problem in the following theorem with proof in Appendix G. Theorem 6 (Weak stability). Under Assumption 1,2,3, denoting D-SGDA algorithm A, we have the following weak stability bound when Ti mmaa & max/Nu,t, ,y, and n) mai & min My }:
a. for fixed learning rates that Tyuur mm and mi = 17 mnn
(aa < 2V2G2 maa
+ 2L max2222 2T
1-
I+I' and mmmo TetIje 1 b. for decaying learning rates that mn
1
2/2G2TL (c+L- - 1)m 2c L
4V2G
Bm
Bm,1-= 72
sta (A) S (c L) ( 1-
Weak primal-dual generalization gap. According to Thm. 1, we can derive the weak primal-dual generalization gap as egen (Ax (y)) S V2Gezia (A4) for D-SGDA in NC-NC condition.
Remark 9, For case a. with fixed learning rates, the weak stability and weak primal-dual gen- eralization gap is bounded by O + D which can reach O + (I-AT) when 17 1. For case b. with decaying learning rates, the stability and generalization gap is bounded by (((C)) T (m)===a) plc size and fewer nodes will result in a smaller stability error and generalization gap, which coincides with results in (S)C conditions (see Remark 5). Approaching to the weak primal-dual gener- 2 2ap
It is evident analyze the influence of factors that, larger sam-
alization bound of O(n 20073/ T 2uplz) ) provided p-weakly-convex-weee wwtte-ooooewwwlll-ooooe weakly-concave (see Thm.5 in [19). CA reflects the effect of topology on the stability and generalization gap and value has been discussed in Reamrk 5 and Table 2.
8

---

229
5u0De
Figure 1: A against the number of iterations, with the first row showing different settings. From left right, the settings include varying learning rates, communication typologies, sample sizes the w5a dataset, and learning ralex(svmguide3) generalization error is displayed the bottom accordingly.
0.55
SaHERR
meddemiingie
100003
0.010
Sedee
5203893
633
rechknrgeeerii
631
0.0000
45
1-21822
12-420
0,0000
Teder/br
0/00
0.3020
Sox100)
Toder menim1s
6004
6005
0.018
6.005
0,003
33000
0.000
01033)
Number
Mendrr
Humber Tomeelor
Namber
Figure 2:
The first row shows the performance of the generator. From left to right, the settings include varying learning rates, the number of nodes, sample sizes, and communication typologies on the MNIST dataset. The performance of the discriminator displayed at the bottom accordingly. The dashes denote different layers.
5 Experiments
Experiments Setup. We evaluate our theoretical results of the C-C case by adopting the SOLAM method [41] to solve the AUC problem on two datasets svmguide and w5a, and the NC-NC case by solving the generative adversarial network MNIST. We extend the methods for both cases to decentralized implementation. Our experimental setting follows the way conducted [13. 19] to study how the stability and generalizability of D-SGDA would behave along the learning process with different factors, including learning rates, typologies, nodes, and sample sizes. We employ the same randomized method to generate two model sequences, one for the original data and another for a one-observation perturbing data, and subsequently calculate the Euclidean distance between their respective parameter sets. Additional implementation details can be found in the Appendix.
Results analysis: From Fig. 1 and Fig. 2, we can observe that: (i) faster learning rates, fewer number of nodes and smaller sample size can result in smaller Fuclidean distance between weights and smaller difference between training dataset and validation dataset; (ii) the performance of different topology stability: fully conlected(all) > exponential grid ring star sincol))cted(singlee))

---

These validate our theoretical results of the algorithmic stability for D-SGDA (see Remark below 5 Thm. 2). And the impact of different topologies also coincides with our discussion Table 2.
Conclusion
In this paper, we provide the first comprehensive analysis for the stability and generalization of D-SGDA for decentralized minimax problems. Our theoretical results show that a decentralized structure does not destroy the stability and generalization of D-SGDA, instead between the iterations and the number of nodes, as well as sample size to achieve better population performance. Numerical experiments also validate theory. Our analysis technique has the potential used for studying the ability and generalization of other decentralized minimax algorithms.
can leverage
Limitation& Broader Impacts. In our analysis, require the Lipschitz smoothness, which may be further relaxed future work. In addition, D-SGDA can converge with the heterogeneous data distribution, whose stability and generalization are still unexplored in this work. Since our work focuses on the theoretical understanding D-SGDA, it does not suffer from negative impacts.
Acknowledgement
This work was supported in part by the National Natural Science Foundation of China under Grants 62225113.
The authors appreciate Erdun Gao for providing valuable suggestions on the experimental implemen- tation. The authors also thank Tongtian Zhu for pointing out typos as well as useful discussions on the experimental results.
References
[1] Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
[2] Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Dis- tributed saddle-pon point problems under data similarity. Advances in Neural Information Processing Systems, 34:8172-8188 8184, 2021.
[3] Aleksandr Beznosikov, Pavel Dvurechenskii, Anastasiaa Koloskova, Valentin Samokhin, Se- bastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. Advances Neural Information Processing Systems, 35:381 11388166-3133 2022.
[4] Olivier Bousquet and Andr 'e Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[5] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine leurning, 3(1): 2011. 2011.
[6] Lesi Chen, Boyuan Yao, and Luo Luo. Faster stochastic algorithms for minimax optimization under polyak- L) ojasiewicz condition. Advances in Neural Information Processing Systems, 35:13921-13933 2022.
[7] Lesi Chen, Haishan Ye, and Luo Luo. A simple and efficient stochastic algorithm for decen- tralized noncomvex--ttrongly-oommm minimax optimization. arXiv preprint arXiv:2212.02387 2022.
[8] Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
[9] Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. In International Conference on Machine Learning, pages 3174-3185. PMLR, 2021.
10

---

[10] Hongchang Gao. Decentralized stochastic gradient descent ascent for sinite-sum minimax problems. arXiv preprint arXiv:2212.027244, 2022.
[11] Ian Goodfellow, Jean (buget-Abadin Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 1): 1:19-414,, 2020.
[12] Hongyi Guo, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Decentralized sigle-timescall actor-critic on zero-sum two-player stochastic games. In International Conference on Machine Learning, pages 3899-3909. PMLR, 2021.
[13] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International conference on machine learning, pages 1225-1234. PMLR, 2016.
[14] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
[15] Feihu Huang. Adaptive federated minimax optimization with lower complexities, arXiv preprint arXiv:221 1.00303,, 2022.
[16] Zhuo Huang, Miaoxi Zhu, Xiaobo Xia, Li Shen, Jun Yu, Chen Gong, Bo Han, Bo Du, and Tongliang Liu. Robust generalization against photon-limited corruptions via worst-case sharp- ness minimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16175-16185 2023.
[17] Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations.
[18] Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiianov, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. arXiv preprint arXiv:2202.02771. 2022.
[19] Yunwen Lei, Zhenhuan Yang. Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, pages 6175-6186. PMLR, 2021.
[20] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In 11th [USENIX) Symposium on Operating Systems Design and Implementation ((OSDI) 14), pages 583-598, 2014.
[21] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
[22] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
[23] Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jarret Ross, Tianbao Yang, and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. Advances in Neural Information Processing Systems, 10561061-1 2020.
[24] Songtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Başar, and Lior Horesh. Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 8767-8775, 2021.
[25] Luo Luo and Haishan Ye. Decentralized stochastic variance reduced extragradient method. arXiv preprint arXiv:2202.00509, 2022.

---

[26] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference on Learning Representations.
[27] Eric V Mazumdar, Michael Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint (eXiv:/901.000 2019.
(28) Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[29] Angelia Nedié, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-976, 2018.
[30] Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. What is good metric to study generalization of minimax learners? In Advances Neural Information Processing Systems.
[31] Alexander Rogozin, Aleksandr Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems. arXiv preprint arXiv: 102.07758, 2021.
[32] Tao Sun, Dongsheng Li, and Bao Wang. Stability and generalization of decentralized stochastic gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9756-9764, 2021.
[33] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. Advances in Neural Information Processing Systems, 31, 2018.
[34] Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on learning theory, pages 4259-4299. PMLR, 2021.
[35] Xidong Wu, Zhengmian Hu, and Heng Huang. Decentralized riemannian algorithm for noncon- vex minimax problems. arXiv preprinl urXiv:2302.0382) 2023.
[36] Wenhan Xian, Feihu Huang, Yanfu Zhang, and Heng Huang. A faster decentralized algorithm for nonconvex minimax problems. Advances Neural Information Processing Systems, 34: 25885-25877, 2021.
[37] Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34:26523-26553 2021.
[38] Yangyang Xu. Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problems. arXiv preprint arXiv:2304.02444, 2023.
[39] Zhenhuan Yang. Shu Hu, Yunwen Lei, Kush R Vashney, Siwei Lyu, and Yiming Ying. Dif- ferentially private sgda for minimax problems. In Uncertainty in Artificial Intelligence, pages 2192-2202. PMLR, 2022.
[40] Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34:13975-13987, 2021.
[41] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. Advances in neural information processing systems, 29, 2016.
[42] Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statistics, pages 576. PMLR, 2021.
12

---

[43] Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu, and Songtao Lu. Taming communication and sample complexities in decentralized policy evaluation for cooperative multi multi-agent rein- forcement learning. Advances in Neural Information Processing Systems, 011118825-8888 2021.
[44] Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, and Dacheng Tao. Topelogy-aware generalization of decentralized sgd. In International Conference on Machine PMLR, 2022.
Learning, pages
13

---

Appendix
Table of Contents
A Decentralized Optimization
14
B Notation
14
C Important Lemmas
15
D Proof the Connection
17
E Proof the Strongl--Covee--Strongy-
Case
Proof Stability
Proof the Empirical Risk
23
Proof of Strong/Weak Primal-Duu Population Risk
28
F Proof in the Convex-Concave Case
30
F.1 Proof of Stability
30
F2 Proof of the Empirical Risk
30
F3 Proof of Weak Primal-Duu Population Risk
30
G Proof in Nonconvex-Noncooccave Case
31
G.1
Important Lemmas
31
G.2 Proof of Stability
32
Primal Metric
33
Additional Experiments
35
1.1 General setup.
35
1.2 Detailed implementations.
35
A Decentralized Optimization
fully conncctd
grid
ring
star
expoxxiiill
Figure 3: Visualization different typologies. Note that the lines without arrows mean undirected, such as the fully connected, the grid, the ring, and the star graph. While lines with arrows denote the direction, which shows how information flows from one node to another. Our study objective undirected graph in this paper, with the exponential graph an illustrative example of directed graph.
B Notation
& Rd and y E RRd, we use
o: E Rdy to denote the concatenation.
y
14

---

II denote the identity matrix, 2. X A (fff..., m. ) E Ruxxe: y (Vi....
y'm)
E Rmxxy; and we use [X,
(
xy T
)} Ym
(mx(dxzddy) to denote the concatenation
We use 5 to denote the samples collected the 1-th iteration, i.e., (SIJe(L)) -.. Emise(m)) 4. We denote the gradients in the t-th iteration follows:
VaJ(X','
(Vafi ( S..)) ... Vasm (1r Vin (m.)) ) E Rmdd
(Vii (.: ... S (a'm Vin Se,de(m)
E Rmxdy
Vef(X' Y
Vxf(X, )
fa vi: v ( (1)).1))
ao im (arims V (i VyJm(aan Mmi Sm.
E Rmillltdd
We use E R to denote the matrix whose elements are all m and I m E R to denote the vector with all elements equal to 1.
C Important Lemmas
In this section, we provide some important lemmas fundamentals of the following proof. Lemma 1. We define Gg.g
x Ggm
)
Px The V vng(a y)) Pyly My V Ngg(2 y))
with 1f mjman A max Ne: by and 17 min A min(me, Nyy Under the assumption that g is L-Lipschitz smooth, then we have:
Gg.n is + moz ex)eeanassvve
When g is Hx -a-sttronly-convex w.r.t. x and (uy-Stronglycconcvee w.r.t. y, letting L+t maps S
mi < 2 Lp
Ltg 1 where - min(pe, Hyy, then Gg.n is (1 17 Lp
Ltp -eexannsive.
Proof. For case a. where we do not require strong convexity or strong concavity, we have;
Gg.n (
)
x
x x' 7 (Vnglæ y) Vag('', y/)
Gg.n
y'
y - y' - fly (V Vog( (x y - v20 4))
x x'
)
The V Veg(z, 8) Vag(æ', y)) + (
y y
ny V vol v vog(a.)) y))
(
x x
$ + 1u max L.)
y
y'
When function g is further Use -ttoongy convex and syy-only concave in case b., thus we have:
G )
G 9mn
x' 7u V Vag(a x y) V Vag('', (0((x')))) yy)))
2
y yy yy (V, V .3')
V "ng(an 8)
|| n' 1/- (V Vn ar, y) Vng(n', y 221 + 11 yy Bl (V Vug((' yy) Vog(E, y)
||x x' 1|2 + n a 8) Vag(z', y2))12 -n (x x' Vag(a, y) Vag(æ', yy))
+ lly y 12 + 2 V ( .y) V Vog(z, y))l 27y (u y V Vog(2', ,,') V a y)
Recalling the co-coercivity of L-Lipschitz smooth and μ-strongly convex function f(x) that [13]:
Lμ x - y11
(Vf(=) - vf(g), y) L+ [Vf()) 2 + L
15

---

So we can get:
(x - x', Vug( y) Vag(z', + (y- - y, V Fug(t', - V v 8))
- -(( Vag(z, y) Vag(z' .y)
Vug((', ,3') Vug(( y) ) (
y y ))
x'
1
Vag(a, y) Vag(z', yy) V Vug(2' ,y¹) Vug(ar, y)
Lu
|(
2 -ー x'
y y )r₂
2
L ++1
+ L+ 1
(5)
1
1
VVg((x v) Vag(z', y/')l²
| Vogll' yy) - V v2( y)1
μ
L + p
Lp
Lp
+ L +
|| x'11? + L+ lly - 1/1?
Combining above inequalities (4) and (5), we can get:
) Gg.n ( ar' y'
) s 17 min Lape
) x x! ||(
L p
- y'
when L (1) m2x) S. r)arain <
Lte 1 2 satisfies.
Lemma 2. Letting P E R denote the matrix whose elements are all m. following the update rule of D-SGDA (see Algorithm 1), we have:
[T-P) r7 S
mmG)
1 Ma Xt-1a
x=0
where ma = max Ny.s)
Proof. The Lipschitz continuity (see Assumption 1) implies that for any x E X' and y E y on
na f Y':
a given sample &, the gradient value is bounded by G, i.e.,
-7y, V f Y 5')
S
max (N Ny. /mG. Following the proof of Lemma 8 in [32], we can get the result, which can be
expressed as EE ||0|| - x² 1|2 + 1ly! y0112] 1/2 S 22 E. 0 maz -111-
Lemma 3. When < X < 1,
Σ ΣG
H x
C1
C2 a (k/e)*
2e I + Aln
2*
S
0;
( + 1)
A(nn
Aln x
1=0
x
Proof.
X-1-
1-1 1-11-
1 It dx = X-1 + 1 l" x-=
pl X-1-=
J=0 G+1 = x-1
+
Σ
1)+
-1-1 +
xx dr
3=1
whereas for the integral have:
l x-
1/2 x- f
/
1 x-
dr 2 /
/ zk
(5)x {"
1 pt
x dr
1h dr +
dx +
=
4 zk
In
k=
dr
-- 0<k<1
Therefore we have:
1 X-1-j
X X + - x -
k=1
0 0<k<1
16

---

When 0 <
X-1-i Σe=
1-1
G+1 S
xx=1+ + 2² t+
xm 2*
24
where X²
A[In 3
(k/e)*
A : So we can define Cx X(In t) Aln
2e
(kje)*
+
2-
A
that Σj=
- S
C++
Go. And
for the case k = 1 we roughly consider the logarithm as constants our discussion can be put together into the above category as l = 1.
Remark 10. Considering function h(A) A 1 monotonically decrease in interval (0, :) and monotonically increase interval (5. with minimal value e. Analogously for the function
g(A) A(In 27t which monotonically decrease in interval (0, / and monotonically increase in interval (,), 1) with minimal value of (t) .Therffore,, when k = 1, Cx is bounded by O
otherwise, when À + 1, C3 is bounded by O (xxxz) ); when À + 0, Cx is bounded by O( A(In )
D Proof of the Connection
In this section, we will first figure out fundamental lemma that illustrates the structure of dataset in decentralized setting. Then we will provide proof for the connection between argument stability and primal-dual generalization gap.
Lemma 4. Denoting dataset as S = (Si,..., Sm }. and denoting each local samples stored in S, as S, (E.. I1: Then we have the decomposition equation of the empirical finctiion:
n
m
Fs(x, 3)
fa y: E(..)
n
M
11
Im
Proof.
n
f( yi Er,,
7
m
Im
fa y Ei,e))
1=11
4-1=1 ++1==
(x, y)
m-1
h=1
4-1=1
i
1m=1
m
Fs, (x. y)
m
Fs. 3)
Proof of Theorem 1. We let {SI...., Sm where S. = fEutheis and S' = [S)...., Sy, where S 1isiss be two different datasets while S, and S are drawn from the same dis- tribution D:. Further define s()) (8(1)) s( ...., s.,.)) where 1 (2,,k2.-..,m))) and s(())
I,, t,,, }. So we can say that there is at most one different
sample in each local dataset between S and s(),, For function F X y R, denote y y'(x)= = arg maxyey F(x, y).
For case a. the weak primal-dual generalization gap w ( A (A,(S), Ag (Am (y))), We first make some adjustments to the definition:
17

---

Tge (A.)
v'ey htAH://HSSH.HHHHHAAAAAAAAAIAIADD y'Ey
(sup
WER
vey http::/00000110///////../.000101
inf in
v'EY
#'X
sup -
sup
v'Ey
x'Ex
where the expectation can be detailed into EAs in this situation. For the first term, we have
EAs (( v (S)
1
EAS.S(F(AL 3/1 - (F.sss((s(AA(()).
n
Σ (SA,
1 m Σ (S),
EAS,
4=1
i=1
1
SA
Σ
m
) -
m
m
= =EASS, -CEAS.s/IAAS' - As
where the first equation is due to the symmetric distribution between S; and S and there are overall nh permutations of l. And the second equation is due to the independence of sample &i,,, from the training process upon dataset S and Lemma 4.
And we can analyze the second term a similar way:
E (Fs(', (S) - F(x', AA,())) SFA.S.ssIAA,,C. (S')
Therefore we can get the weak primal-dual generalization gap that:
Aa Ast Ay(S) - Ay S VV2G
( (Ac S 2G sup EA S,S'
For case b. the strong primal-dual generalizaiion gap Egen (A, = (AA Ag (S) Observing the structure that:
'gen AA, inf F(x', (S)) - E sup Es (A) 3/) xEX
E[sup (Axx y/) y'Ey
inf x'E
Fs ( (S))
y E)
EAss(sup F (S) y') sup (A, y')) y'Ey
inf (z'
inf F(x', Ay (S))
inf
y'Ey
TEX
FEX
66)
where the expectation can be detailed into Es,A in this situation.
For the first term,
n
EAS sup F (AA, E'EY
EAS.S [sup ((A) y')
4= l==
WEy
(43)
E (F(A)))()). ysan)l
h=11/=1
h=
(8i)
EAS.
Σ (l(A(( ). Eaa))
m
1m=1
Since S; and St are drawn from the same distribution, and there are nm permutations of I [l,,.., )m) so we can get equality (i). In equality (ti), we denote yogo arg maxyey F(Ac(S), y).
18

---

While for equality (ii)), S.u, is independent from the training process under dataset St for each local agent respectively. Using the property of Lipschitz continuous (see Assumption 1), we can further get:
f((A(() Eus fi(Aa(() <
As Az(
)
Ysuu y
(a)
12
G
Amn Am()))
By
where inequality (a) is conclusion of Lemma 4.3 in [22] that 1/550
Usll S ,, ((00)))
By
As(S).. Combining above two inequalities, we can get:
[su (S), v'EY
L (( + G 2/1 -
- Ao -ca
EAS.
n
1=112=1
L
EAS (Fs(An)))) vs5i + GV
GV1+
1+
Esppup A - (s) S.5'
L
< EAS sup (s((A(5))))) + + y/'E)
1+
EA sup AA - (S)Il
suu
S,
where we get the last but one inequality from Lemma 4.
We can do similar operation on the second counterpart since fi is also Ma -tr-nnly convex on a.
L E sup (l - (S)
E. inf Fs( Ay()) - inf F(a', A, S / 1
wee
x'E
m2
S.S'
So the overall strong primal-dual generalization gap satisfies:
Egen (Az (S,,
1
An(S) Ast) Ay(S) (S!)
SG
V
1
112
V2EA
sup LS,S'
2L2
s SG
+
112
where μ = min(ua: My).
E Proof in the Saapgp--CCCoeee-Sttnnn--CCooooe Case
In this section, we will prove the stability and generalization gap of our D-SGDA in the case of Ne -t-sonly convex and My -tronnyy concave.
E.1 Proof of Stability
Proof of Theorem 2. We use (x' y²) and (+', "¹) to represent the output in the f-th iteration when applying D-SGDA on any arbitrary neighbouring dataset S and S' respectively. Since the D- SGDA algorithm is symmetric [4] with respect to the dataset the different samples appear in the last location in each S; without loss of generalization, i.e., E, differs from S, = [Ei,1, ...,,,.. }
(Si, ..., S., J. we can assume
S' = (S,...,s Sm-11: ) where S = [E.1, S,2,
in the n-th data.
19

---

First concentrating on the iteration, we have:
a't11
yttl ) - -(xx, (1x,,) x
1m
m
[wxx
Ma Vff Y
1m
-
Fy, V (X y 59)
m
Na.1 Vaf (X* r
1
P(x,))
YJ
-1yy, V " (X ;
m
(Ix 7 W
Im
The, ze (xx Y -y,t V y ( :(
1 m
-(x)))
m
m
(
xt'
T/ V. v Y 5t)
My V v (X Y E0) )
1m m
P(x.))
xx¹
-yy,t V fa (i.0).)))) )
Ta, V fatt yi (Ls1t))
P(x.)))
y²
i=1
where in the first equality we use the definition that x'' = 11 Ee x V2
1 Em
=== yi and the last
(
equality is due to the fact that W Lm 1m..
We use the notation P(x,,))
E Rda as an
y
Px [ac] Pr
)
abbreviation of
Rd and Pa [[X, ([X, Y means every column should obey
P(x.))) [(
In the t-th iteration, there is a probability of C (1 - m- ) that there are m mo agents not selecting the last different samples while the rest mg agents selecting exactly the last different samples. Without loss of generalization, assume the first mo not selecting and the rest mo agents selecting the different samples respectively. So we can get:
xt+1 +1+1
11+
g'+1
x²' x² y¹ 8¹
Nwe ( fa( vi (es())) V fi st: (aact)))
Px,
Ty V (x (is.0)) V fi of: (isi())))
an 5 yn 5/
Na, V fe wi ()) - mx. V fa of (as(e)) My V y (xf, E(.)))))) + Fy, v (itt (l1
Px,
Th V fi Eim) 7x, V (a (l.
Ny.t V fz), yi: Es..) My. V f (2/, El.)
f=m-mo+1
where equality (i) is due to the setting that agents from to m select f. which is not the last different one while the rest agents from m mg to m select the last different samples, i.e., Ei and 5(,,, respectively.
20

---

Then we can decompose the term inside the projection into several parts as following:
x² 7x V g (3i (it 7w Vafi('', "eei. (((5))(0))
y' + Fy V fi(a'' y ((..(()))) (0'' + ny, V fi(d', vi: (a..())
m
x² T/ V Sa (a :rm)
(x
M/x, VaJi(t' . (l,))
yy + Thy V v fi('' y (a,))
④ + The V Ii ;1
m
I - m1+1
1 (afela)) (15.))))) - Vafi(w', y y'E Tyy (V Vyleta ui Scs.0))))) V v,li( yo: ((s((i))
i=1
11
m mo
-ax (Vafel E.s(0)))) Vafi(t' gf: gr: fit( (()(0))()) V Vufi(at, :
m
112
na, ( fifif E..) Vafilx' E.n)) Thu (V (art vis - V v "i'l",,"''En Ei,))
m
11
Taz (Vnfi(tt, ihs (l.n) Vafiat (l:((,)) Vy. (VyJi U.: &t,) Vulil' ,
I=m - m1+1
11p
According to Lemma and the preoperty of Lipschitz continuity (see Assumption 1), bound the term I, as:
100
Lu
x² 4² |1(
I
11 $
(1
17t
3y "¹
m
+ 1
where ni min(fants My 1/. max max (1m,t M. and p 2 min My). For the term I2, is bounded by:
1
x¹ Um.t V Vn y¹: Ei.n)
(i' Ne,t V m (w ;i: Et
H2ll
< m
Σ
y¹ + Ve V fe( "aai.v"' v
(i'' + Tyu (i ((
1
x Nn. V (xt 4 Eim))
y' Ny. V fi (x' Sin)
(i' + ny, V Vyfi (':
178
+ +|(
M/ (a' 9¹; El.)
- Nn Vn ;
Ny. V Vyffa "/:: Ei.n My. V fat ((
770
(1
n
min
Lp
(
x²'
3¹ )l
2m/ maa
m
+
21

---

For the term II and IT,
((
V Ci ui Sus(o)) V UnJi(aa y (asico)
11 + 11
Σ
maaz
V f . (.)
V vilatt 515,00)
m
man 1(
Va S.m - Vali(wt yy: (z S..)
Va wii Eim))
m
Tho +1
1
x =x' x² y y x²
T L
x
||
y yy¹
m
1/2
Itt
moz
x' 1|? + 11 80113
Vm
< 21 man
LG
men
1-8
8=0
And is the same as the term II2 + IT2 that [[T2 + IT2]l I 2ny LG - 1/5 Taking expectation on the choice of each local sample, we can get:
1maaxe-11
(
x+t1 - x++1
FA
g
m
C
(1-
1
m mo
ymo ((1
T/e min Lpt
EA
(
xt à²
)
)1
mo
2m
maz G
y²
n2
- 1
m
mg=
[-1
+41h
man LG
Maa X
1-
6=0
Lpa
xx at
1it
min
+ p1)
EA
y¹ - ")
+ 4n
mar
LG
Σ
max X 1-11-
8=0
Cmm (1
mm-
mo
mo
21/F
max
11
m
mg 0
Lp
tt xx
)(
2npaa G
min
L L+P
EA
y²
3/
+
4np man LG
1s
max X
1-11-8
(8)
where the last inequality is due the property of binomial coefficient that C.mo Recursively applying the above inequality, we can get:
ma
C 1
m
(
(x) - (5') (5
Ay I
EA
2G
T T-1
maz
T-1
min
44GGL
T-1
max 1
k-1
n
maz
x A-
1-s
T-1
I[
ny
min
L.p.
L+ μ
L
km
4 k++1
k=
=
j=
where the initial difference is zero that X0 and y 0. And we use the last iterate as the output of Algorithm A, i.c., (Ae(S), Ay (x ).))
22

---

For case a. when Ne, and yy are fixed, we further get:
20 T-1
maz 1- min Lpp
R-1
Ipp T-K-1
org ora (A) _
T 1-
4GL
maa
many 1- (1
min
n1 km
L+
Ltp
8=U
21) mm G
Lu
4nj
GLm mar
mni
1
++ P
k=0
L+ F 2G
2(
1f mar
1/min T.ps
Further when mnm rymin 17, the argument stability turns out to be
I + p 2nL
org (A) s 2G
(A)
+ n
Lp 1 - x
For case b. when mea
and 1pp
m(++1]: C S 1. Since + S exp(a), we have:
m(t+1}e
T-1
Lpp
T-1
L j j+1++H
(1 min
II
(1
L +
j=
j=k+1
T-1
++11+#
j=k+1
L
Σ
exp
J+ 1
/=++1
I exp
(In - In (k++
L μ
k+
ztr
T
Then back to inequality (9), we simplify it as:
Ae(S) - (S)) Ay(S) - Ay )
FA
<
2G T-1
k ++1
T + 4GL
T-1
Σ
k-1
u(s + 1) st-1-s)
)
pkk + 1)e²
T
M(k - 1)e ==0
k=0
h=1
2G
4GL
T-1
1
C2
unT ++
k=0
(k + 1) Ifn
z+F
1T 1-
k=
(k + 1)
xpp k
E.2 Proof of the Empirical Risk
Then we are going to present the optimization error of D-SGDA in the SC-SC condition.
Theorem 7 (Optimization error). Under assumption 1,2,3, each local function is ft is SaSCCHHSSC. We further bound the restriction set by supmex | < C. and supyey llyll S Cy. then we have the strong primal-dual empirical risk over the dataset S on the average output in T iterations as following:
a. When learning rates Na,t and Blyt are fixed,
C2 + C2
+ 17 max G2 + 4(C. + CT) max
+ 2(Ca Cy)G
A ( yore) S 2mpait
1-X
VT
23

---

b. When learning rates are varying that ne.
ph (1+1)ss and yy = My(t+1)9y
2G + Cy) + Tu + TT + I maa..
( aver yave) I
VT
where a E far, y)
Kmii min (cz: Cy) and μ min Hyy:
Ta
2pa
G² IthI
Ca =1
T Tima== -
(GLCs(Ce+Cy))nn
4GLC,1Ca+Cy) ((1-kmin) ( yremin
Kmin 1
0 0c <1
Kmin < 1
2p
T
Proof of Theorem 7. First, should notice that when each fo owns the property of Pa Strong convexity and Hy strong concavity, then the linear summation should inherit the properties, i.e. Fs y) = t - - fa yi E,,) is strongyy convex on a and -yrsonnggly concave on y.
First observe the update rule of x (see Algorithm 1), for any given E X::
|x:
x 1/
m
< ||
ne. V V Va x=|²
m
= =|
21|2
2 +1
na felaea vi (1 -((x" "/x''"xx.- na anfi yk (.
(10)
where for the first incquality, we can recall how we transform in the proof for stability (see Appendix E.1) that r++1 (x++1y7 Im = (W na (xf(X (())))"" 1m
x²
Na, V=J 5') Im regardless of the projection.
For the second term, we have:
m
Te. V anfi E
m
m
V of
uf: Vala(ah vi: (macaa))))
m²
< !m,
(mG² + (m² - m)
m² 2
G²
(11)
We decompose the third term in association with the empirical function that:
1 21, x²_ m
=21m (xc x², Van Fssa" yy) + 20 x. 1 m V of Vs ,y))
m
$ 22,, y²) Fs(x', y)') na. - x112
22 x. 1 m
Vafila) (/ (.s.))) V Val'sw'' yy))
(12)
where the last inequality due to the strong convexity of the empirical function Fs on parameter æ.
Then we combine the inequalities (10) (11) (12) and we can get:
2m, FF(w y²) Fs y²)) < (1 (to.:/lz))1 ||0
x²11 - || +1 xx1 2 + m G2
1 m
+ 2m, (or
xx
a fa( vi: En.s11))) V Fs(a", .
m
(13)
24

---

For case a. when learning rates t and yy. are fixed and we write them and Fy respectively. Taking summatation over the above inequality from / & T and using the concavity of the empirical function on y:
2// Fs (x', y²) - (2, yane)
< 2n (Fs( v²) Fs(
t=0
1 m
< (1 ||=11 + GT + +21
x²
V fi fi (ls - (Fs(aa/.')))
m
T-1
1
( - ||
+ GT + 21/m0
Σ
(xt V Fs(a', y²)
m
+ 2m ||=||
Σ
V V fi vis (1)
V Fs("" yn)
t=1
Then we take expectation on the randomness of the algorithm (notice that we not take expectation on the randomness of dataset) both sides of above inequality and choose the infinity of on the left side since the above inequality holds for any x X:
20 E. (Fs((' v²) inf Fa yoneel #EN
t=
T-1
$ (1 Ma )2 + G + 2m
Ea Fs
Vali C...o)))
m
+ 20xn' F/ EA
Σ
V li (of vi: Easrer)) - V= y3")
t=
i=1
(14)
For term I, is decomposed as:
m
Ej, (a', Vo 3²)
m Σ
v a fals Ex,(0)))
E3, (xo"
Va fi g
1
Σ
v vefi'" ('s()))))))
i=1
1=1
Eg (a
V fi y: E...)o)
V nn fi( wi: Ees.co))
(
T-1
m
< 2C
Σ
EA
Vnii v (..,(0))
m
T-1
(1 - 22l1 + 11 1/12)1122
2C'
1=0
T-1-1
4C GL
max 1-1-3
1=0
where inequality (i) is because of the fact that taking expectation on the randomness of j. is equal to the empirical result on the dataset S and inequality (ii) is due to Cauchy- Schwarz. inequality and Lemma 2.
25

---

Then for the term II, we decompose its corresponding quadratic one:
V -aa 2
m
EA
m
m
$ EA
Σ
a of G.ro))
Va Fss("'.)))
m
1
ΣEA
EA
V fc E.s.)))
V fi " E(,)
m
m
+ Σ
EA(
V C. yi: (o)
1 m
V filaf ut :E())())
a f(("", v2 (c,))
m
m
n
< <TTT +
F.A(
ai (0)
V Ji(a", ((a())))
V fi (as(to))
Ji(l"' Eur,,
m
m
V fo : (0)
V fil"" yy ())
Vali(a' ,y (E)))())
Vi .y (E.))
(a)
4GPT Σ
EAC
fa v/ ((s
1 m
V a fi(w", y E.)()))
m
m
t7f!!
V Va fi vi (a))
V aili of (lss
==1
< 4GT + Σ EA 1Ffe"
(V fa wi: (1s,0o)) V Vxfi(æ'' v' :
m
Vnn Vitl ; ((.s)())) V Va v² (isssco)))
m
1/2
2 EA
m
4G
Σ [1|ee at'l + 11 vill)) Σ
(1w0" at5 112 11 2i'113 (13)
m
(4-1!
<4GT + S
Σ L2
Σ +=0
1/
mar x --11-
max X 1-1
where equality (a) owes to that taking expectation on the randomness of je or ju equals to the empirical risk and inequality (b) is due to the Lipschitz smoothness of each fa and Cauchy-Schwar inequality.
26

---

Combining above inequalities of term I and II into the inequality (14) and we can summarize as:
T-1
2n ( v') inf Fs Yave)!
#ER
1=0
$ (1 na 102 The G²T 4n C
max X
xt-1-s
==0
1-1
1-1
+ mbn
4GTT + 42
Σ
Σ
Miaa X
Σ
1/ 1111--
Dividing both sides by T and we can get:
EAlFs(
( EA Bnlin Es v
WEX
Mafa C2
G2
ma
GL,
G
21xT
2
1-A
VT
And get the other-hand result in the same symmetrie way:
Eslsup Fa
v)]
Σ
Σ
EALFs(W' y')]
T
yEy
t=0
(1
C2
"l G2 4C,
Mng max GC,,
2nyT
2
1-X
VT
Combining above two inequalities we can get the result:
C2+ mm + m G2 + 4(0av + GTJ max
2(C + G2)G
( yive) S
1
VT Back to the inequality
Then come to the case b. when Na,t Um (1+1)s and My. (t+1++) (13), we simplify it into:
2 Mo (1+ 1)
G2
Fssa' y¹) Fs(xx v)) s (1-
(1+1) 1| x 1 -12--10²* =2
(1+1) 2
x x
V (z) wi Eiii
- Fs y²))
Ma (t 1 ca
m
2
Mm v¹) ((++))
- 1)
x² 21112
Fi
(t
+ 1) | + x
2
2
2 (++ 1)co
m
x
V ((rt yis E1...1)) - Va Fs ,'))
Taking summation the above inequality from f 0 to t T 1 and making use of the convexity of F's on the second parameter that:
Σ Fs(x", y²) - (s, youee)
T-1
Σ
( x.
1
V fili v Eas. - Vn Fs(a',
2
1)co
t=0
2
1
(a V Fs v²)
2p
+ 1)c=
m
+
||||||
Σ
V
(1, vaPs(a'))))
27

---

Next we will take expectation on the randomness of the algorithm on both sides and proceed in the same way as we do case a. that:
EA
Fs(w",
inf (a, yave)
aEA
1=
G
GL
1/8
man X
Xt11-s.
2/
(1+ 1)
f=0
1-1
C2 AGTT + +G2
Ta Xt-1-8
Ma Xi-1-8
EE
Without loss of generalization, we assume 7/1
1/ll
He (++1y
Therefore the summation
E' 1/ mar X x comes out be E
X--i-
Cx
Then have to analyse different
(1+
categories for the value cr-
First when Cr = 1, the summation result turns out to be EED
#I S1+hT,
G² 1+1 4GLC2Cx
2GC² VT
Σ EA Fs( y²)]
inf (I youc) I
T
DE
2/1 T
H&T
1=0
When
Cx < ET-
Ti-s
then we have:
(1+1)a=
I-ca
G
4GLC,O>
2GC
inf Fs(x Vare) 24 CT EA Fs( ['))]
+ VT
T
mEx
Me cx)
1=
It is in similar way to get the symmetric result the other hand and combining both results obtain the strong primal-dual empirical risk:
2G(C2 + Cy) VT
A Fs(x v) DEY
inf Fs(x voveel aex
TT + Ty + Taaa
where
G² I+hn T 2pm
G² 1+I
Cx =1
Cy =
Tg
Ty
2p4
G² 2pa
0 < Co <
G²
0 <1
and
Cmin
Gmin
1 min
Tmaz
4GLCx(Co+Cp)
0 < Cmin
<
pll ail--min M
E.3 Proof of Strong/Wee Weak Primal-Dual Population Risk
In this part, going to prove the strong and weak primal-dual population risk of the algorithm D-DA Actually this is an obvious result as a summary of above lemmas and theorems.
Proof of Theorem 3. As we introduced the population risk (see Def. 2), we decompose the population risk into generalization gap and empirical risk that:
( a y
(A"("" Viue) (2 vice)) + Ag( y
Notice that we use the average iterate (IT Th instead of the last iterate denote the output of D-SGDA. The first term is the averaged version of the strong primal-dual generalization gap and we will make some adjustments.
[(
x" T y"
)
First we have the argument stability bound of D-SGDA that EA
cnyy (A), where
(xT .y)) and (x"", ( denote the 7-th output when D-SGDA is exccuted the neighboring dataset
28

---

respectively. So we can make use of the convexity of the norm and obtain the argument stability of averaged-version:
T
T ave Vave
((
x x²
y" "²" )
FAA
aue Yave
S EA
S Esta (A)
(15)
Then the strong primal-dual generalization gap should be /v22 2 21 11²
(A))
(A) following Thm.
when each S is strongly convex w.r.t. æ and strongly concave w.r.t. y-
At last, the strong primal-dual empirical risk EA E Yave)l is studied in Thm. 7. So can combine above two bounds to analyze the strong primal-dual population risk different categories when learning rates are fixed:
EA
(x T
2L2
L+ 1a 2(1maaa)2
17 )ma)) )
C + Cg
sG
2+
2G
m
122
r) Li 1-
2nyann
n( GTn)
2(Cx + Cy)
1
VT
And when learning rates are varying that miminn 2c
1 and mnter m(tiIEE 1, requiring
m(++1)
L
+ 1:
L+u
EA MAAA"(20)
(x
ave: Dave)]
2L2
2G
C2 1T t k= + 1) Lif kt
4GL
G
12
unn' Liu
11+ 1)_ it
K=0
2G
+gy)
G2
1+
InT
4GLCX(Co +
In In
VT
T
n²
2L"
2G
4GLC3
1
2G(C + Cy)
G2 (21+ TnT
<
G
2
+
+
112
(T
L
pº(1
L+p
TITE
I.
VT
T
4GLCX + Cy) In
pT
When 1 and requiring 2c > D+H 1:
Ex|A (x
avee TT )
212
2G
T-1
4GL
C2
G 2+
+
42
UMI T
(k + 1)
IF k= (Ir + 1)- कr kc
k=
2G + Cy)
G²
1+ I
4GLOx(Ca + Cy)
VT
2p
T
(1 (1-o)Te
m(1 cc''e
212
2G
T1-a
4GLCA
2G(C + Cyy)
G
2 +
+
n
n111 +
L+p
n
12(2c L+4 1) T
L.
VT
G
+ In
4GICC + CTy)
2p
T
(1
T)
#(1 c)p'
29

---

When < 1 and 2c
L
+
L+u
EA(A over yavell
T
2L2
2G
4GL
1
C2
G
2
112
(k+
1)0--+ b+x
(k: 1) c
Ibp ke
k=0
C + +Cy)
G
1+ InT
1
+ 4GLC) CCx + Cy)
+
VT
+
24
T
+
(1
c)-
111 c)
212
r
4GTC0> lnT
2G + Cy)
G² 11+11 ln
<G
2+
+
+
+
112
cp
VT
24
T
(1 c)
4GLOX(Co + Ccy)
M(1 - c
F Proof in the Convex-Concave Case
In this section, we will provide corresponding proof for argument stability, optimization error and weak primal-dual population risk in the C-C condition.
F. Proof of Stability
Proof of Theorem 4. Analogous to Eq, (9) in the proof for SC-SC (see Appendix E.I,, considering C-C special case for SC when Ma 0, My 0.
Thus we can get the result:
Ae(S) AS") Ay - As
FA
T-1 2G
T-1
1k
mar
+ 4GL Σ
Σ
mar X k
n
k=0
8=0
F.2
Proof of the Empirical Risk
Similar to Thm. 7, considering C-C as a special case of SC-SC for Hæ = My = O, we can get the weak primal-dual empirical risk in the following corollary, where use the Jensen's inequality that (g y) & (z(x y).
Corollary Under assumption 1,2,3 and the restriction that supagx ||=||| S C. and supwey Illll Cy. each local function is ft is C-C. We have the weak primal-due empirical risk over the dataset S on the average output in iterations as following for fixed learning rates:
C2 C2 (x Vine) S 2mmiiTT + G2 4(Cx + GLm 2(Oa + Cgy
1-X
VT
F.3 Proof of Weak Primal-Dual Population Risk
Proof of Theorem 5. When each local function fi is not strongly convex strongly concave, not get access to the strong primal-dual generalization gap but weak primal-dual generalization gap. Following the same step in above proof that:
(A (x v Ag ve Ag (xT The y
Analogously we have the weak primal-dual generalization gap according to Thm. that: VTTe))
A (x
A (x V S V2Ge (A)
30

---

where ( (A) < 2Gn T 4GL "allyymaa"" I'T follows Thm. 4 when learning rates are fixed.
a
1-x
In the case without strong convexity or strong concavity, we select the fixed learning rates and following the Thm. 7, we can bound the weak primal-dual empirical risk as:
C2 +C 21iminT
+ + G² + 4(Cx + Cy)GLy +
( owee Blove)
1-X
VT
Finally we combine above patterns and we can get the weak primal-dual population risk:
2GrmaasT 4GL((n"aa)2
th (auver Vevee S V2G
11
1-
+2 C2
+ Cf + 4(Cx + Cy) +
2(Cx Cg)
1
VT
G Proof in Nonconvex-Nonconcaayy Case
In this section, we will provide proof for weak stability and therefore we can derive the weak primal-dual generalization gap following Thm. in the NC-NC condition.
G.1 Important Lemmas
Before we present the proof for the stability bound in nonconvex-noncooeass case, we should first introduce an important lemma which describes the fact that D-SGDA will run several iterations before encountering the different samples. We extend the Lemma 3.11 in [13] and make adjustments on Lemma F.1 in [19] to fit our decentralized setting.
Lemma 5. Let S (Si...., Sm3 and S' S be any arbitrary neighboring datasets, (x', y²) and (á', .'') represent output in t-th iteration under dataset S and S' respectively. We further require each local function is bounded that [f(( S B, vo E N. y y. Denoting
x² 5² 5. y¹
'' )|. then we have:
-
EAls(a ( E) f( 5): + v': f( (+: V V2GTA 6r 8ea =0 + Bmdo
n
Proof. First according the property of Lipschitz continuity (see Assumption 1): f(x', y f v): {) + f(z', g f(x', (
< Gll 4'll Glly r'll
< 28,
Then we decompose the expectation by the law of total expectation:
(xlf E): f(t', :) f( y':E) f(x'.
-0
= -P = D
f(x',v': E): f(#" 3) + f( v²:4) (': 8e =0
+ P(6ro + O)EA
"(x'vv': f( v + f( v4: f(x', (4: des +0
de 01 =0] + BB #
< <V2GFA
While the event that dr, * 0 means the training process has already encountered the different samples before to:
P6. #0) Σ
-
- ym to(1 (1 -mm) < mto
ml
Combining above inequalities and we can prove the Lemma.
31

---

G.2 Proof of Stability
Proof of Theorem 6. We are under the same setting as in the proof for SC-SC (see Appendix E. that (x', yy) and ( representing the t-th output over neighboring dataset S and S' respectively.
And we assume each local dataset S S' {S}. ..., St } differs from S by the last sample without loss of generalization, i.e., S; (5i,1,..., ...., Si,n) while S = (fi,1,-.. ... -i,-11 Si,
Analogous to the decomposition equality (7), we will bound the term J1 and 12 without convexity or concavity. Referring to Lemma 1, we have:
||/|||
S
m mo
min Li)
x² x²
)
y¹
m
|2
mg
(1 + li
min L)
|(
x x'
)
21 man
m
where we use the same denotation that 1/. ri min (yn,ee +t and 1y! max(mn,t Ny.t) So we can get the similar result as the inequality (8):
Ea [I(
x - +
)
5to =o]
3 g
Cm (1
1
m
mo
1
ym
(1 + T/i
minn L) EA
(1(
xt x. )l 8to of yy
71
n
m0=0
217 + m
mo
max G + 4m
max LG
mar x* st-1- 1-s
(1 + miin 1.) EA [|(
x²
yy
it
8to 0
+ Anj
moz
LG
t-1
1/5
max x
1111-
5=0
+
mmo (1 1 ym-muu
mo
1
mo
201
max G
m
n
m
mg
xt o² y¹
|||
2m 2mm G
=1+m min EA
des =0 =0]
+An LG
1/8
max x 1
n
==0
Recursively applying above incqualities from = to to =
Ae(S) 4 As
)
EA
Ay(S) - Ay(8') Au()))
8to =
2G
T-1
T-1
T
T-1
Tk
maz
II
(1 + 1/s
mán L.) + 4GL
Σ
1k
max
1ls
max k-1-88
(1 + "
min L)
n
k=to
s=t+1
k=to
0
j=
(16)
((
x'- tt
)
where we use the fact that 8c
=0.
y² 8¹
When learning rates are fixed that N/m,t = am and W/yt = Tly then we have:
E de Seo =0
2az (1 + 17 minn L)T - 1) MGL(nmazy)(() + 17 miin m -1) (1 N)ppmin
mmpmnn I
Then combining with Lemma 5, we have the following result:
Ealf(a',''s f(t", g + f f(x', y': f(z', :)
S V2G 2G
4GT 4GTxp max?
Bmlo
>T - to) +
1->
where it can obtain the optimal of ( marr 2Ln ma=2y when to = 0.
32

---

When learning rates are varying that vi the production by 1 S exp(a):
1 and meme
(1+1)e, e I 1, then we can simplify
1
1+1
T-1
T-1
T-1
L
T-1
II j=++1
(1+ + min L) II (1
II
Σ
exp
exp
[ [++1
j+1
j=++1
j=++1
j=k+]
T
T
S exp
Lln
k +
k
Then back to the inequality (16), we can obtain:
61o = 0
E
<
2G
T
Σ
1
(
T ) 4GL
T-1
Σ
Cx
) (17)
n
(k + 1)c
k k+1
(k + 1)e ke
k +
k=ta
k=1o
2GTL
T-1
T-1
Σ
+k+ 1) + 4GLC,
Σ
n
(I + +1
Amto
Requiring c+ L for convergence and combining with Lemma 5, we have the following inequality:
Ealf(x', ,'':''')))) f('', E) + f(x', y² - (()))"%)))
< 2G 2GT T-1
(k + 1)etL + 4GLC,TT
T-1
Σ
(k + 1)c- + Bmto
k=to
k=to
2V2GTTL
4V2G2
Bmtt
< (c+ 1, 1)m 10
1o+l--
(2c 1- to
20t1.-1
2/2G2TL
LV20"
Bm
s (c+ L) L - 11)
+
47.
(c+L-) - 1)m
2c + -
11
(ct
24
4v26 2C,T"
where for the last inequality, when to mal.
Le+1- Bm
The
20 20-6-1
_tzz it can obtain mini-
Taking supremum over parameters æ, separately and over the random sample, we can get the weak stability for D-SGDA in the NC-NC condition.
H Primal Metric
In addition to the primal-dual population risk (see Def. 2) as well as the corresponding generalization gap (see Def. 3), primal measure extends the relative concept in single variable minimization problem.
The excess primal population risk is defined as (x" ((t.) and the excess primal empirical risk is Agr (x) = supy Fss y²) - inf supyey Fs(w', yz). for a randomized model (xr y).
yey F(x' y');
There are two ways to define the corresponding generalization gap. One is to directly subtract the excess primal empirical risk from the excess primal population risk, defined as the excess primal generalization gap: Egen (x) = A ez (x) Ag (x) (called primal gap in [30]). Another one is to neglect the difference between the saddle point of F and Fs, defined as the primal generalization gap: epr (x:) supy'ey F(x, (() supy'ey Fs( y²).
Remark 11. Our definition of strong primal-dual population risk (see Def. 2) has included the expectation inside for assistance with the definition of weak primal-dual population risk (see Def. 2). Although the definitions in [19] hold different forms, which do not contain the expectation inside, while theoretical result aims at the same value.
Ozdaglar et al. [30] points out that the excess primal generalization gap gen can act as a better metric to characterize the generalizability in the nonconvex condition. It is our limitation that we do not
33

---

calculate the corresponding excess primal generalization gap and population risk for nonconvex case our paper.
While we omit the primal generalization gap gen and excess primal population risk A under C-C condition in the main text, for it can be derived from the corresponding proof of strong primal-dual risk. And we will illustrate them in the following as corollary.
Corollary 2. For an e-argument stable decentralized algorithm A, under Assumption 1, 2, when each S. is By Stronggy concave on the second parameter, we have the primal generalization gap: BA.s Legee (Ae(S)) GVL L 14
Proof of Corollary 2. Egen (A (S)) is exactly the first counterpart of the strong primal-dual gener- alization gap gen (S). (S)) in Eq. (6). And referring to the proof for case b. in Thm. (see Appendix D), we can get the result as above.
Corollary 3. Under Assumption 1,2,3, when each fi is MLSSC- we have the excess primal popu- Timin & min Ny,ch, μ min(pe Pyl
lation risk as follows, where nhuar & max Ny.th 7/2 and (waver Vuve) is defined in Eq. (3):
a. for fixed learning rates,
1
(2G I+ 2m1
naz 1)
C2 + C2 m
E[APT (x:
S 2
1+ u2 n mm Lpp 1-
+
+ mmmaa + 1(Cr Gyn
2(C, + Cyy)
1
VT
b. for decaying learning rates that mi ni 1[t+1] and naa m(t+1Je with c and 2c L+H
L +1,
E[A""
(wave)
2
2G
T1-c
4GLCs 1207L/(Lu))-1 1.
2
1+
2o + In 127-222- (((
112
H(1
c+
Lep
L
2e
T.
G²
141+
1,
(1 (1+InT)1
AGLCx(C.rt Ct)
1es1 +In T-1.
VT
2p
T
+
(1-c)TT
T
μu
Proof of Corollary 3. Firstly already know the argument stability bound for D-SGDA (denoted as A) on the last iterate. Then the averaged output follows due to the convexity of the norm:
(
x T T aape aae y yave
)l
((
x T T """
)
F.A
S FEA
(A)
D Uave
y
Then have the primal generalization gap according to Corollary 2 that E. (1 S
My Esta (A).
L arg
We decompose the primal population risk for the averaged output (xT v as follows:
F( y¹) - inf sup F(x',y) sup v'EY
Φ'E y'Ey
sup F( v') sup Fs Fs )') W'EY
sup Es(w v') inf Fs(w', y xeE
v'Ey
y'yy
inf Fs(a', t inf F(x', Vove) w'EX
inf F(x', vare) w'e
inf sup F(a', y') x'Ex v'Ey inf Fs(a', vive) ØeX
x'X
< sup F F(aT Tar y') sup Ps TT vn) W'EY
sup WEy
Y'EY)
inf Fs(x', wEX
inf F(x', vonn)
x'eX
where the inequality is due to: infarex F(a', Ay(S)) S infwrex supyrey F(x'v))
34

---

The first term is the primal generalization gap. And notice that the third term is analogous to the contrast side of the primal generalization gap. So both of them can be bounded by Egen (x aove))
While the second term is the strong primal-dual empirical risk referring to the proof of Thm. (see Appendix E.2).
Overall we can get the excess primal population risk, almost the same with the strong primal-dual population risk for SC-SC case (see Appendix E.3) except a /2-times factor in the argument stability error. And our bound analysis for the excess primal population risk is consistent with strong primal-dual population risk (see Remark below Thm.
I Additional Experiments
In this paper, we include two experiments including solving the AUC problem on svmguide and w5a by the decentralized SGD to verify the conclusions for the Convex-Concan case and the generative adversarial network training for the Nonconvex-Nonconcav Case on MNIST.
L1 General setup.
Different from the stability and generalization analysis of the way in [19], we need to deal with learning in a decentralized manner. In our experiments, we denote the total number of clients as Ne and S = {S1, S2, ................................ SN.). as the set of samples, where S; represents the observations stored in the i-th client. And we let Ns, denote the size of S. We follow the same experimental setting as outlined dataset S', which is constructed by individually changing one observation on each node. That is to say, for each S,, S is constructed by randomly changing one element in S. Then, we deploy the totally same sub-model on each client and initialize them to the same starting point. Then, each sub-model is trained on its local data. After each iteration, each sub-model is communicated with some other clients per predefined communication topology. To evaluate the distance between two models trained on and S', after finishing training, we obtain an ensemble model by averaging all sub-models collected from all clients.
in [13, 19] to build neighboring/perturiin
1.2 Detailed implementations.
For the AUC problem, we get two model squences {(w, u)} and ((w), Then, we calculate the Fuclidean distance A (I] - w' + ||v - v/113)1/2 For training each model on each client, the algorithm we used in our experiment is SOLAM [41], which is the SGDA designed for the minimax AUC problem. We repeat the experiments 10 times report the average results as well as the standard deviation.
For the generative adversarial learning problem, we just take the vanilla GAN structure, of which the generator and the discriminator comprise 4 fully connected layers, respectively, The leaky ReLU taken before the output layer. Following [19]. we ignore all forms of regularization such as the weight decay or dropout, and data augmentation tricks. We take 3 different seeds and 3 different ways construct S', which means changing different observations (total runs). To evaluate the model distance, we also take the Euclidean distance between the generator and discriminator separately.
Our implementation is highly based on the source 23
Pharp://gituuh..om//eeennnttni http://hh.naaaocccoooaoyyyy/m/na http://gttttt.oooommdddoooolllnt DSGDD
35


Reviews:
[{"review_id": "FTXqRZMiap", "reviewer": "Reviewer_5Agt", "summary": "This paper analyzes the generalization of the Decentralized Stochastic Gradient Descent Ascent (D-SGDA) Algorithm for min-max problem using the algorithm stability framework. Specifically, the paper analyzes the weak and strong primal-dual generalization gap under both convex-concave (C-C) and nonconvex-nonconcave (NC-NC) settings.\n\nThe key result is that the decentralized structure with undirected graph does not harm the generalization upper bound of D-SGDA.\nEmpirical experiments are performed to further validate the theoretical findings.", "questions": "1. In Table 1, why only the NC-NC case has a bound depending on $m$, the number of agents while other results do not depend on $m$?\n\n2. Please also include results on the optimization error and population risk in Table 1 or in the appendix.\n\n3. One theoretical result shows that the decentralized structure does not harm stability and generalization of D-SGDA. This is different from the conclusion of [31], which shows the decentralized SGD are adversely affected by an extra non-vanishing term compared to SGD. What leads to the difference in the conclusions? Is it because of specific assumptions on the structure of the undirected graph, or improved / tighter analysis? This needs to be discussed carefully since it is the main contribution of this work.\n\n4. In Theorem 6, what are the step size choices to achieve the corresponding bound? This needs to be stated as in other theorems.", "limitations": "The authors have discussed the limitations in Section 6, conclusion.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written and easy to follow.\n\n2. The paper studies an important problem of the generalization of the DSGDA algorithm for minmax problems in the decentralized settings.", "weaknesses": "1. Technical novelty is limited.\n\nThe algorithm stability for decentralized SGD algorithm has been analyzed in prior work [31]. And the algorithm stability for the SGDA algorithm for minmax problem has also been analyzed in prior work [18]. The techniques used in this paper mainly combine the two papers [18, 31].\n\n2. The tightness of the generalization upper bound obtained in this paper is not discussed.\n\n3. Some results are not clearly described. See **Questions**.\n\n\n### Minor:\n\n1. Unify the notations for projection operator. e.g. Algorithm 1 uses $P_{\\cal X}$, while line 564-567 in the appendix uses $Proj_{\\cal X}$.\n\n2. Line 109, \"differential\" -> \"differentiable\".\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 5Agt\n\nThank you for your careful reading and constructive suggestions! We have answered your questions in the comment below.\n\n\n***Q1: Limited technical novelty.***  \nWe answer this question on the common response. Please refer to part ***Technical novelty*** in the common response.\n\n\n***Q2: The tightness of upper bound.***  \nThank you for your constructive suggestions! We have not discussed the tightness of the generalization bound in our paper due to the fact that we are the first work to analyze the stability and generalization of decentralized minimax problems and we can not make comparisons. And we have to admit that we do not analyze the lower bound of our generalization gap, which is valuable for generalization analysis. We are thinking about this problem and will continue on this as future work inspired by [ref].  \nHowever, in a certain sense, we have a tighter bound compared with the existing stability and generalization analysis on D-SGD, our upper bound does not contain a *constant* term concerned with $\\lambda$. Specifically, as we have illustrated in the ***Technical novelty*** part in the common response, results in [31] contain an extra constant term concerned with $\\lambda$ which means the upper bound suffers from a nonvanishing influence of the communication network. While in our work, the term concerned with $\\lambda$ in the upper bound, in all cases of SC-SC ($\\frac{C_{\\lambda}}{T^{\\frac{L}{L+\\mu}}}$),C-C ($\\frac{1}{(1-\\lambda)T}$), and NC-NC ($(C_{\\lambda}T^L)^{\\frac{1}{c+L}}(\\frac{m}{n})^{1-\\frac{1}{c+L}}$), can vanish as iterations $T$ or the sample amount $n$ increase.   \nWe also implement comparisons with vanilla SGDA in the table presented in the PDF in the common response.\n\n[ref] *Stability of SGD: Tightness Analysis and Improved Bounds*\n\n***Typos***\n> Minors:\n> 1. Unify the notations for projection operator. e.g. Algorithm 1 uses $P_{\\cal X}$, while line 564-567 in the appendix uses $Proj_{\\cal X}$.\n> 2. Line 109, \"differential\" -> \"differentiable\".  \n\nThank you for your careful reading and we will revise in the paper as suggested.\n\n***Q3: Why only the NC-NC case has a bound depending on $m$?***  \nThank you for your insightful questions! In the NC-NC condition, we are using different deduction methods due to a lack of convexity. When meeting with the \"different\" sample for each local loss function, the cross term of the inner product between different local loss functions cannot be eliminated by the inequality property of convexity-concavity. Thus these cross terms can only be bounded by the Lipschitz property, and the number of cross terms will remain as a factor in the upper bound, which is related to the number of agents $m$.\n\n***Q4: More results on the optimization error and population risk in Table 1 or in the appendix.***  \nThanks for your kind suggestions. We present our main results as a summary in Table 1, including the generalization gap and population risk under SC-SC and C-C cases. We omit the optimization error here since we are mainly concerned about the generalization performance of D-SGDA and the population risk acts as a sum of generalization gap and optimization error. For more details, we present the optimization error (empirical risk) in Theorem 7 in Appendix E.2 and Corollary 1 in Appendix F.2 for SC-SC and C-C respectively. As for NC-NC conditions, we only obtain results on its generalization gap without its optimization error or even population risk. It's a great challenge for minimax stochastic optimization problems under NC-NC conditions, where the Nash equilibrium saddle point may not exist, and finding it is NP-hard.  \nBesides, we implement some comparisons with vanilla SGDA in the table presented on the PDF in the common response which you can refer to.\n\n\n***Q5: More discussion on the result that the decentralized structure does not harm the stability and generalization of D-SGDA.***  \nYes indeed, we draw the conclusion that the decentralized structure does not harm the stability and generalization of D-SGDA from the observation that our algorithmic stability bound does not contain a non-vanishing term concerned with $\\lambda$ (see Theorem 2, Remark 5 and Theorem 4, Remark 7). While in [31], as their Theorem 1 indicates that the second term in the algorithmic stability bound can not vanish with decaying learning rates and Theorem 2 shows that the second term does not disappear with iteration $T$ increasing.  \nActually, this difference does not come from extra assumptions. We can obtain a tighter bound due to the several preliminary steps in Line 563-567 in Appendix while [31] just directly comes to the norm of the differences, which result in a looser bound.  \n\nAt last, thank you for your kind suggestion to stress this contribution. We will revise our paper to stress our technical contribution.\n\n\n***Q6: More statement on the choice of the step size in Theorem 6.***  \nThank you for your kind suggestions. We miss the discussion about the choice of step size in Theorem 6. Here we complement the following discussion which will later be revised into our paper in the remark below Theorem 6.  \nFor fixed learning rates, the weak stability can be bound: $\\epsilon^w_{sta}(A)\\leq2\\sqrt{2}G^2(\\frac{{\\eta^{max}} T}{n}+\\frac{2L{\\eta^{max}}^2T}{1-\\lambda})$ which can reach $\\mathcal{O}(\\frac{1}{n}+\\frac{1}{(1-\\lambda)T})$ when $\\eta\\sim\\frac{1}{T}$. For deacaying learning rates that $\\eta_t^{min}=\\frac{1}{t+1}$, and $\\eta_t^{max}=\\frac{1}{(t+1)^c}, c\\leq1$, the stability and generalization gap is bounded by $\\small \\mathcal{O}((C_{\\lambda})^{\\frac{1}{c+L}}T^{\\frac{L}{c+L}}(\\frac{m}{n})^{1-\\frac{1}{c+L}})$."}, {"review_id": "r6yOSWGuAP", "reviewer": "Reviewer_FcPE", "summary": "The paper studied the generalization analysis of the decentralized stochastic gradient descent ascent algorithm through the lens of argument stability for solving minimax problems. Strong/weak primal-dual population risks are established for both convex-concave, strongly convex-strongly concave and nonconvex-nonconcave cases. \n", "questions": "1. Can the stability and generalization results be generalized to the directed graph?\n\n2. As mentioned in Weakness 2, could the authors provide some discussions or corollaries for discussing the choices of stepsize $\\eta$ and iteration number $T$ to establish the explicit population rates? \n\n3. A small question: in table 2, for fully connected graph, why $\\frac{1}{1-\\lambda}$=0?\n", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper provided a comprehensive stability and generalization analysis of D-SGDA for solving the minimax problem. Their results imply that the decentralized structure does not destroy the stability and generalization of SGDA.\n\n2. The impact of different topologies of the decentralized structure on the generalization bound is observed, which is very interesting.\n\n3. Experiments validate the theoretical results.\n", "weaknesses": "1. The results in Theorem 1 might be improved. Specifically, [1] established the connection between on-average argument stability and the weak primal-dual generalization gap for Markov chain SGDA (Here, SGDA is a special case of Markov chain SGDA) only with the Lipschitz assumption. Also, [2] provided this connection for Lipschitz losses. However, Theorem 1 requires the loss to satisfy both Lipschitz continuous and smooth conditions. For strong primal-dual generalization gap, [2] established the connection under the assumption $f$ is $\\mu_y$ strongly-concave, while Theorem 1 assumes that $f$ is $\\mu_x$ strongly-convex $\\mu_y$ strongly-concave. In addition, $\\mu$ is not defined in the theorem.\n\n\n2. The results for both weak primal-dual and strong primal-dual population risks depend on $T$, $\\eta$ and $n$. The authors might give some discussion on the choices of $\\eta$ and $T$, and establish the explicit population rates as provided in [1] and [2], and compare with their results. \n\n[1] Wang, P., Lei, Y., Ying, Y., and Zhou, D. X. (2022). Stability and generalization for markov chain stochastic gradient methods. Advances in Neural Information Processing Systems, 35, 37735-37748.\n\n[2] Lei, Y., Yang, Z., Yang, T., and Ying, Y.(2021). Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, pages 6175–6186.\n\n3. The experiment setup is unclear, I would suggest the authors add some details in the appendix. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer FcPE\n\nThank you for your positive feedback, constructive suggestions, and insightful questions! We have answered your questions in the comment below.\n\n***Q1: The results in Theorem 1 might be improved. Specifically, [1] established the connection between on-average argument stability and the weak primal-dual generalization gap for Markov chain SGDA (Here, SGDA is a special case of Markov chain SGDA) only with the Lipschitz assumption. Also, [2] provided this connection for Lipschitz losses. However, Theorem 1 requires the loss to satisfy both Lipschitz continuous and smooth conditions. For strong primal-dual generalization gap, [2] established the connection under the assumption $f$ is $\\mu_y$ strongly-concave, while Theorem 1 assumes that $f$ is $\\mu_x$strongly-convex$\\mu_y$strongly-concave. In addition, $\\mu$ is not defined in the theorem.***  \nThank you for your kind suggestions and we will add a detailed discussion on these two referred papers in our revision.  \n1.When establishing the connection between argument stability and weak primal-dual generalization gap, we are careless when checking the required conditions which strictly only need Lipschitz continuity. We will revise Theorem 1 for this part of our paper.  \n2.When establishing the connection between argument stability and strong primal-dual generalization gap, we check our proof process again and conclude that it does require $\\mu_x$SC-$\\mu_y$SC that strong convexity cannot be omitted. Because the deduction on the term $\\inf_{x'\\in\\mathcal{X}}F(x',y)$ also relies on the property of strong convexity to derive $F(x^*(y),y)$ and Lipschitz property of $x^*(y)$ with respect to $y$. This deduction is just symmetric to the term $\\sup_{y'\\in\\mathcal{Y}}F(x,y')$ which requires strong concavity as well. And we look into [2] and find that part c in Theorem 1 also requires strong convexity.  \nBesides, we apologize for the negligence of definitions here $\\mu\\triangleq \\min \\lbrace\\mu_x,\\mu_y\\rbrace$ which we will revise in our paper later.\n\n\n***Q2: More discussion on the results of population risks and the choice of $\\eta$, $T$, and $n$.***  \nThank you for your kind suggestions.  \nFor strong primal-dual population risk, for fixed learning rates, when we choose $\\eta\\sim\\frac{1}{\\sqrt{T}}$, our population rate is $\\mathcal{O}(\\frac{1}{n}+\\frac{1}{(1-\\lambda)\\sqrt{T}})$. For decaying learning rates that $\\eta^{min} _ t=\\frac{1}{\\mu(t+1)}$ and $\\eta^{max} _ t=\\frac{1}{\\mu(t+1)^c}$ , the population rate is $\\widetilde{\\mathcal{O}}(\\frac{T^{1-c}}{n}+\\frac{C_ {\\lambda}}{T^{\\min\\lbrace\\frac{1}{2},\\frac{L}{L+\\mu}\\rbrace}})$. Compared with vanilla SGDA[2], who reaches $\\mathcal{O}(\\frac{ln N}{\\mu N})$ for decaying learning rates that $\\eta_t=\\frac{1}{\\mu(t+t_0)}$ and $T\\sim N$, our results can matach when $n\\sim T^{\\min\\lbrace\\frac{1}{2},\\frac{L}{L+\\mu}\\rbrace}$.  \nFor weak primal-dual population risk, when $\\eta\\sim\\frac{1}{T^{\\frac{2}{3}}}$, the population rate is $\\mathcal{O}(\\frac{T^{\\frac{1}{3}}}{n}+\\frac{1}{(1-\\lambda)T^{\\frac{1}{3}}})$. Compared with vanilla SGDA[2], whose result is $\\mathcal{O}(\\frac{1}{\\sqrt{n}})$ when $T\\sim n$ and $\\eta\\sim\\frac{1}{\\sqrt{T}}$. And our results can match when $n^{\\frac{1}{2}}\\sim T^{\\frac{1}{3}}$. But there is no need to compare with the results in [1] of $\\mathcal{O}(\\frac{log n}{\\sqrt{n}log(\\frac{1}{\\lambda(P)})})$ when $T\\sim n$ and $\\eta\\sim\\frac{1}{\\sqrt{T log(T)}}$ , since their results are under the Markovian assumptions.  \nWe have included the discussions in Remark 6 and Remark 8 respectively. And further proof details can be referred to Appendix E.3 and F.3 respectively. We will revise our paper to include more detailed comparisons with the referred [1][2].\n\n\n***Q3: More details about the experiment setup.***  \nWe simplify the descriptions of the experiment set up in the paper due to the space limit, but we have implemented the details in Appendix I. We will make the descriptions more clear later.\n\n\n\n\n\n***Q4: Can our results be generalized to the directed graph?***  \nWe have to admit that our current methods have restrictions that the mixing matrix should be symmetric, i.e., the network is limited to undirected graphs. However, we have tried some experiments on exponential topology which is a directed graph. The results do not exhibit contradictions with undirected graphs, which may be potential for future theoretical work on directed graphs. And we are thinking of the decentralized distributed method of push-sum which may help us analyze the directed network.\n\n\n\n\n***Q5: Why $\\frac{1}{1-\\lambda}=0$ for fully connected graph?***  \nWe are sorry for the vague expressions in Table 2. The first row of $\\lambda$ represents the value of the crucial constant, while the last two rows of $C_{\\lambda}$ and $\\frac{1}{1-\\lambda}$ mean the value concerned about $\\lambda$ appeared in our bound result respectively. For a fully connected graph, $\\lambda=0$ so that $\\lambda$ will not appear in the bound result. Therefore we remark it as $0$ which means will disappear in the term."}, {"review_id": "ZWkXz9IN66", "reviewer": "Reviewer_ipno", "summary": "The paper investigates the primal-dual generalization gap bound of the decentralized stochastic gradient descent ascent (D-SGDA) algorithm. The authors start with a general decentralized minimax stochastic optimization problem, and its empirical counterpart calculated by the training dataset consisting of local samples. They model the network as an undirected graph with symmetric double stochastic matrix W. They assume Lipschitz-continuity and Lipschitz-smoothness on the local functions for the algorithm. They define weak and strong population risks, weak and strong generalization gaps -between the training dataset and original unknown distribution-, and algorithmic stability. The main purpose of the paper is the connection between and e-argument stable algorithm to its generalization gaps, both weak and strong. The authors show that the weak and strong -for strong convexity- strong concavity satisfied- generalization gaps are bounded by the argument stability error of an e-argument stable algorithm. The authors further show the boundedness of the argument and weak stability errors for strongly convex-strongly concave, convex-concave, and nonconvex-nonconcave settings. They analyze the generalization gaps for various parameters, including network topology, learning rates, and the number of nodes to show that the results are bounded as proposed.", "questions": "None", "limitations": "As the authors state, the analysis requires Lipschitz continuity and smoothness, and the stability and generalization analysis of D-SGDA for heterogeneous data distribution is missing. How would the analysis on stability and generalization vary for a directed network? In this case, W wouldn’t be necessarily symmetric, how would that affect the analysis?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper aims to investigate the connection between argument and weak stability with strong and weak generalization gaps for a training dataset for D-SGDA algorithm. The authors claim to propose this connection not only for D-SGDA algorithm, but for decentralized minimax algorithms in general. Their generalization and stability bounds for decentralized SGDA extent the stability and generalization for vanilla SGDA, so it can be said that the study is original. The overall quality of the paper is well, the problem is well-defined in a clear way and the approach is shown clearly. The results are significant at an acceptable level, since the study proposes the decentralized structure does not violate stability and generalization of SGDA algorithms, and decentralized minimax algorithms in general, as the bounds are shown by the authors.", "weaknesses": "In general, the paper is well-structured, but I believe a few things could be more elaborate. For example:\n\n1. The mixing matrix and its purpose, how to select λ, what the W corresponds for a network topology could be explained better.\n\n2. Proof of Theorem 1 in Appendix could show some intermediate steps where 𝑆(𝑙) is included.\n\n3. Typos: Theorem 2, part b. wording, Ref. 6, sizes of parentheses in equations", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer ipno\n\n\nThank you for your careful reading and constructive suggestions! We have answered your questions in the following comment.\n\n***Q1: More explanations on the mixing matrix $W$ and the crucial constant $\\lambda$.***  \nThank you for your kind suggestions. We will provide more details about the background and preliminary of the network and its associated mixing matrix in Section 3.2. Actually each communication network $G=(V,E)$ is naturally associated with an adjacency matrix, which is usually called a mixing matrix in the context of decentralized learning. Each element in the mixing matrix represents whether these two nodes communicate and the non-zero value will estimate the probability of one node choosing to communicate among its neighborhood. As for the crucial constant $\\lambda$, it is naturally defined with a given matrix that is the second largest eigenvalue. So there exists a correspondence between specific network topology and the mixing matrix also and the constant $\\lambda$.  \nI can further illustrate the relationship by an example in the PDF in the common response which you can refer to.\n\n\n***Q2: More intermediate steps in the proof of Theorem 1.***  \nActually $S^{(l)}$ is only a symbol for neighboring dataset in a decentralized manner (see Definition 4). In the proof of Theorem 1, we specify the detailed setting of $S^{(l)}$ as illustrated in Line 527-530 that $l=(l_1,l_2,...,l_m)$ with each $l_k$ representing the $l$-th local dataset differs by the $k$-th local sample. As for the formula begins at Line 536, the first equation is because there are $n^m$ kinds of permutation of $S^{(l)}$ and the symmetric distribution between $\\xi_{i,l_i}$ and $\\xi'_{i,l_i}$. And the subsequent steps do not involve the derivation of $S^{(l)}$.\n\n\n***Typos: Theorem 2, part b. wording, Ref. 6, sizes of parentheses in equations.***    \nThank you for your careful reading. We will revise these typos in our paper and polish our writing later.\n\n\n***Limitations: directed network.***   \nThank you for your insightful comment! Our theoretical result does rely on the property of the undirected graph, where the mixing matrix needs to be symmetric. We have also made experimental attempts on the *exponential* network and the experiment shows similar results, which offers us a clue for further theoretical research on directed networks. The research for directed graphs is nowadays a novel research avenue with notable works of *push-sum distributed algorithm* and we will attempt to address this issue in future work."}, {"review_id": "6VifmeZ4cp", "reviewer": "Reviewer_CPGp", "summary": "this paper provides an analysis of the stability and generalization of decentralized GDA algorithms in SCSC, CC, and NCNC settings. the main results indicate that a decentralized setting GDA has similar error bounds as centralized settings. numerical experiments on AUC and GAN problems are reported.", "questions": "1. what is the main technical difficulty for DGDA compared with the centralized case?", "limitations": "see weakness", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. the analysis looks solid to me and the results build the bridge between GDA and DGDA for generalization bound.\n2. the numerical experiments are strong and convinsing.", "weaknesses": "1. the figures are too small, need to zoom in to read the content.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments! We have answered your questions in the following comment.\n\n***Q1: Size of the figures.***  \nThank you for your valuable suggestions. We will zoom in on Figure 1 and Figure 2 for better readability.\n\n***Q2: Technical difficulty of D-SGDA.***  \nThank you for your insightful question. We answer this question in the common response. Please refer to the part ***Technical challenges*** in the common response."}, {"review_id": "KoExjETyve", "reviewer": "Reviewer_Z6QM", "summary": "This paper establishes the algorithmic-stability analysis of the decentralized stochastic gradient descent-ascent (D-SGDA) algorithm which is commonly used for min-max problems in distributed settings. This is turn leads to generalization bounds of D-SGDA for various assumptions on convexity-concavity of the objective. In particular, the paper focuses on two notions of generalization for min-max problems, namely weak and strong primal-dual generalization error. The bounds are expressed in terms of sample-size, training horizon and certain information about the mixing matrix such as the spectral gap. The flavor of results are closely-related to the recent analyses in literature that obtain algorithmic-stability bounds for decentralized gradient descent, however this work extend these to min-max scenarios.  The bounds (as expressed in the theorems) take complicated forms in term of the problem parameters, however the authors provide simplified interpretations of them in the remarks. In particular, the derived bounds strongly depend on the learning rate and spectral gap of mixing matrix in order to be meaningful. In particular, for strongly convex-strongly concave objectives, the generalization bounds are of order $O(\\frac{\\eta}{1-\\lambda} + \\frac{1}{n})$ and for the convex-concave case the bounds are $O(\\frac{\\eta T}{n} + \\frac{\\eta^2 T}{1-\\lambda})$ for learning-rate $\\eta$, sample size $n$, training time $T$ and the spectral gap $1-\\lambda.$ ", "questions": "Please see the last section for questions and suggestions. ", "limitations": "The limitations of the work are clear and I see no potential negative societal impact related to this work. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The studied problem is new as it is the first work to obtain generalization bounds for D-SGDA. Although the generalization error of decentralized gradient descent and the gradient-descent algorithms were studied separately in existing works, this paper gives a unifying analysis. The method is largely based on the work of Hardt et al and relevant works on the gradient descent-ascent literature. \n\nThe derived bounds are in rather simple forms and might be informative on the role of sample-size or some other parameters such as the strong-convexity parameter on the generalization. \n\nThe paper is generally clear and easy to read although some aspects of the presentation can be improved as I will discuss in the next section.\n\nSeveral experiments on different topologies presented in the paper seem to back the general claim on the role of spectral-gap and connectivity on generalization performance. I will discuss this more in the next section. \n\n", "weaknesses": "Weaknesses and some questions:\n\n1 - One of my main concerns is that the generalization bounds derived in this paper are essentially vacuous for a large set of commonly used learning-rates or training time choices. Even for strongly convex-strongly concave setup, the generalization bounds are meaningful only when considering time-decaying learning rates. The authors do not compare their results to the state-of-the-art results for the generalization of ordinary gradient descent-ascent with fixed learning rate, therefore it is impossible to discuss the optimality of the obtained rates. This is especially important due to the role of step-size on the optimization and convergence of D-SGDA. The derived bounds also appear to be very sub-optimal for convex-concave objectives: the bounds are increasing in $T$ (because of the $\\eta^2 T/(1-\\lambda)$ term), therefore common early stopping choices such as $T\\approx \\sqrt{n}$ lead to a vacuous generalization bound unless the learning rate is decaying.      \n\n2 - The results in Table 1 are not very informative: there is no comparison with Decentralized SGD (D-SGD) and SGDA methods and the choice of step-size for each row is also not specified. It will be helpful if these comparisons are added.      \n\n3 - In line 47-49 the authors assert that *\"Note that even for the decentralized minimization problem, the generalization and\n stability of decentralized SGD are adversely affected by an extra non-vanishing term [31], and the stability usually suffers from a constant term λ^2\"*. While the current results on the stability of D-SGD indeed suffer from this additional term, these are just upper bounds therefore the conclusions on the role of topology/mixing matrix are not accurate until the optimality of these bounds are proved. \n\nIn the conclusions section the authors state *\"Our theoretical results show that a decentralized\nstructure does not destroy the stability and generalization of D-SGDA\"* . This is wrong as explained above and even in contradiction with the generalization rates obtained throughout the paper, as the generalization error rates is severely affected by decentralization.  \n\n4- A precise discussion on the optimization guarantees of DSGDA with the given learning rate selections seems lacking in the paper. This will be beneficial for understanding final test error rates. \n\n5 - Some parts of the paper can be rephrased: \n\n- The descriptions in the \"Related Works\" section are wrong in some places: The work of Bousquete and Elisseeff  established the connection between generalization and stability. Hardt et al. just showed that the output of SGD satisfies the stability notion. I think the lines 87-89 need to be edited. \n\n- The sentence in line 80 \"Huang [15]....\" is also not clear and I think it needs to be rephrased. \n\n- The authors refer to (Sun et al. 2021) and (Zhu et al. 2022) for previous works on generalization of decentralized methods. Some missing and relevant works that study generalization of DGD are the following:\n\n  *\"Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent\"* by Richards et al. 2020.\n\n  *\"On Generalization of Decentralized Learning with Separable Data\"* by Taheri et al. 2023.\n\n  *\"High-dimensional inference over networks: Linear convergence and statistical guarantees.\"* by Sun et al 2022.\n\n\n- In the abstract (lines 11-13), the purpose of the sentence is not clear, since the bounds essentially are in terms of sample-size, learning rate and iterations. \n\n- The sentence in line 35 is not clear. Can the authors please rephrase this sentence?\n\n- Line 150: the sentence starting with \".And therefore\" needs to be rephrased. Also see Line 235 and the sentence \".So...\". \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer Z6QM\n\nThank you for your careful reading and constructive suggestions! We have answered your questions in the following comment.\n\n***Q1: Vacuous results for generalization bounds.***  \n1.Our results of generalization are not vacuous even for fixed learning rate conditions. In SC-SC case, the stability and corresponding generalization gap bound is $\\mathcal{O}(\\frac{\\eta}{1-\\lambda}+\\frac{1}{n})$ for fixed learning rates as we have discussed in Remark 5, where we can choose the learning rates as $\\eta\\sim\\frac{1}{T}$ to get a non-vacuous bound. And in C-C condition, the generalization bound is $\\mathcal{O}(\\frac{\\eta T}{n}+\\frac{\\eta^2 T}{1-\\lambda})$ for fixed learning rates as shown in Remark 7, where we can also choose $\\eta\\sim\\frac{1}{T}$ to obtain a non-vacuous bound.  \n2.Compared with vanilla SGDA, their generalization bound under SC-SC tis $\\widetilde{\\mathcal{O}}(\\frac{1}{\\sqrt{T}}+\\frac{1}{N})$ (see Theorem 2.(e) in [18]). Our results can almost match it except for the influence of $C _{\\lambda}$. Under C-C condition for fixed learning rates their generalization bound is $\\mathcal{O}(\\frac{\\sqrt{T}}{n}+\\frac{1}{\\sqrt{n}})$ (see Theorem 2.(b) in [18]), our result can approach it when $\\eta\\sim\\frac{1}{T^{\\frac{3}{4}}}$ and $n\\sim T^{\\frac{3}{4}}$ except for the influence of $\\frac{1}{1-\\lambda}$. As for the influence of $\\lambda$, i.e., the topology effect. We have made a thorough investigation in Remark 5.(3) with proof in Lemma 3 and Remark 10 in Appendix C for detail.\n\n***Q2: The results in Table 1 are not very informative: there is no comparison between Decentralized SGD (D-SGD) and SGDA methods and the choice of step size for each row is also not specified. It will be helpful if these comparisons are added.***  \nThank you for your kind suggestions! In fact, our work focuses on the minimax problem, and we revise the Table and make comparisons with vanilla SGDA in generalization gap and population risks with respect to specified learning rates in the table presented in the PDF in the common response which you can refer to.  \nHowever, compared with D-SGD which solves the minimization problem, our results can in a certain sense be tighter for the reason that our results do not contain a constant term concerned with $\\lambda$. The $\\lambda$-concerned term in all settings, SC-SC($\\frac{C_{\\lambda}}{T^{\\frac{L}{L+\\mu}}}$), C-C($\\frac{1}{(1-\\lambda)T}$), NC-NC($(C_{\\lambda}T^L)^{\\frac{1}{c+L}}(\\frac{m}{n})^{1-\\frac{1}{c+L}}$) can all vanish as iterations $T$ and sample amount $n$ increase.\n\n\n***Q3: Questions about the statement.***  \nThank you for your constructive comments. We should revise our statement. Actually, we draw this conclusion due to the fact that our results containing $\\lambda$-term can vanish as we have illustrated in the answer to ***Q2***. While in [31], the term concerned with $\\lambda$ can not eliminate no matter how we choose the parameters.\n\n\n***Q4: More discussions on the optimization guarantees.***  \nThank you for your kind suggestions. We have put the discussions about the optimization error in the appendix due to the space limit. Specifically, the optimization error for SC-SC is $\\frac{C_{x}^2+C_{y}^2}{2\\eta^{min}T}+\\eta^{max}G^2+\\frac{4(C_{x}+C_{y})GL\\eta^{\\max}}{1-\\lambda}+\\frac{2(C_{x}+C_{y})G}{\\sqrt{T}}$ for fixed learning rates, and $\\frac{2G(C_{x}+C_{y})}{\\sqrt{T}}+T_{x}+T_{y}+T_{max}$ for decaying learning rates $\\eta_{x,t}=\\frac{1}{\\mu_{x}(t+1)^{c_{x}}}$ and $\\eta_{y,t}=\\frac{1}{\\mu_{y}(t+1)^{c_{y}}}$, where $T _ {\\alpha}=\\left\\\\{\\begin{array}{cc}\n                \\frac{G^2}{2\\mu_{\\alpha}}\\frac{1+\\ln{T}}{T} & c_{\\alpha}=1\\\\\\\\\n                \\frac{G^2}{2\\mu_{\\alpha}(1-c_{\\alpha})T^{c_{\\alpha}}} & 0< c_{\\alpha}<1\n            \\end{array}\n            \\right.$ and $T _ {max}=\\left\\\\{\\begin{array}{cc}\n                \\frac{4GLC_{\\lambda}(C_{x}+C_{y})\\ln{T}}{\\mu T} & k_{min}=1\\\\\\\\\n                \\frac{4GLC_{\\lambda}(C_{x}+C_{y})}{\\mu(1-k_{min})T^{k_{min}}}  &  0< k_{min}<1\n            \\end{array}.\n            \\right.$  \nAnd the optimization error for C-C is $\\frac{C_{x}^2+C_{y}^2}{2\\eta^{min}T}+\\eta^{max}G^2+\\frac{4(C_{x}+C_{y})GL\\eta^{\\max}}{1-\\lambda}+\\frac{2(C_{x}+C_{y})G}{\\sqrt{T}}$ for fixed learning rates.  \nThe details are presented in Theorem 7 in Appendix E.2 and Corollary 1 in Appendix F.2 respectively.  \nFurthermore, considering the population risk is a sum of the generalization gap and optimization error. We have to re-choose the learning rates for lower population risk. For SC-SC case, we should choose $\\eta\\sim\\frac{1}{\\sqrt{T}}$ to also guarantee the optimization convergence, as we discussed in Remark 6. For C-C case, we have to re-choose $\\eta\\sim\\frac{1}{T^{\\frac{2}{3}}}$ to also guarantee the optimization convergence, as we discussed in Remark 8. \n\n\n\n\n***Suggestions on the rephrased parts.***  \nThank you for your careful reading and constructive suggestions. We will revise our paper and polish our writing.  \n- Line 87-89: Bousquete and Elisseeff[4] established the connection between generalization and stability. Elisseeff[8] extends the concept to randomized algorithms. Hardt[13] followed the theory and proved the stability of SGD.\n- Line 80: Huang[15], Luo and Ye[24] proposes accelerating algorithms by methods of variance reduction.\n- We will discuss these related works in proper positions in our paper.\n- Line 11-13: Yes indeed, what we mean is our results also analyze the impact of different topologies on the generalization bound except the trivial factors. - Line 35: However, it is important to consider the generalization performance for the stochastic algorithm, which is quantitatively evaluated by the value difference between Eq.(1) and Eq.(2).\n- Line 150: Hence, the difference between the empirical and population gaps can reflect the generalization performance.\n- Line 235: The major difference with vanilla SGDA lies in $C_{\\lambda}$ and the number of nodes $m$."}]

Author rebuttal:
# Common Response

***Technical challenges***  
The major difference with vanilla SGDA lies in the communication through different local agents. The vanilla SGDA can be seen as a special case where there is only one agent and it can train on its own dataset and update its parameters all by itself. While in the decentralized setting, after each local agent updates by each local gradient sampled on the local dataset, they have to communicate with each other to complete the iterations.  
So the key challenge is how we deal with the communication process. By means of the mixing matrix $W$ and its associated crucial constant $\lambda$, we can quantitatively characterize the communication between agents and observe from the bound results to figure out the impact of different communication ways (or associated network topology) on the generalization performance. In a decentralized setting, we need to measure the impact of consistency on generalization due to the fact that gradients are computed locally. Compared with the centralized approach, the decentralized setting lacks the aggregation step involving all workers, which can lead to a certain degree of model inconsistency.


***Technical novelty***  
We are the first work to analyze the stability and generalization of D-SGDA for decentralized minimax problems, which is nontrivial considering the complex structure of minimax problems combined with the communication between agents.  
Firstly, we propose the decentralized framework for analyzing stability and generalization based on the thought of permutation, which is not discussed in existing decentralized work. While under the new definitions of the decentralized neighboring dataset and corresponding decentralized algorithmic stability (see Definition 4 and 5, where we allow each local dataset to hold at most one different sample), we can see more clearly how the number of agents and local samples could influence the generalization performance. Furthermore, our proposed definitions are well-defined that when $m=1$, the decentralized definitions can be naturally degraded into vanilla one. When $m>1$, it can characterize the isolated influence of the number of the agent on the generalization performance.  
Secondly, we have derived a tighter generalization bound compared with existing decentralized results. There are only two works concentrating on the generalization of decentralized algorithms. [43]requires a rather strong assumption that the weight difference obeys Gaussian distribution, and results in [31] contain an extra constant term concerned with $\lambda$ which means the upper bound suffers from a nonvanishing influence of the communication network. While in our work, the term concerned with $\lambda$ in the upper bound, in all cases of SC-SC ($\frac{C_{\lambda}}{T^{\frac{L}{L+\mu}}}$),C-C ($\frac{1}{(1-\lambda)T}$), and NC-NC ($(C_{\lambda}T^L)^{\frac{1}{c+L}}(\frac{m}{n})^{1-\frac{1}{c+L}}$), can vanish as iterations $T$ or the sample amount $n$ increase.  


To summarize our ***contribution***, we are the first work to investigate the stability and generalization of D-SGDA for minimax problems. When meeting with the above challenges, we come up with the method of permutation and eventually draw the conclusion with a tightly bound to reveal the topology effect on the generalization performance.



Meta-review: The paper presents generalization bounds for decentralized SGDA for min-max problems using the algorithmic stability approach. Reviewers appreciate the pioneering and comprehensive exploration of this important problem. The novel finding that the decentralized structure doesn't compromise SGDA's stability and generalization, along with its enhancement of existing work by relaxing assumptions on $\lambda$, is well-received. Although there were initially raised concerns about technical novelty, these were addressed in the rebuttal, leading to a revised score. Therefore, I recommend its acceptance.

I also strongly encourage the authors to thoroughly address all reviewers' comments in the revised version, particularly concerning the relationship with relevant cited papers.
Decision: Accept (poster)