Drifting games and Brownian motion. (English) Zbl 1052.68147

Summary: We combine the results of R. E. Schapire [Mach. Learning 43, 265–291 (2001; Zbl 0988.68149)] and Y. Freund [Mach. Learning 43, 293–318 (2001; Zbl 0988.68150)] and derive a continuous variant of a large class of drifting games. Our analysis furthers the understanding of the relationship between boosting, drifting games, and Brownian motion and yields a differential equation that describes the core of the problem.


68W05 Nonnumerical algorithms


Full Text: DOI


[1] Aslam, J., MIT technical report, (1995)
[2] Aslam, J.A.; Dhagat, A., Searching in the presence of linearly bounded errors, Proceedings of the twenty third annual ACM symposium on theory of computing, (May 1991)
[3] Aslam, J.A.; Dhagat, A., On-line algorithms for 2-coloring hypergraphs via chip games, Theoret. comput. sci., 112, 355-369, (1993) · Zbl 0768.68115
[4] Breiman, L., Probability, (1992), SIAM Philadelphia
[5] Cesa-Bianchi, N.; Freund, Y.; Helmbold, D.P.; Warmuth, M.K., On-line prediction and conversion strategies, Mach. learning, 25, 71-110, (1996)
[6] Dhagat, A.; Gács, P.; Winkler, P., On playing “twenty questions” with a liar, Proceedings of the third annual ACM-SIAM symposium on discrete algorithms (Orlando, FL, 1992), (1992), Assoc. Comput. Mach New York, p. 16-22 · Zbl 0818.90138
[7] Freund, Y., Boosting a weak learning algorithm by majority, Inform. and comput., 121, 256-285, (1995) · Zbl 0833.68109
[8] Freund, Y., An adaptive version of the boost by majority algorithm, Mach. learning, 43, 293-318, (2001) · Zbl 0988.68150
[9] Freund, Y.; Schapire, R.E., A decision-theoretic generalization of on-line learning and an application to boosting, J. comput. system sci., 55, 119-139, (1997) · Zbl 0880.68103
[10] Gardiner, C.W., Handbook of stochastic methods, (1985), Springer-Verlag Berlin/New York · Zbl 0862.60050
[11] Mason, L.; Baxter, J.; Bartlett, P.; Frean, M., Functional gradient techniques for combining hypotheses, ()
[12] Mason, L.; Baxter, J.; Bartlett, P.; Frean, M., Boosting algorithms as gradient descent, Advances in neural information processing systems, (2000)
[13] Schapire, R.E., Drifting games, Mach. learning, 43, 265-291, (2001) · Zbl 0988.68149
[14] Schapire, R.E.; Singer, Y., Improved boosting algorithms using confidence-rated predictions, Mach. learning, 37, 297-336, (1999) · Zbl 0945.68194
[15] Shafer, G.; Vovk, V., Probability and finance, It’s only a game!, (2001), Wiley New York · Zbl 0985.91024
[16] Spencer, J., Ten lectures on the probabilistic method, (1987), SIAM Philadelphia
[17] Spencer, J., Ulam’s searching game with a fixed number of lies, Theoret. comput. sci., 95, 307-321, (1992) · Zbl 0749.90102
[18] Vovk, V.G., A game of prediction with expert advice, J. comput. system sci., 56, 153-173, (1998) · Zbl 0945.68528
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.