Tracking the Best Linear Predictor

By Mark Herbster, Manfred K. Warmuth. 2001

263 citations recorded by the source corpus.

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

Online Convex Optimization in Dynamic Environments (2015, background): “This idea is typically referred to as “tracking” or “shifting” regret [20], [21], which is closely-related to “adaptive” regret [22], [23].”
Memory Limited, Streaming PCA (2013, methodology): “They go under a variety of names, including Incremental PCA (though the term Incremental has been used in the online setting as well [10]), Hebbian learning, and stochastic power method [1].”
Online Convex Programming and Generalized Infinitesimal Gradient Ascent (2003, methodology): “This is a generalization of both work in minimizing error online (Cesa- Bianchi et al., 1994; Kivinen & Warmuth, 1997; Gordon, 1999; Herbster & Warmuth, 2001; Kivinen & Warmuth, 2001) and of the experts problem (Freund & Schapire, 1999; Littlestone & Warmuth, 1989).”
The uniform hardcore lemma via approximate Bregman projections (2009, methodology): “Our algorithm is also inspired by Warmuth and Kuzmin's [16] technique (which, in turn, uses ideas that originated in the work Herbster and Warmuth [4]) of obtaining smooth distributions from any other distribution by projecting it into the set of smooth distributions using the Kullback-Leibler diver”
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].”
A new look at shifting regret (2012, background): “…this section we show thateir algorithms in fact work very well in comparison with a much larger class of sequencesu1, . . . ,uT that are “regular”—that is,m(uT1 ), defined in (2) is small—and “sparse” in the sense that the quantity n(uT1 ) = d∑ i=1 max t=1,...,T ui,t A NEW LOOK AT SHIFTING…”
Mirror Descent Meets Fixed Share (and feels no regret) (2012, unknown): “We now introduce a generalized notion of shifting regret which uniﬁes and generalizes the notions of discounted regret (see [3, Section 2.11]), adaptive regret (see [8]), and shifting regret (see [2]).”
Learning to search: structured prediction techniques for imitation learning (2009, background): “…optimization setting that generalizes a breadth of prior work in minimizing errors online (Cesa-Bianchi, Long, & Warmuth, 1994; Kivinen & Warmuth, 1997; Gordon, 1999; Herbster & Warmuth, 2001; Kivinen & Warmuth, 2001) and expert problems (Freund & Schapire, 1999; Littlestone & Warmuth, 1989).”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “In the literature, dynamic regret is also referred to as tracking regret or shifting regret (Littlestone & Warmuth, 1994; Herbster & Warmuth, 1998; 2001).”
Online learning with kernels (2001, methodology): “The stochastic gradient descent algorithms we propose (collectively called NORMA) differ from the tracking algorithms of Warmuth, Herbster, and Auer [5], [12], [13] insofar as we do not require that the norm of the hypothesis be bounded beforehand.”
Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties (2010, unknown): “ and its Properties: The Euclidean projection operator onto a set Ω ⊆Rnis deﬁned as PΩ(w′) = argmin w∈Ω kw−w′k. (3) The projection operator satisﬁes the following property (s ee e.g. equation (59) in [5]): hPΩ (ˆw) −w,ˆ wˆ −wi≤−kPΩ (ˆw) −wˆk 2 ≤0, ∀w∈Ω. (4) A Result from Analysis of Markov Chains: W”
Online Optimization in Dynamic Environments (2013, background): “been studied previously in the literature in the context of tracking regret (also known as shifting regret) [25, 26], and the closely-related concept of adaptive regret [21,27].”
The On-Line Shortest Path Problem Under Partial Monitoring (2007, background): “Efficient solutions, with time and space complexity proportional to the number of edges rather than to the number of paths (the latter typically being exponential in the number of edges), have been given in the full information case, where in each round the weights of all the edges are revealed afte”
On the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithms (2010, methodology): “A similar problem was tackled by Herbster and Warmuth [ HW01 ], who provided O(mlog(m)) and O(m) algorithms for performing entropic projections.”
Non-Stochastic Bandit Slate Problems (2010, methodology): “This algorithm is implicit in the work of [13, 18].”
New Analysis and Algorithm for Learning with Drifting Distributions (2012, background): “Variants of this model where the target is allowed to change a fixed number of times have also been studied [3, 4, 5, 6].”