Enhancing Parallelism in Decentralized Stochastic Convex Optimization

• URL: http://arxiv.org/abs/2506.00961v1
• Date: Sun, 01 Jun 2025 11:17:32 GMT
• Title: Enhancing Parallelism in Decentralized Stochastic Convex Optimization
• Authors: Ofri Eisen, Ron Dorfman, Kfir Y. Levy,
• Abstract summary: We propose Decentralized Anytime SGD, a novel decentralized learning algorithm that significantly extends the critical parallelism threshold.<n>Within the convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that surpasses the current state-of-the-art.
• Score: 10.632248569865236
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decentralized learning has emerged as a powerful approach for handling large datasets across multiple machines in a communication-efficient manner. However, such methods often face scalability limitations, as increasing the number of machines beyond a certain point negatively impacts convergence rates. In this work, we propose Decentralized Anytime SGD, a novel decentralized learning algorithm that significantly extends the critical parallelism threshold, enabling the effective use of more machines without compromising performance. Within the stochastic convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that surpasses the current state-of-the-art, allowing larger networks to achieve favorable statistical guarantees and closing the gap with centralized learning in highly connected topologies.

Related papers

• From promise to practice: realizing high-performance decentralized training [8.955918346078935]
  Decentralized training of deep neural networks has attracted significant attention for its theoretically superior scalability over synchronous data-parallel methods like All-Reduce. This paper identifies three key factors that can lead to speedups over All-Reduce training and constructs a runtime model to determine when, how, and to what degree decentralization can yield shorter per-it runtimes.
  arXiv  Detail & Related papers  (2024-10-15T19:04:56Z)
• DRACO: Decentralized Asynchronous Federated Learning over Row-Stochastic Wireless Networks [7.389425875982468]
  We propose DRACO, a novel method for decentralized asynchronous Descent (SGD) over row-stochastic gossip wireless networks.<n>Our approach enables edge devices within decentralized networks to perform local training and model exchanging along a continuous timeline.<n>Our numerical experiments corroborate the efficacy of the proposed technique.
  arXiv  Detail & Related papers  (2024-06-19T13:17:28Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  We take a closer theoretical look at Independent Subnetwork Training (IST) IST is a recently proposed and highly effective technique for solving the aforementioned problems. We identify fundamental differences between IST and alternative approaches, such as distributed methods with compressed communication.
  arXiv  Detail & Related papers  (2023-06-28T18:14:22Z)
• Scalable Optimal Margin Distribution Machine [50.281535710689795]
  Optimal margin Distribution Machine (ODM) is a newly proposed statistical learning framework rooting in the novel margin theory. This paper proposes a scalable ODM, which can achieve nearly ten times speedup compared to the original ODM training method.
  arXiv  Detail & Related papers  (2023-05-08T16:34:04Z)
• Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks [8.860889476382594]
  Decentralized optimization with time-varying networks is an emerging paradigm in machine learning. It saves remarkable communication overhead in large-scale deep training and is more robust in wireless scenarios especially when nodes are moving.
  arXiv  Detail & Related papers  (2022-11-01T15:37:54Z)
• Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning [55.198301429316125]
  Machine learning (ML) is a key technique for big-data-driven modelling and analysis of massive Internet of Things (IoT) based intelligent and ubiquitous computing. For fast-increasing applications and data amounts, distributed learning is a promising emerging paradigm since it is often impractical or inefficient to share/aggregate data. This paper studies the problem of training an ML model over decentralized systems, where data are distributed over many user devices.
  arXiv  Detail & Related papers  (2022-02-07T15:04:15Z)
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping [77.53019031244908]
  We present a novel decentralized learning framework based on nonlinear gossiping (NGO), that enjoys an appealing finite-time consensus property to achieve better synchronization. Our analysis on how communication delay and randomized chats affect learning further enables the derivation of practical variants.
  arXiv  Detail & Related papers  (2021-11-04T15:36:25Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• Decentralized Deep Learning using Momentum-Accelerated Consensus [15.333413663982874]
  We consider the problem of decentralized deep learning where multiple agents collaborate to learn from a distributed dataset. We propose and analyze a novel decentralized deep learning algorithm where the agents interact over a fixed communication topology. Our algorithm is based on the heavy-ball acceleration method used in gradient-based protocol.
  arXiv  Detail & Related papers  (2020-10-21T17:39:52Z)
• Optimal Complexity in Decentralized Training [45.468216452357375]
  We present a gossip-style decentralized algorithm that achieves the lower bound with only a gap. We show DeTAG enjoys faster convergence compared to baselines, especially on unshuffled data and in sparse networks.
  arXiv  Detail & Related papers  (2020-06-15T02:03:04Z)

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.