Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies

Abstract

We revisit the stochastic limited-memory BFGS (L-BFGS) algorithm. By proposing a new framework for the convergence analysis, we prove improved convergence rates and computational complexities of the stochastic L-BFGS algorithms compared to previous works. In addition, we propose several practical acceleration strategies to speed up the empirical performance of such algorithms. We also provide theoretical analyses for most of the strategies. Experiments on large-scale logistic and ridge regression problems demonstrate that our proposed strategies yield significant improvements vis-à-vis competing state-of-the-art algorithms.

References in corpus (7)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Sketching as a Tool for Numerical Linear Algebra
• Global Convergence of Online Limited Memory BFGS
• Decentralized Quasi-Newton Methods
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Linear Convergence of Stochastic Frank Wolfe Variants
• A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning

Cited by in corpus (3)

• Secant Penalized BFGS: A Noise Robust Quasi-Newton Method Via Penalizing The Secant Condition
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Asynchronous Parallel Stochastic Quasi-Newton Methods