ML Anthology

Adaptive Online Prediction by Following the Perturbed Leader

Marcus Hutter, Jan Poland
JMLR 2005 pp. 639-660
/jmlr/2005/hutter2005jmlr-adaptive/

Abstract

When applying aggregating strategies to Prediction with Expert Advice (PEA), the learning rate must be adaptively tuned. The natural choice of sqrt(complexity/current loss) renders the analysis of Weighted Majority (WM) derivatives quite complicated. In particular, for arbitrary weights there have been no results proven so far. The analysis of the alternative Follow the Perturbed Leader (FPL) algorithm from Kalai and Vempala (2003) based on Hannan's algorithm is easier. We derive loss bounds for adaptive learning rate and both finite expert classes with uniform weights and countable expert classes with arbitrary weights. For the former setup, our loss bounds match the best known results so far, while for the latter our results are new.

PDF JMLR Semantic Scholar

Cite

Text

Hutter and Poland. "Adaptive Online Prediction by Following the Perturbed Leader." Journal of Machine Learning Research, 2005.

Markdown

[Hutter and Poland. "Adaptive Online Prediction by Following the Perturbed Leader." Journal of Machine Learning Research, 2005.](https://mlanthology.org/jmlr/2005/hutter2005jmlr-adaptive/)

BibTeX

@article{hutter2005jmlr-adaptive,
  title     = {{Adaptive Online Prediction by Following the Perturbed Leader}},
  author    = {Hutter, Marcus and Poland, Jan},
  journal   = {Journal of Machine Learning Research},
  year      = {2005},
  pages     = {639-660},
  volume    = {6},
  url       = {https://mlanthology.org/jmlr/2005/hutter2005jmlr-adaptive/}
}