Prediction with Corrupted Expert Advice
arXiv:2002.10286
Abstract
We revisit the fundamental problem of prediction with expert advice, in a setting where the environment is benign and generates losses stochastically, but the feedback observed by the learner is subject to a moderate adversarial corruption. We prove that a variant of the classical Multiplicative Weights algorithm with decreasing step sizes achieves constant regret in this setting and performs optimally in a wide range of environments, regardless of the magnitude of the injected corruption. Our results reveal a surprising disparity between the often comparable Follow the Regularized Leader (FTRL) and Online Mirror Descent (OMD) frameworks: we show that for experts in the corrupted stochastic regime, the regret performance of OMD is in fact strictly inferior to that of FTRL.
arXiv commentNeurIPS 2020 Camera Ready
References in corpus (9)
- Online Learning with Predictable Sequences
- Online Learning: A Modern Introduction Using Convex Optimization
- More Adaptive Algorithms for Adversarial Bandits
- Adversarial Attacks on Stochastic Bandits
- Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
- On the optimality of the Hedge algorithm in the stochastic regime
- Adaptive Online Learning
- ZigZag: A new approach to adaptive online learning
- Fast rates in statistical and online learning