Asynchronous Coordinate Descent under More Realistic Assumptions

By Tao Sun, Robert Hannah, Wotao Yin. 2017

77 citations recorded by the source corpus.

Asynchronous-parallel algorithms have the potential to vastly speed up algorithms by eliminating costly synchronization. However, our understanding to these algorithms is limited because the current convergence of asynchronous (block) coordinate descent algorithms are based on somewhat unrealistic assumptions. In particular, the age of the shared optimization variables being used to update a block is assumed to be independent of the block being updated. Also, it is assumed that the updates are applied to randomly chosen blocks. In this paper, we argue that these assumptions either fail to hold or will imply less efficient implementations. We then prove the convergence of asynchronous-parallel block coordinate descent under more realistic assumptions, in particular, always without the independence assumption. The analysis permits both the deterministic (essentially) cyclic and random rules for block choices. Because a bound on the asynchronous delays may or may not be available, we establish convergence for both bounded delays and unbounded delays. The analysis also covers nonconvex, weakly convex, and strongly convex functions. We construct Lyapunov functions that directly model both objective progress and delays, so delays are not treated errors or noise. A continuous-time ODE is provided to explain the construction at a high level.

Subfields: Numerical Analysis, Statistics and Probability

How researchers see this paper

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

In Numerical Analysis

In Statistics and Probability

Citations in the corpus

LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning (2018, background): “Recent research eﬀorts in this line have been centered on understanding asynchronous-parallel algorithms to speed up machine learning by eliminating costly synchronization; e.g., (Cannelli et al., 2016; Sun et al., 2017; Peng et al., 2016; Recht et al., 2011; Liu et al., 2015).”
Asynchronous Distributed Learning with Sparse Communications and Identification (2018, methodology): “Asynchronous coordinate descent methods able to handle unbounded delays were recently proposed [8, 30] but use decreasing stepsizes.”
More Iterations per Second, Same Quality - Why Asynchronous Algorithms may Drastically Outperform Traditional Ones (2017, unknown): “Only a few papers that we are aware of make progress in eliminating this assumption [3]–[5].”
Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning (2018, background): “This approach was studied in Recht et al. (2011); Agarwal and Duchi (2011); Dean et al. (2012); Li et al. (2014) (among many others) for the case of data parallelism, and Liu et al. (2015); You et al. (2016); Peng et al. (2016); Sun et al. (2017) for coordinate descent methods (model parallelism).”
Distributed Learning with Sparse Communications by Identification (2018, methodology): “roduced iterations; the intuition being that combining delayed points is more stable than using a combination of delayed directions; see the numerical comparisons of [21]. Thus, using the terminology [30], the local iterate xk i[j] of our algorithm suers from the combination of two kinds of delays: ”
A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning (2018, background): “Except (Sun et al., 2017) in a stochastic context, the assumptions on delays of the above algorithms are very restrictive.”