Decentralized Consensus Optimization with Asynchrony and Delays

Abstract

We propose an asynchronous, decentralized algorithm for consensus optimization. The algorithm runs over a network in which the agents communicate with their neighbors and perform local computation. In the proposed algorithm, each agent can compute and communicate independently at different times, for different durations, with the information it has even if the latest information from its neighbors is not yet available. Such an asynchronous algorithm reduces the time that agents would otherwise waste idle because of communication delays or because their neighbors are slower. It also eliminates the need for a global clock for synchronization. Mathematically, the algorithm involves both primal and dual variables, uses fixed step-size parameters, and provably converges to the exact solution under a bounded delay assumption and a random agent assumption. When running synchronously, the algorithm performs just as well as existing competitive synchronous algorithms such as PG-EXTRA, which diverges without synchronization. Numerical experiments confirm the theoretical findings and illustrate the performance of the proposed algorithm.

added a table for comparison between related algorithms; added a numerical comparison with asynchronous decentralized ADMM

References in corpus (10)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• An inertial forward-backward algorithm for monotone inclusions
• Sensor Networks with Random Links: Topology Design for Distributed Consensus
• Distributed Pareto Optimization via Diffusion Strategies
• Coordinate Friendly Structures, Algorithms and Applications
• Stability and Performance Limits of Adaptive Primal-Dual Networks
• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• Asynchronous Distributed Optimization using a Randomized Alternating Direction Method of Multipliers
• Stochastic Proximal Gradient Consensus Over Random Networks

Cited by in corpus (7)

• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• Improved Convergence Rates for Distributed Resource Allocation
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• Asynchronous decentralized accelerated stochastic gradient descent
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication