Data di Pubblicazione:
2022
Citazione:
A Regret-Variance Trade-Off in Online Learning / D. van der Hoeven, N. Zhivotovskiy, N. Cesa Bianchi (ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS). - In: NeurIPS / [a cura di] S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh. - [s.l] : Curran Associates, 2022. - ISBN 9781713871088. - pp. 35188-35200 (( Intervento presentato al 36. convegno Conference on Neural Information Processing Systems : Monday November 28th through Friday December 9th tenutosi a New Orleans nel 2022.
Abstract:
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(logK) 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(logK) 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(logK) regret bound in this setting. Finally, we extend our results to the setting
of online linear regression.
Tipologia IRIS:
03 - Contributo in volume
Elenco autori:
D. van der Hoeven, N. Zhivotovskiy, N. Cesa Bianchi
Link alla scheda completa:
Titolo del libro:
NeurIPS