Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
arXiv:1509.02597 · doi:10.1109/TSP.2016.2537271
Abstract
Aiming at solving large-scale learning problems, this paper studies distributed optimization methods based on the alternating direction method of multipliers (ADMM). By formulating the learning problem as a consensus problem, the ADMM can be used to solve the consensus problem in a fully parallel fashion over a computer network with a star topology. However, traditional synchronized computation does not scale well with the problem size, as the speed of the algorithm is limited by the slowest workers. This is particularly true in a heterogeneous network where the computing nodes experience different computation and communication delays. In this paper, we propose an asynchronous distributed ADMM (AD-AMM) which can effectively improve the time efficiency of distributed optimization. Our main interest lies in analyzing the convergence conditions of the AD-ADMM, under the popular partially asynchronous model, which is defined based on a maximum tolerable delay of the network. Specifically, by considering general and possibly non-convex cost functions, we show that the AD-ADMM is guaranteed to converge to the set of Karush-Kuhn-Tucker (KKT) points as long as the algorithm parameters are chosen appropriately according to the network delay. We further illustrate that the asynchrony of the ADMM has to be handled with care, as slightly modifying the implementation of the AD-ADMM can jeopardize the algorithm convergence, even under a standard convex setting.
37 pages
References in corpus (7)
- Convex Optimization for Big Data
- On the Linear Convergence of the Alternating Direction Method of Multipliers
- Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
- Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
- A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
- Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
Cited by in corpus (41)
- Asynchronous Distributed Optimization over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
- Privacy-preserving Incremental ADMM for Decentralized Consensus Optimization
- Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation
- Towards Transactive Energy: An Analysis of Information-related Practical Issues
- Multi-Path Alpha-Fair Resource Allocation at Scale in Distributed Software Defined Networks
- Asynchronous ADMM for Distributed Non-Convex Optimization in Power Systems
- Generalized gradient optimization over lossy networks for partition-based estimation
- Distributed Optimization over Lossy Networks via Relaxed Peaceman-Rachford Splitting: a Robust ADMM Approach
- ADMM-Tracking Gradient for Distributed Optimization over Asynchronous and Unreliable Networks
- Robust Online Learning over Networks
- Distributed ADMM with Synergetic Communication and Computation
- Distributed Augmented Lagrangian Method for Link-Based Resource Sharing Problems of Multi-Agent Systems
- Newton-Raphson Consensus under asynchronous and lossy communications for peer-to-peer networks
- Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions
- Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
- Balancing Communication and Computation in Distributed Optimization
- Superlinearly Convergent Asynchronous Distributed Network Newton Method
- Byzantine-Resilient Distributed P2P Energy Trading via Spatial-Temporal Anomaly Detection
- Asynchronous distributed collision avoidance with intention consensus for inland autonomous ships
- Hybrid Voltage Control in Distribution Networks Under Limited Communication Rates
- A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- Harnessing the Power of Serverless Runtimes for Large-Scale Optimization
- Impact of Communication Delay on Asynchronous Distributed Optimal Power Flow Using ADMM
- A Fully-Distributed Asynchronous Approach for Multi-Area Coordinated Network-Constrained Unit Commitment
- Technical Report: A Totally Asynchronous Algorithm for Tracking Solutions to Time-Varying Convex Optimization Problems
- Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
- Composite Optimization with Coupling Constraints via Dual Proximal Gradient Method with Applications to Asynchronous Networks
- A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
- Linearly Convergent Asynchronous Distributed ADMM via Markov Sampling
- Resource-aware Exact Decentralized Optimization Using Event-triggered Broadcasting
- Toward Model Parallelism for Deep Neural Network based on Gradient-free ADMM Framework
- A Partition-Based Implementation of the Relaxed ADMM for Distributed Convex Optimization over Lossy Networks
- Convergence Analysis and Design of Multi-block ADMM via Switched Control Theory
- Distributed and Asynchronous Algorithms for N-block Convex Optimization with Coupling Constraints
- Decentralized Consensus Optimization Based on Parallel Random Walk
- Exponential Convergence of a Distributed Algorithm for Solving Linear Algebraic Equations
- An Asynchronous Distributed Framework for Large-scale Learning Based on Parameter Exchanges
- Distributed Optimization Using the Primal-Dual Method of Multipliers
- Convergence Analysis of Nonconvex ADMM for Rigid Registration