Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Asynchronous Speedup in Decentralized Optimization
 
research article

Asynchronous Speedup in Decentralized Optimization

Even, Mathieu
•
Hendrikx, Hadrien  
•
Massoulie, Laurent
2025
IEEE Transactions on Automatic Control

In decentralized optimization, nodes of a communication network each possess a local objective function, and communicate using gossip-based methods in order to minimize the average of these per-node functions. While synchronous algorithms are heavily impacted by a few slow nodes or edges in the graph (the straggler problem), their asynchronous counterparts are notoriously harder to parameterize. Indeed, their convergence properties for networks with heterogeneous communication and computation delays have defied analysis so far. In this article, we use a continuized framework to analyze asynchronous algorithms in networks with delays. Our approach yields a precise characterization of convergence time and of its dependence on heterogeneous delays in the network. Our continuized framework benefits from the best of both continuous and discrete worlds: the algorithms it applies to are based on event-driven updates. They are thus essentially discrete, and hence, readily implementable. Yet their analysis is essentially in continuous time, relying in part on the theory of delayed ordinary differential equations. Our algorithms moreover achieve an asynchronous speedup: their rate of convergence is controlled by the eigengap of the network graph weighted by local delays instead of the network-wide worst-case delay as in previous analyses. Our methods thus enjoy improved robustness to stragglers.

  • Details
  • Metrics
Type
research article
DOI
10.1109/TAC.2024.3454386
Scopus ID

2-s2.0-105001077323

Author(s)
Even, Mathieu

École Normale Supérieure

Hendrikx, Hadrien  

École Polytechnique Fédérale de Lausanne

Massoulie, Laurent

École Normale Supérieure

Date Issued

2025

Published in
IEEE Transactions on Automatic Control
Volume

70

Issue

3

Start page

1467

End page

1482

Subjects

Asynchronous

•

decentralized

•

gossip

•

optimization

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
EPFL  
FunderFunding(s)Grant NumberGrant URL

Agence Nationale de la Recherche

ANR19-P3IA-0001

Available on Infoscience
May 5, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/249671
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés