Prediction with Corrupted Expert Advice
Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, Roi Livni
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.
BibTeX
@inproceedings{NEURIPS2020_a5122944,
author = {Amir, Idan and Attias, Idan and Koren, Tomer and Mansour, Yishay and Livni, Roi},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {14315--14325},
publisher = {Curran Associates, Inc.},
title = {Prediction with Corrupted Expert Advice},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/a512294422de868f8474d22344636f16-Paper.pdf},
volume = {33},
year = {2020}
}