A parameter-free hedging algorithm
arXiv:0903.2851
Abstract
We study the problem of decision-theoretic online learning (DTOL). Motivated by practical applications, we focus on DTOL when the number of actions is very large. Previous algorithms for learning in this framework have a tunable learning rate parameter, and a barrier to using online-learning in practical applications is that it is not understood how to set this parameter optimally, particularly when the number of actions is large. In this paper, we offer a clean solution by proposing a novel and completely parameter-free algorithm for DTOL. We introduce a new notion of regret, which is more natural for applications with a large number of actions. We show that our algorithm achieves good performance with respect to this new notion of regret; in addition, it also achieves performance close to that of the best bounds achieved by previous algorithms with optimally-tuned parameters, according to previous notions of regret.
Updated Version
References in corpus (2)
Cited by in corpus (18)
- Online Learning: A Modern Introduction Using Convex Optimization
- Need for Speed: A Benchmark for Higher Frame Rate Object Tracking
- Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
- Deep Counterfactual Regret Minimization
- Towards Minimax Online Learning with Unknown Time Horizon
- Adaptive Online Learning
- Prediction strategies without loss
- Parameter-free online learning via model selection
- Achieving All with No Parameters: Adaptive NormalHedge
- Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
- Relax and Localize: From Value to Algorithms
- Prediction with Expert Advice under Discounted Loss
- A method for Hedging in continuous time
- Online Learning with Many Experts
- Kernalised Multi-resolution Convnet for Visual Tracking
- Online Influence Maximization with Local Observations
- Search in Imperfect Information Games
- An Online Learning-based Framework for Tracking