Improved Regret for Bandit Convex Optimization with Delayed Feedback

Many thanks for the constructive reviews!

Q1: The paper could be written more clearly. I found myself understanding parts of the introduction only after going through the entire paper (e.g. line 69).

A1: Thank you for the helpful suggestion. We will improve our writing by adding necessary explanations to help the understanding.

Q2: The proofs are hard to follow. Some explanations before each lemma to understand how those are used would be helpful.

A2: As you suggested, we will explain the usefulness of each lemma in our analysis. Moreover, we will start each proof by providing a high-level overview of the upcoming procedures.

Q3: It seems hard to use the blocking updates to further improve the regret, so the value of the presented algorithm could be temporary.

A3: We agree that the blocking update mechanism may prevent our algorithm from further improving regret bounds to be depending on the average delay. However, we want to emphasize that our regret bounds achieved via the blocking update mechanism are already quite favorable, and it is highly non-trivial to develop a better algorithm, especially in the case with strongly convex functions. Note that even in the easier full-information setting, previous studies can only achieve the $O(d\log T)$ regret for strongly convex functions, which is the same as the delay-dependent part in our regret bounds for strongly convex functions.

Q4: Can you explain each term in the theorems and where does it come from? As is, the theorems are packed with different terms and besides substituting the optimal values I don't know how to interpret them

A4: We first provide the following explanations for each term in our Theorem 1.

1. The first two terms $\frac{4R^2}{\eta}+\frac{\eta T\gamma}{2K}$ are an upper bound on the expected regret of an ideal action for each block, i.e., $\mathbf{y}_m^\ast$ defined in line 305 of our paper. Therefore, they are affected by the step size $\eta$, the block size $K$, and the variance of cumulative gradients in each block $\gamma$. Moreover, the variance $\gamma$ depends on both the block size $K$ and the exploration radius $\delta$ at first glance, but we can select an appropriate $K$ to remove the extra dependence on $\delta$ as discussed in our paper.
2. The third term $\frac{\eta TG}{2}\sqrt{2\left(\frac{d^2}{K^2}+4\right)\gamma}$ is an upper bound on the expected cumulative distance between the preparatory action $\mathbf{y}_m$ of our Algorithm 1 and the ideal one $\mathbf{y}_m^\ast$, which is further affected by the maximum delay $d$.
3. The last two terms $3\delta GT+\frac{\delta GRT}{r}$ are caused by the error of the shrunk set $\\mathcal{K}\_\\delta$ and the $\delta$-smoothed function $\hat{f}_{t,\delta}(\cdot)$, and thus are affected by the exploration radius $\delta$.

Additionally, we note that the terms in our Theorems 2 and 3 can be similarly divided into these three categories. In the revised version, we will provide detailed explanations for each term in all our theorems.

Many thanks for the constructive reviews!

Q: The paper lacks numerical experiments ... I would be curious about how much improvement can be made in practice. In bandit setting, people often consider large time horizon, in which cases the regret is dominated by the delay-independent term.

A: Please check our common response to the suggestion about experiments, which introduces numerical results completed during the rebuttal period, and has shown the advantage of our algorithm in practice. Moreover, we want to emphasize that although $T$ could be very large, the delay-dependent term in the existing $O(\sqrt{n}T^{3/4}+(n\bar{d})^{1/3}T^{2/3})$ regret bound [Bistritz et al., 2022] cannot be ignored. Specifically, this regret bound is dominated by the delay-independent term only for $\bar{d}=O(n^{1/2}T^{1/4})$. However, this condition can be easily violated due to the sublinear dependence on $T$ and $n$, and the fact that the delay may also increase for larger $T$. For example, our experiment on ijcnn1 has $T=40000$ and $n=22$, and thus the condition is violated as long as $\bar{d}>n^{1/2}T^{1/4}\approx 67$. Even if we consider a much larger $T=400000000$, $\bar{d}>664$ is sufficient to violate the condition. By contrast, our $O(\sqrt{n}T^{3/4}+\sqrt{dT})$ regret bound is dominated by the delay-independent term for a larger amount of delays, i.e., $d=O(n\sqrt{T})$.

Many thanks for the constructive reviews!

Q: The paper only makes an improvement on state-of-the-art for certain delay sequences, i.e. when $d=O((n\bar{d})^{2/3}T^{1/3})$.

A: First, we want to emphasize that both $n$ and $T$ can be very large in modern online applications, and thus the condition $d=O((n\bar{d})^{2/3}T^{1/3})$ can be satisfied by many delay sequences including those with $\bar{d}=1$. Second, it is also worth noting that besides convex functions considered in previous studies [Héliou et al., 2020; Bistritz et al., 2022], our paper further investigates two special cases with strongly convex functions, and achieves $O((nT)^{2/3}\log^{1/3}T+d\log T)$ and $O(n\sqrt{T\log T}+d\log T)$ regret bounds, respectively. These two bounds are better than the state-of-the-art result for a larger portion of delay sequences.

Many thanks for the constructive reviews!

Q: The contribution of this work is quite concerning. It would be better for the authors to emphasis the contribution (either algorithmic or analytic) on improving the delayed feedback result for BCO problem in certain conditions that the max delay $d$ is close to $\bar{d}$? Some parts of the proof are rather straightforward and standard.

A: Thank you for the helpful suggestion. Our technical contributions can be summarized as follows.

1. At the algorithmic level, our paper is the first work that exploits the blocking update mechanism to design improved algorithms for delayed BCO. Moreover, unlike existing algorithms [Héliou et al., 2020; Bistritz et al., 2022] based on online gradient descent, our algorithm is based on follow-the-regularized-leader (FTRL). As discussed in lines 228 to 235 of our paper, in this way, we can utilize the delayed information more elegantly.
2. At the analytic level, we derive the first regret bound that can decouple the joint effect of the delays and the bandit feedback. To this end, besides some standard analysis for FTRL and BCO, we need to carefully analyze the delay effect under blocking update to establish an improved upper bound for $\\|\mathbf{y}_m-\mathbf{y}_m^\ast\\|_2$, where $\mathbf{y}_m$ is the preparatory action of our Algorithm 1 and $\mathbf{y}_m^\ast$ is an ideal action defined in line 305 of our paper.
3. Moreover, different from previous studies [Héliou et al., 2020; Bistritz et al., 2022] that only consider convex functions, our paper further investigates two special cases with strongly convex functions, and achieves better regret bounds.

Many thanks for the constructive reviews!

Q1: The practical impact of this theoretical toy seems limited, and the problem was of more interest a couple of years ago. In order to increase the reception, it would be instructive to connect the implications of these findings to other topics of recent interest or include some simulations

A1: Thanks for the suggestion. Please check our common response to the suggestion about experiments, which introduces numerical results completed during the rebuttal period, and has shown the advantage of our algorithm in practice. Moreover, it is also worth noting that our algorithm has a potential application in memory-efficient fine-tuning of large language models (LLM). Very recent studies [1,2] have utilized zero-order optimization algorithms to reduce the memory required by fine-tuning LLM. Our algorithm may be utilized to further achieve the asynchronous update, because of its ability to deal with delayed feedback. We will provide more discussions about our potential applications in the revised version.

[1] Y. Zhang et al. Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark. In ICML, 2024.

[2] S. Malladi et al. Fine-Tuning Language Models with Just Forward Passes. In NeurIPS, pages 53038–53075, 2023.

Q2: Could the authors comment on what the problem looks like for the regular stochastic case with all $f_t=f$ for some fixed $f$, and how this might make the problem easier under delays?

A2: We notice that the stochastic case of delayed online convex optimization (OCO) has been investigated in the pioneering work of Agarwal and Duchi [3], which is referred to as distributed or parallel stochastic optimization with asynchronous update. Therefore, the stochastic case of delayed bandit convex optimization (BCO) reduces to a zero-order variant of this asynchronous optimization problem. Moreover, as discussed in Agarwal and Duchi [3], the stochastic case itself is not sufficient to make the delayed problem easier. Actually, the smoothness assumption on the loss functions is also required.

More specifically, Agarwal and Duchi [3] show that in the stochastic case, the delay only increases the regret of delayed OCO for convex and smooth functions in an additive way, i.e., an $O(\sqrt{T}+d^2)$ regret bound. The key insight for this improvement is that the perturbed error of the delayed stochastic gradients can be much smaller under the smoothness assumption. Therefore, it is natural to conjecture that the stochastic case will make delayed BCO for convex and smooth functions easier in a similar way. We will provide detailed discussions about the stochastic case in the revised version.

[3] A. Agarwal and J. Duchi. Distributed Delayed Stochastic Optimization. In NIPS, pages 873–881, 2011.

Q3: Why do the authors conjecture that the lower bound depends on $\bar{d}$, whereas the upper bound depends on $d$? What improvements would be required to get these to match?

A3: Our conjecture of the dependence on $\bar{d}$ stems from the existing $\Omega(\sqrt{\bar{d}T})$ lower bound [Bistritz et al., 2022] for delayed BCO. However, as discussed in our paper, it is hard for our algorithm to achieve regret bounds depending on $\bar{d}$ due to the blocking update mechanism. Nonetheless, we want to emphasize that our regret bounds achieved via the blocking update mechanism are already quite favorable, and it is highly non-trivial to develop a better algorithm, especially in the case with strongly convex functions. Note that even in the easier full-information setting, previous studies can only achieve the $O(d\log T)$ regret for strongly convex functions, which is the same as the delay-dependent part in our regret bounds for strongly convex functions.