acceptodds
Under review as a conference paper at ICLR 2027

Universal Online Convex Optimization With Delayed Feedback

Abstract

We study universal online convex optimization with delayed feedback. We develop a single algorithm that simultaneously adapts to general convex, strongly convex, and exp-concave losses without prior knowledge of the curvature class or parameters. Our regret bounds match the best known dependence on the time horizon and delays up to doubly logarithmic factors: roughly for convex losses and rates with curved losses, where is the total cumulative delay and is the maximum number of simultaneously missing observations. Our main technical contribution is a delayed meta-learner with a second-order excess-loss guarantee, which enables curvature-adaptive aggregation of delayed base learners. In addition, our new exp-concave base learner yields a sharper regret bound which improves the state-of-the-art delay dependence by replacing the maximum delay with the potentially much smaller , while retaining the complementary dependence.

Primary area:
learning theory
Keywords:
online learning, delayed feedback

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_6U5sOpenReview ↗
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 dmax⁡d_{\max} with the potentially much smaller σmax⁡\sigma_{\max} in the logarithmic branch, while retaining a complementary dtot\sqrt{d_{\mathrm{tot}}} 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 ∑j≥2(j−1)Nj≤dtot\sum_{j\ge2}(j-1)N_j\le d_{\mathrm{tot}}. A refined per-copy analysis yields a dtot\sqrt{d_{\mathrm{tot}}} 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 β\beta. Algorithm 1 does not explicitly require a surviving expert, while Lemma 3 assumes min⁡hηh≤1/T\min_h\eta_h\le1/T, 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 β=12min⁡1/(4GD),α\beta=\frac12\min\\{1/(4GD),\alpha\\}, and consider normalized excess losses, meta-learning rate η=βGD\eta=\beta GD, and priors βGD\beta GD for BOLD–ONS and 1−βGD1-\beta GD for delayed ONS. Can this construction retain the finer GD1+dtotGD\sqrt{1+d_{\mathrm{tot}}} 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 β\beta 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 I(h∈Ht)I(h\in\mathcal H_t) in the coordinate update. Remove St=⟨1,Ft⟩S_t=\langle\mathbf1,F_t\rangle, which need not hold after expert retirement, and carry the St=0S_t=0 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 0<β≤12min⁡1/(4GD),α0<\beta\le\frac12\min\\{1/(4GD),\alpha\\} 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 ηh≤1/T\eta_h\le1/T, not necessarily ηh=1/T\eta_h=1/T.

  • 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 GEC=9G/8G_{\mathrm{EC}}=9G/8 and β~=β^/4\widetilde\beta=\widehat\beta/4.

  • Notation and typos: Correct LhL_h to HρH_\rho (p. 20, l. 1072) and 2GDrt2GD r_t to 2GDrth2GD r_t^h (p. 21, l. 1080). Restore the missing first time index in ut,t+dthu_{t,t+d_t}^h (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

We thank the reviewer for pointing out various typos in the initial submission; these issues have been addressed in the revision.

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 ∑j≥2(j−1)Nj≤dtot\sum_{j \geq 2} (j-1)N_j \leq d_{\mathrm{tot}}. A refined per-copy analysis yields a dtot\sqrt{d_{\mathrm{tot}}} 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.

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\sqrt{d_{tot}} 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)R_{\mathrm{base}}(m)\leq C\log(1+m), the scheduling constraint can yield RTBOLD=O(C[log⁡(T+1)+min⁡σmax⁡log⁡(T+1),dtot]),R_T^{\mathrm{BOLD}} = O\left( C\left[\log(T+1)+\min\\{\sigma_{\max}\log(T+1),{\sqrt{d_{\mathrm{tot}}}}\\}\right]\right), For standard ONS, C=O(n/β)C=O(n/\beta). Thus, BOLD-ONS incurs a nβdtot\frac{n}{\beta}\sqrt{d_{tot}} penalty in the square-root branch, while Algorithm 2 achieves the dimension-free O(1βdtot)O(\frac{1}{\beta}\sqrt{d_{tot}}). 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).

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 β=12min⁡1/(4GD),α\beta = \frac{1}{2}\min\\{1/(4GD),\alpha\\}, and consider normalized excess losses, meta-learning rate η=βGD\eta = \beta GD, and priors βGD\beta GD for BOLD--ONS and 1−βGD1-\beta GD for delayed ONS. Can this construction retain the finer GD1+dtotGD\sqrt{1+d_{\mathrm{tot}}} 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.

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+dtotGD\sqrt{1+d_{tot}} 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 β\beta, 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.

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 NN denote the number of meta-experts and nn the dimension. For a direct implementation of Algorithm 1, the bookkeeping requires O(N(1+∣mt∣+∣Ft∣))O(N(1+|m_t|+|\mathcal F_t|)) operations at round tt. Since ∑t∣mt∣=dtot\sum_t|m_t|=d_{\mathrm{tot}} and ∑t∣Ft∣=T\sum_t|\mathcal F_t|=T, this gives O(N(1+dtot/T))O(N(1+d_{\mathrm{tot}}/T)) amortized time per round and O(N(1+σmax⁡))O(N(1+\sigma_{\max})) 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 O(n2(1+dtot/T))O(n^2(1+d_{\mathrm{tot}}/T)) amortized arithmetic operations per round and O(n2(1+σmax⁡))O(n^2(1+\sigma_{\max})) memory, together with one constrained quadratic minimization per round. The cost of this minimization depends on the geometry of X\mathcal X.

The full universal algorithm (Algorithm 3) uses only O(log⁡T)O(\log T) distinct base learners, since the O(log⁡2T)O(\log^2 T) 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 O(log⁡T)O(\log T) 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 O(log⁡T)O(\log T) curvature-dependent base learners, as in our approach. Since BOLD may require up to σmax⁡+1\sigma_{\max}+1 independent copies of this universal learner, this would result in O((σmax⁡+1)log⁡T)O((\sigma_{\max}+1)\log T) base-learner instances, compared with O(log⁡T)O(\log T) 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 log⁡(1+σmax⁡)\sqrt{\log(1+\sigma_{\max})} 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 (n/β)dtot(n/\beta)\sqrt{d_{\mathrm{tot}}} penalty, compared with our dimension-free (1/β)dtot(1/\beta)\sqrt{d_{\mathrm{tot}}}, as discussed earlier.

W3. Some formal conditions and proof dependencies are incomplete. Theorem C.1 omits a sufficient restriction on β\beta. Algorithm 1 does not explicitly require a surviving expert, while Lemma 3 assumes min⁡hηh≤1/T\min_h \eta_h \leq 1/T, 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 β\beta 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: ηJ=2−⌈log⁡2T⌉≤1/T,ηJσmax⁡+≤1\eta_J=2^{-\lceil\log_2 T\rceil}\le 1/T, \qquad \eta_J\sigma_{\max}^{+}\le 1 Thus, the active set remains nonempty throughout. We have also corrected the corresponding proof to use ηJ≤1/T\eta_J\le 1/T, rather than equality.

Additionally, we have stated the sufficient restriction 0<β≤12min⁡1/(4GD),α0<\beta\le \frac12\min\\{1/(4GD),\alpha\\} 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 β\beta 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, ηJ≤1/T\eta_J \leq 1/T, and the β\beta 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.

Reviewer_hJDvOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies universal online convex optimization with delayed feedback. Its goal is to design a single algorithm that adapts to different loss geometries without prior knowledge of the loss class or its curvature parameters. The main technical contribution is delayed ML-Prod, which is a meta-algorithm that provides a second-order excess-loss guarantee while explicitly accounting for delayed observations. The authors further develop delay-accounting ONS for exp-concave losses, which improves the dependence on delays by using the maximum number of simultaneously missing observations rather than the maximum individual delay. By combining this meta-algorithm with delayed OGD, delayed FTRL, and the proposed ONS, the resulting universal algorithm can adapt to general convex, strongly convex, and exp-concave losses. Plus, the regret guarantees essentially match the corresponding class-specific bounds up to small doubly logarithmic factors.

Critical strengths
  1. The core technique is clean and I believe it is correct. Keeping the old weight vectors in reserve and releasing them when their feedback arrives lets the analysis go through with one telescoping potential under arbitrary delays. The online retirement of learning rates is handled carefully, with Lemma 5 showing that the mass removed by retirement does not break the potential argument, and the same bookkeeping carries over to log-determinant potentials for ONS.

  2. The algorithm delay-accounting ONS replaces the dmax⁡nlog⁡Td_{\max} n \log T branch of [Qiu et al. 2025] by σmax⁡nlog⁡T\sigma_{\max} n \log T, and sigma_max can be polynomially smaller than d_max.

  3. This is the first curvature-adaptive guarantee for delayed OCO. I did not find prior or concurrent work on universal OCO with delays, and the rates match the class-specific ones up to log⁡log⁡T\log\log T factors, the same overhead as in the non-delayed universal literature.

Critical weaknesses
  1. The related work misses the paper [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees, arXiv 2602.02634] which gives a delay-adaptive reduction that turns any online linear optimization algorithm into one that handles delays.

  2. The claim that no knowledge of the delays is needed is not fully covered by the analysis. In the convex case of Theorem 4.2 the proof uses Theorem 2.1 of Quanrud and Khashabi, which has a fixed step size tuned with the total delay, and the step size of the convex base learner is never specified in Algorithm 3 or in Theorem 4.2.

  3. The paper does not discuss about the cost. There are also no experiments, while the closest prior work [Qiu et al. 2025] does include simulations under several delay patterns.

Questions for authors
  1. Does the reduction of [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees, arXiv 2602.02634] applied to a non-delayed universal algorithm, already give the convex and strongly convex guarantees in Theorem 4.2?

  2. Which step size does the convex base learner use in Theorem 4.2? Can the theorem be stated and proved for the doubling variant, so that the claim about not knowing the delays holds for the whole algorithm?

  3. Given Lemma 11, is there any regime where the dtot\sqrt{d_{\mathrm{tot}}} branch beats σmax⁡log⁡T\sigma_{\max}\log T by more than a log factor for curved losses? If not, would you consider presenting the contribution as dmax⁡d_{\max} versus σmax⁡\sigma_{\max}?

2 comments

The related work misses the paper A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees, arXiv 2602.02634 which gives a delay-adaptive reduction that turns any online linear optimization algorithm into one that handles delays.

...

Does the reduction of A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees, arXiv 2602.02634 applied to a non-delayed universal algorithm, already give the convex and strongly convex guarantees in Theorem 4.2?

Thanks for pointing this out; we had missed this as it is a relatively recent work. While this work has results relevant to curved losses in delayed OCO, their rates are not universal rates (the guarantees are not minimax optimal for each loss class simultaneously without prior knowledge of which class the learner will be facing). We have added it to the related work section.

The reduction of Ryabchenko et al. is not directly applicable for obtaining universal rates in delayed OCO. In particular, their reduction is not a reduction to ordinary OCO, it is a reduction to OCO with drift penalties of the form ∑n∣wn−wn−δn∗∣,\sum_n\\|w_n-w_{n-\delta_n^*}\\|, where δn∗\delta_n^* denotes the lag induced by the observation ordering. These terms are not controlled by standard non-delayed universal regret guarantees.

To our knowledge, no existing universal algorithm provides the additional drift guarantees required by this reduction. Establishing such guarantees would be particularly challenging for universal algorithms based on meta-learner/base-learner constructions, since the drift depends not only on the movement of the base learners but also on changes in the meta-learner's aggregation weights.

Consequently, the convex and strongly convex guarantees of Theorem 4.2 cannot be recovered by simply applying the proposed reduction to an existing non-delayed universal algorithm. Doing so would require developing and analyzing additional machinery for controlling these drift terms.

The claim that no knowledge of the delays is needed is not fully covered by the analysis. In the convex case of Theorem 4.2 the proof uses Theorem 2.1 of Quanrud and Khashabi, which has a fixed step size tuned with the total delay, and the step size of the convex base learner is never specified in Algorithm 3 or in Theorem 4.2.

...

Which step size does the convex base learner use in Theorem 4.2? Can the theorem be stated and proved for the doubling variant, so that the claim about not knowing the delays holds for the whole algorithm?

The convex base learner uses delayed OGD (Quanrud and Khashabi, 2015), with a step size of order D/(GT+dtot)D/(G\sqrt{T+d_{\mathrm{tot}}}). As discussed on page 3 of their work, prior knowledge of dtotd_{\mathrm{tot}} can be avoided using the standard doubling trick, since the cumulative delay can be tracked online through the number of outstanding observations. This preserves the O(GDT+dtot)O(GD\sqrt{T+d_{\mathrm{tot}}}) regret guarantee without requiring prior knowledge of the delays.

We mention this in Footnote 2 on page 8, but agree that the step-size specification and the use of the doubling variant could be made more explicit. We have clarified this in Section 4.

The paper does not discuss about the cost.

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 NN denote the number of meta-experts and nn the dimension. For a direct implementation of Algorithm 1, the bookkeeping requires O(N(1+∣mt∣+∣Ft∣))O(N(1+|m_t|+|\mathcal F_t|)) operations at round tt. Since ∑t∣mt∣=dtot\sum_t|m_t|=d_{\mathrm{tot}} and ∑t∣Ft∣=T\sum_t|\mathcal F_t|=T, this gives O(N(1+dtot/T))O(N(1+d_{\mathrm{tot}}/T)) amortized time per round and O(N(1+σmax⁡))O(N(1+\sigma_{\max})) 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 O(n2(1+dtot/T))O(n^2(1+d_{\mathrm{tot}}/T)) amortized arithmetic operations per round and O(n2(1+σmax⁡))O(n^2(1+\sigma_{\max})) memory, together with one constrained quadratic minimization per round. The cost of this minimization depends on the geometry of X\mathcal X.

The full universal algorithm (Algorithm 3) uses only O(log⁡T)O(\log T) distinct base learners, since the O(log⁡2T)O(\log^2 T) 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 O(log⁡T)O(\log T) 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 O(log⁡T)O(\log T) curvature-dependent base learners, as in our approach. Since BOLD may require up to σmax⁡+1\sigma_{\max}+1 independent copies of this universal learner, this would result in O((σmax⁡+1)log⁡T)O((\sigma_{\max}+1)\log T) base-learner instances, compared with O(log⁡T)O(\log T) 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.

Given Lemma 11, is there any regime where the dtot\sqrt{d_{\mathrm{tot}}} branch beats σmax⁡log⁡T\sigma_{\max}\log T by more than a log factor for curved losses? If not, would you consider presenting the contribution as dmax⁡d_{\max} versus σmax⁡\sigma_{\max}?

The main contribution is indeed dmax⁡d_{\max} vs. σmax⁡\sigma_{\max}, as discussed on page 7. In particular, the closest existing result to our own for exp-concave losses is Qiu et al. (2025), which achieves a dmax⁡log⁡T∧dtotd_{\max}\log T \wedge \sqrt{d_{tot}} rate. Our result improves the logarithmic branch to the potentially much smaller σmax⁡log⁡T\sigma_{\max} \log T, which was a key open problem in their work, while still maintaining the dtot\sqrt{d_{tot}} branch.

Reviewer_aajFOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates universal online convex optimization with delayed feedback, which can adapt convex, strongly convex, and exp-concave losses without prior knowledge of the curvature information. It propose Delayed ML-Prod and Delay-Accounting ONS, with the latter improving the delay dependence for exp-concave losses. The authors further incorporates them into a unified framework.

Critical strengths
  • This paper addresses the unknown loss curvature and unknown delays simultaneously. By aggregating base learners with appropriately designed surrogate losses, the proposed algorithm accommodates general convex, strongly convex, and exp-concave losses within a single framework.
  • I find the extension of ML-Prod to delayed feedback technically interesting. The difficulty is that the current weights may differ from those used for prediction when feedback arrives. The authors retain the historical weights and adjust the mass reserved for rounds with pending feedback. This lets them apply each update to the corresponding prediction weights and establish the second-order bound through a telescoping potential argument.
  • Theorem 3.1 controls the regret through a delay-weighted sum of squared excess losses. This structure is useful because it allows the aggregation cost to be absorbed by the negative quadratic terms supplied by strong convexity or exp-concavity. The analysis is clearly developed, and the delayed second-order aggregation result is a meaningful contribution.
  • Compared with Qiu et al. [2025], this paper improves the dmax⁡d_{\max} term in the regret with the smaller σmax⁡\sigma_{\max} term. This provides a more refined characterization of delay effects, particularly when a small number of observations experience long delays.
Critical weaknesses
  • Maintaining multiple base learners may require multiple projections per round. It would be heavily computed when the feasible domain is complex.
  • Page 6, line 292 defines St=⟨1,Ft⟩S_t=\langle\mathbf 1,F_t\rangle, whereas Algorithm 1 maintains StS_t as a separate bookkeeping mass. Is it a typo?
Questions for authors

Could the authors extend the proposed framework to require only one projection onto the feasible domain per round while maintaining comparable regret bounds? If not, what are the main technical challenges posed by delayed feedback?

1 comment

Maintaining multiple base learners may require multiple projections per round. It would be heavily computed when the feasible domain is complex.

...

Could the authors extend the proposed framework to require only one projection onto the feasible domain per round while maintaining comparable regret bounds? If not, what are the main technical challenges posed by delayed feedback?

We agree that projections onto a complex feasible set can be costly. Our approach does maintain multiple base learners, each of which may require projection, though this is standard computation in most previous works obtaining universal guarantees.

An exception is Yang et al. (2024), who achieve universal regret guarantees with only one projection onto the original feasible domain per round. Their approach builds on the domain-reduction technique of Cutkosky and Orabona (2018) and Cutkosky (2020), using appropriately designed surrogate losses to allow the base learners to operate over a simpler domain.

We believe a similar approach could be applied to our framework to reduce the number of projections onto the original domain to one per round. Establishing this formally would require adapting the surrogate losses and verifying that our delayed regret guarantees are preserved. In particular, the analysis must account for the interaction between projection corrections, delay-weighted second-order terms, and the curvature terms used to obtain fast rates. We have added a discussion of this potential extension and the associated technical challenges to the "Conclusion and Future Work" section of the revised manuscript.

Yang, Wenhao, Yibo Wang, Peng Zhao, and Lijun Zhang. "Universal Online Convex Optimization with 11 Projection per Round." Advances in Neural Information Processing Systems 37 (2024): 31438-31472.

Page 6, line 292 defines St=⟨Ft,1⟩S_t=\langle F_t,1\rangle, whereas Algorithm 1 maintains StS_t as a separate bookkeeping mass. Is it a typo?

Thank you for pointing this out. We have corrected the proof sketch: StS_t is the bookkeeping scalar maintained by Algorithm 1, satisfying St+∑τ∈mtaτ,t−1=1S_t+\sum_{\tau\in m_t}a_{\tau,t-1}=1; it need not equal ⟨Ft,1⟩\langle F_t,\mathbf{1}\rangle when experts are removed. The appendix proof already uses this invariant and the terminal bound ∑hFT+1h≤1\sum_h F_{T+1}^h\le1, so the regret guarantee remains unchanged. The revisions have been highlighted in orange in the manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.