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 = {Nicol N. Schraudolph and Jin Yu and Simon Günter}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {436--443}, year = {2007}, editor = {Marina Meila and Xiaotong Shen}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 436--443 %U http://proceedings.mlr.press %V 2 %W PMLR %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 PY - 2007/03/11 DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-schraudolph07a PB - PMLR SP - 436 DP - PMLR EP - 443 L1 - http://proceedings.mlr.press/v2/schraudolph07a/schraudolph07a.pdf UR - http://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 PMLR 2:436-443

Related Material