DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm

• URL: http://arxiv.org/abs/2306.00256v1
• Date: Thu, 1 Jun 2023 00:29:52 GMT
• Title: DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm
• Abstract summary: Decentralized Gradient Descent (SGD) is an emerging neural network training approach that enables multiple agents to train a model collaboratively and simultaneously. In this paper, we propose underlineDecentralized underlineSGD with underlineCommunication-optimal underlineExact underlineConsensus underlineAlgorithm (DSGD- CECA) Our proof is based on newly discovered properties of gossip weight matrices and a novel approach to combine them with DSG
• Score: 30.728112082204724
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decentralized Stochastic Gradient Descent (SGD) is an emerging neural network training approach that enables multiple agents to train a model collaboratively and simultaneously. Rather than using a central parameter server to collect gradients from all the agents, each agent keeps a copy of the model parameters and communicates with a small number of other agents to exchange model updates. Their communication, governed by the communication topology and gossip weight matrices, facilitates the exchange of model updates. The state-of-the-art approach uses the dynamic one-peer exponential-2 topology, achieving faster training times and improved scalability than the ring, grid, torus, and hypercube topologies. However, this approach requires a power-of-2 number of agents, which is impractical at scale. In this paper, we remove this restriction and propose \underline{D}ecentralized \underline{SGD} with \underline{C}ommunication-optimal \underline{E}xact \underline{C}onsensus \underline{A}lgorithm (DSGD-CECA), which works for any number of agents while still achieving state-of-the-art properties. In particular, DSGD-CECA incurs a unit per-iteration communication overhead and an $\tilde{O}(n^3)$ transient iteration complexity. Our proof is based on newly discovered properties of gossip weight matrices and a novel approach to combine them with DSGD's convergence analysis. Numerical experiments show the efficiency of DSGD-CECA.

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)
• SPIN: Decentralized Swarm Control via Tensorized Policy Coordination [0.0]
  This paper introduces the Swarm Policy Interference Network (SPIN) framework.<n>We factorize the joint policy tensors of local multi-agent cliques into Matrix Product State chains.<n>To bridge local continuous spatial geometry with this discrete algebraic backend, we introduce a decoupled, hybrid neuro-symbolic control pipeline.
  arXiv  Detail & Related papers  (2026-05-25T07:45:51Z)
• Beyond Quantity: Trajectory Diversity Scaling for Code Agents [51.71414642763219]
  Trajectory Diversity Scaling is a data synthesis framework for code agents that scales performance through diversity rather than raw volume.<n> TDScaling integrates four innovations: (1) a Business Cluster mechanism that captures real-service logical dependencies; (2) a blueprint-driven multi-agent paradigm that enforces trajectory coherence; and (3) an adaptive evolution mechanism that steers toward long-tail scenarios.
  arXiv  Detail & Related papers  (2026-02-03T07:43:03Z)
• DiffGRM: Diffusion-based Generative Recommendation Model [63.35379395455103]
  Generative recommendation (GR) is an emerging paradigm that represents each item via a tokenizer as an n-digit semantic ID (SID)<n>We propose DiffGRM, a diffusion-based GR model that replaces the autoregressive decoder with a masked discrete diffusion model (MDM)<n> Experiments show consistent gains over strong generative and discriminative recommendation baselines on multiple datasets.
  arXiv  Detail & Related papers  (2025-10-21T03:23:32Z)
• Fully First-Order Methods for Decentralized Bilevel Optimization [17.20330936572045]
  This paper focuses on decentralized bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works.
  arXiv  Detail & Related papers  (2024-10-25T06:11:43Z)
• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• 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)
• Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
  We propose a novel approach to the problem of shared parallel computation. By combining two strategies into a unified framework, DPSGD is a better trade computation framework. The potential gains can be achieved by DPSGD on a deep learning (DRL) problem (Latent Diletrichal inference) and on a deep learning (DRL) problem (advantage actor - A2C)
  arXiv  Detail & Related papers  (2022-10-06T13:06:08Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  We propose to solve a regularized distributionally robust learning problem in the decentralized setting. By adding a Kullback-Liebler regularization function to the robust min-max optimization problem, the learning problem can be reduced to a modified robust problem. We show that our proposed algorithm can improve the worst distribution test accuracy by up to $10%$.
  arXiv  Detail & Related papers  (2022-08-29T18:01:42Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  Reinforcement learning (RL) has been widely investigated and shown to be a promising solution for decision-making and optimal control processes. We propose an adaptive ADMM (asI-ADMM) algorithm and apply it to decentralized RL with edge-computing-empowered IIoT networks. Experiment results show that our proposed algorithms outperform the state of the art in terms of communication costs and scalability, and can well adapt to complex IoT environments.
  arXiv  Detail & Related papers  (2021-06-30T16:49:07Z)
• Training Recommender Systems at Scale: Communication-Efficient Model and Data Parallelism [56.78673028601739]
  We propose a compression framework called Dynamic Communication Thresholding (DCT) for communication-efficient hybrid training. DCT reduces communication by at least $100times$ and $20times$ during DP and MP, respectively. It improves end-to-end training time for a state-of-the-art industrial recommender model by 37%, without any loss in performance.
  arXiv  Detail & Related papers  (2020-10-18T01:44:42Z)
• 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)
• A(DP)$^2$SGD: Asynchronous Decentralized Parallel Stochastic Gradient Descent with Differential Privacy [15.038697541988746]
  A popular distributed learning strategy is federated learning, where there is a central server storing the global model and a set of local computing nodes updating the model parameters with their corresponding data. In this paper, we present a differentially private version of asynchronous decentralized parallel SGD framework, or A(DP)$2$SGD for short, which maintains communication efficiency of ADPSGD and prevents the inference from malicious participants.
  arXiv  Detail & Related papers  (2020-08-21T00:56:22Z)
• O(1) Communication for Distributed SGD through Two-Level Gradient Averaging [0.0]
  We introduce a strategy called two-level gradient averaging (A2SGD) to consolidate all gradients down to merely two local averages per worker. Our theoretical analysis shows that A2SGD converges similarly like the default distributed SGD algorithm.
  arXiv  Detail & Related papers  (2020-06-12T18:20:52Z)
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
  We introduce a unified convergence analysis of decentralized communication methods. We derive universal convergence rates for several applications. Our proofs rely on weak assumptions.
  arXiv  Detail & Related papers  (2020-03-23T17:49:15Z)

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.