Exploiting Curvature in Online Convex Optimization with Delayed Feedback

Q: Missing results of BOLD-OGD for strongly convex functions in Figures (a) and (b).

A: To address the request of a more comprehensive empirical comparison, we will also include the performance of BOLD-OGD in the strongly convex setting. We originally omitted BOLD-OGD because it is a typically inefficient algorithm (needs to run $\sigma_{\max}+1$ independent instances of some base algorithm, here OGD), and for the strongly convex setting (contrarily to the exp-concave and OLR settings) we already have specific benchmarks from prior work (Wan et al., 2022; Wu et al., 2024) to compare against which are more practical and usually show an improved empirical performance compared to the black-box reduction via BOLD. You can find these new plots here, showing our algorithm outperforms BOLD-OGD too.

Q: Similar performance to SDMD-RSC in the strongly convex case; examples showing the improvement by the proposed methods under strong convexity.

A: In fact, we do prove in Appendix F that delayed OMD (originally from Wu et al., 2024) achieves the same optimal regret bound as our delayed FTRL under strong convexity, which is one of the contributions of our work. We remark that showing this result required a non-negligible effort as our analysis is radically different from the one by Wu et al. (2024), which was a crucial difference in deriving the improved guarantees. Specifically, as mentioned in our Section F and Section 2 as well as in our response to Reviewers jw1R and zZM9, our bound is essentially optimal, while the $O(\frac{G^2+D}{\lambda}(d_{\max}+1)\ln T + \frac{G}{\lambda^2}(d_{\max}+1))$ bound proved in Wu et al. (2024) has some disadvantages including: (1) a multiplicative dependence on the diameter $D$ of the action set $\mathcal{X}$; (2) no robustness to the $\sqrt{d_{tot}}$ regime; (3) a worse dependence on the strong convexity parameter $\lambda$; (4) a worse $d_{\max}$ dependence. In turn, our regret bound for delayed OMD improves upon all these points and recovers the optimal $O(\frac{G^2}{\lambda}\ln T)$ regret in the no-delay setting under strong convexity. Our improved analysis also explains why the empirical performances of the two algorithms we studied have a similar performance in our experiments for the strongly convex case.

Q: Empirical comparison with methods achieving $\sqrt{d_{tot}}$ regret in the exp-concave case.

A: We remark that DOGD is one such algorithm and we do compare our method to DOGD in our experiments. The results are shown in Figures (b) and (e), and that our algorithm indeed outperforms DOGD in both cases.

Q: Possibly extending results of Wu et al. (2024) to the exp-concave setting.

A: Based on our understanding, extending the results of Wu et al. (2024) to the exp-concave setting is highly nontrivial. Wu et al. (2024) focuses exclusively on OMD and FTRL algorithms with a fixed regularizer $\psi$, and their analysis critically relies on this assumption. In contrast, analyzing exp-concave functions typically requires handling time-varying or data-dependent regularizers (required as illustrated by the reviewer themselves, and addressed by our Algorithm 2), for which Wu et al.'s techniques do not directly apply. Addressing this challenge under delayed feedback is one of the key technical contributions of our work. We will better highlight this difference and our contribution with respect to this aspect in our next revision.

Q: Definition of delays and presentation of results.

A: In our introduction, we mainly focus on the delay-dependent terms in the bounds for conciseness, but we will clarify the presentation to avoid any confusion. While we also appreciate the suggestion on the definition of delays, we remark that our current definition is common in the related literature. See the seminal work by Weinberger and Ordentlich (2002), Joulani et al. (2013, 2016), and McMahan and Streeter (2014), and more recent work like Masoudian et al. (2022, 2024) and Van der Hoeven et al. (2023).

Q: Limited contribution for strongly convex functions and OLR.

A: For the strongly convex case, we remark that our analysis is radically different from the one by Wu et al. (2024), which is crucial in proving the improved guarantees and we believe is an important contribution. As mentioned in our Appendix F and Section 2 as well as in our response to Reviewers jw1R and htSw, the bound we prove via our analysis is essentially optimal, while the results by Wu et al. (2024) have multiple disadvantages; see our responses to Reviewers jw1R and htSw for more details due to the space limit. Moreover, our careful regret analysis also leads to our $\sigma_{\max}\ln T$ regret bound, which can be significantly better as $\sigma_{\max}$ can be much smaller than $d_{\max}$ as shown in Lemma B.10.

For the OLR setting, we also argue that our contribution is not limited as the analysis required significant changes. In OLR, we consider the unconstrained $\mathcal{X} = \mathbb{R}^n$ and need to leverage the structure to tackle the problem. The main change is in analyzing the $\text{Drift}_T$ term in the regret. While we can nicely control it in the exp-concave case, also due to the bounded diameter, in OLR we cannot do the same. This challenging task requires clipping the predictions and we also avoid prior knowledge of $\max_t |y_t|$, which needs a careful analysis of the cumulative clipping error (see lines 1277-1308 and 1344-1358).

Q: Parameter setting and its impact in experiments.

A: The learning rates of all baseline methods and our algorithms are proportional to the theoretical ones w.r.t. $T$ and delay-related terms, whereas we ignored $G$ and $D$ as they are reasonable constants in our experimental setup. Following your suggestion, we rerun the experiments with the learning rates as stated in the theoretical results. What we observe is that the performance of all algorithms worsens as including the worst-case bound $G$ and $D$ is somewhat pessimistic, while leading to no change from a comparative point of view, hence providing essentially no further information than the current plots.

Q: Validation on real-world data.

A: We first remark that the contribution of our work is mainly theoretical, as written in the Impact Statement and observed by Reviewer jw1R. The experiments' goal is thus to validate our findings, which we think already transpires from our current empirical results. Following your suggestion, we consider a real-world dataset mg_scale with 1385 samples; each sample has 6 features with values in $[-1,1]$ and a label in $[0,2]$. The experimental setup, including constructions of losses and delays, follows what already done for the experiments in our work. The resulting plots are found in the "Real World Data" folder in this repository, and show a similar behavior of the algorithms as already shown in our original experiments.

Q: Assumption $t+d_t \leq T$.

A: To be precise, we do not make explicit use of it, and we may even remove it. In any case, we remark that one can always introduce it without loss of generality because the feedback of any round $t$ with $t+d_t\ge T$ is not used by any learner. This assumption is also made, e.g., by the same authors of [1; Joulani et al., 2013] in Joulani et al. (2016).

Q: Improvement w.r.t. the diameter dependence.

A: To the best of our knowledge, previous methods (e.g., Wan et al., 2022; Wu et al., 2024) have a polynomial dependence on the diameter $D$ of $\mathcal{X}$, while Wu et al. (2024) also show a $O(\frac{G^2}{\lambda}(d_{\max}+1)\ln T)$ regret via an FTL-based algorithm but only for the significantly easier setting with full-function feedback. We remark that the regret of our delayed FTRL as well as our novel analysis for delayed OMD are the first results that are independent of $D$, thus allowing to handle even unbounded domains, and recover the optimal $O(\frac{G^2}{\lambda}\ln T)$ regret in the no-delay setting under strong convexity.

Q: Typo at line 929.

A: Thanks, we will fix it in our next revision.

Q: $T=1000$ is too small in experiments.

A: We extended our experiments to have $T=10000$ and plan to include the new plots in our next revision. The new plots essentially show the same behavior with an extended time horizon. You can find these extra plots in the "Synthetic Data" folder at this repository.

Q: Comparison to the black-box method (Joulani et al., 2013).

A: We thank the reviewer for pointing this out. Indeed, applying the black-box reduction (Joulani et al., 2013) with ONS can achieve $O(\sigma_{\max}n\ln T)$ regret, and our Algorithm 2 also requires the timestamps to compute the regularizer. However, in Table 1 we did not compare with the algorithms based on the black-box reduction due to their typical inefficiency (also shown to some extent by our experiments). Nevertheless, we will add these remarks for the exp-concave and online linear regression settings in our discussion as well as Table 1 to have a more comprehensive comparison with existing techniques.

Q: Improved regret bounds under strong convexity and comparison with Wu et al. (2024).

A: In fact, proving that the algorithm proposed by Wu et al. (2024) achieves the optimal regret bound in OCO with delays is one of the contributions of our work. Note that our analysis is radically different from Wu et al. (2024), which was crucial in deriving the improved guarantees and we believe is an interesting contribution. As mentioned in our Appendix F and Section 2 as well as in our response to Reviewers zZM9 and htSw, the bound we prove via our analysis is essentially optimal, while the bound $O(\frac{G^2+D}{\lambda}(d_{\max}+1)\ln T + \frac{G}{\lambda^2}(d_{\max}+1))$ in Wu et al. (2024) has some disadvantages including: (1) a multiplicative dependence on the diameter $D$ of $\mathcal{X}$; (2) no robustness to the $\sqrt{d_{tot}}$ regime; (3) a worse dependence on the strong convexity parameter $\lambda$; (4) a worse $d_{\max}$ dependence ($d$ in their work is $d_{\max}+1$ in our notation). The improvements of our analysis are thus multiple, with no assumption on the domain $\mathcal{X}$ having a bounded diameter $D$, thus proving that the algorithm can work even in unbounded domains, the optimal dependence on $G$ and $\lambda$ hence recovering the optimal $O(\frac{G^2}{\lambda}\ln T)$ regret bound in the no-delay setting, and the improved robustness to delays given by our key observations on $\sum_t |m_t|/(t-1)$.

Q: Improvement from $d_{\max}$ to $\sigma_{\max}$ is trivial based on OFW in [1].

A: We respectfully disagree with the reviewer that the improvement from $d_{\max}$ to $\sigma_{\max}$ is trivial. While this refinement may appear straightforward in hindsight, to the best of our knowledge, no prior work has provably achieved a $\sigma_{\max}\log T$ regret for strongly convex losses. Moreover, the improvement is significant as $\sigma_{\max}$ can be much smaller than $d_{\max}$ as shown in Lemma B.10. We thus believe our improvement is valuable. As for the extra references on projection-free algorithms for OCO with delays, we thank the reviewer for providing them and will incorporate them in our next revision. However, we wonder whether this is directly related to the above improvement as Theorem 2 in [1] only achieves $O(\frac{G^3+\lambda^3D^3}{\lambda}(d_{\max}+1)\ln T+\frac{G^2+\lambda^2D^2}{\lambda}T^{2/3})$ regret ($d$ in [1] is $d_{\max}+1$ in our notation), which does not involve $\sigma_{\max}$ and has a polynomial dependence on the diameter $D$ of the action set as well as a worse dependence on $G$, let alone the clearly suboptimal $T^{2/3}$ term. As for Lemma 5 in [1], we are also not sure whether this is directly related since we consider a single update using all the gradients received as feedback in each round and do not bound terms similar to $\\|y_{\tau_{c_t}}-y_t\\|_2$; Lemma 5 also seems to present some downsides that end up causing the above-mentioned shortcomings of Theorem 2, which seem unavoidable via the projection-free algorithms in [1]. We would appreciate it if the reviewer could kindly clarify further on this comment.

Q: Explanations to Eq. (17).

A: We solve the quadratic inequality w.r.t. $\\|x_t^*-x_{t+1}^*\\|_2$ from the previous math display and relax its upper bound to derive (17). We will make this clearer.

Q: Eq. (56)-(59) and dependence on $\eta_t$.

A: Thanks for pointing out the typo. The first inequality in (56) is missing $\eta_t$ in the r.h.s.

Q: In Lemma D.1, $N$ should be $T$.

A: The lemma holds for any $N \in [T]$ and we use it with $N = \tau^\star < T$ in the proof of Corollary 4.2. We will quantify $N$ in the statement of Lemma D.1 and clarify its usage.

Q: Other comments and typos.

A: Thanks for pointing out other minor typos and simplifying the derivation below Eq.(17)/(26). We will incorporate these fixes in our next revision.

Q: Can you run the experiments on more adversarial settings?

A: Following your suggestion, we run our benchmark algorithms on the following more adversarial (i.e., non-stationary) environment. Specifically, in this environment, we set the time horizon as $T = 10000$ (as to also address a concern by Reviewer jw1R) and we partitioned rounds into roughly $\log_2 T$ phases where the length of phase $s \ge 1$ is $2^{s-1}$. For $t\in\\{2^{s-1},\dots,2^s-1\\}$, when $s$ is odd, the feature vector $z_t$ is sampled from the multivariate standard Gaussian distribution with values clipped to the range $[-1,1]$ and the delay $d_t$ is independently sampled from a geometric distribution with a success probability of $T^{-1/3}$; when $s$ is even, each coordinate of $z_t$ is independently and uniformly sampled from $[-1,1]$ and the delay $d_t$ is independently and uniformly sampled from the set $\\{0,1,\dots,5\\}$. The loss function is designed in the same way as already described in Section 6 of our paper for each of the three settings, except we additionally clip the standard Gaussian noise to $[-1,1]$ to have a bounded gradient. You can find the additional plots for these experiments in the "Adversarial Data" folder at the following anonymized link https://anonymous.4open.science/r/Supplementary-experiments-EF2D. We will integrate these plots with appropriate comments, as well as a reference to the source code, in the next revision of our paper.

Q: Typos at lines 583, 628, and 850.

A: Thanks for carefully pointing out these typos. We will fix them in our next revision.