Global Convergence of Online Limited Memory BFGS
  Global convergence of an online (stochastic) limited memory version of the
Broyden-Fletcher- Goldfarb-Shanno (BFGS) quasi-Newton method for solving
optimization problems with stochastic objectives that arise in large scale
machine learning is established. Lower and upper bounds on the Hessian
eigenvalues of the sample functions are shown to suffice to guarantee that the
curvature approximation matrices have bounded determinants and traces, which,
in turn, permits establishing convergence to optimal arguments with probability
1. Numerical experiments on support vector machines with synthetic data
showcase reductions in convergence time relative to stochastic gradient descent
algorithms as well as reductions in storage and computation relative to other
online quasi-Newton methods. Experimental evaluation on a search engine
advertising problem corroborates that these advantages also manifest in
practical applications.
