NeurIPS 2022accept7 citations
Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality
Teodor Vanislavov Marinov, Mehryar Mohri, Julian Zimmert
Abstract
We revisit the problem of stochastic online learning with feedback graphs, with the goal of devising algorithms that are optimal, up to constants, both asymptotically and in finite time. We show that, surprisingly, the notion of optimal finite-time regret is not a uniquely defined property in this context and that, in general, it is decoupled from the asymptotic rate. We discuss alternative choices and propose a notion of finite-time optimality that we argue is \emph{meaningful}. For that notion, we give an algorithm that admits quasi-optimal regret both in finite-time and asymptotically.
BanditsOnline learning
BibTeX
@inproceedings{
marinov2022stochastic,
title={Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality},
author={Teodor Vanislavov Marinov and Mehryar Mohri and Julian Zimmert},
booktitle={Advances in Neural Information Processing Systems},
editor={Alice H. Oh and Alekh Agarwal and Danielle Belgrave and Kyunghyun Cho},
year={2022},
url={https://openreview.net/forum?id=VgX6ceDerh2}
}