Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training

Reply to Strengths And Weaknesses:

Thank 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.

We 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.

We 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.

Once 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.

Reply  to Question 1:

Thank 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.

Empirically, 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$.

However, 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$\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.

In summary, practitioners should select an intermediate learning rate that balances optimization and generalization to minimize the final test loss (excess error).

Reply to Question 2:

Thank 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.

Specifically, 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.

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.

This 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.

Lastly, 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.

Reply to minor 1:

Thank you for your careful reading—you are absolutely right! The correct notation should indeed be

We 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.

Reply to minor 2:

Thank you for catching this typo—your attention to detail is much appreciated. You 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.

Reply to minor 3: Yes, 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.

We 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.

Reply to Weakness 1:

Thank you for your question. While Le Bars et al. [ICML '24] also study optimization-dependent generalization bounds, our work differs in several key aspects:

1. 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).

2. 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.

3. 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.

4. 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.

5. Problem scope: While both papers study generalization, our focus is on gossip-based decentralized training, which introduces unique technical challenges and requires separate analysis.

In 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.

Reply to Weakness 2 and Question 1:

Thank 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.

Key modifications include (full proofs in the revision):

1. Assumption 2 now accounts for mini-batch sampling:

   $$\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}$$

2. Algorithm line 6 updated to mini-batch gradient:

   $$\theta_k^{(t,0)} = \theta_k^{(t)} - \eta_t \frac{1}{b}\sum_{i=1}^b \nabla \ell(\theta_k^{(t)}; Z_{ik})$$

3. Appendix line 855 probability adjusted:

   $$\mathbb{P}(\mathcal{E}(i,j)^c) \leq \sum_{t=1}^{t_0} \frac{b}{n} = \frac{b t_0}{n}$$

With these, the generalization bound becomes:

Note 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.

From 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.

Additionally, “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.

Reply to Weakness 3 and Question 4:

You 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.

However, 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.

Notably, 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.

We will add discussion of this future direction in the revised manuscript. Thank you again for your insightful suggestion.

Reply to Weakness 4 and Question 3:

We 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.

To be precise, our theoretical framework is not fully dependent on the PL condition. The PL condition is specifically invoked to facilitate the analysis of

which 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.

To 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.

Importantly, 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.

We appreciate the reviewer’s insightful comment and will clarify all these points explicitly in the revised manuscript.

Reply to Weakness 5 and Question 5:

We 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.

However, 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.

Reply to Question 2: Thank 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.

1. Theoretical vs. Practical Interplay: Our 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.

However, 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?

2. Experimental Commitment: To 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.

Thank you for your detailed and constructive feedback. We will revise our manuscript to address your comments.

Specifically, we will:

1. Clarify our novel contributions (L2-stability, non-convex/non-IID settings) compared to prior work.
2. Extend our analysis to mini-batch SGD, showing its impact on generalization, and add new experiments on ResNet-18/CIFAR-100.
3. Add an experimental study on the interplay between batch size and MGS steps under a fixed budget.
4. Discuss limitations (e.g., asymmetric graphs) and clarify the role of the PL condition as a technical tool.

We believe these changes will significantly strengthen our paper. Thank you again for your valuable guidance.

Reply to Strengths and Weaknesses:

Thank 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.

We 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.

Moreover, 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.

Your 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.

Once 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.

Reply to Question 1:

Thank 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.

Reply to Question 2:

Thank 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:

1. Remark 5, Point 5 (Spectral Gap)

   • 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

     $$\epsilon_{\mathrm{gen}} = \mathcal{O}\bigl(\rho^T e^{-\tfrac{\delta\gamma Q}{4}}\bigr).$$

     To decrease $\epsilon_{\mathrm{gen}}$, one should increase $\delta$ (and correspondingly decrease $\rho$). We have corrected this in the revised manuscript to:

     “Use a communication topology with a larger spectral gap $\delta$ (which implies a smaller $\rho$).”

   • 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.

2. Remark 5, Point 2 (Number of Nodes $m$)

   • Ignoring $m$-independent constants, Theorem 3 gives

     $$\epsilon_{\mathrm{gen}} = \mathcal{O}\Bigl(\tfrac{1}{m} e^{-\tfrac{\delta\gamma Q}{4}}\Bigr).$$

   • For a ring topology, the paper "Topology‑Aware Generalization of Decentralized SGD" shows

     $$\delta = \frac{16\pi^2}{3m^2}.$$

     Substituting yields

     $$f(m) = \frac{1}{m}\exp\Bigl(-\frac{4\pi^2\gamma Q}{3m^2}\Bigr).$$

   • Mathematical analysis reveals:

     When $m > \sqrt{\tfrac{4\pi^2\gamma Q}{3}}$, $f(m)$ decreases as $m$ increases. Given the definition

     $$\gamma = \frac{\delta}{\delta^2 + 8\delta + (4+2\delta)\,\lambda_{\max}^2(I - W)},$$

     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.

   • 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.

   • 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".

3. Revisions and Future Work

   • 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.
   • We will also include additional experiments across various topologies and network sizes to further validate the generality of these findings.

Once again, thank you for your in-depth review and valuable feedback!

Reply to Question 3:

Thank 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:

1. Definition of Consensus Error Let

   $$x_t = \mathbb{E}\Bigl[\tfrac{1}{m}\sum_{k=1}^m||\theta_k^{(t)}-\bar\theta^{(t)}||^2\Bigr],$$

   where $\bar\theta^{(t)} = \frac1m\sum_{k=1}^m\theta_k^{(t)}$ represents the parameter vector of centralized SGD at iteration $t$.

2. Recurrence Inequality and Residual Error In Appendix C, we show that

   $$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, \tag{1}$$

   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.

3. Error Accumulation for Finite $Q$

   • As $Q\to\infty$, $\rho^{2Q}\to0$, implying $x_t=0$ for all $t$ and thus equivalence to centralized SGD.
   • 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.

4. Fully Connected vs. Practical Decentralized Topologies

   • 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.
   • 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.

5. Practical Bottlenecks

   • Communication–Computation Trade-off: Finite $Q$ and limited bandwidth preclude zeroing out consensus error each round.
   • Topology Constraints: Sparse graphs inherently have $\rho>0$.
   • Gradient Noise Accumulation: The residual error term $24\rho^{2Q}(\sigma^2+\delta^2)\eta_t^2$ accumulates gradient noise over iterations.

6. Revisions and Further Clarifications

   • 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.

Thank you again for your thorough review and valuable feedback!

Reply to Question 4:

Certainly. 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.

Reply to Question 5:

Thank 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.

Thank 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.