article

Adaptive Online Prediction by Following the Perturbed Leader

Authors:

Marcus Hutter,

Jan PolandAuthors Info & Claims

The Journal of Machine Learning Research, Volume 6

Pages 639 - 660

Published: 01 December 2005 Publication History

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.

Cited By

View all

Wang GHu ZMuthukumar VAbernethy JKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Adaptive oracle-efficient online learningProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601970(23398-23411)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601970
Ahmed Ouameur MAnh LMassicotte DJeon Gde Figueiredo F(2022)Adversarial bandit approach for RIS-aided OFDM communicationEURASIP Journal on Wireless Communications and Networking10.1186/s13638-022-02184-62022:1Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1186/s13638-022-02184-6
Mhaisen NSinha APaschos GIosifidis G(2022)Optimistic No-regret Algorithms for Discrete CachingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35706086:3(1-28)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3570608
Show More Cited By

Adaptive Online Prediction by Following the Perturbed Leader
1. Computing methodologies

Recommendations

Adaptive online learning
NIPS'15: Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2

We propose a general framework for studying adaptive regret bounds in the online learning setting, subsuming model selection and data-dependent bounds. Given a data- or model-dependent bound we ask, "Does there exist some algorithm achieving this bound?" ...
On following the perturbed leader in the bandit setting
ALT'05: Proceedings of the 16th international conference on Algorithmic Learning Theory

In an online decision problem an algorithm is at each time step required to choose one of the feasible points without knowing the cost associated with it. An adversary assigns the cost to possible decisions either obliviously or adaptively. The online ...
The follow perturbed leader algorithm protected from unbounded one-step losses
ALT'09: Proceedings of the 20th international conference on Algorithmic learning theory

In this paper the sequential prediction problem with expert advice is considered for the case when the losses of experts suffered at each step can be unbounded. We present some modification of Kalai and Vempala algorithm of following the perturbed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research

The Journal of Machine Learning Research Volume 6, Issue

12/1/2005

2169 pages

ISSN:1532-4435

EISSN:1533-7928

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Published: 01 December 2005

Published in JMLR Volume 6

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
49
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang GHu ZMuthukumar VAbernethy JKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Adaptive oracle-efficient online learningProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601970(23398-23411)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601970
Ahmed Ouameur MAnh LMassicotte DJeon Gde Figueiredo F(2022)Adversarial bandit approach for RIS-aided OFDM communicationEURASIP Journal on Wireless Communications and Networking10.1186/s13638-022-02184-62022:1Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1186/s13638-022-02184-6
Mhaisen NSinha APaschos GIosifidis G(2022)Optimistic No-regret Algorithms for Discrete CachingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35706086:3(1-28)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3570608
Bernasconi de Luca MVittori ETrovò FRestelli M(2021)Conservative Online Convex OptimizationMachine Learning and Knowledge Discovery in Databases. Research Track10.1007/978-3-030-86486-6_2(19-34)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-86486-6_2
Dudík MHaghtalab NLuo HSchapire RSyrgkanis VVaughan J(2020)Oracle-efficient Online Learning and Auction DesignJournal of the ACM10.1145/340220367:5(1-57)Online publication date: 29-Sep-2020
https://dl.acm.org/doi/10.1145/3402203
Huang JWu FPrecup DCai Y(2018)Learning safe policies with expert guidanceProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327546.3327585(9123-9132)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327546.3327585
Muñoz Medina AVassilvitskii SYin DCuzzocrea AAllan JPaton NSrivastava DAgrawal RBroder AZaki MCandan SLabrinidis ASchuster AWang H(2018)Online Learning for Non-Stationary A/B TestsProceedings of the 27th ACM International Conference on Information and Knowledge Management10.1145/3269206.3271718(317-326)Online publication date: 17-Oct-2018
https://dl.acm.org/doi/10.1145/3269206.3271718
Hu ZZhu MLiu POkhravi HOu X(2017)Online Algorithms for Adaptive Cyber Defense on Bayesian Attack GraphsProceedings of the 2017 Workshop on Moving Target Defense10.1145/3140549.3140556(99-109)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.1145/3140549.3140556
Lattimore T(2015)The pareto regret frontier for banditsProceedings of the 29th International Conference on Neural Information Processing Systems - Volume 110.5555/2969239.2969263(208-216)Online publication date: 7-Dec-2015
https://dl.acm.org/doi/10.5555/2969239.2969263
Koolen W(2013)The Pareto regret frontierProceedings of the 27th International Conference on Neural Information Processing Systems - Volume 110.5555/2999611.2999708(863-871)Online publication date: 5-Dec-2013
https://dl.acm.org/doi/10.5555/2999611.2999708
Show More Cited By

Abstract

Cited By

Recommendations

Adaptive online learning

On following the perturbed leader in the bandit setting

The follow perturbed leader algorithm protected from unbounded one-step losses

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations