Online Frank-Wolfe with Arbitrary Delays
Authors: Yuanyu Wan
Wei-Wei Tu
Lijun Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online Convex Optimization
Online Frank-Wolfe
Arbitrary Delays

Abstract: The online Frank-Wolfe (OFW) method has gained much popularity for online convex optimization due to its projection-free property. Previous studies show that OFW can attain an $O(T^{3/4})$ regret bound for convex losses and an $O(T^{2/3})$ regret bound for strongly convex losses. However, they assume that each gradient queried by OFW is revealed immediately, which may not hold in practice and limits the application of OFW. To address this limitation, we propose a delayed variant of OFW, which allows gradients to be delayed by arbitrary rounds. The main idea is to perform an update similar to OFW after receiving any delayed gradient, and play the latest decision for each round. Despite its simplicity, we prove that our delayed variant of OFW is able to achieve an $O(T^{3/4}+dT^{1/4})$ regret bound for convex losses and an $O(T^{2/3}+d\log T)$ regret bound for strongly convex losses, where $d$ is the maximum delay. This is quite surprising since under a relatively large amount of delay (e.g., $d=O(\sqrt{T})$ for convex losses and $d=O(T^{2/3}/\log T)$ for strongly convex losses), the delayed variant of OFW enjoys the same regret bound as that of the original OFW.

Online Trank-Wolfs with Arbitrary Delays
Yuanyu Wan Wei-Wei Tu Lijun Zhang
Schooo of Software Technology, Zhejiang University, Ningbo, China "Zhejiang Uniiersity-Chiin Southern Power Grid Joint Research Centre on AI, Hangzhou, China
*4Paradigm Inc., Beijing, China
National Key Laboratory for Novel Software Technology. Nanjing University, Nanjing, China wanyyōzju. edu. cn, tuweixeii@4aardiie com, zhanglj jalagle www.njuuuucc edu.
Abstract
The online Frank- Wolfe (OFW) method has gained much popularity for online convex optimization due to its projection-free property. Previous studies show that OFW can attain an O(T3/4) regret bound for convex losses and an 2(72/3) regret bound for strongly convex losses. However, they assume that each gradient queried by OFW is revealed immediately, which may not hold in practice and limits the application of OFW. To address this limitation, we propose delayed variant of OFW, which allows gradients to be delayed by arbitrary rounds. The main idea is to perform an update similar to OFW after receiving any delayed gradient, and play the latest decision for each round. Despite its simplicity, we prove that our delayed variant of OFW is able to achieve O(73/4 + dT'144 regret bound for convex losses and an O + +d dog T) regret bound for strongly convex losses, where d is the maximum delay. This quite surprising since under relatively large amount of delay (e.g., d = O(TT) for convex losses and = O(T2/3 log T') for strongly convex losses), the delayed variant of OFW enjoys the same regret bound as that the original OFW.
Introduction
Online convex optimization (OCO) has become leading paradigm for online learning due its ca- pability to model various problems from diverse domains such as online routing, online collaborative filtering, and online advertisement (Hazan, 2016]. In general, it is formulated as structured repeated game between a player and an adversary. In each round t. the player first chooses decision x, from convex decision set X. C R", where is the dimensionality. Then, the adversary selects a convex function fx(x) + R, and the player suffers a loss (x.). The player aims to choose decisions such that the regret R(T) Σ fx(x)) minxek: Σ fi(x) is sublinear in the number of total rounds T. Online gradient descent (OGD) is a standard method for OCO, which enjoys an O(VT) regret bound for convex losses [Zinkevich, 2003] and an Ollog 7') regret bound for strongly convex losses [Hazan et al., 2007]. However. needs compute a projection onto the decision to ensure the feasibility of each decision, which is computationally expensive for complex decision sets (Hazan and Kale, 2012].
To tackle this computational issue, Hazan and Kale [2012) propose the online Frank-Wolft (OFW) method, which has become one of the most commonly used algorithms for OCO over complex decision sets. The main advantage of OFW is its projection-free free property: instead of performing the projection operation, utilizes linear optimization step to select feasible decision, which could be much more efficient. For example, in the problem of online collaborative filtering, the decision set
"Lijun Zhang is the corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

consists of matrices with a bounded trace norm, and the linear optimization step is at least an order of magnitude faster than the projection operation [Hazan and Kale, 2012]. Moreover, it has been shown that OFW achieves an O(T%/4) regret bound for convex losses [Hazan and Kale, 2012, Hazan, 2016] and an O(T2/a) regret bound for strongly convex losses [Wan and Zhang, 2021, Garber and Kretzu, 2021J, which are the best known regret bounds of projection-free methods without further assumptions.
However, OFW requires that the gradient V f((e)) is revealed immediately after making the decision x,. which is not necessarily satisfied in reality. For example, in the previously mentioned online collaborative filtering [Hazan and Kale, 2012], the decision is a prediction of a user-item rating matrix, and the corresponding gradient depends on the true rating of user on item, which may not be decided by the user immediately. Therefore, it is natural to consider a more practical setting, where the gradient V (xx) arrives the end of round + de 1, and de 2 denotes an arbitrary delay, To handle this setting, one potential way is to combine OFW with an existing black-box technique for converting any traditional OCO algorithm into this delayed setting [Joulani et al., 2013]. To be precise, this black-box technique is to pool independent instances of OFW, each of which acts as a learner in the non-delayed setting over a subsequence of rounds. In each round, single instance will be taken out from the pool, which makes decision and then waits for its feedback before rejoining the pool. If the pool is empty. a new instance of OFW will be added it. Moreover, according to Joulani et al. 3), their black-box technique is able to attain a regret bound of dR(T/d) by combining with traditional OCO algorithm with R(T) regret, where d the maximum delay. As a result, combining it with OFW will attain an O(d /dT3//33/4)) regret bound for convex losses and an (d21/372/3 regret bound for strongly convex losses, which magnify the regret bounds of OFW in the non-delayed setting by coefficient depending the delay. Thus, it is natural to ask whether the effect of delay can be further reduced.
In this paper, we give an affirmative answer by developing a simple method called delayed OFW, which is robust to a relatively large amount of delay for both convex and strongly convex losses. Different from the black-box technique that needs to maintain multiple instances of OFW [Joulani al., 2013], our delayed OFW is a natural extension of OFW in the delayed setting, which updates the decision similar to OFW after receiving any delayed gradient, and plays the latest decision for each round. Our theoretical contributions are summarized as follows.
First, we prove that our delayed OFW attains an O(T + d//1/4) regret bound for convex losses, where d is the maximum delay, which matches the O(73/4) regret bound in the non-delayed setting as long as does not exceed O(VT).
Second, we prove that our delayed OFW attains an O + d log T) regret bound for strongly convex losses, which matches the ((T2/33) regret bound in the non-delayed setting as long as does not exceed (TT2/3/ log T).
Therefore, our regret bounds are strictly better than those achieved by combining the black-box technique [Joulani et al., 2013] with OFW, when the term involving d in them is not dominant. Furthermore, simulation experiments are conducted to verify the performance of our delayed OFW.
2
Related work
In this section, we briefly review related work on projection-free algorithms for OCO, and OCO under delayed feedback.
2.1 Projection-free algorithms for OCO
The OFW method [Hazan and Kale, 2012, Hazan, 2016] the first projection-free algorithm for OCO, which is an online extension of the classical Frank-Wolfe method [Frank and Wolfe, 1956. Jaggi, 2013]. For convex losses, OFW first chooses an arbitrary x1 K. and then iteratively updates its decision by the following linear optimization step
Vt E (Vg x), X xx + oo(1 -x1)
(1)
xE

---

where (x) is a surrogate loss function defined as
Fx = (iVA((s))))) + +|x x1
and 17, of are two parameters. By setting parameters appropriately, it can attain an O(T3/4) regret bound for convex losses.
If losses are convex and smooth, Hazan and Minasyan [2020] propose randomized projection-free method, which is based on a classical OCO method called follow the perturbed leader [Kalai and Vempala, 2005], and achieve a regret bound of ( Recently, Wan and Zhang [2021] prove that OFW can achieve an O(T2/3) regret bound for strongly convex losses. Specifically, to utilize the strong convexity of losses, they redefine Fx(x) in (2)
Fx Σ (fi((x),)) + 3 211xx x1113
(3)
where 3 is the modulus of the strong convexity. The same regret bound is concurrently established by Garber and Kretzu [2021] in a similar way.
Moreover, projection- OCO algorithms, which are able achieve an O(VT) regret bound for convex losses and an (log T) regret bound for strongly convex losses, have been proposed for polyhedral sets [Garber and Hazan, 2016]. smooth sets [Levy and Krause, 2019], and special sets that are accessible through membership oracle [Mhammedi, 2022] or a separation oracle [Garber and Kretzu, 2022], respectively. Although regret bounds of these algorithms are better than those of OFW, they can only be efficiently implemented in some special cases, and thus are still not able to replace OFW. addition to these algorithms, Wan and Zhang [2021] show that by setting a with a line search technique, OFW can adaptively utilize the strong convexity of decision sets to attain an O(T*/3) regret bound for convex losses and O(vT) regret bound for strongly convex losses. Besides the standard setting, projection-fre free algorithms for other OCO scenarios such as the distributed setting [Zhang et al., 2017, Wan et al., 2020, 2022b] and the bandit setting [Chen et al., 2019, Garber and Kretzu, 2020, 2021] have also been proposed.
However, despite this great flourish of research on projection-free OCO algorithms, the practical problem of delayed feedback has not been considered.
2.2 OCO under delayed feedback
The starting point for studies on OCO under delayed feedback is the seminal work of Weinberger and Ordentlich [2002], which focuses on special case with fixed delay d', i.e., the feedback for each decision x, is received at the end of round L + d' - 1. They propose a technique that can convert any traditional OCO algorithm for the non-delayed setting into this delayed setting. Specifically, their technique is to run d' instances of traditional OCO algorithm, where each instance is used every d' rounds, which is feasible because the feedback for any decision x, must be available for selecting the decision X++d'- If the traditional OCO algorithm enjoys regret bound of R(T) in the non-delayed setting, they prove that this technique achieves regret bound of d' R(T/d"). As result, by combining with OGD, the regret bound of this technique is (VdTT) for convex losses and (dd TT) for strongly convex losses. However, it needs to run d' instances of OGD, which requires more storage and computational resources than the original OGD. To address this problem, Langford et al. [2009] study the same delayed setting. and show that simply performing each gradient descent step in the original OGD with delayed gradient can also achieve the O(V regret bound for convex losses and the (d' log T)) regret bound for strongly convex losses.
Furthermore, Joulani et al. [2013] extend the technique in Weinberger and Ordentlich [2002] to handle a more general setting, where each feedback is delayed by arbitrary rounds. For this setting, their technique is able to attain a regret bound of ddR(T /Tdd) by combining with traditional OCO algorithm with R(T) regret, where d is the maximum delay. Note that although this technique can also convert OFW to the delayed setting, it can only attain an ((d//48//4) regret bound for convex losses and an (32/3322/3) regret bound for strongly convex losses, which cannot match regret bounds of OFW in the non-delayed setting as long d is larger than ?(1). Additionally, similar to the technique
3

---

in Weinberger and Ordentlich [2002], it also needs to run multiple instances of traditional OCO algorithm, which could be prohibitively resource-intensive Many studies [Quanrud and Khashabi, 2015, Joulani et al., 2016, Li et al., 2019, Flaspohler et al., 2021, Wan et al., 2022a] have proposed delayed OCO algorithms, which only require the same storage and computational resources as in the non-delayed setting, but do not consider projection-free algorithms.
3
Main results
In this section, we first introduce necessary preliminaries including the problem setting, definitions. and assumptions. Then, we present our delayed OFW and the corresponding theoretical guarantees for convex and strongly convex losses, respectively.
3.1 Preliminaries
consider the problem OCO with arbitrary delays [Joulani et al., 2013, Quanrud and Khashabi, 2015]. Similar to the standard OCO, in each round = ....... T, the player first chooses a decision X₁ from the decision set K. and then the adversary selects a convex function f((x). However, different from the standard OCO, the gradient g: V fxx,) ) is revealed at the end of round + d, 1, where d 2 denotes an arbitrary delay. As a result, the player actually receives gradients {g&| E F.) t). Then, recall the standard definition for
at the end of round i, where Fr {Aekk dg- strongly convex functions [Boyd and Vandenberghe, 2004].
Definition 1 A function fxx KC + R is called B-strongly convex over K. for all x,y E K, it holds that f(y) 2 f(x) + (V f(x) x) + x1
Finally, we introduce two assumptions, which are commonly used in studies about OCO [Shalev- Shwartz, 2011, 1, Hazan, 2016].
Assumption The gradients of all loss functions are bounded by G, i.e. it holds that [\V z G for any x E XC and t E [T).
Assumption 2 The diameter of the decision set 1C is bounded by D, i.e., it holds that ||x y112 S D for any x, E K.
3.2 Delayed OFW for convex losses
As presented in (1) and (2), the original OFW for convex losses requires the gradient g: before making the decision X.+1. However, in the problem of OCO with arbitrary delays, this requirement is not necessarily satisfied, because the player actually receives gradients {gx A E Fi) at each round t, which may not contain ge. To address this limitation, we propose a natural generalization of OFW to this delayed problem, which is described as follows.
The main idea is to update the decision similar to OFW for each received gradient, and play the latest decision for each round. In this way, there exist some intermediate decisions that are not really played. To facilitate presentations, intermediate decision. Moreover, we denote the sum of T received gradients by gr- Initially, we choose an arbitrary vector y1 K. and set 1, go 0. At each round / 1,..., T, we play the latest decision x, = y- and query the gradient that are queried in set of rounds Fr, and perform the following steps for each received gradient.
introduce additional notation y, to denote the 7-th
V (x.). Then, we receive delayed gradients
Specifically, for any Fe, inspired by (2) of the original OFW, we first compute g, = gr-1 + gk and define
F+ (g.. + lly - 11.
Then, similar to (1) of the original OFW, we perform the following update
Vr E argmin (VF, Y++1 Y- + o, yr)
yEK
where is a parameter. Following Wan and Zhang [2021], it is set by line search rule
argminn((vv, Y7), VF, (y+)) + + y oE(0.1]
(4)

---

Algorithm Delayed OFW for Convex Losses
1: Input:
2: Initialization: choose an arbitrary vector y1 E I0 and set r 1, = 0
3: for t = 1, .,, do
4: Play x, = Yr and query g: = (x,,
5: Receive
of delayed gradients {ge/h Fi}
6: for k E Fi do
7:
Update gr Br-1 + 8x and define Fy(y) m(Br.y) + |yy v1
8: Compute V, (egminyxx(VFrXy
9: Update Y++1 Yr + yr) with or in (4) and set +
end for end for
11:
Finally, we update T + that still indexes the latest intermediate decision.
The detailed procedures are summarized Algorithm 1, which is named as delayed OFW for convex losses. Let d = max (d1............ dr We establish the following theorem with respect the regret of Algorithm 1.
Theorem For any x" E K., under Assumptions and 2, Algorithm with /2G(T+22a/4 has
D
T f(xs) - - + 144)
T
1=1
Theorem shows that without knowing the value of d, our Algorithm can attain an O(T3/4 +dT regret bound for convex losses with arbitrary delays. This bound matches the (TT3/4 regret bound of OFW in the non-delayed setting [Hazan, 2016), as long does not exceed ((VT). Moreover, is better than (dd/4488/4 regret bound achieved by combining the technique Joulani et al. [2013] and the (TT3/1) regret bound of OFW for convex losses, as long d does not exceed (TT233).
3.3 Delayed OFW for strongly convex losses
We proceed to handle 3-strongly convex losses by slightly modifying Algorithm 1. Recall that the standard OCO without delays, the critical idea of utilizing the strong convexity of losses is to replace the surrogate loss function in (1) by that in (3) [Wan and Zhang, 2021]. The main difference that the regularization term in (3) is about all historical decisions, instead of only the initial decision.
Inspired by (3), we first redefine F; (y) in Algorithm 1 to
Ff = g y) + ly y.l
Second, since Fy( is modified, we adjust the line search rule to
OTO²
or = argmin(o - y-), Vv,()))) eE
2 ||v - yr
(5)
The detailed procedures are summarized in Algorithm 2, which is named delayed OFW for strongly convex losses. Then, we establish the following theorem about the regret of Algorithm 2.
Theorem Suppose all losses are 3-strongly convex and Assumptions and 2 hold. For any x K. Algorithm 2 has
T
T Σ -xx))= O dlogg)
Σ (xx))
Theorem 2 shows that our Algorithm 2 can attain O + d log T) regret bound for strongly convex losses with arbitrary delays. First, this bound is better than the O(T3/1 + dT regret bound
5

---

Algorithm 2 Delayed OFW for Strongly Convex Losses
1: Input: /
2: Initialization: choose an arbitrary vector y1 E IC and set r = 1, = 0
3: for t = 1,,2..... ........7 do
4: Play X = Yr and query 8: = (x((x)
5: Receive set of delayed gradients {gx Fi}
6: for k E Fi do
7:
Update g = gr-1 + g: and define F+ (gr. + E y:
8: Compute V,, (
9: Update Y++1 Yr + yr) with or in (5) and set 7 = +
end for end for
11:
in Theorem 1, which is established by only using the convexity condition. Second, it matches the ((T2/3) regret bound of OFW for strongly convex losses in the non-delayed setting [Wan and Zhang, 2021], as long as d does not exceed O log T). Third, it is better than the O(d1/372/3) regret bound achieved by combining the technique of Joulani et al. [2013] and the O regret bound of OFW for strongly convex losses, as long as d does not exceed (TT/(log 3)3/2).
4 Theoretical analysis
In this section, first introduce some insights and preliminaries for analysis, and then prove Theorems and 2 by introducing some lemmas. Due to the limitation of space, the proofs for those lemmas provided in the appendix.
4.1 Insights and preliminaries
Note that in the non-delayed setting, the regret bound of OFW is worse than that of OGD due the gap between the linear optimization step and the projection operation. Thus, in the delayed setting, it natural to conjecture that both the linear optimization step and the delay will affect the regret of our delayed OFW. To keep the same regret bound as the original OFW, our key insight is to prove that the combined effect of the linear optimization step and the delay can additive, instead of being multiplicative, and the effect of the delay can be weaker than that of the linear optimization step for relatively large amount of delay.
Moreover, there are some necessary preliminaries for our analysis. First, because of the effect of delays, there may exist some gradients that arrive after round T. Although our Algorithms 1 and do not need to use these gradients, they are useful for the analysis. As result, in our analysis, we further set x, = yr and perform steps to 10 Algorithms and for any = 1,...... . d-1- way, all gradients B1, 82, gr queried by our algorithms are utilized, which produces decisions y1,
In this
Then, let Ti = + E Fil for any E [T + d). is not hard to verify that our Algorithms and ensure that
X Vo.
(6)
for any 1 E [T +d 1). Next, we define
0. if [f = 0,
I
(7)
{T,, T: + 1,..., ,441 1). otherwise.
Let min (1/4 E [T + d - 11, [F > 0}. Is not hard to verify that
i=s T+d-1I [T] 0i
(8)
T UT+--1f, [7, - 0, #
To facilitate the analysis, we further denote the time-stamp of the 7-th gradient used in the update of our Algorithms and 2 by e,- To help understanding, one can imagine that our Algorithms and also implement c, & in their step 7. [ o 0, we have
, -1 F.
(10)

---

By using this notation, Fy( defined in Algorithms and 2 are respectively equivalent to
Fy(y) =
ge, y) + lyy - -yillé-
(11)
1=1
7
B ly Vell2.
Fr(y) Σ
Be y)
Σ
(12)
2
4.2 Proof of Theorem
Let = =t+ + d. - for any & E [7]. According to the convexity of fx(x), we have
f((x)) - f((x')
S gr X - x") = (g:, Xx' xx) + (g. Xe - xx)
S (g), X x") + G||x; xx Yor x*) + Glly,, -r
where the last equality is due to (6).
Let A = Etm Glly+. Vr,,12. 11. By summing over & = 1...., T, we have
T (x))
I(x) S
Σ g X xx) S Σ Nr. xx) A.
(13)
Then, bound the first term in the right side of (13) as follows
T-d-1 Σ
Σ t=1
gis Yre - x*)
g. Y -144,-1 -x*)
FeF.
T-d-1
Ttd-19ts-1
gi Yr. - xx) Σ
ga. -x")
iEFi
(14)
1441-
Σ
(g Vi xx) + (g. .r. - -v))
T+d-1 T441-1
Yr x')
YT. yt)
where the first equality due to (9), the second equality is due to + d3 t for any i Fe, the third equality is due to (10), and the last equality is due to (7) and (8).
Then, let B = Ein (ge, - x") and C = ETt T+d-l Eie
Glyy,, V1ll2. By combining (13),
(14), and (ge, Vr. - -v)) S Glly - -ysll2, we have
Σ fxx)) -((e)s
(15)
Next, proceed to bound terms A, B, and C. Specifically, first establish the following bound for the sum of terms A and C by carefully analyzing the distance l|y,, yr ll2 in the term and the distance lyy,, y.lla in the term C.
1), where F((y) is defined in (11). Suppose Assumption I and 2 hold, and there exist some constants y >> 0 and 0 < S 1 such that Fi-1(y)) Fx-1 < r(t 2)- for any E [T + 1). Algorithum ensures
Lemma Let Y argmingek Fy-1(y) for any 1 E [T+1)
8G SG 11 + 3rGG2dT
A+ < 3dGD + 4Gd
2 a-a a
2
where A = -T Glly,. -Y,, ll2 and C == -T++ Emt-1
1+11-1 Glyr. -yll2
Note that Lemma I introduces an assumption about y: and F.-1 (y). According to our Algorithm 1. Yt is actually generated by approximately minimizing Fy-1(y) with a linear optimization step. Therefore, by following the analysis of the original OFW [Hazan, 2016], we show that this assumption can be satisfied with y 8D2 and 1/2.
7

---

Lemma Le argmin yek Fi-1(y) for any E [T + 11, where Fi(y) is defined in (1I). Under Assumptions I and for any [T' + 11, Algorithm with 1l /2G(T+2)374
D has
8D2
Fr Fr)1 - Fy-) vl 4 2
Then, by combining 1)
/2G(T+2)9/4 with Lemmas 1 and 2, we have
D
A+C S (3+88(3+))) 32v2GD 13/4
3GDdT
= O(T8/4 + dT
(16)
3
2/2
Furthermore, by following the analysis of the original OFW [Hazan, 2016], we establish an upper bound for the term B.
Lemma 3 Under Assumptions and for any x* E K. Algorithm I with 1
+2C(T+2)8/4
D
ensures
T
(g Yt - xx) S 11v2GD + 2)3/4
GDT1/4
Σ
3
V2
Finally, by combining (15), (16), and Lemma 3, we complete this proof.
4.3 Proof of Theorem 2
Since fi(x) is B-strongly convex, we have
T
T
3
Σ
(xx))
I1(e) < Σ gr, X
(g.
x²)
Σ
X
1011-x111
x2112
(17)
2
1=1
1=1
Then, we note that the first term in the right side of (17) can be bounded by reusing (13) and (14). Specifically, we have
T
T
T ge, Yr - xx)
T
-
f((i)
Σ
X
x211
(18)
2
1=1
where terms A and C are defined in the proof of Theorem 1.
Next, we consider the last term in the right side of (18). For any X,, E K, we have
l x 12 ly: x:113 ||x:
x" 1| - 2(y: xt, -x)
<3D X; [12 + | 1
where the last inequality is due 2(y, Xt, X x*) - 221yy x x" ||2 and Assumption 2.
Let B' Ei= (ge, Yt -x)x") Σ' fly x 113 and E -'- 3BD y Y- 12. By combining the above inequality and (6) with (18), we have
- - (('
(19)
Then, we proceed to establish upper bounds for terms A, C, and E by carefully analyzing the distance lyy,, -y,, |/2 in the term A, the distance Ily,, y:ll2 in the term C, and the distance ||y, - yr, 12 in the term E.
Lemma 4 Let y argmin Fy-ily) for any t 2 where Fe(y) is defined in (12).
Suppose Assumption I and 2 hold, all losses are 3-strongly convex, and there exist some constants
Y 0 and 0 < a 1 such that F(-1(y:) F--1ly)) < 7(1 1)aa for any 2, .,....7 T 1. Algorithm I ensures
E <3dD + 2D.227 (1+0)/2 + 33dD2 + +DD(G + (D)ddn
1+0
A+ C S3GGD + 4G + 3D) In
4dG
2"
2y
8G
7 (1+a)/2
B
B
3
1
+
8

---

where A Ei Glly+, Vr C= I++-1 Disr Glly,, Ville. and E = Σt=1 1==1 yr.1l2.
38D
Note that Lemma 4 also introduces an assumption about Yt and Fy) According our Algorithm 2, Yt is actually generated by approximately minimizing Fi-1(y) with a linear optimization step. Therefore, by following the analysis of OFW for strongly convex losses [Wan and Zhang, 2021], we show that this assumption is satisfied with 7 16(G 2/3D)²/B and a 1/3.
Lemma Let y argmin Fy-1(y)fon for any t 2,..., T + 1, where Fe(y) defined in (12).
Suppose Assumption I and 2 hold, and all losses are B-strongly convex. For any t 2, T Algorithm 2 has
16(G 23D) 1)1/3
Pe-1 Fe-1(y)) -
B
By combining Lemmas 4 and 5, we have
A A+C+ F (T(2+a)/2+ dlog T) O(T2/3 + d dlogT) T).
(20)
Furthermore, by following the analysis of OFW for strongly convex losses [Wan and Zhang, 2021]; we establish an upper bound for the third term in (19).
Lemma 6 Suppose Assumption I and 2 hold, and all losses are B-strongly convex. For any x* E K.
Algorithm 2 ensures
6v DRGG+2DDj2Ta + B
23G+23D) hT
B' <
+ (G+
3
where B' = D St x*) - Ily, - x
Finally, by combining (19), (20), and Lemma 6, we complete this proof.
Experiments
In this section, we conduct simulation experiments to verify the performance of our delayed OFW for convex losses and strongly convex losses. All algorithms are implemented wtih Matlab R2017a and tested on laptop with 2.4GHz CPU and 16GB memory. The code is available from https: / //github. wwwcccmmmmm///ee
Specifically, we consider delayed OCO problem with T' = 10000 total rounds over the decision set K { R 10000 ||x||| S 200). which satisfies Assumption 2 with D) 400 due to ||x [ix-Xx -yll2 S
||||| + ||y||2 < |xx|| + || 400 for any x, y E K. Inspired by Li et al. [2019], in each round 1 E [T], the adversary chooses the following loss function
f((x) |x|2 + (b,,x)
where each element of b, E 1000 is independently and uniformly sampled from [-1, For any x K, since V (x) 2x + b;, it is easy verify that ||V fx()ll S 2 2||x||2 + ||b.ll S
2||x|| + | S 400 /1000, which implies that this loss function satisfies Assumption I with G 400 + 1000. We also notice that this loss function satisfies the definition 3-strongly convex function (i.e., Definition 1) with 3 = 2. Moreover, different values of the maximum delay d in the set (1,51, 11,,1,00,.-. .00)) are tried in our experiments, For each specific to simulate arbitrary delays, de is independently and uniformly sampled from the set {[0.1d), [0.1d] + [0.1d] + 2....,,),, d).
We compare our proposed algorithms against the combination of the technique in Joulani al. [2013] and OFW. Our delayed OFW for convex losses and strongly convex losses are denoted as DOFW (i.e., Algorithm 1) and DOFW... se (i.e.. Algorithm 2). respectively. Similarly, since the technique in Joulani et al. [2013] is named as black-box online learning under delayed feedback (BOLD), we denote the combination of BOLD with OFW for convex losses and strongly convex losses as BOLD-OFW and BOLD-OFW... se, respectively. The parameters of all algorithms are set as what their corresponding theories suggest. Specifically, according to our Theorems and 2, we set 7) VIG(T+2)av4 for
DOFW and set 2 for our DOFW se- According to Joulani et al. [2013], BOLD-OFW

---

x10
x10
DOFW
3.5
BOLD-OFW
DOFW,
ROLISOFW.
Cumultive Loss
Total Loss
2.5
2.5
DOFW DOEW, OF..
2
2
1.5
1.5
100
200
300
400
500
2000
4000
6000
8000
10000
Number of Iverations
(a) Different d
(b) d 501
Figure 1: Comparisons of our DOFW and DOFW sc against BOLD-OFW and BOLD-OFW... sc.
and BOLD- D-F.- sc will maintain several instances of OFW for convex and strongly convex losses, respectively. Note that in the non-delayed case with d = 1 our delayed OFW actually reduces to the original OFW. Therefore, our Theorems and 2 also be utilized choose the parameters for each instance of OFW maintained in BOLD-OFW and BOLD-OFW... To be precise, in BOLD-OFW, we set rj VIG(T/d42y5/4 for each instance of OFW for convex losses, since the total rounds of each instance is roughly T/d. In BOLD-OFW ses only need to set 3 2 for each instance of OFW for strongly convex losses. Moreover, for our delayed OFW and each instance of OFW, the initial decision is set to 1/50, where denotes the all-ones vector.
Fig. 1(a) shows the total loss delay d. First, when d = 1, the total loss of our DOFW is the same that of BOLD-OFW and the total loss of our DOFW is the same as that of BOLD-OFW... sc. which is reasonable because this case DOFW and BOLD-OFW reduce to the original OFW for convex losses, and DOFW.... sc and BOLD- OFW sc reduce to the original OFW for strongly convex losses. Second, for d = 51, 101, 151,.... 501, our DOFW and DOFW sc are better than BOLD-OFW and BOLD-OFW respectively, which clearly verifies the advantage of our algorithms in the delayed setting. larger than 72/3, Moreover, for our DOFW and DOFWsc. when d increases from to 501, the growth of the total loss is very slow, which is consistent with the dependence of our regret bounds on Fig. 1(b) shows the cumulative loss for each algorithm when d 501. As the number of iterations increases, the cumulative loss of BOLD-OFW and BOLD-OFW se increase much faster than that of our algorithms.
rounds for each algorithm under different values of the maximum
worthy to notice that 501
Conclusion and future work
In this paper, we propose delayed OFW for OCO with arbitrary delays. For convex losses, we show that it attains an O(T3/4 +dT//4 regret bound, which matches the ((T3/4) regret bound of OFW in the non-delayed setting, as long as does not exceed ((VT). When losses are strongly convex, we further prove that it can attain an O(T2/3 + dloo T) regret bound, which matches the (TT//3) regret bound OFW in the non-delayed setting, as long as does not exceed O / log T). Simulation experiments demonstrate the performance of delayed OFW in the delayed setting.
This paper only extends the classical OFW to the delayed setting. the future, we will investigate how to develop delayed variants for other projection-fres online algorithms.
Acknowledgments
This work was partially supported by NSFC (61921006, 62 62122037), and JiangsuSF (BK20200064).
10

---

References
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Lin Chen, Mingrui Zhang, and Amin Karbasi. Projection free bandit convex optimization. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 2047-2056, 2019.
Genevieve E Flaspohler, Francesco Orabona, Judah Cohen, Soukayna Mouatadid, Miruna Oprescu, Paulo Orenstein, and Lester Mackey. Online learning with optimism and delay. In Proceedings of the 38th International Conference on Machine Learning, pages 3363-3373, 2021.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2):95-110, 1956.
Dan Garber and Elad Hazan. linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3):1493-1528, 2016.
Dan Garber and Ben Kretzu. Improved regret bounds for projection-free bandit convex optimization. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 2196-2208 2020.
Dan Garber and Ben Kretzu. Revisiting projection-free online learning: the strongly convex case. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 3592-3600 2021.
Dan Garber and Ben Kretzu. New projection-free free algorithms for online convex optimization with adaptive regret guarantees. In Proceedings of 35th Conference on Learning Theory, pages 2326- 2359, 2022.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Elad Hazan and Satyen Kale. Projection-free online learning. In Proceedings of the 29th International Conference on Machine Learning, pages 1843-1850, 2012.
Elad Hazan and Edgar Minasyan. Faster projection free online learning. Proceedings of the 33rd Annual Conference on Learning Theory, pages 1877-1893, 2020.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Muchine Learning, 6992)1169-192, 2007.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, pages 427-435, 2013. 2013.
Pooria Joulani, András György, and Csaba Szepesvári. Online learning under delayed feedback. In Proceedings of the 30th International Conference on Machine Learning, pages 1453-1461, 2013.
Pooria Joulani, András György, and Csaba Szepesvári. Delay-toler online convex optimization: Unified analysis and ddaptive-gradien algorithms. Proceedings of the 30th AAAI Conference Artificial Intelligence, pages 1744-1750, 2016.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):2913377, 2005.
John Langford, Alexander Smola, and Martin Zinkevich. Slow learners are fast. In Advances in Neural Information Processing Systems 22, pages 2331-2339, 2009.
Kfir Y. Levy and Andreas Krause. Projection free online learning over smooth sets. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 1458-1466. 2019.
Bingcong Li, Tianyi Chen, and Georgios B. Giannakis. Bandit online learning with unknown delays. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 993-1002, 2019.
11

---

Zakaria Mhammedi. Efficient projection-free free online convex optimization with membership oracle. In Proceedings of 35th Conference on Learning Theory, pages 5314-5390, 2022.
Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. In Advances Neural Information Processing Systems 28, pages 1270-1278, 2015.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-19,, 2011.
Yuanyu Wan and Lijun Zhang. Projection-free online learning over strongly convex sets. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 10076-10084, 2021.
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Projection- distributed online convex optimization with O(VT) communication complexity. In Proceedings of the 37th International Conference on Machine Learning, pages 98 18 9828, 2020.
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Online strongly convex optimization with unknown delays. Machine Learning. 111(3::71-893, 2022a.
Yuanyu Wan, Guanghui Wang, Wei-We Tu, and Lijun Zhang. Projection- distributed online learning with sublinear communication complexity. Journal Machine Learning Research, 23 1172):1-53, 2022b.
Marcelo J. Weinberger and Erik Ordentlich. On delayed prediction of individual sequences. IEEE Transactions Information Theory, 48(7):1959-1976, 2002.
Wenpeng Zhang. Peilin Zhao, Wenwu Zhu, Steven C. H. Hoi, and Tong Zhang. Projection-free distributed online learning in networks. In Proceedings of the 34th International Conference on Machine Learning, pages 4054 4062, 2017.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-936, 2003.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work
mostly theoretical and the societal impacts discussion is not applicable.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Only synthetic data are used in this work, which do not contain personally identifiable information and offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "rTSLHRiYTl", "reviewer": "Reviewer_rmw7", "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.", "questions": "Is it clear whether OFW is the optimal algorithm for delayed feedback?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ywo5ZnqNHah", "reviewer": "Reviewer_LySe", "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. ", "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. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe 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.\n\nWeaknesses: \n1. It would be nice if the authors provide a numerical comparison with Joulani et al. [2013].\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TElIIqZTtdu", "reviewer": "Reviewer_cKYY", "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.\n\nThe 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.", "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nQuality : This paper is technically solid. The lack of simulations comparing their algorithms to benchmark algorithms is somewhat disappointing.\n\nClarity : This paper is clearly written. The assumptions are justified. The motivations and the literature review well addressed.\n\nSignificance : This paper presents a clear contribution by adapting a classical algorithm to a well motivated, practical problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5NGMoolR0pg", "reviewer": "Reviewer_6sxN", "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. ", "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.\n\nin 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.\nPlease discuss the relationship with these previous research results, and how much has it improved.\n\n\n", "limitations": "I don't  know the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n（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.\n（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.\n（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.\n（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.\n\nWeaknesses:\n\n（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.\n（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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept