Online Learning under Delayed Feedback

By Pooria Joulani, András György, Csaba Szepesvari. International Conference on Machine Learning, 2013

332 citations recorded by the source corpus.

Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze the effect of delay on the regret of online learning algorithms. Somewhat surprisingly, it turns out that delay increases the regret in a multiplicative way in adversarial problems, and in an additive way in stochastic problems. We give meta-algorithms that transform, in a black-box fashion, algorithms developed for the non-delayed case into ones that can handle the presence of delays in the feedback loop. Modifications of the well-known UCB algorithm are also developed for the bandit problem with delayed feedback, with the advantage over the meta-algorithms that they can be implemented with lower complexity.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/2e0e05796251a38ee811fd4e0719f92027953a81

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Asymptotic Convergence in Online Learning with Unbounded Delays (2016, background): “Dudik et al. [1], Joulani, György, and Szepesvári [2], and others have studied online learning with delayed feedback, but they assume that delays are bounded, whereas in our setting the delays necessarily grow ever-larger.”
Parallelised Bayesian Optimisation via Thompson Sampling (2018, background): “Besides BO, there has been a line of work on online learning with delayed feedback (as we have in the parallel setting) [22, 33].”
Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, background): “Our ﬁnal result for the uniform and half-normal random variables follows as a consequence of Lemma 20.”
Bandit Algorithms (2020, methodology): “A comprehensive examination of various generalizations is given by Joulani et al. [2017]. For follow the regularized leader convexity of F suffices, as you will show using directional derivatives in Exercise 28.”
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates (2018, background): “A similar bound on average regret has been shown in an adversarial online learning setting, for general convex functions, and this bound is known to be optimal [10].”