On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms

By Robert Hannah, Wotao Yin. 2016

58 citations recorded by the source corpus.

The need for scalable solvers for massive optimization problems has motivated the development of asynchronous-parallel algorithms, where a set of nodes runs in parallel with little or no synchronization, thus computing with delayed information. This paper develops powerful Lyapunov-functions techniques, and uses them to study the convergence of the asynchronous-parallel algorithm ARock under potentially unbounded delays. ARock is a very general asynchronous algorithm, that takes many popular algorithms as special cases: for instance, asynchronous block gradient descent, forward backward, ADMM, etc. Therefore our results have broad implications, and a range of applications. ARock parallelizes a fixed-point iterations by letting a set of nodes randomly choose solution coordinates to update in an asynchronous parallel fashion. The existing analysis of ARock assumes the delays to be bounded, and uses this bound to set a step size that is important to both convergence and efficiency. Other works, though allowing unbounded delays, impose strict conditions on the underlying fixed-point operator, resulting in limited applications. In this paper, convergence is established under unbounded delays, which can be either stochastic or deterministic. The proposed step sizes are more practical and larger than those in the existing work. The step size adapts to the delay distribution or the current delay being experienced in the system, instead of being limited by worst-case scenario delays. New Lyapunov functions, which are the key to analyzing asynchronous algorithms, are generated to obtain our results. A general strategy for generating Lyapunov functions is presented, which may find application in convergence analyses of other algorithms. A set of applicable optimization algorithms with large-scale applications are given, including machine learning and scientific computing algorithms.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

More Iterations per Second, Same Quality - Why Asynchronous Algorithms may Drastically Outperform Traditional Ones (2017, unknown): “2The case of r = 1 was considered in [2].”
On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays (2016, background): “The work [12] allows unbounded delays but requires convexity, and [8,3] do not assume convexity but require bounded delays.”
Decentralized consensus optimization with asynchrony and delays (2016, background): “As we are finishing this paper, the recent work [40] has relaxed the above assumption by associating step sizes to potentially unbounded delays.”
Asynchronous Distributed Learning with Sparse Communications and Identification (2018, background): “Asynchronous coordinate descent methods able to handle unbounded delays were recently proposed [8, 30] but use decreasing stepsizes.”
Asynchronous Coordinate Descent under More Realistic Assumptions (2017, background): “1 Dependence between delays and blocks In previous analyses [13, 14, 16, 9], it is assumed that the block index ik and the delay ~j(k) were independent sequences.”
Decentralized Consensus Optimization With Asynchrony and Delays (2016, methodology): “The detailed proofs are omitted due to the page limit; interested readers are referred to [44].”