Follow the Leader If You Can, Hedge If You Must

Abstract : 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.
Type de document :
Pré-publication, Document de travail
2013
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00920549
Contributeur : Tim Van Erven <>
Soumis le : mercredi 18 décembre 2013 - 16:45:06
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 20 mars 2014 - 11:25:49

Fichier

flipflop-rev1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00920549, version 1

Collections

Citation

Steven De Rooij, Tim Van Erven, Peter Grünwald, Wouter Koolen. Follow the Leader If You Can, Hedge If You Must. 2013. 〈hal-00920549〉

Partager

Métriques

Consultations de la notice

241

Téléchargements de fichiers

157