A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach

Abstract

The alternating direction method of multipliers (ADMM) has been popular for solving many signal processing problems, convex or nonconvex. In this paper, we study an asynchronous implementation of the ADMM for solving a nonconvex nonsmooth optimization problem, whose objective is the sum of a number of component functions. The proposed algorithm allows the problem to be solved in a distributed, asynchronous and incremental manner. First, the component functions can be distributed to different computing nodes, who perform the updates asynchronously without coordinating with each other. Two sources of asynchrony are covered by our algorithm: one is caused by the heterogeneity of the computational nodes, and the other arises from unreliable communication links. Second, the algorithm can be viewed as implementing an incremental algorithm where at each step the (possibly delayed) gradients of only a subset of component functions are update d. We show that when certain bounds are put on the level of asynchrony, the proposed algorithm converges to the set of stationary solutions (resp. optimal solutions) for the nonconvex (resp. convex) problem. To the best of our knowledge, the proposed ADMM implementation can tolerate the highest degree of asynchrony, among all known asynchronous variants of the ADMM. Moreover, it is the first ADMM implementation that can deal with nonconvexity and asynchrony at the same time.

References in corpus (10)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part I: Nash Equilibria
• Slow Learners are Fast
• A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers
• Sparse Inverse Covariance Selection via Alternating Linearization Methods
• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning

Cited by in corpus (13)

• Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
• Stochastic Variance Reduction for Nonconvex Optimization
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Fast Incremental Method for Nonconvex Optimization
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
• Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part II: Complexity and Numerical Results
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems