Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training
Authors: Qinglun Li
Yingqi Liu
Miao Zhang
Xiaochun Cao
Quanjun Yin
Li Shen
Venue: NeurIPS 2025 spotlight ()
Keywords: stability and generalization; DSGD; Multiple Gossip Steps; generalization error; excess error
Primary area: theory

Abstract: Decentralized training removes the centralized server, making it a communication-efficient approach that can significantly improve training efficiency, but it often suffers from degraded performance compared to centralized training.
Multi-Gossip Steps (MGS) serve as a simple yet effective bridge between decentralized and centralized training, significantly reducing experiment performance gaps. 
However, the theoretical reasons for its effectiveness and whether this gap can be fully eliminated by MGS remain open questions.
In this paper, we derive upper bounds on the generalization error and excess error of MGS using stability analysis, systematically answering these two key questions.
1). Optimization Error Reduction: MGS reduces the optimization error bound at an exponential rate, thereby exponentially tightening the generalization error bound and enabling convergence to better solutions.
2). Gap to Centralization: Even as MGS approaches infinity, a non-negligible gap in generalization error remains compared to centralized mini-batch SGD ($\mathcal{O}(T^{\frac{c\beta}{c\beta +1}}/{n m})$ in centralized and  $\mathcal{O}(T^{\frac{2c\beta}{2c\beta +2}}/{n m^{\frac{1}{2c\beta +2}}})$ in decentralized).
Furthermore, we provide the first unified analysis of how factors like learning rate, data heterogeneity, node count, per-node sample size, and communication topology impact the generalization of MGS under non-convex settings without the bounded gradients assumption, filling a critical theoretical gap in decentralized training. Finally, promising experiments on CIFAR datasets support our theoretical findings.

Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training
Qinglun Li', Yingqi Liu?, Miao Zhang', Xiaochun Cao², Quanjun Yin'.", Li S3, State Key Laboratory of Digital Intelligent Modeling and Simulation, National University of Defense Technology, Changsha, 410073
SSchool of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University, China Center for AI Theoretical Foundation and Systems, Shenzhen Loop Area Institute, China 1 Liqinglume un@nddt. edu. yn,yin, Laan_uuannn_ juanjunn11e jun@163.... com mathshenl @gmail. com
Abstract
Decentralized training removes the centralized server, making it a communication- efficient approach that can significantly improve training efficiency, but it often suffers from degraded performance compared to centralized training. Multi-Gossip Steps (MGS) serve as a simple yet effective bridge between decentralized and centralized training, significantly reducing experiment performance gaps. How- ever, the theoretical reasons for its effectiveness and whether this gap can be fully eliminated by MGS remain open questions. In this paper, we derive upper bounds on the generalization eтrоr and excess егтоr of MGS using stability analysis. sys- tematically answering these two key questions. 1). Optimization Error Reduction: MGS reduces the optimization eтror bound at an exponential rate, thereby exponen- tially tightening the generalization error bound and enabling convergence better solutions. 2). Gap to Centralization: Even MGS approaches infinity, non- negligible gap in generalization error remains compared to centralized mini-batch ed SGD (# /nm) in centralized and O x=m4 in decentralized), Furthermore, we provide the first unified analysis of how factors like learning rate, data heterogeneity, node count, per-node sample size, and communication topology impact the generalization MGS under non-convex settings without the bounded gradients assumption, filling critical theoretical gap in decentralized training. Finally, promising experiments on CIFAR datasets support our theoretical findings.
Introduction
Recently, decentralized training 2 has
emerged as a promising alternative to central- ized training, which suffers from challenges like high communication overhead 3 single point of failure (4, and privacy risks (5] In
Gouda Ne coich dop
Test Accorne
12.
baiie Mout a Caute
trast, decentralized training eliminates the cen- tral server, offering stronger privacy protection (6), faster model training [7] and robustness slow client devices making it an increas- ingly popular method
Pestezad00
Lik
Communicahonn Rounds
Communiratioe Rounds
Figure 1: Under ring topology. DSGD-MGS with 20 gossip steps still shows significant performance gaps versus Mini-batch SGD in both training loss and test. accuracy (LeNet on CIFAR-10, Dir 0.3, 50 nodes).
Corresponding Authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, despite the aforementioned advan-
tages of decentralized training, some works g TO have pointed out that decentralized training methods underperform compared to centralized training methods in terms of model performance. Therefore, improving the performance of decentralized training models remains an important research question. Multiple Gossip Steps (MGS) 12 [3]. as simple yet effective method to enhance the per- formance of decentralized training models, has been experimentally proven to significantly improve the efficiency and performance of decentralized training 15 16 17.. Even under communication compression, MGS continues to demonstrate its advantages in performance improvement [1].
Despite the substantial empirical benefits of MGS, the underlying theoretical understanding of its efficacy and its potential to eliminate the performance gap with centralized training remain critical open questions. Specifically, two key issues need to be addressed:
(1) Why is MGS effective in improving model performance? (2) Can decentralized training ultimately match or even surpass the performance of centralized training by increasing the number of gossip steps?
To answer these open questions, we aim to theoretically explain how MGS works and how it affects model generalization. Using stability analysis, we find upper limits for the generalization error and excess error of MGS, giving systematic theoretical answers to these two main questions.
For Question 1, our theoretical analysis shows that MGS can reduce the optimization error bound at an exponential rate. This reduction in optimization error directly leads to an exponential reduction in the generalization error (as shown in Theorem
2 S and Remark 2). enabling the model find better solutions. This relationship clearly explains why MGS effectively improves model performance. As illustrated Figure D when the number of gossip steps is increased from I to 5, there is a significant reduction in the training loss (indicating reduced optimization error), and the test accuracy (measuring generalization) also shows a noticeable improvement. Furthermore, this improvement tends to diminish almost linearly as the number of gossip steps increases exponentially, consistent with the exponential decay in our theory findings.
For Question 2, our further analysis shows that even with very large number of gossip steps, basic difference in generalization error remains between decentralized DSGD-MGS and centralized mini-batch SGD.
Specifically, when the number of gossip steps becomes extremely large, the generalization error bound 2e8 for DSGD-MGS becomes at most (T 2c342 /rem 2o242). However, this is still noticeably larger than
the centralized mini-batch SGD bound of (T /nm). highlighting a lasting difference in how it scales with the number of clients (because 1/m < 1/m 369 when >> 1). This theoretical observation reveals basic constraint: decentralized training cannot fully achieve the generalization performance of centralized training solely by increasing the number of MGS steps. Experiments shown in Figure D support this conclusion, indicating that even with 20 gossip steps, DSGD-MGS still performs worse than centralized mini-batch SGD in the same settings.
Moreover, we are the first to provide theoretical framework understand how critical factors, in- cluding learning rate, data heterogeneity, number of nodes, sample size per node, and communication topology, jointly influence the generalization performance of MGS (see Reamrk 2 Remarkably, we also eliminate the bounded gradient assumption in the non-convex condition. This work enhances our understanding of the challenges in decentralized learning and provides theoretical insights for hyper- parameters to better model generalization. Finally, extensive experiments on CIFAR datasets further validate our thcoretical results. The main contributions of this paper can be summarized as follows:
Theoretically elucidating the mechanism by which MGS enhances the generalization performance of decentralized training models through an exponential reduction in optimization error.
Revealing that even with sufficient gossip communication, a theoretical gap in generalization error remains between MGS and centralized training, and this gap cannot be eliminated by MGS alone.
Establishing, for the first time under non-convex and without the bound gradient assumption, unified framework analyzing factors impacting the MGS generalization performance (i.e., learning rate, data heterogeneity, number of nodes, sample size, and topology), thereby addressing a significant gap in existing theoretical frameworks.

---

Validating our theoretical findings through empirical experiments on the CIFAR datasets.
These findings provide new theoretical insights and practical implications for understanding and improving decentralized learning algorithms.
2 Related Works
This section reviews the current theoretical understanding and challenges in decentralized training. along with the evolution and impact of MGS. Moreover, at the end of each subsection, we highlight the existing gaps and open questions within these areas to position the contributions of this paper.
Theoretical Analysis of D-SGD. Decentralized learning has attracted significant research interest due to its potential for enhanced privacy, communication efficiency, and scalability [7 6 g Early theoretical studies primarily focused the convergence analysis of D-SGD, examining the number of iterations or communication rounds needed to reach an e-accurate solution 7 [8] [9] More recently, attention has shifted towards understanding the generalization performance of these algorithms. Sun et al. (20 were the first to analyze the generalization performance of D-SGD using uniform stability, later extending their results to asynchronous D-SGD [1]. However, these analyses assumed homoge- neous data and bounded gradients. Zhu et al. [22 further studied the impact of communication topol- ogy the generalization eгror of D-SGD, with their generalization bounds later improved by [Л], but they also relied on the same assumptions. More recently, Ye et al. [23) analyzed the generalization be- havior of D-SGD under heterogeneous data, but their analysis was limited strongly conver loss func- tions. Overall, current D-SGD theories still lack unified framework that comprehensively accounts for all key algorithm parameters (c.g., data heterogeneity, non-convex loss function, topology, etc.).
MGS in Decentralized Training. Multiple Gossip Steps (MGS) 24 2
is a technique that improves consensus by allowing multiple rounds of local communication. When integrated into decentralized algorithms, MGS not only enhances generalization performance but also accelerates convergence (25). Additionally, Yuan al. [19] showed that MGS reduce the adverse effects of data heterogeneity, a finding supported by other studies [26] [6]. Li et al. [27] found that MGS can significantly improve algorithm accuracy. In the field of decentralized federated learning, Shi al. (16) incorporated MGS into their DFedSAM algorithm, significantly improving its generalization performance experimentally. Notably, MGS alone can achieve optimal convergence rates in non-convex settings [99] without
relying on more complex techniques like gradient tracking (28). quasi-global momentum [29]. or adaptive momentum (30). However, these studies have largely overlooked the question of why MGS is effective from a generalization perspective, with these advantages demonstrated mainly through empirical results, leaving significant gap in the theoretical understanding of MGS.
Background
In this section, we first present some fundamental definitions required for stability analysis, including population risk, empirical risk, generalization error, excess error, and l2 on-average model stability. Subsequently, we introduce a key lemma that establishes the relationship between the generalization error bound and le on-average model stability.
3.1 Stability and Generalization in Decentralized Learning
We consider the general statistical learning setting, adapted to decentralized framework with m agents] Each agent & observes data points drawn from a local distribution D3 with support Z. The goal is to find global model 0 E R&d that minimizes the population risk, defined as:
M
1
R(0)
(0)
Ez-D, [e(; 2))
m
where l is some loss function. We denote by 0* global minimizer of the population risk, i.e., O" arg ming R(0).
In this paper. the terms node, agent, and client used interchangeably.
3

---

Although the population risk R(O) is not directly computable, we can instead evaluate an empirical counterpart using local datasets S (S.....,Sa Sm). where S [Zik,.... Zun represents the dataset of agent k, with each sample Zi drawn from the local distribution Dx. For simplicity, we assume that each local dataset has the same size n, though our analysis can be extended to the heterogeneous case. The resulting empirical risk is given by:
1
(0)
A
Rs (0)
{(0; 7sk)
1=1
k=1
One of the most well-known and extensively studied estimators is the empirical risk minimizer, defined as FERM - arg ming (f). However, in most practical scenarios, directly computing this estimator is infeasible. Instead, one typically employs potentially random decentralized optimization algorithm A, which takes the full dataset S as input and returns an approximate minimizer A(S) Rd for the empirical risk (f)
In this setting, the expected excess risk R(A(S)) - R(O*) can be upper-bounded by the sum of the (expected) generalizution error (Egen) and the (expected) optimization error (tops) 23
(3.1) where Egen EAAs(R(A(SS) -ss(((() and Copt (A.s(Rs(A(S)) Rs (PERM)] This work focuses on controlling the expected generalization error Eyen: for which a common approach is to use the stability analysis of the algorithm A.
EA R(A(S)) - R(0")] S 'gen + Capt
(s((()))
Contrary to large body of works using the well-known uniform stability
32 our analysis relies
on the notion of on-average model stability (33,, which has the advantage of removing the bounded gradient assumption 3 (34] [00 in our analysis, making the theoretical results more general. Below, we recall this notion, with slight adaptation to the decentralized setting.
Definition 1 (/2 on-average model stability). Let S (Si.... Sm) with S (........ knk3 and S = (SI,..., Sm) with S₁ = {Zik..... Znxz} be two independent copies such that Ziae ~ Dy and Zix ~ Dr. For any E {I.....n) .n. and j E {l....,m) m.. let us denote by S(35) (Si....,
S S( : Sstt.:..., Sm), with 5 [Zzj..... Zs-1j, Ziz. Zet2s.... Zngh: the dataset formed S by replacing the i-th element the j-th agent's dataset by Zig. A randomized algorithm A is said to be la on-average model e-stable if
n m |IA(S) - A(S E
S.S.AA IIM
(3.2)
3=1
key aspect of on-average model stability is that it can directly be linked to the generalization error, as shown in the following lemma.
Lemma 1 (Generalization via on-average model stability 33). Let A be l2 on-average model f B-smoothness for all E 2, we have
e-stable. Let oy >> 0. Then, {(; 2) is nonnegative and is
1 m
8 ++7
m
ΣΣ
EA.s (A
E A.A.sSllA(SS) A((((())))(()) |2]
Egen
2mn
In fact, we modified the proof of the lemma from Lei al. (33, replacing the Rs (s()) on the right- hand side with gradient EA.s [[(A(S): )1.) This adjustment better captures the impact of data heterogeneity on the generalization error. With this lemma, obtaining the desired generalization bound reduces to controlling the l2 on-average model stability of the decentralized algorithm A.
3.2 Decentralized SGD with Multiple Gossip Steps
In this paper, we focus the widely-used Decentralized Stochastic Gradient Descent (D-SGD) algorithm 735 which aims to find minimizers (or saddle points) of the empirical risk Rs(0) in fully decentralized manner. This algorithm relies on peer-to-peer communication between agents, with a graph representing which pairs of agents (or nodes) are able to interact. Specifically, the communication topology is captured by a gossip matrix W [0, 1 (see Definition 2). where Wjk. > 0 indicates the weight that agent j assigns to messages from agent k, and Wfk 0 (no edge) implies that agent j does not receive messages from agent k.

---

The D-SGD with Multiple Gossip Steps (DSGD- MGS) algorithm performs multiple gossip up- dates during the communication phase of the D)- SGD algorithm, while all other computational components remain identical to D-SGD, as de- tailed in Algorithm [] Specifically, the main procedure at time is divided into two steps:
Algorithm 1 Decentralized SGD with MGS
1: Input: Initialize Vk, 000 ((4) E R itera-
tions T, stepsizes (17 t=u weight matrix W, Multiple Gossip Steps Q.
2:
for 0, ..... T' do
3:
for each node k: = 1,... m in parallel do
Local Update Steps: Each node inde-
4: Local Update Steps:
pendently and uniformly draws training
5:
Sample 12 u(1........
sample Zidz from its local dataset Sj. Based
e(.00) g 1/6 Ve A Zigk)
6:
on the current model parameter 0%- it computes the gradient Ve(o(") Z)gx) and performs gradient descent obtain the initial point for Multiple Gossip Steps:
7:
Multiple Gossip Steps: for q = 0 to Q do
8:
0(+-0t1) = Li=1 Wa
9:
end for
11: o
0(:.0) = o( 7/ Ve KiTx), where ve denotes the step size.
k
end for
13:
end for
Multiple Gossip Steps: Each node exchanges
information with its neighbors through Q gossip averaging steps: g(.0011) = En Wuo The
resulting model parameter olt.a++) is then used as the initial point of for the next Local Update
Steps.
Generalization Analysis
In this section, we first introduce the Definition and Assumptions required for analyzing the gener- alization of the DSGD-MGS algorithm. We then present the upper bounds for the generalization eтror and excess error, followed by detailed analysis of these bounds. Proofs for all Lemmas and Theorems can be found in the Appendix
4.1 Definition and Assumption
Definition 2 (Gossip Matrix). Let W E [0. 1j be a symmetric doubly stochastic matrix. This means that W W and both the row sums and column sums of W equal one, i.e, W1 and 1 W = 1 where 1 is the vector of all ones. The eigenvalues of W are ordered as = (W) D> (W) 2 ... 2 (W)), The spectral gap of W, denoted by 8, defined as 5 = 1 - (T) (0.
Assumption 1. (3-smoothnesss. The loss function E is B-smooth i.e. 78 O such that '00 O' Ve(0'; S 0100 1|2. Assumption 2. (Bounded Stochastic Gradient Noise). There exists 0² (V8(0 Zi,)) RRs, (0) S for any agent j E [m]] and E Rd.
2, 2 (VE((;
0 such that
Assumption (Bounded Heterogeneity). There exists g² 0 such that m EK=1 V Rs, (0) RRs(0) S for any E TR..
Using the property B-smoothness of E(0;z), Ez-D. [e(0; Z) and Rs, (0) = 3 E E(0; Z,x) also satisfy the property 8-smoothness.
straightforward to show that (x
Remark 1. Definition 2 stipulates that the communication topology must be a doubly stochastic
matrix, which appears in many decentralized optimization works M7 34 77 78 3j. Assumption 7 specifies that the loss function is smooth, which is often used in optimization and generalization
studies under non-com non-conve settings [36] TO, 37 38 39 40). Assumption 2 states that the stochastic
gradients of the samples are bounded, and Assumption
3 bounds the heterogeneity of the data. These
assumptions are frequently used in the convergence analysis of many works [36] 3 T6 37), and we will employ them this paper to analyze the stability and generulization of DSGDDMGS..
4.2 Generalization Error and Excess Error of DSGD-MGS
Due to its fully decentralized structure, DSGD-MGS produces m distinct outputs, (S) A ((T) ..... (S) A ell²), one for each agent. As result, the stability and generalization anal-
5

---

ysis that follows will focus on these individual outputs, rather than single global output A(S) as described in Section 3.1 Denote by (s) o and Ag(S(()) ((. (i.j), the final iterates of agent & for DSGD-MGS run over two data sets S and S( that differ only in the i-th sample of agent j. To obtain tighter upper bound for the non-convex case, modify Lemma [ by
introducing a variable to. resulting in the following key lemma, which transforms the computation of the generalization error upper bound Egen into the computation of the stability upper bound.
Lemma 2. Assume the loss function ll., z) is nomnegative and bounded in [o, 1], and that Assumptions 7 hold. For all 1,....
; n and j = 1,....,1, m,, let (0(2) Y and (0t (i, (i.j))zo the iterates of agent 1,.... m mmforr DSGI-MGS run on S and ((1)) respectively. Then, for every to E {0, 10.,,...,77
we have:
[EA, (AA,((((A((S))) Rs (S)(II
< 10
7
E ())
2mn
2mnr
Is: 1a on-average model stability
12: Related to optimization error
where (i, is the vector containing Wk = 1....,.mm m, g (i.j) = 10 0 (i.))lB
According Lemmal compute the generalization error Egen. We need to calculate the la on- average model stability (41) and the gradient related to the optimization error (12). Below, we first provide the stability upper bound, followed by the optimization error upper bound.
Upper bound of I:: For fixed couple (i.j), we are first going to control the vector A 0j. When it is clear from context, simply write (i.ji (( Next, we provide the upper bound of the on-average model stability for the DSGD-MGS algorithm.
17722 Σi, (i,
(i, where (i, & (i (2,j))88t))..)
(i.j)
Theorem (Stability for the DSGD-MGS). As in the conditions of Lemma 2
then the following
holds:
m
(T) (i, (80)) = =0 0] E 8ev/Bc22
T 2cB
E BIO
mIn
(1 + 203) nmmlo
To
Upper bound of 12: Let G 1 E.s El| E( Zay 123. According to the Assumptions 2 and
mn
3 the following inequality holds:
E| ElIVEE( 21)11
B[[ 2gg) + V (
(0(T) + ( I
mm
mm
1.j
< 30 + 3 +
3E
RR
1
Since é satisfies the 3-smoothness property, it straightforward to show that R0 (T)) also satisfies
the 3-smoothness property. Consequently, (o) also satisfies the self-bounding property in Lemma
3 (see the Appendix B), i.e., (0) 1 < (.).. Then, we have
G < 30 + + + 63Es[Rs(0(())
(4.1)
According the results from Lemma 2 in the Appendix B), we have the following theorem:
Next, we will focus on bounding Es [R (O (o ).
18 Theorem 1] (see
Theorem 2 (Optimization error of DSGD-MGS). Let A =- maxa E VRs, (0*)
Ro := ()()))) R'g, where X arg ming Ro( and Rts- Rss (OERM) Suppose Assumptions (PL) condition (see Assumption Ain the Appendix) hold. Define
1 and
11- (1- 87 2 p
Qo = log (1//4)//logg
11
m3
82
85 (4+ 28) 22 (I W)

---

Then, if the nodes are initialized such that 0 0, for any Q > Qu after T iterations the iterates of DSGD-MMS with satisfy
(s(Rs(0())) RTg =0
A 6
1
B (1+ 444 up
Rop²)
(4.2)
Here, å represents the spectral gap of W, and p 2 1
(22(W) defined in definition
By combining Equation 4.1 with Theorem 2 we obtain the upper bound for G.
252
G = 0 + 5 + R2s) +
0
+
1+ up (1+0-
Roopp)
(4.3)
1-p
Generalization Bound for DSGD-MGS: With the above Theorem & 2 we can derive the generalization eтror upper bound for DSGD-MGS.
Theorem 3 (Generalization error of DSGD-MGS). Based Lemma 2 Theorem D and Theorem and assuming that Assumptions 7 hold, let the learning rate satisfy di I c t+1 for some constant
e > O. We derive the following resull by uppropriately selecting to and y::
(A.s[R(AAx()))) - (e((AR (s)(A(())]I
2cB +3
@Gev/3ee22e
2cB +2
[BBev /4Bev23c 23c2T20B 20012
(n(2c8 + 1)) 20043
20242
17
n(2cB + 1)
m
where the expression for G is given in Equation 4.3
Remark 2 (Optimization Error Reduction). As shown in Theorem 3 the generalization error bound obtained via l2 on-average model stability is closely related to the optimization error G. Analyzing the MGS-relater terms reveals that increasing the number of MGS steps Q reduces G. thereby lightening the generalization error bound. Moreover, a more detailed analysis shows that the reduction in the generalization error bound is exponential, specifically the order of O $x8 indicating that even a small increase in Q can lead to significant gains. This observation will also be validated in the experimental section 5.2
Remark 3 (Gap to Centralization). As indicated by Theorem 3 by letting Q approach infinity, we can derive the limiting generalization error bound, which helps address whether DSGD-MGS with sufficiently many steps can effectively approximate centralized mini-batch SGD. The answer T (23334/ /nmm (om22 which still differs in terms of
no, because the resulting bound is at most
(TeoFI /mm) established for centralized mini-batch SGD based on uniform stability in M 41y. Therefore, this gap persists unless the number of nodes or the data size per node is significantly increased. As illustrated in Figure[]
node count m and per-node data size n. from the bound O
Remark 4 (Related to the Optimization Error). Compared to prior works on the generalization er- of D-SGD (42 (7 22y, which rely Lipschitz assumptions for the loss function, approuch removes this assumption, allowing for a more explicit connection between optimization error and generalization error. In those works, the Lipschitz assumption effectively absorbs optimization-rrlateee quantitiies (e.g., gradients) into a Lipschtiz constant, obscuring this relationship. In contrast, our work removes the Lipschitz assumption, making the relationship between generalization and optimization ervors more explicit. Our results show that reducing optimization error can also decrease generaliza- tion error to some extent, which explains the common observation that training progresses, both the training error decreases and the model's performance on the validation set improves.
Remark (Influential Factors of the Generalization Error for DSGD-MGS). When the model, loss function, and dataset are fixed, parameters like the smoothness 3, gradient noise and data heterogeneity 8 are also fixed. In this case, to reduce the generalization error bound according the upper bound in Theorem 3 the following strategies are effective: 1) Increase the data size per node n; 2) Increase the number of nodes mi; 3) Increase the MGS step count Q; 4) Reduce the distance between the optimal point and the initial point Ro; 5) Use communication topology with a larger spectral gap (which implies a smaller p); 6) Decrease the learning rate e. The first five are straight- forward, while the sixth is recommended because the number of iterations T is usually large. making
7

---

T the dominant term in the bound. Reducing can significantly reduce this term. Additionally, if the choice of dataset is flexible, selecting one that is as close to i.i.d. as possible is beneficial, as a larger data heterogeneity parameter & will generally increase the generalization error bound.
Remark 6 (Innovation in Generalization Error Bounds). Our work introduces l2 on-average model stability to deriving generalization error bounds for decentralized algorithms, characterized by the following key innovations: 1) Removal of Lipschitz Assumption: Unlike previous proof's based on uniform stability [47 20 I
TO 9 43y, our approach removes the Lipschitz assumption on the loss function (which implicitly bounds the gradient), allowing the relationship between optimization error and generalization error to become more explicit. 2) Explicit Role of Optimization Error: We establish, for the first time, a direct connection between the optimization error and generalization error of the D-SGD algorithm, revealing that reducing the optimization error also decreases the gen- eralization error, which aligns better with observed training dynamics. 3) Exponential MGS Benefit: Our bounds demonstrate that the impacl of MGS on reducing generalization error exponential, high- lighting the significant gains achievable with moderate number of MGS steps. 4) Quantification of Heterogeneity Impact: Ye et al. (23] were the first to theoretically reveal that data heterogeneity can degrade the generalization bound of the D-SGD algorithm under the strongly convex setting. Building on this, we take a further step by providing a precise characterization of how data heterogeneity affects generalization in the non-convex setting, filling critical gap in existing theoretical analyses.
Theorem 4 (Excess Error of DSGD-MGS). Under the same conditions and notation as Theorems 3 Band2 2 and based on the decomposition of excess error in Equation (.I, the optimization error bound (Equationn) 4.2). and the generalization error bound (Theorem 3) bound for the excess error.
we obtain the following upper
8-Q A
B 14
(1+e-578)
$10)
)]
E EA.s(R(A(S)) R(O0) = O
1+
Rop"
(4.4)
P
G CT203
20073
1
+
2G0
Ti 33.443
m
n2
m
(The difference of conclusions obtained from excess error and generalization error). Since the excess error can be decomposed as (RA()(((())) - conclusions about the generalization error also apply to the excess error (see Remark 5}. The only key difference lies in the choice of learning rale, For Egen a smaller learning rate (i.e., smaller c) is preferred, as Egen is dominated by the term OT this term and hence the generulization error. However, this is not the case for Eopt. Prior work on the
Remark 7
R[O*)] S Egen Eopt. most
20. 2), meaning that reducing e significantly reduces
convergence of D-SGD [7] shows that Cape = O Ro ) indicating that an excessively large learning Tn)
rate increases Eopp. thereby undermining convergence. Thus, the choice of learning rate involves a trade-off between minimizing generalization error and maintaining convergence, a conclusion that will be confirmed in the Experimental Section A.2
Remark 8. (On the Technical Role of the PL Condition). Our analysis of the generalization error requires bounding the expected squared gradient norm at the final iterate, denoted as G. However, establishing a tight upper bound for the final iterate's 's gradient in non-convex decentralized optimization remains a challenging frontier problem. While recent advances have been made in last-iterate convergence analysis (e.g., (44)), existing results either do not incorporate the MGS mechanism or provide bounds only on the function value gap, which are insufficient for directly bounding G. To bridge this gap, we adopi the ollyak-Lojasewwicz (PL) condition. This is a standard approach in the literature (e.g., (34)) used to connect the squared gradient norm with the function value gap. This technical choice is deliberate and crucial, as a light upper bound on the function value gap under the MGS setting is available [18]. Consequently, the PL condition enables us to derive some of the first fine-graineee MGS-aware generalization bounds that explicitly link the generalization error to key algorithmic hyperparameters, including the number of MGS steps (Q), communication topology, and learning rate. This provides concrete, quantitative insights that significantly advance beyond high-level bounds, such as the classic (1/TT) analysis provided by L2 L2-stability [33]. Therefore, the reliance on the PL condition reflects the current theoretical limits in non-convex last-iterate analysis rather than a fundamental limitation of our stability framework. Our frumework is modular: should future research provide a direct, assumption-free upper bound for G in the MGS setting, our generalization bounds can be immediately strengthened by replacing this component. A more detailed discussion is provided in the Appendix D.4
8

---

Remark 9. All the above discussions are also solid to ( - In addition, our theoretical results apply to decentralized topologies other than the fully connected case. When the topology becomes fully connected, the iterative update reduces the centralized setting. For detailed analysis, please refer to the Appendix. For detailed proof. please refer to Appendix [ Additionally, we provide consensus error analysis further illustrate the behavior of MGS in both finite and infinite regimes (detailed discussion provided in Appendix Furthermore, we extend our theoretical analysis the case involving batch size b. The detailed proofs and analyses provided in the Appendix D.2
5
Experiment
In this section, we present extensive experiments to validate our theoretical findings. We first describe the experimental setup, followed by the empirical results and corresponding analysis. Due to space constraints, the experimental validation of excess error is presented in Appendix A.2 Furthermore, we conduct an in-depth exploration of the subtle relationship between mini-batch size and (Q) on the CIFAR-I00 100 dataset, providing practitioners with insights for achieving higher performance. Detailed analyses and discussions can be found in the Appendix D.3
5.1 Empirical Setup
We conduct experiments the CIFAR-10 dataset 45 with a Dirichlet distribution (non-IID, 0.3) using LeNet to validate the excess error and generalization error of DSGD-MGS. To examine the impact of key hyperparameters,
follow the study by Hardt et al. [41] and investigate the weight distance 12==1 -j=1 [10]0 g (2) and the loss distance (R(((()
()(())) when replacing only one data point the training dataset. We primarily validate the experimental performance of key parameters in the DSGD-MGS algorithm, such communication topology, the number of MGS steps, and the total number of clients. For fairness, when exploring one parameter, all other parameters
are kept at the same settings. Further implementation details are provided in Appendix A.1
5.2 Experimental Validation of Generalization Error.
As shown in Figure subplots (a) and (b) respectively illustrate the weight distance and loss distance for different parameter settings of the DSGD-MGS algorithm on the perturbed dataset. Overall, both weight distance and loss distance exhibit the same power-law behavior as our theoretical bound
OT (see Theorem 3). Additionally, within each column of Figure (corresponding to the same parameter setting), these two metrics follow similar trends, confirming the validity of Lemma which states that the generalization error can indeed be captured by the stability bound.
33
communication Topology
Piple Gessip Steps
Learning Robe
Client Number
Veigi delence
Communicalion Bounds
Communicatinn Roundds
Communication Ituurds
Communication Rouncs
(a) Weight distance
Boology
oif pile Gress Sleps
Leathin
des Frallyy
Cal
Lowe Desesncc
Loss
Cross Step
Communicaton Rounds Roundss
Commu rication Rounds
Communicatinn Rounds
Commun icaioon Rounds
(b) Loss distance
Figure 2: A comparison of the l2 weight distance and Loss distance (i.e. test loss train loss) for the DSGD-MGS algorithm on the c dataset.

---

From subplots (a) and (b) in Figure 2 we can observe the following patterns: 1) Using a communica- tion topology with a smaller spectral gap (i.e., a larger p in Theorem leads lower generalization ervor. 2) Increasing the number of MGS effectively reduces the generalization error. For example, terms of weight distance (Figure (a)), setting MGS
reduces the weight distance to roughly half of that with MGS = 1. 3) Smaller learning rates help reduce generalization error, consistent with the findings in [10] on decentralized federated learning. 4) A larger client number (i.e., m in Theorem 3 also helps reduce generalization error, reflecting nearly linear speedup effect with the number of clients. Notably, these observations align well with our theoretical results (see Theorem and Remark This further validates the correctness of our theoretical analysis.
6 Conclusion
This paper the first to establish the generalization error and excess error bounds for the DSGD-MGS algorithm in non-convex settings without the bounded gradients assumption. It addresses how MGS can exponentially reduce the generalization error bound and shows that even with a very large number of MGS steps, it cannot completely close the gap between decentralized and centralized training. Additionally, our theoretical results capture the impact of key factors like data heterogeneity communication topology spectrum Ç. Multiple Gossip Steps Q. client number m, and per-client data size n. Previous work has not unified the analysis of these critical parameters, and this paper fills that gap, offering both theoretical insights and experimental validation and significantly advancing the theoretical understanding of decentralized optimization.
Limitation. The theoretical findings in this paper depend on the properties of the last iteration of D-SGD in optimization theory, which an emerging area yet to be explored. This paper derives the properties of the function value at the last iteration under the PL-condition. Future work can further explore the properties of the loss function gradient at the last iteration under non-convex conditions.
Acknowledgment
This work is supported by STI 2030-Main Major Projects (No. 20212D0201405), NSFC Grant (No. 62576364), Shenzhen Basic Research Project (Natural Science Foundation) Basic Research Key Project (NO. (CY)202412021 24430041) and National Natural Science Foundation of China (No.62025604, No.62261 160653). Miao Zhang is supported by the National Natural Science Founda- tion of China (NO. 62403484).
References
[1] Jianshu Chen and Ali H Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8):4289-4305. 2012.
[2] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[3] Qinglun Li, Li Shen, Guanghao Li, Quanjun Yin, and Dacheng Tao. Dfedadmm: Dual constraint controlled model inconsistency for decentralize federated learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, (7(6):48034481 2025.
[4] Min Chen, Yang Xu, Hongli Xu, and Liusheng Huang. Enhancing decentralized federated learning for non-iid data on heterogeneous devices. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 2289-2302. IEEE, 2023.
[5] Edoardo Gabrielli, Giovanni Pica, and Gabriele Tolomei. A survey on decentralized federated learning. arXiv preprint arXiv:2308.00400 2023.
[6] Edwige Cyffers and Aurélien Bellet. Privacy amplification by decentralization. In International Conference on Artificial Intelligence and Statistics, pages 5334-5353. PMLR, 2022.
[7] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 2017.
10

---

[8] Giovanni Neglia, Gianmarco Calbi, Don Towsley, and Gayane Vardoyan. The role of network topology for distributed machine learning. In IEEE INFOCOM 2019-IEEE Conference on Computer Communications, pages 2350-2358. IEEE, 2019.
[9] Yan Sun, Li Shen, and Dacheng Tao. Which mode is better for federated learning? centralized or decentralized. 2023.
[10] Yingqi Liu, Qinglun Li, Jie Tan, Yifan Shi. Li Shen, and Xiaochun Cao. Understanding the stability-based generalization of personalized federated learning. In The Thirteenth International Conference on Learning Representations, 2025.
[11] Batiste Le Bars, Aurélien Bellet, Mare Tommasi, Kevin Scaman, and Giovanni Neglia. Improved stability and generalization guarantees of the decentralized sgd algorithm. arXiv preprint arXiv:2306.0299 02939, 2023.
[12] Sujay Sanghavi, Bruce Hajek, and Laurent Massoulié. Gossiping with multiple messages. IEEE Transactions on Information Theory, 33(12):464004454 2007.
[13] Liu, Shaoshuai Mou, A. Stephen Morse, Brian D. O. Anderson, and Changbin Yu. Determin- istic gossiping. Proceedings of the IEEE, 99(9): 10555555--5244 2011.
[14] Boyue Li, Shicong Cen, Yuxin Chen, and Yuejie Chi. Communication--ffiiinn distributed optimization in networks with gradient tracking and variance reduction. Journal of Machine Learning Research, 21(180):1-51, 2020.
[15] Haishan Ye and Tong Zhang. Deepca: Decentralized exact pea with linear convergence rate. Journal of Machine Leurning Research, 22(238):1-27, 2021.
[16] Yifan Shi, Li Shen, Kang Wei, Yan Sun, Bo Yuan, Xueqian Wang, and Dacheng Tao. Improving the model consistency of decentralized federated learning. arXiv preprint 2.t::2322.0088. 2023.
[17] Haishan Ye, Ziang Zhou, Luo Luo, and Tong Zhang. Decentralized accelerated proximal gradient descent. Advances in Neural Information Processing Systems, 33:18308-1888 2020.
[18] Abolfazl Hashemi, Anish Acharya, Rudrajit Das, Haris Vikalo, Sujay Sanghavi, and Inderjit Dhillon. On the benefits of multiple gossip steps in catptuuiicaaioncconstiiii decentralized federated learning. IEEE Transactions on Parallel and Distributed Systems, 33(11))2727-2733 2021.
[19] Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33:18342-118351 2020.
[20] Tao Sun, Dongsheng Li, and Bao Wang. Stability and generalization of decentralized stochastic gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9756-9764, 2021.
[21] Xiaoge Deng, Tao Sun, Shengwei Li, and Dongsheng Li. Stability- generalization analysis of the asynchronous decentralized sgd. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 7340-7348, 2023.
[22] Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, and Dacheng Tao. Topology-aware generalization of decentralized SGD. In International Conference on Machine Learning, pages 27479-27500 PMIR, 2022.
[23] Haoxiang Ye, Tao Sun, and Qing Ling. Generalization guarantee of decentralized learning with heterogeneous data. In ICASSP 2025 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5, 2025.
[24] Olivier Catoni. PAC-Bayesian supervised classification: the thermodynamics of statistical learning. arXiv preprint arX1vv0712.02448. 2007.
[25] Liu and A Stephen Morse. Accelerated linear iterations for distributed averaging. Annual Reviews in Control, 3502):660-16,, 2011.

---

[26] Alexander Rogozin, Mikhail Bochko, Pavel Dvurechensky, Alexander Gasnikov, and Vladislav Lukoshkin. An accelerated method for decentralized distributed stochastic optimization over time-varying graphs. In 2021 60th IEFF Conference on Decision and Control (CDC), pages 3367-3373. IEFE, 2021.
[27] Guanghao Li, Yue Hu, Miao Zhang, Li Li, Tao Chang, and Quanjun Yin. Fedgosp: A novel framework of gossip federated learning for data heterogeneity. In 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 840-845, 2022.
[28] Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Interna- tional conference on machine learning, pages 7111-7123. PMLR, 2021.
[29] Tao Lin, Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogencous data. In ICML, 2021.
[30] Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Dadam: A consensus- based distributed adaptive gradient method for online optimization. JEEE Transactions on Signal Processing, 70:6065-6079, 2022.
[31] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499 -566, 2002.
[32] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010.
[33] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819. PMLR, 2020.
[34] Tao Sun, Dongsheng Li, and Bao Wang. Decentralized federated averaging. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[35] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent opti- mization. IEEE Transactions on Automatic Control, 54(1):48 61, 2009.
[36] Qinglun Li, Miao Zhang, Tao Sun, Quanjun Yin, and Li Shen. Dfedgfm: Pursuing global consistency for decentralized federated learning via global flatness and global momentum. Neural Networks, 184:107084, 2025.
[37] Yingqi Liu, Yifan Shi, Qinglun Li, Baoyuan Wu, Xueqian Wang, and Li Shen. Decentralized directed collaboration for personalized federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 23168 221788, 2024.
[38] Qinglun Li, Miao Zhang, Yingqi Liu, Quanjun Yin, Li Shen, and Xiaochun Cao. Boosting the performance of decentralized federated learning via catalyst acceleration. arXiv preprint arXiv:2410.07272. 2024.
[39] Qinglun Li, Miao Zhang, Mengzhu Wang, Quanjun Yin, and Li Shen. Oledfl: Unleashing the potential of decentralized federated learning via opposite lookahead enhancement. arXiv preprint arXiv:2410.0644 06482, 2024.
[40] Qinglun Li, Miao Zhang, Nan Yin, Quanjun Yin, Li Shen, and Xiaochun Cao. Asymmetrically decentralized federated learning. IEEE Transactions on Computers, 2025.
[41] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[42] Tao Sun, Dongsheng Li, and Bao Wang. Stability and generalization of the decentralized stochastic gradient descent. Proceedings of the AAAI Conference on Artificial Intelligence. 35(11)99756-964, Sep 2022.
[43] Yan Sun, Li Shen, and Dacheng Tao. Understanding how consistency works in federated learning via stage- wise relaxed initialization. arXiv preprint arXiv:2306.05766 2023.
12

---

[44] Kun Yuan, Xinmeng Huang, Yiming Chen, Xiaohan Zhang, Yingya Zhang, and Pan Pan. Revis- iting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. Advances in Neural Information Processing Systems, 35:36382-36395, 2022.
[45] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[46] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy. and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 160..04600004886 2016.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We explicitly state the problem addressed and the contributions made by this paper in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the paper the end of the article.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provide the complete proofs in the appendix, and detailed assumptions are presented in the theoretical analysis section.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the details of the algorithm in experimental and appendix sections. And we guide how to select hyperparameters and reproduce it.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Our method is highly implementable, requiring only minor changes to the optimizer in open-source platforms such as FedML..
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
Moolic//guide//Coeeetuliiis
www.sssinnooiiiilo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
www.ssssiicggooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: provide detailed descriptions of data segmentation, hyperparameter selec- tion, and additional implementation details in the experimental and appendix sections.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: section.
We included the standard errors of the tests in the tables in the experimental
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our experiments were conducted on an NVIDIA GeForce RTX 3090, with the runtime of each experiment ranging from hour 4 hours. The duration depends on the size of the dataset and the complexity of the model.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our work complies with NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
19

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This paper does not involve the use of LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neure http:///rrrrrscce//oofff/errr//r cc//oonferences/2225/LLL. for what should or should be described.
20


Reviews:
[{"review_id": "J2IsWsyZHp", "reviewer": "Reviewer_gMXp", "summary": "This paper presents analysis of multiple gossip steps (MGS) approach to decentralized SGD, i.e., a framework in which several rounds of model averaging are performed between stochastic gradient updates. The results include on‑average model stability bounds that explicitly depend on the number of gossip steps and the spectral gap, demonstrating that the error decays exponentially -- in non-convex settings, without making assumption of bounded gradients, and allowing for heterogeneous data distributions. Empirical results on CIFAR‑10 align with the theory, showing that increasing the number of gossip steps significantly improves test accuracy. While MGS tightens the decentralization-induced gap, the analysis shows that a residual asymptotic generalization gap relative to centralized SGD remains even as the number of gossip steps grows to infinity.", "questions": "1) Can the theoretical analysis be extended to the case where local nodes perform mini-batch updates, followed by MGS? If so, the local batch size would become a variable of interest.\n\n2) Even if theoretical analysis appear challenging, an experimental study of the interplay between communication and computation (i.e., (M)GS + local mini-batch) would provide beneficial insight.\n\n3) Can PL condition be relaxed or is it necessary?\n\n4) Could the framework be extended beyond synchronous and symmetric gossip?\n\n5) Broader empirical evaluation would be appreciated.", "limitations": "Yes.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is well-written and technically solid -- as far as I can tell, the presented derivations are correct. However, the contributions are somewhat incremental and the framework raises some concerns, as outlined below:\n\n(1) Previously, Le Bars et al. [ICML '24] used a technique for deriving optimization-dependent generalization bounds for DSGD. The paper under review applies this technique to the analysis of gossip-style local averaging of SGD updates.\n\n(2) The MGS framework assumes sampling one point from a local dataset, computing SGD, and then running multiple gossip steps. However, in addition to inducing latency, the cost of repeatedly communicating the model can be rather expensive -- both from the bandwidth as well as energy perspective. For instance, Savazzi et al. [An Energy and Carbon Footprint Analysis of Distributed and Federated Learning, '22] argue that in many cases communication exceeds computation cost. It may therefore be more natural if the nodes perform mini-batch processing in the same vain done by the centralized scheme which is anyways used as a benchmark.\n\n(3) Performing MGS is predicated upon the assumption of networks with stable links yet in practice the nodes may be available only intermittently. Moreover, in any given round, the communication may be asymmetric -- if A communicates with B, B need not necessarily be able to compute an update and communicate with A. This would violate the doubly-stochastic gossip matrix assumption. It is not clear if/how the current analysis may be extended to such more realistic scenarios.\n\n(4) Theorem 2, a main result, relies on the PL condition yet abstract/introduction do not mention this -- the way they are written now, a reader gets an impression that the results are more general. If indeed necessary, the assumption that PL condition holds should probably be listed along with Assumptions 1-3 in the main paper, rather than given in the appendix.\n\n(5) Experimental results are somewhat limited, considering only CIFAR-10 and LeNet.", "was_revised": true, "final_justification": "Thanks to the authors for addressing the concerns. With the final adjustments (additional results, discussion), I think the paper goes above the acceptance bar. I raised my score accordingly, trusting those additions will find their way to the supplementary material of the final version of the paper.", "rebuttal": "**Reply to Weakness 1:**\n\nThank you for your question. While Le Bars et al. \\[ICML '24] also study optimization-dependent generalization bounds, our work differs in several key aspects:\n\n1. **Theoretical framework:** We use **L2-stability**, while Le Bars et al. rely on **L1-stability**, leading to different starting points, analyses, and results (e.g., our Lemma 4 is derived under L2-stability).\n\n2. **Gradient analysis:** Their treatment replaces the Lipschitz constant with a gradient term in a limited way. We provide a **detailed analysis** of the gradient, linking it to algorithmic hyperparameters, yielding more practical insights.\n\n3. **Convexity assumptions:** Le Bars et al. assume convex losses; we **do not**, allowing our results to apply to **non-convex** settings. To our knowledge, we are the **first** to establish generalization bounds for DSGD under non-convexity when MGS = 1.\n\n4. **Data heterogeneity:** Their analysis assumes iid data. We explicitly address **data heterogeneity**, making our results more realistic—especially since non-convex + non-iid settings remain largely unexplored.\n\n5. **Problem scope:** While both papers study generalization, our focus is on **gossip-based decentralized training**, which introduces unique technical challenges and requires separate analysis.\n\nIn summary, our work differs from Le Bars et al. in theory, assumptions, depth, and focus—representing a substantive advancement, not an incremental extension. **Remark 6** further clarifies our core contributions, including several results that are, to our knowledge, presented for the first time. \n\n---\n\n*Reply to Weakness 2 and Question 1:*\n\nThank you for your insightful comment. You are correct that decentralized training incurs higher communication overhead than centralized schemes. Moreover, **mini-batch SGD** is more commonly used in practice, while most theory focuses on **single-sample SGD**, revealing a gap between theory and practice. Following your suggestion, we extended our theoretical analysis to **decentralized mini-batch SGD** in the revised version.\n\nKey modifications include (full proofs in the revision):\n\n1. **Assumption 2** now accounts for mini-batch sampling:\n\n   $$\n   \\mathbb{E}||\\frac{1}{b}\\sum_{i=1}^b \\nabla \\ell(\\theta; Z_{i,j}) - \\nabla R_{\\mathcal{S}_j}(\\theta)||^2 \\leq \\frac{\\sigma^2}{b}\n   $$\n\n2. **Algorithm line 6** updated to mini-batch gradient:\n\n   $$\n   \\theta_k^{(t,0)} = \\theta_k^{(t)} - \\eta_t \\frac{1}{b}\\sum_{i=1}^b \\nabla \\ell(\\theta_k^{(t)}; Z_{ik})\n   $$\n\n3. **Appendix line 855** probability adjusted:\n\n   $$\n   \\mathbb{P}(\\mathcal{E}(i,j)^c) \\leq \\sum_{t=1}^{t_0} \\frac{b}{n} = \\frac{b t_0}{n}\n   $$\n\nWith these, the generalization bound becomes:\n\n$$\n    \\left|\\mathbb{E}_{A,S}[R(A_k(S)) - R_S(A_k(S))]\\right|\n    \\le \\frac{(2c\\beta+3) b^{\\frac{2c\\beta+2}{2c\\beta+3}}}{\\left(n(2c\\beta+1)\\right)^{\\frac{2c\\beta+2}{2c\\beta+3}}} \\left( \\frac{2 \\bar{G} e \\sqrt{2\\beta} c^2 T^{2c\\beta}}{m} \\right)^{\\frac{1}{2c\\beta+3}} + \\frac{b(2c\\beta+2)}{n(2c\\beta+1)} \\left( \\frac{4 \\beta e \\sqrt{2\\beta} c^2 T^{2c\\beta}}{m} \\right)^{\\frac{1}{2c\\beta+2}}\n$$\n\nNote that \\$\\bar{G}\\$ contains a variance term of order \\$\\mathcal{O}(\\sigma^2 / b)\\$. Comparing to single-sample SGD, increasing batch size \\$b\\$ **increases** the generalization bound, indicating **larger batches enlarge generalization error**.\n\nFrom a stability view, selecting one sample gives a perturbation probability of \\$\\frac{1}{n}\\$; for batch size \\$b\\$, it rises to \\$\\frac{b}{n}\\$. This leads to faster and larger error accumulation in stability \\$\\delta\\_k^{(t)}(i,j)\\$, loosening the generalization bound.\n\nAdditionally, *“On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima”* explains that large batches reduce gradient noise, causing convergence to **sharp minima** with worse generalization, while smaller batches promote **flatter minima** and better generalization—consistent with our theory.\n\n---\n\n*Reply to Weakness 3 and Question 4:*\n\nYou are correct that real-world networks often have intermittent links and asymmetric topologies. Algorithms like **Push-Sum** and **Push-Pull** address this by maintaining an extra scalar to correct aggregation bias from unstable communication. Works such as *Asymmetrically Decentralized Federated Learning* have analyzed **convergence** under such settings.\n\nHowever, **generalization analysis** for asymmetric or time-varying graphs remains largely unexplored. We appreciate the reviewer highlighting this practical and important issue. Our paper focuses on how the **MGS mechanism improves generalization** in decentralized training and compares to centralized schemes. Extending to asymmetric graphs is valuable but beyond this paper’s scope.\n\nNotably, The recent work *\"Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness\"* has successfully applied **L2-stability** techniques to analyze asynchronous SGD. Building on this, we believe that similar **L2-stability-based tools** can be extended to study the generalization behavior over **asymmetric communication graphs**.\n\n\nWe will add discussion of this future direction in the revised manuscript. Thank you again for your insightful suggestion.\n\n---\n\n*Reply to Weakness 4 and Question 3:*\n\nWe sincerely thank the reviewer for this constructive suggestion. In the revised version, we will explicitly include the PL condition in the list of assumptions in the main paper and clearly state its role in the convergence analysis. We will also provide a discussion in the introduction to justify the use of the PL condition and clarify the scope of our results.\n\nTo be precise, our theoretical framework is **not fully dependent** on the PL condition. The PL condition is specifically invoked to facilitate the analysis of\n\n$$\n\\bar{G} = \\frac{1}{mn} \\sum_{i,j}\\mathbb{E}\\left[||\\nabla\\ell(\\theta_k^{(T)};Z_{ij})||^2\\right],\n$$\n\nwhich corresponds to the **expected squared norm of the gradient at the final iterate** of D-SGD. Unfortunately, to the best of our knowledge, this quantity has not yet been well understood in the existing optimization literature, especially in non-convex settings.\n\nTo bridge this gap, we adopt the PL condition as a technical device to relate the squared gradient norm \\$\\bar{G}\\$ to the **function value gap at the final iterate** $R_S(\\theta)$. This allows us to leverage results from prior work — particularly *\"On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization\"* — which provides bounds on the function value at the final iteration. This connection enables a tractable and detailed analysis of \\$\\bar{G}\\$, which in turn leads to fine-grained generalization bounds involving key algorithmic hyperparameters.\n\nImportantly, our reliance on the PL condition is **not inherent to our generalization analysis framework**, but a temporary workaround due to the lack of sharper theoretical tools for analyzing \\$\\bar{G}\\$ in the general non-convex case. We expect that as future research develops more refined characterizations of the final iterate’s gradient norm in non-convex optimization, our generalization bounds can be further improved or even **made independent of the PL condition**.\n\nWe appreciate the reviewer’s insightful comment and will clarify all these points explicitly in the revised manuscript.\n\n---\n*Reply to Weakness 5 and Question 5:*\n\nWe appreciate your valuable feedback. In the revised version of the paper, we have added experimental results using ResNet-18 on the CIFAR-100 dataset, along with corresponding discussions. These results further support our theoretical findings and demonstrate the generality of our conclusions beyond CIFAR-10 and LeNet.\n\nHowever, due to NeurIPS policy, we are not allowed to include any PDF files or external links during the rebuttal period, so we are unable to present these additional results here.\n\n---\n\n*Reply to Question 2:*\nThank you for your insightful question. We agree the interplay between local computation (batch size `b`) and communication (MGS steps `Q`) is a critical, practical aspect.\n\n**1. Theoretical vs. Practical Interplay:**\nOur extended theoretical analysis shows `b` and `Q` affect the error bound via distinct mechanisms. `b` creates an optimization-generalization trade-off in the **computation step**, while `Q` improves consensus in the **communication step**. Mathematically, their effects appear separable, as we find no direct cross-term in our bounds.\n\nHowever, we fully agree a practical \"interplay\" emerges from the **resource trade-off under a fixed training budget** (e.g., wall-clock time). This leads to the fundamental question: is it better to \"compute more, communicate less\" (large `b`, low `Q`) or vice versa?\n\n**2. Experimental Commitment:**\nTo investigate this, we will add an experimental study to the final version. We will fix a training budget, evaluate a grid of `(b, Q)` pairs, and plot the resulting performance (e.g., a test accuracy heatmap). We hypothesize this will reveal a \"ridge\" of optimal configurations, showing the best balance between local work and communication effort for different scenarios. This analysis will be included in the camera-ready paper. Thank you again for this valuable feedback.\n\n\n---\n\nThank you for your detailed and constructive feedback. We will revise our manuscript to address your comments.\n\nSpecifically, we will:\n1.  Clarify our novel contributions (L2-stability, non-convex/non-IID settings) compared to prior work.\n2.  Extend our analysis to mini-batch SGD, showing its impact on generalization, and add new experiments on ResNet-18/CIFAR-100.\n3.  Add an experimental study on the interplay between batch size and MGS steps under a fixed budget.\n4.  Discuss limitations (e.g., asymmetric graphs) and clarify the role of the PL condition as a technical tool.\n\nWe believe these changes will significantly strengthen our paper. Thank you again for your valuable guidance."}, {"review_id": "uOx6y258xL", "reviewer": "Reviewer_rX3y", "summary": "This paper focuses on DSGD-MGS which is a Decentralized Stochastic Gradient Descent (DSGD) algorithm with Multiple Gossip Steps (MGS) after each model update step. It establishes the generalization error and excess error bounds for the DSGD-MGS algorithm in non-convex settings without the bounded gradients assumption. The paper established theoretical results showing that MGS can exponentially reduce the generalization error bound but however can not recover the performance of the centralized SGD algorithm. The paper also outlines the influence of various factors such as dataset size, number of nodes, spectral gap, MGS count, learning rate etc on the generalization error. The paper validates the theoretical findings with empirical experiments on CIFAR-10 dataset  (non-IID, $\\alpha=0.1$) trained on LeNet with 50 clients.", "questions": "1. What are the dataset, model architecture and number of nodes used for Figure 1 plot? It is important to highlight the number of nodes in Figure 1 as it indicates a practical upper bound for number of MGS steps. \n2. Spectral gap is defined as $\\delta = 1- |\\lambda_2|$ which indicates that larger spectral gap results in better connectivity with $\\delta =1$ for fully connected graphs. However, remark 5 indicates to use graphs with smaller spectral gap to reduce the generalization error bound. Also, for fixed graph structure (say ring), increasing number of nodes $m$ (reducing $\\delta$) will result in poor performance empirically but the remark 5 suggests to increase the number of nodes. This is a bit counterintuitive, can authors shed some light on point 2 and 5 of remark 5?\n3. Consider an decentralized setup with n nodes and doubly stochastic weight matrix (say undirected ring topology) and full communication in each MGS. In this scenario, when we set number of multi-gossip steps to n at each iteration, DSGD-MGS should recover the same performance as centralized SGD. In the extreme case, one could have a fully connected network with DSGD-MGS and this should be able to recover centralized SGD generalization performance at least for linear neural networks. However, the paper claims that decentralized training cannot fully achieve the generalization performance of centralized training solely by increasing the number of MGS steps. Why is this the case? In particular, what is the bottleneck here when functionally DSGD with fully connected graph ($\\delta=1$) is same as centralized SGD? \n4. Can the authors add centralized SGD baseline to Figure 2?\n5. $\\gamma$ is introduced in Lemma 2 but not described till Theorem 2. Please include $\\gamma$'s equation in Lemma 2 itself.", "limitations": "Multi-step gossip comes at the additional cost of communication which is a major overhead for decentralized settings that will limit the practical application of the DSGD-MGS method.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper claims to be the first to establish the generalization error and excess error bounds for the DSGD-MGS algorithm in non-convex settings without the bounded gradients assumption.\n2. The paper clearly mentions all the assumptions and theoretically shows the mechanism by which MGS enhances the generalization performance of decentralized training models through an exponential reduction $O(e^{\\frac{-\\delta \\gamma Q}{4}})$ in optimization error.\n3. The paper relies on on-average model stability to remove the bounded gradient assumption making the theoretical results more general.\n4. The paper clearly presents the remarks for the theorems explaining the impact of various terms on generalization error. The paper also makes recommendations regarding the hyper-parameters such as number of nodes, spectral gap, learning rate etc that will result in reduction in the generalization error based on the theoretical results.  \n5. The paper present experimental results, on a small scale dataset and model architecture i.e., CIFAR-10 with Lenet, validating the theoretical claims. Ablation studies are presented in Appendix (Figure 4 and Figure 5). \n\nWeaknesses:\nNo major weakness.", "was_revised": true, "final_justification": "Authors have addressed all my concerns", "rebuttal": "*Reply to Strengths and Weaknesses:*\n \nThank you very much for your careful review and encouraging feedback. We are delighted by your recognition of our work as **the first to establish generalization and excess error bounds for the DSGD‑MGS algorithm in non‑convex settings without relying on a bounded gradients assumption**.\n\nWe appreciate your highlighting our use of on‑average model stability **to effectively relax the common bounded‑gradient requirement**, thereby rendering our theoretical results **more broadly applicable—a goal we set out to achieve for decentralized learning scenarios**. We are also pleased that you found our explanation of how MGS enhances generalization—through an exponential reduction in optimization error of order $\\mathcal{O}(e^{-\\gamma Q\\delta/4})$—to be clear and insightful.\n\nMoreover, we are grateful for your acknowledgement of our **detailed remarks following each theorem, in which we undertake a comprehensive analysis** of the influence of various terms on the generalization error and **provided practical recommendations** on key hyperparameters (e.g., number of nodes, spectral gap, learning rate). We hope these discussions will benefit both theorists and practitioners in tuning DSGD‑MGS.\n\nYour positive assessment of our experimental work is equally appreciated. Although our current experiments are limited to CIFAR‑10 with LeNet, our ablation studies (Appendix Figures 4 and 5) **have preliminarily validated the robustness of our theoretical findings**. To further strengthen our empirical validation, we will include additional experiments using ResNet‑18 on CIFAR‑100 in the revised manuscript, thereby evaluating our method in a larger‑scale setting.\n\nOnce again, thank you for emphasizing the strengths of our paper and noting the absence of significant weaknesses—your encouragement is invaluable. We will continue **to deepen and extend** this line of research under more general theoretical assumptions (such as non‑convex, non‑smooth loss functions) to advance our contributions further.\n\n---\n*Reply to Question 1:*\n\nThank you very much for your valuable question. To facilitate readers’ understanding of the experimental setup in Figure 1, we will augment the figure caption in the revised manuscript with the following details: the dataset is CIFAR‑10, the model architecture is LeNet, the decentralized network consists of 50 nodes, and data heterogeneity is generated via a Dirichlet(α=0.3) partition.\n\n---\n*Reply to Question 2:*\n\nThank you very much for your careful questions regarding points 2 and 5 in Remark 5. We clarify and correct our statements on the spectral gap and number of nodes’ impact on the generalization error as follows:\n\n1. **Remark 5, Point 5 (Spectral Gap)**\n\n   * In the original manuscript, we mistakenly wrote that “using a **smaller** spectral gap $\\delta$ (which implies a larger $\\rho$) reduces the generalization error.” In fact, by Theorem 3, the generalization error bound satisfies\n\n     $$\n       \\epsilon_{\\mathrm{gen}} = \\mathcal{O}\\bigl(\\rho^T e^{-\\tfrac{\\delta\\gamma Q}{4}}\\bigr).\n     $$\n\n     To decrease $\\epsilon_{\\mathrm{gen}}$, one should **increase** $\\delta$ (and correspondingly **decrease** $\\rho$). We have corrected this in the revised manuscript to:\n\n     > “Use a communication topology with a **larger** spectral gap $\\delta$ (which implies a **smaller** $\\rho$).”\n   * Empirically, Figure 2(b) confirms this correction: the exp topology’s spectral gap exceeds that of the ring topology, and its generalization error bound is indeed lower. We have also carefully reviewed the other conclusions in Remark 5 to ensure overall consistency and correctness.\n\n2. **Remark 5, Point 2 (Number of Nodes $m$)**\n\n   * Ignoring $m$-independent constants, Theorem 3 gives\n\n     $$\n       \\epsilon_{\\mathrm{gen}} = \\mathcal{O}\\Bigl(\\tfrac{1}{m} e^{-\\tfrac{\\delta\\gamma Q}{4}}\\Bigr).\n     $$\n   * For a ring topology, the paper \"*Topology‑Aware Generalization of Decentralized SGD*\" shows\n\n     $$\n       \\delta = \\frac{16\\pi^2}{3m^2}.\n     $$\n\n     Substituting yields\n\n     $$\n       f(m) = \\frac{1}{m}\\exp\\Bigl(-\\frac{4\\pi^2\\gamma Q}{3m^2}\\Bigr).\n     $$\n   * Mathematical analysis reveals:\n\n     > When $m > \\sqrt{\\tfrac{4\\pi^2\\gamma Q}{3}}$, $f(m)$ **decreases** as $m$ increases.\n     > Given the definition\n\n     $$\n       \\gamma = \\frac{\\delta}{\\delta^2 + 8\\delta + (4+2\\delta)\\,\\lambda_{\\max}^2(I - W)},\n     $$\n\n     one can show $\\gamma < \\tfrac18$. Taking a typical value $Q = 10$ yields a threshold of approximately 5, so for $m > 5$, increasing the number of nodes reduces the generalization error.\n   * **Intuition**: Although increasing $m$ shrinks the spectral gap, it also increases the total data volume (per-node data remains fixed), which benefits generalization. The gain from larger data volume outweighs the loss from a smaller gap, leading to a net decrease in error.\n   * Our experiments in Figure 2 (varying client number from 25 to 50) corroborate this trend. A similar conclusion is supported by \"*Stability and Generalization of the Decentralized Stochastic Gradient Descent*\".\n\n3. **Revisions and Future Work**\n\n   * We have corrected points 2 and 5 in Remark 5 in the revised manuscript and added detailed theoretical derivations and intuitive explanations to eliminate reader confusion.\n   * We will also include additional experiments across various topologies and network sizes to further validate the generality of these findings.\n\nOnce again, thank you for your in-depth review and valuable feedback!\n\n---\n*Reply to Question 3:*\n\nThank you very much for raising this important question. In Appendix Remark 9, we provide a detailed **consensus error** analysis to explain why, in practical decentralized settings, merely increasing the number of MGS steps does not fully recover the generalization performance of centralized SGD. We summarize the key points below:\n\n1. **Definition of Consensus Error**\n   Let\n\n   $$\n     x_t = \\mathbb{E}\\Bigl[\\tfrac{1}{m}\\sum_{k=1}^m||\\theta_k^{(t)}-\\bar\\theta^{(t)}||^2\\Bigr],\n   $$\n\n   where $\\bar\\theta^{(t)} = \\frac1m\\sum_{k=1}^m\\theta_k^{(t)}$ represents the parameter vector of centralized SGD at iteration $t$.\n\n2. **Recurrence Inequality and Residual Error**\n   In Appendix C, we show that\n\n   $$\n     x_{t+1}\\le \\rho^{2Q}\\bigl(2+24\\beta^2\\eta_t^2\\bigr)x_t +24\\rho^{2Q}(\\sigma^2+\\delta^2)\\eta_t^2,\n     \\tag{1}\n   $$\n\n   where $\\rho=|\\lambda_2(W)|<1$ and $\\sigma^2$ denotes gradient noise. This inequality reveals a **residual term** in each iteration that accumulates over time.\n\n3. **Error Accumulation for Finite $Q$**\n\n   * As $Q\\to\\infty$, $\\rho^{2Q}\\to0$, implying $x_t=0$ for all $t$ and thus equivalence to centralized SGD.\n   * Practically, $Q$ must remain finite, so $\\rho^{2Q}>0$. Each gossip round leaves a small residual error, which is subsequently amplified through iterations, leading to parameter divergence and a gap in generalization performance.\n\n4. **Fully Connected vs. Practical Decentralized Topologies**\n\n   * In a **fully connected graph**, $\\delta=1$ and thus $\\rho=0$. Even with $Q=1$, one achieves $x_t=0$, exactly matching centralized SGD. This aligns with your “functional equivalence” scenario.\n   * However, fully connected topologies incur $O(m^2)$ communication cost per round and impose stringent requirements on network bandwidth and stability, rendering them impractical at scale.\n\n5. **Practical Bottlenecks**\n\n   * **Communication–Computation Trade-off**: Finite $Q$ and limited bandwidth preclude zeroing out consensus error each round.\n   * **Topology Constraints**: Sparse graphs inherently have $\\rho>0$.\n   * **Gradient Noise Accumulation**: The residual error term $24\\rho^{2Q}(\\sigma^2+\\delta^2)\\eta_t^2$ accumulates gradient noise over iterations.\n\n6. **Revisions and Further Clarifications**\n\n   * In the revised manuscript, we will explicitly state in Remark 9 and the main text that our conclusions are **restricted to decentralized topologies** with $\\delta\\in[0,1)$ (i.e., $\\rho>0$). Because the case $\\delta=1$ recovers the performance of centralized SGD.\n\nThank you again for your thorough review and valuable feedback!\n\n---\n*Reply to Question 4:*\n\nCertainly. We have added the centralized SGD baseline to Figure 2 in the revised manuscript. The results show that centralized SGD consistently achieves the lowest weight distance and loss distance across all iterations, highlighting its superior generalization performance. Due to NeurIPS rebuttal guidelines prohibiting additional PDF uploads or external links, we are unable to present the updated figure here, but it will be fully included in the revised submission.\n\n---\n*Reply to Question 5:*\n\nThank you very much for pointing out this misuse of notation. In fact, the **$\\gamma$ in Lemma 2** carries the same meaning as the $\\gamma$ in Lemma 1: it is an **arbitrary positive constant** (first introduced in **Appendix Lemma 4**, around **line 849**) whose purpose is to **tighten the final generalization error bound** by selecting an appropriate value. During the derivation of **Theorem 3**, the specific choice of $\\gamma$ appears just above **line 900** in the Appendix. By contrast, the **$\\gamma$ in Theorem 2** is a **topology‐dependent constant** and thus **differs** from the $\\gamma$ in Lemma 2. In the revised manuscript, we will correct this notation conflict by **renaming the $\\gamma$ in Theorem 2 to $\\tilde{\\gamma}$**, thereby eliminating any ambiguity. Thank you again for highlighting this issue; your suggestion **significantly enhances the rigor** of our paper.\n\n---\n\nThank you once again for your thorough review and invaluable comments. It is precisely because of the issues you raised that we were able to clarify our notation, refine our theoretical derivations, and supplement the revised manuscript with more comprehensive experiments and intuitive explanations. Your feedback has greatly enhanced the rigor and readability of our paper."}, {"review_id": "nPuyDPsjfD", "reviewer": "Reviewer_2yXa", "summary": "This work considers the efects of using Multi-Gossip Steps (MGS) in decentralized learning. From experimental records, MGS seems to be an effective method in improving performance and efficiency in decentralized learning, and a central question is to study whether MGS can make decentralized learning as good as the centralized version. \n\nIn this paper, they want to answer from the theoretical perspective why MGS works better by studying the generalization error and excess error of the MGS.They contribute an upper bound of the generalization error as sum of a term $I_1$ related to model stability and a term $I_2$ related to optimization error. Moreover, they attempt to compare the MGS with the centralized learning scheme when the number of gossip steps is large. They discover that the error bound obtained by taking the number of gossip steps to be large does not match the centralized SGD. If the error bound is tight, then this result indicates a negative answer to the centrall question aforementioned.  \n\nFrom these bounds they also offer suggestive strategies to practitioners on how to reduce generalization error, including increasing the MGS steps, decreasing the learning rate etc. These findings are also validated through experiments on the CIFAR datasets.", "questions": "While I understand the rationale behind the claims in Remark 5 as derived from your bounds—and I appreciate that they are supported empirically—I wonder if there are more intuitive explanations for choosing strategies 2 and 6. Specifically:\n1. It would be helpful to provide more insight into why a smaller learning rate improves generalization error. The explanation around Lines 280–281, while mathematically sound, appears closely tied to the specific form of the bound and may not provide a clear, generalizable intuition for practitioners.\n2. I am also curious about the recommendation to increase $m$. Intuitively, increasing $m$ makes the algorithm more decentralized and arguably further from the centralized baseline, which one might expect to hurt performance due to increased communication noise or model divergence. Some discussion reconciling this intuition with the observed benefit in your bounds would strengthen the impact of the result.\n\nMinor:\n1. In Line 142, do you mean $S^{(ij)}=(S_1,...,S_{j-1},S_j^{(i)}, S_{j+1},...,S_m)$. \n2. In Line 211, I guess the second $\\theta_k^{(T)}$ is supposed to be $\\theta_k^{(T)}(i,j)$?\n3. In Line 234, from Lemma 3, it seems to miss a square root.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper tackles an important and fundamental problem in decentralized federated learning from a theoretical perspective. While much of the literature focuses on optimization error, this work takes a significant step by analyzing the generalization error of Decentralized SGD (DSGD) under MGS, which is of broad interest to the community and believed to be challenging.\n\nThe authors present their main claims in a reasonably clear and accessible manner. Notably, their analysis goes beyond the claimed focus on the number of gossip steps but also explores the influence of other key hyperparameters, providing a more comprehensive understanding of DSGD behavior.\n\nAlthough I have not verified the proofs in the appendix line by line, the results appear to be well-supported under the stated assumptions, and the bounds themselves seem plausible. The paper also offers thoughtful discussions on the implications of their findings, including practical takeaways and insights that could inform future work or empirical practices.\n\nSome of the claims initially seem counterintuitive, but the experimental results are convincing and effectively reinforce the theoretical conclusions. To the best of my knowledge, this is the first work that directly studies the generalization behavior of DSGD with message gossiping, and it presents a well-rounded treatment of this question.\n\nOverall, this is a solid and insightful contribution, and I believe it opens up several promising directions for follow-up work. I recommend acceptance to NeurIPS.", "was_revised": false, "final_justification": "", "rebuttal": "*Reply to Strengths And Weaknesses:*\n\nThank you very much for your **detailed reading** and **positive evaluation** of our work. We are particularly encouraged by your observation that our study is the **first** to systematically investigate, from a theoretical perspective, the **generalization error** of DSGD under the message gossiping mechanism (MGS) in decentralized federated learning—an angle of **significant importance** in the literature.\n\nWe are pleased that you found our analysis both **clear and comprehensive**, going **beyond** the number of gossip steps to examine the impact of other **key hyperparameters** on DSGD behavior. This broader theoretical guidance for **practical implementation** was precisely our goal, and your recognition of its **practical implications** is invaluable.\n\nWe also appreciate your note that some of our findings may initially seem **counterintuitive**, yet the **experimental results** convincingly support our theoretical analysis. We believe that this **combination of theory and empirical validation** will serve as a **useful reference** for future work.\n\nOnce again, thank you for your **affirmation and encouragement**. Your feedback not only **validates our efforts** but also **provides important direction** for our ongoing research. Additionally, we sincerely appreciate your **recommendation to accept our paper at NeurIPS**; this endorsement provides tremendous encouragement to our team.\n\n---\n*Reply  to Question 1:*\n\nThank you for your question. In fact, with respect to the generalization error, **smaller learning rates always yield better performance**, regardless of the specific schedule or form. In Theorem 2 of Sun et al. (“Stability and Generalization of the Decentralized Stochastic Gradient Descent”), it is proven that for DSGD, reducing the learning rate $\\eta$ directly **decreases the generalization error** regardless of the specific schedule or form.\n\nEmpirically, we measure generalization error as$\\bigl|R(\\theta) - R_S(\\theta)\\bigr|,$where $R(\\theta)$ is the test loss and $R_S(\\theta)$ is the training loss. Early in training, this gap is small, but it grows over iterations roughly on the order of $\\mathcal{O}(T^\\alpha)$. In the extreme case $\\eta=0$, the model never updates and the gap remains near zero, confirming that **the smaller $\\eta$, the smaller the generalization error** for a fixed iteration budget $T$.\n\nHowever, in practice our primary concern is the **test loss** $R(\\theta)$, since lower test loss on unseen data implies a smaller **excess error**$R(\\theta) - R(\\theta^\\star),$ where $R(\\theta^\\star)$ is constant. The excess error admits the upper bound$\n\\epsilon_{\\text{opt}} + \\epsilon_{\\text{gen}},$with$\\epsilon_{\\text{opt}} = \\mathcal{O}\\bigl(\\tfrac{1}{T\\eta}\\bigr)$ and $\\epsilon_{\\text{gen}}$ increasing in $\\eta$. Thus, **larger $\\eta$** reduces optimization error $\\epsilon_{\\text{opt}}$, while **smaller $\\eta$** reduces generalization error $\\epsilon_{\\text{gen}}$, yielding a **trade‑off** in $\\eta$. Experimentally (Appendix Figure 3), we observe exactly this trade‑off: **$\\eta=0.03$** achieves the minimum test loss. \n\nIn summary, **practitioners should select an intermediate learning rate** that balances optimization and generalization to minimize the final test loss (excess error).\n\n---\n\n*Reply to Question 2:*\n\nThank you for your thoughtful question. Your concern about the effect of increasing $m$ aligns closely with Reviewer rX3y’s Question 2—**namely, why increasing the number of nodes $m$, which seemingly decentralizes the system further, leads to a reduction in generalization error**. In our response to Reviewer rX3y, we provided a more detailed theoretical explanation, which we summarize here.\n\nSpecifically, under a Ring topology, we analyzed the relationship between $m$ and the generalization bound $\\epsilon_{\\text{gen}}$, and showed that **when $m$ exceeds a certain threshold, increasing $m$ actually decreases $\\epsilon_{\\text{gen}}$** by studying the monotonicity of a function $f(m)$ that appears in the bound.\n\n**Intuitively**, while a larger number of nodes introduces a more decentralized setup—which may suggest increased communication noise or divergence—**it simultaneously increases the total training data size**. Since each node holds a fixed amount of local data $n$, the total dataset size scales as $mn$. **In our analysis, the benefit of having more data outweighs the drawbacks introduced by further decentralization**, leading to better generalization.\n\nThis insight is supported by both our theoretical analysis and empirical results. Furthermore, a similar conclusion is drawn in the work by Sun et al., *“Stability and Generalization of the Decentralized Stochastic Gradient Descent,”* further validating our findings.\n\nLastly, we acknowledge that our current manuscript provides limited discussion on the role of $m$. **We will include additional content in the revised version**—both to provide this intuitive interpretation and to elaborate on the theoretical analysis referenced in our reply to Reviewer rX3y—to clarify and strengthen this potentially counterintuitive result. We greatly appreciate your suggestion.\n\n---\n\n*Reply to minor 1:*\n\nThank you for your careful reading—you are absolutely right!\nThe correct notation should indeed be\n\n$$\nS^{(ij)} = (S_1, \\ldots, S_{j-1}, S_j^{(i)}, S_{j+1}, \\ldots, S_m).\n$$\n\nWe have corrected the typo from \"\\$j-1\\$\" to \"\\$j+1\\$\" in the revised version. Your comment contributes significantly to improving the clarity and rigor of the manuscript—we greatly appreciate it.\n\n---\n*Reply to minor 2:*\n\nThank you for catching this typo—your attention to detail is much appreciated.\nYou are absolutely right: the second occurrence of \\$\\theta\\_k^{(T)}\\$ in Line 211 should indeed be \\$\\theta\\_k^{(T)}(i,j)\\$. We have corrected this in the revised version of the manuscript.\n\n---\n*Reply to minor 3:*\nYes, you are correct. We have corrected the error in the revised version from \\$||\\nabla R\\_{S}(\\theta)|| \\leq 2\\beta R\\_{S}(\\theta)\\$ to \\$||\\nabla R\\_{S}(\\theta)||^2 \\leq 2\\beta R\\_{S}(\\theta)\\$. It is important to note that this was merely a typographical mistake and does not affect the correctness of the subsequent proofs. Thank you again for your careful and thorough reading—your feedback has greatly contributed to the rigor and completeness of our paper.\n\n---\nWe sincerely thank you for your careful reading, insightful comments, and encouraging feedback. Your recognition of our theoretical contributions and practical implications is deeply appreciated. We are especially grateful for your recommendation to accept our paper to NeurIPS—it means a great deal to us and provides strong motivation for our continued work."}]

Author rebuttal:

Meta-review: This paper presents a very interesting theoretical study of decentralized versus centralized optimization in the context of training neural networks. The authors establish two key findings: first, that MGS allows an exponential reduction in optimization error; second, that despite this improvement, a non-trivial gap with centralized learning persists. These results are well supported by experiments and, to the best of my knowledge, this is among the first works to obtain such insights.

I believe the paper’s main strength lies in its novelty and the depth of its analysis. Rather than reiterating the view that centralized learning is simply a special case of decentralized learning, the work demonstrates that the relationship is much more subtle and requires careful theoretical study. This provides an important contribution to our understanding of optimization in neural network training and the potential scalability of decentralized learning of NNs.

The authors have also provided an excellent rebuttal that clarified the reviewers’ concerns. Given the originality of the results, the strong experimental support, and the convincing responses during the discussion phase, all reviewers recommend acceptance. I concur with their assessment and also recommend acceptance.
Decision: Accept (spotlight)