An Asynchronous Parallel Randomized Kaczmarz Algorithm

By Ji Liu, Stephen J. Wright, Srikrishna Sridhar. 2014

65 citations recorded by the source corpus.

We describe an asynchronous parallel variant of the randomized Kaczmarz (RK) algorithm for solving the linear system Ax = b. The analysis shows linear convergence and indicates that nearly linear speedup can be expected if the number of processors is bounded by a multiple of the number of rows in A.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “…and Duchi, 2011, Zhang et al., 2014, Feyzmahdavian et al., 2015, Paine et al., 2013], stochastic coordinate descent [Avron et al., 2014, Liu et al., 2014a], dual stochastic coordinate ascent [Tran et al., 2015], randomized Kaczmarz algorithm [Liu et al., 2014b], and ADMM [Zhang and Kwok, 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 gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, positive): “…problem (5.1) in the form (2.1), we see that the source distribution D is uniform over { 1 , 2 , . . . , n , the components are , and the residual is P Note that in the case that A is not full-rank, one can instead replace µ with the smallest nonzero eigenvalue of A ∗ A as in [23, Equation (3)].”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, methodology): “problem type upper bound of T model ASGD [25] SGD smooth, strongly convex O(N) C ASGD [1] SGD smooth, convex O(K min{σ, σ}) C ASGD[11] SGD composite, convex O(Kσ) C ASGD [18] SGD smooth, nonconvex O(NKσ) I ASGD [18] SGD smooth, nonconvex O(Kσ) C ARK [21] SGD Ax = b O(N) C ASCD [20] SCD smooth, conve”
SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm (2016, background): “The randomized Kaczmarz algorithm [36,26], which solves overdetermined linear systems Ax = b, is a special case of (4.”
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.”
Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties (2014, methodology): “Recently, parallel multicore versions of stochastic gradient and stochastic coordinate descent have been described for problems involving large data sets; see for example [30, 33, 3, 20, 37, 21].”