An Asynchronous Parallel Randomized Kaczmarz Algorithm

Abstract

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$.

Cited by in corpus (18)

• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Stochastic Dual Ascent for Solving Linear Systems
• CYCLADES: Conflict-free Asynchronous Machine Learning
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Asynchronous Stochastic Proximal Optimization Algorithms with Variance Reduction
• Convergence Rates for Greedy Kaczmarz Algorithms, and Faster Randomized Kaczmarz Rules Using the Orthogonality Graph
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Block stochastic gradient iteration for convex and nonconvex optimization
• Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction
• Greed Works: An Improved Analysis of Sampling Kaczmarz-Motzkin
• Distributed stochastic optimization with large delays
• Randomized Block Kaczmarz Method with Projection for Solving Least Squares
• Regularized Kaczmarz Algorithms for Tensor Recovery