Online Learning with Optimism and Delay
arXiv:2106.06885
Abstract
Inspired by the demands of real-time climate and weather forecasting, we develop optimistic online learning algorithms that require no parameter tuning and have optimal regret guarantees under delayed feedback. Our algorithms -- DORM, DORM+, and AdaHedgeD -- arise from a novel reduction of delayed online learning to optimistic online learning that reveals how optimistic hints can mitigate the regret penalty caused by delay. We pair this delay-as-optimism perspective with a new analysis of optimistic learning that exposes its robustness to hinting errors and a new meta-algorithm for learning effective hinting strategies in the presence of delay. We conclude by benchmarking our algorithms on four subseasonal climate forecasting tasks, demonstrating low regret relative to state-of-the-art forecasting models.
arXiv commentICML 2021. 9 pages of main paper and 26 pages of appendix text
References in corpus (9)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Online Learning with Predictable Sequences
- Optimization, Learning, and Games with Predictable Sequences
- Fast Convergence of Regularized Learning in Games
- Online Learning: A Modern Introduction Using Convex Optimization
- Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
- Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice
- Improved Optimistic Mirror Descent for Sparsity and Curvature