Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Authors: Hao Qiu
Emmanuel Esposito
Mengxiao Zhang
Venue: ICML 2025 poster (2025)
Keywords: online learning
delayed feedback
curved losses
Primary area: theory->online_learning_and_bandits
TL;DR: We provide improved regret bounds for delayed online convex optimization with curved losses.

Abstract: In this work, we study the online convex optimization problem with curved losses and delayed feedback.
When losses are strongly convex, existing approaches obtain regret bounds of order $d_{\max} \ln T$, where $d_{\max}$ is the maximum delay and $T$ is the time horizon. However, in many cases, this guarantee can be much worse than $\sqrt{d_{\mathrm{tot}}}$ as obtained by a delayed version of online gradient descent, where $d_{\mathrm{tot}}$ is the total delay.
We bridge this gap by proposing a variant of follow-the-regularized-leader that obtains regret of order $\min\\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\\}$, where $\sigma_{\max}$ is the maximum number of missing observations.
We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret $\min\\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\\}$ where $n$ is the dimension.
To our knowledge, this is the first algorithm to achieve such a regret bound for exp-concave losses.
We further consider the problem of unconstrained online linear regression and achieve a similar guarantee by designing a variant of the Vovk-Azoury-Warmuth forecaster with a clipping trick.
Finally, we implement our algorithms and conduct experiments under various types of delay and losses, showing an improved performance over existing methods.

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Hao Qiu Emmanuel Esposito Mengxiao Zhang
Abstract
this round update her strategy in the next round. However, in many real-world applications, feedback is not immedi- ately available after the learner's ' decision but is instead sub- ject to delay. For instance, in online ad recommendation systems (He et al., 2014), click-through information may be delayed, and during this time the system must continue making recommendations for other users without access to the delayed feedback.
In this work, we study the online convex opti- mization problem with curved losses and delayed feedback. When losses are strongly convex, ex- isting approaches obtain regret bounds of order dmax T', where dmax is the maximum delay and T is the time horizon. However, in many cases, this guarantee can be much worse than vhhtt as obtained by delayed version of online gradi- ent descent, where di is the total delay. We bridge this gap by proposing a variant of follow- the-regularired-lleadr that obtains regret of order min In I", v J where max is the max- imum number of missing observations. We then consider exp-concave losses and extend the On- line Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret min 7 7i In T, )d where n is the dimen- sion. To our knowledge, this is the first algorithm to achieve such a regret bound for exp-concave losses. We further consider the problem of un- constrained online linear regression and achieve a similar guarantee by designing a variant of the Vovk-Azoury- Warmuth forecaster with a clipping trick. Finally, we implement our algorithms and conduct experiments under various types of de- lay and losses, showing an improved performance over existing methods.
Another crucial element in OCO is given by properties of the loss functions such as the curvature. It is indeed of- ten the case that losses have additional curvature properties such as strong convexity or exp-concavity. For example, exp-concave losses are prevalent portfolio management (Cover, 1991), in which the learner (investor) needs to dis- tribute her wealth over a set of financial instruments in order to maximize her return. When the loss functions have certain curvature, previous works (Hazan et al., 2007) have shown that a significantly better regret guarantee can be achieved (i.e., the so-called fast rates). However, this type of assumption received little attention when assuming that the feedback suffers some delay. Therefore, we are inter- ested investigating the following question:
Can we design algorithmss that exploit the loss curvature to obtain improved guarantees even with delayed feedback?
There is a line of works studying OCO with delayed feed- back. For general convex functions, Quanrud & Khashabi (2015) provided an algorithm called Delayed Online Gradi- ent Descent (DOGD) and achieves a regret of (VT + where T the time horizon and deot the total delay. Sub- sequently, Wan al. (2022a); Wu et al. (2024) focused on strongly convex losses, introducing DOGD-SC and SDMD- RSC, which achieve a regret bound of ((dmax + 1) In T), where dmax represents the maximum delay for any single round of feedback. However, the ((dmax + 1) In 7) regret bound can sometimes much worse than O OVTT+ ).oo) This occurs in scenarios when even a single round of feed- back is delayed by ((T)) rounds (e.g., missing feedback), undermining the benefits of having both regret guarantees under stronger curvature assumptions. Furthermore, to the best of our knowledge, no prior work has investigated whether improved regret guarantees are achievable for exp- concave losses under delayed feedback, leaving an impor- tant gap in the literature.
1. Introduction
Online convex optimization (OCO) a powerful framework for sequential decision making in uncertain environments (Hazan et al., 2007; Orabona, 2025). In classic OCO, learner repeatedly makes a decision, incurs loss for the chosen action, and uses the feedback of the loss function at
'Equal contribution 'Università degli Studi di Mi- lano Uniiersity of lowa. Correspondence to: Hao Emmanuel Esposito <em- manuel emmannelesposiooitt. Mengxiao Zhang <mengxiao- zhang @ @uiowa.cdu>.
Qiu <hao.qiue cerooiiuuunnin utimiiiiii..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Contribution. To address these gaps, we propose suite of algorithms and offer a comprehensive analysis for OCO with delayed feedback under both strongly convex and exp- concave losses, and we include a special case of (uncon- strained) online linear regression with delays. The main contributions of this work can be summarized as follows (see also Table 1):
O (Ilu) [[iin (dmas In T, v vdhat) + n In T)) with- requiring any prior knowledge of neither the com- parator u E IK" nor the data. This result is achieved by incorporating carefully designed clipping technique and, once again, employing an adaptive tuning of the learning rate.
Finally, in Section 6, we implement all our proposed algorithms and conduct experiments to validate our theoretical results across multiple delayed settings and loss functions with different curvature properties. We also compare our methods with existing approaches to demonstrate their effectiveness.
We first consider the class of strongly convex losses in Section Specifically, we propose an algorithm based on the hellow--heerrgulaiiie---eeee framework and obtain O (min { maxx In T, vdvot) } + In T) re- gret, where max is the maximum number of missing observations over rounds. Compared with the results obtained by Wan et al. (2022a) and Wu et al. (2024), our results have several advantages. First, since max is always no larger than dmax and can be significantly smaller than it, our a max In T bound improves upon the dmax In T bound in Wan et al. (2022a) and Wu et al. (2024). Second, we prove that our algorithm simultane- ously achieves a O (Vdrot + In T) regret bound, mak- ing our algorithm no worse than the bound achieved by DOGD (Quanrud& & Khashabi, 2015) either. Third, compared with the regret bounds obtained in Wan et al. (2022a) and Wu et al. (2024), our regret guarantee does not depend on the diameter of the action domain and recovers the one proven in Hazan et al. (2007) when there is no delay. Additionally, we provide a novel and improved analysis of the OMD-based algorithm originally proposed by Wu et al. (2024) in Appendix E, obtaining a regret bound that is again independent of the diameter of the action domain.
1.1. Related works
Online learning with curved losses. While Abernethy et al. (2008) have shown that @(VT) is the minimax regret for OCO, if the loss functions further enjoy curvature, the minimax regret can be improved. Hazan al. (2007) show that OGD with specific choice of learning rate achieves O G² maximum lg norm of any loss gradient and À is the strong convexity parameter. This upper bound is also minimax op- timal proven in Abernethy al. (2008). For exp-concave losses, Hazan et al. (2007) proposed Online Newton Step (ONS) achieving O({ + GD) T) regret where a is the exp-concavity parameter and D is the diameter of the feasi- ble domain. Hazan et al. (2007) also proposed Exponential Weight Online Optimization (EWOO), achieving diameter and gradient scale independent guarantees. However, the algorithm is less practical due to its sampling complexity. For OLR, Vovk (2001) and Azoury & Warmuth (2001) in- dependently introduced the Vovk-Azoury- -armmuhh (VAW) forecaster achieving (I T) regret without requiring prior knowledge of the data and the comparator. For a more de- tailed survey on OCO, we recommend the reader to Hazan (2016) and Orabona (2025).
X In T) regret for strongly convex losses where G is the
In Section 4, we consider exp-concave losses, a broader function class compared to the strongly convex one. Specifically, we propose an algorithm based on the Online Newton Step (ONS) method that achieves a } + +n T) regret bound.
O (min [dmax n T, / /dnot] To the best of our knowledge, this is the first algorithm to achieve logarithmic regret for exp-coneave losses under delayed feedback, answering an open question proposed in Wan et al. (2022a). While both the bounds d In T and Vdz.t can be achieved using a simple learning rate within the ONS framework, it is essential to use a delay-adaptive learning rate tuning scheme to achieve the best of these two guarantees within our analysis.
Online learning with delayed feedback. Weinberger & Ordentlich (2002) initiated the study of online learning with delayed feedback, proposing an algorithm achieving d- R(TTdd) where d is the fixed and known per-round delay and R(T) is the regret upper bound for some base algorithm that assumes no delay in the feedback. Specifically, their meta-algorithm runs d + independent copies of the base algorithm on disjoint time lines in a round-robin fashion. However, this meta algartagg is computationally expensive and does not show good empirical performances. Subse- quently, Langford et al. (2009) proposed a practical algo- rithm by simply performing the gradient descent step using the observed gradients at each round, and achieved O (0VV) /dT) and O (d T) regret bounds for convex and strongly convex
In Section 5, we investigate online linear regres- sion (OLR) problem, where the feasible domain is unconstruined, i.e., it corresponds to the en- tire n-dimensional Euclidean space R". Lever- aging the specific structure in OLR, we de- velop an algorithm based on the Vook-Azoury- Warmuth forecaster, achieving regret bound of
'hhe definitions these parameters are deferred to Section
2

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Regret bound
Loss type
Wan et al. (2022a);
Quanrud & Khashabi (2015)
Our work
Wu et al. (2024)
Strongly convex
Vdvot + T
(dmax + 1) In T
min 0 max In T, /doce) } + In T min [max Ti In T, vdoot) + v2 In T min [mmxx In T, v drot + 12 nnnnnnn In T
Exp-concave
Vent + +
N/A
Online linear regression
N/A
N/A
Table 1. Main results and comparisons with prior work. Here T is the number of rounds, v is the dimension of the feasible domain, dmax the maximum delay, max S dnax is the maximum number of missing observations, and deos is the total delay. In Table I, we omit the dependency on the curvature paramcters, Lipschitz parameters, the norm of the comparator and domain diameter for conciseness. The detailed dependencies are explicitly shown in the respective thcorem statements.
functions, respectively.
2. Problem setting
When delay is not uniform, Joulani al. (2013) proposed BOLD (Black-box Online Learning with Delays) extend- ing the method of Weinberger & Ordentlich (2002) and achieve dmaxx /dmaa) regret, but the algorithm still maintains multiple instances of base algorithms, which could be prohibitive in terms of computational costs. For convex functions, Quanrud & Khashabi (2015) achieved (Vviro)) where deoe the total delay accumulated over T rounds. Wan et al. (2022b; 2023) proposed a first Frank- Wolfe-type online algorithm to handle delayed feedback and obtain a regret bound of O ((T3/4 + dene T 3-344) for general convex loss and ( + dmax In T) under strong convex- ity. There is also an interesting line of works whose focus is to obtain adaptive regret guarantees with delayed feedback (McMahan & Streeter, 2014: Joulani al., 2016; Flaspohler et al., 2021) or to consider variants of delayed feedback (Gatmiry& & Schneider, 2024; Bar-On & Mansour, 2025; Ryabchenko et al., 2025).
Let T E N be the time horizon and n E N be the dimension. Denote by X' c R" the domain, which we assume to be closed and non-empty. In each round & E [2'] the learner selects point x4 E X as its decision and incurs loss St (2x4 given by some unknown function f2: X - TR that we assume to be convex and differentiable. Normally, in the standard OCO setting, the learner would then immediately observe the gradient 9r = V (1ze). On the other hand, here we consider the delayed feedback scenario in which such a gradient g: is only observed at round t + de with some unknown arbitrary delay de 2 O. We assume + d, S T for all E [T] without loss of generality (Joulani al., 2013; 2016) because the feedback of any round t with + de 2 T cannot be used the learner. The performance of the learner is then measured via the regret, which is defined as follows:
Regz- max (wg "
max uEX
Σ (((()))-((0 t=1
Two most related works to ours are Wan et al. (2022a) and Wu et al. (2024), which consider strongly convex losses together with delays. Specifically, Wan et al. (2022a) first proposed DOGD-SC for strongly convex losses, and estab- lish a regret bound of O( GD+GG dmax In T). Subsequently, Wu et al. (2024) proposed SDMDDRSC and obtained a O( dmma + G2+D dmax In T') regret b
For convenience, we define Or = fr E N T dr < {} S [t 1] to be the set of rounds whose gradients are observed before round r, and let m = [t - 1] og be the set of rounds whose observation is yet to be received at the beginning of round t. Define maax max [mm] to be the maximum number of missing observations over T rounds, dmax = max de to be the maximum delay, and drat = -. de to be the total delay. Also define dii max, min dyy t t-r} } as the maximum delay that has been perceived up to round t.
Beyond full-gradien feedback, there exists a growing inter- est in developing algorithms with delayed bandit feedback for a range of problems, including multi-armed bandits (Cesa-Bianchi al., 2016; Cella & Cesa-Bianchi, 2020; Zimmert& & Seldin, 2020; Masoudian et al., 2022; Van der Hoeven & Cesa-Bianchi 2022; Esposito et al., 2023; Van der Hoeven et al., 2023; Masoudian et al., 2024; Schlis- selberg et al., 2025; Zhang et al., 2025), Markov decision processes (Lancewicki et al., 2022: Jin et al., 2022; Van der Hoeven et al., 2023), and online convex optimization (Héliou et al., 2020; Bistritz al., 2022; Wan et al., 2024).
Before presenting our main results, we must first introduce some definitions about the curvature of the loss functions.
Definition 2.1. function f: X + R is X-strongly convex with respect to |1-I1 for À > if, for all 2, E X, f(y) > f(x) + (z)))) 2) + yy 21.2. Definition 2.2. A function f: X - o-exp-concave for a > 0f + exp(-af(x)) is concave over X.
Wu al. (2024) also considers the class of relative strongly convex loss functions.
We finally introduce some standard boundedness assump- tions relating to the gradients and the domain.
3

---

4: end for Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Algorithm 1 Delayed FTRL for strongly convex functions
SDMD-RSC exhibit polynomial dependence the di- ameter D of the action set X, we remark that our bound does not depend on D and recovers the optimal O G2 regret in the no-delay setting.*
input strong convexity parameter À >
(xx In T)
initialize 21 E X'
1: for t 1, do
2: Play zi; receive
((T( ) for all E 0+41 \ o
3: Update
3.1. Regret analysis
J++1 arg min
Σ 2) +
Σ
xoll2 (1)
Here provide a proof sketch of Theorem 3.1, whereas the full proof is deferred to Appendix B. Specifically, using the strong convexity property, we first decompose the regret:
sE
+E0++1
A 10-2211 21 u11
Assumption 2.3. For every t E [T], the gradient of ft has
Regr(") (w) S Σ
(gt 1)
norm bounded by G 2 0, i.e., maxzex (x=))]l G. Assumption 2.4. The diameter of X is bounded by D 2 0, i.e., gaxx,gex: || yll2 S D. We also assume 0 E A'
T
T
Σ (g 2
u) + Σ
(gc, Tt x1)
1 Σ
|
ull2
2
(e)
Driftr
Other notations. For a positive semidefinite matrix A E R.xx and x E RS, we denote ||ж/|/ = Vx Ax to be the Mahalanobis norm induced by A and, is positive definite, let || Vz A x be the dual norm. We denote the all-one vector in an appropriate dimension.
(2)
where xt = arg min S + -, 12)) for 2 2 and 21 = I1 are the decisions assuming that all gradients before round are observed.
3. Delayed OCO with strongly convex losses
Next, we analyze the term Reg) and Driftr separately. For the term Driftr, applying the Cauchy-Schwar in- equality and using the fact that ||g ll s G' for all E [T] by Assumption 2.3, we can obtain that
In this section, we consider the problem of delayed OCO with strongly convex losses and propose Algorithm 1, which built upon the whwllw-thh-rrguuarieeeeeeeeeee gorithm. Specifically, after receiving the gradients 9, for all 7 00 at the end of round I, compute the updated decision I++1 shown in Eq. (I), which is the minimizer of the cumulative linearized loss with respect to all the currently observed gradients, plus a squared ér-reulaaiizatonn term with respect to all the past deci- sions. The following theorem shows that Algorithm achieves O( O( G² X (In + min [Tmax In T, / ddoo))) regret bound without any diameter assumption on the domain.
(FTRL) al-
T xell2-
Driftr S
Σ || SG>
(3)
For the term Regī following a standard FTRL analysis and using the optimality of 27, we are able to obtain that
A T 2
(u)
| u1 + > 19. 2it1)
Theorem 3.1. Assume that fi...., fr are X-strongly con- vex with respect to the Euclidean norm 11-1 Then, under Assumption 2.3, Algorithm guarantees that
Since the first term be canceled by the last negative term shown in Eq. (2), we only need to control the second term x3 -xf+1), which is further bounded by G'Ila -xft1 la via Cauchy-Schwar and the fact that l|gella < G. Then, using a stability lemma for FTRL (Lemma A.2), we can show that
Regt = =0 1
G² (InT+ + min {omax In T, Vdnne)) 3))-
Theorem 3.1 highlights two advantages over previous works. From the perspective of the delay-related term, while both DOGD-SC (Wan et al., 2022a) and SDMD-RSC (Wu et al., 2024) achieve O (dmax T) regret bound, the terms Fmax and Vioae in our regret bound can be substantially smaller than d with Tnax dinax always being true (Ma- soudian et al., 2022).² 3 Second, while both DOGD-SC and
2G
||ا| x1t1lla S X(21-1) -) + || xel12-
Interestingly, this inequality relates the Euclidean distance between adjacent "cheating" iterates (x:) )221 i in the stability term of FTRL to the distance between x; and 2;, which is
'Despite the fact that G-Lipschitzness and X-strong convexity of the losses over the domain X' imply that its diameter is bounded by 2G/A, \x, the guarantees of DOGD-SC and SDMD-RSC remain suboptimal.
In fact, we also show in Lemma A.7 that max S Vdhoo, and in Lemma A.9 that there are delay sequences such that max E dhot and mmax R Vdhat, respectively.
4

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
also present in the Driftr term and intuitively quantifies the influence of delays on the regret.
Algorithm 2 Delayed ONS for exp-concave functions
input 8 > 0, learning rate rule (n1e21.
Combining the inequalities involving (u) and Driftr, we can finally bound the regret from above as follows:
initialize x1 X'
1: for t = 1, do
2: Play 2y; receive 9F = V[r((T) for all T E o++1 Vo
Regr 1
T
20
+ 2G
Σ
| - mell2
3: Tx+1 = arg min TE
Σ (gr, 2) + (0r, x,,²²
1(2
- 1)
TEOL-1
1=1
+
tt
|
G InT + 1) + 2G
T
4: end for
2
||a| xz 22112-
It remains to show how to bound | - zell2 by O min(omax TT vdhoo)), which is the key novelty in our analysis compared to previous works. Recalling the definitions of xi and st, we can apply the stability lemma of FTRL (Lemma A.2) again and show for all t that
Theorem 4.1, Assume that fi...., ... fr are o-exp-concave
and let ( = 3 min aGD a). Then, under Assumptions 2.3 and 2.4, Algorithm 2 with 0 no S m S S 'p
guarantees that
X(t- - 1) 2
1 9T 12
Regr =0( In In(1+
1+
SGTT non
+ D + +min {Bi, B2))
|1o| -xal3
(4)
2X(t-
1)
1 |Erem 8-112 A(1-1)
where B1
G2 nl
})
nedmax In (1+ SG Mon
and B₂
meaning that Ei= ||== - 22122 S 2
<
G2 E
[mme
Glmme]
Et=2 X(t-Ij+ where we also use the fact that of 21- Here, we highlight the importance of including all previous decisions 2, for T S 6, instead of T Or+-1 only, in the regularization term of the update rule of 21+1 shown in Eq. (1). Doing so particularly ensures that the updates of xt and ož share the same regularization terms, which is crucial in leading to a diameter-free upper bound for ||at - melle using the stability lemma.
m
We can now introduce two careful tunings of the time- varying learning rates (n4)21 to derive the regret bounds Od In T) and O(y individually.
Simple tuning. With constant learning rate constant T)t 1 for all & E [T] Algorithm 2 directly ob- tains Oddmax In regret. Alternativlyy, setting T =
Imm Directly bounding Finally, we study the term Ei= I-1
G VEege |mal + |mel + 1 for all 2 1, Algorithm 2 achieves O regret; here, the |m:] + 1 term is an essentially tight worst-case estimation of |ma-1], since M4+1 S m, m,muf (t).
D
|m,| from above by max leads to the first a max In T bound. To further obtain the vdrot bound, it is crucial to observe that Evse mm|| S (t- -12 since m, S [T - 1]. Therefore, by also using Orabona (2025, Lemma 4.13)
able to prove that Σiz T-I S Σt= VErgi |m+] S dhots which concludes the regret analysis.
[mma
[mme]
Note that either of these two bounds can be significantly better than the other under different delay sequences, e.g., as shown by our Lemma A0 in the appendix. Therefore, we idcally want achieve O (dmax In T, Vdvi)) )) regret via single choice of the learning rates. In fact, we can show that it is indeed possible to obtain such bound by a careful delay-adapticn learning rate tuning.
4. Delayed OCO with exp-concave losses
In this section, we consider the delayed OCO problem with exp-concave losses. Exp-concave losses are more general class of loss functions that require more sophisticated tech- niques to be tackled. To address this problem. we design Algorithm 2, a variant of Online Newton Step (ONS) which effectively handles delayed feedback. Specifically, after receiving the gradients 9r for all 7 E 0t+1 (or, we select Tt-1 as the minimizer of the cumulative surrogate loss over all the already observed gradients and the past actions, with an additive squared fz-regularization term. For simplicity, in this section we omit dependencies on curvature parame- ters, Lipschitz constants, and domain diameter; they appear explicitly in the theorem statements. The following result provides a first regret bound for Algorithm
daptiie tuning. The adaptive learning rate is given by no = 1 and 17: = min br} + 1 for all t 2 1, where
2
nd St In (1+ 3G
G2 +
(5)
GD
max
G D
b. =
|mgl + |mme|
+
(6)
The overall idea behind this learning rate tuning is to keep track of both the dmaz I and / vdhoo regret guarantees over the rounds via a and by, respectively. Then, ne is set
5

---

Here we consider the problem of online linear regression (OLR) with delays. This setting essentially corresponds to a variant of OCO where the domain is = RR and loss functions are fc(z) 1 ((2,, )2)² comparing any point IR" to label yt E given some feature vector 24 R"; to be precise, the predicted label by given point 2: corresponds to the inner product (zt, z)). At each round 4, the learner first observes an n-dimensional feature vector 22 before performing its prediction I,, but the true label y, is Exploiting Curvature in Online Convex Optimization with Delayed Feedback
depending on the best of the two, i.e., min(ar, d,). which then leads to achieve the best of both regrett bounds. Note that this adaptive tuning requires the knowledge of the time- stamps of the received gradients since we need to compute mmax = ma min(d,, - 7) which, we recall, is the maximum delay that has been perceived up to round t. The following corollary provides a regret bound for Algorithm 2 with this adaptive tuning. The full proof of Corollary 4.2 can be found in Appendix C.
9-9,- Applying Lattimore where - - & Szepesvári (2020, Lemma 19.4). the last sum the right-hand side of the above inequality satisfies
T
0 In 1
BGTT
min Gl.lllll,,
1 :) - O
Now we consider the Driftr term. By applying the Cauchy-Schward incquality followed by the stability lemma (Lemma A.2) again, it follows that for all t 2 1,
Corollary 4.2. Assume that fIT fT are a-exx-concave and let B = 2 minf 1 JCD: 1GD: a.}. Then, under Assumptions 2.3
and 2.4, Algorithm 2 with the adaptive learning rute T)t-
T
min (a,, by) +,, where a, and by are defined in Equations (5)
Driftr S
Σ
l daella, ب
l - 2i,1A,11
and (6), guarantees that
t=1
T
Regr- = 0 n 1n(1+ 11+
BGTT)
+ +D² min (C2, C2)
S 4
1 1l al
Σ TEm
l1g (0rllaaza
(10)
where C1 = (g +1) GP ( ( and C2 = -G2 GD) (Vdeot+ + +1)
ndmax In (1+ 3G
By applying Lemma C.I, it holds that
Drifty = ((0² +BB) nd ndmax In (1+ 3G2T
1
Corollary 4.2 shows Algorithm 2 with the adaptive learning rate obtains regret O (min [dmax" In T, vd }). The main advantage of an adaptive learning rate is that it requires no prior knowledge of diot or dmaxx nor does rely on a doubling trick that would throw away information via resets.
n
(1I)
At the same time, we can also prove that
[mgl
Drifty = O G²
(12)
Mh-1
4.1. Regret analysis
Combing Equations (7) to (12) concludes the proof of The- orem 4.1. To prove Corollary 4.2, we carefully consider the adaptive learning rate tuning and separate the analysis into two cases. case 0T S by at the end of the T rounds, we utilize a delayed version of the elliptical potential lemma (Lemma C.1) to achieve the logarithmic regret. On the other hand, if by < aT we split the regret analysis at the last round r" at which a,. I b,-. Then, we use again the loga- rithmic bound up to round r* and the vdhao bound for the remaining rounds. It suffices to observe that the first bound is no worse than vdeut since a,- S by to conclude the proof.
In this section, we provide a proof sketch of Theorem 4.1 and Corollary 4.2, while their full proofs are deferred to Ap- pendix C. Specifically, using the exp-concavity property and Lemma A.3, decompose the overall regret as follows:
(u) Σ
(gt, x. u²
Lgt, Tt xt)
Regg (1)
Driftr
3
T
(gt, Ve - -u)2
(7)
2
t=1
where we define of 01 and, for 1 2 2, x
5. Online linear regression with delayed labels
arg min E (1or. .7) + 2 (gr. x - xT) )) -h- | to be the decisions assuming that all gradients before round t are observed.
For the term Reg? (u), following a standard FTRL analysis, we are able to obtain that
Reg (u) S 1/T |
2 +
(gt, u - 22
+
min
GD, l1ge l1gell
(8) only revealed at a later round t + dy. A common assumption on feature vectors and labels in this setting, analogous to
6

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
the ones we introduced in Section 2 for instance, is their boundedness.
knowledge about all labels from past rounds. To bound the cheating regret (eg, it is important to leverage the curvature of the squared loss. Specifically, by definition,
Assumption 5.1. The feature vectors 21...., 2T and the labels yı,... yr are bounded, i.e., ||=e||2 I Z and Iyal < Y for any & E (T). given Y, Z 2 0.
T
2tz xt)
(Ze, u)
T
Reg7 (u) =
Ur 2 u)
2
Algorithm 3 Delayed VAW forecaster with clipping input learning rate rule fmh121 initialize P1 = 0
Then, we can study the second sum via the standard tools for the regret analysis of FTRL with respect to the linear losses x + -Be x), which yields
1: for f.= = 1,2,... do
2: Observe Zt
(u) S MT |lul + nY In
ZºT
1+
3: Set 24 arg min FER" TEa
Σ - Vr (2r, 2) + +/2 |011
+ Ers 2)²
This is exactly the first line in the regret guarantee presented in Theorem 5.2, and corresponds the part that does not depend delays.
4: Play āe = It . min( Ta)
+1
5: Receive yr for all 0++1 Or \
6: Set Pt+1 = 6044 Brr
On the other hand, the drift term Driftr requires much more care and novel techniques. By the convexity of fú, we have that Driftr S E (Vaa 3h - x;)- Here we immediately observe the importance of the additional clip- ping of xt to define the selected point T., which is inspired from the clipping ideas by Cutkosky (2019); Mayo al. (2022). Its scope is guarantee that the predicted label (z,, 3.) falls within the range of true labels; the reason for this is to avoid the gradient of ft evaluated at o, to blow up, otherwise obstructing an attempt to nicely bound Driftr. We also remark that, differently form Mayo et al. (2022), we do not require to clip the labels used in the iterates update too. If we had knowledge of Y. we could use it to clip to the interval [-Y,Y] thus guaranteeing fa( I Y. However, since we want to assume no prior knowledge of Y, the best clipping we can do at any time f is via pt. Doing so requires to handle possible rounds when the label falls outside the clipping interval, which in turn requires a careful analysis that accounts for the feedback to be revealed only after some delay (as Pt could possibly be updated much later in time). We are then able to prove that
7:
end for
Note that the loss ft becomes exp-concave when the do- main is also bounded. If this were the case, we could solve this problem by designing& version of ONS that can han- dle delayed labels. In OLR, however, the domain is un- constrained as it corresponds to the whole n-dimensional Euclidean space, which makes it particularly challenging to simply adapt one of the techniques seen so far without further assumptions. We instead design an algorithm for this problem (see Algorithm 3) that corresponds to an adaptation of the Vovk-Azoury- Warmuth (VAW) forecaster (Azoury & Warmuth, 2001; Vovk, 2001) in order handle delayed labels. We can then prove that the regret guarantee for this algorithm in the delayed OLR setting becomes as stated in Theorem 5.2 below (whose proof is in Appendix D).
Theorem 5.2. the OLR problem with delayed labels under Assumption 5.1, Algorithm guarantees for any O- < No S m S S A/ that
2²T
(u) -
'T | + 2 2
In 1+
Driftr = OY mmax + + min M1,, M2))
Nun
+ o (r2 (mmax + min (M1, M23))
which is the delay-dependent part of the regret; the Y' term, in particular, is the one due clipping mistakes.
where M1 = nduax In(1 + z²r) and M2
Given any 7 > O. we may now set t70- 7 and m 7min Liminfag. (az, be + 1) for all t 2 1, where
TT 1=1 2
[mel
The idea behind the regret analysis is once again to decom- pose the regret into cheating regret term and a drift term:
b. = EVV.gilms zzT) ym
a: 2t In 1+ max
(13)
T
Regr (w) ((io)) ff(w)))f((())- -
By doing so, we obtain the following Corollary 5.3 which provides a regret bound for Algorithm 3 with this adaptive tuning, and whose proof is deferred to Appendix D.
Regg-(u) (M)
Drifer
where (Ze)221 are the actions played by Algorithm 3, while (x1) are the "cheating" iterates that assume to have
Corollary 5.3. In the OLR problem with delayed labels un- der Assumption 1, Algorithm with the adaptive learning
7

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
rate 'ie = am,nn(aa, be} + 1), where at and by are defined
Exp-concave loss. The loss functions we consider for exp- concave ones are fe(z) = 1 ((2,, 2) -yr)² y,)² The other con- figurations are the same as the experiments in the strongly convex case. We evaluate our Algorithm and compare its performance with that of DOGD (Quanrud & Khashabi, 2015) and BOLD-ONS, which applies the reduction pro- posed in Joulani et al. (2013) to ONS (Hazan et al., 2007).
in Equation (13) for any > 0 guarantees that
211u1122 +nY In (1+ Z y
Regr V
+ (min Q2)),
2
where Q1 - (1|14|2+ + 22) )2) radmax In (1 z²T (>2]|u|12+ + (Z + 1) Vdveo.
and Q2
m
Online linear regression. We still consider the loss func- tion ft(x)) 2 ((2,, ) for all L E [7], the same one used in the exp-concave setting. The only difference is that the action space is now unconstrained (X' IR"), We empirically evaluate Algorithm 3 on this loss sequence and compare the performance with DOGD (Quanrud & Khashabi, 2015) and BOLD-VAW, which is again a combi- nation of the reduction in Joulani et al. (2013) and the VAW forecaster (Azoury & Warmuth, 2001; Vovk, 2001).
To achieve this final result, we leverage similar ideas from the adaptive tuning for delayed ONS in Corollary 4.2, as mentioned above, together with a nontrivial relation be- tween max and vdto to handle the additive Y2 term from the clipping errors (see Lemma A.7). We remark that here we used directly Z for the tuning, which requires its knowledge since the first round; we could easily do without this prior knowledge by using Z = max+ || || ll2 instead because we always observe all the previous and the current feature vectors by the beginning of round
Experimental results. Figure shows the mean cumula- tive regret and its standard deviation over 20 rounds for the instances with strong convexity, exp-concavity, and OLR under the two previously mentioned delay regimes. For strongly convex losses, we find that our algorithm per- forms much better than DOGD-SC (Wan et al., 2022a) and have similar performances compared to SDMD-RSC, which is proven to only achieve Oddmax In T) regret (Wu et al., 2024). However, we point out that this mismatch in the empirical performance and the theoretical guarantee of SDMD-RSC is due to a loose analysis of this algorithm. In fact, we show that SDMD-RSC can also achieve the same O(min In T. vdrot)) regret via a refined analy- sis. The proof is deferred Appendix E.
6. Experiments
In this section, we evaluate the performance of the pro- posed algorithms on three types of loss functions in the delayed OCO setting. 5 All experiments are conducted over T 10000 round and results are averaged over 20 inde- pendent trials. To showcase the advantage of our algo- rithms, consider two delay regimes. For the first case, each delay d, is independently and uniformly sampled from the set (0, (0.),....)), thus leading to Bl(d = O(VT) and [[] < E[dmax] < 5. In the second case, we define p = 1/3 = 0.1. Then, for each t. de is sam- pled from the same distribution with probability - p. and it is set to be d,- = T with probability p. In this case, TE[ drot = O()), Bl[dmux] 2 T(1 (1 p)²), and [[[max] = OpT)). We compare our algorithms against several baselines designed for delayed feedback settings. Below, we describe how we construct losses, together with the bascline algorithms we compare against. We provide additional experiments in Appendix F.
For both exp-concave and OLR settings, our algorithms consistently outperform DOGD, which does not leverage the curvature of the loss function, as well as the reduction-based algorithms proposed in Joulani et al. (2013), under both delay regimes, showing the effectiveness of our algorithms under different delay conditions.
7. Conclusions
Strongly convex loss. We consider the following strongly convex losses fxrr) = ((2,,)) y² + 211x1 || The feasible set is the ball X {x E RR, ||0/|2 S 2}. Each co- ordinate of the feature vector E R5 at round t is uniformly chosen from [] while y/- = (z,, 1) + <, where e, is an i.i.d. standard Gaussian noise. We evaluate Algorithm on this loss sequence and compare its performance with DOGD-SC (Wan et al., 2022a), SDMD-RSC (Wu et al., 2024, Algorithm 6), and BOLD-OGD which applies the reduction proposed by Joulani et al. (2013) to OGD.
In this paper, we study how to leverage the curvature of the loss functions in online convex optimization with delayed feedback so as to improve regret guarantees. For strongly convex functions, we derive an algorithm achieving O'min In vdroc)) regret, improving upon previous work (Wan et al., 2022a; Wu et al., 2024), which only obtain Od In T) regret. We also derive (min(dmaxxl In T, vdhot)) for exp-concave losses and online linear regression, answering an open question pro- posed in Wan et al. (2022a). It is still left open whether O (mmin(mmaxe ma In T, / / is achievable for exp-concave losses.
'The code for the experiments htpp://gitulccom/mmnii5550CCC
available at
8

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Smungl oanay, Bare Vifi
Expecceaace deass de. Ville
Ol.R, deas Vf Vila
60
DOGD DOLDONS
DOGD
30XI-R3C
DOLD
30
Delanad FTRL.
DSS
VANT
40
-0.0
30
20-
40-
10
70
Strongly Beas Vil..
dees vdd...
des.,
DOGIESST
3000
DORD
3300
SDATD-RSC
2500
BOLL8-NXS
BOL.3-AKT
Delavel PIRL
D4fges. ONN
3500
Dobovel NMNV
90
FOX
2000
2000
D00
1200
600
1000
300
2300
1000
0000
8000
10000
2000
8000
6000
8000
10000
2020
4000
5000
8000
10000
Figure 1. Comparison with relevant baselines. The shaded areas consider range centered around the mean with half-width corresponding to the empirical standard deviation over 20 repetitions.
Acknowledgements
evolving observations. In Kamath, G. and Loh, P.-.. (eds.), Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceed- ings of Machine Learning Research, pp. 204-227. PMLR, 2025.
EE and HQ acknowledge the financial support from the FAIR (Future Artificial Intelligence Research) project, funded by the NexIGenerationEU program within the PNRR-PE-AA scheme (M4C2, investment 1.3, line on Ar- tificial Intelligence), the EU Horizon CL4-2022-HUMAN, 02 research and innovation action under grant agreement 101120237, project ELIAS (European Lighthouse of AI for Sustainability), and the One Health Action Hub, Univer- sity Task Force for the resilience of territorial ecosystems, funded by Università degli Studi di Milano (PSR 2021-GSA- Linea 6).
Bistritz, I., Zhou, Z., Chen, X., Bambos, N., and Blanchet, J. No weighted-regret learning in adversarial bandits with delays. Journal of Machine Learning Research, 23(139): 1-43, 2022.
Cella, L. and Cesa-Bianchi, N. Stochastic bandits with delay-dependent payoffs. In International Conference Artificial Intelligence and Statistics, pp. 1177. PMLR, 2020.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. The contribution of work is pri- marily theoretical in nature. Thus, do not foresee any societal consequences.
Cesa-Bianchi, N., Gentile, C.,, Mansour, Y., and Minora, A. Delay and cooperation in nonstochastic bandits. In Feldman, V., Rakhlin, A., and Shamir, O. (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 605-622,
Columbia University, New York, New York, USA, 23-26
References
Jun 2016. PMLR.
Abemneth,, J., Bartlett, P. L.., Rakhlin, A., and Tewari, A. Optimal strategies and minimax lower bounds for on- line convex games. In Proceedings of the 21 annual conference on learning theory. pp. 414-424, 2008
Chang, C.-C. and Lin, C.-J. LIBSVM: A library for sup- port vector machines. ACM Transactions Intelligent Systems and Technology (TIST). 2(3):1-27, 2011.
Azoury, K. S. and Warmuth, M. K. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine learning, 43:211-246. 2001.
Cover, T. M. Universal portfolios. Mathematical finance, (1):1-29, 1991.
Cutkosky, A. Artificial constraints and hints for unbounded online learning. Beygelzimer, and Hsu, D. (eds.),
Bar-On, and Mansour, Y. Non-stochastic bandits with

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Proceedings of the Thirty-Second Conference on Learn- ing Theory, volume 99 of Proceedings of Machine Learn- ing Research, pp. 874-894. PMLR, 2019.
Learning Research, pp. 1285-1321. PMLR, 12-15 Jul 2023.
Jin, T., Lancewicki, T.,, Luo, H.,, Mansour, Y., and Rosen- berg, A. Near-optimal regret for adversarial mdp with delayed bandit feedback. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, vol- ume 35, pp. 33469-33443 Curran Associates, Inc., 2022.
Esposito, E., Masoudian, S., Qiu, H., Van der Hoeven, D., Cesa-Bianchi, N., and Seldin, Y. Delayed bandits: When do intermediate observations help? In Krause, A.. Brun- skill, E.,, Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Confer- ence on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9374-9395. PMLR, 2023.
Joulani, P., Gyorgy, A., and Szepesvári, C. Online learning under delayed feedback. In International conference on machine learning, pp. 1453-1461. PMLR, 2013.
Flaspohler, G. E., Orabona, F., Cohen, J., Mouatadid, S., Oprescu, M., Orenstein, P., and Mackey, L. Online learn- ing with optimism and delay. In International Conference on Machine Learning, pp. 3363-3373. PMLR, 2021.
Joulani, P., Gyorgy, A., and Szepesvári, C. Delay-
tolerant online convex optimization: Unified analysis and dnlaptie-gradienn algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Gatmiry, K. and Schneider, J. Adversarial online learning with temporal feedback graphs. In Agrawal, S. and Roth, A. (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 4548 4572. PMLR, 2024.
Lancewicki, T., Rosenberg, A., and Mansour, Y. Learn- ing adversarial markov decision processes with delayed feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7281-7289, 2022.
Hazan, E. Introduction to online convex optimization. Foun- dations and Trends@ in Optimization, 2(3-4):157-325, 2016. doi: 10.1561/2400000013.
Langford, J., Smola, A., and Zinkevich, M. Slow learners are fast. arXiv preprint arXiv:0911.049) 2009.
Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret al- gorithms for online convex optimization. Machine Learn- ing, 1922 2007.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Masoudian, S., Zimmert, J., and Seldin, Y. A best-of-both- worlds algorithm for bandits with delayed feedback. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Informa- tion Processing Systems, volume 35, pp. 11752-11762. Curran Associates, Inc., 2022.
He, X., Pan, J., Jin, O., Xu, T., Liu, B., Xu, T., Shi, Y., Atallah, A., Herbrich, R., Bowers, S., et al. Practical lessons from predicting clicks on ads at facebook. In Proceedings of the eighth international workshop on data mining for online advertising, pp. 1-9, 2014.
Héliou, A., Mertikopoulos, P., and Zhou, Z. Gradient-free online learning in continuous games with delayed re- wards. In International conference on machine learning, pp. 4172-4181. PMLR, 2020.
Masoudian, S., Zimmert, J., and Seldin, Y. A best-of-both- worlds algorithm for bandits with delayed feedback with robustness to excessive delays. In The Thirty-eighth An- nual Conference on Neural Information Processing Sys- tems, 2024.
Van der Hoeven, D. and -isacBianchi, N. Nonstochas- tic bandits and experts with arm-dependent delays. In Camps-Valls, G., Ruiz, F, J. R., and Valera, I. (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Pro- ceedings of Machine Learning Research, pp. 2022-2044. PMLR, 28-30 Mar 2022.
Mayo, J. J.. Hadiji, H., and Van Erven, T. Scale-free uncon- strained online learning for curved losses. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Con- ference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 4464-4497. PMLR, 2022.
Van der Hoeven, D., Zierahn, L., Lancewicki, T., Rosen- berg, A., and Cesa-Biannchi, N. A unified analysis of nonstochastic delayed feedback for combinatorial semi- bandits, linear bandits, and mdps. In Neu, G. and Rosasco, L. (eds.). Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine
McMahan, B. and Streeter, M. Delay-tolerant algorithms for asynchronous distributed online learning. In Ghahra- mani, Z., Welling, M., Cortes, C., Lawrence, N., and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014.
10

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Orabona, F. A modern introduction online learning. arXiv preprint /9X1v:/9/2.132/11 2025.
Learning Research, pp. 38768-38800. PMLR, 23-29 Jul 2023.
Quanrud, K. and Khashabi, D. Online learning with adver- sarial delays. Advances in neural information processing systems, 28, 2015.
Zhang, M., Wang, Y., and Luo, H. Contextual linear bandits with delay as payoff. arXiv preprint arXiv:2502. 12528v2, 2025.
Ryabchenko, A., Attias, I., and Roy, D. M. Capacity- constrained online learning with delays: Scheduling frameworks and regret trade-offs. arXiv preprint arXiv:2503. 19856v1, 2025.
Zimmert, J. and Seldin, Y. An optimal algorithm for ad- versarial bandits with arbitrary delays. In Chiappa, and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learn- ing Research, pp. 3285-32222 3294. PMLR, 2020.
Schlisselberg, O., Cohen, I., Lancewicki, T., and Mansour, Y. Delay payoff in MAB. Proceedings of the AAAI Con- ference on Artificial Intelligence, 39(19)20031-2000 2025.
Vovk, V. Competitive on-line statistics. International Statis- tical Review, 69(2):213-248, 2001.
Wan, Y., Tu, W.W.,, and Zhang. L. Online strongly convex optimization with unknown delays. Machine Learning. 111()):77-893, 2022a.
Wan, Y., Tu, W.-W., and Zhang, L. Online frank-wolfe with arbitrary delays. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 19703-19715. Curran Associates, Inc., 2022b.
Wan, Y., Wang, Y., Yao, C., Tu, W.-W,, and Zhang, L. Projection-free online learning with arbitrary delays, 2023.
Wan, Y., Yao, C., Song, M., and Zhang, L.. Improved regret for bandit convex optimization with delayed feedback. Globerson, A., Mackey, L.. Belgrave, D., Fan, A., Paquet, U., Tomozak, and Zhang, C. (eds.), Advances Neural Information Processing Systems, volume 37, pp. 169-196. Curran Associates, Inc., 2024.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Linear last-iterate convergence in constrained saddle-poin op- timization. In International Conference on Learning Representations, 2021.
Weinberger, M. J. and Ordentlich, E. On delayed prediction of individual sequences. IEEE Transactions on Informa- tion Theory, 48(7): 1959-197., 2002.
Wu, P., Huang, H., and Liu, Z. Online sequential decision- making with unknown delays. In Proceedings of the ACM on Web Conference 2024, pp.
2024.
Xu, Y. and Zeevi, A. Bayesian design principles for fre- quentist sequential learning. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, (eds.), Proceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
A. Auxiliary results
In this section, we show several auxiliary lemmas that will be helpful throughout the paper.
A.1. General results for the regret analysis
The following lemma is a standard result for the regret of FTRL.
Lemma A.1 (Orabona (2025, Lemma 7.1)). Let X _ IR" closed and non-empty. Denote by F((x) (x) + (x)) Assume that arg min (2)) is not empty and T2 arg min mixxex Ft(x)). Then, for any E X,
Σ (((())) (())) (u)) min v/a (I) ZEX
Σ (
FF+1((T44) -rez()
The next lemma bounds the distance between two FTRL iterates with different linear losses and possibly different regularizers. also shows a simplified upper bound in the case when the two iterates have the same regularizer.
Lemma A.2 (Stability lemma). Let X S R" be closed and non-empry. Let A1. A2 f be two positive semidefinite
matrices, b b2 R and C1, C R. Define t/1 (x)) x² A1x + bj x + 01 and 2/2(21) x A2x bj x c2. Suppose that E arg min (w),,)) 2)) + thi (x)} and 22 arg min (w2, x) + (>)) Then, we have
- 21 + |||| 221 S (w0 W2, 22 21) (1/1 (22) rb2(22)) (1/(211) - 2/2(211)
Furthermore, (x) = (x)(x) TTAr Arr b x + with positive definite A > O, we have
|| - 22l1A - / 1l w2lla-1
Proof. Let h1 (x) (w),, +hi (x) and h2(2)) = (w2, x)) +/22(2r) (x) be twice-differentiable functions with Hessians A + A and A2 + A,, respectively. Note that 21 E arg min 1 (x) and 22 E arg min h2(x)). By Taylor's theorem and first-order optimality conditions, we know that
((w1, 22) + 1/1 (22)) - ((11,2)) + (21)) = h1(22) - h1(21) 2 || 22 11
(ww2, 21) + (21)) - ((w2, 22) + 222(22)) = h2(21) - h2(22) 2 21/21 22 22
Summing up the above two inequalities, we obtain
|| 22 11,,, + || 22 21 S (wi W2, 22 21)
(1) - v2((11)
The second result is directly obtained by applying the Cauchy-Schwarz inequality when 1 (x) (2(x))
The following lemma is the quadratic bound of a-exp-concave functions.
Lemma A.3 (Hazan et al. (2007, Lemma 3)), Let f: X' + R be an peeepp-concavefucctiii Then, under Assumptions 2.3 and 2.4, we have that
f(x) 2 f(v) + (Vf(y), r - y) + - ((V(W)))=)))
for any v,y X, where 3 min 1 a.).
The following lemma is the link of the Bregman divergences between 3 points.
Lemma A.4 (Wei et al. (2021, Lemma 10)). Let A be a convex set and x2 = arg oigminge (9 + (1,))))) Then, for any u A.
(a2 g. < (1) - (vlu, 22) (o(
The following lemma is the general bound on (g. v) |||u|| which related to the achievable via the Fenchel- Young inequality but strengthened thanks to norm constraint on
Lemma A.5 (Flaspohler et al. (2021, Lemma 18)). Let ||-|| be a norm over R and let || be its dual norm. For any constants X, c, > 0 and any E T
(Q.,)) 2 [1111p min
2x llg 12. 5 -119ll.. bllglla
sup VERn:llo|Smmmuf (.))
2
12

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
A.2. Results for delay-related quantities
The following three lemmas quantify the relationship between O maxx dmmxx and drot.
Lemma A.6 (Masoudian et al. (2022, Lemma 3)), Let dmax(() = max+es dr and S = [T] S for any S S (T). Then,
max I min ( + dmax(())
scPl
Lemma A.7. Let (S) =Ees dy and S = [2') for any S [T]. Then,
O max 2v2
min SC
|S] + v dror(5)
Proof. First, observe that (S) = Σt= m, nS| for any S S [T]. Also note that the bound trivially holds if max 0; hence, assume max 2. 1 without loss of generality. Let to be any round such that |m-- maxx Consider any S C [T].
and define A = my S and B my n S. If A (v2 1) m then
|S| V deat (5) S
A (V2 - 1) maxx
Otherwise, we have that [B] > (2 22) m Hence, denote B = .t...... ttat such that t <... < t| and observe
that |4 n B| 2 i for any 44 E B. We can consequently prove that
B
|S] + V doot(() (S) 2 v dra((S) =
Σ ml ns 2
m4+1 1 nB
(V2 1)0
EEB
which concludes the proof 12-1 2/2.
Lemma A.8. Let Th max max+ mr Sl and S [T'} \ S for any S S [T]. Then,
(SS) on
maax
min SCIT
Proof.
First, it trivially holds that
(iS] + mmax)
mmax
min
SC[T]
We now only need to show the inequality in the other direction. Consider any S (T) and let be any round such that [m,- = maxx Then,
I JS| + max
2 |S| + (ma-- 05) = |S| + |mg- S 2
m
Omax
which concludes the proof.
The following lemma further illustrates the relationship between Fmax and v dhot in a more concrete way. Lemma A.9. There exists delay sequence (de (de)re(m) such that Fmax v1.5 deot- In addition, there also exists delay sequence such that mmax and viot = VT.
Proof. Given positive integer N > 5, consider the sequence (d)) where de N L for all / S N and d, = 0 for all t N. In this case, maax ON-1 1 N and v VI.5 deot = 3N(N-I) N On the other hand, consider the sequence where d, for all E [T). In this case, maxx and vhot VT.
On similar note, we show another similar result depicting the relationship between dmaax and V Lemma A.10. There exists a delay sequence (de)setr) such that dmaa = T and vihant = VT. In addition, there also exists delay sequence such that d and vdiot VT.
Proof. Consider the sequence (de)uE(T where round to T1/2 with de, = to and all the other rounds d, 0 for t + to. then we can choose to = and have dmax = and /d = VT. On the other hand, consider the sequence where d. for all E (T), then dmax and Vdhat VT.
13

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
B. Omitted details in Section 3
In this section, we show the omitted details in Section 3. For completeness, we restate the theorem and provide its proof. Theorem 3.1. Assume that fi.....fr are X-strongly convex with respect to the Euclidean norm 11-1/2- Then, under
Assumption 2.3, Algorithm guarantees that
Reg- =0 =0( (InT + min { {mmux In v dhoce) ()
@
Proof. First of all, define
1-1
and FT(+)= = Σ (or, [((e))) + x 11:0 x 2=112
(((x)= = E(.r +
Σ r=1
|/
TEa.
for any 2 1. Observe that Z2 arg m Fx) and additionally define z E arg min (z) for t 2 2, while oi (since (x) = Fi)).. The sequence (zt 1221 represents the "cheating" sequence that uses the gradients from all rounds up to t - 1, including those from rounds in my that are yet to be received because of the delays. As mentioned in Section 3, we decompose the regret as follows:
T
T
A
(egr(u) = (((o))) - Se(w))
(gt, Ft - 1))
1 - u113
2
1=1
1=1
T
T
T 1
(gt, xx - u) +
Σ
(g Tt x7)
u|
(14)
t=l
Regg (t4)
Driftr
where the first inequality follows from the X-strong convexity of ft. Next, we analyze the cheating term Regī (u) and the drift term Driftr individually, and their respective upper bounds will then be combined derive the final regret bound.
To analyze (u), first define (x)) 2/ Er= 11113 for t 2 1. We can therefore rewrite both F((z) EtEo, (9r:2) + (x) and Fx( Ei=1 (9), + (x)). Hence, applying Lemma A.1, we can bound Reg?(u) as follows:
1
Reg =
Σ 1=1
(gt, o - u)
T
= (b)+1(u)
min 22 (x) + zEX
Σ (x;) - -FA((1)4) + (9,, + F7 F7+1 (2t+1) - (f)1(u)
1=1
Σ t=1
(Ft + (9)) (Fi (x(+1) x(.,)))))) 2' (x(+1) + p((00+1))
(15)
where the last inequality holds because Fi (x)+4) < (w) by optimality of x/+1 together with the non-negativity
of 1/.
Focus on the difference between the terms F² (x;) + (gt, xt) and F; (x;-1) + (9t, ri+1) within the sum in the right-hand side of Equation (15). Applying Lemma A.2 for xtt1 with A1 = de I and w1 = Enso gr, and 22 x with
A2 A(t-1)] I and w2 = Er Sr, we have that
2
A (2t 2 2++1l1
||ا| 2 1la, + ||x - x;+1 113
< (0 riti) + A
|itt - -xel2
2
2
< ||00||2|22 - 2ttilla 112 2 +
||ا - =x113
2
14

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
where we used the Cauchy-Schwarz inequality in the last step. By straightforward calculations, can show that the above inequality implies that
2/1 - 1 S X(21 - 1)
|07 xell2
2|1ge112 + 1|07 - xx sel12.
+
(16)
221 -1
X(21 1)
We can leverage this inequality show that (F. (xt) + (g. x;)) (F7 + ((+1) 1 (g), 22 - xit1)
(F) S (+
1 119.11a112z 2;+1ll2 ll2
(Cauchy-Schwarz)
2 2e
||aellall0t mxl12,
(Equation (16))
X(21 - 1)
where the first inequality is due to the optimality of x with respect to FÝ. Plugging the above into the bound on Reg+(u) from Equation (15), we obtain
T
21 12
(e) S (n)
+
+ l1g: 12lll - xellz + (b((at+1) - (
A(2t 1)
A
T
T
2 2119. 12
A
1st - w1/2 +
Σ
+ |1allal1 - xell2 2 2111211 -xxel3
2
A(21 - 1)
1=1
1=1
G2
2
u1/2
Σ
G
| xx ll2
2
π
2t -1
T
G²
T
$ 2 10 u u
Σ
(2T + +)+
| xell2
(17)
X
where the equality is due the definition of the while the second inequality follows from ||9:|12 S G by Assumption 2.3.
Observe that, given such a bound on the cheating term, now have to consider three different terms shown in Equation (17). While the second one is a desirable logarithmic term, and the first one is negligible since it will be canceled when plugging this bound on Regy (u) into Equation (14), the third one needs some further analysis. Interestingly enough, this latter term involves a difference between r and Fy, in an analogous way as in the drift term Drifty. We indeed show that we can handle both terms in the same way.
We thus move to the analysis of the Driftr term. One can immediately observe that, by Cauchy-Schwar and by Assumption 2.3,
T
T Σ 11ll2lllz 1=1
T
Driftr Σ 1=1
(gt, I 2t) S
zz 1l2
G
Σ | xell2-
(18)
While it immediately follows that || x1l12- 0 by definition of zj. we require some additional effort when studying the other norms ||=; Zt 2|/ for 2 2. To this end, we rely once more on Lemma A.2 for x; with w1 = E Ir and 22 = Fe with w22 = ΣrEo, Ir. using = (L - 1) T, and show that
A(t ||;
rell2 | 2rl S
Σ gr
Σ gr TEm+
2x(t
1)
rmm,
A-1
We can thus rewrite this inequality in the following way:
Glmel X(-1))
|| xella
Σ 9r
5
(19)
X(L 1)
X(1-))
TEm,
rEm,
where we used once again that 11 G by Assumption 2.3. The above considerations consequently imply that the sum of interest for bounding Driftr satisfies
G T
Σ
1 xell2
mg
(20)
2
15

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
The sum on the right-hand side of the above inequality can be immediately bounded
m2
o max
Σ
S mmxx In (2T)
(21)
by definition of max- Furthermore, by using the fact that Exselmm S (1 1)2 since m, S [ - 1] for any 7, we can prove at the same time that
T
Σ
m4
mg
mel
S 2
Σ t=1
mmel= S 62 deot
(22)
(=2
1)²
t=
EESs
where the second inequality is due to Orabona (2025, Lemma 4.13).
Combining all the results gathered so far, finally derive the overall regret bound as follows. In particular, for any E X, we have
A
Regr (u) S Regr(u) + Driftr
u11
(Equation (14))
2 tm
G
In (2T +1 +1)++G+ >
|, xz 2r|12 + Driftr
(Equation (17))
t=1
G2
π (2T + 1) 2G
>
||a| rella
(Equation (18))
G
2G
T
|m/
(2T +1)
(Equation (20))
x
G²
2G
(2T +1)+
min {amax In(27), 2 deat
(Equations (21) and (22))
X
0 In T + min { (maxx In T, v dhot ))
G
C. Omitted details from Section
In this section, we show the omitted details from Section 4. To do so, we first introduce the following useful lemma that will be crucial in the regret analysis of Algorithm 2. It essentially corresponds to the standard elliptical potential lemma, but here adapted the presence of delays.
Lemma C.1. Let > 0, O, and 0 < 770 S mm S.... ... S AN. For any E [N], let ag E 12 such that ||aell2 S and define A, I + $ Erst a.a Then, it holds that
2nd
TL2
OL2N
Σ Noolla Teme
Σ ||r Maaz
max
+1
In +
100
and that
N Σ
2nd N
ΦLZN N
|
Σ ||ar ||a||la,1
max
In
1 1+
1=1
Tem,
Proof. Define B, = A,, and Ct = B, D. 2-221
3 B, for any t E [N]. By the AM-GM inequality, we first show that
N
N
mmd
|aill A:م Σ Eaaallaa2
Σ
||a
1 + Σ
|ar |a-1l/r21
2
t=1
TEme
t=1
TEm.
16

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
N
mc
2
A,-1
+
2
Σ
a
A--1
1=1
TEm,
N
a
||
2
B
B
rem,
where we also used the fact that - I A,1 for any 7 < Now observe that
ma ||ael| |
ar
max
B
since |mm]|= S
deN for S N. Similarly, we can show that max
N
N
Σ
Σ
l| 1| B- Σ
ds. max
a
B
1=1 TEm,
for any [MV there are no more than d, rounds such that T my Putting these results together, we obtain that
N
N
N
mg
2
aalll B
+ 2
Σ a B
B--
I.N max
B
JSS max
Larl
|
TEm,
By the fact that ||aell
c-1
S
dL? no
we can use Lemma 19.4 in Lattimore & Szepesvári (2020) and show that
Σ Iac <00L
(OLe 110
+ Σ
min || 11l1,11(;2,, }
2n
(ØL² 1/0
[L? +1
In
L
t=1
Yoo
Concatenating all the above results concludes the proof of the first inequality.
For the second inequality, similar steps suffice to prove it, but with a different observation that now ||ae| 0- 5 min { 1, ||,ol|?;;,
} because
|aail S oi
([
(ul
(ul+ +
) at = at (-) a,a, 22 + v||a, 1/
laell
la
a 11 S $1,
a2
2 + viladl1
+ ||02
where we used the Sherman-Morrison formula in the first equality with u = n and since |1ello, S ||aello given that Ct-1 C..
For completeness, we restate Theorem 4.1, the main result of Section 4.1, and provide its proof.
Theorem 4.1. Assume that JI...., fr are a-exp-concave and let = min a a). Then, under Assumptions 2.3 and 2.4, Algorithm 2 with 0 < I 1h Σ ... I guarantees that
BG2T
Regr 0 In
+ D2 + min (Bi, (BI,B)))
where Bi = = no + ) ndmax In (1+ and Ba G2
BG2T 7)
mmel
T
Proof. First, in similar way as the proof of Theorem 3.1, we define
F((x) = Σ (gr, x) + (2()
and
F1) Σ (0. x) + (x),
TEOr
17

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
where (x) 1 + Ereo, (gr, - xz, and 4 (a) " V x,)² Observe that ay arg min (z)), and define o; E arg ze F (z) for i to be the predictions following similar update rule
while using all the information up to round - 1. Similarly to the regret decomposition for the strongly convex case shown in Appendix B, we decompose the regret as follows:
T (u) = ((((a)) S
B (tt 9t)
(tt Ft. u)
2m1
8
(gt 2x
u) +
(gt 22
xxt)
u. u.
(23)
2 t=
Regg(())
Driftr
where the inequality holds thanks Lemma A.3.
Let us begin the analysis of the "linearized" regret by first focusing on the cheating term Reg?(u). Let F/(x) F7 + (oc, 2)) and define z E arg min (z). Leveraging Lemma A.1 with & (gt, 1), we show that
Regī Σ
(g, - u)
= 07+1(u)
min
(x) + Σ
[ (x]) - Fit (Ii+1) + (g), + F7+1 (x7+1) - F7+1(u)
Zed
1=1
S S07+1 (u) +
[ (x;) + (ge, x))) - (FT + Vi+1(1541) + (xt+1)
< 50041(4) +
[F((z]) F((D + +0074)+)) - (2t1(1
(definition of Fy and 2t))
S 01441(4)+ M
- (((at)-F((c)))
(24)
where in the first inequality we used the facts that (1+1(174)) S F7-1(u) and that v is nonnegative, while the last inequality is due to ebt (2++1) $ (x7+()))1) Applying now Lemma A.2, have 2| a!llA-- I Ilaellazi, where
A-- = - - 9- - This further means that
F( - (x1) < (V)( - 24)
(convexity of FD)
(xt) + gc, 2t 21))
(definition of F?)
(un, at =ad)
(first-order optimality)
min ||ae - 2//12, 119. (leella |A, ||2 x'Ells-11
Ccauchy-ccwwrzz inequality)
S min min((G)) (GD, [1.. 1171, || - 2/ [m
(Assumptions 2.3 and 2.4)
GD,, [1 12
s min
(25)
We now focus on the sum of terms on the right-hand side of Equation (24). Because T)t is non-decreasing by assumption, we have
T
T
Σ -
<
Σ min GD, 11 11,
(Equation (25))
min GD. 1
l1 l1sell 1+
(7--1 2 1)
18

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
T
I max
GD.
min
{ 1,
18 14 (
1=1
s <(DD+ 3)
PGTT)
nln 1
(26)
mnoo
where the last inequality follows by Lattimore & Szepesvári (2020, Lemma 19.4). Combining the previous inequalities, we can show that Regī (u) satisfies
Regī (u) S 2 (++((u) (u) +
(((o))-F(((1))
(Equation (24))
8
1
BGTT
S 1z (1+ +
(1gt (0)))==x)))² xz1))+ + GD+
n in
1+
(Equation (26)
3
rorlo
7F 2
1uu122
+
8
Σ
I
(gg, u - xz))²+ + GD+ n In 1+
1
3G
(27)
2
B
nurjo
1=1
where we simply replace i1+1 with its definition in the last step.
We thus move to the analysis of the Drifty term. Using the Cauchy-Sehward inequality, we have
Driftr Σ (gc, Ft x11 2 l
A, A 1| - 2:1lA
(28)
Applying Lemma A.2, we obtain that
(xe) F2 (x;) 2 2 |10e - -2,1 and F((x;) - F1(1:)) 2 2 11:0 x; =ll.
where Ao, = - + Et 9-9.- Summing the above inequalities, and replacing F7 and F, with their definitions,
follows that
1|0, - 12,1, + +22122 112 27 11 11
2
(9+ vz)) - Σ (gr, xt)
Σ (gr - Σ (0r, vi)
TEor
TEat
+ 2
3
Σ (gr, 1z - xz,)² -
Σ (gr: xt xzT)
1-1
Σ
(gr, xz - -x7) 2- Σ
(gr, xz,)
TEo.
TEDe
<
(gr, It- x²7) + 2
(gr, Iz - -Ir)
(gr, xTT?
Emm
TEm:
Tmm
3
Σ TEME
(g,, Dt xz²) +
Σ
(gr: Dt -z²) (gr, It + x -2xx7)
TEmi
Kgr 24 -17i|= +
(gr, It 2;)1 199 21 xz - 2xxx))
TEME
< (1 + 2GD3)
Kgr, 2t siإ
(Assumptions 2.3 and 2.4)
TEme
< +1 2GD3)
Σ l1g ll Arth
|| - 2illa-
(Cauchy-Schhe Seecha-S inequality)
Trm,
< 5
Σ
l1 ||+ )
110e x2 Am
(8 sGD)
4
19

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
2
|
l
27 AlA-11
T TEm
Rearranging the terms, we can obtain that || xillA Al S S4Erem. 11 1,0 Plugging this inequality into Driftr, we
have
Driftr
1| - xz 1
(Equation (28))
Issella
Σ
11
Teme
G
3TG
<
8d
+
In
1+
(29)
%
3
Tujjo
where the last inequality is due to Lemma C.I. On the other hand, we can also bound Drifty in a different way:
T
Driftr z
Σ
- ||are - 2 |lA
< 4
11 1l بدد
Σ
l1 1orllaaz
t=1
TEme
mel
I 4G
(30)
?/--1
where in the last step we use the fact that ||9.||3 bounds together, finally obtain that
A,1
A,
G² for any [T], also due Assumption 2.3. Combining all
8 Σ
Regr(u) S (w) + Driftr
(tt - u, 91)²
(Equation (23))
2
BGTT
||u|6
+
GD +
nn
1+
+ Drifty
(Equation (27))
2
B
11700
BG2T
|| 3
+
GD +
nn
1
2
3
1i7lo
G²
1)
3GT
T
[
+
4min
2d
In
1
G2
(Equations (29) and (30))
3
1/0
1hn
1/2
1=1
SGTT
0
In
1
+ Dr D2 min {a,, B2l
(Assumption 2.4)
nonn
where
Bi
2
nddmaxx In
(1+
3GTT
and
B₂
G²
mel
170
non
M--1
are defined as in the theorem statement, and we used the fact that GD < D-
The following corollary is a restatement of Corollary 4.2, which shows that via an adaptive tuning of the learning rate used by Algorithm 2, we are able to guarantee Omin In T, v 1) regret.
Corollary 4.2. Assume that fi,..., JT are a-exp-concave and let 3 1 mint AGD or.. Then, under Assumptions 2.3 and 2.4, Algorithm 2 with the adaptive learning rate πt minfa,, b,} + where at and be are defined in Equations (5) and (6), guarantees that
Regr 0 (0
In 1+ 3GTT
+ D2 - min (C1, (c),CC)).
20

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
where C₁ = 1) (G + +1) ndmax In (1 + BG²T and C2 = (G² + GD) (Vdrot + 1).
Proof. The adaptive learning rate given by 7/ and 7)t = min(ai, bt} + for all 2 1, where we recall that
04
c (++))
1 ndmax In I
3G*T
and
b.
G D
Σ |msl
|imel 1
GD
Note that Tt is non-decreasing since ar and be are non-decreasing. When aT S by, we have
(u) =
GD + B)
1 1) n In 1+ 3GT
+ D²
(50
2D
8
(
G2 + 1
ndmax In (1+ BGTT)
(31)
where ||u|22 S D by Assumption 2.4. When or 2 by, we instead have
(u) S GD+ 3) nln 1+ BGT
T
D2
GGD
Σ
m +
T
Ilalll 1|00 - uillar
+
Σ
11
l - aill--11
t=
where 7" is last round a,- by. Hence, have
-ل 111re- - 2/llA--1 S G2 (++ +
1
nd In 1+ max
BGTT
(Equation (29))
7
< 8G
me + 1m |
+
t=l
S 8G2
mm/ + 1
(32)
Regarding the remaining rounds until T, we can also show that
T
Σ +1
1-111-22100 - - S SG
Σ
m4
(Equation (30))
7--1
(=
D mll
< 4G2
Σ
t G
Σ ==
(-1
mmal
|ma-1++1
D|mel
< 8G2
Σ
( GV El
Ei [mg
T
< 8GD,
[m|]
1=
< 8GD,
mme]
(33)
where the last inequality due to Orabona (2025, Lemma 4.13). Combining the above three inequalities together, we have
SG2T
Regr (u) < GD +
In 1+
+ D2 + +8G2 + 9GD)
Σ mel + 1)
21

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Finally, we obtain
S
Regr(u) -
GD +
nh
1
+ +D2
[
+ +min {
(
+8)
(A max
d
dST
max
n In
11 PGPT)
(8G² + +9GD) (Vdaa+1)
G
B
0
1 In
+
D22 + min (Ci,Ca)),
n
where
G +1 G2 + 1 111 nd In 1+ 3
D
C =
n
and
C2= (G² + +GD) (Vdrot +1)
as in the theorem statement.
D. Omitted details from Section 5
Here we present the omitted details from Section 5. For completeness, we restate the main result (Theorem 5.2) and provide its proof.
Theorem 5.2. In the OLR problem with delayed labels under Assumption 5.1, Algorithm 3 guarantees for any 0 < no S
7 S Ty that
1T 2
||ul12 + nY In (1 1+
Z2T
Regr(u) S
7um
0 Y2 (o min {Mi, M23))
where M1 = ndmax In(1 +1+
2 Von
and M2 = 22 E/=1 mme
Proof. We begin by defining
F((x)= Σ (2r,2) + (x(x)
and (T Σ Ue (2) + ve(z),
TEDr
where (x) = 1 (2., 2 and define 2t E arg z (xr for 1 to be the predictions following similar update rule while using all the information up round t 1, including the labels y- for rounds T m, that the algorithm is missing because of the delays.
|x11 for t E [T], and we let vhr+1 = thr. Observe that æt E arg min F((x),
Similarly to the regret decomposition for the strongly convex case shown in Appendix B, we rewrite the regret as follows:
(((()))) = - (((())) fc(w)) + Σ (f((G)) - f((z))
Reg = t=1
(34)
(u)
Driftr
where (u) is the cheating regret for the iterates ....... mt. while Driftr is drift term that quantifies the influence of the missing labels on the regret because of the delayed feedback. Note that, contrarily other regret analyses in this work, here Drifty is also affected by the clipping in the definition of Ft-
Let us first analyze the cheating regret Regī (u). By the definition of the loss f((x) = 1/2 ((z,, x)) - y1) we can rewrite the
regret in the following way:
1 T
T
T >\2
(eg
((((tt) Se(u))
- Σ
(- Me (t) + (xr, w/)
(z,, u)²
(35)
2 tml
t=1
[=]
22

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
We can move our focus the central sum, which essentially corresponds the regret of the same sequence (z)))21 against the comparator u IR", but with respect the linear losses + -y (z), Additionally define
Ff(2) = (x) - ye(2,, æ)) for notational convenience. Hence, we analyze the above-mentioned term by applying Lemma A. which yields
Σ (- (2). 27) + u2)
min 1/2 (x)) Σ (x;) F1 -vlle, FF+1(17+1) F7+ mERn
T 50T+1(1) +
Σ
(x;) Fitr(1841) - (e, mitt)]
T
T
= -TTIl + Σ
(F)( - F((eit1))
Σ
- - (1(()(+1)
1=1
1=1
T
= (1) +
Σ (F)(zt) - F((()+1))
-
(2,, x7)²
1=1
1 Σ 1=1
S 2 (1)
Σ (F)(ot)-
(ze, 2;)2
(36)
where we let z E arg min (z);; in particular, the first incquality is due to the fact that 1 S (u) and that 1/ non-negative, whereas the last equality follows by definition of the and at =
Consider now any term (xt) (x() in the sum after the last inequality and let A, = E ž, Applying Lemma A.2 for 2 and 22 27 with A As, we derive that
yel 2
| x'ilas S
|| ||
(37)
We can now use this fact to show that
F( F(() < (vF(( x7 a'i)
(convexity of F3)
(VF) (xi) 41 x² x1))
(definition of F?)
S 1n - =z,)
(first-order optimality)
< well ||| A; -1107 ll
(Cauchy-Schwarz inequality)
1
||
(Equation (37))
2
y²
2x 11
1|
(38)
2
where the last step is consequence of yel S Y by Assumption 5.1. Further notice that || 1a S || since A Ac, as well as
|| A, S 2. (ndl - -22,) = 2T
244 + The
11 S 1,
1/t
2
2t
T)
1/ + ne nel
1/t
using the Sherman-Morrison formula the first equality. Therefore, we show that the sum of the terms involving F/ is
T
Y2
T
-
<
2x 11 AT
(Equation (38))
2
Y2
T
<
Σ
min 1,
1| A-
t=
23

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Z
S
ny² In
1
+
(39)
7/
using Lemma 19.4 in Lattimore & Szepesvári (2020) at the last step. Then, combining together all these observations, we can bound (u) from above and obtain that
Reg7 (u) S
(F((z]) - Fx(())) + (b)(2))
(2 u)²
(Equations (35) and (36))
1=1
1=1
I nY In 1 T²T)
+ (b)(t)
Σ
(2,, u)
(Equation (39))
Z²T
= T |uu1 + nY In
1
(definition of v/T)
(40)
TJ
Let us now consider the drift term Drifty from the decomposition in Equation (34). Define T= [t E (T] f(
fx())) to be the rounds when H. is worse than oz with respect to the square loss ft. Moreover, recall the definition of P: max |-| as the threshold used for clipping in the definition of Ty. By the convexity of fi, we immediately have that
Driftr S - S
(f. 21)
((ee, ((2e, Fx)) 22). (41)
TET
IET
IET
Now, we distinguish the two following cases for any L E TT:
f(,))) s f(()): thus, if (ze, Tx) S y it must be the case that (2), 0z) S (2,, T2), otherwise if (x,, Yt then
(2), 2 (21, ; in either case we have that
(1), v1) 3.) (2e, 21)) s ((ze, Tz) v1) (122, (2.,
< (lpil + +lvel) (2l) F0 x771
(triangle inequality, definition of 2y) (Assumption 5.1)
2Y (2t, Dtz x;)1
< 2Y L a, 11 xz A
(Cauchy-Schwaal
(42)
f(())) > f((z)): here it must be the case that 3. # Fz, B1 (Ze, Rr) 2 0. and |yel > Pe (otherwise, clipping would have only decreased the square loss fi); since t T implies that (2,, 2t) vil K2,, F2) yel. it follows that
((2. ye) ((2,, Fo) xi)) < K2, To) (01( Mil + 1ee. vel)
(triangle inequality)
s 2((2,, Tz) y1)²
2lvel - 1(ze, 1) 2
(2, 0)
-2(lvel - p
(12,,, Fi)] = pt)
2|yal?.
(0 S Pt < (y:))
(43)
Given the above remarks, let Ti = ftET fe(z,) S fz()) be the subset of rounds in T when clipping does not worsen the value of ft, and let Ta = T \ Ti be the remaining rounds in T. Then,
Drifty S (((,,))) - ye) ())(()))))))) Tx) (2,,))) +;)) < 2Y
1 1 |12 - -=;--=10 1l., +
Σ lyvl
(44)
SET
NE
TET2
At this point, for any round E Ti interested in understanding the behavior of ||=||lA51 |lare x Il Applying Lemma A.2, we have that
||a.a - 2211%,, S
1 Σ
V=(2,, - -x4) S 2
Σ
Iu- /00lllztlaa - zellA, 1
Y
Σ || || - -
2
2 TEm:
TET
TEm.
24

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
where the second inequality follows Cauchy-Schwarc while the last one comes from Assumption 5.1. By rearranging terms in the previous inequality, obtain that
Y Σ ||
|| ll S
(45)
TEMR
Recall that we define dax mr min - as the maximum delay that has been perceived up to round t. Hence, we can now bound the sum relative to rounds in Ti from above as
2Y
Σ IT
|
|,g - x, S y² Y²²
Σ
|
Σ
(Equation (45))
IET1
TEmy
y2
zella,
||
TEme
If we now adopt Lemma C. 1, we have that
Z²T
Σ
|
S 2nd In
1
77072
t=1
TEma
while at the same time we have
T
|m
Σ || S 2
where we used the fact that ||aallA, S
2 for any E [T]. Thus, we have that
2Y
2 | |0, lllla, I Y min 2nd max
In 1
ZTT
z2
T
mg
(46)
77
ET
If we instead consider the sum over rounds in T2, it is possible to further bound it from above and relate to the rounds for which the corresponding label does not belong to our estimate for the label range given by Pe- Indeed, if we let R {t [T] I > pt} and given our previous remarks about Tz, we have that T2 C R. Now let Q1 min([log, Pt] Pt 0, [T+ 1]} and Q2 flog2 PI+1]. For convenience, define I, [2 22+1) for any Then, for any E R. there exists j. E (91...., (2) such that |ya| E IJ.- Moreover, if we denote by Vj E T 1] as the first time when Pv, I, for any E (q...., 92), we can further show that any t E R has to be such that / E mæy, -1; if it were not the case, Yr would have been observed before time Vj, which is a contradiction because yel > P. for any T < Vj.. All things considered, we can derive that
j E (91,...,
92
42 Myy- -1|
Wel 2
We
<
Σ
Σ
1ye 2 <
Σ
2
EER
i=qi
rEmuy
92
8
32 max
Tmax
221+1
max
192
+1
11Y2 max
(47)
3
j=
Combining all the results gathered so far, we can finally derive the overall regret bound follows:
(u) < Reg (u)
Driftr
7T 2
| 2 In
1
2²T
+ Driftr
(Equation (40))
n2
Z²T
<
| n2 In
1
+ 11Y2
0 max
22 Σ
lella; || xilla. (Equations (44) and (47))
2
tET
(48)
25

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Z²T
mr 2
| ny²
In
1+
+
11Y 0 max
non
T
me
+ y min 2ndmax In
1+
2
(Equation (46))
10n
The following corollary is restatement of Conollary 5.3, which shows that further achieve (min max In T, Vd }) regret guarantee via adaptive tuning of the learning rate of Algorithm similar to the one adopted for Algorithm 2.
Corollary 5.3. In the OLR problem with delayed labels under Assumption 5.1, Algorithm: with the adaptive learning rale ? (min b + 1). where or and be are defined in Equation for any 0 guarantees that
Regr
+ nY² In (1+
1+
Z²T
+ O (Q1,
2
7/2
where Q1 (r/lulli + 22) ndd In 1n(1 Z²r qm
and Q2 (7 uu + (Z + 1)Y?) Vdvat.
Proof. By performing similar analysis in the proof of Theorem 5.2 up Equation (46), for any time threshold r [T] we can actually separately analyze the time ranges r" and {-* ,,...,T' Th in analogous way as in the proof of Corollary 4.2, and have a bound of the following form:
ZTT Too
T
|m
2Y Σ IZ
12 |-t-- 27 Al. S 2²
2nd In
max
1+
+ z
(49)
t=y
Then, we use an adaptive tuning of the learning rate in a similar way as performed for the proof of Corollary 4.2. In particular, we define
ZTT ym
a: 2nd In 1
and be Z
Σ ms
and, for any 7 0, we set vio = and r2t = (min br} + 1) for any 2 First, when or S by we have that
7/T |/4| + n In
1+ Z²T
x2 [lomax + 2ndmax In 1+ Z²T 221)
Reg, (u) 5
(Equations (46) and (48)
7m
m
||ul2 1/r + nY In
1+ Z2T
dd (11+2n 1 m
221"
<
(a S dmax)
7m
< 2|
Z2T
Z²T
+ n In
1+
11112 + (r/luu13 + 2X ndmax 1
7
7m
< r||u||2 + n In
Z2T
2²T
1+
+ (7/ + 13Y ridmax ) In 1
On the contrary, when or > br, we let 7* be the last round such that a,- S b,- and show that
|ull mr + n In (1 1+
ZTT
11Y max x2 ( 2nd In
In(11
z²T
[mm]
Regy (u) <
11
Z
an
mm
W
(Equations (48) and (49))
||u|[ <
2 7/ + n In (1+ 72T
T'
[m.]
11Y2 o max + ZY2
Σ
m + Z
(a.- S by.)
yn
26

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Pr + nY In (1 1+
Z
ZY²
me
+
11Y o max
m
+
Σ
2
7n
7
1= +1
mmm)
(definition of m))
| 1/
+ n. In (1
ZaT
1
11Y
max ZY2
Σ
ml + +2,
Σ
|ms
2
yn
(Orabona (2025, Lemma 4. 4.13))
|u|| 1/ + ny² In
Z²T
1
11Y2 O max + 22Y2 v /22rot
2
7n
1+ 7
Pr + nY² In
+ 2(11 + Zjy² / 2deot
(Lemmaa A.7)
2
> 11 2
ZTT
$ 2 (1 + 7 ZV (oo)
+ ny In
+ 2(11 + 2) /2doot
(definition of w/)
ym
Considering the conditions in each of the two cases together with the definitions of ur and by this concludes the proof.
E. Online mirror descent for delayed OCO with strongly convex losses
In this section, we prove that the following online mirror descent (OMD) algorithm achieves regret guarantee whose dependence on the delays is of order min mmax In T, vdvot) j. similarly to Algorithm 1. To be precise, an OMD-based algorithm which handles delays was initially proposed by Wu et al. (2024) in their Algorithm However, Wu et al. (2024) only manage show that this algorithm achieves regret O [dmaa((² + In T
dupp under Assumptions 2.3 and 2.4. Here, report its pseudocode in Algorithm 4 and we provide improved regret analysis for it. Not only do we provide significantly better guarantee, but we also manage to lift Assumption 2.4 and only require the boundedness of the gradient norms via Assumption 2.3. The key to achieve these improvements simultaneously is fundamentally different and more careful regret analysis.
Algorithm 4 Delayed OMD for strongly convex functions
input strong convexity parameter À > learning rates 7): for all [T]
initialize #1 E X
1: for = 2, do
2: Play It
3: Receive
(x+) for a 00+1 \ )0
4: Update Tz+1 = arg min Σ (gr, + nic 111 xz11.
ZEX rEq111'00
5: end for
Theorem E.1. Assume that fI...., . fo are X-strongly convex functions with respect the Euclidean norm |1-1|2. Then, under Assumption 2.3, Algorithm 4 guarantees
Reg, = - -0(20 (InT + min {o In T, //ot 3))
Proof. We begin with decomposition of the regret that, similarly to the proof of Theorem 3.1, leverages the strong convexity of losses fi,..., fr and attempts to isolate the discrepancy in the information available the learner because of the delayed gradients. However, this decomposition differs from the one in Theorem 3.1 since the algorithm updates its predictions differently via mirror descent. Our approach follows the idea of framing such information discrepancy via optimism (Flaspohler et al., 2021). For notational convenience, define ÿ1 0 and 0r+1 + Σ Eeor44 Vor Or 9r for any
l 2 1. Note that, by definition, each Ør is equal to
gE
0r+1
..) - s=1
Σ ATE0041
9-
9s
Σ 9, 8Eor
9, - Σ 9. Σ
(50)
SEm
27

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
and consequently Ør+1
since m1r+1 0. This definition of 9t allows rewrite the "linearized" regret as
T
T
gt, Ft - u) =
Σ
Ir.
- u
+
9t
9641,
(51)
IE los
1=1
and to have that, for every round t
Σ
gr, Jt
Ze+1
(gt 9t 91+1.22 24 Te+1) (9)
- I(41) + (9++1. T141).
(52)
TE00+11 /or
Moreover, according to the standard regret analysis of OMD (Lemma A.4), we know that
Dr, Tt
- (Iu T)t
It 112 ||u xe+1 1| || xet1
Σ
gr.
Te+1 )-
(53)
TEELL1 Yo
The above observations then make it possible to bound the first sum in the right-hand side of Equation (51) as
Σ
1
[1u
22l2 - ||ue 2++1l12 112 |1are xe+1 113
9r,
77t
voo
Σ
Fr, 2t Jz+1
(Equation (53))
| 10t
(Iu Iz 1/2 ||u
2441112 1 - 2441112
1
T
T
+
(9) Te xt x1+1)
+
00+1, 22 - xe+1)
(Equation (52))
1=1
T
[|u rell - 111 x2+1
|| - x++1 12
1h
Σ (gt T1, Ii 21+1) + Σ 19 x1)
+
11)
(1T+,,
T
|1 - 12 - ||u Zz+1 - 1|5e - xz+ 113))
1/1
1=1
T
T
+
[gt Tr, It xt+1) +
Σ
(0+ Tee 2τ)
(54)
t=1
where the second equality follows by carefully rearranging the terms the sum ΣT" (0++1, - -k++1), while the last equality is due to "1 9r+1 by definition.
At this point, we can rewrite the regret in the following way:
Regr(u) (f((z))-f((z)
- f((w))
T
A T
(gt, Ft. - -u)
Σ
[24 21
2 1=1
Ir.
gt
gt 10-1. σ4)
~
(Equation (51))
2 1=1
1=1
28

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
u 2
|
I2+1
20
Ie+
T
T
9
Dt.
22+1)
1
ull2
Np
2
t=1
(Equation (54))
111
Tell3 - -1|u xz+1
A T
11,r F 112
22
u112
+
Σ
[ ge, 21 x2+1)
9/
t=1
n
11 - Fe+1
(1122) - u113
1 u1(5) - 1004 u113)
+
(g
gt, 22z xet1)
2
?7 (definition of m))
XT
T
11 xe+ 112
|rr+1 uu12
+
(9) It 2141)
2
11
1=1
1,2e Fe+ 11
Σ
(g) Te, It l(+1)
(55)
7
where the first inequality holds because of the X-strong convexity of ft-
We now focus the right-hand side of Equation (55). Applying Lemma A.2, we can bound from above the distance between subsequent iterates:
|| xet1ll2 S mellge + Te+1 Hell2 7/
Σ
9r
S Gn (1ot+1l-11 -
(56)
1EOL11
where the last inequality follows by jointly using the triangle inequality, the bound on the gradient norm (Assumption 2.3), and the fact that o, S 0.+1-
What remains to analyze now is the distance [|ge Dell2. and a direct calculation allows us to show that
1g: - Tell2 = 9t
+
Jr TEm,
S
G(Imal + +1)
(57)
2
again by using the triangle inequality and Assumption 2.3.
Applying Lemma A.5 with Equation (56), show that the each term of the sum in the right-hand side of Equation (55) satisfies
Tr. 2t xe41) ||, x < min {Gne De l12 0041l
(gt
(o.1) mellge 9t 12)
(58)
7/
Therefore, starting from Equation (55), we are able to derive the final regret bound:
Regr (u)
De 12119 + 0e+1 Fe l
(Equations (55) and (58))
1=1
2G
|1g. 3r 112((1++111 lorl)
(definition of m))
2G
T
(/mel
1)((04411 lo:l)
x
Σ
(Equation (57))
A
t
t=1
Crucially, what remains to analyze is the sum in the right-hand side of the above inequality. We can first show that
(mell + 1)(
loel) < (amax + 1)
10 1l loel
(definition of dmax))
0
29

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
00+1
lol
I max + 1)
(0r+1 S [t]
00+1
t=1
(10041 - 10c))
maax + 1) Σ
(100011 - 10.1)
t=1
S (max + 1) + In)))
(59)
where the last inequality follows by Orabona (2025, Lemma 4.13) and the fact that E (104t1) -lot)) lor+1l T. Second, can also bound such sum an alternative way:
T (Imel + 1)((++11 - lorl)
me mel((ot 10x1)
(01+1 loel)
t
t
mel(
10x1)
T
(10+111 - orll)
(definition of o.)
===1
(10+11 l0,1)
|eel(o0411-- 10o1)
In T +1
mel((
|m2411 - 1-mmm + +
(ool + |mel t for all
|mmel mme((
[me+1
+ In +
t
mmell
|m
|MT+1l
T
|me]
m [mx]
+ |m1/
+
Σ
+ 7
t
1
t=2
mel
|m
me)]
In T +1
(definition of m.)
mmel
(mm-11
11)mmll
|me-1 [11mg]
+ +n +
t-1
(m++1 C m. U (t) for all t)
T mm + In +1
2 that + In +1,
where the last inequality follows by Equation (22). Combing the above two inequalities, we finally obtain
202
2G min f (1 + In T) 2 2ddeo
Regr(u) < (1 (n+
0 ( + min {o (max In V /dott) )))
6
InT+mmn/
F. Additional experiments
We consider real-wood worldw dataset mg mnglccale from the LIBSVM repository (Chang & Lin, 2011). This dataset has 1385 samples and each sample has 6 features with values in 1-1, 1] and label in [0, 2). The experimental setup, including constructions of losses and delays, follows what already done for the experiments in Section 6. Figure 2 shows a similar behaviour of the algorithms as already shown in Section 6.
We also designed a non-stationary environment as follows. The generation processes for the feature vectors, as well as the definition of the loss function, remain the same as the environment Section 6. However, we modified the generation of the
30

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Samngle coman, Baae Vifu
Expeverave dasn C. yllle
OLE denr &ha
33
50
30-
30XI-REC
BOLD-OSS
BULD-VAWF
25-
Delanad FTRL.
40
Delaust OXS
40-
Delapot VAWV
20
30
300
45 15-
62
20-
201
10-
104
30-
08
Stoongle conver deas 26 V/due
Expeoinnon:: dess v/d...
dass 20 v
250
SUMD&RSC
BOLD-UNS
210
BOLDWVWW
Detaed FTRL
ONS
Isheval
ROLDO
150
60
100
40
70
0
1200
1200
800
1020
200
Figure 2. Comparison with relevant baselines. The shaded areas consider range centered around the mean with half- corresponding the empirical standard deviation over repetitions.
label y/:
3/1 = (z,; 0z) + ct,
(60)
where the latent vector 0g alternates every 30 rounds between the vectors 1 and O. This periodic change introduces non-stationarity, reflecting scenarios where the optimal action shifts over time. The delay d, is independently sampled from distribution that alternates every 30 rounds between geometric distribution with success probability T-1/3 and
uniform distribution over the set {0, 1, 5}. Additionally, we also modify the noise term inspired by Xu & Zeevi (2023). Specifically, we flatten an abstract art piece by Jackson Pollock and take consecutive grayscale values in [o, 1] as the noise eg. Figure shows that our algorithms again perform the best among all the benchmark algorithms.
31

---

Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Stronely adi
Exp coccaav, adv
OLR. adv
60
60
175
SOMN--R8C
ROU/N-VAW
50
130
Delene ONS
50-
Ditaned
DOLU3OG0
75
201
25-
20-
700
1000
17:0
500
1000
210
4.91
63.43
$50
1000
X30
400
05.0
1000
Strougly conver adu
adh
OLR, ade
FOG
DOUD ROLD--AWP
100
60
BOLD-OGD
300
D14gpe CNN
60
100
1101
75
30
25-
Figure 3. Comparison with relevant haselines. The shaded areas consider range centered around the mean with half-width corresponding empirical standard deviation over 20 repetitions. top plots correspond to T 1000, while the bottom plots correspond T 10000.
32


Reviews:
[{"review_id": "r800uJzWiO", "reviewer": "Reviewer_CNFg", "summary": "The authors present a FTRL-based algorithm that achieves logarithmic regret for strongly convex loss functions. More importantly it depends on $\\min(\\sigma_{max} \\log T, \\sqrt{d_{tot}})$ which improves the previous results $O(\\sqrt{d_{max}} \\log T)$. The key idea is to have a regularizer that uses all the previous timesteps and not just the ones with observations. This helps bound the difference between the update $x_t$ with delays and the hypothetical $x_t^\\star$ with no delays.\n\nFurthermore they present an algorithm, inspired from ONS, for exp concave losses, which is the first algorithm to give regret when there is delay in the observation of the gradients. They achieve $\\min(d_{max} n \\log T, \\sqrt{d_{tot}})$.\n\nFinally, they present an adaptation of Vovk-Azoury-Warwuth for online linear regression, which is also the first algorithm to solve it with delay.\n\n## update after rebuttal\n\nBased on the successful adversarial  experiences, I decided to maintain my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q:** Can you run the experiments on more adversarial settings?\n\n**A:** Following your suggestion, we run our benchmark algorithms on the following more adversarial (i.e., non-stationary) environment. Specifically, in this environment, we set the time horizon as $T = 10000$ (as to also address a concern by Reviewer jw1R) and we partitioned rounds into roughly $\\log_2 T$ phases where the length of phase $s \\ge 1$ is $2^{s-1}$. For $t\\in\\\\{2^{s-1},\\dots,2^s-1\\\\}$, when $s$ is odd, the feature vector $z_t$ is sampled from the multivariate standard Gaussian distribution with values clipped to the range $[-1,1]$ and the delay $d_t$ is independently sampled from a geometric distribution with a success probability of $T^{-1/3}$; when $s$ is even, each coordinate of $z_t$ is independently and uniformly sampled from $[-1,1]$ and the delay $d_t$ is independently and uniformly sampled from the set $\\\\{0,1,\\dots,5\\\\}$. The loss function is designed in the same way as already described in Section 6 of our paper for each of the three settings, except we additionally clip the standard Gaussian noise to $[-1,1]$ to have a bounded gradient. You can find the additional plots for these experiments in the \"Adversarial Data\" folder at the following anonymized link [https://anonymous.4open.science/r/Supplementary-experiments-EF2D](https://anonymous.4open.science/r/Supplementary-experiments-EF2D). We will integrate these plots with appropriate comments, as well as a reference to the source code, in the next revision of our paper.\n\n**Q:** Typos at lines 583, 628, and 850.\n\n**A:** Thanks for carefully pointing out these typos. We will fix them in our next revision.", "claims_and_evidence": "They provide proofs for all their claims and show with an experiment, how their algorithm performance does depend on that minimum: $\\min(d_{max} n \\log T, \\sqrt{d_{tot}})$.", "methods_and_evaluation_criteria": "They use regret as a metric which is standard. Their algorithms also follow standard existing algorithms.", "theoretical_claims": "I checked the proofs of the strongly convex and exp-concave claims. I did not check the proof of the OLR problem. I did not see anything problematic in the first two.", "experimental_designs_or_analyses": "The experiment setting is a good one, except for the data generation that is NOT adversarial but stochastic with a fixed distribution. It would be way more compelling to use a distribution that changes, potentially in a way to disturb the proposed method as much as possible.", "relation_to_broader_scientific_literature": "The algorithms build on existing ones for standard OCO without delay, i.e FTRL, ONS and VAW.\n\nThey then modify the regularizers and the learning rate to adapt for the delay in feedback, which is new.\n\nTheir algorithm for strongly convex has some similarities with Wan et al. (2022) and Wu et al. (2024) with the major difference in that they update $x_t$ and every timestep (even in the absence of new gradients) and use a regularizer that cover all previous timesteps, not just the ones already observed.", "essential_references_not_discussed": "None that I can think of.", "other_strengths_and_weaknesses": "Strengths:\n1- Provides the first algorithm for  exp-concave and OLR cases\n2- Strictly improves  previous methods for strongly convex by having a bound that depend on the minimum of two quantities that, depending on the setting, can differ significantly\n3- The paper is clear and quite easy to follow\n\nWeaknesses:\n1- The experiment is fully stochastic and not adversarial enough.", "other_comments_or_suggestions": "Typo\n- line 628: $|m_{t'}| \\to |m_{t^\\star}|$\n- line 850: $d_{max} \\to d_{max}^{\\leq N}$", "questions_for_authors": "- can you run the experiments on more adversarial settings?\n- minor question: On line 583, why use $A_1 + A_1^T$ for the Hessian instead of $2A_1$ since the matrix $A_1$ is symmetric?", "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": "rAOlE3viuG", "reviewer": "Reviewer_jw1R", "summary": "In this paper, the authors consider online convex optimization with delayed feedback, and aim to exploit the curvature property of loss functions, i.e., strong convexity and exp-concavity, to improve the regret bound. Specifically, for strongly convex functions, the authors show that a delayed variant of follow-the-regularized-leader can obtain a regret bound of $O(\\log T+\\min(\\sigma_{\\max}\\log T,\\sqrt{d_{tot}}))$. When functions are exp-concave, the authors propose a delayed variant of online Newton step, and establish a regret bound  $O(n\\log T+\\min(d_{\\max}n\\log T,\\sqrt{d_{tot}}))$. Moreover, the authors also consider the problem of online linear regression, and propose a delayed variant of the Vovk-Azoury-Warmuth forecaster.\n\n---Post Rebuttal---\n\nThanks for the authors' responses. I agree that the $O(\\sigma_{\\max}\\log T)$ regret bound cannot be *directly* derived by Theorem 2 and Lemma 5 in [1]. However, I still feel this result is not surprising. Thus, I keep my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q:** $T=1000$ is too small in experiments.\n\n**A:** We extended our experiments to have $T=10000$ and plan to include the new plots in our next revision. The new plots essentially show the same behavior with an extended time horizon. You can find these extra plots in the \"Synthetic Data\" folder at [this repository](https://anonymous.4open.science/r/Supplementary-experiments-EF2D).\n\n**Q:** Comparison to the black-box method (Joulani et al., 2013).\n\n**A:** We thank the reviewer for pointing this out. Indeed, applying the black-box reduction (Joulani et al., 2013) with ONS can achieve $O(\\sigma_{\\max}n\\ln T)$ regret, and our Algorithm 2 also requires the timestamps to compute the regularizer. However, in Table 1 we did not compare with the algorithms based on the black-box reduction due to their typical inefficiency (also shown to some extent by our experiments). Nevertheless, we will add these remarks for the exp-concave and online linear regression settings in our discussion as well as Table 1 to have a more comprehensive comparison with existing techniques.\n\n**Q:** Improved regret bounds under strong convexity and comparison with Wu et al. (2024).\n\n**A:** In fact, proving that the algorithm proposed by Wu et al. (2024) achieves the optimal regret bound in OCO with delays is one of the contributions of our work. Note that our analysis is **radically different** from Wu et al. (2024), which was crucial in deriving the improved guarantees and we believe is an interesting contribution. As mentioned in our Appendix F and Section 2 as well as in our response to Reviewers zZM9 and htSw, the bound we prove via our analysis is essentially optimal, while the bound $O(\\frac{G^2+D}{\\lambda}(d_{\\max}+1)\\ln T + \\frac{G}{\\lambda^2}(d_{\\max}+1))$ in Wu et al. (2024) has some disadvantages including: (1) a multiplicative dependence on the diameter $D$ of $\\mathcal{X}$; (2) no robustness to the $\\sqrt{d_{tot}}$ regime; (3) a worse dependence on the strong convexity parameter $\\lambda$; (4) a worse $d_{\\max}$ dependence ($d$ in their work is $d_{\\max}+1$ in our notation). The improvements of our analysis are thus multiple, with no assumption on the domain $\\mathcal{X}$ having a bounded diameter $D$, thus proving that the algorithm can work even in **unbounded** domains, the optimal dependence on $G$ and $\\lambda$ hence recovering the optimal $O(\\frac{G^2}{\\lambda}\\ln T)$ regret bound in the no-delay setting, and the improved robustness to delays given by our key observations on $\\sum_t |m_t|/(t-1)$.\n\n**Q:** Improvement from $d_{\\max}$ to $\\sigma_{\\max}$ is trivial based on OFW in [1].\n\n**A:** We respectfully disagree with the reviewer that the improvement from $d_{\\max}$ to $\\sigma_{\\max}$ is trivial. While this refinement may appear straightforward in hindsight, to the best of our knowledge, no prior work has provably achieved a $\\sigma_{\\max}\\log T$ regret for strongly convex losses. Moreover, the improvement is significant as $\\sigma_{\\max}$ can be much smaller than $d_{\\max}$ as shown in Lemma B.10. We thus believe our improvement is valuable. As for the extra references on projection-free algorithms for OCO with delays, we thank the reviewer for providing them and will incorporate them in our next revision. However, we wonder whether this is directly related to the above improvement as Theorem 2 in [1] only achieves $O(\\frac{G^3+\\lambda^3D^3}{\\lambda}(d_{\\max}+1)\\ln T+\\frac{G^2+\\lambda^2D^2}{\\lambda}T^{2/3})$ regret ($d$ in [1] is $d_{\\max}+1$ in our notation), which does not involve $\\sigma_{\\max}$ and has a polynomial dependence on the diameter $D$ of the action set as well as a worse dependence on $G$, let alone the clearly suboptimal $T^{2/3}$ term. As for Lemma 5 in [1], we are also not sure whether this is directly related since we consider a single update using all the gradients received as feedback in each round and do not bound terms similar to $\\\\|y_{\\tau_{c_t}}-y_t\\\\|_2$; Lemma 5 also seems to present some downsides that end up causing the above-mentioned shortcomings of Theorem 2, which seem unavoidable via the projection-free algorithms in [1]. We would appreciate it if the reviewer could kindly clarify further on this comment.\n\n**Q:** Explanations to Eq. (17).\n\n**A:** We solve the quadratic inequality w.r.t. $\\\\|x_t^*-x_{t+1}^*\\\\|_2$ from the previous math display and relax its upper bound to derive (17). We will make this clearer.\n\n**Q:** Eq. (56)-(59) and dependence on $\\eta_t$.\n\n**A:** Thanks for pointing out the typo. The first inequality in (56) is missing $\\eta_t$ in the r.h.s.\n\n**Q:** In Lemma D.1, $N$ should be $T$.\n\n**A:** The lemma holds for any $N \\in [T]$ and we use it with $N = \\tau^\\star < T$ in the proof of Corollary 4.2. We will quantify $N$ in the statement of Lemma D.1 and clarify its usage.\n\n**Q:** Other comments and typos.\n\n**A:** Thanks for pointing out other minor typos and simplifying the derivation below Eq.(17)/(26). We will incorporate these fixes in our next revision.", "claims_and_evidence": "Yes, all theoretical results have been proved by detailed analysis.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I have checked almost all the proofs in this paper, and do not find any serious problems.", "experimental_designs_or_analyses": "As a theoretical work, the experimental setting is acceptable. A minor concern is that the total number of rounds used in the experiments is too small, i.e., $T=1000$.", "relation_to_broader_scientific_literature": "This paper is related to existing works about online convex optimization (OCO) with curvature and/or delayed feedback. Among those related works, the most comparable ones are existing results for OCO with strongly convex functions and unknown delays (Wan et al., 2022; Wu et al., 2024) and a black-box method for OCO with arbitrary but stamped delays (Joulani et al., 2013). Although the authors have cited these works, the corresponding discussions are a bit opportunistic.\n\nSpecifically, one actually can simply utilize the black-box method (Joulani et al., 2013) to derive an $O(\\sigma_{\\max}n\\ln T)$ regret bound for delayed OCO with exp-concave functions respectively, and a similar result for online linear regression. However, in Table 1 (as well as the whole Introduction), it seems that there are no existing results on exp-concave functions and online linear regression. I understand that the authors may want to emphasize the black-box method is not suitable for the case with unknown delays, i.e., the timestamp of each feedback is unknown. But, their regret bound for exp-concave functions also needs to know the timestamp of each feedback.\n\nIn the case of strongly convex functions, the authors emphasize that their result has two improvements, i.e., replacing $d_\\max$ in the regret bound with $\\sigma_\\max$ and simultaneously achieving a regret bound of $\\ln T+\\sqrt{d_{tot}}$. However, as also confirmed by the authors, the existing algorithm of Wu et al. (2024) is sufficient to enjoy the improved regret bound, which limits the significance of the proposed algorithm for strongly convex functions. Moreover, from the technical view, it is actually trivial to replace $d_\\max$  with  $\\sigma_\\max$ (based on an existing work discussed below). The only interesting finding is that the term $|m_t|/(t-1)$ can be relax to $|m_t|/(\\sum_{\\tau\\leq t}|m_{\\tau}|)$, and then the sum of this term over $t=1,...,T$ can be bounded by $\\sqrt{d_{tot}}$ based on a classical inequality.", "essential_references_not_discussed": "Although the authors have cited some existing algorithms for online convex optimization (OCO) with delays and strongly convex functions (Wan et al., 2022; Wu et al., 2024), there exists a delayed variant of online Frank-Wofle (OFW) for strongly convex functions [1][2] that is related to the delayed variant of follow-the-regularized-leader (FTRL) proposed in this paper. \n\nSpecifically, OFW originally can be viewed as a combination of follow-the-regularized-leader (FTRL) with linear optimization, and if the projection is allowed, it actually can recover the original FTRL. Therefore, the delayed OFW (i.e., Algorithm 2 in [1]) can also recover the delayed FTRL. For example, it is easy to modify the proof of Theorem 2 and Lemma 5 in [1] to derive a regret bound of $\\sigma_{\\max}\\ln T$ for strongly convex functions.\n\n[1] Wan et al. Projection-free Online Learning with Arbitrary Delays. In arXiv:2204.04964v2, 2023.\n\n[2] Wan et al. Online Frank-Wolfe with Arbitrary Delays. In NeurIPS, 2022.", "other_strengths_and_weaknesses": "#Strengths\n1) The authors provide a careful analysis, especially the simple yet useful relaxation of $|m_t|/(t-1)$, to derive an improved regret bound for delayed online convex optimization with strongly convex functions.\n2) The authors propose a delayed variant of online Newton step without using the black-box reduction, and establish an $O(n\\log T+\\min(d_{\\max}n\\log T,\\sqrt{d_{tot}}))$ regret bound for exp-concave functions. The analysis is more complicated than that of strongly convex functions.\n3) The authors also consider the problem of online linear regression, and develop a delayed variant of the Vovk-Azoury-Warmuth forecaster.\n\n#Weaknesses\n1) There lacks a detailed comparison with the theoretical results derived by the black-box method (Joulani et al., 2013). Moreover, it seems that the black-box method can achieve $O(\\sigma_{\\max}n\\ln T)$ regret bound for exp-concave functions. However, the regret bound of this paper depends on the maximum delay $d_{\\max}$, instead of $\\sigma_{\\max}$.\n2) As also confirmed by the authors, the existing algorithm of Wu et al. (2024) is sufficient to enjoy the improved regret bound for strongly convex functions, which limits the significance of the delayed variant of follow-the-regularized-leader (FTRL). Moreover, there exists a delayed variant of online Frank-Wofle that is related to the delayed FTRL but missed.\n3) Some procedures in the proofs are unnecessary. For example, below Eq. (17), from the definition of $x_t^\\ast$, it is easy to verify that $(F_t^\\ast(x_t^\\ast)+\\langle g_t, x_t^\\ast \\rangle)-(F_t^\\ast(x_{t+1}^\\ast)+\\langle g_t, x_{t+1}^\\ast \\rangle)\\leq \\langle g_t,x_t^\\ast- x_{t+1}^\\ast \\rangle$ (it is no need to use the convexity of $F_t^\\prime$, the definition of $F_t^\\prime$, and, the first-order optimality). The same issue exists below Eq. (26). Moreover, some procedures need more explanations, e.g., the straightforward calculations for Eq. (17).", "other_comments_or_suggestions": "#Suggestions\n1) In Lemma D.1 and its proof, $N$ should be $T$.\n2) In line 850, the superscript of $d_{\\max}$ is omitted.\n3) In line 888, $g_t$ should be $g_{\\tau}$", "questions_for_authors": "At the bottom of page 29, if we simply combine Eq. (56) and (58), it seems that $\\eta_t^2$ will be introduced, which is different from the procedures in your Eq. (59). Is there a typo somewhere？", "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": "giyfZseJ07", "reviewer": "Reviewer_zZM9", "summary": "This paper investigates various types of loss functions in the context of Online Convex Optimization (OCO) with delayed feedback and proposes a variant of Follow-The-Regularized-Leader (FTRL) to improve upon previous results. Firstly, it slightly enhances the existing regret bound for strongly convex loss functions. Secondly, it provides the first theoretical guarantee for exp-concave loss functions. Additionally, the authors analyze online linear regression with delayed feedback. Finally, experimental results confirm the effectiveness of their proposed approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q:** Definition of delays and presentation of results.\n\n**A:** In our introduction, we mainly focus on the delay-dependent terms in the bounds for conciseness, but we will clarify the presentation to avoid any confusion. While we also appreciate the suggestion on the definition of delays, we remark that our current definition is common in the related literature. See the seminal work by Weinberger and Ordentlich (2002), Joulani et al. (2013, 2016), and McMahan and Streeter (2014), and more recent work like Masoudian et al. (2022, 2024) and Van der Hoeven et al. (2023).\n\n**Q:** Limited contribution for strongly convex functions and OLR.\n\n**A:** For the *strongly convex* case, we remark that our analysis is **radically different** from the one by Wu et al. (2024), which is crucial in proving the improved guarantees and we believe is an important contribution. As mentioned in our Appendix F and Section 2 as well as in our response to Reviewers jw1R and htSw, the bound we prove via our analysis is essentially optimal, while the results by Wu et al. (2024) have multiple disadvantages; see our responses to Reviewers jw1R and htSw for more details due to the space limit.\nMoreover, our careful regret analysis also leads to our $\\sigma_{\\max}\\ln T$ regret bound, which can be significantly better as $\\sigma_{\\max}$ can be much smaller than $d_{\\max}$ as shown in Lemma B.10.\n\nFor the *OLR* setting, we also argue that our contribution is not limited as the analysis required significant changes. In OLR, we consider the unconstrained $\\mathcal{X} = \\mathbb{R}^n$ and need to leverage the structure to tackle the problem. The main change is in analyzing the $\\text{Drift}_T$ term in the regret. While we can nicely control it in the exp-concave case, also due to the bounded diameter, in OLR we cannot do the same. This challenging task requires clipping the predictions and we also avoid prior knowledge of $\\max_t |y_t|$, which needs a careful analysis of the cumulative clipping error (see lines 1277-1308 and 1344-1358).\n\n**Q:** Parameter setting and its impact in experiments.\n\n**A:** The learning rates of all baseline methods and our algorithms are proportional to the theoretical ones w.r.t. $T$ and delay-related terms, whereas we ignored $G$ and $D$ as they are reasonable constants in our experimental setup. Following your suggestion, we rerun the experiments with the learning rates as stated in the theoretical results. What we observe is that the performance of all algorithms worsens as including the worst-case bound $G$ and $D$ is somewhat pessimistic, while leading to no change from a comparative point of view, hence providing essentially no further information than the current plots.\n\n**Q:** Validation on real-world data.\n\n**A:** We first remark that the contribution of our work is mainly theoretical, as written in the Impact Statement and observed by Reviewer jw1R. The experiments' goal is thus to validate our findings, which we think already transpires from our current empirical results. Following your suggestion, we consider a real-world dataset [mg\\_scale](https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/regression.html\\#mg) with 1385 samples; each sample has 6 features with values in $[-1,1]$ and a label in $[0,2]$. The experimental setup, including constructions of losses and delays, follows what already done for the experiments in our work. The resulting plots are found in the \"Real World Data\" folder in [this repository](https://anonymous.4open.science/r/Supplementary-experiments-EF2D), and show a similar behavior of the algorithms as already shown in our original experiments.\n\n**Q:** Assumption $t+d_t \\leq T$.\n\n**A:** To be precise, we do not make explicit use of it, and we may even remove it. In any case, we remark that one can always introduce it **without loss of generality** because the feedback of any round $t$ with $t+d_t\\ge T$ is not used by any learner. This assumption is also made, e.g., by the same authors of [1; Joulani et al., 2013] in Joulani et al. (2016).\n\n**Q:** Improvement w.r.t. the diameter dependence.\n\n**A:** To the best of our knowledge, previous methods (e.g., Wan et al., 2022; Wu et al., 2024) have a polynomial dependence on the diameter $D$ of $\\mathcal{X}$, while Wu et al. (2024) also show a $O(\\frac{G^2}{\\lambda}(d_{\\max}+1)\\ln T)$ regret via an FTL-based algorithm but only for the significantly *easier* setting with full-function feedback. We remark that the regret of our delayed FTRL as well as our novel analysis for delayed OMD are the first results that are independent of $D$, thus allowing to handle even *unbounded* domains, and recover the optimal $O(\\frac{G^2}{\\lambda}\\ln T)$ regret in the no-delay setting under strong convexity.\n\n**Q:** Typo at line 929.\n\n**A:** Thanks, we will fix it in our next revision.", "claims_and_evidence": "Yes, it improves the previous results.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "There is an issue with the results presented in the abstract and introduction. The authors assume the delay $d_t \\geq 0$.  Under the no-delay setting ($d_t = 0$), their regret bound in the Table~1 (i.e., $\\min \\\\{\\sigma_{\\max}\\ln T, \\sqrt{d_{tot}} \\\\}$) reduces to  $O(1)$. \nThis is because of the discarded term $O(\\ln T)$. The complete regret bound should be presented as $O(\\ln T + \\min \\\\{\\sigma_{\\max}\\ln T, \\sqrt{d_{tot}} \\\\})$.\n\nIn addition, I suggest modifying the assumption to $d_t \\geq 1$, where the feedback for round $t$ is received at round $t+d_t- 1$. This adjustment aligns with the assumptions made in previous works. [1][2]\n\n[1]Quanrud, K. and Khashabi, D. Online learning with adversarial delays. Advances in neural information processing systems, 28, 2015.\n\n[2]Wan, Y., Tu, W.-W., and Zhang, L. Online strongly convex optimization with unknown delays. Machine Learning, 111(3):871–893, 2022.", "experimental_designs_or_analyses": "The experiment lacks a description of the parameter settings for the baseline methods.\n\nIn the experiments, the learning rate for DONS appears to be set differently from what is stated in the theorem. Could you clarify the rationale behind this choice? I am concerned that the experimental results may be highly dependent on the specific learning rate setting, which could impact the generality and robustness of your results.", "relation_to_broader_scientific_literature": "This work is relative to [1] and [2], and claims answering an open question proposed in [1].\n\n[1] Online strongly convex optimization with unknown delays. Machine Learning, 2022.\n\n[2] Online sequential decisionmaking with unknown delays. In Proceedings of the ACM on Web Conference 2024, 2024.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths**\n\n- The paper is well-written and easy to follow.\n- The authors provide the code for the experiments.\n- The idea for exp-concave loss functions is interesting, although there are some unclear presentation (see Theoretical Claims).\n\n\n**Weakness**\n\n- I think the improvement for strongly convex loss functions is somewhat limited.\n- The authors need to validate their findings with experiments on both real-world tasks.\n- The results of OLR appear to be a combination of the results from ONS and Vovk-Azoury-Warmuth (VAW), which further limits its contribution.", "other_comments_or_suggestions": "- Typo Line 929  delete $d$.", "questions_for_authors": "- I concern about the assumption $t+d_t \\leq T$, as it does not appear in previous works [1]. Could you clarify the role this assumption plays in your analysis?\n\n\n- The authors claim that their regret guarantee does not depend on the diameter of the domain. This is primarily attributed to the inclusion of an additional $Drift_T$ term. However, I think the constant improvement provided by this term does not constitute a significant contribution to the overall result.\n\n\n[1] Online learning with adversarial delays. Advances in neural information processing systems, 2015.", "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": "ceXdbppS9x", "reviewer": "Reviewer_htSw", "summary": "This paper studies online learning with delayed feedback under curved loss functions. Specifically, for strongly convex functions, the proposed FTRL method achieves a regret bound of $O(\\min\\{\\sigma\\_{\\max} \\ln T, \\sqrt{d}\\_{\\text{tot}}\\})$, where $\\sigma\\_{\\max}$ denotes the maximum number of missing data. This result improves upon the best-known bound of $O(d\\_{\\max} \\ln T)$ for strongly convex functions. For exp-concave functions, the paper establishes that a regret bound of $O(\\min\\\\{d\\_{\\max} n \\ln T, \\sqrt{d}\\_{\\text{tot}}\\\\})$ is achievable. Additionally, the similar idea extends to the VAW algorithm for online least-squares regression.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q:** Missing results of BOLD-OGD for strongly convex functions in Figures (a) and (b).\n\n**A:** To address the request of a more comprehensive empirical comparison, we will also include the performance of BOLD-OGD in the strongly convex setting. We originally omitted BOLD-OGD because it is a typically inefficient algorithm (needs to run $\\sigma_{\\max}+1$ independent instances of some base algorithm, here OGD), and for the strongly convex setting (contrarily to the exp-concave and OLR settings) we already have specific benchmarks from prior work (Wan et al., 2022; Wu et al., 2024) to compare against which are more practical and usually show an improved empirical performance compared to the black-box reduction via BOLD.\nYou can find these new plots [here](https://anonymous.4open.science/r/Supplementary-experiments-EF2D), showing our algorithm outperforms BOLD-OGD too.\n\n**Q:** Similar performance to SDMD-RSC in the strongly convex case; examples showing the improvement by the proposed methods under strong convexity.\n\n**A:** In fact, we do prove in Appendix F that delayed OMD (originally from Wu et al., 2024) achieves the same optimal regret bound as our delayed FTRL under strong convexity, which is one of the contributions of our work. We remark that showing this result required a non-negligible effort as our analysis is **radically different** from the one by Wu et al. (2024), which was a crucial difference in deriving the improved guarantees. Specifically, as mentioned in our Section F and Section 2 as well as in our response to Reviewers jw1R and zZM9, our bound is essentially optimal, while the $O(\\frac{G^2+D}{\\lambda}(d_{\\max}+1)\\ln T + \\frac{G}{\\lambda^2}(d_{\\max}+1))$ bound proved in Wu et al. (2024) has some disadvantages including: (1) a multiplicative dependence on the diameter $D$ of the action set $\\mathcal{X}$; (2) no robustness to the $\\sqrt{d_{tot}}$ regime; (3) a worse dependence on the strong convexity parameter $\\lambda$; (4) a worse $d_{\\max}$ dependence. In turn, our regret bound for delayed OMD improves upon all these points and recovers the optimal $O(\\frac{G^2}{\\lambda}\\ln T)$ regret in the no-delay setting under strong convexity. Our improved analysis also explains why the empirical performances of the two algorithms we studied have a similar performance in our experiments for the strongly convex case.\n\n**Q:** Empirical comparison with methods achieving $\\sqrt{d_{tot}}$ regret in the exp-concave case.\n\n**A:** We remark that DOGD is one such algorithm and we do compare our method to DOGD in our experiments. The results are shown in Figures (b) and (e), and that our algorithm indeed outperforms DOGD in both cases.\n\n**Q:** Possibly extending results of Wu et al. (2024) to the exp-concave setting.\n\n**A:** Based on our understanding, extending the results of Wu et al. (2024) to the exp-concave setting is highly nontrivial. Wu et al. (2024) focuses exclusively on OMD and FTRL algorithms with a fixed regularizer $\\psi$, and their analysis critically relies on this assumption. In contrast, analyzing exp-concave functions typically requires handling time-varying or data-dependent regularizers (required as illustrated by the reviewer themselves, and addressed by our Algorithm 2), for which Wu et al.'s techniques do not directly apply. Addressing this challenge under delayed feedback is one of the key technical contributions of our work. We will better highlight this difference and our contribution with respect to this aspect in our next revision.", "claims_and_evidence": "To me, the claim made in the paper is well supported.", "methods_and_evaluation_criteria": "Yes, regret is typically used as a performance measure for online learning methods.", "theoretical_claims": "I have gone through the proof for the strongly convex function and did not find any issues. The proofs for the exp-concave loss and the VAW method also appear correct.", "experimental_designs_or_analyses": "- It appears that the results of the BOLD-OGD methods for strongly convex functions are not presented in Figure (a) and Figure (d).  \n- In the strongly convex case, although the proposed methods have a clearly better regret bound than SDMD-RSC, their empirical performance remains similar in both cases: $d_{\\max} \\ll \\sqrt{d_{\\text{tot}}}$ and $d_{\\max} \\gg \\sqrt{d_{\\text{tot}}}$. It is unclear whether this is due to shortcomings in the experimental setup or if the analysis of the previous method is overly loose.  \n- For exp-concave loss functions, I believe it would be fair to compare with methods that achieve the $\\sqrt{d_{\\text{tot}}}$ bound to assess whether the curvature of the loss function really helps for learning with delayed feedback.  \n- It seems that the method by Wu et al. (2024) applies to relatively strongly convex functions. I am unsure whether their approach can also be extended to the exp-concave case by selecting the function in the Bregman divergence as $\\frac{1}{2} \\Vert x \\Vert^2_{\\nabla f_t \\nabla f_t^\\top}$ within their framework.", "relation_to_broader_scientific_literature": "The paper presents an algorithm for delayed feedback within the OCO framework with curved loss, with its main contribution being introducing methods with improved bounds.", "essential_references_not_discussed": "It appears that the relevant works have been cited. However, I am unsure whether the method of Wu et al. (2024) can be extended to the exp-concave loss setting through a specific choice of the Bregman divergence. Additionally, Wu et al. (2024) also studied FTRL-based methods. I believe it would be beneficial to provide a more detailed comparison highlighting the differences between the proposed methods and the previous one.", "other_strengths_and_weaknesses": "**Strengths:**  \n+ The paper presents a new algorithm for learning with delayed feedback, offering an improved bound.  \n+ The method and proof are clear and well-structured.  \n+ The empirical results validate the effectiveness of the proposed method.  \n\n**Weaknesses:**  \n- It is unclear how significant the improvement of the proposed method is. Theoretically, it would be beneficial for the authors to provide concrete examples illustrating when and why the improvement is substantial. Experimentally, the proposed method appears to perform similarly to the previous approach for strongly convex functions.", "other_comments_or_suggestions": "Please see above.", "questions_for_authors": "- Please refer to the first three points in the \"Experimental Designs or Analyses\" part.  \n- Could you discuss whether the method of Wu et al. (2024) can also be applied to the exp-concave case by selecting an appropriate function in the Bregman divergence?  \n- Could you provide some concrete examples where the improvement of the proposed method is significant, both theoretically and empirically, for strongly convex functions?", "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:

Meta-review: This paper provides an algorithm for online convex optimization with delayed feedback in the setting of exp-concave losses and online linear regression. The regret bounds appear to improve the delay-dependent terms of previous work from a worst-case dependence on the maximum delay, to a dependence on the sum of the delays. Overall, the reviews express some concern the closeness of this paper's contribution to prior work. The authors defend this point by pointing out deficiencies in prior analyses, and all reviewers are in favor of acceptance.
The authors are encouraged to incorporate their reviewer response into the final copy.
Decision: Accept (poster)