Follow the leader if you can, hedge if you must

By S. D. de Rooij, Tim van Erven, Peter D. Grünwald, Wouter M. Koolen. 2013

194 citations recorded by the source corpus.

Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has poor performance for worst-case data. Other hedging strategies have better worst-case guarantees but may perform much worse than FTL if the data are not maximally adversarial. We introduce the FlipFlop algorithm, which is the first method that provably combines the best of both worlds. As a stepping stone for our analysis, we develop AdaHedge, which is a new way of dynamically tuning the learning rate in Hedge without using the doubling trick. AdaHedge refines a method by Cesa-Bianchi, Mansour, and Stoltz (2007), yielding improved worst-case guarantees. By interleaving AdaHedge and FTL, FlipFlop achieves regret within a constant factor of the FTL regret, without sacrificing AdaHedge's worst-case guarantees. AdaHedge and FlipFlop do not need to know the range of the losses in advance; moreover, unlike earlier methods, both have the intuitive property that the issued weights are invariant under rescaling and translation of the losses. The losses are also allowed to be negative, in which case they may be interpreted as gains.

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

AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, background): “In fact, unaware to the authors at the time, a very similar update to the WNGrad stepsize was previously proposed in [22], and generalized to optimization in [19].”
Efficient tracking of a growing number of experts (2017, background): “In this case, the growing body of work on the automatic tuning of the learning rate (de Rooij et al., 2014; Koolen et al., 2014) as well as alternative aggregation schemes (Wintenberger, 2017; Koolen and van Erven, 2015; Luo and Schapire, 2015) might open the path for even further improvements.”
Inconsistency of Bayesian Inference for Misspecified Linear Models, and a Proposal for Repairing It (2014, background): “The Mixability Gap We express posterior nonconcentration in terms of the mixability gap (Grünwald, 2012, de Rooij et al., 2014).”
Exploiting easy data in online optimization (2014, unknown): “Figure : Hand tuned loss sequences from [1] Discussion”