ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

By Zhimin Peng, Yangyang Xu, Ming Yan, Wotao Yin. 2015

274 citations recorded by the source corpus.

Finding a fixed point to a nonexpansive operator, i.e., $x^*=Tx^*$, abstracts many problems in numerical linear algebra, optimization, and other areas of scientific computing. To solve fixed-point problems, we propose ARock, an algorithmic framework in which multiple agents (machines, processors, or cores) update $x$ in an asynchronous parallel fashion. Asynchrony is crucial to parallel computing since it reduces synchronization wait, relaxes communication bottleneck, and thus speeds up computing significantly. At each step of ARock, an agent updates a randomly selected coordinate $x_i$ based on possibly out-of-date information on $x$. The agents share $x$ through either global memory or communication. If writing $x_i$ is atomic, the agents can read and write $x$ without memory locks. Theoretically, we show that if the nonexpansive operator $T$ has a fixed point, then with probability one, ARock generates a sequence that converges to a fixed points of $T$. Our conditions on $T$ and step sizes are weaker than comparable work. Linear convergence is also obtained. We propose special cases of ARock for linear systems, convex optimization, machine learning, as well as distributed and decentralized consensus problems. Numerical experiments of solving sparse logistic regression problems are presented.

Subfields: Artificial Intelligence, 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 Computer Networks and Communications

Citations in the corpus

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Another asynchronous, rather framework than an algorithm, for coordinate updates, applicable to wider class of objectives is presented in [72].”
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].”
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).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Another asynchronous, rather framework than an algorithm, for coordinate updates, applicable to wider class of objectives is presented in [138].”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, neutral): “This expression is also considered in [3, 18, 19, 27].”
Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization (2017, methodology): “This approach has been recently extended to general block-coordinate schemes by Peng et al. (2016), to greedy coordinate-descent schemes by You et al. (2016) and to non-convex problems by Davis et al. (2016).”
Decentralized Consensus Optimization With Asynchrony and Delays (2016, methodology): “6 of [33], the asynchronous decentralized ADMM.”
A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning (2018, methodology): “We mention e.g. ARock (Peng et al., 2016), Asynchronous ADMM (Zhang & Kwok, 2014), COCOA (Ma et al., 2015), Delayed Proximal Gradient algorithms (Feyzmahdavian et al., 2014; Aytekin et al., 2016; Vanli et al., 2016), or dSAGA (Calauzènes & Roux, 2017).”
Cyclades: Conflict-free Asynchronous Machine Learning (2016, background): “Finally, [PXYY15] introduces a new framework for analyzing coordinate-wise ﬁxed point stochastic iterations.”
Privacy-Preserving Distributed Multi-Task Learning with Asynchronous Updates (2017, methodology): “Convergence results on proximal methods have been previously studied in [13, 37].”
On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays (2016, background): “, [16,24]) over their synchronous counterparts partly due to the better speed-up performance.”
Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, background): “Parallel, coordinated, and asynchronous algorithms were discussed in [16] and the references therein.”
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).”
FedBCD: A Communication-Efficient Collaborative Learning Framework for Distributed Features (2022, methodology): “Compared with the existing distributed (stochastic) coordinate descent methods [12], [13], [14], [15], we show for the first time that when the number of local updates, mini-batch size and learning rates are selected appropriately, the FedBCD converges to a O(1/√T ) accuracy with O(√T ) rounds of co”
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.”