Fetching the paper…

Reading the bibliography…

2012

Mirror Descent Meets Fixed Share (and feels no regret)

Cesa-Bianchi, Nicolò, Gaillard, Pierre, Lugosi, Gabor et al.

Original
PDF
Post on X

Understand

Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension.

This is done using either a carefully designed projection or by a weight sharing technique.
Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds on a notion of regret generalizing shifting, adaptive, discounted, and other related regrets.
Our analysis also captures and extends the generalized weight sharing technique of Bousquet and Warmuth, and can be refined in several ways, including improvements for small losses and adaptive tuning of parameters.

Mirror Descent Meets Fixed Share (and feels no regret) · Around

Built on

Tracking the best expert
M. Herbster and M. Warmuth · 1998
Earlier work this paper cites.
Derandomizing stochastic prediction strategies
V. Vovk · 1999
Earlier work this paper cites.
Tracking the best linear predictor
M. Herbster and M. Warmuth · 2001
Earlier work this paper cites.
Tracking a small set of experts by mixing past posteriors
O. Bousquet and M.K. Warmuth · 2002
Earlier work this paper cites.

Similar

Adaptive and self-confident on-line learning algorithms
P. Auer, N. Cesa-Bianchi, and C. Gentile · 2002
Cited alongside, same era.
Online convex programming and generalized infinitesimal gradient ascent
M. Zinkevich · 2003
Cited alongside, same era.
Tracking the best of many experts
A. György, T. Linder, and G. Lugosi · 2005
Cited alongside, same era.
Prediction, learning, and games
N. Cesa-Bianchi and G. Lugosi · 2006
Cited alongside, same era.

Then

From extermal to internal regret
A. Blum and Y. Mansour · 2007
Later among the works it cites.
Prediction with expert advice under discounted loss
A. Chernov and F. Zhdanov · 2008
Later among the works it cites.
Efficient learning algorithms for changing environments
E. Hazan and C. Seshadhri · 2009
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…