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

Renbo Zhao, William B. Haskell, Vincent Y. F. Tan
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:740-749, 2017.

Abstract

We revisit the stochastic limited-memory BFGS (L-BFGS) algorithm. By proposing a new framework for analyzing convergence, we theoretically improve the (linear) convergence rates and computational complexities of the stochastic L- BFGS algorithms in 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 via-á-vis competing state-of-the-art algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-zhao17b, title = {Stochastic L-{BFGS} Revisited: Improved Convergence Rates and Practical Acceleration Strategies}, author = {Zhao, Renbo and Haskell, William B. and Tan, Vincent Y. F.}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {740--749}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/zhao17b/zhao17b.pdf}, url = {https://proceedings.mlr.press/r15/zhao17b.html}, abstract = {We revisit the stochastic limited-memory BFGS (L-BFGS) algorithm. By proposing a new framework for analyzing convergence, we theoretically improve the (linear) convergence rates and computational complexities of the stochastic L- BFGS algorithms in 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 via-á-vis competing state-of-the-art algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Stochastic L-BFGS Revisited: Improved Convergence Rates and Practical Acceleration Strategies %A Renbo Zhao %A William B. Haskell %A Vincent Y. F. Tan %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-zhao17b %I PMLR %P 740--749 %U https://proceedings.mlr.press/r15/zhao17b.html %V R15 %X We revisit the stochastic limited-memory BFGS (L-BFGS) algorithm. By proposing a new framework for analyzing convergence, we theoretically improve the (linear) convergence rates and computational complexities of the stochastic L- BFGS algorithms in 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 via-á-vis competing state-of-the-art algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
Zhao, R., Haskell, W.B. & Tan, V.Y.F.. (2017). Stochastic L-BFGS Revisited: Improved Convergence Rates and Practical Acceleration Strategies. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:740-749 Available from https://proceedings.mlr.press/r15/zhao17b.html. Reissued by PMLR on 04 October 2026.

Related Material