Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Abstract

We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices in such a way that all iterates (approximate solutions) generated by the algorithm are positive definite matrices themselves. This opens the way for many applications in the field of optimization and machine learning. As an application of our general theory, we develop the {\em first accelerated (deterministic and stochastic) quasi-Newton updates}. Our updates lead to provably more aggressive approximations of the inverse Hessian, and lead to speed-ups over classical non-accelerated rules in numerical experiments. Experiments with empirical risk minimization show that our rules can accelerate training of machine learning models.

arXiv comment37 pages, 32 figures, 3 algorithms

References in corpus (3)

• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Stochastic Dual Ascent for Solving Linear Systems
• Breaking Locality Accelerates Block Gauss-Seidel

Cited by in corpus (8)

• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses
• Heavy Ball Momentum Induced Sampling Kaczmarz Motzkin Methods for Linear Feasibility Problems
• Improving SAGA via a Probabilistic Interpolation with Gradient Descent
• $\text{RidgeSketch}$: A Fast sketching based solver for large scale ridge regression
• Learning-Augmented Sketches for Hessians