Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method

By Deanna Needell, Joel A. Tropp. arXiv.org, 2012

368 citations recorded by the source corpus.

The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0d625471780fe974d7984373ce3196c6bcecbaca

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 Statistics and Probability

Citations in the corpus

How catastrophic can catastrophic forgetting be in linear regression? (2022, background): “Finally, we believe our bounds are novel and can provide a new perspective in these areas, especially in the cyclic block Kaczmarz setting [15, 45], i.”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “Needell and Tropp (2014) analyzed a randomized block Kaczmarz method in the context of solving linear systems, which also minimizes the empirical loss on a randomly sampled minibatch.”
Rows vs. Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression (2015, result): “This result was extended to the inconsistent case [16], derived via a probabilistic almost-sure convergence perspective [2], accelerated in multiple ways [5, 4, 22, 19, 18], and generalized to other settings [13, 23, 17].”
Continual Learning in Linear Classification on Separable Data (2023, background): “Much like cyclic orderings, random orderings have been studied in many related areas (e.g., Nedić (2010); Needell & Tropp (2014); Evron et al. (2022)).”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Needell and Tropp (2014) studied a blocked version of the RK algorithm, which is practically more efficient for many of the same reasons that other blocked algorithms work well (Section 16.2).”
A new perspective on randomized gossip algorithms (2016, methodology): “More generally, if Sk is a random column submatrix of the m×m identity matrix, the dual method is the randomized Newton method [21], and the corresponding primal method is a block version of RK [14].”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, background): “Recent works use acceleration techniques to improve conver gence rates [18, 27, 9, 31, 41, 10, 8, 5, 28, 29, 30, 23, 22].”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “The randomized Kaczmarz method, its variants have received considerable attention recently [31, 65, 32, 43], and several connections to existing methods were made.”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “This result sparked renewed interest in design of randomized methods for solving linear systems [56, 57, 18, 51, 93, 58, 74, 41].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In the special case that only one edge is selected in each iteration (Sk ∈ Rm×1) the update rule of mRBK is simplified to the update rule of mRK.”
Randomized Iterative Methods for Linear Systems (2015, methodology): “Though this results in a somewhat harder to interpret convergence rate, a matrix paving could be used explore this block convergence rate, as was done for the block Kaczmarz method [24, 23].”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, methodology): “Kaczmarz algorithms [55, 35, 41, 40] for overdetermined linear systems, as in Example 4, are effective, solving feasible systems Ax = b (where A ∈ Rm×n,m ≥ n) using careful stochastic gradient steps on the objective ‖Ax− b‖22 to achieve fast convergence.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “1 Importance of Large Block Size Many recent works have shown that using larger block sizes can be very beneficial for the performance of randomized iterative algorithms [18, 44, 34, 27].”