Non-statistical analysis of on-line learning algorithms

In the on-line learning model, learning takes place in a sequence of trials. On each trial, the learner makes some kind of prediction and then receives some kind of feedback so that training and testing take place all at the same time. There are a number of simple but highly robust learning algorithms for this model (and its many variations). Very often, these algorithms can be analyzed and shown to work quite well even when no statistical assumptions of any kind are made about the process producing the observed data. Many of the algorithms and methods of analysis used in this area can trace their roots to the work of Littlestone, Vovk and Warmuth:

• Nick Littlestone.
  Learning when irrelevant attributes abound: A new linear-threshold algorithm.
  Machine Learning, 2:285-318, 1988.

• Nick Littlestone and Manfred K. Warmuth.
  The weighted majority algorithm.
  Information and Computation, 108:212-261, 1994.

• Volodimir G. Vovk.
  Aggregating strategies.
  In Proceedings of the Third Annual Workshop on Computational Learning Theory, pages 371-383, 1990.

• Robert E. Schapire.
  Drifting games.
  Machine Learning, 43(3):265-291, 2001.
  Postscript or gzipped postscript.

• Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire.
  The non-stochastic multi-armed bandit problem.
  Accepted pending revision to SIAM Journal on Computing .
  Postscript or gzipped postscript of journal submission (11/20/01).

• Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire.
  Gambling in a rigged casino: The adversarial multi-armed bandit problem.
  Extended abstract appeared in 36th Annual Symposium on Foundations of Computer Science, pages 322-331, 1995.
  Postscript or compressed postscript of significantly revised journal submission (6/8/98).

• Yoav Freund and Robert E. Schapire.
  Large margin classification using the perceptron algorithm.
  Machine Learning, 37(3):277-296, 1999.
  Postscript or compressed postscript.

• William W. Cohen, Robert E. Schapire and Yoram Singer.
  Learning to order things.
  Journal of Artificial Intelligence Research, 10:243-270, 1999.
  Postscript or compressed postscript.

• Yoav Freund and Robert E. Schapire.
  Adaptive game playing using multiplicative weights.
  Games and Economic Behavior, 29:79-103, 1999.
  Postscript or compressed postscript.

• Yoav Freund, Robert E. Schapire, Yoram Singer and Manfred K. Warmuth.
  Using and combining predictors that specialize.
  In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pages 334--343, 1997.
  Postscript or compressed postscript.

• Yoav Freund and Robert E. Schapire.
  Game theory, on-line prediction and boosting.
  In Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996.
  Postscript or compressed postscript.

• David D. Lewis, Robert E. Schapire, James P. Callan, and Ron Papka.
  Training algorithms for linear text classifiers.
  In SIGIR '96: Proceedings of the 19th Annual International Conference on Research and Development in Information Retrieval, 1996.
  Postscript or compressed postscript.

• David P. Helmbold, Robert E. Schapire, Yoram Singer, and Manfred K. Warmuth.
  On-line portfolio selection using multiplicative updates.
  Mathematical Finance, 8(4):325-347, 1998.
  Postscript or compressed postscript.

• Yoav Freund and Robert E. Schapire.
  A decision-theoretic generalization of on-line learning and an application to boosting.
  Journal of Computer and System Sciences, 55(1):119-139, 1997.
  Postscript or compressed postscript.

• Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, and Manfred K. Warmuth.
  How to use expert advice.
  Journal of the Association for Computing Machinery, 44(3):427-485, 1997.
  Postscript or compressed postscript.

• David P. Helmbold and Robert E. Schapire.
  Predicting nearly as well as the best pruning of a decision tree.
  Machine Learning, 27(1):51-68, 1997.
  Postscript or compressed postscript.

Back to my home page.
Last update: December 2, 2002.

Free software for viewing postscript files is available here.