Timezone: »

Online Learning with Adversarial Delays
Kent Quanrud · Daniel Khashabi

Tue Dec 08 04:00 PM -- 08:59 PM (PST) @ 210 C #99 #None
We study the performance of standard online learning algorithms when the feedback is delayed by an adversary. We show that \texttt{online-gradient-descent} and \texttt{follow-the-perturbed-leader} achieve regret $O(\sqrt{D})$ in the delayed setting, where $D$ is the sum of delays of each round's feedback. This bound collapses to an optimal $O(\sqrt{T})$ bound in the usual setting of no delays (where $D = T$). Our main contribution is to show that standard algorithms for online learning already have simple regret bounds in the most general setting of delayed feedback, making adjustments to the analysis and not to the algorithms themselves. Our results help affirm and clarify the success of recent algorithms in optimization and machine learning that operate in a delayed feedback model.

Author Information

Kent Quanrud (UIUC)
Daniel Khashabi (UIUC)