Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness
Authors: Shuang Zeng
Yunwen Lei
Venue: ICML 2025 poster (2025)
Keywords: Algorithmic stability
generalization analysis
decentralized SGD
Primary area: theory->learning_theory
TL;DR: We develop stability and generalization bounds for decentralized SGD.

Abstract: Decentralized SGD (D-SGD) is a popular optimization method to train large-scale machine learning models. In this paper, we study the generalization behavior of D-SGD for both smooth and nonsmooth problems by leveraging the algorithm stability. For convex and smooth problems, we develop stability bounds involving the training errors to show the benefit of optimization in generalization. This improves the existing results by removing the Lipschitzness assumption and implying fast rates in a low-noise condition. We also develop the first optimal stability-based generalization bounds for D-SGD applied to nonsmooth problems. We further develop optimization error bounds which imply minimax optimal excess risk rates. Our novelty in the analysis consists of an error decomposition to use the co-coercivity of functions as well as the control of a neighboring-consensus error.

Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness
Shuang Zeng' Yunwen Lei
Abstract
gree of the connection. Then, each local model iteratively conducts a weighted average and a gradient descent.
Decentralized SGD (D-SGD) is popular op- timization method to train large-scale machine learning models. In this paper, we study the gen- eralization behavior of D-SGD for both smooth and nonsmooth problems by leveraging the algo- rithm stability. For convex and smooth problems, we develop stability bounds involving the training errors to show the benefit of optimization in gen- eralization. This improves the existing results by removing the Lipschitzness assumption and im- plying fast rates in low-noise condition. We also develop the first optimal stability- general- ization bounds for D-SGD applied to nonsmooth problems. We further develop optimization error bounds which imply minimax optimal excess risk rates. Our novelty in the analysis consists of an еттor decomposition to use the co-coercivity of functions as well as the control of a neighboring- consensus error.
The impressive success of D-SGD in practice motivates a lot of theoretical studies to understand their behaviour, for which challenge lies in the control of a consensus error. Most of these studies focus on the convergence analysis to show the behavior the training datasets (Lian et al., 2017; 2018; Koloskova et al., 2020; Xin et al., 2020). As comparison, there is far less work on the generalization analysis to understand the performance on testing datasets, which is central topic in learning theory. Indeed, gener- alization analysis sheds insights on how different factors contribute the prediction, which helps the construction of early-stopping rule avoid overfitting (Hardt et al., 2016).
Richards and Rebeschini (2020) initialized the generaliza- tion analysis of D-SGD by leveraging the concept of uni- form stability. Several works improve the generalization analysis by considering another stability concept called on- average model stability (Zhu et al., 2022; Le Bars et al., 2024; Taheri and Thrampoulidis, 2023). While these results are interesting to understand the generalization behavior of D-SGD, there is still room for further improvements. For example, these stability analyses often impose restric- tive assumptions such as bounded gradient assumption and bounded variance assumption. Furthermore, they fail to imply optimal generalization bounds that can fully capture low-noises conditions for fast rates. In this paper, we aim to improve these discussions by removing restrictive assump- tions and getting optimistic risk bounds. Our contributions are summarized as follows.
1. Introduction
Modern machine learning often involves large-scale datasets which contain private information of users. This asks for the development of scalable optimization methods that can preserve the private information (Lian et al., 2017: 2018). An efficient methodology to meet these requirements is to distribute the datasets over several agents, each of which only processes its own local datasets. In this way, the pri- vate information of a local dataset is not revealed to other agents. Decentralized stochastic gradient descent (D-SGD) representative distributed optimization method where each agent updates its own local model by building stochas- tic gradient using its own local dataset. These agents are connected via a communication graph which shows the de-
We present the generalization and convergence analysis for D-SGD on smooth and convex problems, for both of which we remove the existing Lipschitzness assumptions and get fast rates under a low noise condition. We build on-average model stability bounds, which involve the training errors to show the benefit of optimization in generalization. We present clear comparison (Table 1) to show the advantage of our stability analysis as compared to existing results.
'Department of Mathematics, The University of Hong Kong, Hong Kong, China. Correspondence to: Yunwen Lei <leiyw@ hku.
We also consider nonsmooth problems with Hölder con- tinuous gradients, for which we present a comprehensive analysis show the effect of smoothness parameter and
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Stability and Generalization Analysis of Decentralized SGD
the spectral gap on stability and generalization. For the specific Lipschitz problems, we present the first optimal generalization bounds for D-SGD.
2.2. Decentralized SGD
The exploration of decentralized optimization algorithms dates back to the work of Tsitsiklis (1984). Decentralized gradient descent (DGD) was studied by Nedic et al. (2009), where the consensus error was introduced as an important ingredient in the analysis of decentralized algorithms. The stochastic variants were also extensively studied due to their simplicity and effectiveness in addressing large-scale ma- chine learning challenges, mostly focusing on the optimiza- tion properties (Sundhar Ram et al., 2010; Xu et al., 2015; Duchi et al., 201 I; Lian et al., 2017; Vlaski and Sayed, 2021; Pu and Nedić, 2021; Koloskova et al., 2020; Le Bars et al., 2023; Zhang et al., 2024b). Generalization issues of D-SGD are also drawing increasing attention recently. Richards and Rebeschini (2020) considered a different variant of D-SGD and derived generalization bounds by using uniform stabil- ity and Rademacher complexity (Bartlett and Mendelson, 2002). Sun et al. (2021) considered the same D-SGD ours, and developed uniform stability bounds. On-average model stability of D-SGD was recently studied, where topology- aware (Zhu et al., 2022) and
A challenge in the stability analysis of D-SGD is the control of a neighboring consensus error. Our key obser- vation is that this error can be offset by the co-coercivity of gradient map, towards which we introduce new error decomposition.
The paper is organized as follows. Section 2 gives the related work. Section 3 formulates the problem. We present our result for smooth and nonsmooth problems in Section 4 and Section 5, respectively. Conclusions are given in Section 6.
2. Related Work
2.1. Algorithmic Stability
Algorithmic stability is fundamental concept in learning theory to measure the sensitivity of an algorithm with re- spect to a perturbation on the training dataset. Various stability concepts have been introduced in the literature, including the uniform stability (Bousquet and Elisseeff, 2002), on-average stability (Shalev-Shwartz et al., 2010), argument stability (Liu et al., 2017) and on-average model stability (Lei and Ying, 2020). The uniform stability is arguably the strongest stability measure, which can imply high-probability generalization bounds (Bousquet and Elis- seeff, 2002: Bousquet et al., 2020; Klochkov and Zhivo- tovskiy, 2021; Feldman and Vondrak, 2019; Fan and Lei, 2024; Li et al., 2024). The on-average stability has a close connection to the learnability (Shalev-Shwartz et al., 2010). The influential work (Hardt et al., 2016) pioneered the sta- bility analysis of SGD for Lipschitz and smooth problems, which motivates a lot of interesting studies on the stability of stochastic optimization algorithms (Kuzborskij and Lam- pert, 2018; Neu et al., 2021; Lei and Ying, 2020; Charles and Papailiopoulos, 2018; Bassily et al., 2020; Nikolakakis et al., 2022; Schliserman et al., 2025). For example, the Lipschitzness and smoothness assumption in Hardt et al. (2016) were weaken based the on-average model stabil- ity. While convexity assumption is often imposed in the stability amalysis, recent progress leverages the stability con- cept to study the generalization hehavior of gradient descent methods to train neural networks (Richards and Kuzborskij, 2021; Wang et al., 2025; Taheri et al., 2025; Deora et al., 2024; Zhang et al., 2024a). Algorithmic stability was widely used study the generalization behavior for various learn- ing tasks such as adversarial training (Xiao et al., 2022; Zhang et al., 2024a), federated learning (Sun et al., 2024: Chen et al., 2024), differential privacy (Bassily et al., 2020; Wang et al., 2024) and meta-learning (Maurer, 2005).
(Le Bars et al., 2024) generalization bounds were developed. These stability analyses were extended to other decentralized algo- rithms such as DGD (Taheri and Thrampoulidis, 2023) and decentralized stochastic gradient descent ascent (Zhu et al., 2024).
3. Problem Setup
Let TP be probability measure defined on sample space 2 := X' V, where X' is an input space and y S R is an output space. We consider a decentralized learning set- ting where the training examples are distributed over m agents. Specifically, for the k-th agent, we assume that a training dataset S = {zI. ) of size n is inde- pendently drawn from P. We collect all these m datasets into S := - Sk. based on which we want to build a prediction function h X' + R. We consider parametric learning where the prediction function / is parameterized by 0 E W C Rdd The performance of 0 is measured by {(0; z). where E W x Z + R,, is a loss function. Our objective is to find a global model e E W minimizing the population risk defined by
example
1 Σ
R(O)
E Ea-z[e(0, 2)},
which quantifies the behavior of the model on a testing dataset. Here E-[-] denotes the expectation w.r.t. z. We also
define the empirical risk as
Rs. (0), where Rs, (0) = 1 Σ ((0, 22,e),
Rs(
n2 1=1
which quantifies the behavior of the model on training.
2

---

Stability and Generalization Analysis of Decentralized SGD
Given S, we apply a randomized learning algorithm A to build model as an approximation of 0r arg mineew R(O). We denote A(S) as the model produced by running A to S. We are interested in studying the excess risk (()) - R[ which can be decomposed as
between the moduli of the two largest singular values of matrix associated with graph. In decentralized learning, the spectral gap measures the connectivity of the underlying communication graph (Zhu et al., 2022). For instance, À = 0 for a fully connected graph, where each element of the communication matrix is Conversely, in a ring graph of varying sizes, the value of X increases with the size of the graph and approaches as the size of the ring approaches infinity (Vogels et al., 2022). The inverse of the spectral gap, i.e. I-VX' can significantly depend on the number of agents m. For one of the most standard communication matrices, the inverse of the spectral gap is O(1) in the fully connected graph, (m) in the grid graph and ((m²) in the cycle graph (Lu and De Sa, 2023).
B[R(A(S))] - R(0*)= = E[)(A(5)) - Rs(A())) + E[(Rs(A(S) Rs())), (3.1)
R(O"). We refer to B[R(A(S)) [s()] the generalization gap, which measures the difference between training and testing for the output model. Moreover, we call E[Rs(A(S)) Rs [ the optimization error which measures the difference be- tween the training error of the output model versus the best model.
where we use (0))
Algorithm Decentralized SGD
Input: Initialize Vk, 0% = O(0) E Rd, iteration number T, stepsizes {m T 1 weight matrix W. for 1 =
3.1. Decentralized SGD
In this paper, we apply D-SGD (Lian et al., 2017) to mini- mize (0). We assume there are m agents communicated via a communication graph represented by weight matrix W E [0, 1] |mm" where Wa reflects the weight of informa- tion sent from agent / to agent k. D-SGD initializes all the local models with the same point ((0) At the t-th round, each agent k independently samples datapoint =y uni- formly from its local dataset Sy (i.e., 1/ follows the uniform distribution over [n] := 21. n)), based on which it computes a local gradient at its own model 8(*) Then, it receives local models from other agents for weighted ag- gregation, after which it moves along the negative direction of local gradient with the step size T)t This process can be formulated as
T ,, do
for each agent = 1,.... m do
Sample 1 by the uniform distribution over [x]
o(t+1) + - Wwo T/ Ve(O zrg.a)
end for end for
3.2. Stability and Generalization
Algorithmic stability measures how the output model will change if we change a single example in the training dataset (Bousquet and Elisseeff, 2002). Various stability concepts have been proposed in the literature. In this paper, we consider the on-average model stability which can relax the smoothness and the Lipschitzness assumption. Below, we adapt the stability concept in Lei and Ying (2020) to the decentralized learning setting.
m Σ
(1++1) k
Ww - N1 Ve(O a).))
(3.2)
In this paper, we always consider non-increasing step sizes, ie.. M S. T/- We summarize the procedure of Decentral- ized SGD in Algorithm 1.
Definition 3.2 (On-average model stability). Let c > 0. Let S = (SI...., with St = {E1,K. 2n,k] and = ($,...,,S,, 3m) with S₁ = (........, } be two indepen- dent copies such that 2i, ~ P and & ~ P. For any i E [n] and j E [m], denote by S( the dataset formed from S by replacing the i-th element of the j-th agent's dataset by بر
To study D-SGD, we impose an assumption on the mix- ing matrix, which is standard and has been widely used in the analysis of decentralized learning algorithms (Sun et al., 2021: Deng et al., 2023; Le Bars et al., 2024; Taheri and Thrampoulidis, 2023; Zhu et al., 2022; Richards and Rebeschini, 2020).
5(0)) -S (S,,...,,SSI,,SS S 5/00 Sy-1...... Sm).
where s() fai...... 2-1,, 2,, 2+11, .......... 2n. We say algorithm A is on-average eoodel stable if
Assumption 3.1 (Mixing matrix). We assume W is doubly stochastic, i.e., W W1 = 1 where 1 E Rm is the vector that contains only ones, and max ( ([>((W), (Am (W)I) < 1, where (W) denotes the i-th largest eigenvalue of W.
n m
Es.SAA
ΣΣ
|IA(S) -
((S))A(((()))))) A(S S a
Lim
Let À = maxx{)3(W X2, (W)). Then, 1 - v is referred to as the spectral gap, which defined as the difference
To study the connection between stability and generaliza- tion, we need to introduce standard concepts on the Hölder
3

---

Stability and Generalization Analysis of Decentralized SGD
continuity and Lipsethizness. Smooth loss functions include the logistic loss for classification and the least square loss for regression. Lipschitz loss functions include the logistic loss, hinge loss and Huber loss (Mohri et al., 2018). 8). Examples of loss functions with Hölder continuous gradients include the q-norm hinge loss and q-th power absolute distance loss with y E [1, 2] (Steinwart and Christmann, 2008).
function {(;; is convex and T-smooth. Les (0)
0 be
the I-th iterates of D-SGD run over S, and 0 (((1)))
..... 0n (1))
be the t-th iterates of D-SGD run over S(t)), Denote f(t) m m 2k=1 A=1 8 and ((t.i))
1 m -k= 0(6.55) Let
A(S) = - and A(S = ((T.i)) (4.1)
Definition 3.3 (Hölder continuity). Let a E [0,1] and T. > O. We say a function g has (a, I.)-Hölder continu- ous gradients if
If
2 +)Lm +2) m
1 s 0,
(4.2)
(1- 212
L
then
[V - Vgg (0')ll2 S 1100 0 vO,0'.
BIIA(S)) - )13) 5
Especially, when a = L, we say the function g is L-smooth. Definition 3.4 (Lipschitzness). Let G > 0. We say a function g is G-Lipschitz continuous if [g()) g(0') 1
m
T-1
LA
+ m
GilØ 2 for any 0.0'.
m²n
(1-
The following lemma is direct extension of a result in Lei and Ying (2020) to the decentralized learning setting. We give the proof in Section A for completeness.
n
Tie E
|
2n |12] )}
m
nn
Lemma 3.5. Let S, S and ((ú) be constructed in Defini- tion 3.2, and let > 0. Let A be a randomized algorithm.
Remark 4.2. If we impose a G-Lipschitzness condition,
Theorem 4.1 implies (we assume ne = 77 for brevity)
a) Suppose for any z, the function w + ((W;2) is non- negative and L-smooth. Then
m
BIIA(()) - AAS
VI
1=1
G²
(1 X)2 1) + m²n2
LT
G
S L (Rss(()((((S))+
(4.3)
mn
L ++7
In S m(1 m(11)))/L, which is widely used in both the exist-
E S.S. B.S.SA (IA(((())) - A
2mm
ing convergence analysis (Richards and Rebeschini, 2020) and stability analysis (Taheri and Thrampoulidis, 2023) of decentralized algorithms, then Eq. (4.3) further implics
b) 1fw + ((w; 2) is G-Lipschitz continuous, then
1
G2 T 12
ESS (R(A()()(S))) - Rss
B[ILA(S) - ) S
mn
G " m mn
E (s. - A(S))l2).
(4.4)
If we impose G-L.ischtizzness condition in Lei and Ying (2020), then it was shown that the vanilla SGD is on-average e-mdel stable with e² S d'n²² (T+ TT) Therefore, our on- average model stability analysis recovers the existing result for the specific single-machine serial case. Eq. (4.4) can be G"n² rewritten as N ( + T with N = mn, showing that increasing m improves stability even when the total number of samples N is fixed. The underlying reason that we consider E2 on-average model stability, which is the second moment of random variable and can be decomposed as bias and variance term. Since the average operator reduces the variance by factor of m, there is factor of 1/m in our stability bound (Theorem 4.1 gives a bound on the square of the le on-average model stability). As a comparison, the previous discussions either consider local iterates or the
4. Convex and Smooth Problems
In this section, we present the generalization analysis in the convex and smooth case.
4.1. Stability Analysis
We first present our main result on the stability of D-SGD, which control the stability by the magnitude of gradients en- countered in the trajectory. The proof is given in Section B. We denote S B if there exists a universal constant C' such that A < CB. We denote x B if S B and B S A. Theorem 4.1 (Stability bound), ). Let Assumption 3.1 hold. Let S, ((1) be defined in Definition 3.2. Assume the loss
4

---

Stability and Generalization Analysis of Decentralized SGD
4 version of stability, which may not show the effect of variance reduction of D-SGD with agents. Our results also match recent findings in Lei et al. (2023), which show that the variance decreases by a factor of batch size or local machines.
bounds involving training errors, which shows the benefit of optimization in stability. Our analysis requires step sizes to satisfy Eq. (4.2) and 1i2 S ( (1=2)² (8L*[I+A] + zi ) which are A)/
satisfied if 7) - (1- L. This is a mild assumption since for D-SGD we often choose Tt X 1/VT, which vanishes as T co. The proof is given in Section B.1.
Remark 4.3 (Novelty). As compared to the stability anal- ysis for the vanilla SGD, a challenge in the decentral- ized case is to control the neighboring consensus er-
Corollary 4.4. Let Assumption 3.1 hold. Let E((;2) be convex and L-smooth. Let A(S),A((())) be defined in [1-A1²
rors: Σ -0==B[[[00 [[[ o( ((..1)) + o((.65) [|]] Existing works (Sun al., 2021; Taheri and Thrampoulidis, 2023)
Eq. (4.1). If (4.2) holds and th S [87-(1+7] + -i _ then
decompose this term into two consensus errors and use the
n m
estimate for the consensus eπror as follows
B[II((S) - 1(5
mn
T-1 n
[[|01]] 0/²) - g(.s)) + o(. [|3]
I.
Lapt
+ 1 m
E [Rs((O)))
1)2
mn
T
1=0
B B11000
1 -0(
[1((1.155) 0(6.65)) - [
+ 2
2 T-1
T/E
R [[Rs(00))]
(4.5)
1=0 1=
t= 1=1
m2n
Tm
T-1
- (1 - 2)²
E n Σ
( (0')
Remark 4.5 (Comparison). For brevity, we consider con- stant step sizes. We now compare our stability bounds with existing results. Richards and Rebeschini (2020) consid- ered different variant of D-SGD, and derived uniform stability bounds of order GTTT' which was extended to the D-SGD in Algorithm 1 (Sun et al., 2021). Under a Gaussian weight difference assumption, a topology-aware stability bound of order 3 m Ex= Rs, (ol + 1 + À was derived (Zhu et al., 2022). Le Bars et al. (2024) developed an improved stability bound as follows
This decomposition ignores the important property that o and el(:)) are produced based on two neighboring datasets, which should be close. Due the ignorance of this impor- tant property, the existing stability analysis implies some- what crude bounds (Sun et al., 2021; Taheri and Thram- poulidis, 2023). Instead, we give a bound of neighboring consensus errors which can capture the closeness of 0% and c (5)
vm
(see in Lemma B.3)
m
E [[IA(S)- x onf + GTTOWW
0 g(a.ss) + 0|6,50112 2
mn
mn
m RRs (0% ) +, (4.6)
T-1
ve(Ol () -
2 1|
m7
m
t=
where R3,- = ming Rs, (0), ΣT I - 1| and a bounded variance assumption was imposed
where Z1, = 2ng. and (11) = ري,ة if (A: = j & = and ærg.* otherwise. Our key observation is that the term /v(((() [1.,x) ve(0( 212 can be offset by us- ing the co-coercive property of the convex and smooth loss functions, To this aim, we introduce an error decomposition
1 sup max - O RE m) TE
VE( Z,, V 0². (4.7)
Taheri and Thrampoulidis (2023) showed that DGD is on- average e-model stable with (detailed calculations are given in section B.2)
to get (0())
g(t.)j) (E(B()) (?) Zig,a) - ve(o ) |E( [(., - vE(Of( 2(10)
k
which offsets
12 by
VVTT mE
LiRVVT 1-X
( E E (4.8)
ES
(0 -
ve(o(") mm(aa - ve(o((t)) )
VE(O kıg,k) ve(Of(b)) 2 I
1
Under mild assumption that n S TL, our analysis shows that D-SGD is on-average e-mddel stable with
We control the gradient norm with a self-bounding prop- erty (Srebro et al., 2010), and derive the following stability
LIVTT mn
Vmn(1 X
E E[Rss(
$ (4.9)
5

---

Stability and Generalization Analysis of Decentralized SGD
Table I: Stability Bounds for Convex and Smooth Problems. C,S, L denote the assumptions of convexity, L-smoothness and G-Lipschitzness respectively. Here, A in the column "Type" means the variant A of D-SGD, i.e., of+ - (o
T: v xr,,),, B means the variant B of D-SGD, i.e., o((+1) t Ei=1 Wia Ve(
k 2gg.)). For the bound in Cw = Σi= W - w 1|2 and impose a bounded
Le Bars et al. (2024), we use the notation Rg = ming Rs, Cw variance assumption in Eq. (4.7).
Type
Reference
C
S
L
Stability Bounds
SGD/A
Richards and Rebeschini (2020)
v
v
GTT
170
SGD/B
Sun et al. (2021)
v
v
v
Gx22' mm + Gi
SGD/B
Zhu et al. (2022)
v v
x
k=1 Rss (0 + vm
+
vn
SGD/B
Le Bars et al. (2024)
v
m 2i=1
Ris.. ElRss (0(0) - + GTT+
mn
GD/B
Taheri and Thrampoulidis (2023)
v
x
DVLT
L D 1-x
V ET=
El ElRs ( (Section B.2)
SGD/B
Ours
LyvT
Laj² mn
Ly
+ #n)
E [[R((0(0))
11-
Our analysis improves the stability analysis in Le Bars et al. (2024) by removing the bounded variance assump- tion and the Lipschitzness assumption. While Eq. (4.6) also involves training errors, the dominant term in the bound is oyI+GTTCW if is not sufficiently small. As a compari- son, stability analysis can imply fast rates in low-noise condition. Our analysis also outperforms that in Taheri and VT
and L-smooth. Define 0(() 3.1 holds and nt- = 1) with
m Ek=1 Ex=
0% If Assumption
8L² + A)n²"
+ +2m S 2' (1 - 1)2
(4.11)
then
T
E((|@(1) --1131
Thrampoulidis (2023), as it involves a factor 1-A nore/ L. for brevity), which is replaced by
(we ig-
E (o()))) Rs((0))
2
7/
"
Vmn(1- (1-xj Xj
m/n
16L + A)n² 1)2 + +4Tn) [[Rs((0)] (4.12)
in Eq. (4.9). If 1 2 mnT and v) 2~ 1-2 bound is better since
then our stability VTnm"
Remark 4.7 (Comparison). For convex, L-smooth and G- Lipschitz problems, it was shown (Richards and Rebeschini, 2020; Sun et al., 2021)
VT
1
77
(4.10)
mmn(1- - X)
myn
Our analysis suggests 17 x 1/ymn and T x mn Re- mark 4.9, and in this case the left-hand side of Eq. (4. is significantly larger than the right-hand side. Then, Eq. (4.9) is sharper than Eq. (4.8). Finally, it should be emphasized that we consider D-SGD, while Taheri and Thrampoulidis (2023) considered DGD. We summarize the comparison in Table 1. According to the table, it is also clear that our stability analysis also improves Sun et al. (2021) and Zhu et al. (2022) by removing the term GrfT/(1 A) and X, respectively, which do not converge to even if nm goes to infinity.
T
|00113 TfT 1 (1 X)2
G2T GLm +
Σ - 1=1
T
(4.13)
A key difference between our result and Eq. (4.13) that our optimization error bound involves the empirical risk of 0r. Therefore, it implies fast rates in an interpolation set- ting. In more detail, by choosing 17 x 1/VT, Theorem 4.6 implies convergence rates of order O(1/VT) in a general case. In the interpolation setting with a vanishing (8())), Theorem 4.6 implies fast convergence rates of order O(1/T) by choosing 1) X As a comparison, Eq. (4.13) requires an additional Lipschitzness assumption and can only im- ply convergence rates of order O(1/VT), Convergence of DGD was also recently studied in Taheri and Thrampoulidis (2023). Their analysis considers learning with separable data. As a comparison, our convergence analysis covers a more general case and focus on D-SGD, which is more than DGD.
4.2. Convergence Analysis
Theorem 4.6 to be proved in Section B.3 gives convergence rates of D-SGD for smooth and convex problems. It should be mentioned that our assumption on step size in Eq 14.11) is consistent with Eq. (4.2) and that in Corollary 4.4.
Theorem 4.6 Optimizzaiion error). Assume E(:; 2) is convex
computationally--fii
6

---

Stability and Generalization Analysis of Decentralized SGD
4.3. Excess Risk Analysis
et al. (2018)), where is the sample size. Since our training set has mm examples in total, our stability analysis implies minimax optimal excess risk bounds of the order 1/ l/ymn.
We combine the stability and convergence analysis together, and derive the following excess risk bounds for D-SGD convex and smooth problems. Our bound is optimistic in the sense of involving the risk of the best model (Srebro et al., 2010). The proof is given in Section B.4.
We now consider a low-n setting where R(0*) + | IB/ (17) S 1/(7T). Theorem 4.8 with y L shows
1 L'11 (1 - A) + LM +
Theorem 4.8. Let assumptions in Theorem 4.1 and Theorem 4.6 hold. Then for any Y > O we have
Crisk 2
1/T
Ln TL3( (1-X)2 + mn
1912T² + m²n2
B[R(A(S)) R(00) 2 (R(O)+ + 118112 112
1/T
T/I
L
T(L + 7) 1--XP (11
Ln + n)
(L + 1)) m²n²
which can be simplified as
mn
1.2n L 1 + Giak 2 T(1 T(1-1)2
12
T2nT
100 1
L21p2 (1 A)2 + Lm B
+ T nI
mn(1 - 2)2 m²n
+
of
We choose 17 x (1 sizes, and get
L to meet our assumption on step
Remark 4.9 (Mlustration). In the standard setting with
R(0*) + |10 (1/(( 1, Theorem 4.8 shows that
L
L
L3 AJT
Crisk == E[R(A(S)) - R(0*) S
10"
I2²12
Ln
Crisk ~ T(1-
mm
m2n1
nfT
(1- A)2
L T(L + + (1- + ))
(L+ 17 m²n²
We choose T X VI(1-X) and get Grisk S That is, we get fast rates of order 1/(m)) independent of the spectral gap in a low-noise case.
mn
+
+ ?
mn
We choose the optimal to minimize this bound and get
Remark 4.10 (Comparison). Excess risk bounds of or- der 1/ /nn were also developed in Richards and Rebes- chini (2020) for a different variant of D-SGD, where the model aggregation is performed after local update. The work (Sun et al., 2021) considered our D-SGD and de- veloped excess risk bounds of order 1 + G' + T-X 7/T
110113
1,212 (1-
LVTn/
Ln
1
Crisk S
-npt
n/T
Vmn
212
m
mn
Since
LvTn Vmn
Ly
z
L'n² [1 A)²
+ LanT and assuming
G'y
TI., we further get
GºaT which, however, will not converge due to the term 1-X The recent work (Le Bars et al., 2024) considered the generalization gap without discussions on optimization error. Furthermore, their generalization bound involves VTa ( m Em E[Rs, (0(")- -),,,)) It is not clear how mn to control this term by optimization theory. Therefore, their analysis fails to imply fast rates of order 1/(mn) even com- bined with optimization error bounds in low-noise setting. As a comparison, our stability bound involves EE ((())(()))) $ which can be controlled by opti- mization theory and implies the first fast rates of order (11(mm)) under a low-noise condition. Moreover, these works (Richards and Rebeschini, 2020; Sun et al., 2021; Le Bars al., 2024) require Lipschitzness assumption, which is removed in our analysis.
10
L2 X)2
+ Lm + LaTTT
Grisk
nf
mn
Taking 17 x
110" l
gives
([(L+)//T/(mm)))
1
L
Crisk S
+100012 12
T(1 7(1 (mn))
T mn
Setting T mm/m\ve VT., we get
a 10 2)2
10 Vmn
Crisk
mn
The minimax statistical error for learning with a convex and smooth function is O(1/vn)) (c.g., Theorem 7 in Chen
5. Convex and Nonsmooth Problems
Forr simplicity, we assume T is large so that such y satisfy the condition y S (1 - A)/T. in Eqs. (4.2) and (4.1 1). For example, suggested choice is T x mn/ /T. Our assumption on step sizes holds mn is large.
In this section, we study the stability and generalization of D-SGD applied to convex and nonsmooth problems. Instead, we impose a Hölder continuity assumption on the gradients.
7

---

Stability and Generalization Analysis of Decentralized SGD
5.1. Stability Analysis
Then,
We first present stability bound for D-SGD applied to non- smooth problems. Our bound incorporates the magnitudes of gradients encountered in the learning process, and shows the benefit of optimization in improving generalization. The proof is given in Section C.I.
1
Ca.1
2
T
E E[Rs
S
(B(Rs(0(0)))
T
T
1=1
E
0(1)
01
L2'n
2n/I'
maT
Theorem 5.1 (Stability bound). Let Assumption 3.1 hold and b 2(1+A)
(1-X)² + 2L. Let A(S) and A(S(s)) be defined in Eq. (4.1). If e(=:2) is convex and has (a, -HHöder continuous gradients with a E [0, 1). then
L
T
El|[O! 100') (5.3)
+ (a + 1)m
We can control the above consensus errors and derive the ex- plicit convergence rates. For simplicity, we only consider the Lipschitz case. By choosing l x 1//T., Theorem 5.5 im- plies convergence rates of order O(1/VT), which matches that of vanilla SGD (Bottou et al., 2018).
B[IA(S)) - (
m
T-1
3 +
2
I z ||
<
n²n
m
Theorem 5.5 (Optimization Error for Lipschitz problems), Let Assumption 3.1 hold. Assume {(:: 2) is convex and G- Lipschitz continuous. Define 1it) 1
16
1
[V z4,5) (1))))1))))))))))))
E
m k= o( E Rdd
n
j=
If we choose constant step size ll and B > 0 such that (1 + B) 2 < 1, then
4L(1 -
Σ
7
(5.1)
1 1+a
1 T T
E1 - 11
E B (Rs(()))
+13GPn
21/T
For Lipschitz continuous problems, we get the following simplified stability bounds to be proved in Section C.1.
1=1
10/2(1+1/3)) G2n
(5.4)
Corollary 5.2 (Stability bound for Lipschitz problems). Let Assumption 3.1 hold. Let A(S) and A()())) be defined in is convex and G- G-Lischiitz continuous, then
(1 (1- (1+
(4.1). If ((12)
5.3. Excess Risk Analysis
In this subsection, we combine the above stability and con- vergence analysis together to derive excess risk bounds for D-SGD. For simplicity, we only consider the Lipschitz case. The proof given in Section C.3.
n
m
B[IAASS) - A(S(3))
mn
==
T-1
G2
T-1 Σ
m
2 h
(5.2)
Theorem 5.6 (Excess Risk for Lipschitz problems). Let assumptions in Corollary 5.2 and Theorem 5.5 hold. Then
m n 2
Remark 5.3. For convex and Lipschitz problems, it was shown that the vanilla SGD is on-average e-model stable
E E|((((())-R(()) GTTT GTTT'
10 TfT (1
G
mn 1-X +
with e² $ (T + T T²/n")n² )n? Our analysis recovers their bound in the single machine case.
Remark 5.7. We choose
110-112 T 7= GVT mn
VT
5.2. Convergence Analysis
+
+
1 1-
X (1- x) vm
We now study the convergence for nonsmooth problems. Our optimization error bound involves the consensus errors (I)(()) - (+)) [|, which reflect the variation of the D-SGD iterates around their agent center. The idea of using consen- sus errors to study the convergence of D-SGD dates back to Nedic et al. (2009). The proof is given in Section C.2.
and derive
E[((A(())) Gl 1|2
T
VT
VT
m
1-x
(1 A) m
We can choose T x (mm)²
X) to get
Lemma 5.4 (Optimization error). Let Assumption 3.1 hold. Assume ((::2) 2) is convex and has (a,, L) -Höler continuous gradients with a E [0, 1). Define g(t) = m -m 0(4)
G 1
[[R(A()))--R(0))
v m
8

---

Stability and Generalization Analysis of Decentralized SGD
Excess risk bounds were also developed for D-SGD applied to convex and Lipschitz problems based on a uniform con- vergence approach (Richards and Rebeschini, 2020), where it was assumed that (o; are Rademacher random variables, i.e, taking values in { 11,41 with the same probability)
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential socictal consequences of our work, none which we feel must be specifically highlighted here.
Bo,,sEin|
sup mn
Σ ort((;
mn
2
1 Vmn
(5.5)
References
P. L.. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-48)) 2002. R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stabil- ity of stochastic gradient descent nonsmooth convex losses. In Advances in Neural Information Processing Systems, volume 33, pages 4381 1-4991, 2020.
Under this assumption, D-SGD with appropriate param- eters was shown to satisfy E[R(A(S))] - - & L/(mn)& (Richards and Rebeschini, 2020). As a com- parison, our stability analysis removes the assumption in Eq. (5.5) and implies minimax optimal bounds of order O(1/ /m) (Chen et al., 2018).
L. Bottou, F. E. Curtis, and J. Nocedal. Optimization meth- ods for large-scale machine learning. SIAM Review, 60 (2):223-311, 11, 2018.
6. Conclusions
We present comprehensive stability and generalization analysis of D-SGD for convex problems, covering both the smooth and nonsmooth setting. Our stability bounds involve the training errors of the D-SGD iterations, which establish a connection between generalization and optimization. We also get convergence rates that can interpolate between the slow rate O(1/VT) and the fast rate O(1/T), depending on whether there exist models with small training errors. We combine the generalization and convergence analysis to develop optimistic excess risk bounds that can be of order 1/ (mm) in low-noise setting. We also give the first excess risk bounds of order O(1/ /mn) for D-SGD applied to non- smooth problems. Our studies remove several assumptions in the literature such as the Lipschitzness condition and the bounded variance assumption.
O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2(Mar):499 2002.
O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626, 2020.
7. Charles and D. Papailiopoulos. Stability and generaliza- tion of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages
744-753, 2018.
J. Chen, H. Chen, B. Gu, and H. Deng. Fine-grained the- oretical analysis of federated zeroth-order optimization. In Advances in Neural Information Processing Systems, volume 36, 2024.
Y. Chen, C. Jin, and B. Yu. Stability and convergence trade- off of iterative optimization algorithms. arXiv preprint arXiv: htv:/800/ 804,01619, 2018
There remain several interesting problems for further stud- ies. First, we only consider convex problems in this paper. It is interesting to investigate whether our stability analy- sis can be extended to a nonconvex setting. For example, it is interesting to study the stability and generalization analysis of decentralized algorithms for training overpa- rameterized neural networks, where we can exploit some weak-convexigy (Richards and Kuzborskij, 2021; Wang et al., 2025) and self- bounding weak-convexity (Taheri et al., 2025; Deora et al., 2024) to develop stability bounds. Sec- ond, we only develop excess risk bounds in expectation. It is interesting to develop tigh-probability bounds to understand the robustness of D-SGD.
X. Deng, T. Sun, S. Li, and D. Li. Stability-based gen- eralization analysis of the asynchronous decentralized sgd. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 7340-7348, 2023.
P. Deora, R. Ghaderi, H. Taheri, and C. Thrampoulidis. On the optimization and generalization of multi-head attention. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
J. C. Duchi, A. Agarwal, and J. Wainwright. Dual aver- aging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):592 606, 2011.
Acknowledgement
J. Fan and Y. Lei. High-probability generalization bounds for pointwise uniformly stable algorithms. Applied and Computational Harmonic Analysis, 70: 101662, 2024.
We are grateful to the area chair and reviewers for their con- structive comments and suggestions. The work of Yunwen Lei is partially supported by the Research Grants Council of Hong Kong [Project Nos. 22303723, 17302624].
V. Feldman and J. Vondrak. High probability generaliza- tion bounds for uniformly stable algorithms with nearly

---

Stability and Generalization Analysis of Decentralized SGD
optimal rate. In Conference on Learning Theory, pages 1270-1279, 2019.
Learning Research, 24(93):1-62, 2023.
A. Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research, 6(Jum):967-994, 2005. M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
M. Hardt, B. Recht, and Y. Singer. Train faster, general- ize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1234-1234, 2016.
A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis. On distributed averaging algorithms and quantization ef- fects. IEFE Transactions on automatic control, 54(11):
Y. Klochkov and N. Zhivotovskiy, Stability and deviation optimal risk bounds with convergence rate (11nn). In Advances in Neural Information Processing Systems, vol- ume 34, pages 5065-5076, 2021.
2506-2517, 2009.
Y. Nesterov. Universal gradient methods for convex opti- mization problems. Mathematical Programming, 152(1):
A. Koloskova, N. Loizou, S. Boreini, M. Jaggi, and S. Stich. A unified theory of decentralized sgd with changing topol- ogy and local updates. In International Conference on
381-404, 2015.
G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-theoretic generalization bounds for stochas- tic gradient descent. In Conference on Learning Theory, pages 3526-3545 3545. PMLR, 2021.
Machine Learning, pages 5381-5393. PMLR, 2020.
I. Kuzborskij and C. Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning. pages 2820-2829, 2018.
K. Nikolakakis, F. Haddadpour, D. Kalogerias, and A. Kar- basi. Black-box generalization: Stability of zeroth-order learning. In Advances in Neural Information Processing Systems, volume 35, pages 31525-31541, 2022. S. Pu and A. Nedić. Distributed stochastic gradient tracking methods. Mathematical Programming, 187(1):409-457, 2021.
B. Le Bars, A. Bellet, M. Tommasi, E. Lavoie, and A.-M. Kermarrec. Refined convergence and topology learning for decentralized sgd with heterogeneous data. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 1672-1702. PMLR, 2023.
B. Le Bars, A. Bellet, M. Tommasi, K. Scaman, and G. Neglia. Improved stability and generalization guaran- tees of the decentralized sgd algorithm. In International Conference on Machine Learning, pages 26215-26240, 2024.
D. Richards and I. Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. In Advances in Neural Information Processing Systems, volume 34, pages 8609-8622 2021. implicit
Y. Lei and Y. Ying. Fine- graingr analysis of stability and generalization for stochastic gradient descent. In Inter- national Conference Machine Learning, pages 5809- 5819. PMLR, 2020.
D. Richards and P. Rebeschini. regularisation for distributed stochastic subgradient de- scent. Journal of Machine Learning Research, 21(4)): 1-44, 2020.
Y. Lei, T. Sun, and M. Liu. Stability and generaliza- tion for minibatch sgd and local sgd. arXiv preprint arXiv:2310.011 1339 2023.
M. Schliserman, U. Sherman, and T. Koren. The dimension strikes back with gradients: Generalization of gradient methods in stochastic convex optimization. In Interna- tional Conference on Algorithmic Learning Theory, pages 1041-1107. PMLR, 2025.
S. Li, B. Zhu, and Y. Liu. Algorithmic stability unleashed: generalization bounds with unbounded losses. In Inter- national Conference on Machine Learning, pages 29489- 29510, 2024.
S. Shalev-Shwarde O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Jour- nal of Machine Learning Research, 11(0ct):2635-26770 2010.
X. Lian, C. Zhang, H. Zhang, C.-J, Hsich, W. Zhang, and Liu. Can decentralized algorithms outperform central- ized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Infor- mation P Processing Systems, pages 5331-5344 2017.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, pages 2199-2207, 2010.
X. Lian, W. Zhang, C. Zhang, and J. Liu. Asynchronous decentralized parallel stochastic gradient descent. In Inter- national Conference on Machine Learning, pages 3043- 3052. PMLR, 2018
I. Steinwart and A. Christmann. Support Vector Machines. Springer Science & Business Media, 2008
T. Sun, D. Li, and B. Wang. Stability and generalization of decentralized stochastic gradient descent. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9756 1756-9764, 2021.
T. Liu, G. Lugosi, G. Neu, and D. Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pages 2159-2161 2017.
Z. Sun, X. Niu, and E. Wei. Understanding generalization of federated learning via stability: Heterogeneity matters. In International Conference on Artificial Intelligence and
Y. Lu and C. De Sa. Decentralized learning: Theoretical op- timality and practical improvements. Journal of Machine
10

---

Stability and Generalization Analysis of Decentralized SGD
Statistics, pages 676-684, PMLR, 2024.
tivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1-52, 2024.
S. Sundhar Ram, A. Nedić, and V. V. Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and appli- cations, 147:516-545, 2010.
M. Zhu, L.. Shen, B. Du, and Tao. Stability and gener- alization of the decentralized stochastic gradient descent ascent algorithm. In Advances in Neural Information Processing Systems, volume 36, 2024.
H. Taheri and C. Thrampoulidis. On generalization of de- centralized learning with separable data. In International Conference on Artificial Intelligence and Statistics, pages 4917-4945. PMLR, 2023.
T. Zhu, F. He, L. Zhang. Niu, M. Song, and Tao. Topology-aware generalization of decentralized sgd. In International Conference on Machine Learning, pages 27479-27503. PMLR, 2022.
H. Taheri, C. Thrampoulidis, and A. Mazumdar. Sharper guarantees for learning neural network classifiers with gradient methods. In International Conference on Learn- ing Representations, 2025.
N. Tsitsiklis. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology, 1984.
S. Vlaski and A. H. Sayed. Distributed learning in non- convex e ii: Polynomial escape from saddlc-points. IEEE Transactions on Signal Processing, 69:1257-1270, 2021.
T. Vogels, H. Hendrikx, and M. Jaggi. Beyond spectral gap: The role of the topology decentralized learning. Advances in Neural Information Processing Systems, 35: 15039-15050, 2022.
P. Wang, Y. Lei, Y. Ying, and D.-X. Zhou. Differentially private stochastic gradient descent with low-noise. Neu- rocomputing. 585:127557, 2024.
P. Wang, Y. Lei, D. Wang, Y. Ying, and D.-X. Zhou. Gen- cralization guarantees of gradient descent for shallow neural networks. Neural Computation, 37(2):344 402, 2025.
J. Xiao, Y. Fan, R. Sun, J. Wang, and Z.-Q. Luo. Stability analysis and generalization bounds of adversarial training. In Advances in Neural Information Processing Systems, volume 35, pages 15446-15459, 2022.
R. Xin, S. Kar, and U. A. Khan. Decentralized stochastic optimization and machine learning: A unified variance- reduction framework for robust performance and fast convergence. IEEE Signal Processing Magazine, 37(3): 102-113, 2020.
J. Xu, S. Zhu, Y. C. Soh, and L. Xie. Augmented distributed gradient methods for multi-agent optimization under un- coordinated constant stepsizes. In IEEE Conference on Decision and Control, pages 2055-2060. IEEE, 2015.
K. Zhang, Y. Wang, and R. Arora. Stability and generaliza- tion of adversarial training for shallow neural networks with smooth activation. Advances in Neural Information Processing Systems, 37:16160-16131 2024a.
S. Zhang, N. Xiao, and X. Liu. Decentralized stochastic sub- gradient methods for nonsmooth nonconvex optimization. arXiv preprint arXiv:2403. 1555, 2024b.
P. Zhao, Y.-.. Zhang, L.. Zhang, and Z.HH. Zhou. Adap-

---

Stability and Generalization Analysis of Decentralized SGD
A. Proofs on Stability and Generalization
In this section, we present the proof of Lemma 3.5 on the connection between on-average model stability and generalization for decentralized methods. The following lemma (Srebro al., 2010) builds the self-bounding property for a smooth and nonnegative function, meaning that the gradient can be bounded by function values. The self-bounding property has been widely used to improve the theoretical guarantee of various learning algorithms (Srebro al., 2010; Lei and Ying, 2020; Taheri et al., 2025; Zhao et al., 2024).
Lemma A.1
property). If is L-smooth and nonnegative, then for any 0 we have Vv(00)1 - (Lg(O).
Proof of Lemma 3.5.
Similar to the proof of Theorem 2 in Lei and Ying (2020), due to the symmetry, we know
12
Es,A [R(A(S)) (s((())) = E $33,4
(B(A(S())) - (s(A())))
mm
= E 3,3,4 LYN
(E(A(S())) : E(A(S);*
(A.1)
where the last identity holds since A(S(5) is independent of Zi.j. The stated bound in part b) then follows directly from the Lipschitzness condition.
We now prove part a). According to the I-smoothness of w -> E(w; 2), we know (Nesterov, 2015)
2w; S 2(W;;) + (w w. w. V((W;2)) /||
wl3
2
which, together with Eq. (A.1), implies that
[s.a[R(A65) ((()) Rs(A(S)))
12
m
E S.S.A (A(S(6)) A(A),)) - -1A($10))A($511)) (A.2)
mn
According to the Schwarz's 's inequality we know
(A(S() -(()), VE(A(S); z.,)) & A(S)S//SSSI///((())::.)).)))))
2 (14((111 - A(S) A(5))
1 VE(A(S);
27
- 2 (1((S00)) - A(S) ((A(S)) 21.),
(A.3)
where the last incquality due the self-bounding property of smooth functions (Lemma A. Combining Eq. (A.2) and Eq. (A.3), we derive
Es (R(AS)) - Rss(S)))
L ++7 Σ
a m
E S.3.A -
ES.A ((A(S):
2mn
mm
f=1
L L+7 7
n m
E S, [|A(S(09) -A()))
L (Rs
+
2mn
where we use the fact that mi
Σn ((A(S): z:)) (A(S)))
B. Proofs for Convex and Smooth Problems
B.1. Proofs on Stability Analysis
Before our stability analysis, we first introduce some useful notations which will be used throughout the paper. Let g(t) ,..., 8l be the 1-th iterates of D-SGD run over Let (ft-))) ,..., ((t.5)) be the 1-th iterates D-SGD run over (5())).
12

---

Stability and Generalization Analysis of Decentralized SGD
Denote 0(0) 1. m Σ 0 ((..))) m
1
Ek=
For any [m]] denote Zıg.8 = =ig.b and
2 1
i = and I = i,
else.
That is, (10) is the example selected by the k-th local machine at the t-th iteration when applied D-SGD to S We 1..k collect all the weights in matrices
(+) (0 ( E Rx (
=(6 (B( )
RRxd
(B.1)
( (0()) T E Rx g(..)) (0(L. g(a,t))) Rmxd
where 0 =
2==1 m
0g is an average over m agents. Furthermore, denote
VI(O 2r. = (V(())) Zg..),... Ve(o mmmmm))) E Rmxd
VI(OM) 2/r2) = (V(())) Z.,.)..... Ve(On)) (pm,m) E RR
VI(A(())) -...) (Ve(o( 2/1 v((0().)) -Z(o) )) E Rmxd
VE(((CL))) k,.) (Ve()))))) Z(0)
((((tt..)((((( ( m)
Ve(((t.i))
) Ruxd
Then, we have
(+)) = (W 7/-
- V ((.ii)) = ( -
(B.2)
Let
0n +1+ 2(1 8- 12
02 4(1 + +
03 (1 B)A, 04 -1
(B.3)
where we choose some 3 > 0 such that a1, a3 < 1. For a matrix A, we denote by ||A||] its Frobenius norm and ||A||| its operator norm.
The following lemma shows how to solve quadratic inequality. omit the proof for simplicity.
Lemma B.1. Let a, 2 x < ar + b, then x² < a² 2b.
The following lemma shows the co-coercivity of convex functions with Hölder continuous gradients (Hardt et al., 2016; Lei and Ying. 2020), which plays an important role in our stability analysis.
Lemma B.2 (Co-coercivity). (f((2))) is corvex and has (a, L--Hölder continuous gradients with a E [0, 1}, then
2L _
(0 - ve(0 vE(00:2)) 2 1 VE(0;2) ve(0';
Note if a 0, the right-hand side means 0.
We first present a lemma to control the cetehbbbrinn-coosssssiii error in terms of the difference of gradients.
Lemma B.3. Let Assumption 3.1 hold and ag a4 be defined in Eq. (B.3). Let ((t), ((t.is), 6(1) and ((t.i)) be defined as in Eq. (B.1). Then,
m The
m
0000 0/ ((e,)) + 11. S
a4
ve(O Zig.x) -(0( -
(1
03
m
k=1
Proof. Denote
1
1 =
E mx
-11
E R mm
(B.4)
m
13

---

Stability and Generalization Analysis of Decentralized SGD
It is clear that @ W By Eq. (B.2) and the standard inequality (a + 6)2 + 3)a² + (1+ + 1/3)6² for any
B 0, we know
|0(0 - @00) - ((..0)) + 1| F
= ||0(| - ((t-1) - 6(00 + ((t-1) - @(1.0) + ((--1,6) + (((.)) - 5 100 r = /|6(0) - -((11) - (1.15) + +0(1-1.5111
= ||We((-1) 1) - 7 Ve(6(( 2, 1) - + + (( 21 +)+ -( }
S (1 (L -(t- -6((111
;2,-11- - Ve(G)t-1..)) k ) | p ( ||= + (1 + | M |E( ;
where we have used ||0 - 6 p $ |0|| for all θ E nxd (Taheri and Thrampoulidis, 2023). For any θ E R=dd we know
www - 61 = (I - - و|1 - I|W - | - 6)
S max (x (W)H)e - 0)1 = A/| - 1)
(B.5)
where we have used the inequality that |W - 1 S then follows that
(Taberi and Thrampoulidis, 2023). It
(1) - @(1) - (+.65)) + 1( ||
$ (1+ (1+ (+-)),))) - (t-11) + ((--1.1)) | + +1+ 1
1
- - 2 )|(
3
+1+ (1++)>/10((-)) - = 61t-1.66 ||
1 2
ve(0 1) (1:--))) - e(0
-e(00=) 1,60), -((01 1/- 22
-
+ (1 +
Mi-
B
By the definition of ag and a4 in Eq. (B.3), we further get
||00- 600) (1+1))) + (t.1))) 2
F
m
I - (t-1.)))) - ((--1) + 111-1:101 F
a4th-11 Σ
ve(ok--)) ; (x) - 0(0(1-1.6); 2/th x 111
+
Applying this inequality repeatedly implies
1-1 2 Σ 013
m
||0 1 - - () + (((,))))
1|=
Ve +) Z1z=a)) v.) ve(0k=--6)) 7000 ,
S 0.
1/-
r=1
k=1
Since the step size sequence is non-increasing, i.e., 7/t+7 S T/,, we further get
1-1
m
g (/0² -((,))) + ((200)
2
047
2
Ve(ot 7771 +1)) - -E(ol- ((((t-T))) 3
pp- 2
03
1/1
m
2
m
k=
1100g
1
Ve(0l (TT)) Z - -(0(( (001)
#
1/
t=
k=1
m
ve(ol): -zz.,) - E(o((:)) : 1
ne+r Mi
ve(O(") Zig. - -((f(t)) :
IN
7 m
ve(O (t) Zrg.z) -((((:00) |0:0 11
7=1
t=0
m
04
VE(O(() Zig -(0(( .21g2111
(1 0z3 m
14

---

Stability and Generalization Analysis of Decentralized SGD
The proof is completed.
We first present a general stability bound with general step size. As we will see, Theorem 4.1 follows as direct corollary of Theorem B.4.
Theorem B.4 (Stability bound). Let Assumption 3.1 hold. Let A(S) and A(S(i)) be defined in Eq. (4.1). Let E(:: be
convex and smooth. For any 31 > 0, B2 2. assume the step size sequence satisfies
0432 (1 03)
(1 + 3:)(m - 1) )
2
71e +
m
T.
3
0
(B.6)
and
04432
1 +
1
2
1
1/p +
T/-
S 0.
(B.7)
(1 (1-ca a3)
L
B2
Then, we have
B[IA(S)) A(5
S m2n²
8
T-1
0x4
1/t
+
1 D1
mn
03
m
=1j11
1=0
16
VE(O ; =
E
(B.8)
1=0
Proof. We first temporarily fix i E [m].] E [m]] and control control||A((s)) - | A(S 112. Recall the notation in Eq. (B.1). According to the implementation of D-SGD, we know
(1+1)
T(()_ The
Ve(Ol Zig.a) and O(++,11) = -((.6))
VE(OL.
200)
It then follows that
1) m
m
110(++1) - g((+1.6)
1 = 11000 g(1.6))
Ve(0 Zrg.k) T
VE(OK
.Z(00
k
m
k=
m
||0(0)
1
ve(((() Zzg,x)
ve (11)) 2
m2
k
2n
(0(0)
gl..s)
: Zrg,x) v
(B.9)
m
Part 1: For the second term in Eq. (B.9), for any Bi > 0, we have
m
(E(OL"; Z)z,a) - - |( _
$ (1 + B1 Σ (VE(O Zig.a) Ve(0/1.0) : (1++ 1 | - -Ve(ouu5)) [//3T/ )12
(1+
3
kij
$ (1 + (m 1) Σ (VVE :Z.,) - 2 + (1+
1 >|]E{())) Zzg.) - - / 11 l|:
B
(B.10)
where the last step uses the
inequality.
Part 2: For the last term in Eq. (B.9), we first consider two cases to control
(Ø - g((,)))
ve(O()) Zn.x) ve(o( k)
15

---

Stability and Generalization Analysis of Decentralized SGD
if) = j and 1 i, then it is clear
(0 g(t.s)) ve(0f);2..) ;2.,) ve(o B.d)) -1(0() |1..0) ( (B.11)
(2) if (k= = j and 1 + i) or if 1: + j. then
(0 - ve(o(") Zrz,a) -Ve(0 {(()))
)) = (0 ol:001 ve(ol) :21,)) ve(ol(,0); :2(g2)
+ +(B()) g(0 - g(c,6) + + ve(Of)) Z1z,s) - ve(( [1 (B.12)
The convexity and L-smoothness imply that the gradients are co-coercive (Lemma B.2), namely,
(0 - 0f ,,)5,) vE(OE); - ve(O (2 2 L 1 - 2/
(B.13)
For any B2 0, we know
(B()) 8 20)--(te g((.)))) + o (((,,0) ve(o! Zrz Zrg,a) - ve(e( -
2 -11010) 000 g(.s)) of /( |1 |e( (1) ZIg,a) ve(O( [
12.
22 000 - 00 - g(1,6) + ((:25t _ 1
Ve(OR) ; (1z ve(o :
(B.14)
2
2
Plugging Eq. (B.13) and Eq. (B. into Eq. 12),,), we have, for (h: = j and 13 fi) or k #;
(g()) - git.i)) vE(O[") Z1(,a) ve(o((it) x(EDا)>
2 32 (00)) ((0) git. of.:))) 1/= 1
1
ve(e(-10) 1 2
(B.15)
2
232²
Then, we combine the results above to control
2m
m (0 g(t.i)) VE(O!": Zig.k) - -VE(O((6)) x2(110
m
(1) If 13 * i, by plugging in Eq. (B.15), we have
2mp
m
gatt
g(t.h))
Ve(el") Zrg,a) - Ve(O(ti5), Z(0)
m
32
m
|0000- 0( - g(.,)) 0(.5))) 1|2
2
1 2 m
Ve(O()) kzg,x) - -
2/220112 (B.16)
m
32
m
(2) If 13 = i, we know
2T
(0 - g((.1)) V Z1g.a) )
m
1=1
277
(00)) g(.,))) v((O))) Z1z,,) - ve(o((5)) -(,NN)
2Tk (g(0) glt-15) vero!o Z155) - velof(i)) )(,1))
m
m
kjj
2/h
( ((A)) v((O Z)g,,) - ve(o((:0); ((002)
+ 277 (())) - g(...0)|| V mn)) -e(00 2m01111
16

---

Stability and Generalization Analysis of Decentralized SGD
From Eq. (B.15), we know
27
(00)) - g(0.6))
V - ve(of ((()e))
k
(8(0) 0k²) g(t.s)) g 1| 112
(
2
1/2
VE(OE -1z,k) - ve(ok( 2/2
m
B2
m
k
B2/li
m
|0(0)
0 g(a,)) + 0 1|
2
VE(O( : - vE(O
m
32
m
Combining these two inequalities above, for the case when 13 = i, we have
27
(0 O(1.)))
vE(OR) Zrg.n) - vv(o0/tb0) (((0)((00022(())))
m
32
ggtt) 0% - g(+))) + 00..59112 11
(2
2
1
nk
vE(Ol) Zrg,t))
ve(ol
m
B2
ktj
2M
|000
g(+-10) |2 | = ve(oft.5);
(B.17)
m
Therefore, combining the cases when 13 # i and 1j = i, i.e. Eq. (B.16) and Eq. (B.17), we have
2T
( g(t-15)
ve(Ol"; Z1g,k) - -e(( (
m
32
(ftt) (0)0) - - + ((6b5)) 1
1
2
1 T
(0 Z1g.a)) ve(ofutt) 2//2211
m
B2
m
1=1
kjj
1
2
Th
[e(of - - |1300 |1
+
27 m
|1000 g(.
2/ (2
ve(0 Eass 2 Juy=
B2 m
(B.18)
where [1,3 denotes the indicator function, i.e., returning if the argument holds and otherwise. Iteration form: Plugging Eq. (B.10) and Eq. (B.18) into Eq. (B.9), we have
|10(+11) - -041160) < 11000 - 00..001
3211
(0(0]_
0
- 0((.)) + 0 112
m
k=1
(11 + 31)(m=
1)
'/22
(7,
2
1
Th
(V((0 -r(,a) ve(ol ; 2(16)
)) 12
m²
B2
m
+ (1+ + 1
(2
2
1
|E(O))) ; -1g.5) - VE(Of 21,0
31 m2
L
82 m
+ (1 +
1 T
(Ve(0)))
; - ve(oft:0) ( |3
31 m
2111
(0(1)
g(++1)
||2 V = ; ve(of و
(B.
m
17

---

Stability and Generalization Analysis of Decentralized SGD
By Lemma B.3, we get
T-1
1
(gtt_ - -00- - -0(..) + (((65)) 2
(1+31)(mm 1)
2
71
; ZIg.a) ve >/(
m2
L
32
m
|
(1+
1
2
7t
|e(Os) :1,,)) ve(o -
11
31
m2
L
B2
ml
04432
(1 + 31) -
ym (1) 12
( -1)b))²
(VE(O))) ; Zrg,a) - ve(o 2
03)
111-
m
32 Aif
043²
1 31
--11) ) /0(0
2
(1 21z,)) - vecoft:0): - 3133
11 +
1/e
T.
m
0z3)
m
m (1 (1-ax) am)
)
ve(O ; - 232013 Σ m
T-1
|E(O -1z,a) - [(gh) 11
(1 a3)m
where we have used Eq. (B.6) and Eq. (B.7) in the last inequality. Therefore, taking a summation for = 0,..., T to both sides of Eq. (B.19) and using Lemma B.3, we have
( - g(T.50)
0 Ni +
1
B1 oh
[VEE())) =1.)) - ve(of(.5); ). (T
1 az
21I:
((t))
g(c.3)
2
- - (
(B.20)
m
Taking expectation to both sides of Eq. (B.20) and using the fact that 1 is independent of g(t), @(e,2)) og9 and 8f4:50 we know
EI|@TT - 1
0132
1+ 3.
n (VE(O))) (2.)) - ve(of 2
nt=
+
mn
03
m
2m
g(t) - g(t.t)) ||| VE(o!o :2.5) - ve(og/ib) En.
E
(B.21)
mn
Introduce
A = (EI10(0-8810))
- g(c.60 12)) Vt E [T] and A
max A. 1sT
By the inequuza we know
s (1e [10000 (10100))))01))) (1. (E[IVE(0)) (F : -L)))-e((ff(.0 ;2,5) 11])* 7
E - 0(. 2[100006600)
(n.)) - 1
v
It then follows that
A
<
1 T-1
a432
1)1
+
1 31
m (]((((()))) (2,)) ve(oh::0); ;2,))) [|]
mn
a3
m
1=0
T-1
2
E
VE(O!" 24.) (2.))
ve(oft:0); 21,))13) A.
(B.22)
mn
18

---

Stability and Generalization Analysis of Decentralized SGD
According to Lemma B.I, this further shows
2
T
0x4.3
1/
+
1
1
$1
)
[[(((f))) ;
m2
03
4
1
E
-
2n 111)) )²²
(B.23)
m²n2
By the symmetry between žijj and E. we know
E B[IVE(0 ; - ve(of 2 S 2E |V ; = + 2 ve 2
4E
(B.24)
We combine the above two inequalities together, and get
T
a13²
1 1
B[|[A(5) 1(5 =
+
[1
;2 21.
mn t=0
az
m
16
velo = = $)² (B.25)
R
n
t=0
Taking an average over all E [n] and j [m], we get
((I)(S)) - A(S S
T
04
1 + 3.
ve(0 ; 11
1h +
m2n2
03
16
m
T
; =0)))(])
Ve(O5);
7t
m
n
The proof is completed.
Proof of Theorem 4.1. By choosing 3 = 1-A 2X
we know
Q1
1 1+ +
1+ 21
1-1
2(1
1
0g
1- (1 3)x
1 (1 2X
T 2
X)²
The stated bound then follows from Theorem B.4 by choosing 31 = 1 and B3 = L (note Eq. (B.6) and (B.7) hold if Eq. (4.2) holds).
Proof of Corollary 4.4. By the Cauchy-Schwarc Schwarz inequality, we know
T-1 Σ t
Mh E [
= =11)))
R [[ve()) =
(B.26)
By the elementary inequality (Lemma A.I), know
a² < 2(a b)2 28? the L-smoothness and self bounding property of the loss function &
VE(O 2n 12.))
21, < 2/| 22 24)) ; +
< 2213110/0 - g0)) -0) v
< 222110000 - /00) ALE(0(), 2..))
(B.27)
19

---

Stability and Generalization Analysis of Decentralized SGD
Plugging Eq. (B.26) and Eq. (B.27) into Theorem 4.1, we have
m B[|A(S)- 1(S(6))13)
1 T
Tiee
+
1
R
m
1000
B(0) 10]
77212
mn
(1 1)2
m
777
j=1
L
Lap
1
1 E
1
Σ
m
e(0(0) 21, }]
mn
(1
2)2
m
m
1=
x=1
1,2
1=
1/1
T-1
E
(1())
m²n²
1=0
j=1
1. 1
T-1
m
+
T/
{000 2z
(B.28)
m2n
mn
j=1
From Lemma B.5, we know
1-1
E
(0
000
[ =
1
-aalll - -
S a2L Σ aj
1 1 ()),
-=1
7=1
from which we know
T-1
Life
+ [
m Σ
(00) g00) 13]
))2
m
m
j=1
Lmp
1
1-1
+
m/
L
2
aj
-- ni
E ((s (((-))))
(1 X)2 m
L
1-1
T-1
Σ
Litt
+ m
1 ) t/e nh ( )]
(1- (1-
1=
+ 1 m) E ((
<
Σ
2)²
T-1
Lmptr + +1) m² E(
Σ
(1- m
T-1
Li):
+ +1
D E (((())
<02L]
Σ
(1 -x²
m
1=1
1=0
12L
T-1
Litt
+ m
(B.29)
1
01
(1 [1² A)2
[=0
In a similar way, we can show
E
Σ
10000 - | | <
0:2 L
T
n (s(
(B.30)
a1
j=1
t=0
20

---

Stability and Generalization Analysis of Decentralized SGD
Plugging Eq. (B.29), Eq. (B.30) into Eq. (B.28) and using the identity
Ei=1 Ej=1 ((010; Rs(00c)), we get
Li
1 m
El| A(S) ((5(0))
v
mn
212
1=
T-1
LT7e
) Rss(
mn
x)2
m
1=0
022 2
T-1
E (0(0))
(1 01) m
1=0
L 0
T-1 th
E B[Rs(0(0)]
m2n2
If it S
L-m, Teaz'
we know n/2222/(1 /(1 a1) & 1 and get
B[(A(5)) A(S(W))
L
T Lm
(1 - 2)2 m ) Rs( +
+
1,2 DtD 1/2 T-11
Σ
E Rs (((0))
m?n?
mn
j=1
t=
By choosing 3 =
L-d 2A
we know
a-a1
1- (1+ 1-(++
3- (1+ 2A + 1- m²
-1
L²aa2
(1
4T2(1 + )
1-1 + 2(1+2) Ri
+ nF (1+(++1 8L2(1+A)
A1-
(B.31)
2
1-X
The proof is completed.
B.2. Proof of Stability Bounds in Taheri and Thrampoulidis (2023)
According to Eq. (12) in the proof of Lemma 8 in Taheri and Thrampoulidis (2023) (with a = 1/2,c= = v2L), we know
1
E| @TT) - -
E
LT mnn
T-1
Σ t=
E (+())
+
L' T-1
|000) - 16(2)
mn
From Lemma 11 there, we know
11000 11) < Σ
T-1
|10(0 - 1
<T
ā2L7²2 m
T-1
E (0'))
1 ō1
0=
1=0
where a1 = +3+ 2)/4, d2 = 4(2/(1 - A) 1). Combining the above two inequalities gives
L T-1
E ( + à2L3n T-1
B ((1) ggraan
E [[Rs(((0)]
mn
m n
1 a
1=
L
1 T-1
E B[ss( [
Σ
E B[Rs(
mnn
(1 - X)2
where we have used the fact that
02
4( 2 - 1)
4(
-
1(+A))
1-A
16(1 + A) (1-
01
1
3+1
1-X
21

---

Stability and Generalization Analysis of Decentralized SGD
B.3. Proofs on Convergence Analysis
In this subsection, we study the convergence analysis of D-SGD, Our analysis is motivated by Taheri and Thrampoulidis (2023), who derived convergence rates for DGD. We adapt their analysis to D-SGD, which is computationally efficient for large-scale problems. Following the standard analysis of decentralized optimization, first present lemma to control the distance between local models and their average.
Lemma B.5. Assume the loss fimction ()) is L-smooth and Assumption 3.1 holds. Let ( and 6 be defined in Eq. (B.1). Assume that 0 are the same for different I [m]. Let on, 02 be defined in Eq. (B.3) with on 1. Then, there holds
BlIl@()) - 6(0)) S 02 Lm Σ aj a -i, BlRs (1)--)))
Proof. Recall Wo defined in Eq. (B.4). For any 3 > we have
||e(0) - ( ||0(0) - ((t-1) -( + 1 - [(((0) (1(
T/-1 V //,-1
- - (1)1))
(1 + ())(
- -
(1 + 3) M ;21-))-
(B.32)
where the first inequality holds due to 10 Q||F - | F for all e n (Taheri and Thrampoulidis, 2023), and the last inequality holds due to ||a + b < (1 + 3) |||| + (1+ 11102 For any 0 gmxd Eq. (B.5) shows that
| - 61% s el| - O1l... Applying this to Eq. (B.32), we know
(| - 1 // < (1 + (1+ - 1 + (1
1
(B.33)
By the L-smoothness of (() and the self-bounding property, we get
[V(((((-1);)) 2z I [V((@((-)) Zy. 1) V((6(--)) 2n 1) ((((0(-11) 12 Zp 1)11?
< 2| ;); - ve(0(t-);; )1ا + 2/ 2 ;
+ 4L m
s 22 11--1) -
1001-1); 211 le).
(B.34)
Taking expectation to both sides of Eq. (B.34), we have
E ( :2; < 21 ( |12]]
4LE
Rss (0(1-1)))
2L ( ()(-1) + 4.mE (0(1-1))]
(B.35)
where the first inequality holds due to the independence of (t--1) and T and we use the fact that Rs(-) = 1 Em Rs, for the last equality. Taking expectation to both sides of Eq. (B.33) and plugging Eq. (B.35) into it, we have
(.)
m
1 - < ((1 + 3) + 2(1 3 ) ( (1)
1(1 | + 4(1 + 3 L (0 )).
By the definition of a1, a2 in Eq. (B.3) and the assumption that the step size is nonincreasing, we further get
(I (t) a (9)) | < a ([ 6(1-"" 02 LmE||
(B.36)
Applying Eq. (B.36) repeatedly and using the assumption that 0000 are the same for I E [m]. we have
( (1 S az Lm Σ
T--1 a
2 mh S._,EER, (0
(B.37)
The proof is completed.
22

---

Stability and Generalization Analysis of Decentralized SGD
Proof of Theorem 4.6. Let O and 6 be defined in Eq. (B.1). Firstly, we develop bound for According to Lemma B.5, we know
(0) [|
T
Bl|l@( - 110) S
1zL
T t-1 ΣΣ
oi
[[R -
S
025 T
T-1
Σ Th B
mT
1=2 T=1
T=1
1=T+1
T-1
12
12l T
1/1
E Rs( -
n
[
T=1
-=1
02L
T-1
Σ
(0(0))
(B.38)
a1)7 )T
Secondly, for any 0 R², there holds
- -013 = -10000 1/c
m
: : =1g,e) - - 2
10
m
2
-10000 01 + vi ;zrg 11
12
21 21 (01))
1
m
Vi(o 1000iirgge =
0,
(B.39)
m
By the Cauchy- Schwar'S 's inequality, we know
ve(ol)) ()) ; krg.k) S 2
Ve(oR - -V =12,,)) 11: +2
ve(0(t) 2 21g.1/ 1/3
V Ve(Ok) ( - ve(oi)) 2
12
2
VE(O ; 2 m,
112
+
1
k=1
2L m
4L m
Σ
110%0 - g +
e(att) 25g.k)
m k=1
m
k=1
21.
4L m
||0(0) - 10
e(0()) 21g,
(B.40)
m
m
where the third inequality holds due to the L-smoothness of f(. 2) and the self-bounding property (Lemma A.1). Taking expectation to both sides of Eq. (B (B.40), we have
E
ve(0 (1) kgg.k)
2 S
2 21, B[|(@()) E ( +j++0 (LE())((())))
(B.41)
m
k=1
where we use the fact that Rs(.)) m
Et=l Rs (-). Note
(10) - 0, V ve(O (2thk)))
1
(00) 0, v (2)),)))
k=
k=1
1 m
m
g( ) V((0(.) :((,)(=11),)))) x2)1,a)
( 8, ve(0l)) 21I1a)
m
m kml
1 m
((010) >)g,1) e(089) =1.,k)
1 110
L
7 18
+ 1 m
m Σ
- E(0;; =12,))
2
m
1 m
((010) ;1g,a) e(; (10x2)
- - 110( 5l013)
-
(B.42)
m
23

---

Stability and Generalization Analysis of Decentralized SGD
where the third inequality holds due the L-smoothness and convexity of ((: Taking expectation on both sides of Eq. (B.42), have
E
000)
0,
ve( : [ [[[)( - [[)
L
El - ())
(B.43)
2m
Taking expectation to both sides of Eq. (B.39) and plugging Eq. (B.41) and Eq. (B.43) into it, we have
[[]
01
21.21 + Lm
S B[[ 0 +
E E
( |2 + (4Lm) - 2nh 2n.) + Bn,
2L 2 + Lm
=[[ 0 +
E Bi (0)) (En 2n, B(ss(
(0())
m
Taking summation of the above inequality gives
Σ EE R (010)
(0)
B(1 0133
2 + L
2L T
-69 +
E Rs (0(1))
2T/T
2mT
T
1=1
B[(1@0) - -111
T
2Lm
T Σ
- -
+
EE [[
2T/T
m.
T
t=1
t=1
B11 - -
21)2
Σ
T
(((s(((0)))
2Lm
Σ
E ([(s(((1))
2n/T"
01 )T
T
t=1
t=1
E[((@(1) - -
aggLin² (1- 01)
2Tm)
Σ
E
R (0 B[))(())()))))))))))))))))))))
(11 a1)
+ +2 R[Rs(())
2n/TT
where we have used the assumption that 17 5 1/(2L) for the first inequality and Eq. (B.38). By Eq. (B.31), we know
1- 01 (1-
oी z A)
A)2
L2a2 8L3(1+
Therefore, it follows from Eq. (4.11) that
12
812 + Airi
1
+ +
2Tm S
(B.44)
(1 01)
(1 - 2)2
We now consider two cases. [[)(] S ΣT E| Rs (((((((())) (o(t)), }}, then we combine the above discussions to derive that
B[(1((1) 01131
0021,172 E (Rs( Rs(0)) + (1- a1) + 2I.1 E (0)),
Σ E (((( Rs(0))
+
2n7T
2T
from which and Eq. (B.44) we get
E [(
01121
E (0(0) Rss()
2
(1- (1) 2Lm [[)
1/L'
E [(1) - 01131
(66L(11+ + X)n?
(1 X)2 + 4 (())
nT
(() > + ET_ ((())) the above inequality still holds. The proof completed.
24

---

Stability and Generalization Analysis of Decentralized SGD
B.4. Proofs on Excess Risk Analysis
In this subsection, we present the proof of Theorem 4.8 on excess risk bounds.
Proof of Theorem 4.8. By Lemma 3.5 and Eq. (4.5), we know
Es.s(R(A(S)) Rs(A(S)) & ! (E(R((00)) +
(I++)1
Lape
+ _ + [ Rs (010))
(1 (1-
mm
(L+ (L+ E 11=0 + n²n2
T
7
Σ
E
(Rs((()))
By noting that (0())) S + Et= Rs (o())) and choosing a constant step size 7)t = 77, this further implies
L (TT
+ +
7)) Ly
)n
(L+ 2)1
Es.4 (s.A(R(A(S)) Rs(A(S)))
+
E [
(B.45)
mn
m n2n
Eq. (4.12) and Eq. (4.11) imply that
110-13
Σ E [[ss( 2 R(00)
(B.46)
T
7/T
We combine Eq. (B.45) and Eq. (B.46) together, and derive
(R(((S() Rs(A(S)) & [((0)) + 10 L
( (1-12 by + nn
+ (L+ + 1)
(B.47)
TIT
m²n²
Plugging Eq. (B.47) and Eq. (4.12) into Eq. (3.1), we have
E[R(A(S)) - -((')) $ (R(0')+ + 10-112 11
(
L
T(L + +1) (1 + n)
(L + 12)
+
1/T
1711
m²n1
10
L2
(1 21- Ln ([(s(0*))
The proof is completed.
C. Proofs for Convex and Nonsmooth Problems
C.1. Proofs on Stability Analysis
In this subsection, we present the proof on the stability analysis of D-SGD for convex and nonsmooth problems. An useful inequality for our analysis is the Young's inequality
ab < p 1a + 1 1619,
L.D.R. 0 with p + -1 =
(C.1)
Proof of Theorem 5.1. Eq. (B.9) shows that
||0(c+1) g(+l.0) | = ||000 g(c.)))
W
m
(Ve(O - 2160))
m
2n
(0()
g(.)))
VE(0 Zig.x) -V((O -2(0))
(C.2)
m
25

---

Stability and Generalization Analysis of Decentralized SGD
Part 1: For the first term in Eq. (C.2), Eq. (B.10) shows that for any B1 >
[ ZIg,a) - , 12 - (1+ 8m) 1)
Σ
KØj
(1+ + 31
1
|| -Iz.,)
ve(ofu.0) 2 (C.3)
Part 2: For the last term in Eq. (C.2), we first consider two cases to control
(00) - g(c.i)) - ve(Ok) Z1g,a) - ;
(1) If j = and 13 = i, then it is clear
(BL0 g(t.s), ve(ef9: 2n,)= ve(ofon)); 2n,)) 2 -1100) g(c.3)) 2 ve(0f) : (C.4)
(2 If (k= = j and 1 + i) or if k + j. then
(00) - gum,,) v Z(g,x) ve(oltt), ((1gh) = (0()- - of vE(OE); Z(g,,) - ve(Of ./((a)
+ (0()) 0 g(.,))) + th (1)))) v((O() Zrg,a)) - Ve(O() ) (C.5)
The convexity and (a, H--Hölder continuity imply that the gradients are co-coercive (Lemma B.2), namely.
2L à I+a
(06- ve(ol Zrg.s) - -
;) )(n
|ie(o 2rgxx) - ve(ol 1 -
which further yields the following inequality for any b 0
| 2r - ve(O (1)); 1
1+a (0(") - 06 ((6b)) ve(ol" Z1g.a) - ( 2(11h)))
2L aa
LL(1 + a) (0()) - 0(.300 ve(o()) Z4p,k) - ve(O ((((((10):((1)))
h
20
ITe
2a
2(1-a]
1
2bmaa
T. (o!) o(.i))) Ve(olo) Zrg,,) Ve(O! -(00)
20 bi
I
bitt
1+
where we use Young's inequality with p = Ita 2n
and g = Ita for the last inequality above. Therefore, i-a
ve(o(t (0f)- -0 ((.,))) ; - (200)) z
by
| (1) Zmg,0~ ve(o 2/
1-a a (1+a)
+ L. (C.6)
I
For any B2 > O, we know
(B(0) g/ - g(t.))) + o((,)), ve(O!) -1ax)-
- ve(((())) -
-10000 00 ((.,)) 0f. (1,01) || |e(0 Zig,a) ve(O! -
32 1000000 o0 - -(w)) + 0f (1:)) }
1
ve(o -zg.,)) ve(ol 21000112
(C.7)
2
2B3
Plugging Eq. (C.6) and Eq. (C.7) into Eq. (C.5), we have, for (k- = and 13 + i) or k: j::
(0t)) - -(t,i)) ve(O (1) Zig,k) - ve(o( 1g.
2 2
32 000) 0/ g(.bs) + 112 + (7 2/2
bn 1
[[ - ve(e((15), 2((6)
112
1- a (by,)
It L.
I a
(C.8)
26

---

Stability and Generalization Analysis of Decentralized SGD
Then, we combine the results above to control
2m > - ve(O - - -Ve(O(:)) z
((..6))
(1) If 13 o i, by plugging in Eq. (C.8), we have
2T)
(g(t) - g(t.is),
ve(OR) Z1g.b)
Ve(O :
1g.k)) -
327h:
Σ
[0()) - -80 -g((.b))) + : |
2
m k=1
m k=1
-(
2bm
11
m
VE(O -11,,) - Ve(O x 1/22111 +
21(1 a)
11
(C.9)
A32
m
1+ a
(2) 1f 1 = i, we know
2T
(00) - ((..1)) ve(of); 2ig.aa - -Ve(o :2((,))
m
k=1
2T
(B(O) g(.,)) ve(E( 2ig,x) - ve(e((i0); -(((/)
21 (B()) g(..))) ve(0))) Z1g.)) - veloffit): {(t1)
m
m
21T
(B()) g(.3)) VE(Bl Zrg,e) - Ve(Ok -}(pa)
27 g(t)) - go..5) 11 |E(O : m4.)) - ve(of(ib) : 222
+
m
m
k
From Eq. (C.8), we know
27/
Σ (7()) - g(0,))) ve(0!"); (xg.e)
3277
m
|00(0 0.00 (000-(0a ((0,)) + 0l(.55) |
m
m
2
kgj
2bm
1
M
VE(O (0 ; Zig,k) - ve(ok ,
2 + 2L(1 - a)
1+a -
bi
1- 7/6
L
B2
1 a
køj
Combining these two inequalities above, for the case when 1j- = i, we have
2n
m
(0(+) g(t.)f) VE(O Zig.a)
ve(0((.5);
-112121
m
327
(0()) 0 ( + 112 (
2bme
1 TJ
VE(OL) Zrg.k) ve(ofti0)
m
T,
B2
m
kzj
2n
| - ((t.5))
|| [E((0)) (2,)) - (((o0(.01:;2,,))]
2L(1
a)
bia
1-a
-
(C.10)
1 a
Therefore, combining the cases when 13 # i and 13 i, i.e., Eq. (C.9) and Eq. (C.10), we have
277
m
(00) ((11))) ve(O Zgg,k) -Ve(o(i55) [
m
3211
(0(10 0/0 - ((.,)) + 16 (
2bTr
1
11t
- - -
m
L
B2
1=1
2m
1 T
VE(O (1.55) ve(o - || 113211
L
32 m
+
21h
|0000 g(t.3))
|| | ( - ve(o)t ; ر |1 T1
2L a) a) 1+a
b
1/
1-c
(C.11)
27

---

Stability and Generalization Analysis of Decentralized SGD
Iteration form: Plugging Eq. (C.3) and Eq. (C.11) into Eq.(C.2), we have
[ - -0(t1,00) - 110(0 - 03 +
3271
|0(t))
0% -
-o(t.15) + + 1/
+ (1 + 3:)(m - 1)
1/2
2
2b1
1
21
(VEE0
16 (,; 2rz,a) V {
)) 1
m12
L
B2
m
Ref
+ (11 + B1 m
2bT
|e(0 :0 : :Zzza)
- -Ve(o - -13 11
T,
B2
m
(Ve(0)) ;.ي) - ve(ofu.00 ;(n))) 11 11y=1 + 21(1 a) 1 مo
+ (1 + 31 m2
+
+ m
2
||000] g(c.))) |1 [e(00( (20)) - ve(Oft.01 3.d -
(C.12)
By Lemma B.3, we get
32 |00)) -0(0) - - + +00 - 1
(1+ 31)(m= - 1)
'12
2b1
1 1 2
Σ
(VE(O))) (Tz.x) - ve(ofl.0), -((0))
-/(,)))11 12
m²
L
32 m
(1+ + 1 r/
20m
1 1t
Ve(0g)) :Z1g,) ve(ol1.0) (12
B1 3mm
m²
L
32 m
T/
04,32
(1 + 31) -1) 1) 1/1 - (
2bm 1
Σ
||
(VE(O -Ig,x) - ve(ol(i5) 2000 2/22))112
1/p +
m
(1 - az)
m
B2
Th
31
1 D1
1
-
2bmT
1 [VE(0 :13,))
-ve(ol -1333) (5
m
(1 03)
111
m
1/-
L
3r
n 1/a13211133
| - -ve(0 : 2113)11
(1 - mm)
n LTl (1-=
| ; 213a0 - ve(oft:5); 12
03) )bm
where we choose B1 = 11,32 L/me),, and b
anb 1-03
+ 2L to use (b 2 L)
0,482
(1 + B1)(m - 1) )n (
2b1
1
) =
asL
2(m 1im-11 1)
b
7) +
I n
(1 ax3)
m
L
32
b(1 a.s)
m
agL + 22
04
T-ag
+
1/:
1
03
L
and similarly
04.32
1+ 1
Br
2b1Je
1
1/ +
11 -
<
1 1-03
m
L
3r
28

---

Stability and Generalization Analysis of Decentralized SGD
Therefore, taking a summation for L =0,.... ..,.... T - to both sides of Eq. (C.12) and using Lemma B.3, we have
||0()) - 0(
12
T-1
a4L
+ 2 o
(Ve(0f))))) - -
(1 0z3)
1=
T-
21
(0()) - g(.,3)) 1 ; =و) : + 2L - a
1e
b
1/1
1+a
1=
(C.13)
Taking expectation to both sides of Eq. (C.13) and use the fact that 1j independent of (10) 0(r.6)) o35) and of we know
T-1 1
g(t.65)
+ 2 1 (VE(O)) 24.)) - ve(o 8, [|
mn
(1 0g)b
m
24
[ g(e.s)) 2 ; - v f.. + 21 - a)
T-1
Σ
b m
(C.14)
mn
1+a
t=
Introduce
A. = (ElI -
(10.)11))))) $ vt E [T).
and
max A. SST
By the Suunhy--cwwarzzeeequea inequality, we know
E [| pt1.0) la ve(0) 111 $
& :2)) )(n)) 112)
(2:)
then follows that
2
a1L
2 _ [V
;2:)) ve(of(:00) ((,)))1
77171
(1
0z)b
m
[=
2
T-1
(i(e(((( (2)) v ;
2 1 A+ 2L(1 a)
T-1
140
-2
M
61-0 17
(C.15)
Mn
1+a
t=0
1=0
According to Lemma B. this further shows
A
T4T
+ _ | -v/(0()) 21,5) [1
veloft:0)
TIN
(1 aa)b
t=0
T-1
4L(1 a)
T-1 -
Me
b
17
(C.16)
2 2
1+a 1=0
Eq. (B.24) shows
E
VE(ef") 2.1) (z,))
( S 4E (VVE((()) : 11.)
We combine the above two inequalities together, and get
B|||A(S)- 1
8
agL
+
2 10
21.
mn
03)b
t=0
16
T-1
Σ n/
(B
: =1))) +
4L(1 a)
T-1 2
Σ
b b
m (C.17)
n2 2
1ta a
29

---

Stability and Generalization Analysis of Decentralized SGD
Taking average all E [n] and j [m], get
04L
[[]] A(S
)1
S
n2
0z3lb
= =11))11) + 4L - a) T-1
16
B
1 Σ
m
n
j=1
tm0
By choosing =
1-1
we know
0K4
1 8-1
1+
--
21
03
- (1+
1 (1
1-1
11
and further get
B[[A(())
A(S
<
2(1+ A) ンjab
211+
+ [E
m2n2
j1j=1
V 2 011)) +
4L - a)
T-1
E
Σ
6i-a 1
mr n
1+0
Furthermore, we know
a1L
2L(1 + A)
+ 2
(1 - A}² 2L.
1 03
The proof is completed.
Proof of Corollary 5.2. From the G-Lipschitz continuity of the loss function ((:=)) (Definition 3.4), we know
[V(0,2) ve(0", < |]v + (V - 2G, 00,0' E R
i.e., the loss function has (0, (Hölder continuous gradients (Definition 3.3). Then, by choosing 0 Theorem 5.1, know
E[IA(S))
A(S 1
<
2G +
n
t=0
16
T
E
VE(O
2 M1))
T-1 8Gb
Σ
2
(C.18)
m
t=0
1=0
From the G-Lipschitz continuity of the loss function {(: z) (Definition 3.4), we know
(VE(0,2)ll S G, 4I E FR..2e Z.
Plugging this into Eq. (C.18) and noting b 4(1+AGG (1-X)=
4G give the stated bound.
C.2. Proofs on Convergence Analysis
For the convergence analysis, we require the following two lemmas on functions with Hölder continuous gradients. Lemma C.1 shows the self- bounding property. while Lemma C.2 presents a bound on the first-order approximation for functions with Hölder continuous gradients.
30

---

Stability and Generalization Analysis of Decentralized SGD
Lemma C.I (Lei and Ying 2020). Assume the loss function 2(32) is nonnegative and has (a, Ly-Hölder continuous gradients with [0, 1. Then,
[e((,, 2))2 S ca.1erfa J 2.
where Ca is defined as
(1 (1+1/a)
fa>0
Ca.1
sup, Ve((: 2)112 + L,
i.a
Lemma C.2 (Nesterov 2015). Suppose f has (a, -Hööler continuous gradients over given convex set D, where [0, 1). Then for any y E D,
L f(y) S f(x) (Vf(x). x) + a + ly- x|(*t1
Proof of Lemma 5.4. Let (+) and ( be defined in Eq. (B.1). For any Rd, there holds
[10(++1) -013 = | l/} m
-10(() 012 1
m
ve
ve 3 2 w) 1|
21j 2m (0l))
0,,
1 m
vi(0 1 (....)).
(C.19)
m
By the Cauchy-Schwand inequality, we know
ve(0())
())
2
1
ve(0k):215.41
ve(0
2 x.)x
11 +
1 Σ
ve(
21 ||
771
VE(O =1
ve(
21z
+
2
VE(BCO
272 2,2,1111
k=
2L
202
10000 8 +
(B(0) ; 2).2))
aatl
m
m
k=1
k=1
2L2 ||0
2
m
1/
(f(t)) zrg,k)
(C.20)
m
m
where the second inequality holds due the (a, L)-Hölder continuity of V((,,)) and the self-bounding property (Lemma C.I), and the last inequality holds due to the concavity of x + x
172
20
110
g(0)
(C.21)
m
m
Taking expectation to both sides of Eq. (C.20), and using the fact that
E
(8())
2Tg.K)
E
1
(((t)) 2
2n 2x(,,)]]
(E(Rs(0(!)))) .t1
m
m
we have
m
2L
E
- [33] 2 (E(Rs(((0)))
(C.22)
ma
31

---

Stability and Generalization Analysis of Decentralized SGD
Since
0 m
1
(0)
2)g.k)
((t)) 0, V
21g,b))
(00) 00 Ve(0
(1) (5rg,))
1
0/ 0, ;=(.,)=(1++))))))
k=1
L
[(010) (11,,a -((0%) (211,))
100
-
; E(0; E(0; 21g,k))
+ 1
k=
E(71; 1 21g,k) ((0:211..)
L
|10g)
g(t)
12 )
(C.23)
a +
where the third inequality holds due to the (a, L)- -ölder continuity (Lemma C.2) and convexity. Taking expectation on both sides of Eq. (C.23), we have
E
(000
m
(0) ; ] [[]
L (a + 1)m
E||@( -00))
(C.24)
m
where we have used the following inequality since a E [0, 1] (i.e., if S q, then ||a||, 2 ||a|| for a IT")
m
m
10 1 00)13) _ |0000 (l.
Σ
000) 010112+1)
Taking expectation to both sides of Eq. (C.19) and plugging Eq. (C.22) and Eq. (C.24) into it, have
2 E[|l@(
2 E|| 6(011t
E Bl 01131 < Ell|@(0 0|2)
( [
ma
(a + 1)m
202 th (E R& (1))
पी + (ss() Rs())
Taking a summation of the above inequality gives
T
E 01 01
L'n
T
E ((()) Rs(()]
Bl|[@(() - 1
2//T
T
1=1
L
Bl|le(() - ((0)) 1011111111
| 22111
E (E(R)((0))) 2.
(a 1)ml
The proof is completed.
The following lemma presents a bound on the distance between the D-SGD iterates around their mean over the nodes.
Lemma C.3. Assume the loss function f(:; 2) has (a, Hö-Her continuous gradients and Assumption 3.1 holds. Let (1) and ( be defined in Eq. (B.1). For any x E (0, 1}. and R, we choose tp such that
Go == (1+ + + ol1 (l--a) <1,
then
+ 1 1) m²
(1) - 600 < (2ch,
a nh (E(Rs 1
1=1
[-1
+ (1- (1-a)(2(11 + m
=(1aaa) Σ
(C.25)
r=1
32

---

Stability and Generalization Analysis of Decentralized SGD
Proof. Recall 8o defined in Eq. (B.4). For any 0 < x < 1 and 8 > 0, we have
||0(0) - 100 ||6(0 - G((-)) - - + || = || - 11
= -| V بب 1) - 12
< ((L ((1+ =)] 60-1) || + (1 + 1
/ nm / 3z. 1)1B²a x
$ (1+ + (1+ ( - 1| (1 + 1/3) V1 ; 11
(C.26)
where the first inequality holds due to - | = |0|| for all θ E Rmd (Taheri and Thrampoulidis, 2023), the second inequality holds due to ||a + b1l2 < (1 + () ||a| + (1 + }) and the last inequality holds due to the fact that for any
ai > O, 02 > O, and x E (0,
(a1 + 02)² )0 2 af + azz
For any θ E Raxd Eq. (B.5) shows that ||W - -17 - e|| 012- Therefore,
|W - 01 S X x=11e - 61.
Applying this to Eq. (C.26), we know
V2(( || e F S (1 3)- - ./ - +11 + 1 I)...
(C.27)
By the (a, Hölder continuity of v and the self-bounding property in Lemma C.1, we get
(V((0((11);))) >) =
- () 1)) - (7((0((-))2)111) -
; -
+ 2 2
< 21
100 - 0/ 1/'
1 + 2 |1( z 1
k=1
< 100m)-)10((-1-000))) + 2:
lati (ō 1) 1
k=1
where we have used Eq. (C.21). Therefore.
(2(00(=):22-1)) = ;2)7(()(0))2111)))))
m
6/1-11 < ( -10-0-1- 12:00 +
(2ca.1 Σ f (0ll-)) :z
(C.28)
Due to the concavity of y - y fu the independence of ()--1) and 1/ and the fact that Rs(.)) m
1 Ex Rs. (-), we
know
m
m
E
20 (
- 1),
x E
gl
1) 2 1 1,x)
m
m R=
m = =(B1
- = (B (R>(((<))))))) aM
E m
R.s. (alt-1))
by using which we get
m
m
E
(01-11); 1
: ,,))²² S (B| [
- (0( x)))
k=
m
m
E
ب (|--1);
و - x1)) S m² (E[Rss (7 aFf
m
33

---

Stability and Generalization Analysis of Decentralized SGD
where the concavity of + y² for the first inequality above. Therefore, taking expectation both sides of Eq. (C.28),
have
B [ (2L'm' "B[l[((-))) (2[ (|(-))
+ (2c2.) "mmmm"""" (E) (E|Rs ( (0))
(C.29)
Taking expectation to both sides of Eq. (C.27) and plugging Eq. (C.29) into it, we have
B(Il@( - |
(2(1 3) )) m m= 20 -i ([16((((1)) - (((11) 20
+ (2e (1 + )) m m (E|Rs( (0(r )1)
+
(C.30)
By Young's 's inequality (i.e., Eq. (C.1)) with = a and 1-a" we know for any a E IR,
22 =(]0(()( 1) v (nk 1ili -((-1) n
ank 11 ( + (1 n-11
22-00
Therefore,
- - S ((1 (|+
1 ) 3n'm* n" (E(Rs(00))))1 (2 (1
2uz
(1- + 1/3)
h--1
(C.31)
By our definition of aa we know
m (1 B) a + m==- 1 S aa,z <
Plugging this into Eq. (C.31), we get
[i](@()) - 1010 I a -
(1--1) 3)mm
22 (1 + 3))² m2 पr (B(Rs(((t-()))
+(1 +11-))2(1+1/8)3) (0)) 28-ao
n (C.32)
Applying Eq. (C.32) repeatedly gives
( - 1 < (2c², (1 + 1 1) m
2x 0 Th --
(E(Rs(0((-T))) 201
+ (1 (2 + 1 3 123 m
m
a 1/!
r-1
The proof is completed.
Now, we are ready to present the proof of Theorem 5.5 on convergence of D-SGD for convex and nonsmooth problems.
Proof of Theorem 5.5. From Lemma 5.4, choosing
0, we know for any 0 Rd
1 ())) Rs R0)
(())
011
(I2 + 20
L
Σ
Ell0 -
[[]]
(C.33)
T
2n/T
mT
From the G-Lipschitz continuity of the loss function ((:22 (Definition 3.4). we know
[V)(0==)- ve(0', =1)02 = ([Ve(0,)) =) =2) S 2G, 00,0' Rd
34

---

Stability and Generalization Analysis of Decentralized SGD
i.e., the loss function has (0, --rrer continuous gradients (Definition 3.3). Then, from Lemma C.3. by choosing o 0.
1/2, and I. = 2G there and noting that CO,1 I 3G, then there holds
Gm
0 M +
m
0 7/t-r
4
= 5522m1++1100
(C.34)
Plugging Eq. (C.34) into Eq. (C.33) and choosing a constant step size 7/: - 1, we have
r
E ( - Rs(()) v B[ll0() - 013
+ 133 n + 10 + 1/3) G2
T 1-1
Σ
1 00
7/-
T
2n/T
mT
B1 013
10 11/))
+ 13G +
2//T
(1 - 0 )m
where we use the following fact for the second inequality above
T
T-r
T-1
T-1
ΣΣ r=
0 T/1 - S
0.
S
0
Th
t=1
[=1
Furthermore, we know 3 (1 + 33. The proof is completed.
C.3. Proofs on Excess Risk Analysis
Proof of Theorem 5.6. By Lemma 3.5 and Jensen's 's inequality, we know
G
m
(ssA(R((((S) - Rs(A(S))
E S S. - A(S))la
mn
E s B All - A(S)1a) 1/2
<
(C.35)
Plugging Eq. (5.2) into Eq. (C.35), by choosing a constant step size Mi- = 17. we know
1²12
1J²
$
[ [EsA(((A(SS) Rss (A(S))) G2
(C.36)
n2n2
(1- (1-
Plugging Eq. (C.36) and Eq. (5.4) into Eq. (3.1), we have
T2
T
|
(1 (1+1/B)+O2
E[R(A())) - R(00) x G2
m2
+
(1 - 2)2
+
T/T
+ G2
1 +
(1 (1 )/
By choosing 3 =
1-1 2x
we know
(1+
(1 (1+1/
Vē(1 + +A)#
1 (1 + B3) 1 (1+ +
(1- x)- (V2 (1+A)1)
v2(1 (V2
1
<
(1 (2
(1 11
Therefore,
E[R(A(S))] - R(O0) & GTT GnTT
101
G
+ 1-
+ G +
mn
n/
(1 X) 2)
The proof is completed.
35


Reviews:
[{"review_id": "oWVtFhFLDU", "reviewer": "Reviewer_f9L5", "summary": "This paper presents the generalization and excess risk analysis for decentralized stochastic gradient descent (D-SGD) on smooth (including Hölder continuous, which generalizes smoothness) and convex problems. The key contribution is the removal of the standard Lipschitzness assumption in the analysis. The authors derive generalization bounds under the relaxed condition and compare them with existing results. The paper is well-written, with clear notations and explicit order analysis of the derived bounds.\n\n## update after rebuttal\nNo remaining concerns.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.\n\n**Q1**: Exploring nonconvex settings could further enhance the practical relevance of the results.\n\n**A**: Thanks for the suggestion. We agree that generalization analysis for nonconvex problems is interesting for understanding the practical performance of decentralized SGD. We will explore this direction in our future studies. For example, it is interesting to study the stability and generalization analysis of decentralized algorithms for training overparameterized neural networks, where we can exploit some weak-convexity [2, 3] and self-bounding weak-convexity [4, 5] to develop meaningful stability bounds.\n\n**Q2**: The paper only analyzes the generalization of the average iterate but does not study local iterates.\n\n**A**:  We consider the average of iterates since most of the existing convergence analyses focus on the average of iterates [6, 7, 8]. Then, we can combine our generalization analysis and existing convergence analyses to derive excess risk bounds. We note that the recent work [9] gave interesting discussions on the stability analysis for local iterates. Their studies consider the $\\ell_1$-version of on-average model stability. It is interesting to apply our techniques to study the $\\ell_2$-version of on-average model stability for local iterates. We will consider this in our future studies.\n\n**Q3**: Theorem 4.1 imposes a G-Lipschitz condition and establishes the bound $\\frac{G^2 \\eta^2}{m n}\\left(\\frac{T}{m}+\\frac{T^2}{m n}\\right)$. The authors state that this matches the serial case $\\frac{G^2 \\eta^2}{n}\\left(T+\\frac{T^2}{n}\\right)$. Notably, this bound implies that increasing the number of agents/nodes $(m)$ enhances generalization, as the first term in the parentheses decreases with larger $m$. The authors could explain more about this effect.\n\n**A**: Note that each agent has $n$ examples in our setting, and therefore we have $mn$ examples in total. Then, the effect of perturbing a single example diminishes as $m$ increases, which implies improved stability. We will add discussions to explain this more clearly.\n\n**Q4**: The authors could consider mentioning \"non-Lipschitz\" in the title to better highlight the key contribution of the paper. In Theorem 4.1 (Stability bound), there is an extra space after \"Stability bound.\"\n\n**A**: Thanks for your valuable suggestions. We will add \"non-Lipschitz\" in the title and fix this formatting issue in the revision.\n\n**Q5**: In Theorem 4.1, the assumption $\\left(\\frac{2(1+\\lambda) L \\eta_t}{(1-\\lambda)^2}+2\\right) \\eta_t-\\frac{1}{L} \\leq 0$ is not carefully analyzed. The authors state that it holds when $\\eta_t \\lesssim \\frac{(1-\\lambda)}{L}$. However, in a ring topology with a large number of nodes (where $\\lambda$ is close to 1), this assumption seems difficult to satisfy. This contradicts empirical results, such as Figure 1 (right) in [1], where experiments suggest that larger node sizes in a ring topology actually allow for a larger learning rate.\n\n**A**: Thanks for your intuitive comment on the learning rate. We note that the assumption $\\eta_t\\lesssim (1-\\lambda)/L$ is also used in both the existing convergence analysis [6] and stability analysis [8] of decentralized algorithms. Indeed, the estimation of consensus error often leads to a term $1/(1-\\lambda)$, which becomes infinite if $\\lambda$ is close to $1$. Furthermore, in Remark 9 we set $\\eta_t\\asymp 1/\\sqrt{T}$ and $T\\asymp mn$ to get risk bounds of order $1/\\sqrt{mn}$. Then, the assumption $\\eta_t\\lesssim (1-\\lambda)/L$ roughly becomes $1/\\sqrt{mn}\\lesssim (1-\\lambda)/L$, which is a mild assumption if $n$ is large. While $1-\\lambda$ becomes smaller as $m$ increases, our suggested step size $\\eta_t\\asymp 1/\\sqrt{mn}$ also decreases with $m$. It is very interesting to further relax the requirement $\\eta_t\\lesssim (1-\\lambda)/L$. We will leave this as an interesting question for further investigation.\n\n[1] Beyond spectral gap: The role of the topology in decentralized learning. NeurIPS, 2022.\n\n[2] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. NeurIPS, 2021.\n\n[3] Generalization guarantees of gradient descent for shallow neural networks. Neural Computation, 2024.\n\n[4] Sharper guarantees for learning neural network classifiers with gradient methods. arXiv preprint, 2024.\n\n[5] On the optimization and generalization of multi-head attention. TMLR, 2024.\n\n[6] Graph-dependent implicit regularisation for distributed stochastic subgradient descent. JMLR, 2020.\n\n[7] Stability and generalization of decentralized stochastic gradient descent. AAAI, 2021.\n\n[8] On generalization of decentralized learning with separable data. AISTATS, 2023.\n\n[9] Improved stability and generalization guarantees of the decentralized sgd algorithm. ICML, 2024.", "claims_and_evidence": "The main claims of the paper are well-supported by theoretical derivations. The generalization bounds for D-SGD under non-Lipschitz assumptions are derived and compared with prior work.", "methods_and_evaluation_criteria": "The comparison with existing results is reasonable. No experiments provided.", "theoretical_claims": "The reviewer checked the theoretical claims but did not check the proof carefully.", "experimental_designs_or_analyses": "No experiments provided.", "relation_to_broader_scientific_literature": "The discussion of related work the comparison with prior literature is through.", "essential_references_not_discussed": "No essential references not discussed.", "other_strengths_and_weaknesses": "**Weaknesses**: \nThe study focuses on **convex problems**, which provides valuable theoretical insights. However, exploring nonconvex settings could further enhance the practical relevance of the results. Additionally, the paper only analyzes the generalization of the average iterate but does not study local iterates.", "other_comments_or_suggestions": "Theorem 4.1 imposes a G-Lipschitz condition and establishes the bound\n$\\frac{G^2 \\eta^2}{m n} \\left(\\frac{T}{m} + \\frac{T^2}{m n}\\right)$.\nThe authors state that this matches the serial case\n$\\frac{G^2 \\eta^2}{n} \\left(T + \\frac{T^2}{n}\\right)$.\nNotably, this bound implies that increasing the number of agents/nodes ($m$) enhances generalization, as the first term in the parentheses decreases with larger $m$. The authors could provide a more detailed explanation and analysis of this effect.\n\nThe authors could consider mentioning \"non-Lipschitz\" in the title to better highlight the key contribution of the paper.\n\nIn Theorem 4.1 (Stability bound), there is an extra space after \"Stability bound.\"", "questions_for_authors": "In Theorem 4.1, the assumption  \n   $\\left(\\frac{2(1+\\lambda) L \\eta_t}{(1-\\lambda)^2} + 2\\right) \\eta_t - \\frac{1}{L} \\leq 0$  \n   is not carefully analyzed. The authors state that it holds when  \n   $\\eta_t \\lesssim \\frac{(1-\\lambda)}{L}$.  \n   However, in a ring topology with a large number of nodes (where $\\lambda$ is close to 1), this assumption seems difficult to satisfy. This contradicts empirical results, such as Figure 1 (right) in [1], where experiments suggest that larger node sizes in a ring topology actually allow for a larger learning rate. \n\n[1] Beyond spectral gap: The role of the topology in decentralized learning. NeurIPS, 2022.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hFK6qMwr8X", "reviewer": "Reviewer_5LWF", "summary": "This paper studies the stability of D-SGD, and presents new and sharper convergence bounds on the assumption that the functions are convex and L-smooth. The removal of the function Lipschitzness and the bounded variance assumptions highlight the novelty of the work. Theoretical analysis shows an improved stability bound compared to Zhu et al. under similar conditions. In addition, the theoretical results this paper offers also interpolated many known tight bounds under certain conditions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.\n\n**Q1**: The theoretical claims are mostly to be expected and seem to be either an extension of previous D-SGD analysis or from the stability/generalization of SGD in the centralized setting.\n\n**A**: We highlight our novelty as follows. As compared to SGD in the centralized setting, the analysis of decentralized SGD is more challenging as this introduces the neighboring consensus error $\\mathbb{E}[\\\\|\\bar{\\theta}^{(t)}-\\theta_k^{(t)}-\\bar{\\theta}^{(t,i,j)}+\\theta_k^{(t,ij)}\\\\|^2]$. The existing analysis of neighboring consensus error is a bit crude since it directly decompose it into two consensus errors $\\mathbb{E}[\\\\|\\bar{\\theta}^{(t)}-\\theta_k^{(t)}\\\\|^2]$ and $\\mathbb{E}[\\\\|\\bar{\\theta}^{(t,i,j)}-\\theta_k^{(t,ij)}\\\\|^2]$ [1, 2], which ignores the important property that $\\theta_k^{(t)}$ and $\\theta_k^{(t,ij)}$ are produced based on two neighboring datasets and should be close. A novelty of our analysis is to show that the neighboring consensus error can be offset by using the co-coercivity of a gradient map, which is achieved via a new error decomposition. In this way, we improve the stability analysis of decentralized algorithms [2,3]. Please see Remark 4.3 for the novelty of our analysis. Our stability analysis also improves the existing analysis by removing the Lipschitzness condition [1, 3], removing the Gaussian weight difference assumption [4], and removing the bounded variance assumption [5]. We also remove some terms  $G\\eta T/(1-\\lambda)$ and $\\lambda$ in [3] and [4], respectively. Finally, our analysis shows the benefit of optimization in improving the stability, and gives the first fast rates of order $1/(mn)$ for decentralized SGD under a low-noise condition. \n\n**Q2**: However, I have some questions on the inequality shown on the left hand side of line 226, the consensus error is upper bounded by a norm of difference between $\\nabla l$ and $l$. This seems to be a typo since $l$ denotes a scalar loss function.\n\n**A**: Thanks for indicating it. This should be the difference of two $\\nabla$. We will revise these typos in the revision.\n\n**Q3**: Misspelling of \"related\" on line 60.\n\n**A**: Thanks for indicating it. We will modify it in the revision.\n\n[1] Graph-dependent implicit regularisation for distributed stochastic subgradient descent. JMLR, 2020.\n\n[2] On generalization of decentralized learning with separable data. AISTATS, 2023.\n\n[3] Stability and generalization of decentralized stochastic gradient descent. AAAI, 2021.\n\n[4] Topology-aware generalization of decentralized sgd. ICML, 2022.\n\n[5] Improved stability and generalization guarantees of the decentralized sgd algorithm. ICML, 2024.", "claims_and_evidence": "The major contribution of this paper is theoretical, please see Theoretical Claims.", "methods_and_evaluation_criteria": "There are no numerical evaluations in this paper. The author provided a good comparison of the stability bounds of related literature in Table 1.", "theoretical_claims": "The theoretical claims are mostly to be expected and seem to be either an extension of previous D-SGD analysis or from the stability/generalization of SGD in the centralized setting. \n\nThe authors were able to highlight the novelty of this work in Remark 4.3. However, I have some questions on the inequality shown on the left hand side of line 226, the consensus error is upper bounded by a norm of difference between $\\nabla l$ and $l$. This seems to be a typo since $l$ denotes a scalar loss function.", "experimental_designs_or_analyses": "There are no experiments provided in this paper.\n\nThe analysis seems straightforward and the authors were able to highlight the difference in analysis compared to prior works.", "relation_to_broader_scientific_literature": "The author provided a comparison of the stability bounds of related literature in Table 1. Although the comparison is far from complete, it was able to highlight the comparison of the current paper with some closely related papers.", "essential_references_not_discussed": "I am not very familiar with the related literature. There are no more related works that should be referenced to the best of my knowledge.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "misspelling of \"related\" on line 60.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JoWRrNRH5J", "reviewer": "Reviewer_PhLr", "summary": "This work studies decentralized stochastic gradient descent where a network of agents collaborate to minimize an aggregate of local cost functions privately available to each agent. It focuses on the generalization analysis, which is different from the convergence rate analysis. It improves the generalization analysis compared to previous works under more general settings such as removing the Lipschitzness assumption and also considering nonsmooth settings. It also provides optimal generalization bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.\n\n**Q1**: Lack of clarity in presenting the problem and results. Notation is quite confusing.\n\n**A**: Thanks for your valuable feedback. We will reorganize the problem statement more clearly, systematically sort out the notations and present our results in a more readable way.\n\n**Q2**: The analysis applies to convex setting.\n\n**A**: Thanks for the suggestion. We agree that generalization analysis for nonconvex problems is interesting for understanding the practical performance of decentralized SGD. We will explore this direction in our future work. For example, it is interesting to study the stability and generalization analysis of decentralized algorithms for training overparameterized neural networks, where we can exploit some weak-convexity [2, 3] and self-bounding weak convexity [4, 5] to develop meaningful stability bounds.\n\n**Q3**: Explain novelty and how you provided tighter bounds with less assumption.\n\n**A**: We highlight our novelty here. First, we remove the Lipschitzness assumptions used in [1, 6] and replace the uniform gradient bound by function value via the self-bounding property, i.e., $\\lVert \\ell(\\theta, z) \\rVert_2^2 \\leq 2 L \\ell(\\theta, z)$. In this way, we build stability bounds involving training errors, which shows the benefit of optimization in stability and implies fast rates under low noise conditions. Second, instead of decomposing the neighboring consensus error $\\mathbb{E}[\\lVert \\bar{\\theta}^{(t)}-\\theta_k^{(t)}-\\bar{\\theta}^{(t, i j)}+\\theta_k^{(t, i j)}\\rVert_2^2]$ into two consensus errors as in [6, 7], we show that it can be offset using the co-coercivity of functions, which improves the stability analysis.\n\n**Q4**: Discuss Table 1 in detail and explain how your result is tighter.\n\n**A**: Our results improve the discussions in [1, 6] by removing the Lipschitzness assumptions and involving training errors, which implies faster rates under low noise conditions. Our results improve the results in [6] and [8] by removing the term $G\\eta T/(1-\\lambda)$ and $\\lambda$ respectively, which do not involve $m$ and $n$. Our results improve [9] by removing both the bounded variance assumption and the term $C_W$. Furthermore, our stability analysis implies fast rates under a low noise condition. As a comparison, the stability bound in [9] involves $(\\sigma\\eta T+GT\\eta C_W)/(mn)$, which does not imply fast rates in the low noise case. The stability bound in [7] involves a dominant factor $\\frac{\\eta^2\\sqrt{T}}{1-\\lambda}$ (if $\\eta\\gtrsim \\frac{1-\\lambda}{mn}$ and we ignore $L$ for brevity), which is replaced by $\\frac{\\eta^{\\frac{3}{2}}}{\\sqrt{m n}(1-\\lambda)}+\\frac{\\eta}{m\\sqrt{n}}$ in our bound. If $\\eta \\gtrsim \\frac{1}{mnT}$ and $\\eta\\gtrsim \\frac{1-\\lambda}{\\sqrt{Tn}m}$, then we have $\\frac{\\eta^2\\sqrt{T}}{1-\\lambda}\\gtrsim \\frac{\\eta^{\\frac{3}{2}}}{\\sqrt{m n}(1-\\lambda)}+\\frac{\\eta}{m\\sqrt{n}}$ and our stability bound is better. Our analysis suggests $\\eta\\asymp 1/\\sqrt{mn}$ in Remark 4.9, and in this case we have $\\frac{\\eta^2\\sqrt{T}}{1-\\lambda}\\gg \\frac{\\eta^{\\frac{3}{2}}}{\\sqrt{m n}(1-\\lambda)}+\\frac{\\eta}{m\\sqrt{n}}$.\n\n**Q5**: How your result is tighter than [7]? Is it comparable when considering deterministic gradient?\n\n**A**: Yes, our technique can still imply better stability bounds when applied to decentralized gradient descent. Indeed, the discussions in [7] control the neighboring consensus errors by two consensus errors (Remark 4.3), which fail to use the property that neighboring consensus errors consider the difference of models produced on neighboring datasets. We introduce new techniques to control the neighboring consensus errors with an error decomposition and the coercivity of smooth functions. We can apply this technique to decentralized GD and improve the existing stability analysis.\n\n**Q6**: Providing experimental results is useful.\n\n**A**: Thanks for your suggestions. We agree that empirical analysis is helpful to validate our theoretical findings. We will leave it as future work.\n\n[1] Graph-dependent implicit regularisation for distributed stochastic subgradient descent. JMLR, 2020.\n\n[2] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. NeurIPS, 2021.\n\n[3] Generalization guarantees of gradient descent for shallow neural networks. NeurIPS, 2024.\n\n[4] Sharper guarantees for learning neural network classifiers with gradient methods. arXiv preprint, 2024.\n\n[5] On the optimization and generalization of multi-head attention. TMLR, 2024.\n\n[6] Stability and generalization of decentralized stochastic gradient descent. AAAI, 2021.\n\n[7] On generalization of decentralized learning with separable data. AISTATS, 2023.\n\n[8] Topology-aware generalization of decentralized sgd. ICML, 2022.\n\n[9] Improved stability and generalization guarantees of the decentralized sgd algorithm. ICML, 2024.", "claims_and_evidence": "Yes. All proofs are provided.", "methods_and_evaluation_criteria": "No simulations are provided.", "theoretical_claims": "I did not check the proofs. The results seem reasonable. However, the writing and presentation of the results needs working on.", "experimental_designs_or_analyses": "There are no numerical experiments.", "relation_to_broader_scientific_literature": "The contributions are novel as the theoretical results give tighter bounds with less restrictive assumptions.", "essential_references_not_discussed": "No. The work discusses all relevant works.", "other_strengths_and_weaknesses": "The paper has sufficient novelty but lacks clarity in presenting the problem and results. Notation is quite confusing, and clearer discussion should be provided regarding the main results.\n\nAnother weakness is that the analysis applies to convex setting.", "other_comments_or_suggestions": "I suggest clearly discussing the novelty in this work and how you were able to provide tighter bounds with less restrictive assumption. A clear explanation of the theoretical novelty would be useful. \n\nIt would be useful to provide experimental results backing the theoretical findings.", "questions_for_authors": "Can you please discuss Table 1 in details and clearly explain how your result is tighter. The bounds involve the stepsize and it is not clear to me how you result is tighter than Taheri and Thrampoulidis (2023). Are your results comparable when considering deterministic gradient?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fTdDF8Q3Te", "reviewer": "Reviewer_wK2k", "summary": "This work establishes sharper stability and generalization bounds for decentralized SGD (D-SGD) under weaker assumptions. The analysis primarily builds on the on-average model stability, with a key innovation lying in the novel decomposition of neighboring consensus errors in decentralized settings.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.\n\n**Q1**: The theoretical analysis in this paper is limited to the convex problem. Can the analysis in this paper be extended to non-convex problems, e.g., training deep neural networks, and does the neighboring consensus error behave differently in this case?\n\n**A**: Thanks for the suggestion. We agree that generalization analysis for nonconvex problems is interesting for understanding the practical performance of D-SGD. We will explore this direction in our future studies. For example, it is interesting to study the stability and generalization analysis of decentralized algorithms for training overparameterized neural networks, where we can exploit some weak-convexity [2, 3] and self-bounding weak-convexity [4, 5] to develop meaningful stability bounds.\n\n**Q2**: In line 22, the authors say that this paper develops optimal generalization bounds, how to show that the results in the paper are optimal?\n\n**A**: The minimax statistical error for learning with a convex and smooth function is $O(1/\\sqrt{n})$ (e.g., Theorem 7 in [1]), where $n$ is the sample size. As we have $mn$ training examples in total, the minimax optimal error bound for the decentralized setting is $O(1/\\sqrt{mn})$. Since we achieve excess risk bounds of order $O(1/\\sqrt{mn})$ (Remark 4.9), we derive the minimax optimal risk bounds. We will clarify this in the revision.\n\n[1] Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint, 2018.\n\n[2] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. NeurIPS, 2021.\n\n[3] Generalization guarantees of gradient descent for shallow neural networks. Neural Computation, 2024.\n\n[4] Sharper guarantees for learning neural network classifiers with gradient methods. arXiv preprint, 2024.\n\n[5] On the optimization and generalization of multi-head attention. TMLR, 2024.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I have checked the theoretical results in the main text.", "experimental_designs_or_analyses": "This paper does not contain experiments.", "relation_to_broader_scientific_literature": "Prior work was constrained by strict assumptions (Richards et al., 2020; Sun et al., 2021; Zhu et al., 2022; Le Bars et al. 2024); this work relaxes the assumptions and yields improved generalization results.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strengths \n* For smooth convex problems, this paper analyzes the convergence and generalization of D-SGD without relying on the Lipschitzness assumption.\n\n* The paper investigates the generalization performance of D-SGD in non-smooth problems (satisfying the Holder continuous gradients condition).\n* The analysis utilizes the co-coercivity property of the gradient for a novel decomposition of the neighboring consensus error.\n\nWeaknesses\n* The theoretical analysis in this paper is limited to the convex problem.", "other_comments_or_suggestions": "See the questions.", "questions_for_authors": "1. ~~Can the analysis in this paper be extended to non-convex problems, e.g., training deep neural networks, and does the neighboring consensus error behave differently in this case?~~\n\n2. ~~In line 22, the authors say that this paper develops optimal generalization bounds, how to show that the results in the paper are optimal?~~", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a refined generalization and excess risk analysis for decentralized stochastic gradient descent (D-SGD) in convex settings, where the authors remove the standard Lipschitzness assumption and extend the analysis to include smooth and nonsmooth problems. A novel error decomposition of neighboring consensus errors is introduced, leading to tighter stability bounds and fast excess risk rates under low noise conditions.

All reviewers appreciate the paper's strong theoretical contributions and clear exposition. Therefore, I recommend acceptance.
Decision: Accept (poster)