Timezone: »

 
Spotlight
Prediction with Corrupted Expert Advice
Idan Amir · Idan Attias · Tomer Koren · Yishay Mansour · Roi Livni

Wed Dec 09 07:30 AM -- 07:40 AM (PST) @ Orals & Spotlights: Social/Adversarial Learning
in Orals & Spotlights Track 20: Social/Adversarial Learning »

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.

Author Information

Idan Amir (Tel-Aviv University)
Idan Attias (Ben Gurion University)
Tomer Koren (Tel Aviv University & Google)
Yishay Mansour (Tel Aviv University / Google)
Roi Livni (Tel Aviv University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors