Randomized Iterative Methods for Linear Systems

By Robert Mansel Gower, Peter Richtárik. 2015

327 citations recorded by the source corpus.

We develop a novel, fundamental and surprisingly simple randomized iterative method for solving consistent linear systems. Our method has six different but equivalent interpretations: sketch-and-project, constrain-and-approximate, random intersect, random linear solve, random update and random fixed point. By varying its two parameters$-$a positive definite matrix (defining geometry), and a random matrix (sampled in an independently and identically distributed fashion in each iteration)$-$we recover a comprehensive array of well-known algorithms as special cases, including the randomized Kaczmarz method, randomized Newton method, randomized coordinate descent method and random Gaussian pursuit. We naturally also obtain variants of all these methods using blocks and importance sampling. However, our method allows for a much wider selection of these two parameters, which leads to a number of new specific methods. We prove exponential convergence of the expected norm of the error in a single theorem, from which existing complexity results for known variants can be obtained. However, we also give an exact formula for the evolution of the expected iterates, which allows us to give lower bounds on the convergence rate.

Subfields: Artificial Intelligence, Numerical Analysis, Statistics and Probability, Numerical Methods & Scientific Computing

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 Numerical Analysis

In Statistics and Probability

In Numerical Methods & Scientific Computing

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “MORE DETAILS AND CONVERGENCE ANALYSIS Recently several new randomized iterative methods (sketch and project methods) for solving largescale linear systems have been proposed [13, 27, 29, 48].”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “Gower and Richtárik [31] have recently studied randomized iterative methods for linear systems in a general sketch and project framework, which in special cases includes randomized Kaczmarz, randomized coordinate descent, Gaussian descent, randomized Newton, their block variants, variants with impor”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “[84] • Chapter 4: Jakub Konečný, Jie Liu, Peter Richtárik and Martin Takáč: “Mini-batch semi-stochastic gradient descent in the proximal setting.””
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “, 2020), consistent linear systems (Gower and Richtárik, 2015; Richtárik and Takác, 2020; Loizou and Richtárik, 2017, 2019) and multi-class classification using deep networks (Vaswani et al.”
Better Theory for SGD in the Nonconvex World (2020, background): “…Richt´arik & Tak´aˇc (2017) who, motivated by the desire to obtain deeper insights into the workings of the sketch and project algorithms developed by Gower & Richt´arik (2015), study the behaviour of SGD applied to a reformulation of a consistent linear system as a stochastic convex quadratic…”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “The sketch-and-project algorithm [25, 73] for solving a consistent linear system Ax = b has the form”
A new perspective on randomized gossip algorithms (2016, background): “Algorithm (10) can be shown to be equivalent to the following “sketch and project” iteration (see [22] for additional equivalent viewpoints):”
Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms (2016, methodology): “In particular, the theory in [15] proves that the expected norm difference of each column of WXk converges to W −1/2A−1 with rate ρ as defined in (2.”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “Gower and Richtarik (2015a) observed that the RK algorithm is a particular type of iterative sketching method.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “Randomized Gaussian Kaczmarz (RGK) method was first proposed in [73]; mRGK is its momentum variant.”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “While there are deep links between standard SGD and RCD methods, these are often indirect and rely on duality (Shalev-Shwartz and Zhang, 2013; Csiba and Richtárik, 2018; Gower and Richtárik, 2015).”
Linearly convergent stochastic heavy ball method for minimizing generalization error (2017, background): “Then we have the identity (see, for instance [4]) This means that the quantity E [ (cid:107) x − x ∗ 2 ] appearing in our L2 convergence result (Theorem 1) is larger than E [ x − x ∗ ] 2 appearing in the L1 convergence result (Theorem 3), and hence harder to push to zero.”
Stochastic Block BFGS: Squeezing More Curvature out of Data (2016, background): “This is yet one more reason to expect that in our setting the matrices H tapproximately track the inverse Hessian. For similar techniques applied to the problem of solving linear systems, we refer to [12, 14]. The solution to (5) is H t = D t tD T t + I D t tY t T H t 1 (I Y t tD t); (6) where t def”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “ted method (for a suitable 7 choice of the parameters ωand γ) is q 1/λ+ min. Novelty. All convergence results presented in this paper are new in one way or another. Indeed, we extend the methods from [20, 21] to include a stepsize/relaxation parameter, or analyze these methods under a weaker conditi”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “That is S ∼ N(0,Σ) [18, 29].”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, background): “[11] Robert M Gower and Peter Richtárik.”