Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
From MaRDI portal
Publication:4598334
DOI10.1137/16M1062053zbMATH Open1379.65016arXiv1602.01768OpenAlexW2295492468MaRDI QIDQ4598334FDOQ4598334
Authors: Peter Richtárik, Robert M. Gower 
Publication date: 20 December 2017
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Abstract: We develop and analyze a broad family of stochastic/randomized algorithms for inverting a 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 convergence. By inverting several matrices from varied applications, we demonstrate that AdaRBFGS is highly competitive when compared to the well established Newton-Schulz and minimal residual methods. In particular, on large-scale problems our method outperforms the standard methods by orders of magnitude. Development of efficient methods for estimating the inverse of very large matrices is a much needed tool for preconditioning and variable metric optimization methods in the advent of the big data era.
Full work available at URL: https://arxiv.org/abs/1602.01768
Recommendations
- Global convergence of online limited memory BFGS
- A stochastic quasi-Newton method for large-scale optimization
- Different stochastic algorithms to obtain matrix inversion
- Matrix algebras in quasi-Newton methods for unconstrained minimization
- Quasi-Newton methods for machine learning: forget the past, just sample
preconditioningquasi-NewtonCholesky decompositioniterative methodsmatrix inversionstochastic methodsminimal residual methodstochastic convergenceNewton-Schulz methoddirect inversion methodBroyden-Fletcher-Goldfarb-Shanno
Direct numerical methods for linear systems and matrix inversion (65F05) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10)
Cites Work
- The University of Florida sparse matrix collection
- A randomized Kaczmarz algorithm with exponential convergence
- Variable Metric Method for Minimization
- A Rapidly Convergent Descent Method for Minimization
- Updating Quasi-Newton Matrices with Limited Storage
- A Family of Variable-Metric Methods Derived by Variational Means
- Conditioning of Quasi-Newton Methods for Function Minimization
- Variable metric random pursuit
- Randomized Hessian estimation and directional search
- Randomized methods for linear constraints: convergence rates and conditioning
- Title not available (Why is that?)
- Positive definite matrices
- On A Class of Limited Memory Preconditioners For Large Scale Linear Systems With Multiple Right-Hand Sides
- Factorized Sparse Approximate Inverse Preconditionings I. Theory
- Approximate Inverse Preconditioners via Sparse-Sparse Iterations
- A Class of Methods for Solving Nonlinear Simultaneous Equations
- Randomized iterative methods for linear systems
- A comparative study of sparse approximate inverse preconditioners
- Stability of Methods for Matrix Inversion
- A family of iterative methods for computing the approximate inverse of a square matrix and inner inverse of a non-square matrix
- Randomized Sketches of Convex Programs With Sharp Guarantees
- Variations on Variable-Metric Methods
- Sparse Approximate-Inverse Preconditioners Using Norm-Minimization Techniques
- Frobenius norm minimization and probing for preconditioning
- Modification Methods for Inverting Matrices and Solving Systems of Linear Algebraic Equations
- Probabilistic interpretation of linear solvers
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Broyden updating, the good and the bad!
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- A New Method for Obtaining the Inverse Matrix
Cited In (16)
- slimTrain---A Stochastic Approximation Method for Training Separable Deep Neural Networks
- Towards explicit superlinear convergence rate for SR1
- Sampled limited memory methods for massive linear inverse problems
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Greedy quasi-Newton methods with explicit superlinear convergence
- Rates of superlinear convergence for classical quasi-Newton methods
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Unifying relations between iterative linear equation solvers and explicit Euler approximations for associated parabolic regularized equations
- Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
- An overview of stochastic quasi-Newton methods for large-scale machine learning
- Beyond the EM algorithm: constrained optimization methods for latent class model
- Batched Stochastic Gradient Descent with Weighted Sampling
Uses Software
This page was built for publication: Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598334)
