Drifting games

Research output: Contribution to conferencePaper

5 Scopus citations

Abstract

We introduce the study a general, abstract game played between two players called the drifter and the adversary. The game is played in a series of rounds using a finite set of 'chips' which are moved about in Rn. On each round, the drifter assigns a desired direction of movement and an importance weight to each of the chips. The adversary then moves the chips in any way that need only be weakly correlated with the desired directions assigned by the drifter. The drifter's goal is to cause the chips to be moved to low-loss positions, where the loss of each chip at its final position is measured by a given loss function. We present a drifter algorithm for this game and prove an upper bound on its performance. We also prove a lower bound showing that the algorithm is essentially optimal for a large number of chips. We discuss computational methods for efficiently implementing our algorithm. We show that our general drifting-game algorithm subsumes some well studied boosting and on-line learning algorithms whose analyses follow as easy corollaries of our general result.

Original languageEnglish (US)
Pages114-124
Number of pages11
StatePublished - Dec 1 1999
Externally publishedYes
EventProceedings of the 1999 12th Annual Conference on Computational Learning Theory (COLT'99) - Santa Cruz, CA, USA
Duration: Jul 6 1999Jul 9 1999

Conference

ConferenceProceedings of the 1999 12th Annual Conference on Computational Learning Theory (COLT'99)
CitySanta Cruz, CA, USA
Period7/6/997/9/99

All Science Journal Classification (ASJC) codes

  • Computational Mathematics

Fingerprint Dive into the research topics of 'Drifting games'. Together they form a unique fingerprint.

  • Cite this

    Schapire, R. E. (1999). Drifting games. 114-124. Paper presented at Proceedings of the 1999 12th Annual Conference on Computational Learning Theory (COLT'99), Santa Cruz, CA, USA, .