Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
arXiv:1704.00116 · doi:10.1109/TSP.2017.2784360
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 (15)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Sketching as a Tool for Numerical Linear Algebra
- A Universal Catalyst for First-Order Optimization
- RES: Regularized Stochastic BFGS Algorithm
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Global Convergence of Online Limited Memory BFGS
- Decentralized Quasi-Newton Methods
- Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
- Stop Wasting My Gradients: Practical SVRG
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- Action constrained quasi-Newton methods
- Linear Convergence of Stochastic Frank Wolfe Variants
- A Proximal Stochastic Quasi-Newton Algorithm
- Centralized and Distributed Newton Methods for Network Optimization and Extensions
- A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning