Excerpt: The main point of this paper is to show that, in situations where the supply of training samples is essentially unlimited, a well designed on-line algorithm converges toward the minimum of the expected cost just as fast as any batch algorithm. In those situations, the convergence speed is mainly limited by the fact that some informative examples have not yet been seen rather than by the fact that the examples already seen have not been fully exploited by the minimization process.

@article{bottou-lecun-2004a,
  author = {Bottou, L\'{e}on and {LeCun}, Yann},
  title = {On-line Learning for Very Large Datasets},
  journal = {Applied Stochastic Models in Business and Industry},
  year = {2005},
  volume = {21},
  number = {2},
  pages = {137-151},
  url = {http://leon.bottou.org/papers/bottou-lecun-2004a},
}

Experimental validation can be found in (Bottou and LeCun, 2004).