Exploiting Curvature in Online Convex Optimization with Delayed Feedback

Emmanuel Esposito; Hao Qiu; Mengxiao Zhang

REVIEW 2 major objections 5 minor 19 references

Exploiting Curvature in Online Convex Optimization with Delayed Feedback

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that curvature lets delayed-feedback online learning escape the $d_{\max}\ln T$ penalty, replacing it with $\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$ for strongly convex, exp-concave, and unconstrained…

desk verdict Strongly convex and OLR results are solid, but the adaptive exp-concave bound has a monotonicity gap that the proof relies on. read the letter →

arxiv 2506.07595 v1 pith:2KCUWDC6 submitted 2025-06-09 cs.LG stat.ML

Hao Qiu , Emmanuel Esposito , Mengxiao Zhang This is my paper · ORCID

classification cs.LGstat.ML

keywords onlineconvexoptimizationdelayedfeedbackstrongconvexityexp-concavelossesfollow-the-regularized-leaderNewtonSteplinearregressionadaptivelearningrate

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Delayed feedback in online convex optimization usually costs a $\ln T$ factor times the maximum delay $d_{\max}$, which can be catastrophic when a single gradient is lost or arrives very late; earlier work with convex losses gets only $\sqrt{d_{\mathrm{tot}}}$, where $d_{\mathrm{tot}}$ sums all delays. This paper tries to close the gap by showing that curvature can buy the best of both regimes: a new follow-the-regularized-leader variant achieves $\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$ for strongly convex losses, where $\sigma_{\max}$ is the maximum number of pending gradients. It then extends the same shape to the broader class of exp-concave losses with a delayed Online Newton Step and an adaptive learning rate, obtaining $\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\}$, stated as the first such guarantee under delays, and to unconstrained online linear regression with a clipped Vovk-Azoury-Warmuth forecaster. A reader should care because the result says the delay penalty can adapt to whichever is smaller, maximum delay or total delay, without knowing either in advance, and it removes dependence on the domain diameter in the strongly convex case.

What carries the argument

The argument rides on a regret decomposition into a cheating term, the regret of a comparator who receives all past gradients, and a drift term $\sum_t\langle g_t, x_t - x^\star_t\rangle$ measuring how far the delayed play is from the cheat. The central object is the missing set $m_t = \{\tau : \tau + d_\tau \ge t\}$ of gradients still unseen at round $t$; its worst-case size is $\sigma_{\max}$ and its total is $d_{\mathrm{tot}}$. A stability lemma for FTRL bounds $\|x^\star_t - x_t\|_2 \le G|m_t|/(\lambda(t-1))$, and the key combinatorial step is bounding $\sum_t |m_t|/(t-1)$ simultaneously by $\sigma_{\max}\ln T$ and by $2\sqrt{d_{\mathrm{tot}}}$, using $m_\tau \subseteq [\tau-1]$ and $\sum_\tau |m_\tau| = d_{\mathrm{tot}}$. For exp-concave losses the same drift is controlled by a delayed elliptical-potential lemma, and the adaptive learning rate $\eta_t = \min\{a_t,b_t\}+1$ switches between a $d_{\max} n\ln T$ potential and a $\sqrt{d_{\mathrm{tot}}}$ potential, splitting at the last round where $a_t \le b_t$; the unconstrained regression result adds a clipping step so the gradient at the played point cannot blow up.

What would settle it

To test the scope claim, run Algorithm 1 on $T$ strongly convex quadratic losses with one gradient delayed past the horizon, say $d_1 = T$, while all other delays are zero; because the paper defines $\sigma_{\max}$ and $d_{\mathrm{tot}}$ only over the in-horizon arrival model, this case is excluded by assumption, and the stated $\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$ guarantee is not formally established. A second check is computational: for fixed $d_{\mathrm{tot}}$, search delay sequences satisfying $t+d_t \le T$ that maximize $\sum_{t=2}^T |m_t|/(t-1)$; if any sequence beats $2\sqrt{d_{\mathrm{tot}}}$, the key combinatorial inequality behind the $\sqrt{d_{\mathrm{tot}}}$ side is false.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is that two standard regret analyses that previously appeared to diverge under delay, the logarithmic $d_{\max}\ln T$ bound for curved losses and the $\sqrt{d_{\mathrm{tot}}}$ bound of delayed gradient descent, are two ends of one drifting-iterate inequality. For $\lambda$-strongly convex losses with gradients bounded by $G$, Theorem 3.1 proves that Delayed FTRL has $O((G^2/\lambda)(\ln T + \min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}))$ regret, with no dependence on the domain diameter. For $\alpha$-exp-concave losses, Theorem 4.1 and Corollary 4.2 prove that a delayed Online Newton Step with the adaptive rate $\eta_t = \min\{a_t,b_t\}+1$ achieves $\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\}$ plus an $n\ln T$ term, the first logarithmic-type delayed guarantee known for this class. Section 5 extends the same guarantee to unconstrained online linear regression by clipping the played predictions so the predicted label never exceeds the largest label seen so far, and the paper also gives an improved analysis of a previously proposed online mirror descent algorithm, showing it attains the same $\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$ shape.

Load-bearing premise

The load-bearing premise is that every gradient arrives no later than the horizon, $t+d_t \le T$, so a delayed gradient that would arrive after $T$ is treated as effectively absent; the paper's identities linking $\sigma_{\max}$, $d_{\mathrm{tot}}$, and the drift are proved only under this truncation.

Editorial extensions

If this is right

For strongly convex losses, the regret is $O((G^2/\lambda)(\ln T + \min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}))$ with no diameter dependence, and with no delay it reduces to the known optimal $O((G^2/\lambda)\ln T)$.
For exp-concave losses, the delayed Online Newton Step with adaptive rate gives $O(\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\} + n\ln T)$, the first such delayed guarantee, and the tuning needs no prior knowledge of $d_{\max}$ or $d_{\mathrm{tot}}$.
For unconstrained online linear regression, the clipped Vovk-Azoury-Warmuth forecaster reaches the same regret shape without knowing the comparator $u$ or the label range in advance.
A single gradient delayed by $\Theta(T)$ rounds makes $d_{\max}\ln T$ far worse than $\sqrt{d_{\mathrm{tot}}}$; the new bounds interpolate automatically, so neither worst case dominates.
The paper also proves that an earlier online mirror descent algorithm achieves the same $\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$ bound, so the improved guarantee is not tied to one update rule.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: because $\sigma_{\max} \le d_{\max}$ and the strongly convex drift argument counts only missing gradients, the exp-concave bound may be improvable from $d_{\max} n\ln T$ to $\sigma_{\max} n\ln T$; the paper explicitly leaves this open.
Editorial inference: the adaptive rate $\eta_t = \min\{a_t,b_t\}+1$ is computed online from timestamps of received gradients, so the same scheme should extend to anytime or unknown-horizon settings without a doubling trick, though the paper does not claim this.
Editorial inference: the clipping idea for unconstrained regression, which clips the prediction rather than the labels, may transfer to scale-free prediction or unbounded-feature settings, since the analysis only needs a running bound on observed labels.
Editorial inference: the two delay benchmarks are genuinely incomparable in practice, so the min shape matters: Lemma A.10 in the paper shows there are delay sequences where $d_{\max}$ and $\sqrt{d_{\mathrm{tot}}}$ differ by a factor of $\sqrt{T}$, and a practical deployment should expect either regime to bind.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: the paper's headline exp-concave result has a real gap, but the strongly convex and online linear regression results look solid. The stress-test lands. Corollary 4.2's adaptive schedule eta_t = min{a_t,b_t}+1 is asserted non-decreasing because a_t and b_t are, but b_t can decrease: b_t^2 = sum_{s<=t}|m_s|+|m_t|+1, so b_{t+1}^2 - b_t^2 = 2|m_{t+1}| - |m_t|, which is negative when many delayed gradients arrive at once. The example delays in the stress-test make b_4 < b_3. The proofs of Theorem 4.1 and Lemma C.1 both require 0

What is actually new and good: Theorem 3.1's min{sigma_max ln T, sqrt(d_tot)} for strongly convex losses is a genuine improvement over the previous d_max ln T bounds, and the diameter-free analysis is nice. I checked the drift-versus-cheating decomposition in Appendix B and it holds. The refined OMD analysis of Wu et al.'s algorithm in Appendix E is also new and looks correct, and Corollary 5.3 for OLR uses a monotone schedule (b_t is a cumulative sum without the extra |m_t| term), so it is not touched by this bug. The experimental section is standard but supports the theory.

The citation pattern is normal; the external lemmas are standard, and I see no fitted constants or circular normalization. The delay model t+d_t <= T is a reasonable convention, not a problem for me.

Bottom line: a reader working on delayed online learning gets real value from the strongly convex and OLR sections. The exp-concave section needs repair before the paper's central claim is credible. A serious referee should send this to major revision, not desk reject. If the authors fix the monotonicity issue, the paper could be quite good.

Referee Report

2 major / 5 minor

Summary. The paper studies online convex optimization with delayed feedback under curvature assumptions. It proposes three algorithms: a delayed FTRL variant for strongly convex losses, a delayed Online Newton Step variant for exp-concave losses, and a delayed Vovk-Azoury-Warmuth forecaster with clipping for unconstrained online linear regression. The main theoretical claims are regret bounds of order min{σmax log T, sqrt(dtot)} for strongly convex losses and min{dmax n log T, sqrt(dtot)} for exp-concave losses and online linear regression, together with experimental comparisons against prior delayed-feedback baselines. Full proofs are provided in appendices, and the analysis decomposes regret into a cheating term and a drift term controlled by a stability lemma.

Significance. If the results are correct, the paper is a substantial advance: it improves on the previous dmax log T guarantees for strongly convex delayed OCO, provides the first exp-concave delayed-feedback guarantee, and extends the framework to unconstrained online linear regression. The paper's methodology is a strength: the bounds are parameter-free in the sense that no constants are fitted, the proofs rely on standard external lemmas (Orabona, Lattimore-Szepesvari, Hazan), and the authors provide reproducible code and experiments across several delay regimes. The strongly convex result is diameter-free and recovers the no-delay fast rate, and the OMD analysis in Appendix E is a genuine improvement over Wu et al. (2024). However, the central exp-concave adaptive-rate proof contains a load-bearing monotonicity error, so the first exp-concave guarantee is not established as stated.

major comments (2)

[Section 4, Eq. (6) and proof of Corollary 4.2] The adaptive learning rate in Corollary 4.2 is asserted to be non-decreasing because "a_t and b_t are non-decreasing," but b_t is not non-decreasing: b_t^2 = (G^2/D^2)(Σ_{s≤t}|m_s| + |m_t| + 1), and |m_t| can drop sharply when a batch of delayed gradients arrives. For example, d_1=2, d_2=1, d_3=0 gives |m_3|=2 and |m_4|=0, so b_4<b_3 and η_4<η_3. Theorem 4.1 and Lemma C.1 are stated under 0<η_0≤...≤η_T, and Lemma C.1 uses A_{τ-1}⪯A_{t-1} for τ<t. The a_T≤b_T case of Corollary 4.2 applies Eq. (29) over the whole horizon, so the d_max log T bound is not proved for the algorithm as stated. The OLR corollary is not affected because b_t in Eq. (13) lacks the |m_t| term and is therefore non-decreasing. A running-maximum learning rate would restore monotonicity, but that is a different algorithm and the sqrt(d_tot) half of the bound must be rechecked; the manuscript should either prove the bound without monotonicity or analyze the modified rule.
[Section 2 and Lemma A.7] The statement that t+d_t≤T is "without loss of generality" is too strong: a delay with t+d_t>T changes the meaning of d_tot and d_max, because such a gradient is missing for only T−t observable rounds, not d_t rounds. Specifically, the identity d_tot(S)=Σ_{t=1}^T |m_t∩S| in Lemma A.7 holds only under the truncation convention d'_t=min{d_t, T−t}; otherwise d_tot(S) is strictly larger than the sum. The main regret inequalities still go through if the equalities are replaced by inequalities, and the paper already uses inequality directions in most places, but the displayed identities are formally false without the truncation. The authors should make the truncation explicit and state Lemma A.7 in terms of truncated delays.

minor comments (5)

[Throughout] Several theorem statements say "under Theorems 2.3 and 2.4" where the intended references are Assumptions 2.3 and 2.4 (e.g., Theorem 4.1 and Theorem 5.2).
[Figure 1 caption] The caption reads "over20repetitions" with missing spaces; it should read "over 20 repetitions."
[Section 4, simple tuning] In the simple tuning paragraph, the constant schedule η_t=1 should specify that η_0=1 as well, since the theorem statements and Lemma C.1 require a positive η_0.
[Equation (5)] The definition of a_t in Eq. (5) divides by G; if G=0 the regret is trivially zero, but the update rule and learning rate are undefined. A one-sentence treatment of the G=0 case would avoid ambiguity.
[Algorithms 1–3] The pseudocode loops over t=1,2,... but the setting has a finite horizon T; this is harmless, but the pseudocode could be made consistent with the finite-horizon analysis.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret bounds are derived from external standard lemmas and the paper's own stability and drift lemmas, with no fitted constants or self-citation chain supplying the central claims.

full rationale

The central claims (Theorems 3.1, 4.1, 5.2 and Corollaries 4.2, 5.3) are derived by decomposing regret into a 'cheating' regret term and a drift term, then bounding each term using standard externally cited results (Orabona 2025 Lemma 4.13, Lattimore & Szepesvari 2020 Lemma 19.4, Hazan et al. 2007 Lemma 2, Wei et al. 2021 Lemma 10, Flaspohler et al. 2021 Lemma 18) together with lemmas proved in the appendix (Lemma A.2 stability lemma, Lemma A.7 relating sigma_max to sqrt(dtot), Lemma C.1 delayed elliptical potential). No parameter is fitted to the target regret, and no claimed prediction is a renamed input: sigma_max, dmax and dtot are defined independently of the regret bounds, and the delay-dependent sums are bounded by external summation lemmas rather than by assuming the desired regret. Self-citations to the authors' bandit papers (Esposito et al. 2023, Zhang et al. 2025) are contextual related-work citations, and the one delay lemma imported from outside with overlapping context (Masoudian et al. 2022, Lemma A.6) is stated but not used in the main proofs. A reviewer concern about Corollary 4.2 is that the proof asserts 'eta_t is non-decreasing since a_t and b_t are non-decreasing', while b_t from Eq. (6) can decrease between rounds; this is a potential technical proof gap in the exp-concave analysis, not circularity, because monotonicity is an explicit hypothesis of Theorem 4.1 and Lemma C.1 rather than an input disguised as a conclusion. The strongly convex and linear-regression results are independent of that disputed monotonicity claim. Therefore the circularity score is 0; the noted issue should be assessed as a correctness risk, not as circular reasoning.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new model entities and fits no constants to data; its only free choices are algorithm hyperparameters whose regret bounds are proven for all valid values, so the ledger is limited to the standard convexity and boundedness assumptions of the problem setting.

assumptions (6)

domain assumption Losses are convex, differentiable, and have gradients bounded by a known G (Assumption 2.3).
Every Cauchy-Schwarz step in the regret proofs uses ||g_t||_2 <= G; if G is unknown or infinite all bounds fail.
domain assumption The action set X is closed, has diameter D, and contains 0 for the ONS and OLR results (Assumption 2.4).
beta = 1/2 min{1/(4GD), alpha} and the D^2 term rely on bounded diameter; 0 is the reference point for the quadratic regularizer.
domain assumption Losses are lambda-strongly convex or alpha-exp-concave with known parameters (Definitions 2.1 and 2.2).
Curvature is the source of logarithmic rates; alpha and lambda enter algorithm constants and Lemma A.3.
domain assumption Every deadline obeys t+d_t <= T and each observed gradient carries the timestamp of its round.
This makes sum_t |m_t| = dtot and lets d_max^<=t be computed online; post-horizon feedback is truncated away, so the stated dtot is the effective one.
domain assumption In online linear regression, feature vectors and labels are bounded by Z and Y (Assumption 5.1).
Y appears in the clipping-drift bound and Z in learning-rate and elliptical-potential terms.
standard math Standard external lemmas: FTRL regret identity (Lemma A.1), FTRL stability (Lemma A.2), Orabona's summation lemma, and the elliptical-potential lemma of Lattimore and Szepesvari.
These are cited black-box results used repeatedly in Appendices B through E.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exploiting Curvature in Online Convex Optimization with Delayed Feedback." pith.science (2026). https://pith.science/paper/2KCUWDC6

@misc{pith2026250607595,
  author       = {Pith},
  title        = {Pith review of: Exploiting Curvature in Online Convex Optimization with Delayed Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2KCUWDC6}},
  note         = {Machine review of arXiv:2506.07595}
}

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.

Figures

Figures reproduced from arXiv: 2506.07595 by the authors.

**Figure 1.** Comparison with relevant baselines. The shaded areas consider a range centered around the mean with half-width corresponding to the empirical standard deviation over 20 repetitions. Acknowledgements EE and HQ acknowledge the financial support from the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR-PE-AI scheme (M4C2, investment 1.3, line on Artificial … view at source ↗

**Figure 2.** Comparison with relevant baselines. The shaded areas consider a range centered around the mean with half-width corresponding to the empirical standard deviation over 20 repetitions. label yt: yt = [PITH_FULL_IMAGE:figures/full_fig_p031_2.png] view at source ↗

**Figure 3.** [PITH_FULL_IMAGE:figures/full_fig_p032_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 16 canonical work pages

[1]

Observe that, given such a bound on the cheating term, we now have to consider three different terms as shown in Equation (17)

+G TX t=1 ∥x⋆ t −x t∥2 ,(17) where the equality is due to the definition ofψ t, while the second inequality follows from∥g t∥2 ≤Gby Theorem 2.3. Observe that, given such a bound on the cheating term, we now have to consider three different terms as shown in Equation (17). While the second one is a desirable logarithmic term, and the first one is negligibl...

work page 2025
[2]

Then, we have ∥z1 −z 2∥2 A1 +∥z 1 −z 2∥2 A2 ≤ ⟨w1 −w 2, z2 −z 1⟩+ (ψ 1(z2)−ψ 2(z2))−(ψ 1(z1)−ψ 2(z1))

Suppose thatz 1 ∈arg min x∈X ⟨w1, x⟩+ψ1(x) andz 2 ∈arg min x∈X ⟨w2, x⟩+ψ2(x) . Then, we have ∥z1 −z 2∥2 A1 +∥z 1 −z 2∥2 A2 ≤ ⟨w1 −w 2, z2 −z 1⟩+ (ψ 1(z2)−ψ 2(z2))−(ψ 1(z1)−ψ 2(z1)). Furthermore, ifψ 1(x) =ψ 2(x) =x ⊤Ax+b ⊤x+cwith positive definiteA≻0, we have ∥z1 −z 2∥A ≤ 1 2 ∥w1 −w 2∥A−1 . Proof. Let h1(x) =⟨w 1, x⟩+ψ1(x) and h2(x) =⟨w 2, x⟩+ψ2(x) be twi...

work page 2007
[6]

(2024) only manage to show that this algorithm achieves regret O dmax(G2+D) λ lnT+ dmaxG λ2 under Theorems 2.3 and 2.4

However, Wu et al. (2024) only manage to show that this algorithm achieves regret O dmax(G2+D) λ lnT+ dmaxG λ2 under Theorems 2.3 and 2.4. Here, we report its pseudocode in Algorithm 4 and we provide an improved regret analysis for it. Not only do we provide a significantly better guarantee, but we also manage to lift Theorem 2.4 and only require the boun...

work page 2024
[9]

Auxiliary results In this section, we show several auxiliary lemmas that will be helpful throughout the paper

11 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 ⊆Rn be closed ...

work page 2025
[12]

linearized

It essentially corresponds to the standard elliptical potential lemma, but here adapted to the presence of delays. Lemma C.1.Let ϕ >0, L >0, and 0< η0 ≤η 1 ≤ · · · ≤ηN . For any t∈[N] , let at ∈R n such that ∥at∥2 ≤L and defineA t =η tI+ϕ P τ≤t aτ a⊤ τ . Then, it holds that NX t=1 ∥at∥A−1 t−1 X τ∈m t ∥aτ ∥A−1 t−1 ! ≤ 2nd≤N max ϕ ϕL2 η0 + 1 ln 1 + ϕL2N η0n...

work page 2020
[13]

Consider now any term F ′ t (x⋆ t )−F ′ t (x′ t) in the sum after the last inequality and let At =η tI+ Pt τ=1 zτ z⊤ τ . Applying Theorem A.2 forz 1 =x ′ t andz 2 =x ⋆ t withA=A t, we derive that ∥x⋆ t −x ′ t∥At ≤ |yt| 2 ∥zt∥A−1 t .(37) We can now use this fact to show that F ′ t (x⋆ t )−F ′ t (x′ t)≤ ⟨∇F′ t (x⋆ t ), x⋆ t −x ′ t⟩(convexity ofF ′ t) =⟨∇F ⋆...

work page 2020
[14]

Corollary 5.3.In the OLR problem with delayed labels under Assumption 5.1, Algorithm 3 with the adaptive learning rate ηt =γ(min{a t, bt}+ 1), wherea t andb t are defined in Equation(13)for anyγ >0guarantees that RegT ≤ γ∥u∥2 2 2 +nY 2 ln 1 + Z 2T γn +O min{Q 1, Q2} , whereQ 1 = γ∥u∥2 2 +Y 2 ndmax ln 1 + Z2T γn andQ 2 = γZ∥u∥ 2 2 + (Z+ 1)Y 2 √dtot . Proof...

work page 2025
[15]

(2024) in their Algorithm

To be precise, an OMD-based algorithm which handles delays was initially proposed by Wu et al. (2024) in their Algorithm

work page 2024

Show all 19 references

[17]

linearized

5:end for Theorem E.1.Assume that f1, . . . , fT are λ-strongly convex functions with respect to the Euclidean norm ∥·∥2. Then, under Theorem 2.3, Algorithm 4 guarantees RegT =O G2 λ lnT+ min n σmax lnT, p dtot o . Proof. We begin with a decomposition of the regret that, simil...

2021
[18]

TX t=1 (|ot+1| − |ot|)Pt s=1(|os+1| − |os|) ≤(σ max + 1)(1 + lnT),(59) where the last inequality follows by Orabona (2025, Lemma 4.13) and the fact that PT t=1(|ot+1| − |ot|) =|o T+1 |=T . Second, we can also bound such a sum in an alternative way: TX t=1 (|mt|+ 1)(|o t+1| − |...

2025
[19]

This periodic change introduces non-stationarity, reflecting scenarios where the optimal action shifts over time. The delay dt is independently sampled from a distribution that alternates every 30 rounds between a geometric distribution with success probability T −1/3 and a un...

2023
[2002]

Online sequential decision- making with unknown delays

Wu, P., Huang, H., and Liu, Z. Online sequential decision- making with unknown delays. InProceedings of the ACM on Web Conference 2024, pp. 4028–4036,

2024
[2014]

A modern introduction to online learning.arXiv preprint arXiv:1912.13213v7,

10 Exploiting Curvature in Online Convex Optimization with Delayed Feedback Orabona, F. A modern introduction to online learning.arXiv preprint arXiv:1912.13213v7,

1912 arXiv
[2015]

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,

arXiv
[2016]

Hazan, E., Agarwal, A., and Kale, S

doi: 10.1561/2400000013. Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret al- gorithms for online convex optimization.Machine Learn- ing, 69(2):169–192,

doi
[2020]

and Cesa-Bianchi, N

Van der Hoeven, D. and Cesa-Bianchi, 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 ofPro- ceedi...

2022
[2021]

Weinberger, M. J. and Ordentlich, E. On delayed prediction of individual sequences.IEEE Transactions on Informa- tion Theory, 48(7):1959–1976,

1959
[2022]

Slow learners are fast.arXiv preprint arXiv:0911.0491,

Langford, J., Smola, A., and Zinkevich, M. Slow learners are fast.arXiv preprint arXiv:0911.0491,

arXiv
[2023]

Contextual linear bandits with delay as payoff.arXiv preprint arXiv:2502.12528v2,

Zhang, M., Wang, Y ., and Luo, H. Contextual linear bandits with delay as payoff.arXiv preprint arXiv:2502.12528v2,

arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Observe that, given such a bound on the cheating term, we now have to consider three different terms as shown in Equation (17)

+G TX t=1 ∥x⋆ t −x t∥2 ,(17) where the equality is due to the definition ofψ t, while the second inequality follows from∥g t∥2 ≤Gby Theorem 2.3. Observe that, given such a bound on the cheating term, we now have to consider three different terms as shown in Equation (17). While the second one is a desirable logarithmic term, and the first one is negligibl...

work page 2025

[2] [2]

Then, we have ∥z1 −z 2∥2 A1 +∥z 1 −z 2∥2 A2 ≤ ⟨w1 −w 2, z2 −z 1⟩+ (ψ 1(z2)−ψ 2(z2))−(ψ 1(z1)−ψ 2(z1))

Suppose thatz 1 ∈arg min x∈X ⟨w1, x⟩+ψ1(x) andz 2 ∈arg min x∈X ⟨w2, x⟩+ψ2(x) . Then, we have ∥z1 −z 2∥2 A1 +∥z 1 −z 2∥2 A2 ≤ ⟨w1 −w 2, z2 −z 1⟩+ (ψ 1(z2)−ψ 2(z2))−(ψ 1(z1)−ψ 2(z1)). Furthermore, ifψ 1(x) =ψ 2(x) =x ⊤Ax+b ⊤x+cwith positive definiteA≻0, we have ∥z1 −z 2∥A ≤ 1 2 ∥w1 −w 2∥A−1 . Proof. Let h1(x) =⟨w 1, x⟩+ψ1(x) and h2(x) =⟨w 2, x⟩+ψ2(x) be twi...

work page 2007

[3] [6]

(2024) only manage to show that this algorithm achieves regret O dmax(G2+D) λ lnT+ dmaxG λ2 under Theorems 2.3 and 2.4

However, Wu et al. (2024) only manage to show that this algorithm achieves regret O dmax(G2+D) λ lnT+ dmaxG λ2 under Theorems 2.3 and 2.4. Here, we report its pseudocode in Algorithm 4 and we provide an improved regret analysis for it. Not only do we provide a significantly better guarantee, but we also manage to lift Theorem 2.4 and only require the boun...

work page 2024

[4] [9]

Auxiliary results In this section, we show several auxiliary lemmas that will be helpful throughout the paper

11 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 ⊆Rn be closed ...

work page 2025

[5] [12]

linearized

It essentially corresponds to the standard elliptical potential lemma, but here adapted to the presence of delays. Lemma C.1.Let ϕ >0, L >0, and 0< η0 ≤η 1 ≤ · · · ≤ηN . For any t∈[N] , let at ∈R n such that ∥at∥2 ≤L and defineA t =η tI+ϕ P τ≤t aτ a⊤ τ . Then, it holds that NX t=1 ∥at∥A−1 t−1 X τ∈m t ∥aτ ∥A−1 t−1 ! ≤ 2nd≤N max ϕ ϕL2 η0 + 1 ln 1 + ϕL2N η0n...

work page 2020

[6] [13]

Consider now any term F ′ t (x⋆ t )−F ′ t (x′ t) in the sum after the last inequality and let At =η tI+ Pt τ=1 zτ z⊤ τ . Applying Theorem A.2 forz 1 =x ′ t andz 2 =x ⋆ t withA=A t, we derive that ∥x⋆ t −x ′ t∥At ≤ |yt| 2 ∥zt∥A−1 t .(37) We can now use this fact to show that F ′ t (x⋆ t )−F ′ t (x′ t)≤ ⟨∇F′ t (x⋆ t ), x⋆ t −x ′ t⟩(convexity ofF ′ t) =⟨∇F ⋆...

work page 2020

[7] [14]

Corollary 5.3.In the OLR problem with delayed labels under Assumption 5.1, Algorithm 3 with the adaptive learning rate ηt =γ(min{a t, bt}+ 1), wherea t andb t are defined in Equation(13)for anyγ >0guarantees that RegT ≤ γ∥u∥2 2 2 +nY 2 ln 1 + Z 2T γn +O min{Q 1, Q2} , whereQ 1 = γ∥u∥2 2 +Y 2 ndmax ln 1 + Z2T γn andQ 2 = γZ∥u∥ 2 2 + (Z+ 1)Y 2 √dtot . Proof...

work page 2025

[8] [15]

(2024) in their Algorithm

To be precise, an OMD-based algorithm which handles delays was initially proposed by Wu et al. (2024) in their Algorithm

work page 2024