- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes a universal algorithm for delayed online convex optimization that adapts to convex, strongly convex, and exp-concave losses without knowing the curvature or delay parameters. Its main contribution is a delayed ML-Prod meta-learner with a second-order excess-loss guarantee. The paper also develops a delayed ONS method that improves the dependence on maximum individual delay. Combining these components yields complementary backlog- and total-delay-sensitive regret bounds with small aggregation overheads. The results are supported by theoretical analysis.
Critical strengths
-
S1. A useful delayed second-order aggregation framework. The reservation mechanism handles unresolved feedback, while expert retirement accommodates an unknown maximum backlog. The resulting second-order guarantee enables curvature-adaptive aggregation and is an important technical contribution.
-
S2. Improved exp-concave delay dependence. Theorem 4.1 replaces with the potentially much smaller in the logarithmic branch, while retaining a complementary branch without an explicit dimension factor. This improves the stated bound of Qiu et al. [2], particularly when a few observations have long delays.
Critical weaknesses
-
W1. The improvement over existing reductions is not sufficiently isolated. Consider the BOLD reduction [1] with smallest-available-index scheduling. The copy counts then satisfy . A refined per-copy analysis yields a term for deterministic anytime logarithmic-regret bases, although its coefficient retains the base learner's dimension and curvature dependence. Thus, the claim that BOLD has no mechanism for this branch is too strong. The paper should distinguish improvements in these coefficients from simultaneous adaptation to unknown curvature and delays.
-
W2. The computational tradeoff is unclear. The algorithm maintains historical weights and quadratic objectives across multiple base learners and requires generalized projections. Without time and memory complexity bounds, the computational cost of the improved guarantees remains difficult to assess relative to simpler BOLD-based alternatives [1].
-
W3. Some formal conditions and proof dependencies are incomplete. Theorem C.1 omits a sufficient restriction on . Algorithm 1 does not explicitly require a surviving expert, while Lemma 3 assumes , which does not follow from Theorem 3.1's comparator condition. The actual dyadic grid satisfies this stronger condition, so these issues appear fixable, but the statements should be made consistent.
Questions for authors
-
Q1 (W1). Which improvements require the proposed machinery? For known curvature, can a BOLD-wrapped ML-Prod master combine BOLD–ONS [1] and the delayed ONS of Qiu et al. [2], all evaluated on common quadratic surrogates, to recover both branches of Theorem 4.1? Let , and consider normalized excess losses, meta-learning rate , and priors for BOLD–ONS and for delayed ONS. Can this construction retain the finer dependence on p. 26? Please quantify any additional logarithmic factors and base-learner coefficients, and distinguish this known-curvature comparison from Theorem 4.2's simultaneous curvature adaptation.
-
Q2 (W2). What are the computational costs? What are the amortized per-round time and peak-memory complexities of Algorithms 1–3, including the base learners, historical states, and projections? Can the quadratic histories share computations or storage, and how do these costs compare with BOLD-based alternatives [1] under the same projection model?
-
Q3 (W3). Can the formal statements be made consistent? Please specify the admissible in Theorem C.1, make Algorithm 1's input conditions explicit, and align Lemma 3 with the surviving-expert condition used in Theorem 3.1. Please also clarify the exp-concave base learner's learning-rate schedule and confirm that these changes preserve the main guarantees.
Required Corrections and Typos
-
Algorithm 1 and Section 3 (p. 5, l. 253; p. 6, l. 292): Replace the vector indicator with the scalar in the coordinate update. Remove , which need not hold after expert retirement, and carry the convention from Appendix A.3 (p. 17, ll. 881–885) into the main proof sketch.
-
Formal conditions (p. 24, ll. 1291–1294; p. 5, l. 243; p. 15, l. 802): State a sufficient restriction such as in Theorem C.1. Clarify Algorithm 1's nonempty-active-set condition. In the proof of Lemma 3 (p. 16, ll. 810–812), the dyadic grid guarantees some , not necessarily .
-
Exp-concave base learner (p. 8, ll. 405–410): Explicitly specify how the learning-rate schedule in Theorem 4.1 (p. 7, ll. 356–359) is instantiated in Algorithm 3 using the surrogate parameters and .
-
Notation and typos: Correct to (p. 20, l. 1072) and to (p. 21, l. 1080). Restore the missing first time index in (p. 6, ll. 288, 297). Remove the duplicated "for" (p. 16, l. 861).
References
[1] Joulani, P., György, A., and Szepesvári, C. (2013). Online Learning under Delayed Feedback. ICML, PMLR 28(3):1453–1461.
[2] Qiu, H., Esposito, E., and Zhang, M. (2025). Exploiting Curvature in Online Convex Optimization with Delayed Feedback. ICML, PMLR 267:50448–50479.
4 comments
W2. The computational tradeoff is unclear. The algorithm maintains historical weights and quadratic objectives across multiple base learners and requires generalized projections. Without time and memory complexity bounds, the computational cost of the improved guarantees remains difficult to assess relative to simpler BOLD-based alternatives [1].
...
Q2 (W2). What are the computational costs? What are the amortized per-round time and peak-memory complexities of Algorithms 1--3, including the base learners, historical states, and projections? Can the quadratic histories share computations or storage, and how do these costs compare with BOLD-based alternatives [1] under the same projection model?
We thank the reviewer for raising this point. We agree that the computational tradeoffs should be clarified and have added a discussion to Section 4 in the revision.
Let denote the number of meta-experts and the dimension. For a direct implementation of Algorithm 1, the bookkeeping requires operations at round . Since and , this gives amortized time per round and memory for the historical weights, excluding the storage and processing of expert predictions.
For Algorithm 2, the historical objectives are quadratic and can be represented by their Hessians and linear terms. With a direct dense implementation, this requires amortized arithmetic operations per round and memory, together with one constrained quadratic minimization per round. The cost of this minimization depends on the geometry of .
The full universal algorithm (Algorithm 3) uses only distinct base learners, since the meta-experts associated with different meta-learning rates share their corresponding base learner. Thus, the base-learner computations are not duplicated across meta-learning rates. The resulting implementation requires constrained optimization operations per round on average, in addition to the delayed bookkeeping. Common gradients, delay coefficients, and surrogate quantities can be shared, although the quadratic states corresponding to different curvature parameters must generally be maintained separately.
For comparison, a BOLD-based universal algorithm should be applied with a universal base learner. In particular, to adapt to curvature the universal learner should itself maintain curvature-dependent base learners, as in our approach. Since BOLD may require up to independent copies of this universal learner, this would result in base-learner instances, compared with in our construction. Although BOLD typically updates only one copy per round, and may therefore have lower per-round bookkeeping costs, it can incur greater memory overhead. Thus, the two approaches involve different computational tradeoffs, and neither uniformly dominates the other.
We also emphasize that BOLD-based reductions do not recover our universal regret guarantees. In the general convex case, Esposito et al. (2026) recently showed that BOLD can incur an additional factor, which cannot generally be eliminated by changing the scheduling of the independent copies. Moreover, applying the refined BOLD directly to ONS in the exp-concave case yields a dimension-dependent penalty, compared with our dimension-free , as discussed earlier.
W3. Some formal conditions and proof dependencies are incomplete. Theorem C.1 omits a sufficient restriction on . Algorithm 1 does not explicitly require a surviving expert, while Lemma 3 assumes , which does not follow from Theorem 3.1's comparator condition. The actual dyadic grid satisfies this stronger condition, so these issues appear fixable, but the statements should be made consistent.
...
Q3 (W3). Can the formal statements be made consistent? Please specify the admissible in Theorem C.1, make Algorithm 1's input conditions explicit, and align Lemma 3 with the surviving-expert condition used in Theorem 3.1. Please also clarify the exp-concave base learner's learning-rate schedule and confirm that these changes preserve the main guarantees.
Thank you for identifying these omissions in the formal statements. Please see the revisions highlighted in orange in the updated manuscript. We have made the surviving-expert condition explicit in Algorithm 1 and aligned Lemma 3 with Theorem 3.1. Note that this condition is already satisfied by the dyadic grid used in Corollary 3.2 and Algorithm 3: Thus, the active set remains nonempty throughout. We have also corrected the corresponding proof to use , rather than equality.
Additionally, we have stated the sufficient restriction in Theorem C.1 and explicitly specified the exp-concave base learner's learning-rate schedule. These corrections make the assumptions and their use explicit and the main regret guarantees remain unchanged.
Thank you for the detailed rebuttal and the revisions. Regarding Q1 (the BOLD-ML-Prod hybrid), I acknowledge that I have not independently verified whether this hybrid construction can fully recover the finer dependence. However, I fully accept your counter-argument: since this construction would be limited to cases where the curvature is known, it does not diminish your proposed algorithm's core contribution of achieving universal adaptation. I consider W1 resolved. Regarding W2 and W3, thank you for adding the "Discussion of Computational Costs" in Section 4 and clarifying the formal conditions (surviving-expert condition, , and the range) in the algorithms and the appendix. These updates adequately address my initial concerns about completeness and computational clarity. In light of these clarifications and the newly added Appendix A, my initial concerns have been addressed. I am raising my score to a 3.
We thank the reviewer for pointing out various typos in the initial submission; these issues have been addressed in the revision.
Thank you for highlighting this refined analysis and for proposing the hybrid construction. We first clarify that the original BOLD theorem [1] does not state dtot branch. In fact, this refined analysis is non-standard and has only explicitly appeared in the literature very recently, in a pre-print from Esposito et al. (2026), which became available only after our submission.
If a deterministic anytime base satisfies Rbase(m)≤Clog(1+m), the scheduling constraint can yield RTBOLD=O(C[log(T+1)+minσmaxlog(T+1),dtot]), For standard ONS, C=O(n/β). Thus, BOLD-ONS incurs a βndtot penalty in the square-root branch, while Algorithm 2 achieves the dimension-free O(β1dtot). We've added a discussion of this alternative to the appendix.
Esposito, Emmanuel, Andrew Jacobsen, Hao Qiu, Alexander Ryabchenko, and Mengxiao Zhang. "Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents." arXiv preprint arXiv:2611.07773 (2026).
We thank the reviewer for suggesting this alternative approach. While this is a potentially interesting alternative construction, it is not clear to us that it recovers the stated guarantee, particularly the finer GD1+dtot dependence. We would appreciate further details on the approach, as it is not completely clear to us what is being suggested, and how the suggested components can be combined to establish a bound matching Theorem 4.1.
Nevertheless, even if the proposed construction can achieve a guarantee matching Theorem 4.1 for known curvature, we believe this would not diminish our contribution. The proposed construction appears to require a non-trivial combination and analysis of existing techniques, rather than following directly from established results, and has not been previously established in the literature. Our Delay-Accounting ONS provides a novel, direct approach which established a new state-of-the-art guarantee for the exp-concave setting with delayed feedback. We do not claim that this is the only way to achieve such a bound.
Beyond the regret bound itself, the design of Delay-Accounting ONS extends the delay-accounting principle developed for our Delayed ML-Prod meta-algorithm to quadratic surrogate objectives. We believe this connection is conceptually important, as it demonstrates how the same underlying technique can be used both for second-order expert aggregation and for online optimization with curved losses.
Finally, we emphasize that the main contribution of our paper is the delayed second-order meta-learning framework, which enables simultaneous adaptation to general convex, strongly convex, and exp-concave losses without knowledge of the curvature class or its parameters (universal rates). The reviewer's suggested construction assumes known β, which is used both in selecting the base learners and in specifying the master's learning rate and prior. Consequently, even if it achieves the same known-curvature bound as Theorem 4.1, it would not be sufficient to establish a universal rate, which is the principle goal of this paper.