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

• URL: http://arxiv.org/abs/2510.07980v1
• Date: Thu, 09 Oct 2025 09:14:47 GMT
• Title: Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training
• Abstract summary: 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.<n>MultiGossip Steps (MGS) serve as a simple yet effective bridge between decentralized and centralized training.
• Score: 64.84977068837371
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization [8.185454167395326]
  We propose emphMulti-Gossip Accelerated DSGD (MG-ADSGD), a decentralized algorithm that combines Nesterov-type primal-dual with multi-round fast gossip averaging.<n>The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance.
  arXiv  Detail & Related papers  (2026-06-05T17:51:11Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization [16.020878731214083]
  This paper introduces a fully first-order decentralized method for decentralized Bilevel optimization, $textC2$DFB. $textC2$DFB is both compute- and communicate-efficient.
  arXiv  Detail & Related papers  (2024-10-18T02:00:45Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Decentralized SGD and Average-direction SAM are Asymptotically Equivalent [101.37242096601315]
  Decentralized gradient descent (D-SGD) allows collaborative learning on massive devices simultaneously without the control of a central server. Existing theories claim that decentralization invariably generalization.
  arXiv  Detail & Related papers  (2023-06-05T14:19:52Z)
• A Unified Momentum-based Paradigm of Decentralized SGD for Non-Convex Models and Heterogeneous Data [0.261072980439312]
  We propose a unified paradigm called U.MP, D-MP and GT-D, which provides a convergence guarantee for non general objectives. In theory we provide the convergence analysis objectives two approaches for these non-MP algorithms.
  arXiv  Detail & Related papers  (2023-03-01T02:13:22Z)
• A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning [1.713291434132985]
  We study a large-scale multi-agent minimax optimization problem, which models Geneimation Adversarial Networks (GANs) The overall objective is a sum of agents' private local objective functions. We show that FedGDA-GT converges linearly with a constant stepsize to global $epsilon GDA solution.
  arXiv  Detail & Related papers  (2022-06-02T16:31:16Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  We consider distributed variational inequalities (VIs) on domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that covers the settings of fully decentralized calculations. We theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone settings.
  arXiv  Detail & Related papers  (2021-06-15T17:45:51Z)
• Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
  Communication bottleneck has been a critical problem in large-scale deep learning. We propose a new distributed error feedback (DEF) algorithm, which shows better convergence than error feedback for non-efficient distributed problems. We also propose DEFA to accelerate the generalization of DEF, which shows better bounds than DEF.
  arXiv  Detail & Related papers  (2020-04-11T03:50:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.