Tracking the Best Expert

By Mark Herbster, Manfred K. Warmuth. 1995

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

Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “…environment is measured by the number of changes of the reference points over time, which is usually termed as shifting regret or tracking regret [Herbster and Warmuth, 1998, Gy¨orgy et al., 2005, Gyorgy et al., 2012, Gy¨orgy and Szepesv´ari, 2016, Mourtada and Maillard, 2017, Adamskiy et al.,…”
Automated Curriculum Learning for Neural Networks (2017, methodology): “The Fixed Share method (Herbster and Warmuth, 1998) addresses this issue by using an (cid:15) -greedy strategy and mixing in the weights additively.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The interested reader is addressed to Sutton and Barto [1998], Kakade [2003], Szepesvári [2010].”
Online Meta-Learning (2019, neutral): “In the dynamic regret setting (Herbster & Warmuth, 1995; Yang et al., 2016; Besbes et al., 2015), the performance of the online learner’s model sequence is compared against the sequence of optimal solutions corresponding to each loss function in the sequence.”
Online Optimization in Dynamic Environments (2013, methodology): “2 In Fixed Share, each expert (here, each sequence of candidate dynamical models) is assigned a weight that is inversely proportional to its cumulative loss at that point yet with some weight shared amongst all the experts, so that an expert with very small weight can quickly regain weight to become”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “Shifting regret (or tracking regret) The M−shifting regret of an algorithm A ∈ A is defined by [6], [38], [40]–[47]”
Exploiting easy data in online optimization (2014, methodology): “P ROD with an appropriately tuned instance of A = FS (see [19]), with the parameter setting suggested in Corollary 1 guarantees against any assignment of the loss sequence.”
Bandit Algorithms (2020, methodology): “1 are mostly generalizations of algorithms designed for the full information setting, notably the Fixed Share algorithm [Herbster and Warmuth, 1998].”
Context Tree Switching (2011, methodology): “Similar approaches were also considered in the online learning community, in particular the Fixed-Share [Herbster and Warmuth, 1998] algorithm for tracking the best expert over time.”
Skip Context Tree Switching (2014, methodology): “We review here a restricted application of this technique based on the work of Veness et al. (2012) and Herbster & Warmuth (1998).”
Online Learning with Gated Linear Networks (2017, background): “This section presents a solution to this problem based on switching (Veness et al., 2012), a ﬁxed share (Herbster and Warmuth, 1998) variant tailored to the logarithmic loss.”
Efficient Tracking of Large Classes of Experts (2011, unknown): “(10) This, together with (9), implies (8).”
Solving Heads-Up Limit Texas Hold'em (2015, background): “Tracking regret [Herbster and Warmuth, 1998] considers the hindsight performance of a larger set of alternatives, e.g., strategies that change their action at most (k − 1) times.”
Tracking the Best of Many Experts (2005, methodology): “Next we present a variation of the “fixed-share” share update algorithm of Herbster and Warmuth [8].”
Efficient learning algorithms for changing environments (2009, background): “The notion of dealing with stronger performance notions than regret has been dealt with in ( Herbster & Warmuth, 1998; Bousquet & Warmuth, 2003) on \tracking the best expert".”
Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “3 Shifting regret (or tracking regret) The M−shifting regret of an algorithm A ∈ A is defined by [6, 38, 40–47] R̃T := T ∑”
The On-Line Shortest Path Problem Under Partial Monitoring (2007, background): “Keywords: On-line learning, shortest path problem, multi-armed bandit problem”