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 \(\sqrt{\mbox{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.
Cite
Text
Hutter and Poland. "Prediction with Expert Advice by Following the Perturbed Leader for General Weights." International Conference on Algorithmic Learning Theory, 2004. doi:10.1007/978-3-540-30215-5_22Markdown
[Hutter and Poland. "Prediction with Expert Advice by Following the Perturbed Leader for General Weights." International Conference on Algorithmic Learning Theory, 2004.](https://mlanthology.org/alt/2004/hutter2004alt-prediction/) doi:10.1007/978-3-540-30215-5_22BibTeX
@inproceedings{hutter2004alt-prediction,
title = {{Prediction with Expert Advice by Following the Perturbed Leader for General Weights}},
author = {Hutter, Marcus and Poland, Jan},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2004},
pages = {279-293},
doi = {10.1007/978-3-540-30215-5_22},
url = {https://mlanthology.org/alt/2004/hutter2004alt-prediction/}
}