Improved Regret for Bandit Convex Optimization with Delayed Feedback
Authors: Yuanyu Wan
Chang Yao
Mingli Song
Lijun Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandit Convex Optimization
Delayed Feedback
Improved Regret
Primary area: online_learning

Abstract: We investigate bandit convex optimization (BCO) with delayed feedback, where only the loss value of the action is revealed under an arbitrary delay. Let $n,T,\bar{d}$ denote the dimensionality, time horizon, and average delay, respectively. Previous studies have achieved an $O(\sqrt{n}T^{3/4}+(n\bar{d})^{1/3}T^{2/3})$ regret bound for this problem, whose delay-independent part matches the regret of the classical non-delayed bandit gradient descent algorithm. However, there is a large gap between its delay-dependent part, i.e., $O((n\bar{d})^{1/3}T^{2/3})$, and an existing $\Omega(\sqrt{\bar{d}T})$ lower bound. In this paper, we illustrate that this gap can be filled in the worst case, where $\bar{d}$ is very close to the maximum delay $d$. Specifically, we first develop a novel algorithm, and prove that it enjoys a regret bound of $O(\sqrt{n}T^{3/4}+\sqrt{dT})$ in general. Compared with the previous result, our regret bound is better for $d=O((n\bar{d})^{2/3}T^{1/3})$, and the delay-dependent part is tight in the worst case. The primary idea is to decouple the joint effect of the delays and the bandit feedback on the regret by carefully incorporating the delayed bandit feedback with a blocking update mechanism. Furthermore, we show that the proposed algorithm can improve the regret bound to $O((nT)^{2/3}\log^{1/3}T+d\log T)$ for strongly convex functions. Finally, if the action sets are unconstrained, we demonstrate that it can be simply extended to achieve an $O(n\sqrt{T\log T}+d\log T)$ regret bound for strongly convex and smooth functions.

Improved Regret for Bandit Convex Optimization with Delayed Feedback
Yuanyu Wan 12.3, Chang Yao 12.3, Mingli Song.., Lijun Zhang*2
School of Software Technology, Zhejiang University, Ningbo, China State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China Hangzhou High-Tech Zone (Binjiang) Institute of Blockchain and Data Security, Hangzhou, China National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China {wanyy, , changy, brooksong) @zju. edu. en, zhangl j@l @1lama.. nju..u..u. edu. cn
Abstract
We investigate bandit convex optimization (BCO) with delayed feedback, where only the loss value of the action is revealed under an arbitrary delay. Let n, T, d denote the dimensionality, time horizon, and average delay, respectively. Previous studies have achieved an O (VTT33/4 (nd) 1/32333) regret bound for this problem, whose -nayyiindeeedeent part matches the regret of the classical non-delayed bandit gradient descent algorithm. However, there is a large gap between its delay- dependent part, i.e., 1 and existing Ω[( V Vd) lower bound. In this paper, we illustrate that this gap can be filled in the worst case, where d very close the maximum delay d. Specifically, prove that it enjoys regret bound of O O(V7T3/1 + VdT) in general. Compared with the previous result, regret bound is better for d ((d))2333113 and the delay-dependent part is tight in the worst case. The primary idea is to decouple the joint effect of the delays and the bandit feedback on the regret by carefully incorporating the delayed bandit feedback with a blocking update mechanism. Furthermore, show that the proposed algorithm can improve the regret bound ( log T + dolog T) for strongly convex funetions. Finally, if the action sets are unconstrained, we demonstrate that it can be simply extended to achieve an Onn/Tloop + log T') regret bound for strongly convex and smooth functions.
first develop novel algorithm, and
Introduction
Online convex optimization (OCO) with delayed feedback [Joulani al., 2013, Quanrud and Khashabi, 2015] has become popular paradigm for modeling streaming applications without immediate reactions to actions, such as online advertisement [McMahan et al., 2013] and online routing [Awerbuch and Kleinberg, 2008]. Formally, is defined as a repeated game between a player and adversary. At each round t, the player first selects action from a convex set IC C IR.. Then, the adversary chooses a convex function fe(-) IR" + R. which causes the player a loss fx;)) but is revealed the end of round & d, 1, where d, 2 1 denotes arbitrary delay. The goal of the player to minimize the regret Reg(T) Σt= (x,) minxek Σt= fi (x),, i.e., the gap between the cumulative loss of the player and that of an optimal fixed action, where T is the number of total rounds.
Over the past decades, plenty of algorithms and theoretical guarantees have been proposed for this problem [Weinberger and Ordentlich, 2002, Langford et al., 2009, Joulani et al., 2013, Quanrud and Khashabi, 2015, Joulani et al., 2016, Héliou et al., 2020, Flaspohler et al., 2021, Wan et al., 2022a,b, Bistritz al., 2022]. However, the vast majority of them assume that the full information or gradients
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

of delayed functions are available for updating the action, which is not necessarily satisfied in reality. For example, in online routing [Awerbuch and Kleinberg. 2008], the player selects a path through a given network for some packet, and its loss is measured by the time length of the path. Although this loss value can be observed after the packet arrives at the destination, the player rarely has access to the congestion pattern of the entire network [Hazan, 2016]. To address this limitation, it is natural to investigate a more challenging setting, namely bandit convex optimization (BCO) with delayed feedback, where only the loss value fi (xx) is revealed at the end of round + de- - 1.
It is well known that in the non-delayed BCO, bandit gradient descent (BGD), which performs the gradient descent step based on one-point estimator of the gradient, enjoys regret bound of Ol O(vnT3/1) [Flaxman et al., 2005]. Despite its simplicity, without additional assumptions on functions, there does not exist any practical algorithm that can improve the regret of BGD. Therefore, a few studies have proposed to extend BGD and its regret bound into the delayed setting [Héliou al., 2020, Bistritz et al., 2022]. Specifically, Héliou al. [2020] first propose an algorithm called gradient-free online learning with delayed feedback (GOLD), which utilizes the oldest received but not utilized loss value to perform an update similar to BGD at each round. Let d = max(d1...
dr } which matches the O ((VTT3/1) regret of BGD in the
denote the maximum delay. According to the analysis of Héliou et al. [2020], GOLD can achieve
regret bound of O(V7TT8/ + (nd)1/3322/83 non-delayed setting for d = O O(Vn22/44) Very recently, Bistritz et al. [2022] develop an improved variant of GOLD by utilizing all received but not utilized loss values one by one at each round, and reduce the regret bound to O(ynT3/4 + (nd)1/3772/3)
where d = (1/T) Di= de the average delay. However, there still exists a large gap between the delay-dependent part in the improved bound and an existing S2( ddT) lower bound [Bistritz et al., 2022]. It remains unclear whether this gap can be filled, especially by improving the existing upper bound.
In this paper, we provide an affirmative answer to this question in the worst case, where d is very close to d. Specifically, we first develop a new algorithm, namely delayed (D-FTBL), and show that it enjoys a regret bound of O(Viir//4 + vdT)) in general. Notice that both the ((nd))//372/3 and 1/333/33722/ terms in previous regret bounds [Héliou et al., 2020, Bistritz et al., 2022] can be attributed to the joint effect of the delays, and the one-point gradient estimator, especially its large variance depending on the exploration radius. To improve the regret, besides the one-point gradient estimator, we further incorporate the delayed bandit feedback with blocking update mechanism, i.e., dividing total T rounds into several equally-sized blocks and only updating the action at the end of each block. Despite its simplicity, there exist two nice properties about the cumulative estimated gradients at each block.
First, with an appropriate block size, its variance becomes proportional to only the block size without extra dependence on the exploration radius.
Second, the block-level delay, i.e., the number of blocks waiting for computing the cumula- tive estimated gradients at each block, is in reverse proportion to the block size.
Surprisingly. by combining these properties, the previous joint effect of the delays and the one-point gradient estimator can be decoupled, which is critical for deriving our regret bound. Compared with the existing results, in the worst case, our regret bound matches the O OVVTT//4) regret of the non-delayed BGD for a larger amount of delays, i.c., d O(nvT), and the delay-dependent part, i... O(VdT), matches the lower bound. Moreover, is worth noting that our regret bound actually better than that of Bistritz et al. [2022] as long as d is not larger than (md))//87113) which even covers the case with d O(1) partially. To the best of our knowledge, this is the first work that shows the benefit of the blocking update mechanism in delayed BCO, though it is commonly utilized to develop projection-fiee algorithms for efficiently dealing with complicated action sets [Zhang et al., 2019, Garber and Kretzu, 2020, Hazan and Minasyan, 2020, Wan et al., 2020, 2022c, Wang et al., 2023, 2024b].
Furthermore, we consider the special case of delayed BCO with strongly convex functions. In the non-delayed setting, Agarwal et al. [2010] have shown that BGD can improve the regret from O ((VT33/4) to ((TT)2//3 log" // T) by exploiting the strong convexity. If functions are also smooth and the action set is unconstrained, BGD has been extended to achieve an O(nyTToo regret
Note that Bistritz et al. [2022] actually only argue a regret bound of 0/4 + 23/23) However, discussed in our Appendix F, it is not hard to derive this refined bound by tuning parameters more carefully.
2

---

bound [Agarwal et al., 2010]. Analogous to these improvements, we prove that our D-FTBL can achieve regret bound of (((I2)//3 log log nogl// T - + log I for strongly convex functions, and its simple extension enjoys a regret bound of O(ny'T log T + d log I') for strongly convex and smooth functions over unconstrained action sets. These regret bounds also match those of BGD in the non-delayed setting for a relatively large amount of delay. Moreover, the Od 7) part in these two bounds matches O(d T' lower bound adapted from the easier full -ollrinfonnntionn setting with strongly convex and smooth functions [Weinberger and Ordentlich, 2002].
2
Related work
In this section, we briefly review the related work on online convex optimization (OCO) and bandit convex optimization (BCO), as well as delayed feedback.
2.1 Standard OCO and BCO
If d, for all i E (T). OCO with delayed feedback reduces to the standard OCO [Zinkevich, 2003]. Online gradient descent (OGD) [Zinkevich, 2003, Hazan et al., 2007] is one of the most popular algorithm for this problem, which simply updates the action x; via gradient descent step based on V (xx,). By using appropriate step sizes. OGD can achieve ((vT) and O(log T') regret bounds for convex and strongly convex functions, respectively. bollow-the-regulariiee--eeee
(FTRL) (Hazan al., 2007, Shalev-Shwarzz, 2011, 1, Hazan, 2016] is an alternative algorithm, which chooses the new action by minimizing the linear approximation of cumulative loss functions under some regularization. With appropriate regularization, FTRL achieves the same ((TT) and Ollog 7') regret bounds as OGD. Moreover, Abernethy et al. [2008] have presented a lower bound of (2(VT) for convex functions, and refined lower bound of 21log T) for strongly convex functions, which implies that both OGD and FTRL are optimal.
BCO is special yet more challenging case of OCO, where the player can only receive the loss value fx(x) at each round f. The first algorithm for BCO is bandit gradient descent (BGD) [Flaxman et al., 2005], which replaces the exact gradient used in OGD with an estimated gradient based on the single loss value (known as the classical one-point gradient estimator). By incorporating the approximation error of gradients into the regret analysis of OGD, Flaxman et al. [2005] establish an O( / regret bound for BGD with convex functions. Later, Agarwal et al. [2010] show that BGD enjoys an ((TT)22/3 2/3 2/3 T) regret bound for strongly convex functions, and can be extended to achieve an (nnyTinnn T') regret bound in the special case of unconstrained BCO with strongly convex and smooth functions. Saha and Tewari [2011] develop a new algorithm for BCO with smooth functions,
and establish the ((TT)2/3 log" 1/3 T') regret bound without the strongly convex assumption. van der Hoeven et al. [2020] propose novel BCO algorithms, which adaptively improve the previous regret bounds for convex and smooth functions if the norm of the comparator is small. By revisiting the case with strongly convex and smooth functions, several algorithms [Hazan and Levy, 2014, Ito, 2020] have been developed to achieve the OnyTToogT T)) regret bound in the constrained setting.
Moreover, series of studies [Bubeck and Eldan, 2016, Hazan and Li, 2016, Bubeck et al., 2017, Lattimore, 2020, Bubeck et al., 2021] have been devoted to designing nearly optimal algorithms, which almost match the (2(n/T) lower bound for the general BCO [Shamir, 2013] without any additional assumption. However, the running time of their algorithms are either exponential in and T, or polynomial with a high degree on n and T. which is not suitable for practical large-scale applications. We refer the interested reader to Lattimore [2024] for a comprehensive survey on BCO. Additionally, we notice that BCO is closely related to the zero-order stochastic optimization (ZOSO) problem [Duchi et al., 2015, Bach and Perchet, 2016, Shamir, 2017], where the stochastic values available for minimizing a fixed loss function. However, ZOSO is less challenging than BCO in the sense that it does not need to deal with time-narying functions and is usually allowed to query the loss value at two points per iteration.
2.2 OCO and BCO with delays
The seminal work of Weinberger and Ordentlich [2002] first considers the case with a fixed delay, ic., de = d for all t [T]. and proposes black-box technique that can covert any traditional OCO
3

---

algorithm into the delayed setting. The main idea is to maintain d' instances of the traditional algorithm. and alternately utilize these instances to generate the new action. If the regret of the traditional algorithm is bounded by Reg(T), this technique can achieve an d (egg(Td) /d) regret bound. Moreover, there exist Q(vdI and [dd T) lower bounds for convex functions, and strongly convex and smooth functions, respectively [Weinberger and Ordentlich, 2002]. However, the delays are not always fixed in practice, and its space complexity is d times much as that of the traditional algorithm, which could be prohibitively resource- dasource-intensive. Although Joulani et al. [2013] have generalized this technique to deal with arbitrary delays, the space complexity remains high. Besides these black-box techniques, there exists surge of interest in developing and analyzing specialized algorithms for delayed OCO [Langford et al., 2009, McMahan and Streeter, 2014, Quanrud and Khashabi, 2015, Joulani et al., 2016, Li et al., 2019, Flaspohler et al., 2021, Wan et al., 2022a,b, 2023, 2024], which do not require additional computational resources.
Despite the great flourish of research on OCO with delays and BCO, delayed BCO has rarely been investigated. GOLD [Héliou et al., 2020] is the first algorithm for this problem, which originally has the O( O(VTT8//4 + (md)² ) regret, and is further refined to enjoy the O( /nTT//44 (2d))/377233 regret [Bistritz. et al., 2022]. However, Bistritz et al. [2022] also present an unmatched lower bound of ((VdT). Although two recent advances in more complicated bandit non-stochastic control problem [Gradu et al., 2020, Sun et al., 2023] provide some intermediate results about OGD and FTRL with the delayed bandit feedback, they focus on the case with a fixed delay and can only recover the O(VāT3/4 + (nd)1/372///
regret in general. In this paper, we take one further step toward understanding the effect of arbitrary delays on BCO by establishing improved regret bounds such that the delay-independent part is equal to the regret of BGD, and the delay-dependen part matches the lower bound in the worst case. Moreover, we notice that although the block-box technique of Joulani et al. [2013] can also convert BGD into the delayed setting, it only achieves (Vyrd' /4T0/44 regret bound for convex functions, which is much worse than that of GOLD and our algorithm.
3 Main results
In this section, we first introduce the necessary preliminaries including definitions, assumptions, and an algorithmic ingredient. Then, we present our improved algorithm for BCO with delayed feedback, as well as the corresponding theoretical guarantees.
3.1 Preliminaries
We first recall two standard definitions about the smoothness and strong convexity of functions [Boyd and Vandenberghe, 2004].
Definition 1. A function fxx R² E is called 3-smooth over K. for all x,y E K, it holds that f(y) S fxx) + (Vf(x). y x) + Glly x12
Definition 2. A function fxx IR" + IR is called o-strongly convex over K. ifr all x,y E K., it
holds that f(y) Z f(x) + (V - x) + Ily - x1i2.
Note that as proved by Hazan and Kale [2012], any a-strongly convex function f(x): : 12 + IR over the convex set KC' ensures that
1x-xx fxx) [xx")
(1)
2
for any E K., where x" argminxee fxx)
Then, following previous studies on BCO [Flaxman et al., 2005, Héliou et al., 2020, Garber and Kretzu, 2020, 2021], we introduce some common assumptions.
Assumption 1. The convex set K. is full-dimensional and contains the origin, and there exist two constants R >>0 O such that r C K. C RB", where 13th denotes the unit Euclidean ball centered at the origin in R.a.
A Assumption 2. All loss functions are G-Lipschisz over K., for all x,y E K. and t E [T), it holds that [f((x) fr(y)) S G||x 11xx-y yl12-
Assumption 3. The absolute value of all loss functions over K. are bounded by M, i.e., for all x e K. and E (T), it holds that [f((x)] S M. Additionally, all loss functions are chosen beforehand, iee. the adversary is oblivious.

---

Finally, we introduce the one me--point gradient estimator [Flaxman et al., 2005], which is standard technique for exploiting the bandit feedback. Given a function f(x) R + I. we can define the 3-smoothed version of I (x) as
(x) Eu-B- if + óu)]
where the parameter & (0, 1) is the so-called exploration radius. As proved by Flaxman et al. [2005], the d-smoothed version satisfies the following lemma.
Lemma 1. (Lemma 1 in Flaxman et al. [2005]) Given a function [xx R - R and constant
5 E (0, 1), its 6-smoothed version fx(x) defined in (2) ensures
fs(x) Eu-ss
n [5 [ + Su)u
where S" denotes the unit Euclidean sphere centered at the origin in R".
From Lemma the randomized vector 6 fxx + ōu)u, which can be computed by only utilizing single loss value, is an unbiased estimator of V fa (x). Moreover, Flaxman et al. [2005] have also shown that (x) is close to the original function f (x) over shrunk set
Ks = (1 k/r) = {(1 8/r)x E K.).
Therefore, this moi- estimator can be utilized as good substitute for the gradient V (x) in the bandit setting. For example, we notice that at each round t, BGD [Flaxman et al., 2005] first plays an action y+ ue, where y, E Ks and u, S", and then updates ye as
V1+1 = -Ilcs Yy=
Tt 8
((x)))
where II,, (y) = argmin ||x size.
v11 denotes the projection onto the set KSs, and 17, is the step
3.2 Our improved algorithm
Before introducing our algorithm, we first briefly discuss the joint effect of the delays and the bandit feedback in GOLD [Héliou et al., 2020], which will provide insights for our improvements. Recall that in the delayed setting, the loss value (xe) will be delayed to the end of round L d, - 1, and thus f}. Since the set Fg may not contain the round f, the vanilla BGD in (4) is no longer valid. To address this issue, GOLD [Héliou et al., 2020] replaces f((x;) (4) with the oldest received but not utilized loss value at the end of round f. Intuitively, the update of this approach is O(d) rounds slower than that of the vanilla BGD, which is analogous to those delayed OCO algorithms. However, due to the use of the one-point gradient estimator, the slower update causes difference of (r)dn/5) between its action and that of BGD, and the cumulative difference will bring additional regret of (TTdnn/ where a constant step size 7/ is discussed for brevity. Note that from the standard analysis of BGD, to control the total exploration cost, the value of 1/5 should be sublinear in T. Therefore, will amplify the effect of delays, and finally results in the ((VTT3/1 + (3d)3/372/33 regret [Héliou et al., 2020].
the player can only receive (ff (xx) k E Fi} the end of round t. where F, = {ki]k + dg
To reduce the effect of delays, we propose incorporate the delayed bandit feedback with a blocking update mechanism [Zhang et al., 2019, Garber and Kretzu, 2020]. Specifically, we divide the total T rounds into T T/K K blocks, each with K rounds, where T/K K is assumed be an integer without loss of generality. For each block m E [T/K] [], we only maintain preparatory action ym E K.s, and play x, Ym ou, with u, S each round in the block. Due the randomness of u, and the independence of in the same block, is not hard to verify that for each block m E [T/K], the sum of randomized gradients generated by the one-point estimator, i.e., V.. mn satisfies (see Lemma 5 presented in Section 3.4 for details)
(m- K)K+ f (x())),,
Bi| |22 = Olv Kn2/82 K).
By using an appropriate block size of K = (8), this upper bound will be =[]\v=lll]=0(M By contrast, without the blocking update mechanism, one can only achieve E|]] V [2] = O(n/8)) Moreover, notice that the cumulative estimated gradients V will be delayed at most O(d/K)
5

---

Algorithm Delayed Follow-The- Tollow-Thh-Banddi-LLaddee
1: Input: K, a, and 1j 0 a 0
2: Initialization: set go = and choose y1 E Ks arbitrarily
3: for m = 1,2,. T/K do
4: for (- (m 1)K I....,mk do
5: Play x, = ym du,, where u, S"
6:
Query Se fe(x:), and receive (f((xa) E Fi)
7: Update g: gc-1 + ΣXEF, (x
8:
end for
1| 1|x--111 v1ll
a
9: Set Rm (x)
Dx Ka
| vi 1
otherwise
10: Mm+11 argmin {BmKK , X) + Rm (x)
11:
end for
blocks, because even the last component fffm (Xm um is available at the end of round mkK + 1.
As a result, one possible approach to determine ym for each block is to extend the update rule of GOLD [Héliou al., 2020] into the block level with K = O(n² / Combining with previous discussions, it will reduce the effect of delays on the regret from (TTndn/0) to
( (V Tn K
(V Kn² 82 + (X)
( )
o
which is good enough for deriving our desired regret bounds. However, requires a bit complicated procedure to maintain the cumulative estimated gradients for any block that has not been utilized to update the action. For this reason, instead of utilizing this approach, we incorporate FTRL [Hazan al., 2007, Hazan, 2016] with the delayed bandit feedback and blocking update mechanism, which provides a more elegant way to utilize the delayed information.
Specifically, we initialize y1 E Kg arbitrarily, and use variable to record the sum of gradients estimated from all received loss values, i.e., g. = Ei= ΣnEF, (xx Ju; Then, according to FTRL, an ideal action should be selected by minimizing the linear approximation of cumulative loss functions under some regularization, i.e.,
m++1
argmin xEKs
(V x) + Rm (x)
(5)
1=1
where the regularization is set (x)
" ||x vıl12 for convex functions [Hazan, 2016] and
Rm, (x) = Σm Ka x v:1lž for a-strongly convex functions [Hazan et al., 2007]. Unfortunately, due to the effect of delays, the value of Σ V, required by (5) may not be available. To address this limitation, we generate ym+1 by replacing this term with the sum of all available estimated gradients, i.e., Bmx.²
2
The detailed procedures are outlined in Algorithm 1, where the input is the modules of the strong convexity of functions, and it is called delayed follow-the-bandit-eedddd (D-FTBL).
3.3 Theoretical guarantees
We first present the regret bound of our D-FTBL for convex functions.
Theorem 1. Under Assumptions 1, 2, and 3, Algorithm I with 0 ensures
4R²2
r''
TT
d2
7 35GT + 8GRT
E [Reg(T)
+
(6)
11
2K
2
R2
r
:=A
where y =
K ( K2G
FFrmm the above discussions, one may replace >m, V. with the sum of all available V.. However, we find that simply utilizing gmx attain the same regret, though they have slight difference.

---

Remark. To help understanding the regret bound in (6), we notice that the term A actually is derived from the expected regret of the ideal action y on sequence of surrogate losses, and the term B is caused by the cumulative distance between our preparatory action ym, and the ideal one. Additionally, the term C' caused by the exploration error of the one-point gradient estimator, At first glance, seems that term B suffers multiplicative joint effect of the maximum delay d and the exploration radius ó due to the existence of y, However, as discussed before, this joint effect can be decoupled by setting an appropriate block size of K O /8*), which allows to derive an improved regret bound. Specifically, by substituting 5 = e//TT-1/4 into (6), where e is constant such that our D-FTBL can enjoy
0, K n nvT, 7) 1/ max{ VTd, /nT3//4, and
E [Reg(Z)) 0o (Vrr + dT
for convex functions, 3 It is tighter than the OV + (md))/3/T2/5) regret of GOLD (Héliou et al., 2020), and matches the O (V/TTS/1) regret bound of BGD in the non-delayed setting as long as d is not larger than Onv Even for d (((vTT), our regret bound is dominated by the O(vdT) part, which matches the Q(VdT) lower bound [Bistritz al., 2022] the worst case. Moreover, although the (V/nT3/4 + l regret bound of Bistritz et al. [2022] could benefit from small average delay, is also worse than our regret bound when d not larger than ((nd))/3TT1/))
Then, we establish an improved regret bound for a-strongly convex functions.
Theorem Under Assumptions 1, 2, and 3, if all functions are a-strongly convex, Algorithm with >> 0 ensures
24Cr
GCT
d K2
8GRT
E [Reg(T)) S
aK + CCRVT+
+4
38GT
(8)
a
==
:=
where K (2M))² + K2G? Cr In and C7 41n
Remark. By comparing Theorem with Theorem 1, we find that the strongly convexity can be exploited to reduce the expected regret of the ideal action y on the surrogate losses, and the cumulative distance between our preparatory action ym and the ideal one, i.e., improving terms A
and B in (6) to terms A' and B' in (8). By further substituting a > 0, K = (nTT)2/3 In 2/3 T, and 8 = 2/3TT- In 1/3 T into (8), where cs constant such that 6 < r, our D-FTBL can enjoy
E (Reg(T) (T)) $o (n/T)2/3
2/3 log 1/3 T + dloog
(9)
for strongly convex functions. This regret bound is tighter than the above O D(/TT3/4 + VdT) regret bound achieved by only utilizing the convexity condition, and match the ( log 2/3 T) regret bound of BGD in the non-delayed setting long d is not larger than ((nTT/ log 2)2/3). Even if d ((nTT log 2/3, is dominated by the O(d log 7') part, which matches the Si T) lower bound (Weinberger and Ordentlich, 2002), and thus cannot be improved. Moreover, different from the case with convex functions, the parameters for achieving the bound in (9) do not require the information of delays.
Furthermore, we consider the unconstrained case, i.e., K. RR" with a-strongly convex and B- smooth functions, and extend our D-FTBL to achieve a better regret bound. Specifically, without the boundedness of K,, Assumptions 2 and may longer hold over the entire space [Agarwal et al., 2010]. Therefore, we first introduce a weaker assumption on the Lipschitz continuity, ie, all loss functions are G-Lipschitz O. Combining with (1), it is not hard to verify that the fixed optimal action argmin Σt f((x) satisfies
x 112 < 2G
(10)
'One may notice that step size for achieving this result depends on maximum delay which may be unknown beforehand. Fortunately, as discussed in previous studies [Quanrud and Khashabi, 2015, Wan et al., 2024], there exists a standard solution utilizing the "doubling trick" [Cesa- -ianchh et al., 1997] to adaptively estimate the maximum delay d and adjust the step size, which can attain the same bound as in (7).
7

---

As result, the player only needs to select actions from the following set
2G K' = x R"
|
(11)
a
which satisfies Assumption I with r R 2G/a, and it is natural to further assume that all loss functions satisfy Assumptions 2 and 3 over the set KC'. Now, we can apply our D-FTBL over the shrink set of K",, i...
(1- = (1- ad
K
(12)
2G
instead of the original Ks, and establish the following regret bound.
Theorem 3. Let K R If all loss functions a-strongly convex and B-smooth over K., and Assumptions 2 and 3 hold over K' defined in (11), applying Algorithm with a > over K' defined in (12) ensures
2y0r E [Reg(T))
GV a
GCT
( dd2 +1) y 35
GT
aK +
/2 K2 +
(13)
a
where 7 = K (aM) K2G CT In and C7 + 4
Remark. By comparing Theorem with Theorem 2. we find that the exploration error of the one-point gradient estimator is reduced, i.c. improving the last two terms in (8) to the term C" in (13). Then, by substituting > 0, K nyT/In' T, and 2/2 1/4 In 1/4 T into (13), where c is a constant such that 2G/a, we can achieve an O (nvT log + dlog T) regret bound for strongly convex and smooth functions in the unconstrained case. It is better than the (((nT)2/3 log 1/3 T + dlog T) regret bound achieved by only utilizing the strong convexity. Moreover, this bound matches the O(nvTlog?)) regret bound achieved by using BGD in the non-delayed setting as long as d is not larger than On Iog Otherwise, it is dominated by the Odd T') part, which cannot be improved as discussed before.
3.4 Analysis: proof of Theorem 1
Due to the limitation of space, here we only prove Theorem 1, and the omitted proofs can be found in the appendix. Specifically, let x* = (1 8/r)x* where x" E argmin Σ fx(),, and recall the ideal action defined in (5). As in Lemma we first notice that the expected regret of Algorithm I can be bounded by the sum of three parts including the expected regret of ideal actions on some surrogate losses, the cumulative distance between ym and the ideal one, and the exploration error of the one-point gradient estimator.
Lemma 2. Under Assumptions 1 and 2, Algorithm I with a 0 ensures
TуK
T/K
ll vinlle + 38GGT + SGRT
E [eg SE
E
Vn..". - xx) + KG
Σ m=1
(14)
Note that the part regarding the exploration error in (14) is exactly the same the term C in (6). So, we only need to analyze the first two parts in (14). For the first part, we define surrogate losses as (xx (V1.x) + || x yılla and &m (x) (Vm:.) x) for any
2..... .....,T/K.. Combining with (5) for convex functions, it is easy to verify that ym+1 = argminxex. Em (x().. Then, we introduce the following lemma to bound the regret y². .T/KK4 on (i(.)...,, (T)
Lemma 3. (Lemma 6.6 in Garber and Hazan (2016)) Let (lx(x) be sequence of functions over set K., and let x argmin xex: Ei=1 (x(x) for any E [T]. Then, it holds that Σt= (x(x;)
minxek ΣT= (x(x) S...
Specifically, by applying Lemma 3, we have TT/K em (n -XTTK TT/K (x())) S 0. Combining
this inequality with Assumption 1, have
T/K
x y1
122
V1
4R²
V ma y m+11 - x*) <
(15)
71
8

---

Moreover, to replace y in the left side of (15) with y we introduce the following lemma.
Lemma 4. (Lemma in Duchi al. [2011]) Let 1 (u, argmin { (u, x) have [[]x(,, (x " v|12-
,
11xx We
Combining Lemma 4 with (5) for convex functions, we have
||
2y
2y "
Iy 1m+1lll - 2
Σ V
V
V 1 (16)
2
1=1
Then, combining (15) with (16), have
T/K
T/K
Σ
V Mms y -x) = Σ
mm y m+1 -X" + +ym - -Ym+1)
m=1
m=1
(17)
4R
T/K
Σ
M ymm S
4R
1
T/K
Σ
V m
2
2
m=1
We notice that the term || 2 (17) can directly benefit from the blocking update mechanism, as shown by the upper bound in the following lemma.
Lemma 5. Under Assumptions 2 and 3, for any m E [T/K], Algorithm ensures EE V B S K (MM) K2G?
However, completely bound the right side of (14), we still need to analyze llym y 12. which is more complicated due to the effect of delays. Specifically, let
Um = [1, (m - 1)K} 10m-- Fr
(18)
be the set consisting the time stamp loss values that are queried but still not arrive the end of round (m 1)K. By using Lemma 4 again, we have
Im y 1 s 77
8(m-1)K
2y1
Σ
V
2y1 "
Σ
fx(x))
(19)
2
Moreover, we establish the following lemma regarding the right side of (19). Lemma 6. Under Assumptions 2 and 3, for any m E [T/K], Algorithm ensures
Σ 5 (x
2
d
+ 4
K
nM
+ K2
K2
tetl
Combining (14), (17), (19), Lemma 5, Lemma 6, and 7 = K [nM 2
+ K2G?, we have
T/K
T/K
E [Reg(T))
4R
+
E
7
V
11
+ KG
Σ m=1
E Ellym
y [2] 35GT
5GRT
11
2
m=1
2R
TT
TG
d2
SGRT
S
+
V2
K2 +4
++35GT
x 35GT
"
2K
2
Experiments
In this section, we compare our D-FTBL against GOLD [Héliou et al., 2020] and improved GOLD [Bistritz et al., 2022] by conducting simulation experiments two publicly available data sets-ijjenn and SUSY from the LIBSVM repository [Chang and Lin, 2011]. All algorithms are implemented with Python, and tested on a laptop with 2.4GHz CPU and 16GB memory.

---

100
-10*
4.8
D-FTBL. GOLD
4.5
-..
Improved GOLD
4.6
M8.
Improved GOLD
GOLD
4.4
Total Loss
Total
4.2
2,5
3.8
3.6
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
ijennl
(b) SUSY
Figure 1: Experimental results on delayed online binary classification for ijennl and SUSY.
Specifically, we randomly select T' 40000 examples from the original data sets, and consider online binary classification over convex set K (x E |*|||[|| S 50}. The dimensionality of ijennl and SUSY are n 22 and n = 18, respectively. In each round E [7]. the adversary chooses the hinge loss
[x()) = max {1 w 0]
where w, and y/ E { the feature vector and class label of the t-th example. respectively. Different values of the maximum delay d in the set {200, 600, 1000. ... 5000) have been tried in experiments. For each specific d, to simulate arbitrary delays, de is independently and uniformly sampled from [d]. In this way, the average delay d is equal to (d + 1 in expectation, and thus is close to the maximum delay.
According to the previous discussions about Theorem 1, we set = 0, K
and - c max| / for our D-FTBL by tuning these two constants and é'. For those two baselines, we only need to set parameters ö and f). addition to the theoretically suggested value of 5 and 17. also introduce and c' the scale factor, respectively. For all algorithmss, and are respectively selected from {0.1, 1.0, 10} and {0.01, 0.1, 100} simply according to their performance for d 200. Moreover, due the randomness of these algorithms,, repeat them 20 times and report the average of their total loss.
Fig. 1 shows the results of all algorithms on both data sets. We first find that when d increases from 200 to 5000, the total loss our D-FTBL grows slowly, which is consistent with the dependence of our regret bound on d. Second, from d = 600 to d 5000, the total loss of our D-FTBL is better than both GOLD and improved GOLD, which verifies the advantage of our algorithm in the delayed setting. By contrast, due to d sz d. the performance of improved GOLD is very close to that of GOLD. Finally, also notice that D-FTBL is slightly worse than basclines for = 200. However, it is reasonable because the block update mechanism enlarges each delay to be at least the block size, which could result in slightly larger constant factor in the regret.
worth noting that d = 5000 is larger than nvT in our experiments.
Conclusion and future work
In this paper, we investigate BCO with delayed feedback, and propose novel algorithm called D-FTBL by exploiting the blocking update mechanism. Our analysis first reveals that it can achieve a regret bound of ( 3/7 + vdT) in general, which improves the delay-dependent part of the existing 3/vn13/44 (nd) 2/3/233 regret bound as long as d is not larger than ( ((nd)2/3TT1 Furthermore, we consider the special case with strongly convex functions, and prove that the regret 1/3 1/3TT T + d log T). Finally, if the action sets are uncon- of D-FTBL can be reduced to ((n7))2/3 l/3 strained, we show that D-FTBL can be simply extended to enjoy the O(nyTooo log + dolog T') regret for strongly convex and smooth functions. Nonetheless, there still exist several open problems, which discussed in the appendix due to the limitation of space.
10

---

Acknowledgments
This work was partially supported by the National Natural Science Foundation of China (62306275. U23A20382), the Zhejiang Province High-Level Talents Special Support Program "Leading Talent of Technological Innovation of ThoTuuasa Talents Program" (No. 2022R52046), the Key Research and Development Program of Zhejiang Province (No. 2023C03 192), and the Open Research Fund of State Key Laboratory of Blockchain and Data Security, Zhejiang University. The authors would also like to thank Chenxu Zhang for helping conduct experiments.
References
Jacob D. Abemetthy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal stragies and minimax lower bounds for online convex games. Proceedings of the 21st Annual Conference on Learning Theory, pages 415-424, 2008
Alekh Agarwal and John C. Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems 24, pages 873-881, 2011.
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi- point bandit feedback. In Proceedings of the 23rd Annual Conference on Learning Theory, pages 28 40, 2010.
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008
Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. Proceedings of the 29th Annual Conference Learning Theory, pages 257-283, 2016.
Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet. No weighted-regret learning in adversarial bandits with delays. Journal of Machine Learning Research, 23(139):
2022.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Sébastien Bubeck and Ronen Eldan. Multi-scale exploration of convex functions and bandit convex optimization. In Proceedings of the 29th Annual Conference on Learning Theory, pages 583-589, 2016.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimiza- tion. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72-80 85, 2017.
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimiza- tion. Journal of the ACM, 68(4):1-25, 2021. 2021.
Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How use expert advice. Journal of the ACM, 44(3):427-485, 1997.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions Intelligent Systems and Technology, 2(27):1-27, 2011.
Sijia Chen, Yu-Jie Zhang, Wei-Wei Tu, Peng Zhao, and Lijun Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 25(178):1-62, 2024.
John C. Duchi, Alckh Agarwal, and Martin J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57(3)5592- 606, 2011.
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for 7ero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788-22) 2015.

---

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.
Abraham Flaxman, Adam Tauman Kalai, and Brendan McMahan. Online convex optimization in the bandit setting: Gradient descent without gradient. In Proceedings of the 16th Annual ACMM-IAMM Symposium on Discrete Algorithms, pages 385-394, 2005.
Dan Garber and Elad Hazan. A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. SIAM Journal on Optimization, 26(3): 1493)15493-5 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 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.
Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. In Advances in Neural Information Processing Systems 33, pages 10764-10774, 2020.
Elad Hazan, Introduction to online convex optimization. Foundations and Trends Optimization, (3 (3-4):157-325, 2016.
Elad Hazan and Satyen Kale. Projection-five online learning. Proceedings of the 29th International Conference Machine Learning, pages 1843-1850, 2012.
Elad Hazan and Kfir Y. Levy. Bandit convex optimization: Towards tight bounds. In Advances in Neural Information Processing Systems 27, pages 784-792, 2014.
Elad Hazan and Yuanzhi Li. An optimal algorithm for bandit convex optimization. arXiv:1603.04330 2016.
Elad Hazan and Edgar Minasyan. Faster projection-free online learning. In 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. Machine Learning, 69(2):169 192, 2007.
Amélie Héliou, Panayotis Mertikopoulos, and Zhengyuan Zhou. Gradient-free online learning in games with delayed rewards. Proceedings of the 37th International Conference on Machine Learning, pages 4172-4181, 2020.
Shinji Ito. An optimal algorithm for bandit convex optimization with strongly-convex and smooth loss. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, pages 2229-22333 2020.
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-tolerant online convex optimization: Unified analysis and adaptive-gradien algorithms. Proceedings of the 30th AAAI Conference on Artificial Intelligence, pages 1744-1750, 2016.
John Langford, Alexander J. Smola, and Martin Zinkevich. Slow learners are fast. In Advances in Neural Information Processing Systems 22, pages 2331-2339, 2009.
Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathematical Statistics and Learning. 2(3/4):311-333 2020.
Tor Lattimore. Bandit convex optimisation. arXiv:2402.06553 2024.
12

---

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 Statisties, pages 993-1002, 2019.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. In Advances in Neural Information Processing Systems 36, pages 53038-53075, 2023.
H. Brendan McMahan and Matthew Streeter. Delay-tolerant algorithms for asynchronous distributed online learning. In Advances in Neural Information Processing Systems 27, pages 2915-2923 2014.
H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young. Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg, Arnar Mar Hrafnkelsson, Tom Boulos, and Jeremy Kubica. Ad click prediction: A view from the trenches. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1222-12322 1230, 2013.
Arkadi Nemirovski. Interior point polynomial time methods convex programming, Lecture notes, Technion - Israel Institute of Technology, 2004.
Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. In Advances in Neural Information Processing Systems 28, pages 1270-1278, 2015.
Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pages 636-642, 2011.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Ohad Shamir. On the complexity of bandit and Verivative-free stochastic convex optimization. In Proceedings of the 26th Conference on Learning Theory, pages 3-24, 2013.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Y. Jennifer Sun, Stephen Newman, and Elad Hazan. Optimal rates for bandit nonstochastic control.
In Advances Neural Information Processing Systems 36, pages 21908-21919, 2023.
Dirk van der Hoeven, Ashok Cutkosky, and Haipeng Luo. Comparator-adaptive convex bandits. In Advances in Neural Information Processing Systems 33, pages 19795-19804, 2020.
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Projection-free 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, 1113))871-893, 2022a.
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Online Folle with arbitrary delays. In Advances in Neural Information Processing Systems 35, pages 19703-19715, 2022b.
Yuanyu Wan, Guanghui Wang, Wei-Wei Tu, and Lijun Zhang. Projection-fiee distributed online learning with sublinear communication complexity. Journal of Machine Learning Research, 23 (172):1-53, 2022c.
Yuanyu Wan, Yibo Wang, Chang Yao, Wei- Wei Tu, and Lijun Zhang. Projection-free free online learning with arbitrary delays. NBV::2204404464412 2023.
Yuanyu Wan, Chang Yao, Mingli Song, and Lijun Zhang. Non-stationary online convex optimization with arbitrary delays. Proceedings of the 4 International Conference on Machine Learning, pages 49991-50011, 2024.
13

---

Yibo Wang, Yuanyu Wan, Shimao Zhang, and Lijun Zhang, Distributed projection-free free online learning for smooth and convex losses. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages 10226-10234, 2023.
Yibo Wang, Sijia Chen, Wei Jiang, Wenhao Yang, Yuanyu Wan, and Lijun Zhang. Online composite optimization between stochastic and adversarial environments. Advances in Neural Information Processing Systems 37, 2024a.
Yibo Wang, Wenhao Yang. Wei Jiang, Shiyin Lu, Bing Wang, Haihong Tang, Yuanyu Wan, and Lijun Zhang. Non-stationary projection-free online learning with dynamic and adaptive regret guarantees. In Proceedings of the 38th AAAI Conference Artificial Intelligence, pages 15671-15679, 2024b.
Marcelo J. Weinberger and Erik Ordentlich. On delayed prediction of individual sequences. IEEE Transactions on Information Theory, (177)11999-19760 2002.
Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization: From full-information bandit feedback. In Advances Neural Information Processing Systems 32, pages 9210-9221, 2019.
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin- Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong. Zhangyang Wang, Sijia Liu, and Tianlong Chen. Revisiting zeroth-order optimization for memory-effiiiet LLM fine-tuning: A benchmark. In Proceedings of the 41st International Conference on Machine Learning, pages 59173-59190, 2024.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-936, 2003.
14

---

A Detailed discussions on future work
First, notice that all our regret bounds depend on the maximum delay, and thus it is natural to investigate whether these bounds can be further improved to be depending on the average delay. It seems highly non-trivial to obtain such results with our D-FTBL because the blocking update mechanism actually enlarges each delay to be at least the block size.
Second, it is appealing apply algorithm to emerging mask-memory-efiicee large language models [Malladi et al., 2023, Zhang et al., 2024]. The key insight is that our algorithm only requires the delayed loss value to update the model, and thus could achieve an asynchronous acceleration while avoiding memory costs of the backpropagation.
fine-tuning of
Moreover, in the above task, we actually only need to handle sequence of stochastic loss functions. Note that Agarwal and Duchi [2011] have shown that the delay only increases the regret of OCO with stochastic and smooth loss functions in an additive way, i.e, an O(VT d²) regret bound. Thus, it is interesting to investigate whether the stochastic setting or an intermediate setting [Chen et al., 2024, Wang et al., 2024a] can make delayed BCO easier in a similar way.
Finally, it is also worth extending other BCO algorithms into the delayed setting, e.g., generalizing the algorithm of Saha and Tewari [2011] improve the regret for smooth functions. However, more complicated analysis is required because they utilize additional techniques, e.g., the self-concordant barrier [Nemirovski, 2004].
B Proof of Lemma 2
Recall the definition of and x* in the proof of Theorem First, is easy to verify that
T/K
mk
Reg(T) =
Σ
Σ
(Jely + tuu)) fe(x"))
m
1JK+1
T/K
5
Σ
Σ
felym) + f((xx)))++++))))))))) -
x*
(20)
r
t= (m 1)K+1
T/K
mK
8GRT
$ Σ
Σ
- 8GT +
- IJK+1
where the first inequality is due to Assumption 2, and the second inequality is due to Assumption and Algorithm are computed according to approximate gradients
u, ~ S Note that of the d-smoothed version of original functions, i.e., (x) Eu-5= [fr(x + ōu)], Vt [7]. Therefore, before utilizing the unbiasedness of these approximate gradients in Lemma 1, we introduce the following lemma regarding the connection between the original function and its 5-smoothed version over K. defined in (3).
Lemma 7. (Lemma 2.6 in Hazan (2016)) Let fxx :
R" + R be o-strongly convex and G- G-Lipschitz set IC satisfying Assumption Its 8-smoothed version fs(x) defined in (2) has the following properties:
fo(x) a-stroogly convex over Ks;
fa(x) f(x) & 8G for any x E Kg;;
fa(x) is G-Lipschitz over K.a-
Combining (20) with the second property in Lemma 7, it is easy to verify that
T/K
mK
(fro(y)))- fx,((*) +25)) 5GT 8GRT
Reg(T) S
Σ
Σ
(21)
(1 11K+1
Then, combining (21) with the first property in Lemma where a 0, we have
T/K
mK
(Viasyym) - -x*) + 35GT + 8GRT
Reg(T) <
Σ
Σ
m= t= (m 1)K+1
15

---

From the above inequality, it is easy to verify that
T/K
mK
+ym Ym ym) + 38GT 8GRT
(Tg(T) -
Σ
Σ
(V X
t= mm 1)K+1
T/K
mK
T/K
11 y la + 38GT + 8GRT
Σ
(V...(y))) - -x" + KG
Σ
1)
m=1
(22)
where the last inequality is due the last property in Lemma 7.
Moreover, according to Lemma 1, we have
mk
mk
Σ
(iss(sm)... x*) = Σ
fe + &u,)u,, - x*)
1n-1))+1
(= 1)K+1
-B (V ym xx)]
Finally, complete this proof by first taking expectations of both sides in (22) and then substituting the above equality into the right side.
C Proof of Lemmas and
Lemma 5 can be proved by simply following the proof of Lemma 5 in Garber and Kretzu [2020]. In the following, we first prove Lemma 6, and then include simple proof of Lemma 5 for completeness.
For brevity, let g: (x,e(x))ur ), for any E [T]. Since gi. 8(m 1))- must be available at the end of round (m 1) it is not hard to verify that
m
m-1
g+
Σ
g
+1
Σ
Σ g+
(23)
k=m
1d/ K
A
k=m [d/K]
rEAx
where A {(k 1)K + 1...., kK] lmm.
Because of Ada < K, for any k = m - 1 - [[d/K] [d.,]....,. 1, we have
E
Σ ge
=E
Σ
ge
112 +
Σ
(gi gr)
rEAt
tEAR
A. (
S|Ab
nM
2
E
Σ
E|g,)yx))
8
i.jEAL,775
(24)
nM
2
<K
E
Σ
112 [ygll
8
n.M
ndld 5
<K
+ ([AA2 |ARI) S
K
+
K²
8
where the first inequality is due to Assumption 3, and the third inequality is due to Assumption 2, Lemma 1, and the last property in Lemma 7.
Combining (23) with (24), we have
d K2
nM
Σ
g
2
+4
K
12
which completes the proof of Lemma 6.
16

---

Additionally, let Tm
{(m - 1)K + 1.............. mk) Following (24), it is easy to verify that
nMM
E
V
E
gr
Σ
8i)
K
(25)
iJETm.itj
which completes the proof of Lemma
D Proof of Theorem 2
This proof is similar to that of Theorem 1, but requires some specific extensions to utilize the strong convexity. Note that by combining (21) in the proof of Lemma with the strong convexity, we have
T/K
Reg( Σ
Σ
(V (V). x*) fllm x111) 35GT
8GRT
(26)
r
TETm
where Tm = {(m - 1)K + 1,.... mk) x= =
5/r)x", and x E argmin XEI E Jx(x).
Moreover, by reorganizing (26) and inserting the ideal action y we have
Reg(T) (38GT + 8GRT
T/K
(V.e.o(Mm). - xx)) + (Vfos(ym).m - ym) a ll - xx112) (27)
m= Tm
T/K
TýK KG Ym112
Σ (V - x*) a lly x
+
m= TET
m==1
where the last equality is due to Assumption 2 and the last property in Lemma 7.
For brevity, we define surrogate losses as lm (x) (V m, x) + ak flym x12 for m [T/K], and notice that
Ym+1 = argmin
(x))
(28)
xEK,
in the strongly convex case, Then, is not hard verify that
T/K
E
Σ
Σ
(VVessyym): x2) 2 ym x=1
TET
T/K
Σ
Σ
(( + ouy)u,. yn x²) ym xx xx112
m=1
T/K
aK llym -x1113
=E
Σ
m. ym++ x² y vm
(29)
T/K
T/K
<B
(Lm (ym+1)= -m (x+)))
+E
V mmllllly'
-mmtall
m=1
m=1
T/K
<E
Σ
Velly
-ym+ill2
m=
where the first equality is due to Lemma 1, and the last inequality is due to (28) and Lemma 3. From (27) and (29), we still need to bound ||ym yi lla and l|y -ym+ill2
'Note that the definition of yin in (5) for strongly convex functions is only valid for 2 2. For m = 1. we simply set of y1-
17

---

To this end, we notice that ym for any m = / K is equal to
m=1
a(m 1)
y argmin xEk
Σ V. aKy.), x
x x
(30)
2
Similarly, for any m ,,, T/K, the action Ym of Algorithm with 0 equal to
8(m-1) ((E
{(
aky,, + a(m 1)K
Ym argmin xcKg
Σ
x
2
(31)
2
i=1
Combining (30) and (31) with Lemma 4, for any m = ,,..., T/K, we have
llym ymul2 - a(m - 1)K
1
gim 1)K
m-
1
Σ
n
f(()))
(32)
a(m 1)K
rEMm
where Um is defined in (18).
Moreover, from (1), for any m = 2....
T/K, we have
ly Ym+1ll 113
2
Σ (ely)) - Σ Elym++))
m
amk
amk (em() - lm em(yy++) (ym+1))
2
((Vm + aK(y". - ymm.. vm+1))
amK
2
a(m 1)K (1IV ll2 2aK lly vm+ill2
where the first inequality due to the definition of y and the last inequality is due to Assumption 1. The above inequality further implies that
2
Ily ym+ill2 S a(m 1)K
Vl 2 + 2aK
(33)
Combining (27), (29), (32), and (33), we have
T/K
T/K Σ m=l
[lly - ymallll + 35GT + 8GRT
E [Rgg(T)
<
V
mmlllllym - y vmtilla
KGE
m==1
T/K (II m 1 + 2aK 1l)
V Illlly1 - v
a(m 1)K
m==
T/K
G
n Σ
f((x))
+ 35GT +
8GRT
a
m=
Combining the above inequality with Assumption Lemma Lemma 6, and y K (and) +K? it is easy to verify that
T/K
2n
G
de
+ 38GT + 8GRT
E Reg(T)) S2R
+
+
4R
2
K2 +4 +4)7)
1
aK
2
27
G
K2 +44 +4))))
d2
+ 35GT + 8GRT
<2R (1+ITT)
4R
a 1
aK
r
24Cr aK
GCT
d
+ 35GT + SGRT
+ CCR
2
K?
+4)
?
where =7= 1
In and C 6 4nn..
18

---

E Proof of Theorem 3
The main idea of this proof is to combine the proof of Theorem 2 with an improved property of the 5-smoothed version of smooth functions [Agarwal et al., 2010].
Specifically, for any E
[T] and x, according to the smoothness of functions, we have
fx,(()) & Ru [1((x) + (VI((x) 6u)
38 ||
= f(()) + 382
(34)
2
where f(,(()) = Bu-B- [f 5u)] and the last equality is due to BuwB" [u] = 0.
Moreover, due to the convexity of functions, for any t [T] and have
(x) 2 Bu-B" (x((x) (V (x), ou)] fx(x).
(35)
Then, let x" = argmin XER= Dt= fx(x) and x* = (1 - 6/r)x", where r 2G/a. According to (10), we have x* E K' and X E Kg where K' and K2, are defined in (11) and (12), respectively. By further defining Tm = {(m 1)K + 1,...,mK] m,K], J. it is not hard to verify that
T/K Σ
E [T)
=E
Σ
(fely + tuu) -
TET
T/K
36 mu
<
Σ
Σ
f((y))+ (VSe(ym), (VS(x)))
TET
T/K
Σ Σ -fi(()) + (Tr((x)), 5x
3882 |
E
(36)
m=lteTm
T/K
952
882C)
=E
f f((x)) +
2
m= TE
T/K
+ +.8TT + 38
<
Σ
Σ
(fr((r)) - f
m= TE....
where the first inequality is due to the smoothness of functions, and the last incquality due (34) and (35).
Then, follow the definition of yt in (28), but replace Kcs utilized in (28) with Kg Combining (36) with the strong convexity of functions, we have
B88T + GT
E Reg((T))
a
T/K Σ
<
(Voro(rm)) -xx) x²)- -lym x313)
TET
TyK
(37)
(ViLo(y)))n -x²) (V).s(y))) vm -ym) lly -x111)
=
mm
T/K
T/K
<B
Σ
Σ
(ViLs(rm))M -x) 0 -lym -
x2113)
+E
Σ m=1
KG -Yillz
M=
where we simply set y = Yı. and the last inequality is due Assumption and the last property in Lemma 7.
19

---

Let R = 2G/a denote the radius of K' It is not hard to verify that (29), (32), and (33) in the proof of Theorem 2 still hold here. Therefore, have
GT
E [Reg(T)]
38
T/K K
T/K KGllym -ymllz
Amll2lly sm+ill2 + E
T/K Σ
2 (II m 113 2a
(38)
E Villelly v2l12]
a(m 1)K
m=2
T/K
Σ
E
Σ IE
n2
5
a(m
m=2
where the first inequality is due to (37) and (29), and the last one is due to (32) and (33).
Finally, combining (38) with Lemma 5, Lemma 6, and 7 = K
PM 0
K2G2, we have
E [Re((T) 5
T/K Σ
27 4R
+
G
2
K2 + 4 1)
d2
+.88T GT
m
aK
a
a
+ (1+h7)
27
44R
+ a
K2 + 4 11)
+ 35355
G8
aK
2TC
GC,
GCT
d²
382T + GT
12
+4 7
aK
K2
a
where the last equality is due to 2G/a, Cr 1 + In and Cf + 4ln
A refined regret bound for Bistritz et al. [2022]
From Theorem 4 of Bistritz et al. [2022], their algorithm can achieve the following regret bound
[[Reg(T)) 0 (
(ST
m
2 82
1
nndT
(39)
17
for BCO with delayed feedback, where 5 >>0 0 and > denote the exploration radius and the step size, respectively. Then, by further substituting
8 = max [T-1/4 1/4 T 1/333//3// and min f2 11--133/4 3/4
21/2
into (39), Bistritz al. [2022] have established the OnT33/1 /nd we notice that
regret bound. However,
O 0
Tm²²T 52
andl
n2T 52
ndT
min 8>0.0
+
+
min O
8T +
+
(40)
17
8>0
8
where the equality holds with
2T
ndT
112
(41)
82
8
From (40), if n288-2 2 ndd88-
have
o ( 8T
nm 2T andl
nVT
= =0 =0
(VVTT3/A)
min 5>0,1>
min O
8T +
(42)
82
8
820
8
where the last equality holds with 8 /nT
1/4
20

---

Otherwise, combining (40) with n²T6- 2 ndTo-1
we have
min O ( 6>0,1/0
T 82
nndT
ndT
= =0 ((nd)
min O 820
8T +
(43)
6
8
where the last equality holds with ö (nd) (nd))/877-13,
Combining (39) with (41), (42), and (43), we can improve the regret bound of Bistritz et al. [2022] to
E (Reg(T)) = o (VrIT/4 + (nd) 1//22/3
(44)
by setting and 17 as
8 max { (vTT-V/ 1/4, (nd)1137-1/3) and 1) min {" {n- 1n-1/22-3// 3/4 (nd))1133p 1/33-2133
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction have clearly stated the contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Appendix A, the authors discuss one limitation of the results, and introduce a related open problem.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: The assumptions of any theoretical result are clearly introduced in Section 3.3. The proofs for all theoretical results can be found in Section 3.4 and the appendix. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The setup of our experiments is clearly introduced in Section 4, which is sufficient for reproducing our experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
Any interested people can send the authors an email to query the source code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nwpp..cc////////o https/ccppblcccguiedeeeooo Stup:puiiiiguuuieeeeeottttutaaia
/Cooeeuboeeeeeeeeee sestsubmmsssiooio swwiissssnnoooiiieoee onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The setup of our experiments is clearly introduced in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We have each algorithm 20 times, and reported the average result in Section 4. The standard deviation is omitted because we believe that it does not affect the comparison between algorithm and baselines.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: As mentioned in Section 4, all algorithms are tested on a laptop with 2.4GHz CPU and 16GB memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The authors conducted the research in this paper by strictly conforming to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mostly theoretical and the societal impacts discussion is applicable.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is mostly theoretical and poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: In Section have indicated that data sets selected from the LIBSVM repository [Chang and Lin, 2011].
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "SfdG1pvCLm", "reviewer": "Reviewer_vCin", "summary": "The authors consider the problem of bandit convex optimization in the adversarial setting under delays. In each round, an adversary selects a convex function $f_t$, the optimizer selects an input $x_t$ and observes $f_t(x_t)$ with a delay of $d_t$ timesteps. The goal is to minimize regret with respect to the best action in hindsight.\n\nWithout any delay, the best regret is obtained by the zeroth order one-point flaxman updates. Prior work in the delayed setting adapts this algorithm to use the oldest available feedback to make the update. However, the observation that the authors make is that according to this scheme, information might become available much before it is used -- if there is older information that has not been used yet.\n\nSo instead, to minimize the gap between availability and utilization of information, the authors propose a blocking algorithm. Where at the end of each block, all available information so far is used to make the update. This enables them to get improved regret bounds.", "questions": "1. Could the authors comment on what the problem looks like for the regular stochastic case with all $f_t = f$ for some fixed $f$, and how this might make the problem easier under delays?\n2. Why do the authors conjecture that the lower bound depends on $\\bar{d}$, whereas the upper bound depends on $d$? What improvements would be required to get these to match?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is very well-written with the results laid out very clearly, and the rationale for the solution explained well.\n2. The solution to use blocking in order to minimize stale information is creative, and leads to better bounds.\n3. The results are comprehensive across different classes of objectives, and the authors thus show the wide applicability of the technique.", "weaknesses": "**Significance** The practical impact of this theoretical toy seems limited, and the problem was of more interest a couple of years ago. In order to increase the reception, it would be instructive to connect the implications of these findings to other topics of recent interest or include some simulations", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews! \n\n---\nQ1: The practical impact of this theoretical toy seems limited, and the problem was of more interest a couple of years ago. In order to increase the reception, it would be instructive to connect the implications of these findings to other topics of recent interest or include some simulations\n\nA1: Thanks for the suggestion. Please check our **common response to the suggestion about experiments**, which introduces numerical results completed during the rebuttal period, and has shown the advantage of our algorithm in practice. Moreover, it is also worth noting that our algorithm has a potential application in memory-efficient fine-tuning of large language models (LLM). Very recent studies [1,2] have utilized zero-order optimization algorithms to reduce the memory required by fine-tuning LLM. Our algorithm may be utilized to further achieve the asynchronous update, because of its ability to deal with delayed feedback. We will provide more discussions about our potential applications in the revised version.\n\n[1] Y. Zhang et al. Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark. In ICML, 2024.\n\n[2] S. Malladi et al. Fine-Tuning Language Models with Just Forward Passes. In NeurIPS, pages 53038–53075, 2023.\n\n---\nQ2: Could the authors comment on what the problem looks like for the regular stochastic case with all $f_t=f$ for some fixed $f$, and how this might make the problem easier under delays?\n\nA2: We notice that the stochastic case of delayed online convex optimization (OCO) has been investigated in the pioneering work of Agarwal and Duchi [3], which is referred to as distributed or parallel stochastic optimization with asynchronous update. Therefore, the stochastic case of delayed bandit convex optimization (BCO) reduces to a zero-order variant of this asynchronous optimization problem. Moreover, as discussed in Agarwal and Duchi [3], the stochastic case itself is not sufficient to make the delayed problem easier. Actually, the smoothness assumption on the loss functions is also required. \n\nMore specifically, Agarwal and Duchi [3] show that in the stochastic case, the delay only increases the regret of delayed OCO for convex and smooth functions in an additive way, i.e., an $O(\\sqrt{T}+d^2)$ regret bound. The key insight for this improvement is that the perturbed error of the delayed stochastic gradients can be much smaller under the smoothness assumption. Therefore, it is natural to conjecture that the stochastic case will make delayed BCO for convex and smooth functions easier in a similar way. We will provide detailed discussions about the stochastic case in the revised version. \n\n[3] A. Agarwal and J. Duchi. Distributed Delayed Stochastic Optimization. In NIPS, pages 873–881, 2011.\n\n---\nQ3: Why do the authors conjecture that the lower bound depends on $\\bar{d}$, whereas the upper bound depends on $d$? What improvements would be required to get these to match?\n\nA3: Our conjecture of the dependence on $\\bar{d}$ stems from the existing $\\Omega(\\sqrt{\\bar{d}T})$ lower bound [Bistritz et al., 2022] for delayed BCO. However, as discussed in our paper, it is hard for our algorithm to achieve regret bounds depending on $\\bar{d}$ due to the blocking update mechanism. Nonetheless, we want to emphasize that our regret bounds achieved via the blocking update mechanism are already quite favorable, and it is highly non-trivial to develop a better algorithm, especially in the case with strongly convex functions. Note that even in the easier full-information setting, previous studies can only achieve the $O(d\\log T)$ regret for strongly convex functions, which is the same as the delay-dependent part in our regret bounds for strongly convex functions.", "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": "", "extra_scores": {}}, {"review_id": "exvE4F8y3d", "reviewer": "Reviewer_S7rX", "summary": "This paper studies the bandit convex optimization problem with delayed feedback, where the loss value of the selected action is revealed under an arbitrary delay. \n\nPrevious work achieves $\\mathcal{O}( \\sqrt{n} T^{3/4} + (n\\bar{d})^{1/3} T^{2/3})$ regret bound of this problem. The authors develop a novel algorithm and show that it improves the delay-related part to $\\mathcal{O}( sqrt{dT})$ when $d$ the maximum delay, is close to $\\bar{d}$, the average delay (specifically, strictly better when d = $\\mathcal{O}( (n\\bar{d})^{2/3} T^{1/3}  )$. The authors claim that the primary idea is to decouple the joint effect of the delays by incorporating the delayed bandit feedback with a blocking update mechanism, which reduces the correlation between recent delayed updates (otherwise there could be a $d^2$ term).", "questions": "The questions are raised in the weakness section. I am willing to re-evaluate the scores if these questions are properly answered.", "limitations": "This paper is pure theoretical and does not have any limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Though I have skimmed the proof of several lemmas, the analysis part seems to be rigorous and mathematically correct. \n2. The usage of blocking update mechanism is very interesting, and could be applied in other similar settings.", "weaknesses": "1. The contribution of this work is quite concerning. It would be better for the authors to emphasis the contribution (either algorithmic or analytic) on improving the delayed feedback result for BCO problem in certain conditions that the max delay $d$ is close to $\\bar{d}$? Some parts of the proof are rather straightforward and standard.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews!\n\n---\nQ: The contribution of this work is quite concerning. It would be better for the authors to emphasis the contribution (either algorithmic or analytic) on improving the delayed feedback result for BCO problem in certain conditions that the max delay $d$ is close to $\\bar{d}$? Some parts of the proof are rather straightforward and standard.\n\nA: Thank you for the helpful suggestion. Our technical contributions can be summarized as follows.\n1) At the algorithmic level, our paper is the first work that exploits the blocking update mechanism to design improved algorithms for delayed BCO. Moreover, unlike existing algorithms [Héliou et al., 2020; Bistritz et al., 2022] based on online gradient descent, our algorithm is based on follow-the-regularized-leader (FTRL). As discussed in lines 228 to 235 of our paper, in this way, we can utilize the delayed information more elegantly.\n2) At the analytic level, we derive the first regret bound that can decouple the joint effect of the delays and the bandit feedback. To this end, besides some standard analysis for FTRL and BCO, we need to carefully analyze the delay effect under blocking update to establish an improved upper bound for $\\\\|\\mathbf{y}_m-\\mathbf{y}_m^\\ast\\\\|_2$, where $\\mathbf{y}_m $ is the preparatory action of our Algorithm 1 and $\\mathbf{y}_m^\\ast$ is an ideal action defined in line 305 of our paper.\n3) Moreover, different from previous studies [Héliou et al., 2020; Bistritz et al., 2022] that only consider convex functions, our paper further investigates two special cases with strongly convex functions, and achieves better regret bounds.", "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": "", "extra_scores": {}}, {"review_id": "fnxELBIZAY", "reviewer": "Reviewer_pbhB", "summary": "This paper studies the problem of bandit convex optimization with delayed feedback (where the feedback for round $t$ is delayed by an arbitrary number of rounds $d_t$).\nFor this problem, they show $O(\\sqrt{n} T^{3/4} + \\sqrt{d T})$ regret in general, $O((n T)^{2/3} \\log^{1/3} (T) + d \\log(T))$ regret for strongly-convex functions, and $O(n \\sqrt{T \\log(T)} + d \\log(T))$ regret for smooth and strongly-convex functions in an unconstrained settting.\nIn these bounds, $n$ is the dimension, $T$ is the horizon and $d$ is the maximum delay.", "questions": "No questions at this point.", "limitations": "There is some discussion of the limitation due to the fact that the regret is given in terms of maximum delay rather than average delay.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Their results for the general setting strictly improve on results that use the maximum delay $d$ (Heliou et al (2020)), and supplement results that use the average delay $\\bar{d}$ (Bistritz et al 2022).\n- They give improved regret for specific settings.\n- The literature review is very thorough and the authors are diligent in pointing to the origin of ideas throughout the paper.\n- There is extensive discussion on the difference in techniques with respect to existing approaches and how their approach result in tighter regret gaurantees.\n- The presentation is clear and intuitive.", "weaknesses": "- The paper only makes an improvement on state-of-the-art for certain delay sequences, i.e. when $d = O((n\\bar{d})^{2/3} T^{1/3})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews!\n\n---\nQ: The paper only makes an improvement on state-of-the-art for certain delay sequences, i.e. when $d=O((n\\bar{d})^{2/3}T^{1/3})$.\n\nA: First, we want to emphasize that both $n$ and $T$ can be very large in modern online applications, and thus the condition $d=O((n\\bar{d})^{2/3}T^{1/3})$ can be satisfied by many delay sequences including those with $\\bar{d}=1$. Second, it is also worth noting that besides convex functions considered in previous studies [Héliou et al., 2020; Bistritz et al., 2022], our paper further investigates two special cases with strongly convex functions, and achieves $O((nT)^{2/3}\\log^{1/3}T+d\\log T)$ and $O(n\\sqrt{T\\log T}+d\\log T)$ regret bounds, respectively. These two bounds are better than the state-of-the-art result for a larger portion of delay sequences.", "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": "", "extra_scores": {}}, {"review_id": "9xYKqfBnDg", "reviewer": "Reviewer_knrh", "summary": "The paper investigates the problem of bandit convex optimization (BCO) with delayed feedback, where the value of the action is revealed after some delay. The authors proposed an algorithm D-FTBL, and proved that it enjoys a regret bound of $O\\left(\\sqrt{n} T^{3/4}+\\sqrt{d T}\\right)$, closing the gap between the previous result and the lower bound on delay-dependent part. Furthermore, the proposed algorithm can improve the regret bound to $O\\left((n T)^{2 / 3} \\log ^{1 / 3} T+d \\log T\\right)$ for strongly convex functions, and if the action sets are unconstrained, the proposed algorithm can achieve an $O(n \\sqrt{T \\log T}+d \\log T)$ regret bound for strongly convex and smooth functions.", "questions": "I would be curious about how much improvement can be made in practice. In bandit setting, people often consider large time horizon, in which cases the regret is dominated by the delay-independent term.", "limitations": "The authors addressed the limitations and consider it as future work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The writing style of the article is excellent, and the overall flow is very smooth and enjoyable to follow. \n- The literature review is thorough and well-integrated into the paper. It provides a solid foundation for the research by situating it within the existing literature of BCO and highlighting the gaps that the authors aim to fill.\n- The methodology seems innovative. The application of blocking update mechanism not only adds substantial value to the current study but also potentially inspires other problems with delayed feedback.\n-  The theoretical results presented in the paper are logically sound and well-supported. Each point is substantiated with adequate evidence, avoiding any logical leaps or inconsistencies.", "weaknesses": "The paper lacks numerical experiments. Besides this, I did not spot any significant weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews! \n\n---\nQ: The paper lacks numerical experiments ... I would be curious about how much improvement can be made in practice. In bandit setting, people often consider large time horizon, in which cases the regret is dominated by the delay-independent term.\n\nA: Please check our **common response to the suggestion about experiments**, which introduces numerical results completed during the rebuttal period, and has shown the advantage of our algorithm in practice. Moreover, we want to emphasize that although $T$ could be very large, the delay-dependent term in the existing $O(\\sqrt{n}T^{3/4}+(n\\bar{d})^{1/3}T^{2/3})$ regret bound [Bistritz et al., 2022] cannot be ignored. Specifically, this regret bound is dominated by the delay-independent term only for $\\bar{d}=O(n^{1/2}T^{1/4})$. However, this condition can be easily violated due to the sublinear dependence on $T$ and $n$, and the fact that the delay may also increase for larger $T$. For example, our experiment on ijcnn1 has $T=40000$ and $n=22$, and thus the condition is violated as long as $\\bar{d}>n^{1/2}T^{1/4}\\approx 67$. Even if we consider a much larger $T=400000000$, $\\bar{d}>664$ is sufficient to violate the condition. By contrast, our $O(\\sqrt{n}T^{3/4}+\\sqrt{dT})$ regret bound is dominated by the delay-independent term for a larger amount of delays, i.e., $d=O(n\\sqrt{T})$.", "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": "", "extra_scores": {}}, {"review_id": "N11u2MlAe6", "reviewer": "Reviewer_GZvs", "summary": "The paper investigates the online convex optimization problem with delayed bandit feedback.\n\nThe main contribution is introducing a new algorithm that uses a block updating mechanism with FTRL, proving the algorithm achieves a delay-dependent regret of $O(\\sqrt{dT})$, which is known to be optimal when the average delay is close to the maximal delay: $\\bar{d} \\approx d$.", "questions": "Can you explain each term in the theorems and where does it come from? As is, the theorems are packed with different terms and besides substituting the optimal values I don't know how to interpret them", "limitations": "The authors properly acknowledge the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The paper shows a valuable algorithm that improves on the known regret bounds for the delayed BCO.\n* The techniques used, specifically block updates, while not novel, are original for this kind of problem.", "weaknesses": "* The paper could be written more clearly. I found myself understanding parts of the introduction only after going through the entire paper (e.g. line 69). \n* The proofs are hard to follow. Some explanations before each lemma to understand how those are used would be helpful.\n* It seems hard to use the blocking updates to further improve the regret, so the value of the presented algorithm could be temporary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive reviews!\n\n---\nQ1: The paper could be written more clearly. I found myself understanding parts of the introduction only after going through the entire paper (e.g. line 69).\n\nA1: Thank you for the helpful suggestion. We will improve our writing by adding necessary explanations to help the understanding.\n\n---\nQ2: The proofs are hard to follow. Some explanations before each lemma to understand how those are used would be helpful.\n\nA2: As you suggested, we will explain the usefulness of each lemma in our analysis. Moreover, we will start each proof by providing a high-level overview of the upcoming procedures.\n\n---\nQ3: It seems hard to use the blocking updates to further improve the regret, so the value of the presented algorithm could be temporary.\n\nA3: We agree that the blocking update mechanism may prevent our algorithm from further improving regret bounds to be depending on the average delay. However, we want to emphasize that our regret bounds achieved via the blocking update mechanism are already quite favorable,  and it is highly non-trivial to develop a better algorithm, especially in the case with strongly convex functions. Note that even in the easier full-information setting, previous studies can only achieve the $O(d\\log T)$ regret for strongly convex functions, which is the same as the delay-dependent part in our regret bounds for strongly convex functions. \n\n---\nQ4: Can you explain each term in the theorems and where does it come from? As is, the theorems are packed with different terms and besides substituting the optimal values I don't know how to interpret them\n\nA4: We first provide the following explanations for each term in our Theorem 1.\n1) The first two terms $\\frac{4R^2}{\\eta}+\\frac{\\eta T\\gamma}{2K}$ are an upper bound on the expected regret of an ideal action for each block, i.e., $\\mathbf{y}_m^\\ast$ defined in line 305 of our paper. Therefore, they are affected by the step size $\\eta$, the block size $K$, and the variance of cumulative gradients in each block $\\gamma$. Moreover, the variance $\\gamma$ depends on both the block size $K$ and the exploration radius $\\delta$ at first glance, but we can select an appropriate $K$ to remove the extra dependence on $\\delta$ as discussed in our paper.\n2) The third term $\\frac{\\eta TG}{2}\\sqrt{2\\left(\\frac{d^2}{K^2}+4\\right)\\gamma}$ is an upper bound on the expected cumulative distance between the preparatory action $\\mathbf{y}_m$ of our Algorithm 1 and the ideal one $\\mathbf{y}_m^\\ast$, which is further affected by the maximum delay $d$. \n3) The last two terms $3\\delta GT+\\frac{\\delta GRT}{r}$ are caused by the error of the shrunk set $\\\\mathcal{K}\\_\\\\delta$ and the $\\delta$-smoothed function $\\hat{f}_{t,\\delta}(\\cdot)$, and thus are affected by the exploration radius $\\delta$. \n\nAdditionally, we note that the terms in our Theorems 2 and 3 can be similarly divided into these three categories. In the revised version, we will provide detailed explanations for each term in all our theorems.", "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": "", "extra_scores": {}}]

Author rebuttal:
## Common Response to the Suggestion about Experiments

We thank all the reviewers for your detailed comments. In the following, we first respond to the common suggestion about experiments, and other questions are addressed in a separate response for every reviewer. Please let us know if you have any further questions.

During the rebuttal period, we conducted experiments on two publicly available data sets—ijcnn1 and SUSY from the LIBSVM repository [1]. Specifically, we randomly select $T=40000$ examples from the original data sets. The dimensionality of ijcnn1 and SUSY are $n=22$ and $n=18$, respectively. Moreover, we consider online binary classification over a convex set $\mathcal{K}=\\{\\|\mathbf{x}\\|_2\\leq 50\\}$. In each round $t\in[T]$, the adversary chooses the hinge loss $f_t(\mathbf{x})=\\max\\{1-y_t\\mathbf{w}_t^\\top\\mathbf{x},0\\}$, where $\mathbf{w}_t$ and $y_t\in\\{-1,1\\}$ are the feature vector and class label of the $t$-th example, respectively. 

Different values of the maximum delay $d$ in the set $\\{200, 600,1000,\dots, 5000\\}$ have been tried in experiments on both data sets. For each specific $d$, to simulate arbitrary delays, $d_t$ is independently and uniformly sampled from $[1, d]$. Note that, in this way, the average delay satisfies $\mathbb{E}[\bar{d}]=\frac{d+1}{2}$, and thus is close to the maximum delay $d$. We compare our D-FTBL against GOLD [Héliou et al., 2020] and improved GOLD [Bistritz et al., 2022]. Due to the randomness of these algorithms, we repeat them 20 times and report the average of their total loss. 

Figure 1 in the attached PDF shows the numerical results, and we have the following main observations.
1) For our D-FTBL, when $d$ increases from $200$ to $5000$, the growth of the total loss is very slow, which is consistent with the dependence of our regret bound on $d$. Note that $d=5000$ is larger than $n\sqrt{T}$ in our experiments.
2) From $d=600$ to $d=5000$, the total loss of our D-FTBL is better than both GOLD and improved GOLD, which verifies the advantage of our algorithm in the delayed setting.
3) Although for $d=200$, D-FTBL is slightly worse than baselines, it is reasonable because the block update mechanism enlarges each delay to be at least the block size, which could result in a slightly larger constant factor in the regret.

[1] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(27):1–27, 2011.

Meta-review: This work studies the BCO problem with delayed feedback and presents a novel FTRL algorithm that uses a blocking update mechanism to decouple the effect of the delayed feedback on the regret of the algorithm. Most reviewers find the papers presentation to be very good, that the proofs are sound and that the authors have done a good job with literature review and comparison to prior work. Most reviewers also find the blocking update idea to be novel and interesting and point out that it could have application in other problems. One reviewer has suggested that the authors include an empirical evaluation of their algorithm which the authors do in the rebuttal. The only raised concern during the discussion phase is that of how impactful the algorithm or technical contribution of this paper are, given that the analysis builds on the standard FTRL framework. I find that the blocking update is interesting enough by itself, as other reviewers have also pointed out, and that the technical contributions are good enough for NeurIPS. As such I would recommend this paper for acceptance. I encourage the authors to incorporate the empirical evaluation in the final version of the paper.
Decision: Accept (poster)