Skip navigation
Skip navigation
Open Research will be down for maintenance between 8:00 and 8:15 am on Tuesday, December 1 2020.

Adaptive online prediction by following the perturbed leader

Hutter, Marcus; Poland, Jan

Description

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...[Show more]

dc.contributor.authorHutter, Marcus
dc.contributor.authorPoland, Jan
dc.date.accessioned2015-09-01T04:39:56Z
dc.date.available2015-09-01T04:39:56Z
dc.identifier.issn1533-7928
dc.identifier.urihttp://hdl.handle.net/1885/15049
dc.description.abstractWhen 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.
dc.publisherJournal of Machine Learning Research
dc.rights© 2005 Marcus Hutter and Jan Poland. http://www.sherpa.ac.uk/romeo/issn/1532-4435/..."Publisher's version/PDF may be used. On open access repositories" from SHERPA/RoMEO site (as at 1/09/15).
dc.sourceJournal of Machine Learning Research
dc.subjectprediction with expert advice
dc.subjectfollow the perturbed leader
dc.subjectgeneral weights
dc.subjectadaptive learning rate
dc.subjectadaptive adversary
dc.subjecthierarchy of experts
dc.subjectexpected and high probability bounds
dc.subjectgeneral alphabet and loss
dc.subjectonline sequential prediction
dc.titleAdaptive online prediction by following the perturbed leader
dc.typeJournal article
local.identifier.citationvolume6
dc.date.issued2005-04
local.publisher.urlhttp://www.jmlr.org/
local.type.statusPublished Version
local.contributor.affiliationHutter, M., Research School of Computer Science, The Australian National University
local.bibliographicCitation.startpage639
local.bibliographicCitation.lastpage660
CollectionsANU Research Publications

Download

File Description SizeFormat Image
Hutter and Poland Adaptive Online Prediction 2005.pdf187.12 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator