A Regret-Variance Trade-Off in Online Learning
We consider prediction with expert advice for strongly convex and bounded
losses, and investigate trade-offs between regret and "variance" (i.e., squared
difference of learner's predictions and best expert predictions). With $K$
experts, the Exponentially Weighted Average (EWA) algorithm is known to achieve
$O(\log K)$ regret. We prove that a variant of EWA either achieves a negative
regret (i.e., the algorithm outperforms the best expert), or guarantees a
$O(\log K)$ bound on both variance and regret. Building on this result, we show
several examples of how variance of predictions can be exploited in learning.
In the online to batch analysis, we show that a large empirical variance allows
to stop the online to batch conversion early and outperform the risk of the
best predictor in the class. We also recover the optimal rate of model
selection aggregation when we do not consider early stopping. In online
prediction with corrupted losses, we show that the effect of corruption on the
regret can be compensated by a large variance. In online selective sampling, we
design an algorithm that samples less when the variance is large, while
guaranteeing the optimal regret bound in expectation. In online learning with
abstention, we use a similar term as the variance to derive the first
high-probability $O(\log K)$ regret bound in this setting. Finally, we extend
our results to the setting of online linear regression.