Prediction with expert advice by following the perturbed leader for general weights

Marcus Hutter; Jan Poland

doi:10.1007/978-3-540-30215-5_22

Prediction with expert advice by following the perturbed leader for general weights

Marcus Hutter^*, Jan Poland

^*Corresponding author for this work

Research output: Contribution to journal › Conference article › peer-review

23 Citations (Scopus)

Abstract

When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of √complexity/current loss renders the analysis of Weighted Majority 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 [KV03] (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
Pages (from-to)	279-293
Number of pages	15
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3244
DOIs	https://doi.org/10.1007/978-3-540-30215-5_22
Publication status	Published - 2004
Externally published	Yes
Event	15th International Conference ALT 2004: Algorithmic Learning Theory - Padova, Italy Duration: 2 Oct 2004 → 5 Oct 2004

Access to Document

10.1007/978-3-540-30215-5_22

Cite this

@article{b78eea36653a49e1afee3852d2664e02,

title = "Prediction with expert advice by following the perturbed leader for general weights",

abstract = "When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of √complexity/current loss renders the analysis of Weighted Majority 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 [KV03] (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.",

author = "Marcus Hutter and Jan Poland",

year = "2004",

doi = "10.1007/978-3-540-30215-5_22",

language = "English",

volume = "3244",

pages = "279--293",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Verlag",

note = "15th International Conference ALT 2004: Algorithmic Learning Theory ; Conference date: 02-10-2004 Through 05-10-2004",

}

TY - JOUR

T1 - Prediction with expert advice by following the perturbed leader for general weights

AU - Hutter, Marcus

AU - Poland, Jan

PY - 2004

Y1 - 2004

N2 - When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of √complexity/current loss renders the analysis of Weighted Majority 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 [KV03] (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, the learning rate must be adaptively tuned. The natural choice of √complexity/current loss renders the analysis of Weighted Majority 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 [KV03] (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.

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

U2 - 10.1007/978-3-540-30215-5_22

DO - 10.1007/978-3-540-30215-5_22

M3 - Conference article

AN - SCOPUS:21844436185

SN - 0302-9743

VL - 3244

SP - 279

EP - 293

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 15th International Conference ALT 2004: Algorithmic Learning Theory

Y2 - 2 October 2004 through 5 October 2004

ER -

Prediction with expert advice by following the perturbed leader for general weights

Abstract

Access to Document

Other files and links

Fingerprint

Cite this