Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
This work addresses optimization challenges in machine learning, offering incremental improvements for practitioners dealing with large-scale problems.
The paper tackles the problem of improving stochastic L-BFGS algorithms by proving enhanced convergence rates and proposing practical acceleration strategies, with experiments showing significant improvements over state-of-the-art methods on large-scale logistic and ridge regression tasks.
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.