Online Algorithms and Stochastic Approximations

Abstract: The convergence of online learning algorithms is analyzed using the tools of the stochastic approximation theory, and proved under very weak conditions. A general framework for online learning algorithms is first presented. This framework encompasses the most common online learning algorithms in use today, as illustrated by several examples. The stochastic approximation theory then provides general results describing the convergence of all these learning algorithms at once.

Léon Bottou: Online Algorithms and Stochastic Approximations, Online Learning and Neural Networks, Edited by David Saad, Cambridge University Press, Cambridge, UK, 1998.

online-1998.djvu online-1998.pdf online-1998.ps.gz

@incollection{bottou-98x,
  author = {Bottou, L\'{e}on},
  title = {Online Algorithms and Stochastic Approximations},
  booktitle = {Online Learning and Neural Networks},
  editor = {Saad, David},
  publisher = {Cambridge University Press},
  address = {Cambridge, UK},
  year = {1998},
  url = {http://leon.bottou.org/papers/bottou-98x},
  note = {revised, oct 2012}
}

Revision history

The online version of this paper has been slightly revised in October 2012.

A couple typos were fixed in March 2014. Thanks to Levent Sagun for pointing them out.