A Second-order Bound with Excess Losses
arXiv:1402.2044
Abstract
We study online aggregation of the predictions of experts, and first show new second-order regret bounds in the standard setting, which are obtained via a version of the Prod algorithm (and also a version of the polynomially weighted average algorithm) with multiple learning rates. These bounds are in terms of excess losses, the differences between the instantaneous losses suffered by the algorithm and the ones of a given expert. We then demonstrate the interest of these bounds in the context of experts that report their confidences as a number in the interval [0,1] using a generic reduction to the standard setting. We conclude by two other applications in the standard setting, which improve the known bounds in case of small excess losses and show a bounded regret against i.i.d. sequences of losses.
Cited by in corpus (14)
- Refined Lower Bounds for Adversarial Bandits
- Model selection for contextual bandits
- Tracking the Best Expert in Non-stationary Stochastic Environments
- CRPS Learning
- MetaGrad: Multiple Learning Rates in Online Learning
- Dynamic Regret of Convex and Smooth Functions
- Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
- MetaGrad: Adaptation using Multiple Learning Rates in Online Learning
- Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions
- Prediction with Unpredictable Feature Evolution
- Optimal learning with Bernstein Online Aggregation
- Adaptive and Efficient Algorithms for Tracking the Best Expert
- Universal Online Convex Optimization Meets Second-order Bounds
- Low-Regret Active learning