Asynchronous and Stochastic Distributed Resource Allocation

• URL: http://arxiv.org/abs/2509.01172v1
• Date: Mon, 01 Sep 2025 06:47:23 GMT
• Title: Asynchronous and Stochastic Distributed Resource Allocation
• Authors: Qiang Li, Michal Yemini, Hoi-To Wai,
• Abstract summary: We consider a distributed system with multiple workers and a coordinating server with heterogeneous computation and communication times.<n>We explore an approximate primal-dual approach with the aim of adhering to the resource budget constraints.<n>We prove its convergence in the second moment to the saddle point solution of the approximate problem.
• Score: 27.163306014960515
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work proposes and studies the distributed resource allocation problem in asynchronous and stochastic settings. We consider a distributed system with multiple workers and a coordinating server with heterogeneous computation and communication times. We explore an approximate stochastic primal-dual approach with the aim of 1) adhering to the resource budget constraints, 2) allowing for the asynchronicity between the workers and the server, and 3) relying on the locally available stochastic gradients. We analyze our Asynchronous stochastic Primal-Dual (Asyn-PD) algorithm and prove its convergence in the second moment to the saddle point solution of the approximate problem at the rate of $O(1/t)$, where $t$ is the iteration number. Furthermore, we verify our algorithm numerically to validate the analytically derived convergence results, and demonstrate the advantages of utilizing our asynchronous algorithm rather than deploying a synchronous algorithm where the server must wait until it gets update from all workers.

Related papers

• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  We introduce Ringleader ASGD, the first asynchronous algorithm that attains the theoretical lower bounds for parallel computation.<n>Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary gradient and even time-varying speeds.
  arXiv  Detail & Related papers  (2025-09-26T19:19:15Z)
• A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks [21.66341372216097]
  A challenging problem in decentralized optimization is to develop algorithms with fast convergence on random time topologies under unreliable bandwidth-constrained communication network.<n>This paper introduces a novel approximation approach with a Fully Primal Dual Algorithm (FSPDA) framework.<n> Numerical experiments show the benefits of the FSPDA algorithms.
  arXiv  Detail & Related papers  (2024-10-24T14:26:58Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users [95.77678166036561]
  We propose a UCB-type algorithm with delicate communication protocols. We give sub-linear regret bounds on par with those achieved in the synchronous framework. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.
  arXiv  Detail & Related papers  (2024-02-26T05:31:14Z)
• Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity [85.92481138826949]
  We develop a new method-Shadowheart SGD-that provably improves the time complexities of all previous centralized methods. We also consider the bidirectional setup, where broadcasting from the server to the workers is non-negligible, and develop a corresponding method.
  arXiv  Detail & Related papers  (2024-02-07T12:15:56Z)
• Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimization [13.119144971868632]
  We introduce Asynchronous SGD on Graphs (AGRAF SGD) -- a general algorithmic framework that covers asynchronous versions of many popular algorithms. We provide rates of convergence under much milder assumptions than previous decentralized asynchronous computation works.
  arXiv  Detail & Related papers  (2023-11-01T11:58:16Z)
• AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
  We analyze asynchronous-type algorithms for distributed SGD in the heterogeneous setting. As a by-product of our analysis, we also demonstrate guarantees for gradient-type algorithms such as SGD with random tightness.
  arXiv  Detail & Related papers  (2023-10-31T13:44:53Z)
• 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)
• Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach [6.187780920448871]
  We propose a novel continuous-time framework to analyze asynchronous algorithms. We describe a fully asynchronous decentralized algorithm to minimize the sum of smooth and strongly convex functions.
  arXiv  Detail & Related papers  (2021-06-07T13:09:25Z)

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.