Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization

By Haim Avron, Alex Druinsky, Anshul Gupta. 2013

94 citations recorded by the source corpus.

Asynchronous methods for solving systems of linear equations have been researched since Chazan and Miranker's pioneering 1969 paper. The underlying idea of asynchronous methods is to avoid processor idle time by allowing the processors to continue to make progress even if not all progress made by other processors has been communicated to them. Historically, work on asynchronous methods for solving linear equations focused on proving convergence in the limit. Comparison of the asynchronous convergence rate with its synchronous counterpart and its scaling with the number of processors were seldom studied, and are still not well understood. Furthermore, the applicability of these methods was limited to restricted classes of matrices, such as diagonally dominant matrices. We propose a randomized shared-memory asynchronous method for general symmetric positive definite matrices. We rigorously analyze the convergence rate and prove that it is linear, and is close to that of the method's synchronous counterpart if the processor count is not excessive relative to the size and sparsity of the matrix. Our work presents a significant improvement in convergence analysis as well as in the applicability of asynchronous linear solvers, and suggests randomization as a key paradigm to serve as a foundation for asynchronous methods.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Theory and Mathematics

Citations in the corpus

Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “To avoid such synchronization overhead, in the spirit of asynchronous parallel algorithms for centralized networks Agarwal and Duchi [2011], Avron et al. [2014], Feyzmahdavian et al. [2015], Feyzmahdavian et al. [2016], Liu et al. [2014], Mania et al. [2015], Paine et al. [2013], Recht et al.…”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “It has been successfully applied to the distributed neural network [Dean et al., 2012] and the parameter server [Li et al., 2014a] to solve deep neural network.”
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].”
An asynchronous parallel stochastic coordinate descent algorithm (2013, background): “Recently, parallel multicore versions of stochastic gradient and stochastic coordinate descent have been described for problems involving large data sets; see for example (Niu et al., 2011; Richtárik & Takáč, 2012; Avron et al., 2014).”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, methodology): “This paper provides a comprehensive and generic analysis to study the speedup property for a broad range of asynchronous parallel stochastic algorithms from the zeroth order to the first order methods.”
Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? (2018, background): “…et al., 2013; Chaturapruek et al., 2015; Lian et al., 2015; Feyzmahdavian et al., 2016; Mania et al., 2017), coordinate descent (Liu et al., 2014; Avron et al., 2015; Liu & Wright, 2015; Tappenden et al., 2017; Fercoq & Richtárik, 2015), dual coordinate descent (Tran et al., 2015), block…”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Bach (2013) identified the core role of the smoothed projector for KRR.”
More Iterations per Second, Same Quality - Why Asynchronous Algorithms may Drastically Outperform Traditional Ones (2017, unknown): “In [14], the authors prove linear convergence for an asynchronous stochastic linear solver.”
ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates (2015, methodology): “, linear systems [3, 10, 25, 53], nonlinear problems [4, 5], differential equations [1, 2, 13, 20], consensus problems [35, 24], and optimization [31, 38, 39, 54, 61].”
Asynchronous Stochastic Gradient Descent with Delay Compensation (2016, background): “problem of delayed gradient has been well known (Agarwal & Duchi, 2011; Recht et al., 2011; Lian et al., 2015; Avron et al., 2015), and many practical observations indicate that it usually costs ASGD more iterations to converge than sequential SGD, and sometimes, the converged model of ASGD cannot r”
On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms (2016, background): “In [18], the authors prove linear convergence for an asynchronous stochastic linear solver.”
Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties (2014, methodology): “ Liu et al. [22] developed an asynchronous parallel variant of the randomized Kaczmarz algorithm for solving a general consistent linear system Ax = b, proving a linear convergence rate. Avron et al. [3] proposed an asynchronous solver for the system Qx= cwhere Qis a symmetric positive deﬁnite matri”
PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent (2015, background): “(Avron et al., 2014) showed linear rate of convergence for the asynchronous randomized Gauss-Seidel updates, which is a special case of coordinate descent on linear systems.”
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.”
Pipelined Backpropagation at Scale: Training Large Models without Batches (2020, background): “This results in stale gradients (aka. delayed gradients ), an issue that also occurs in asynchronous SGD training (Lian et al., 2015; Avron et al., 2015).”