Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

• URL: http://arxiv.org/abs/2606.07496v1
• Date: Fri, 05 Jun 2026 17:51:11 GMT
• Title: Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
• Abstract summary: 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.
• Score: 8.185454167395326
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number \(κ=L/μ\) and the network spectral gap \(1-β\). Although deterministic decentralized methods can simultaneously achieve accelerated \(\sqrtκ\) and \(1/\sqrt{1-β}\) dependences, no existing stochastic method attains both improvements at once. In this paper, we propose \emph{Multi-Gossip Accelerated DSGD} (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal--dual extrapolation with multi-round fast gossip averaging. 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. We show that MG-ADSGD achieves the communication complexity \[ \widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right), \] where \(ε\) denotes the target accuracy, \(n\) is the number of nodes, and \(σ^2\) is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of $ε$.

Related papers

• 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)
• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
  We propose Differentially Private Gradient Push with Compressed communication (termedfrac-CSGP) for decentralized learning graphs.<n>For general non-math and smooth objective functions, we show that our algorithm is designed to maintain high accuracy and efficient communication.
  arXiv  Detail & Related papers  (2025-12-15T17:37:02Z)
• Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training [64.84977068837371]
  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.
  arXiv  Detail & Related papers  (2025-10-09T09:14:47Z)
• Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework [33.417831716314495]
  Decentralized gradient descent (DGD) and diffusion are workhorses in decentralized machine learning.<n>We propose a principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies.<n>The use of these tools yields tight convergence bounds, both in the noise-free and noisy regimes.
  arXiv  Detail & Related papers  (2025-03-18T15:36:36Z)
• 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)
• Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps [4.471962177124311]
  In distributed machine learning, linear variables across multiple agents with different data poses significant challenges. In this paper we show that a framework that achieves the Lagrangian convergence on the primal variable requires no inter-agent communication.
  arXiv  Detail & Related papers  (2024-07-02T22:14:54Z)
• A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization [49.17384566985762]
  We propose a communication-efficient method MG-Skip for decentralized composite (smooth + nonsmooth) optimization.<n>For any undirected and connected networks, MG-Skip allows for the multi-gossip communications to be skipped in most iterations in the strongly convex setting.<n> MG-Skip achieves provable communication acceleration, thereby validating the advantages of local updates in the nonsmooth setting.
  arXiv  Detail & Related papers  (2023-12-19T05:13:16Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41: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.