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.
@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}
}
The online version of this paper has been slightly revised over time.
| Date | Change |
|---|---|
| October 2012 | The proof of the global confinement result in section 5.2 has been corrected. Slight changes in the assumptions were necessary. Thanks to Silvère Bonnabel for pointing out the error. |
| October 2012 | A reference to (Fort & Pages, 1995) has been added to illustrate what it takes to weaken the nontrivial regularity assumption used in section 5. This is important for a number of clustering algorithms. |
| March 2014 | Typos – thanks to Levent Sagun. |
| April 2017 | Sign typos – thanks to Wei Wen. |
| May 2018 | The reasoning between (4.21) and (4.23) was clarified – thanks to Francesco Orabona. |