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

By Robert Mansel Gower, Filip Hanzely, Peter Richtárik, Sebastian U. Stich. 2018

49 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mathematics, Statistical and Nonlinear Physics, Optimization & Training

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 Mathematics

In Statistical and Nonlinear Physics

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “The interpolation assumption also allows for momentum-type methods to achieve the accelerated rates of convergence for least-squares (Gower et al., 2018) and more generally in convex settings (Vaswani et al., 2019a; Liu and Belkin, 2016).”
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].”
Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients (2018, background): “On the other hand, there has been recent efforts in performing efficient approximations of (2) in time comparable to that required for a gradient update ([2, 17, 22]).”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, background): “Quasi-Newton methods can also be used [20], but typically without the guarantees that we provide in this paper (which are logarithmic in the condition number in natural scenarios).”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “Below we present the theoretical guarantees of the two options as presented in [41] and [24].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “It can be shown that 1 ≤ ν ≤ 1/λ+min(W), (Lemma 2 in [72]) where ν is as defined in (4.”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “on methods. Quasi-Newton literature. While we were unable to obtain an accelerated method for the quantity E kxk−x∗k2 B , this problem was solved in [60], and later further generalized by Gower et al [18]. As a by-product, they develop the ﬁrst accelerated (and provably so) quasi-Newton matrix inver”