Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms

By Robert Mansel Gower, Peter Richtárik. 2016

87 citations recorded by the source corpus.

We develop and analyze a broad family of stochastic/randomized algorithms for calculating an approximate inverse matrix. We also develop specialized variants maintaining symmetry or positive definiteness of the iterates. All methods in the family converge globally and linearly (i.e., the error decays exponentially), with explicit rates. In special cases, we obtain stochastic block variants of several quasi-Newton updates, including bad Broyden (BB), good Broyden (GB), Powell-symmetric-Broyden (PSB), Davidon--Fletcher--Powell (DFP), and Broyden--Fletcher--Goldfarb--Shanno (BFGS). Ours are the first stochastic versions of these updates shown to converge to an inverse of a fixed matrix. Through a dual viewpoint we uncover a fundamental link between quasi-Newton updates and approximate inverse preconditioning. Further, we develop an adaptive variant of randomized block BFGS, where we modify the distribution underlying the stochasticity of the method throughout the iterative process to achieve faster convergen...

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

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “In [38], the authors utilize recent progress in the area of stochastic matrix inversion [39] revealing new connections with quasi-Newton methods, and devise a new stochastic limited memory BFGS method working in tandem with SVRG.”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “Gower andRichtárik [30,31] use similar ideas to develop linearly convergent randomized iterative methods for computing/estimating the inverse and pseudoinverse of a large matrix, respectively.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “In [67], the authors utilize recent progress in the area of stochastic matrix inversion [69] revealing new connections with quasi-Newton methods, and devise a new stochastic limited memory BFGS method working in tandem with SVRG.”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, background): “[7] Robert M Gower and Peter Richtárik.”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “ble to approach the problem AX = I in the same way we approach the system (1.1) in our paper, writing down stochastic reformulations, and then developing new variants of the sketch and project method [23]: a basic method with a stepsize, and parallel and accelerated methods. This would lead to the d”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “The “sketch-and-project” strategy (9) for updating our Jacobian estimate is analogous to the way quasi-Newton methods update the estimate of the Hessian (or inverse Hessian) [8,9,12].”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “[22] and [27] use similar ideas for the development of linearly convergent randomized iterative methods for computing/estimating the inverse and pseudoinverse of a large matrix, respectively.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “[69, 75] use sketch-and-project ideas for the development of linearly convergent randomized iterative methods for computing/estimating the inverse and pseudoinverse of a large matrix, respectively.”
Batched Stochastic Gradient Descent with Weighted Sampling (2016, background): “For an overview of applications of stochastic gradient descent and its weighted/batched variants in large-scale matrix inversion problems, we refer the reader to [29].”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, background): “Gower [11] observed that the procedure (5) can also be applied to find the inverse of a matrix.”