Online Learning with Adversarial Delays
We study the performance of standard online learning algorithms when the feedback is delayed by an adversary. We show that online-gradient-descent [1] and follow-the-perturbed-leader [2] achieve regret O( √ D) in the delayed setting, where D is the sum of delays of each round's feedback. This bound collapses to an optimal O( √ 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.
The authors slightly modify two well known online algorithms, OGD and FTPL, to address the problem of adversarial delays. In this problem, it is assumed that adversary might not reveal the loss functions at end of every round. The modifications to the algorithms are most natural and I appreciate the simplicity. Since the crux of the paper lies in the analysis of the modified algorithms, I need to be sure about the correctness of the proofs before accepting the paper. While it is of course possible that I have misunderstood a couple of things, I want to be convinced that it is my mistake rather than mistake in the proofs before agreeing that the paper can be accepted to a conference of such prestige.Originality- Unless someone has already published the ideas before, I cannot question the originality of the work. Significance- The authors give a few examples in the beginning as to why adversarial feedback might be delayed. I have not encountered this problem before; so I am assuming that this problem is of interest to the online learning community. Clarity- The introduction and the two (modified) algorithms are certainly clear and simple to understand. However, I have a few issues regarding the presentation of the proofs. Normally, it would not matter, but considering the paper is all about the analysis, and the proofs are in the main paper, I think the presentation is important.1. Line 033- Why is the game fundamentally unfair? Unfair to whom? Learner or adversary? If the adversary is adaptive, I would say that the adversary is very powerful. Moreover, considering the regret is w.r.t to the best single decision learner could have taken in hindsight, I do not understand the unfairness issue. 2. It is confusing how the proof is going from line 151 to 156. While the inequality in line 156 is correct ( I checked it- simply write ||x_{t+1}- y||^2= ||x_t - \sum_{s \in F_t} \nabla f_s|x_s - y||^2 and open up the expression on the right followed by simple algebra), I find what is written in the paper confusing. First, the authors fix s as max F_t, but then the expression is unrolled over $s$. Is s fixed or variable? 3. Please check the expression for x_{t,s} when it is introduced. I think in the gradient term, it should be \nabla f_r|x_r, not \nabla f_s|x_r.4. I found it very difficult to understand the proof of Lemma 3.2. Can it be presented in a better way? It is simply the end part of Theorem 1.1 and Lemma 3.2 in Kalai-Vempala FTPL paper. In their paper, it is so simple to understand (the argument of what fraction of two hypercubes overlap followed by the fact that in the fraction they dont overlap, the maximum difference in decision*cost factor is bounded by L_1 norm of decision and L_{infty} norm of cost, which is precisely what is being done in Lemma 3.2 of this paper). I dont see the need to recast Kalai-Vempala's argument in a more complicated way. 5. There are number of notational mistakes in Lemma 3.3. Please check.Quality- The main questions I have are in the proof of Theorem 1. 1. Why does the inequality in Line 192 hold? Specifically, why is x_{t,s} closer to x'_{s+1} in Euclidean space than to x_{s+1}? I simply could not understand how this came about? As far as as I can see, x_{t,s} is an arbitrarily defined point. Is x_{t,s} inside or outside the convex set K? Either way, why does the inequality hold? 2. I simply could not wrap my head around the argument between Line 200 to line 219. I tried to reason independently but could not. While of course it does not mean the proof is wrong, I would like to talk to other reviewers before being convinced about it.