Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors consider the problem of online convex optimisation where at each time $t\leq T$ the player chooses an action $x_t \in \mathcal{K}$ and receives a payment $f_t(x_t)$, and where the gradient $\nabla f_t(x_t)$ is only revealed after an arbitrary delay $d_t$ smaller than some constant $d$. The aim of the player is to minimize its regret.

The authors propose a modified version of the online Frank-Wolfe algorithm that can adapt to the delays. Under classical assumptions on the boundedness of the gradient and on the diameter of $\mathcal{K}$, the authors bound the regret of their algorithm in the convex case and in the strongly convex case. They show that in the convex case, the regret is $O(T^{3/4} + dT^{1/4})$, while in the strongly convex case, it is $O(T^{2/3} + d \log(T))$. These regret rates improve over previous rates for online convex optimisation with delays. Moreover, when $d$ is small enough, these rates match the rates of the online Frank-Wolf algorithm without delay.
strengths_and_weaknesses: Originality : The authors modify the Frank-Wolfe algorithm to take into account delays in the observation of the gradients. The provide a theoretical analysis of the regret of this algorithm.

Quality : This paper is technically solid. The lack of simulations comparing their algorithms to benchmark algorithms is somewhat disappointing.

Clarity : This paper is clearly written. The assumptions are justified. The motivations and the literature review well addressed.

Significance : This paper presents a clear contribution by adapting a classical algorithm to a well motivated, practical problem.
questions: Is the OWF algorithm particularly suited for delayed feedback because of the form of $F_t$ (that takes into account all previously observed gradients)? Or do you think you could achieve the same rates with other classical algorithm for online convex optimisation? Could you maybe provide a little more intuition on why delay do not lead to an increase in the reget?
limitations: The authors have properly addressed the limitation of the theoretical aspects of their work, however one could have expected their paper to also include a comparison of the empirical performances of their algorithm with benchmark methods.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies online convex optimization with delayed gradients. The authors study the Online Frank-Wolfe (OFW) algorithm, which simply runs the FW update for all the gradients as soon as they arrive. The authors prove regret bounds in the convex and strongly convex settings, which still match the original regret bound for FW, as long as the delay does not exceed certain threshold.
strengths_and_weaknesses: Interesting problem with simple algorithm and nice results. The paper is well-written and the analysis seems clear. The resulting regret bounds are robust to delay up to some threshold, which is surprising and nice.

questions: Is it clear whether OFW is the optimal algorithm for delayed feedback?
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the problem of online convex optimization where the gradient of the function at the query point is revealed after an arbitrary delay. The authors proposed a delayed version of the online Frank-Wolfe algorithm, for convex (Algorithm 1, page 5) and strongly convex (Algorithm 2, page 6). In the case when the maximum of the delays is sufficiently small, the proposed method can recover the regret bounds for convex and strongly convex loss functions. 
strengths_and_weaknesses: Strengths:

The problem of delayed feedback is well motivated. The paper is very well written and easy to understand. The main contribution of the paper is in the case when the maximum of the delays is sufficiently small, the proposed method can recover the regret bounds for convex and strongly convex losses (outlined in lines 64 - 69)4. The authors provide a complete literature review. They clearly discussed their contributions and improvement to the prior work.

Weaknesses: 
1. It would be nice if the authors provide a numerical comparison with Joulani et al. [2013].

questions: 1. Can one use similar ideas for providing a delayed version of online mirror descent algorithm?
limitations: The authors addressed the limitations of their work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper mainly proposed a delayed variant of OFW called Online Frank-Wolfe with Arbitrary Delays, which allows gradients to be delayed by arbitrary rounds. The algorithm can avoid the limitation of the original OFW, as well as solving the problem of Online convex optimization (OCO) that needs to compute a projection onto the decision set to ensure the feasibility of each decision. By performing an update similar to OFW after receiving any delayed gradient, and playing the latest decision for each round, this algorithm could enjoy the same regret bound like that of the original OFW. 
strengths_and_weaknesses: Strength:

（1）This paper extends the classical OFW to the delayed setting, which requires the fewer storage and computational resources compared with the non-delayed setting.
（2）Unlike other algorithms, i.e., Weinberger and Ordentlich proposed a technique that can convert any traditional OCO algorithm for the non-delayed setting into this delayed setting, the Online Frank-Wolfe with Arbitrary Delays provided in this paper can achieve better regret bound for convex losses and strongly convex losses.
（3）The delayed variant of OFW enjoys the same regret bound like that of the original OFW, which has a certain positive impact on the convex optimization field, and has higher practical value than the original OFW.
（4）This paper only theoretically analyzes the effect of the proposed algorithm, and does not carry out more specific experiments to verify the actual effect.

Weaknesses:

（1）This paper only theoretically analyzes the effect of the proposed algorithm, and does not carry out more specific experiments to verify the actual effect. It is necessary to do some experiments.
（2）This paper only extends the classical OFW to the delayed setting, there still are more delayed variants for other projection-free online algorithms. It is meaningful to do more investigations.

questions:  This paper only theoretically analyzes the effect of the proposed algorithm, and does not carry out more specific experiments to qualitatively and quantitatively verify the actual effect.

in addition, Elad Hazan et al.  in the manuscript titled"  Faster Projection-free Online Learning" give an efficient projection-free algorithm that guarantees O(T2/3) regret for general online convex optimization with smooth cost functions and one linear optimization computation per iteration.
Please discuss the relationship with these previous research results, and how much has it improved.



limitations: I don't  know the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: Following a discussion with the authors, all reviewers were in favor of accepting except for Reviewer 6sxN whose main concern is around the experimental evaluation.  From my own look into the paper, I tend to agree with the reviewers: the paper is well-written, it solves a natural (even if a bit niche) problem with a simple algorithm; and the theoretical analysis is well-executed and even somewhat surprising: the effect of the delay turns out to be additive, rather than multiplicative as is the case in other online optimization settings.  The concerns around experimental evaluations are valid, but I do not feel that strong experiments are crucial in such a theory-focused paper.

All considered, I gladly recommend to accept the paper.
confidence: Certain
Decision: Accept