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

DOI10.1109/TSP.2016.2537261zbMATH Open1414.94107arXiv1509.02604OpenAlexW2129375853MaRDI QIDQ4619616FDOQ4619616

Authors: Tsung-Hui Chang, Wei-Cheng Liao, Mingyi Hong, Xiangfeng Wang 

Publication date: 7 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1509.02604

Recommendations

• Asynchronous Distributed ADMM for Large-Scale Optimization—Part I: Algorithm and<?Pub _newline ?>Convergence Analysis
• A Distributed, Asynchronous, and Incremental Algorithm for Nonconvex Optimization: An ADMM Approach
• A distributed asynchronous method of multipliers for constrained nonconvex optimization
• Asynchronous Distributed Optimization Over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
• A novel bound on the convergence rate of ADMM for distributed optimization
• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• Asynchronous Distributed Optimization Via Randomized Dual Proximal Gradient
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• Asynchronous parallel algorithms for nonconvex optimization
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (13)

• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• An alternate minimization method beyond positive definite proximal regularization: convergence and complexity
• Convergence analysis of positive-indefinite proximal ADMM with a Glowinski's relaxation factor
• Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
• Hybrid MPI/OpenMP parallel asynchronous distributed alternating direction method of multipliers
• Linear Convergence of ADMM Under Metric Subregularity for Distributed Optimization
• Decentralized consensus algorithm with delayed and stochastic gradients
• Robust asynchronous stochastic gradient-push: asymptotically optimal and network-independent performance for strongly convex functions
• A novel bound on the convergence rate of ADMM for distributed optimization
• Asynchronous Distributed Optimization Over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
• Synchronous distributed ADMM for consensus convex optimization problems with self-loops
• A Distributed, Asynchronous, and Incremental Algorithm for Nonconvex Optimization: An ADMM Approach
• An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation

This page was built for publication: Asynchronous Distributed ADMM for Large-Scale Optimization—Part II: Linear Convergence Analysis and Numerical Performance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4619616)