Adaptive Online Prediction by Following the Perturbed Leader
arXiv:cs/0504078
Abstract
When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of sqrt(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 Kalai & 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.
25 pages
References in corpus (2)
Cited by in corpus (18)
- A Philosophical Treatise of Universal Induction
- A parameter-free hedging algorithm
- The Price of Differential Privacy For Online Learning
- Efficient Algorithms for Adversarial Contextual Learning
- Asymptotics of Discrete MDL for Online Prediction
- Conservative Bandits
- Second-order Quantile Methods for Experts and Combinatorial Games
- Universal Learning of Repeated Matrix Games
- Defensive forecasting for optimal prediction with expert advice
- The Pareto Regret Frontier for Bandits
- Sparse Adaptive Dirichlet-Multinomial-like Processes
- Sequential Learning of Principal Curves: Summarizing Data Streams on the Fly
- Online Learning in Case of Unbounded Losses Using the Follow Perturbed Leader Algorithm
- FPL Analysis for Adaptive Bandits
- Asynchronous Optimization over Weakly Coupled Renewal Systems
- Master Algorithms for Active Experts Problems based on Increasing Loss Values
- A New Understanding of Prediction Markets Via No-Regret Learning
- Opportunistic Scheduling over Renewal Systems: An Empirical Method