Adaptive online prediction by following the perturbed leader

Marcus Hutter; Jan Poland

Adaptive online prediction by following the perturbed leader

Marcus Hutter^*, Jan Poland

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

52 Citations (Scopus)

Abstract

When applying aggregating strategies to Prediction with Expert Advice (PEA), the learning rate must be adaptively tuned. The natural choice of √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.

Original language	English
Journal	Journal of Machine Learning Research
Volume	6
Publication status	Published - 2005
Externally published	Yes

Cite this

@article{7118d7b51806417dbd5c559d95e19df7,

title = "Adaptive online prediction by following the perturbed leader",

abstract = "When applying aggregating strategies to Prediction with Expert Advice (PEA), the learning rate must be adaptively tuned. The natural choice of √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.",

keywords = "Adaptive adversary, Adaptive learning rate, Expected and high probability bounds, Follow the perturbed leader, General alphabet and loss, General weights, Hierarchy of experts, Online sequential prediction, Prediction with expert advice",

author = "Marcus Hutter and Jan Poland",

year = "2005",

language = "English",

volume = "6",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

}

TY - JOUR

T1 - Adaptive online prediction by following the perturbed leader

AU - Hutter, Marcus

AU - Poland, Jan

PY - 2005

Y1 - 2005

N2 - When applying aggregating strategies to Prediction with Expert Advice (PEA), the learning rate must be adaptively tuned. The natural choice of √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.

AB - When applying aggregating strategies to Prediction with Expert Advice (PEA), the learning rate must be adaptively tuned. The natural choice of √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.

KW - Adaptive adversary

KW - Adaptive learning rate

KW - Expected and high probability bounds

KW - Follow the perturbed leader

KW - General alphabet and loss

KW - General weights

KW - Hierarchy of experts

KW - Online sequential prediction

KW - Prediction with expert advice

UR - http://www.scopus.com/inward/record.url?scp=21844465698&partnerID=8YFLogxK

M3 - Article

SN - 1532-4435

VL - 6

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

ER -

Adaptive online prediction by following the perturbed leader

Abstract

Other files and links

Fingerprint

Cite this