This is an old revision of the document!
Abstract: The SGDQN algorithm is a stochastic gradient descent algorithm that makes careful use of second-order information and splits the parameter update into independently scheduled components. Thanks to this design, SGDQN iterates nearly as fast as a first-order stochastic gradient descent but requires less iterations to achieve the same accuracy. This algorithm won the “Wild Track” of the first PASCAL Large Scale Learning Challenge.
Note: The appendix contains a derivation of upper and lower bounds on the asymptotic convergence speed of stochastic gradient algorithm. This result is exact in the case of second order stochastic gradient.
@article{bordes-bottou-gallinari-2009, author = {Bordes, Antoine and Bottou, L\'{e}on and Gallinari, Patrick}, title = {SGD-QN: Careful Quasi-Newton Stochastic Gradient Descent}, journal = {Journal of Machine Learning Research}, year = {2009}, volume = {10}, pages = {1737--1754}, month = {July}, url = {http://leon.bottou.org/papers/bordes-bottou-gallinari-2009}, }
The complete source code of LibSGDQN is available on Antoine's web site. This source code comes with a script that replicates the experiments discussed in this paper.
There is an erratum for this paper: JMLR, 11:2229−2240, 2010, pdf.