A Stochastic Quasi-Newton Method for Online Convex Optimization

Nicol N. Schraudolph, Jin Yu, Simon Günter
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:436-443, 2007.

Abstract

We develop stochastic variants of the well-known BFGS quasi-Newton optimization method, in both full and memory-limited (LBFGS) forms, for online optimization of convex functions. The resulting algorithm performs comparably to a well-tuned natural gradient descent but is scalable to very high-dimensional problems. On standard benchmarks in natural language processing, it asymptotically outperforms previous stochastic gradient methods for parameter estimation in conditional random fields. We are working on analyzing the convergence of online (L)BFGS, and extending it to nonconvex optimization problems.

Cite this Paper


BibTeX
@InProceedings{pmlr-v2-schraudolph07a, title = {A Stochastic Quasi-Newton Method for Online Convex Optimization}, author = {Schraudolph, Nicol N. and Yu, Jin and Günter, Simon}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {436--443}, year = {2007}, editor = {Meila, Marina and Shen, Xiaotong}, volume = {2}, series = {Proceedings of Machine Learning Research}, address = {San Juan, Puerto Rico}, month = {21--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v2/schraudolph07a/schraudolph07a.pdf}, url = {https://proceedings.mlr.press/v2/schraudolph07a.html}, abstract = {We develop stochastic variants of the well-known BFGS quasi-Newton optimization method, in both full and memory-limited (LBFGS) forms, for online optimization of convex functions. The resulting algorithm performs comparably to a well-tuned natural gradient descent but is scalable to very high-dimensional problems. On standard benchmarks in natural language processing, it asymptotically outperforms previous stochastic gradient methods for parameter estimation in conditional random fields. We are working on analyzing the convergence of online (L)BFGS, and extending it to nonconvex optimization problems.} }
Endnote
%0 Conference Paper %T A Stochastic Quasi-Newton Method for Online Convex Optimization %A Nicol N. Schraudolph %A Jin Yu %A Simon Günter %B Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2007 %E Marina Meila %E Xiaotong Shen %F pmlr-v2-schraudolph07a %I PMLR %P 436--443 %U https://proceedings.mlr.press/v2/schraudolph07a.html %V 2 %X We develop stochastic variants of the well-known BFGS quasi-Newton optimization method, in both full and memory-limited (LBFGS) forms, for online optimization of convex functions. The resulting algorithm performs comparably to a well-tuned natural gradient descent but is scalable to very high-dimensional problems. On standard benchmarks in natural language processing, it asymptotically outperforms previous stochastic gradient methods for parameter estimation in conditional random fields. We are working on analyzing the convergence of online (L)BFGS, and extending it to nonconvex optimization problems.
RIS
TY - CPAPER TI - A Stochastic Quasi-Newton Method for Online Convex Optimization AU - Nicol N. Schraudolph AU - Jin Yu AU - Simon Günter BT - Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-schraudolph07a PB - PMLR DP - Proceedings of Machine Learning Research VL - 2 SP - 436 EP - 443 L1 - http://proceedings.mlr.press/v2/schraudolph07a/schraudolph07a.pdf UR - https://proceedings.mlr.press/v2/schraudolph07a.html AB - We develop stochastic variants of the well-known BFGS quasi-Newton optimization method, in both full and memory-limited (LBFGS) forms, for online optimization of convex functions. The resulting algorithm performs comparably to a well-tuned natural gradient descent but is scalable to very high-dimensional problems. On standard benchmarks in natural language processing, it asymptotically outperforms previous stochastic gradient methods for parameter estimation in conditional random fields. We are working on analyzing the convergence of online (L)BFGS, and extending it to nonconvex optimization problems. ER -
APA
Schraudolph, N.N., Yu, J. & Günter, S.. (2007). A Stochastic Quasi-Newton Method for Online Convex Optimization. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:436-443 Available from https://proceedings.mlr.press/v2/schraudolph07a.html.

Related Material