Fast Linear Convergence of Randomized BFGS

Abstract

Since the late 1950's when quasi-Newton methods first appeared, they have become one of the most widely used and efficient algorithmic paradigms for unconstrained optimization. Despite their immense practical success, there is little theory that shows why these methods are so efficient. We provide a semi-local rate of convergence for the randomized BFGS method which can be significantly better than that of gradient descent, finally giving theoretical evidence supporting the superior empirical performance of the method.

26 pages, 1 algorithm, 3 theorems, 11 lemmas, 9 figures

References in corpus (3)

• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Linearly Convergent Randomized Iterative Methods for Computing the Pseudoinverse
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation

Cited by in corpus (6)

• Rates of superlinear convergence for classical quasi-Newton methods
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Explicit Convergence Rates of Greedy and Random Quasi-Newton Methods
• Explicit Superlinear Convergence Rates of The SR1 Algorithm
• Explicit Superlinear Convergence Rates of Broyden's Methods in Nonlinear Equations
• Asynchronous Parallel Stochastic Quasi-Newton Methods