Stochastic Block BFGS: Squeezing More Curvature out of Data

Robert Gower, Donald Goldfarb, Peter Richtarik
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1869-1878, 2016.

Abstract

We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-gower16, title = {Stochastic Block BFGS: Squeezing More Curvature out of Data}, author = {Gower, Robert and Goldfarb, Donald and Richtarik, Peter}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1869--1878}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/gower16.pdf}, url = {https://proceedings.mlr.press/v48/gower16.html}, abstract = {We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.} }
Endnote
%0 Conference Paper %T Stochastic Block BFGS: Squeezing More Curvature out of Data %A Robert Gower %A Donald Goldfarb %A Peter Richtarik %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-gower16 %I PMLR %P 1869--1878 %U https://proceedings.mlr.press/v48/gower16.html %V 48 %X We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.
RIS
TY - CPAPER TI - Stochastic Block BFGS: Squeezing More Curvature out of Data AU - Robert Gower AU - Donald Goldfarb AU - Peter Richtarik BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-gower16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1869 EP - 1878 L1 - http://proceedings.mlr.press/v48/gower16.pdf UR - https://proceedings.mlr.press/v48/gower16.html AB - We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods. ER -
APA
Gower, R., Goldfarb, D. & Richtarik, P.. (2016). Stochastic Block BFGS: Squeezing More Curvature out of Data. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1869-1878 Available from https://proceedings.mlr.press/v48/gower16.html.

Related Material