Online Convex Optimization with Prediction Through Accelerated Gradient Descent

We would like to thank the reviewer for all the comments! Below we address the comments in the Weaknesses section.

• Thanks for the suggestion on more experiments! In fact, this can already be observed from the existing experimental results: for the objective function in Eq.13, our online-PGM is a slight variation to RHIG and achieves similar theoretical performance. Thus, the comparison in Figure 4 can be viewed as between RHIG and online-AGM. In Figure 4, notice that when $k$ (the number of steps of prediction) increases, the regret of online-AGM converges to a smaller value than that of online-PGM. As pointed out in line 527 - 529, this might be explained by the robustness of online-AGM to long-term prediction error.

• We use superscript to denote the number of updates that have been applied to a variable, and we use subscript to denote different decision variables. For instance, $x_s^{(l)}$ is the decision variable $x_s$ after $l$ steps of updates. For the online problem, our algorithms indeed construct the decisions in a timely manner ($x_t$ is decided at time $t$): our online-PGM takes $x_t$ as a weighted average of $x_t^{(1)},\ldots, x_t^{(L)}$, and our online-AGM takes $x_t = x_t^{(L)}$, where $L$ is the number of updates to each variable. This is online-implementable, since by time $t$, $x_t^{(1)},\ldots, x_t^{(L)}$ have been calculated already. As an example, if $L=2$, and the graph is a line such that for all $t$, the neighbors for $x_t$ are $x_{t-1}$ and $x_{t+1}$, then $x_t^{(2)}$ depends on $x_{(t-1):(t+1)}^{(1)}$, which further depends on $x_{(t-2):(t+2)}^{(0)}$. Since $x_{(t-2):(t+2)}^{(0)}$ is available at time $t$, $x_{(t-1):(t+1)}^{(1)}$ can be computed and thus is available at time $t$. As a result, $x_t^{(2)}$ can be computed at time $t$, and so is the output.

• When $(a,b) = (1,0)$, our online-AGM has better performance than previously proposed algorithms such as RHIG, in terms of dependency on the initial regret and robustness against long-term prediction error. In terms of the optimality, in Li & Li (2020), a regret lower bound of $\Omega(\sum_{t=1}^T (\frac{1-\sqrt{\kappa}}{1+\sqrt{\kappa}})^{t-1}\delta_t)$ is proved, where the factor for the $t$-step prediction error is $\Omega(\frac{1-\sqrt{\kappa}}{1+\sqrt{\kappa}})^{t-1})$, but the corresponding factor for their proposed RHIG is $(1-\kappa/4)^{t-1}$. For our online-AGM, the corresponding factor is $(1-O(\sqrt{\kappa}))^{t-1}$, which achieves an optimal dependency on $\kappa$, thus closing this gap.

Thank you for all the valuable comments and questions. We would like to make the following comments.

Weaknesses:

1. Regarding the motivation and setup, we would like to provide the following details for the three motivating examples.

• For ``aggregate information'', consider a quadrotor tracking problem, where $x_t$ and $\theta_t$ are the positions of the quadrotor and the target at time $t$, respectively. Then, the difference $x_t - x_{t-1}$ represents the velocity, the second order difference $(x_{t+1} - x_t)- (x_t - x_{t-1})$ represents the acceleration, and the moving average $\frac{1}{a+b+1}\sum_{s = t-a}^{t+b} x_s$ represents the average position of the quadrotor between time $t-a$ and time $t+b$. Thus, when one wants to control the velocities, accelerations, and/or average positions of the quadrotor, the natural way to model the problem is to assume that $f_t$, the objective function at time $t$, depends on $x_{(t-a):(t+b)}$.

• Previous works on online optimization with delayed feedback usually study the static regret or competitive ratio (see [1][2] and the references therein), whereas we look at the dynamic regret; in addition, our work provides some insights into the benefits of having predictions in online decision making.

• For the third motivating example, consider the following problem: there are $B$ servers; at day $t=1,2,\ldots,T-a$, one request arrives and $c_t$, its total reward, is revealed. The request takes $(a+1)$ days to be fulfilled, and can be fulfilled partially: if $0\leq x\leq 1$ fraction of it is fulfilled, the reward will be $c_tx$, and this requires $x$ server from day $t$ till day $t+a$. The decision maker needs to decide $x_t$, the fraction of the day-$t$ request fulfilled, at time $t$, with the goal of maximizing the total reward. (In this case, $b=0$.)

  This can be formulated as an online linear programming problem: $\min_{x_t\in [0,1],~ t = 1,\ldots,T-a} -\sum_{t=1}^{T-a} c_tx_t,\quad s.t.~\sum_{t=\max(1,s-a)}^{s} x_t\leq B,\quad s = 1,\ldots,T-a.$ The Lagrangian for this problem is $\mathcal L(x_{1:(T-a)}, \lambda_{1:(T-a)}) = -\sum_{t=1}^{T-a} c_tx_t + \sum_{s = 1}^{T-a} \lambda_s (\sum_{t=\max(1,s-a)}^{s} x_t- B),$ where $\lambda_s$'s are dual variables and can be interpreted as the shadow prices of the (budget) constraints. Due to strong duality of LP, the original constrained LP is equivalent to minimizing $\mathcal L(x_{1:(T-a)}, \lambda^*_{1:(T-a)})$ where $\lambda^*_{1:(T-a)}$ is an optimal dual. In this setting, one can take $f_t(x_{\max(1,t-a):t};\theta_t) := - c_tx_t + \lambda_t (\sum_{s=\max(1,t-a)}^{t} x_s- B),\quad \theta_t = (c_t,\lambda_t),$ with the true parameter $\theta_t^* = (c_t,\lambda_t^*)$. Then, prior information about the sequence $(c_1,\ldots,c_{T-a})$, such as its distribution, might be used to predict $(\theta_1^*,\ldots,\theta_{T-a}^*)$.

[1] Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. 2022. Multi-agent online optimization with delays: asynchronicity, adaptivity, and optimism. J. Mach. Learn. Res. 23, 1, Article 78 (January 2022), 49 pages.

[2] Weici Pan, Guanya Shi, Yiheng Lin, and Adam Wierman. 2022. Online Optimization with Feedback Delay and Nonlinear Switching Cost. Proc. ACM Meas. Anal. Comput. Syst. 6, 1, Article 17 (March 2022), 34 pages. https://doi.org/10.1145/3508037.

2. Regarding contributions, we would like to make the following clarifications.

• Indeed, online-AGM has better theoretical and experimental performance than online-PGM, and we believe our main algorithmic contribution is online-AGM. We provide the results for online-PGM as a comparison to show the benefit of acceleration. In addition, in the special setting of smoothed online convex optimization studied in Li & Li (2020), our online-PGM is similar to their RHIG. Moreover, we also provide regret guarantees when strong-convexity is relaxed for both online-PGM and online-AGM. To the best of our knowledge, this is the first theoretical guarantee for gradient-based algorithms without strong-convexity in this line of work of online convex optimization with prediction.

• Our online-AGM improves both components in the dynamic regret. For the initialization regret, we improve the factor from $(1-\kappa/4)^{k}$ to $(1-O(\sqrt{\kappa}))^{k}$. For the dependency on the $l$-step prediction error, we improve the factor from $(1-\kappa/4)^{l}$ to $(1-O(\sqrt{\kappa}))^{l}$ -- this implies that our online-AGM is also more robust to long-term prediction error. In fact, Li & Li (2020) shows that the regret's dependency on $l$-step prediction error is $\Omega((\frac{1-\sqrt{\kappa}}{1+\sqrt{\kappa}}))^{l})$, yet their RHIG achieves only $(1-\kappa/4)^{l}$. Thus, in terms of the dependency on long-term prediction error, our online-AGM has an optimal dependency on $\kappa$, and closes the gap. We will expand the discussion in line 178 - 185 to make this more clear.

Thank you for the valuable feedback! We would like to make the following clarifications.

Weaknesses

• Regarding the dynamic regret, in our setup, the decisions at different times lie in different sets: $x_t\in \mathcal X_t$ and $\mathcal X_t$'s can be different for different $t$. For instance, if $\mathcal X_1 = [0,1]^{10}$ and $\mathcal X_2 = [0,1]^{20}$, then there is no natural way to quantify the variation between $x_1$ and $x_2$. Thus, we are not sure if the variation of the comparator sequence (or the offline optimal solution) is a good measure of the difficulty in our setup. If such measure of variation is available (e.g. $\mathcal X_t$'s are the same for all $t$), then the regret of our algorithms may depend -- implicitly through the regret of the initialization -- on the difficulty of the comparator sequence. For instance, if $a+b = 1$ and there are $k$-step exact predictions, then the regret (from line 165) of online-AGM is $O(\kappa^{-1}\rho_1^k\cdot Reg(\mathbf x^{(init)}))$. Thus, if $Reg(\mathbf x^{(init)}) = O(\sqrt{T\mathcal P_T})$ where $\mathcal P_T$ quantifies the variation of the comparator sequence, then the regret of online-AGM is $O(\kappa^{-1}\rho_1^k\cdot \sqrt{T\mathcal P_T})$.

• Regarding the writing quality, we would like to thank the reviewer for all the suggestions! We will add a summary section and make the paper more readable by polishing and restructuring.

• Regarding Figure 3, we use colors (degrees of ``redness'') to represent the number of updates that have been applied to the vertices: the darker a vertex is, the more updates it has received. We agree that Figure 3 is a bit confusing and need more explanations, and it might be better to move it to the appendix.

• The suggestion that the experiments could be moved to the appendix sounds reasonable, and we will add a discussion/conclusion in the revision.

Questions

Sorry for the confusion. We assume that the functional form of $f_t(\cdot;\theta_t)$ is known for each $\theta_t$, and what is unknown is the true parameter $\theta_t^*$. The feedback is not the function values (evaluated at, say, $x_{t-a:t}$ and some hypothetical $x_{t+1:t+b}$); instead, after committing $x_t$ at time $t$ (and cannot be modified in the future), the process goes to time $t+1$, and at the beginning of time $t+1$, the decision maker is given information about $\theta_{t+1}^*$ (as well as about future parameters).

Thank you for all the valuable comments and questions! We would like to provide the following clarifications to the concerns and questions raised in the Weaknesses section.

1. Yes, we will provide specific real-world examples in the revised version. Below are two possible relevant settings.

• Consider a simplified data center management problem, where $\theta_t$ and $x_t$ are the numbers of requests and active servers at time $t$, respectively. Then $f_t$ is the sum of the operating cost (which depends on $x_t,\theta_t$) and the switching cost (which depends on $x_t - x_{t-1}$). Prediction in this setting means prediction of the number of requests during time $t+1,\ldots,t+k$.
• Consider a quadrotor tracking problem, where $x_t$ and $\theta_t$ are the positions of the quadrotor and the target at time $t$, respectively. Then $f_t$ is the sum of the distance to the target ($\|x_t - \theta_t\|^2$) and the cost to change the position (which depends on $x_t - x_{t-1}$) and/or velocity (which depends on $(x_{t+1} - x_t)- (x_t - x_{t-1})$). Prediction in this setting means prediction of the positions of the target during time $t+1,\ldots,t+k$.

2. Indeed, the decision maker only decides $x_t$ at time $t$. However, the goal is to minimize the cumulative cost $C = \sum_{t=1}^T f_t$, which is fully determined by time $T$.

• One practical example is tracking problems which also control the acceleration. Consider a quadrotor tracking problem, where $x_t$ and $\theta_t$ are the positions of the quadrotor and the target at time $t$, respectively. Noticing that $(x_{t+1} - x_t)- (x_t - x_{t-1})$ represents the acceleration, then $f_t(x_{(t-1):(t+1)};\theta_t) = (x_t - \theta_t)^2 + ((x_{t+1} - x_t)- (x_t - x_{t-1}))^2$ can be used to control the distance to the target together with the acceleration. In fact, this is an example of the ``aggregate information'' mentioned in motivating example 1, line 82 - 86.
• Another practical example is delayed decision making (motivating example 2, line 87 - 90): if $f_t$ depends only on $x_{t+b}$ for all $t$, then $x_s$, the decision made at time $s$, affects only $f_{s-b}$. That is, the decision making is delayed for $b$ steps.

3. Sorry for the confusion about $\theta$. We assume that the functional form of $f_t(\cdot;\theta_t)$ is known for each $\theta_t$, and what is unknown is the true parameter $\theta_t^*$. We will clarify this in the setup.

4. Regarding $R_0$, we would like to make the following comments.

• In Theorem 3 of Li et al. (2021), the authors give regret upper bound which depends on the regret of the initialization ($Reg(\phi)$ in their notation); in addition, this holds under the assumption that the objective function is strongly convex. Under this assumption, $\|\mathbf{x}^{(init)} - \mathbf{x}^{*}\|$ can be upper bounded by $Reg(\mathbf{x}^{(init)})$. Thus, as discussed in line 162 - 166, our Theorem 1.1 implies that the regret of our online-AGM is $O(\kappa^{-1}\rho_1^k\cdot Reg(\mathbf{x}^{(init)})) + \text{prediction error}$.
• We also provide results when the strong-convexity assumption is relaxed ($\kappa=0$, Theorem 1.1). Without strong-convexity, indeed our regret depends on $R_0$. This inherits from the convergence analysis of classical offline algorithms such as (accelerated) gradient descent. To the best of our knowledge, this is the first performance guarantee for gradient-based algorithms for this problem without strong-convexity.
• Admittedly, $R^2_0$ can scale as $O(T)$. However, when strong convexity holds, with even just $k = O(\log(T))$ steps of prediction and look-ahead initialization, constant (independent of $T$) regret can be achieved. Without strong-convexity, the regret for online-AGM is $O(T/k^2)$; if $k = \Omega(T^{\alpha})$ for some $\alpha>0$, then the regret is $O(T^{1-2\alpha})$, sublinear in $T$.

5. We believe that the main novelty is the connection between online and offline problems, as established in Section 3.2: we view offline iterative algorithms from a state-transition perspective, and thus can be implemented in an online fashion (exactly or approximately) using only sequentially revealed information. The performance of the online algorithms (regret) follows directly from the convergence guarantees of the offline algorithms, which greatly simplifies the analysis. In addition, the rich literature of classical offline optimization problems could bring new insights into the online optimization.

6. Thanks for the suggestion! We will improve the presentation/display in the revised paper.