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

By Mingyi Hong. 2014

72 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Electrical and Electronic Engineering

In Signal Processing

Citations in the corpus

Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “The asynchronous parallel optimization recently received many successes and broad attention in machine learning and optimization [Niu et al., 2011, Li et al., 2013, 2014b, Yun et al., 2013, Fercoq and Richtárik, 2013, Zhang and Kwok, 2014, Marecek et al., 2014, Tappenden et al., 2015, Hong, 2014].”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “A large body of recent work has demonstrated that near-linear speedups are achievable, in theory and practice, on many common machine learning tasks [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13, 16].”
Stochastic Variance Reduction for Nonconvex Optimization (2016, background): “Hong (2014) studies a distributed nonconvex incremental ADMM algorithm.”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, methodology): “[19] M. Hong, M. Razaviyayn, Z. Luo, and J. Pang.”
Cyclades: Conflict-free Asynchronous Machine Learning (2016, background): “Additional work in ﬁrst order optimization and beyond [DJM13, WSD + 14, Hon14, HYD15, FAJ15], extending to parallel iterative linear solvers [LWS14, ADG14], has further demonstrated that linear speedups are generically possible in the asynchronous shared-memory setting.”
ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates (2015, methodology): “2.6 Async-parallel ADMM This is another application of (15).”
Fast incremental method for smooth nonconvex optimization (2016, background): “Hong [9] studies convergence of a distributed nonconvex incremental ADMM algorithm.”
Fast Incremental Method for Nonconvex Optimization (2016, background): “Hong (Hong, 2014) studies convergence of a distributed nonconvex incremental ADMM algorithm.”