{"id":"e2d72660-feb2-472b-ba16-e56d41df552c","arxiv_id":"2506.07595","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Delayed-feedback FTRL, Online Newton Step, and a clipped Vovk-Azoury-Warmuth forecaster achieve regret of order min{logarithmic in maximum backlog, square root of total delay} for strongly convex, exp-concave, and online linear regression losses.","lead":"This paper designs online learning algorithms that exploit loss curvature under delayed feedback, achieving regret equal to the better of a logarithmic bound in the maximum missing-feedback backlog and a square-root bound in total delay. The main result is the first such guarantee for exp-concave losses, with a parallel guarantee for unconstrained online linear regression.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.2's adaptive learning rate is asserted non-decreasing but can decrease when many delayed gradients arrive together, and the exp-concave proof relies on that monotonicity.","rationale":"The reader's identified weakest assumption, t+d_t≤T stated as WLOG, is not the main risk. The proofs only use |m_t| for t≤T, and each delayed gradient contributes to Σ_t |m_t| at most d_t times, so the truncation only weakens the delay terms; the stated bounds still follow from Σ_t |m_t| ≤ d_tot. The load-bearing gap is in the exp-concave adaptive learning rate. Corollary 4.2 defines η_t = min{a_t,b_t}+1 and claims it is non-decreasing because a_t and b_t are non-decreasing. The claim is false for b_t: b_{t+1}^2 − b_t^2 = 2(|m_{t+1}| − |m_t|), and |m_t| can drop sharply when several delayed gradients arrive in the same round. This violates the monotonicity assumption required by Theorem 4.1 and Lemma C.1, and the proof of the a_T≤b_T case applies the logarithmic drift bound over the whole horizon. Thus the first exp-concave delayed-feedback guarantee is not formally established as written. The gap is localized and likely repairable by taking a running maximum of the candidate learning rates, so the appropriate verdict is conditional acceptance rather than rejection. No issue was found with the strongly convex FTRL analysis or the OLR clipping argument.","tokens_in":38495,"tokens_out":27264,"duration_ms":302069,"concrete_test":"Check the monotonicity identity analytically: from Eq. (6), b_{t+1}^2 − b_t^2 = 2(|m_{t+1}| − |m_t|). For the valid delay pattern d_1=2, d_2=1, d_3=0, compute |m_3|=2 and |m_4|=0, so b_4^2 − b_3^2 = −2 and η_4 < η_3 whenever a_4 > b_4, which holds for sufficiently large T. Then trace the proof of Corollary 4.2's a_T≤b_T case: it invokes Theorem 4.1 and Lemma C.1, whose standing assumption is η_0≤…≤η_T; the schedule violates that assumption, so the logarithmic bound is unsupported unless the schedule is patched, e.g., to η_t = max_{s≤t} min{a_s,b_s}+1.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central exp-concave result is not proved as stated because the adaptive schedule in Corollary 4.2 is not monotone. The proof asserts 'η_t is non-decreasing since a_t and b_t are non-decreasing.' While a_t is non-decreasing, b_t defined in Eq. (6) need not be: b_t^2 = Σ_{s≤t}|m_s| + |m_t| + 1, so b_{t+1}^2 − b_t^2 = 2(|m_{t+1}| − |m_t|). Whenever more delayed gradients arrive in round t than are newly missing, this is negative; e.g., d_1=2, d_2=1, d_3=0 gives |m_3|=2 and |m_4|=0. Hence η_t can strictly decrease. Theorem 4.1 and Lemma C.1 both require 0<η_0≤η_1≤…≤η_T, and the elliptical-potential argument needs A_t−A_{t-1}⪰0. The a_T≤b_T case of Corollary 4.2 applies the logarithmic drift bound over the whole horizon, so the false monotonicity claim is load-bearing. The strongly convex and OLR results are not affected; the natural fix is a running maximum of min{a_s,b_s}, but that is not the algorithm analyzed.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":38739,"tokens_out":12573,"duration_ms":147634,"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":[{"comment":"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":"Section 4, Eq. (6) and proof of Corollary 4.2"},{"comment":"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.","section":"Section 2 and Lemma A.7"}],"minor_comments":[{"comment":"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).","section":"Throughout"},{"comment":"The caption reads \"over20repetitions\" with missing spaces; it should read \"over 20 repetitions.\"","section":"Figure 1 caption"},{"comment":"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.","section":"Section 4, simple tuning"},{"comment":"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.","section":"Equation (5)"},{"comment":"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.","section":"Algorithms 1–3"}],"recommendation":"major_revision","confidential_remarks":"The monotonicity gap in Corollary 4.2 is substantive and load-bearing, but it is localized and likely repairable by either proving a non-monotone version of Lemma C.1 or analyzing a monotone envelope of the learning rate. The rest of the paper, especially the strongly convex and OLR results, appears sound. I recommend major revision rather than rejection, and I would ask the authors to also clean up the truncation convention in Section 2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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<eta_0<=...<=eta_T, and the elliptical-potential steps need A_{t-1} <= A_t. So the adaptive exp-concave guarantee as stated isn't supported. The natural fix is a running max of min{a_t,b_t}, but that is a different algorithm and would need a fresh analysis.\n\nWhat 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.\n\nThe 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.\n\nBottom 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.","headline":"Strongly convex and OLR results are solid, but the adaptive exp-concave bound has a monotonicity gap that the proof relies on.","tokens_in":39314,"tokens_out":4318,"would_cite":true,"duration_ms":43406,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["online convex optimization","delayed feedback","strong convexity","exp-concave losses","follow-the-regularized-leader","Online Newton Step","online linear regression","adaptive learning rate"],"falsifier":"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.","tokens_in":38265,"feed_emoji":"📉","tokens_out":11996,"duration_ms":115572,"temperature":0.7,"pith_summary":"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.","feed_headline":"Curved losses shrink the delay penalty to the best of two bounds","feed_subtitle":"The adaptive algorithms guarantee the smaller of the max-delay and total-delay regret in all three curvature settings.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the logarithmic-regret baselines and the exp-concavity quadratic bound used by the delayed algorithms.","marker":"Hazan et al. (2007)"},{"why":"Establishes the delayed-feedback model, the $t+d_t \\le T$ truncation, and the black-box BOLD reduction used as a baseline.","marker":"Joulani et al. (2013)"},{"why":"Provides the delayed online gradient descent algorithm and the $\\sqrt{d_{\\mathrm{tot}}}$ regret benchmark the new bounds must match.","marker":"Quanrud & Khashabi (2015)"},{"why":"Provides the DOGD-SC algorithm and the $d_{\\max}\\ln T$ strongly convex baseline, and poses the exp-concave open question.","marker":"Wan et al. (2022a)"},{"why":"Provides the SDMD-RSC algorithm and the online mirror descent update whose analysis the paper refines to the same min bound.","marker":"Wu et al. (2024)"},{"why":"Supplies the FTRL regret lemma and the key sum bound used in the $\\sqrt{d_{\\mathrm{tot}}}$ path.","marker":"Orabona (2025)"},{"why":"Supplies the elliptical-potential lemma that converts Mahalanobis-norm sums into logarithmic terms for the ONS and VAW analyses.","marker":"Lattimore & Szepesvári (2020)"},{"why":"One of the two sources of the Vovk-Azoury-Warmuth forecaster that the delayed regression algorithm modifies with clipping.","marker":"Azoury & Warmuth (2001)"},{"why":"The other source of the Vovk-Azoury-Warmuth forecaster whose unconstrained logarithmic regret is adapted to delayed labels.","marker":"Vovk (2001)"}],"fun_headline_variants":["Delayed FTRL achieves the best of two regret bounds","Best-of-two regret bounds for delayed online learning with curvature","Curvature cuts delay regret to the smaller of two measures","Adaptive algorithms realize the min of two regret bounds","New analysis unifies two delayed-regret bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Delayed FTRL achieves the best of two regret bounds","Best-of-two regret bounds for delayed online learning with curvature","Curvature cuts delay regret to the smaller of two measures","Adaptive algorithms realize the min of two regret bounds","New analysis unifies two delayed-regret bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00116,"raw_usage":{"total_tokens":4890,"prompt_tokens":1118,"completion_tokens":3772,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":734,"completion_tokens_details":{"reasoning_tokens":3692}},"tokens_in":734,"tokens_out":3772,"duration_ms":26077,"temperature":1.0,"reasoning_tokens":3692,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:32:53.762308+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the FTRL regret lemma and the key sum bound used in the $\\sqrt{d_{\\mathrm{tot}}}$ path."}],"review_version":1}