Adaptive game playing using multiplicative weights

By Yoav Freund, Robert E. Schapire. 1999

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Contextual Dueling Bandits (2015, methodology): “Under this interpretation, it becomes especially natural to use ordinary no-regret learning algorithms as players of this game since it is known that such algorithms, when properly configured for this purpose, will converge to maxmin or minmax strategies (Freund and Schapire, 1999).”
Negative Momentum for Improved Game Dynamics (2018, background): “Interestingly, this geometric divergence implies that even a uniform averaging of the iterates (standard in game optimization to ensure convergence (Freund et al., 1999)) cannot alleviate this divergence.”
Introduction to Online Convex Optimization (2016, background): “The beautiful connection between low-regret algorithms and solving zero-sum games was discovered by Freund and Schapire (45).”
The Unusual Effectiveness of Averaging in GAN Training (2018, background): “Averaging generator and discriminator parameters is known to be an optimal solution for convex-concave min-max games (Freund & Schapire, 1999).”
Batch Policy Learning under Constraints (2019, background): “From a game-thoeretic perspective, the problem becomes finding the equilibrium of a two-player game between the π−player and the λ−player (Freund & Schapire, 1999).”
An Online Learning Approach to Generative Adversarial Networks (2017, methodology): “The proof makes use of a theorem due to Freund and Schapire (1999) which shows that if both A 1 and A 2 ensure no-regret then it implies convergence to approximate MNE.”
Online Convex Programming and Generalized Infinitesimal Gradient Ascent (2003, methodology): “…this solution is very undesirable. regret in repeated games and in the experts domain, such as (Blackwell, 1956; Foster & Vohra, 1999; Foster, 1999; Freund & Schapire, 1999; Fudenberg & Levine, 1995; Fudenberg & Levine, 1997; Hannan, 1957; Hart & Mas-Colell, 2000; Hart & Mas-Colell, 2001;…”
An Introduction to Boosting and Leveraging (2002, methodology): “Moreover, it is similar to an algorithm proposed in [71] (see also [177]).”
Submodular Function Maximization (2014, background): “There are algorithms which achieve O ( | V | log T ) expected regret for stochastic rewards with bandit feedback (Auer et al., 2002), O ( T log | V | ) for the non-stochastic rewards with full information feedback (Freund and Schapire, 1999), and”
A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits (2015, background): “This ‘punitive’ approach of exponential weighing departs from EXP3 and other weighing algorithms which gratify the most rewarding arms while kindly ignoring the nonrewarding ones (Freund and Schapire, 1999; Cesa-Bianchi and Lugosi, 2006).”
Online Deep Learning: Learning Deep Neural Networks on the Fly (2017, background): “RT ≤ √ T lnN , where N is the number of experts [Freund and Schapire, 1999], which in our case is the network depth.”
Regret bounds for sleeping experts and bandits (2010, methodology): “To achieve this regret we transform the sleeping experts problem to a problem with n! experts that are always awake, and we choose among these n! experts using the Hedge algorithm ( Freund and Schapire 1999 ).”
On Early Stopping in Gradient Descent Learning (2007, background): “For example, studies on both lead a road to game theory [e.g. Breiman 1999; Freund and Schapire 1999; Schapire 2001; Stoltz and Lugosi 2004], on the ﬁrst have been seen in [Rudin, Daubechies, and Schapire 2004] and on the second lead to the functional gradient descent view with general convex loss…”
The Boosting Approach to Machine Learning An Overview (2003, methodology): “For instance, Freund and Schapire [30] tested AdaBoost on a set of UCI benchmark datasets [54] using C4.5 [60] as a base learning algorithm, as well as an algorithm that finds the best “decision stump” or single-test decision tree.”
An Overview of Cooperative and Competitive Multiagent Learning (2005, background): “[52] and [50] independently show that a multiplicative-weight algorithm exhibits universal consistency.”