Game theory, on-line prediction and boosting

By Yoav Freund, Robert E. Schapire. 1996

We study the close connections between game theory, on-line prediction and boosting. After a brief review of game theory, we describe an algorithm for learning to play repeated games based on the on-line prediction methods of Littlestone and Warmuth. The analysis of this algorithm yields a simple proof of von Neumann’s famous minmax theorem, as well as a provable method of approximately solving a game. We then show that the on-line prediction model is obtained by applying this gameplaying algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the “dual” of this game.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (2017, background): “By the result of Freund and Schapire [1996], the average plays of both players over time converge to an approximate equilibrium of the game, as long as the Learner has low regret.”
A Reductions Approach to Fair Classification (2018, methodology): “Following Freund & Schapire (1996), the average play of both players converges to the saddle point.”
Training GANs with Optimism (2017, background): “The latter theoretical result is of independent interest, since solving zero-sum games via no-regret dynamics has found applications in many areas of machine learning, such as boosting (Freund & Schapire, 1996).”
Algorithmic Fairness (2020, background): “Note that other closely related problems are aimed at finding equilibrium (minimax) points in the field of game theory , and therefore, game-theoretic schemes may also be used for solutions [4, 5, 32, 55].”
Analyzing Complex Strategic Interactions in Multi-Agent Systems (2002, methodology): “Greenwald and Kephart (2001) observe empirically that agents using methods based on no external regret (Freund & Schapire 1996) and no internal regret (Foster & Vohra 1997) learning play pure strategies in a frequency corresponding to a Nash equilibrium.”
Introduction to Multi-Armed Bandits (2019, methodology): “inberg et al., 2009b; Daskalakis et al., 2018). The repeated game between two regret-minimizing algorithms serves as a subroutine for a variety of algorithmic problems. This approach can be traced to Freund and Schapire (1996, 1999). It has been used as a unifying algorithmic framework for several p”
Bayesian Games for Adversarial Regression Problems (2013, background): “Finding Equilibrium points in adversarial learning problems has been studied for regret minimization problems where it leads to near-optimal solutions (Freund & Schapire, 1996).”
Boosting the margin: A new explanation for the effectiveness of voting methods (1997, methodology): “Related to this, the optimal margin method uses quadratic programming for its optimization, whereas the boosting algorithm can be seen as a method for approximate linear programming [11].”
Advance and Prospects of AdaBoost Algorithm (2013, unknown): “AdaBoost 与博弈理论的联系由 Breiman 、 Freund 和 Schapire 等提出 [16 , 48 − 50] , AdaBoost.”
AdWords and generalized on-line matching (2005, methodology): “Blending this idea together with statistical information seems promising, e.g., using techniques from learning theory, such as learning from experts ([ FS96 ] and references therein).”
An Introduction to Boosting and Leveraging (2002, methodology): “However, from the Min-Max theorem of linear programming [193] (see Theorem 4 below) one finds that the achievable margin ρ∗ is at least γ [69, 27, 72].”
Adaptive computation and machine learning (1998, unknown): “1, stating that the problem of finding a minimum consistent DFA is NP-hard, is due to Gold [1978]. This result was later extended by Angluin [1978].”
Prediction Games and Arcing Algorithms (1999, background): “The definition of the matrix game for classification appeared in Freund and Schapire[1996b] .”