Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance

Abstract

The alternating direction method of multipliers (ADMM) has been recognized as a versatile approach for solving modern large-scale machine learning and signal processing problems efficiently. When the data size and/or the problem dimension is large, a distributed version of ADMM can be used, which is capable of distributing the computation load and the data set to a network of computing nodes. Unfortunately, a direct synchronous implementation of such algorithm does not scale well with the problem size, as the algorithm speed is limited by the slowest computing nodes. To address this issue, in a companion paper, we have proposed an asynchronous distributed ADMM (AD-ADMM) and studied its worst-case convergence conditions. In this paper, we further the study by characterizing the conditions under which the AD-ADMM achieves linear convergence. Our conditions as well as the resulting linear rates reveal the impact that various algorithm parameters, network delay and network size have on the algorithm performance. To demonstrate the superior time efficiency of the proposed AD-ADMM, we test the AD-ADMM on a high-performance computer cluster by solving a large-scale logistic regression problem.

submitted for publication, 28 pages

References in corpus (4)

• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
• Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems

Cited by in corpus (14)

• Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
• Asynchronous Distributed Optimization over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
• Federated PCA on Grassmann Manifold for IoT Anomaly Detection
• CPU Scheduling in Data Centers Using Asynchronous Finite-Time Distributed Coordination Mechanisms
• Distributed ADMM with Synergetic Communication and Computation
• Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• Superlinearly Convergent Asynchronous Distributed Network Newton Method
• 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
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Toward Model Parallelism for Deep Neural Network based on Gradient-free ADMM Framework
• Distributed and Asynchronous Algorithms for N-block Convex Optimization with Coupling Constraints