Abstract

Bandit convex optimization (BCO) is a fundamental online learning framework with partial feedback, where the learner observes only the loss incurred at the chosen decision point in each round. In this work, we investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner. Specifically, given gradient predictions \(m_t\), we seek regret bounds that scale with the cumulative prediction error \(S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2.\) We first establish a negative result: under the single-point feedback protocol, an unavoidable \(\Omega(\sqrt{T})\) regret lower bound persists even when \(S_T=o(T)\), showing that the variance of gradient estimation fundamentally obscures the benefit of accurate predictions. To overcome this barrier, we propose Two-Point Variance-Reduced Optimistic Gradient Descent (TP-VR-OPT) for the two-point feedback setting. The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm. This yields a regret bound of \(O\big(\sqrt{d\,\mathbb{E}[S_T]}\big),\) where \(d\) is the decision dimension. Complementing this result, we establish an information-theoretic lower bound that scales as \(\Omega(\sqrt{\mathbb{E}[S_T]})\), providing a fundamental characterization of the best achievable prediction-adaptive regret and showing that TP-VR-OPT is optimal up to a factor of \(\sqrt d\). We further develop adaptive variants that eliminate the need for prior knowledge of \(\mathbb{E}[S_T]\) or the horizon \(T\), and extend our framework to non-stationary environments, establishing dynamic regret guarantees that adapt simultaneously to the cumulative prediction error and the comparator path length.

1 Introduction↩︎

Online convex optimization (OCO) provides a powerful and unified theoretical framework for sequential decision-making problems [1]–[4]. In the OCO setting, at each round \(t\in[T]\), where \([T]=\{1,\ldots,T\}\), the learner selects a decision point \(x_t\in \mathcal{X}\) from a convex set \(\mathcal{X}\subseteq \mathbb{R}^d\). The environment then reveals a loss function \(f_t:\mathcal{X}\rightarrow \mathbb{R}\), after which the learner incurs a loss \(f_t(x_t)\) and updates the decision point to \(x_{t+1}\). The performance is measured via the regret, defined as the cumulative loss relative to the best fixed decision in hindsight.

In many practical applications, however, the learner does not have access to the full loss function or its gradient. Instead, a more common scenario is that the environment only reveals the loss incurred at the chosen decision point, rather than the entire function. This setting, in which the learner only observes the zero-order (function value) information, is known as Bandit Convex Optimization (BCO) [5], [6]. The central challenge in BCO is that, due to the lack of direct gradient information, the learner must construct gradient estimates using random perturbations and a limited number of loss evaluations to update the learner’s decision.

From a worst-case perspective, in the OCO setting, an \(O(\sqrt{T})\) static regret is typically achievable under the full-information feedback protocol, which serves as a standard baseline in online learning. In contrast, due to the limited feedback available in BCO, regret bounds are generally worse as a consequence of the stability-variance tradeoff. Specifically, under the two-point feedback protocol, one can still achieve \(O(\sqrt{T})\) regret bound [7], whereas under the single-point feedback protocol, the bounds are \(O(T^{3/4})\) [5] for Lipschitz loss functions and \(O(T^{2/3})\) [8] for smooth loss functions. However, all of these guarantees are worst-case. Even when the environment is significantly more benign in practice, such analyses yield only worst-case regret bounds and do not adapt to favorable structure in the loss sequence.

In contrast, an important line of work in the full-information OCO setting shifts the focus from purely worst-case optimization to adaptivity to benign environments, while still retaining robustness to adversarial scenarios [9], [10]. A standard approach to achieving such adaptivity is through optimism or prediction [11], [12]. Specifically, before the beginning of each round, the learner has the ability to compute a prediction \(m_t\) of the next gradient based on historical information and incorporate this prediction into the update rule. Therefore, the regret bound need not scale solely with \(T\); instead, it can be expressed in terms of the cumulative prediction error, typically of the form \(S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2\). Intuitively, when the environment becomes predictable, slowly changing, or exhibits small gradient variation, the predictions \(m_t\) can be accurate, leading to regret bounds that are significantly smaller than the worst-case \(O(\sqrt{T})\) guarantee. If instead the environment is fully adversarial, such methods still recover the standard worst-case performance.

One natural question is: Can prediction-based adaptivity and acceleration in full-information OCO be extended to the BCO setting? In other words, can we design algorithms whose regret is dominated by the prediction error, rather than being fundamentally limited by the worst-case dependence on the time horizon \(T\) under bandit feedback? Furthermore, is it possible to construct a mechanism under which the regret in BCO is significantly better than \(O(\sqrt{T})\) when the prediction is accurate, and then achieve acceleration on favorable instances?

The key challenge is that the gradient estimator in BCO inherently exhibits non-negligible randomness and variance, whereas the benefit of prediction relies on the algorithm’s ability to detect and exploit small residual errors. If the noise in the gradient estimator dominates this residual, then even highly accurate predictions \(m_t\) cannot be effectively leveraged in the update. Consequently, to achieve the adaptive regret bound in terms of prediction error, it is not sufficient to merely incorporate \(m_t\) into the update rule. The gradient estimator itself must be carefully designed such that the variance of the estimator decreases as the prediction residual becomes smaller. This observation suggests that the central question in prediction-adaptive BCO is not only how to use the prediction in the update, but also whether the feedback protocol makes the prediction residual observable with sufficiently small variance.

Based on the above motivations, we study the BCO problem with optimistic gradient prediction. We define the cumulative prediction error and its expectation, respectively, as \[\label{eq:defst} S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2\quadand\quad \bar S_T=\mathbb{E}[S_T].\tag{1}\] Note that the expectation is with respect to the (random) choice of the action \(x_t\). Our objective is to obtain regret guarantees that depend purely on \(\bar S_T\). When \(\bar S_T=o(T)\), the regret should improve accordingly, while for large \(\bar S_T\), the algorithm should inherit the \(O(\sqrt{T})\) worst-case performance. Furthermore, considering practical non-stationary environments, we also study the dynamic regret, which allows the regret to jointly reflect both the variation of the environment and the cumulative prediction error. The variation of the environment is captured by the path length \(P_T(u_{1:T})=\sum_{t=2}^T \|u_t -u_{t-1}\|\) of the comparator sequence \(\{u_t\}_{t=1}^T\).

1.1 Main Contributions↩︎

We summarize our main contributions in this section.

c c ccc Measure & Algorithm & Prediction Adaptivity & Free of \(\bar S_T/T/P_T\) & Regret Guarantees
& Shamir [7] & & & \(O(\sqrt{d T})\)
& (Theorem [thm:two95point]) & & & \(O(\sqrt{d\bar S_T})\)
& (Theorem [thm:tp-vr-adaptive]) & & & \(\widetilde{O}(\sqrt{d\bar S_T})\)
& Zhao et al. [13] & & & \(O(d\sqrt{T(1+ P_{T})})\)
& He et al. [14] & & & \(O(\sqrt{d\,T(1+ P_{T})})\)
& (Theorem [thm:dynamic95regret]) & & & \(O(\sqrt{d\,\bar{S}_{T}(1+ P_{T})})\)
& (Theorem [thm:tp-vr-opt-pp]) & & & \(\widetilde{O}(\sqrt{d\,\bar{S}_{T}(1+ P_{T})})\)

\(\bullet\) Single-Point Feedback Barrier. We first show that under the single-point feedback protocol, one cannot overcome the unavoidable \(\Omega(\sqrt{T})\) barrier, even when the cumulative prediction error is negligible, i.e., \(\bar{S}_T=o(T)\). This lower bound reveals an information-theoretic bottleneck insofar that the inherently large variance of the single-point estimator masks the benefit of the optimistic prediction, thereby preventing the establishment of an adaptive regret bound that depends purely on \(S_T\). This motivates our study of the two-point feedback protocol in the following sections.

\(\bullet\) Optimal Adaptivity with Two-Point Feedback. To overcome the \(\Omega(\sqrt{T})\) barrier under the single-point feedback protocol, we turn to studying the case of two-point feedback. We propose a new algorithm, Two-Point Variance-Reduced Optimistic Gradient Descent (TP-VR-Opt). The key difference between our proposed algorithm compared to classical two-point feedback estimators lies in how we introduce the optimistic prediction when designing the estimator. Instead of directly estimating the gradient \(\nabla f_t(x_t)\), we incorporate the optimistic prediction \(m_t\) as a baseline and construct an estimator for the residual \(\nabla f_t(x_t)-m_t\). This design ensures that the estimation variance scales with the prediction error \(\|\nabla f_t(x_t)-m_t\|^2\), rather than the gradient norm. As a consequence, our proposed algorithm TP-VR-Opt achieves the regret bound \(O(\sqrt{d\bar S_T})\). We also show that this regret bound matches the information-theoretic lower bound up to a \(\sqrt{d}\) factor.

\(\bullet\) Adaptive Implementation via Observable Residual Doubling. The optimal regret bound of TP-VR-Opt relies on tuning certain parameters with oracle information of the expectation of the cumulative prediction error \(\bar S_T\) and the horizon \(T\). To make our proposed algorithm practically applicable, we propose TP-VR-Opt+ using a nested doubling-trick approach, which can achieve the same regret guarantee as TP-VR-Opt up to logarithmic factors, without requiring any prior knowledge of \(\bar S_T\) and \(T\). Specifically, the bandit-specific issue is that \(\bar S_T\) is unobserved; we therefore use the observable residual \(\sum_t\|\widehat g_t-m_t\|^2\) as the doubling trigger.

\(\bullet\) Applications to Dynamic Regret. To demonstrate the effectiveness of our proposed prediction-dependent algorithms in non-stationary environments, we extend our analysis from static regret to dynamic regret. We first show that our proposed TP-VR-Opt can achieve a dynamic regret bound \(O(\sqrt{d\,\bar{S}_{T}(D^{2}+D P_{T})})\), which depends jointly on the cumulative prediction error \(\bar S_T\) and the comparator path-length \(P_T\). To remove the need for prior knowledge of these quantities, we further propose TP-VR-Opt++ built upon TP-VR-Opt+, which leverages the meta-expert framework by maintaining and aggregating a grid of candidate step sizes to adapt to the best choice in hindsight. We show that TP-VR-Opt++ attains the same dynamic regret bound \(\tilde{O}(\sqrt{d\,\bar{S}_{T}(D^{2}+D P_{T})})\) up to logarithmic factors, without requiring any prior knowledge of \(\bar S_T\), \(P_T\), and \(T\).

A summary of our results, together with comparisons with related existing results, is included in Table ¿tbl:tab:summary?.

Bandit Convex Optimization (BCO). BCO can be viewed as a fundamental extension of OCO under partial feedback [6]. Two standard feedback protocols are commonly studied in BCO: single-point feedback and two-point feedback. Under the single-point feedback protocol, the learner observes only a single loss value \(f_t(x_t)\) at each round and constructs a biased or unbiased gradient estimator using the smoothed version of \(f_t\) together with a random perturbation direction. The seminal work [5] introduced the framework of gradient descent without gradient information. The static regret bounds under single-point feedback are \(O(T^{3/4})\) [5] for Lipschitz loss functions and \(O(T^{2/3})\) for smooth [8] or strongly-convex [15] loss functions. When loss functions are both smooth and strongly convex, an \(O(\sqrt{T\log T})\) regret bound is achieved [16]. Moreover, for general convex losses, the regret has been further improved to \(O(\mathrm{poly}(\log T)\sqrt{T})\), albeit with a strong dependence on the dimension \(d\) [17]–[19]. Under the two-point feedback protocol, the learner can query the loss at two nearby points and construct a symmetric difference estimator, which significantly reduces the estimation variance and yields an \(O(\sqrt{T})\) order regret bound [7]. Lower bounds for BCO under various feedback models have been studied in [20], [21].

Prediction/Optimism Adaptivity. In the full information OCO setting, the regret can be expressed in terms of the prediction error rather than the time horizon \(T\) by employing optimistic updates when the environment exhibits a predictable structure. A canonical framework for this approach is the optimistic mirror descent (OMD) algorithm [11], [22]. Another important line of work studies regret bounds based on gradual variation. Chiang et al. [9] introduced bounds based on gradient variation as a problem-dependent measure. The bounds based on gradient variation imply small-loss bounds [10]. More broadly, prediction can be viewed as additional hints provided to the learner [23], [24]. Recently, the Stochastically Extended Adversarial or SEA model [25] was proposed to bridge the gap between adversarial and stochastic OCO.

Incorporating prediction and optimism into bandit feedback presents challenges. Yang and Mohri [26] studied optimistic bandit convex optimization by constructing predictions from historical gradients. Chiang et al. [27] obtained a regret bound in terms of gradient variation under two-point feedback. Wei and Luo [28] and Rakhlin and Sridharan [11] studied the multi-arm bandits and linear bandits under this setting, respectively. Wei et al. [29] achieved an improved regret bound by leveraging loss predictors in the contextual bandit setting. Sequential prediction and regret under probabilistic losses have also been studied from an information-theoretic and Bayesian perspective [30]. In contrast, our predictions are gradient-valued hints used under bandit convex feedback, and the main challenge is to make the estimation variance scale with the gradient-prediction residual. Recent work has also highlighted connections between regret guarantees and time-uniform statistical guarantees in sequential decision problems, for example through universal-portfolio-based confidence sequences [31]. Our focus is different that we use gradient predictions to reduce the variance of bandit gradient estimators, so that regret scales with the gradient-prediction residual.

Dynamic Regret. The dynamic regret with path-length measure was first introduced by [32] and studied in [32]–[34]. Zhang et al. [35] obtained dynamic regret bounds that match the lower bound using an online ensemble framework. Zhao et al. [10] incorporated gradient variation into dynamic regret analysis and derived problem-dependent dynamic regret bounds. In the bandit feedback case, Zhao et al. [13] systematically studied the dynamic regret under the single-point and two-point feedback protocols. Recently, He et al. [14] improved two-point feedback dynamic regret bounds of [13] by a factor of \(O(\sqrt{d})\). The use of expert aggregation to compete with time-varying benchmarks is also closely related to the tracking-the-best-expert literature [36]. Our meta-expert layer differs in that each expert is itself a prediction-centered two-point bandit algorithm with a different stepsize.

2 Problem Setup and Preliminaries↩︎

In this section, we describe the problem setup of BCO with prediction and present notations and preliminaries.

Notation. Let \([T]=\{1,\dots,T\}\). We denote \(\langle \cdot,\cdot\rangle\) for the Euclidean inner product and \(\|\cdot\|\) for the Euclidean norm. Let \(\mathcal{B}=\{x\in\mathbb{R}^{d}:\|x\|\le 1\}\) be the unit ball and \(\mathbb{S}^{d-1}=\{v\in\mathbb{R}^{d}:\|v\|=1\}\) be the unit sphere.

The learner chooses points in a nonempty convex set \(\mathcal{X}\subset \mathbb{R}^{d}\) with finite diameter i.e., \(D=\sup_{x,y\in\mathcal{X}}\|x-y\|< \infty\). We assume that the convex set \(\mathcal{X}\) is well-rounded, i.e., there exist \(0< r\leq R<\infty\) such that \(r\mathcal{B}\subseteq \mathcal{X}\subseteq R\mathcal{B}\). We also assume that \(0\in\mathcal{X}\).

At each round \(t\in[T]\), the environment selects a convex function \(f_{t}:\mathcal{X}\rightarrow \mathbb{R}\). The learner incurs a loss \(f_{t}(x_{t})\) when its action is \(x_{t}\). The performance metric is the regret \[\label{eq:regret95def}\mathfrak{R}_{T}=\sum_{t=1}^{T}f_{t}(x_{t})-\min_{x\in\mathcal{X}}\sum _{t=1}^{T}f_{t}(x).\tag{2}\] For a fixed comparator \(u\in\mathcal{X}\), we also write the regret as \(\mathfrak{R}_{T}(u)=\sum_{t=1}^{T}(f_{t}(x_{t})-f_{t}(u))\).

Assumption 1 (Lipschitz Continuity). For all \(t \in [T]\), the loss function \(f_{t}: \mathcal{X}\to \mathbb{R}\) is convex on \(\mathcal{X}\) and \(L\)-Lipschitz continuous. That is, \(|f_{t}(x) - f_{t}(y)| \le L \|x - y\|\). Therefore, if \(f_{t}\) is differentiable, the gradient is bounded as \(\|\nabla f_{t}(x)\|\le L\) for all \(x\in\mathcal{X}\).

Assumption 2 (Smoothness). For all \(t \in [T]\), the loss function \(f_{t}\) is differentiable on \(\mathcal{X}\) and \(\beta\)-smooth. That is, for all \(x, y \in \mathcal{X}\): \(\|\nabla f_{t}(x) - \nabla f_{t}(y)\|\le \beta \|x - y\|\).

Remark 1 (The necessity of the smoothness assumption). The worst-case baselines listed in Table ¿tbl:tab:summary? typically rely only on the Lipschitz continuity without requiring the smoothness assumption as stated in Assumption 2. However, to achieve the prediction adaptive regret bound that depends solely on \(\bar S_T\) defined in 1 , we impose the smoothness assumption throughout this work. This smoothness assumption is also consistent with the most closely related variation-adaptive and prediction-adaptive literature. In the bandit setting, gradient-variation bounds such as [27], [37] rely on smoothness to control the bias introduced by local function-value queries. In full-information settings, analogous prediction or gradient variation-adaptive bounds are also commonly obtained under smoothness assumptions [10], [25], [35].

Under the two-point feedback protocol, the “local first-order information” observed along a direction \(v\) at scale \(\delta\) is given by the local secant slope \(\big(f_t(y_t+\delta v)-f_t(y_t-\delta v)\big)/(2\delta)\). In worst-case analysis with only the Lipschitz continuity assumption, this symmetric difference can result in the local secant slope being uniformly bounded by the Lipschitz constant \(L\), which implies that \(\|\hat{g}_t\|\leq dL\) for the gradient estimator \(\hat{g}_t\). Plugging this into the standard stability–variance tradeoff yields \(O(\sqrt{T})\) regret guarantee.

Our objective is substantially stronger: we wish to bound the regret in terms of only the expected gradient-prediction error \(\bar S_T\). The natural observable residual signal associated with direction \(v\) is the difference between the secant slope and the predicted directional derivative \(\left\langle m, v \right\rangle\), i.e., \[\frac{f(y + \delta v)-f(y-\delta v)}{2\delta} - \langle m, v\rangle=\langle \nabla f(y)-m, v\rangle + \frac{r(v)}{2\delta},\] where \(r(v)=f(y+\delta v)-f(y-\delta v)-2\delta\langle \nabla f(y),v\rangle\) is the observable residual. To ensure this observable residual is small and thus to obtain the regret in terms of prediction adaptivity, we should ensure that \(r(v)\) vanishes as \(\delta\to 0\). Under the smoothness condition, we have \(|r(v)|\leq \beta\delta^2\) implying \(|r(v)|/2\delta=O(\beta\delta)\). However, under Lipschitz continuity alone, it is possible that \(|r(v)|/(2\delta)=\Theta(L)\), i.e., this observable residual remains constant and non-vanishing (as \(\delta\to0\)) even when \(m=\nabla f(y)\), as shown in Appendix 7. Therefore, this term introduces a constant independent of the prediction error, leading to an \(\Omega(\sqrt{T})\) order floor akin to that in the worst-case analysis. This justifies the need for us to impose Assumption 2.

We now formally describe the standard BCO protocol. One-point and two-point bandit feedback. We adopt a standard “internal point + perturbation” protocol throughout this work. We denote the perturbation radius as \(\delta\in(0,r)\). To ensure feasibility, we define the shrinkage coefficient \(\alpha=\delta/r\) and the shrunk decision set \(\mathcal{X}_{\alpha}=(1-\alpha)\mathcal{X}\).

At each round \(t\): The learner chooses a center point \(y_{t}\in\mathcal{X}_{\alpha}\) and samples a direction \(v_{t}\sim \text{Unif}(\mathbb{S}^{d-1})\), where \(\text{Unif}(\mathbb{S}^{d-1})\) denotes the uniform distribution on \(\mathbb{S}^{d-1}\). The learner plays \(x_{t}=y_{t}+\delta v_{t}\). Under the single-point feedback, the learner observes \(f_{t}(x_{t})\), while the learner can observe \(f_{t}(y_{t}+\delta v_{t})\) and \(f_{t}(y_{t}-\delta v_{t})\) under the two-point feedback.

Since \(y_{t}\in(1-\alpha)\mathcal{X}\) and \(\delta=\alpha r\), we have \((1-\alpha)\mathcal{X}+\alpha r \mathcal{B}\subseteq (1-\alpha)\mathcal{X}+\alpha \mathcal{X}=\mathcal{X}\), which implies \(y_{t}+\delta v_{t}\in \mathcal{X}\) for all \(v_t\) such that \(\|v_{t}\|\leq 1\).

Remark 2. In the two-point setting, \(y_{t}-\delta v_{t}\) is an auxiliary query point, used only for gradient estimation. For computing regret, we only consider loss at the point \(x_t = y_t + \delta v_t\) in this work. We note that for the two-point feedback bandit convex optimization problem, different types of regret definitions are considered in the literature. Some works measure performance at the center point \(y_{t}\) [7] as \(\sum_{t=1}^{T}f_{t}(y_{t}) - \min_{x \in \mathcal{X}}\sum_{t=1}^{T}f_{t}(x)\), while others consider the average loss over the query pair [13]: \(\sum_{t=1}^{T}\left(\frac{1}{2}f_{t}(y_{t}+\delta v_{t}) + \frac{1}{2}f_{t}( y_{t}-\delta v_{t})\right) - \min_{x \in \mathcal{X}}\sum_{t=1}^{T}f_{t}(x)\). However, since each \(f_{t}\) is assumed to be \(L\)-Lipschitz and the perturbation radius is controlled by \(\|x_{t}- y_{t}\| = \delta\), these definitions are equivalent up to lower-order terms of order \(O(L \delta T)\). For convenience and to reflect the true cost, we adopt the definition as Eqn. 2 .

Below, we will formally define the prediction settings.

History and Prediction. Let \(\mathcal{H}_{t-1}\) denote the \(\sigma\)-field generated by all historical information till time \(t-1\), which includes the sequence of actions, predictions, and observed feedbacks up to round \(t-1\), i.e., \(\mathcal{H}_{t-1} = \sigma\big(\{y_{\tau}, m_{\tau}, f_{\tau}(y_{\tau}\!+\!\delta v_{\tau})\}_{\tau=1}^{t-1}\big)\) for single-point feedback, or \(\mathcal{H}_{t-1} = \sigma\big(\{y_{\tau}, m_{\tau}, f_{\tau}(y_{\tau} \pm \delta v_{\tau})\}_{\tau=1}^{t-1}\big)\) for two-point feedback. Before taking the action at round \(t\), the learner generates a raw prediction vector \(\widetilde{m}_t\in\mathbb{R}^d\), which is \(\mathcal{H}_{t-1}\)-measurable. Throughout the algorithm and the analysis, we use its clipped version \(m_t = \Pi_{L\mathbb{B}}(\widetilde{m}_t)\), where \(L\mathbb{B}=\{x\in\mathbb{R}^d:\|x\|\le L\}\). Hence \(\|m_t\|\le L\). This clipping is without loss of generality. By Assumption 1, \(\|\nabla f_t(x)\|\le L\) for all \(x\in\mathcal{X}\), and Euclidean projection onto the ball \(L\mathbb{B}\) does not increase the distance to any vector in \(L\mathbb{B}\). Therefore, replacing \(\widetilde{m}_t\) by \(m_t\) does not increase the prediction error \(\|\nabla f_t(x)-m_t\|\).

This question of how to exploit a history-based gradient prediction sequence to improve regret is well-studied in the full-information OCO setting. In particular, optimistic algorithms, such as Optimistic Mirror Descent (OMD) [11], leverage past gradient information to adapt the updates so that the regret scales with the prediction error rather than the horizon. However, in the bandit setting, it is not immediately clear that such predictors can be effectively exploited. Nevertheless, it is straightforward to construct admissible predictors using past observations: for example, a coordinate-persistent predictor stores the most recent finite-difference estimate for each coordinate. At each round, the predicted directional derivative can be compared against the observed two-point slope, allowing a variance-reduced residual estimator to be constructed whose variance scales with the prediction error \(\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2\) rather than the gradient magnitude itself. This ensures that using \(m_t\) remains meaningful and well-defined even in the bandit context.

This viewpoint is standard in the hints/prediction literature. For instance, Wei et al. [29] study contextual bandits with predictors available before action selection, while Lyu and Cheung [38] consider online resource allocation with bandit feedback and advice. Our focus is the complementary question: given an arbitrary admissible predictor, can a bandit algorithm exploit it so that the regret scales with the realized prediction error? Specifically, in Section 4.2, we further illustrate that, under coordinate sampling, a coordinate-persistent predictor recovers the gradually evolving worlds result of [27] as a special case. Thus, our framework generalizes prior constructions while remaining fully implementable in the bandit setting.

3 The Single-Point Feedback Barrier↩︎

The main goal of this work is to bound the regret in terms of the cumulative prediction error \(S_{T}=\sum_{t=1}^{T}\|\nabla f_{t}(x_{t})-m_{t}\|^{2}\), which effectively replaces the dependence on the horizon \(T\). The worst-case regret bound with smooth convex function under single-point feedback is \(O(T^{2/3})\) [8]. Ideally, one might expect that with the help of optimistic predictions, this regret could be improved to an adaptive bound of order \(O(\bar S_{T}^{2/3})\) in this setting where \(\bar{S}_{T}= \mathbb{E}[S_{T}]\). However, we will show that obtaining such a purely \(\bar S_{T}\)-dependent bound is impossible under single-point feedback. We show an unavoidable lower bound on the regret to be \(\Omega(\sqrt{T})\). This holds even in favorable environments where the cumulative prediction error is negligible, i.e., \(S_{T}=o(T)\), which implies that the \(\Omega(\sqrt{T})\) cost is inherent in the one-point feedback mechanism regardless of the prediction accuracy.

We capture this single-point feedback barrier via a two-hypothesis test with linear losses together with independent and identically distributed Gaussian noise components.

Theorem 3. Fix a convex set \(\mathcal{X}\subset \mathbb{R}^{d}\) with Euclidean diameter \(D\). Given \(T\ge 1\), a Lipschitz constant \(L>0\), and a noise scale \(\sigma > 0\) such that \(\sigma \le 2LD\sqrt{T}\). In the single-point feedback setting, for any algorithm \(\mathcal{A}\) with optimistic prediction \(m_{t}\), there exists a random environment for which each \(f_{t}\) is convex, \(L\)-Lipschitz, and \(\beta\)-smooth, and the expected regret is lower bounded as \[\mathbb{E}[\mathfrak{R}_{T}]\geq \frac{3}{16}\sigma\sqrt{T}.\]

Theorem 3 demonstrates that additive offsets create an information-theoretic bottleneck for single-point feedback, enforcing a universal \(\Omega(\sqrt{T})\) lower bound. Specifically, we construct a hard instance with a linear loss function \(f_t(x) = -M \varepsilon \langle v, x - x_0 \rangle + \xi_t\), where \(M\in \{-1,+1\}\) is sampled uniformly at random and then fixed for all rounds, \(\xi_t \sim \mathcal{N}(0, \sigma^2)\) and \(\varepsilon=\sigma/(2D\sqrt{T})\). Since the gradient is constant over time and has norm \(\varepsilon\), the best history-based cumulative prediction error is at most \(T\varepsilon^2=\sigma^2/(4D^2)=O(1)\).

Hence, Theorem 3 shows that the obstruction under single-point feedback is observational rather than algorithmic. Even if the gradient sequence is highly predictable, the learner only observes an absolute function value at the queried point. Such an observation mixes the local first-order signal with zero-order offsets. In the hard instance above, the linear component determines the optimal decision, but the additive offset makes the two possible gradient directions statistically difficult to distinguish from single-point observations. Consequently, a small prediction error \(S_T\) alone does not guarantee that the learner can exploit the prediction. The predictor may be accurate in the sense that \(\nabla f_t(x_t)-m_t\) is small, but the bandit observation may still fail to reveal this residual with sufficiently small variance. Therefore, no regret bound depending only on \(S_T\) can hold in the single-point model. This motivates the two-point feedback protocol studied next: by comparing two symmetric function values, the learner can cancel common zero-order offsets and directly estimate a local residual relative to the prediction.

4 Two-Point Feedback: Prediction-sensitive Variance Reduction↩︎

The lower bound established in Theorem 3 reveals a fundamental limitation of single-point feedback. Because the learner relies heavily on absolute function values to estimate gradients and lacks a comparative baseline within each epoch, it cannot distinguish between local gradient changes and zero-order noisy bases (e.g., additive offsets \(\xi_{t}\)).

In this section, we overcome this information bottleneck by considering the two-point feedback model. The structural advantage of this protocol lies in its use of differences. Through the query of two relevant points, the learner is able to filter out the zero-order noise effectively and focus on the local variations of the function. This process overcomes the \(\Omega(\sqrt{T})\) lower bound and achieves an adaptive regret bound which solely depends on \(\bar S_{T}\).

4.1 The TP-VR-Opt Algorithm↩︎

Recalling the two-point feedback protocol shown in Section 2: In round \(t\), the learner selects a center point \(y_{t}\in \mathcal{X}_{\alpha}\), samples a random direction \(v_{t}\sim \mathrm{Unif}(\mathbb{S}^{d-1})\), and performs a perturbation on the point \(x_{t}=y_{t}+\delta v_{t}\in \mathcal{X}\). Under the two-point feedback mechanism, the learner observes the function values at two symmetrical points around the center point: \(f_{t}(y_{t}+\delta v_{t})\) and \(f_{t}(y_{t}-\delta v_{t})\). Our main goal is to obtain the adaptive regret with the prediction quality. We retain the definition of prediction sensitivity from 1 as \(S_{T} = \sum_{t=1}^{T}\|\nabla f_{t}(x_t)- m_{t}\|^{2}\). Since the chosen point \(x_{t}\) depends on the learner’s internal randomization \(v_{t}\), \(S_{T}\) is a random variable. Our bounds are thus expressed in terms of its expected value \(\bar S_{T}= \mathbb{E}[S_{T}]\).

To achieve this goal, we incorporate the optimistic prediction \(m_{t}\) into our algorithm. Based on insights of optimistic algorithms such as OMD, we maintain and update two sequences \(\{y_{t}\}\) and \(\{y'_{t}\}\). However, trivially incorporating \(m_t\) into the update rule is insufficient since the classic two-point feedback estimator \(\hat{g}_{t}=\frac{d}{2\delta}\left(f_{t}(y_{t}+ \delta v_{t}) - f_{t}(y_{t}- \delta v_{t})\right)v_{t}\) suffers from high variance that scales with the gradient norm. Instead, we introduce a variance-reduced estimator defined as \(\hat{g}_{t}= m_{t}+ \frac{d}{2\delta}\Delta_{t}v_{t}\), where \(\Delta_{t}= f_{t}(y_{t}+ \delta v_{t}) - f_{t}(y_{t}- \delta v_{t}) - 2\delta \langle m_{t}, v_{t}\rangle\). This estimator uses \(m_{t}\) as a baseline to reduce variance, ensuring that the estimation error scales with the prediction error rather than the gradient norm. We present the detailed procedure of our proposed Two-Point Variance-Reduced Optimistic Gradient Descent (TP-VR-Opt) algorithm in Algorithm 1.

The estimator in Line 5 should be viewed as estimating the residual around \(m_t\), rather than estimating the full gradient from scratch. To see this, denote \(g_t^y=\nabla f_t(y_t)\) and \(a_t=g_t^y-m_t\). Define the symmetric-difference remainder as \[r_t= f_t(y_t+\delta v_t)-f_t(y_t-\delta v_t) -2\delta\langle g_t^y,v_t\rangle.\] Then the centered difference used in Algorithm 1 satisfies \[\Delta_t = 2\delta\langle a_t,v_t\rangle+r_t.\] Plugging the identity \(\Delta_t=2\delta\langle a_t,v_t\rangle+r_t\) into the definition of \(\widehat g_t\) gives \[\widehat g_t-m_t = d\langle a_t,v_t\rangle v_t + \frac{d}{2\delta}r_t v_t .\] This decomposition makes explicit that the random part of the estimator is centered around the residual \(a_t=g_t^y-m_t\), rather than around the full gradient \(g_t^y\). In particular, the leading term \(d\langle a_t,v_t\rangle v_t=dv_tv_t^\top a_t\) is a randomized reconstruction of the residual direction, while the second term is the finite-difference bias caused by using a nonzero smoothing radius \(\delta\).

To analyze the error of the estimator as a gradient estimator, we subtract \(g_t^y=m_t+a_t\) from both sides. This yields \[\widehat g_t-g_t^y = (d v_t v_t^\top-I)a_t + \frac{d}{2\delta}r_t v_t .\] The first term is the sampling fluctuation induced by the random direction \(v_t\), and it is conditionally zero-mean because \(\mathbb{E}[v_t v_t^\top]=I/d\). The second term is the bias term controlled by smoothness. Under \(\beta\)-smoothness, \(|r_t|\le \beta\delta^2\), which yields \[\mathbb{E}\|\widehat g_t-m_t\|^2 \le 2d\|g_t^y-m_t\|^2 + \frac{d^2}{2}\beta^2\delta^2 .\] Thus, when the prediction is accurate, the estimator itself has small second moment. This is the key distinction from the classical two-point estimator, whose second moment scales with the full gradient norm. The role of \(m_t\) is therefore not only to shift the optimistic update, but also to reduce the variance of the bandit gradient estimate.

We now present the main theoretical guarantee for TP-VR-Opt. We first establish a general regret bound that depends on the step size \(\eta\) and the perturbation radius \(\delta\), without tuning for these parameters.

Theorem 4. Suppose the functions \(f_{t}\) are convex, \(L\)-Lipschitz, and \(\beta\)-smooth on \(\mathcal{X}\). If TP-VR-Opt is run with parameters \(\eta, \delta > 0\) and \(\alpha = \delta/r\), then the expected regret is bounded as \[\begin{align} \mathbb{E}[\mathfrak{R}_{T}]&\le\frac{D^{2}}{2\eta}+\eta\left( 4d\,\bar S_{T}+ \left(\frac{d^{2}}{2}+4d\right)\beta^{2}\delta^{2}T \right)+\frac{Dd\beta\delta T}{2}+\left(L+\frac{LD}{r}\right)\delta T. \label{eq:main-exp-bound} \end{align}\tag{3}\]

By optimally tuning the parameters \(\eta\) and \(\delta\) to minimize the bound shown in Theorem 4, we obtain the following adaptive regret guarantee in terms of the expectation of the cumulative prediction error \(\sqrt{\bar{S}_{T}}\).

Theorem 5. Suppose the functions \(f_{t}\) are convex, \(L\)-Lipschitz, and \(\beta\)-smooth on \(\mathcal{X}\). When TP-VR-Opt is run with the oracle-tuned parameters: \[\eta = \frac{D}{\sqrt{8d (\bar{S}_{T}+1)}}, \quad \delta = \min \left\{ \frac{\sqrt{\bar{S}_{T}+1}}{d\beta T}, \frac{1}{\beta\sqrt{T}}, \frac{r}{2}\right\},\] the expected regret is bounded as \(\mathbb{E}[\mathfrak{R}_{T}]=O\big( D \sqrt{d \, \bar S_{T}}\big)\).

The parameter choice in Theorem 5 reflects two separate tradeoffs. The stepsize \(\eta\) balances the usual stability term \(D^2/(2\eta)\) with the residual-variance term \(\eta d\bar S_T\). This is the same stability–variance tradeoff as in optimistic online gradient methods, but with the cumulative prediction error \(\bar S_T\) replacing the horizon-dependent quantity that would arise from a worst-case second-moment bound. The perturbation radius \(\delta\) plays a different role. It controls the price of using a finite difference to approximate local first-order information. In the bound of Theorem 4, the \(\delta\)-dependent terms come from the smoothness bias of the symmetric difference and from the perturbation/shrinkage cost. The choice \(\delta\) ensures that these bias terms are dominated by the leading \(D\sqrt{d\bar S_T}\) term, while also preserving feasibility of the perturbed queries. Thus, after tuning, the regret is driven by the residual variance rather than by the full gradient magnitude or the time horizon.

From Theorem 5, the regret upper bound is determined by the predictive error \(\bar S_{T}\) when the feedback is given by two points, overcoming the barrier of \(\Omega(\sqrt{T})\) in the single-point feedback setting. When the optimistic predictions are good, i.e., when \(\bar S_{T}\) is small (e.g., \(\bar{S}_T=o(T)\)), the performance of the algorithm improves based on the predictions.

4.2 Connection to Gradually Evolving Worlds [27]↩︎

With the same Lipschitz continuity and smoothness assumption, Chiang et al. [27] obtained the regret bound \(\widetilde{O}(d^2\sqrt{D_T})\) in terms of gradient variation \(D_T\) under two-point feedback, where \(D_T=\sum_{t=1}^T \max_{x\in\mathcal{X}}\|\nabla f_t(x)-\nabla f_{t-1}(x)\|^2\) characterizes the gradually evolving worlds. Interestingly, when we specialize our proposed TP-VR-Opt by restricting the sample distribution over \(\mathbb{S}^{d-1}\) to the standard basis vectors, i.e, \(v_t\sim \mathrm{Unif}(\{e_1,\dotsc,e_d\})\) and employing the coordinate-persistent predictor \(m_t\) whose \(i\)-th coordinate stores the most recent finite-difference observation on that coordinate, TP-VR-Opt recovers the results in [27]. In this subsection, we formalize this specialization and highlight how the general framework encompasses the gradually evolving worlds construction as a special case. The variant of TP-VR-Opt can be written shown as the following Algorithm 2. Our notation \(\Delta_{t,i_t}\) in TP-VR-Opt is written as \(\Delta_{t,i_t}=2\delta(\widehat{v}_{t,i_t}-m_{t,i_t})\) for convenience here.

Figure 2: Variant of TP-VR-Opt with coordinate sampling

To recover the result shown in [27], the key idea is that for each coordinate \(i_t\), the finite-difference slope \(\widehat{v}_{t,i_t}\) approximates the true gradient \(\nabla_{i_t} f_t(y_t)\) up to a smoothness-dependent bias of order \(\beta \delta\). By using the variance-reduced estimator \(\widehat{g}_t\) and updating \(m_t\) coordinate-wise, the accumulated estimation error over the trajectory can be controlled in terms of the gradient variation \(D_T = \sum_{t=1}^T \max_{x\in \mathcal{X}}\|\nabla f_t(x)-\nabla f_{t-1}(x)\|^2\). The full technical derivation is deferred to Appendix 9.4.

Corollary 1 (Recovery of Gradually Evolving Worlds [27]). Suppose the functions \(f_{t}\) are convex, \(L\)-Lipschitz, and \(\beta\)-smooth on \(\mathcal{X}\). When Algorithm 2 is run with the oracle-tuned parameters: \[\eta=\min\left\{\frac{D}{4d^2\sqrt{D_T+1}},\frac{1}{16\beta d^{3/2}\sqrt{\log T}}\right\},\qquad \delta=\min\left\{\frac{\sqrt{D_T+1}}{\beta T},\frac{1}{\beta\sqrt{T}},\frac{r}{2}\right\},\] we have \[\mathbb{E}[\mathfrak{R}_{T}]\le\widetilde{O}(Dd^2 \sqrt{D_T}),\] matching the regret bound in [27].

Note that [27] readily provides a scheme to generate hints in the BCO setup, this corollary demonstrates that our general TP-VR-Optframework naturally encompasses the gradually evolving worlds setting as a special case. While the original analysis in [27] explicitly considers the coordinate-persistent predictor and basis-vector sampling, our framework allows arbitrary direction sampling and gradient predictions.

Importantly, the \(d^2\) dependence arises from two sources: (i) the dimension \(d\) itself due to coordinate-wise updates, and (ii) the second-moment scaling in the variance-reduced estimator when tracking the residual along each coordinate. In particular, for each sampled coordinate, the variance contribution is proportional to \(d\), and summing across \(d\) coordinates gives the \(d^2\) factor. For sufficiently smooth losses and bounded gradient variation, the bias terms remain lower order and do not affect the leading-order regret. Recent work [37] demonstrates that this bound can be further tightened by refining the analysis of non-consecutive gradient variations. In this setting, each coordinate is sampled intermittently, so the gradient difference is measured between the current and the most recent observation of the same coordinate. By carefully analyzing the expected maximal interval between consecutive samplings (using a coupon-collector argument) and stabilizing the step-size schedule, the dimension dependence of the regret is further reduced from \(O(d^2 \sqrt{D_T})\) to \(O(d^{3/2} \sqrt{D_T})\) for convex functions, and from \(O(d^2 \log(d D_T)/\lambda)\) to \(O(d \log(D_T)/\lambda)\) for \(\lambda\)-strongly convex functions.

Thus, the corollary highlights both the generality of TP-VR-Optand the compatibility with previously studied special cases. Any alternative sampling scheme or improved gradient prediction immediately extends to gradually evolving worlds, providing a unified perspective on prediction-adaptive bandit convex optimization.

4.3 Parameter Tuning with Unknown Prediction Error and Time Horizon↩︎

The regret bound in Theorem 4 holds for any valid choice of \(\eta\) and \(\delta\). To achieve the desired adaptive regret bound, these parameters need to be tuned according to the complexity of the problem instance, specifically the expected prediction error \(\bar S_{T}\) and time horizon \(T\). By optimally tuning the parameters \(\eta\) and \(\delta\) to minimize the bound in Theorem 4, we obtain the adaptive regret bound shown in Theorem 5.

While Theorem 5 derives a general adaptive bound in terms of \(\bar{S}_T\), one could see that the optimal parameters for \(\eta\) and \(\delta\) cannot be determined without knowledge of \(\bar S_{T}\) and time horizon \(T\). In this subsection, we present an algorithm TP-VR-Opt+ based on a nested doubling-trick approach to adaptively tune the parameters \(\eta\) and \(\delta\) without prior knowledge of \(\bar S_{T}\) and \(T\). Let \(H\) denote the current time budget. We initialize \(H=1\) and double \(H\) whenever the current time step \(t\) exceeds \(H\). Let \(I\) denote the set of rounds within the current time phase with \(|I|\leq H\) and define the phase prediction sensitivity as \(\bar S(I)=\mathbb{E}\left[\sum_{t\in I}\|\nabla f_{t}( x_{t})-m_{t}\|^{2}\right]\). We denote \(S\) as the budget guess for the phase prediction sensitivity, initialized to \(S=1\) and doubled whenever \(\sum_{t\in I}\| \hat{g}_{t}-m_{t}\|^{2}>8dS\). Within each phase, we run TP-VR-Opt with parameters tuned using \(H\) and the local prediction sensitivity guess \(S\). The nontrivial issue here is that the target quantity \(\bar S_T\) is trajectory-dependent and unobserved under bandit feedback. We therefore use the observable residual \(\sum_t\|\widehat g_t-m_t\|^2\) as a proxy for the prediction error and apply a standard doubling scheme to this observable quantity. We summarize the complete procedure in Algorithm 3 and the regret guarantee of TP-VR-Opt+ is presented in the following Theorem.

Theorem 6. Suppose the functions \(f_{t}\) are convex, \(L\)-Lipschitz, and \(\beta\)-smooth on \(\mathcal{X}\). When TP-VR-Opt+ is run as Algorithm 3, the expected regret is bounded as \[\mathbb{E}[\mathfrak{R}_{T}]\le \widetilde{O}\left( D\sqrt{d\,\bar S_{T}}\right).\]

Theorem 6 establishes that TP-VR-Opt+ achieves a regret bound comparable to the oracle bound in Theorem 5, up to logarithmic factors. This result confirms that the benefits of prediction can be realized in an adaptive manner, without requiring prior knowledge of the cumulative prediction error \(\bar S_{T}\) or the time horizon \(T\).

4.4 Lower Bound in Terms of Prediction Error↩︎

In previous subsections, we have first established that the TP-VR-Opt algorithm achieves an adaptive regret bound that scales with the expected cumulative prediction error \(\bar S_{T}\). Then, we also presented a variant TP-VR-Opt+ which does not require prior knowledge of \(\bar S_{T}\) and \(T\) while still achieving a similar adaptive regret rate up to logarithmic factors. In this subsection, we establish an information-theoretic lower bound showing that the \(\sqrt{\bar S_T}\)-dependence in the above upper bounds is unavoidable. Information-theoretic lower bounds are a standard tool for characterizing the oracle complexity of convex optimization [39]; our lower bound is different in that the hardness is parameterized by the irreducible prediction error rather than by the number of oracle queries. Specifically, we show that no algorithm can guarantee regret \(o(D\sqrt{\bar S_{T}})\) even with full-information feedback. Equivalently, for any target prediction error level \(S \in [0, L^{2}T]\), there exist problem instances whose expected cumulative prediction errors satisfy \(\bar S_{T}= S\) while the expected regret is at least \(\Omega(D\sqrt{S})\). As a consequence, the dependence on \(O(D\sqrt{d\bar S_{T}})\) in Theorem 5 is optimal up to a \(\sqrt{d}\) factor.

We begin our analysis by establishing an information-theoretic lower bound via a simple linear function construction. We show that a regret scaling as \(\Omega(D\sqrt{S})\) is unavoidable for any feedback model (whether single-point, two-point feedback, or even full-information). This result highlights the inherent difficulty of the problem with the cumulative prediction errors \(S\). For a distribution \(\mathcal{D}\) over loss sequences, a learning algorithm \(A\), and a prediction policy \(\pi\in\Pi\), define \(\bar S_T^\pi(\mathcal{D},A)= \mathbb{E}_{\mathcal{D},A,\pi} \sum_{t=1}^T\|\nabla f_t(x_t^\pi)-m_t^\pi\|^2\). We further define the intrinsic prediction error as \(\bar S_T^\star(\mathcal{D},A)=\inf_{\pi\in\Pi}\bar S_T^\pi(\mathcal{D},A)\).

Theorem 7. Let \(\mathcal{X}\subset\mathbb{R}^d\) be a convex set with Euclidean diameter \(D\). Fix any horizon \(T\ge1\) and any learning algorithm \(A\) under any feedback model (one-point, two-point, or full-information). Let \(\Pi\) denote the class of all admissible non-anticipating prediction policies, i.e., for every \(\pi = \{m_t^\pi\}_{t=1}^T\in\Pi\), \(m_t^\pi\) is \(\mathcal{H}_{t-1}\)-measurable and \(\|m_t^\pi\|\le L\) for all \(t\in [T]\). Then, for every \(S\in[0,L^2T]\), there exists a distribution \(\mathcal{D}_S\) over sequences of convex, \(L\)-Lipschitz, \(0\)-smooth linear losses \(\{f_t\}_{t=1}^T\) such that \(\bar S_T^\star(\mathcal{D}_S,A)=S\), and for every admissible prediction policy \(\pi\in\Pi\), \[\mathbb{E}_{\mathcal{D}_S,A,\pi}[\mathfrak{R}_T] \ge cD\sqrt S, \label{eqn:lower95bd95S}\tag{4}\] where \(c>0\) is a universal constant.

Then, we specialize our analysis to the two-point feedback setting. Comparing Theorem 7 with Theorem 5, we see that the \(\sqrt{\bar S_T}\) dependence is unavoidable (due to the lower bound \(\Omega(D\sqrt{S})\) in 4 ). Even if the prediction error is interpreted in the strongest possible sense as the irreducible prediction error \(\bar S_T^\star\), no algorithm can improve the dependence below \(D\sqrt{\bar S_T^\star}\) in general. The only remaining gap is the \(\sqrt d\) factor. Theorem 7 does not rule out removing this factor; it only shows that there is no additional lower bound depending solely on \(T\) in the two-point/full-information comparison.

Remark 8 (The \(\sqrt{d}\) Gap). Theorem 7 establishes a universal lower bound on the prediction-error dependence. Even with full-information feedback, no algorithm can improve the \(\sqrt S\) scaling in general. The factor \(\sqrt d\) in Theorem 5 arises from the second-moment analysis of the two-point residual estimator, whose variance scales as \(d\|\nabla f_t(x_t)-m_t\|^2\). Whether this factor is information-theoretically unavoidable for the full class of two-point algorithms is a separate question.

5 Dynamic Regret for TP-VR-Opt↩︎

In this section, we extend our proposed TP-VR-Opt algorithm to the dynamic regret setting. Throughout this section, except considering the non-stationarity of the comparator sequence, we keep the same two-point feedback framework as previously discussed within Section 2 and Section 4.

Dynamic Regret. The performance in the non-stationary environment is measured with respect to a fixed sequence of comparators \(u_{1:T}= (u_{1},\ldots,u_{T}) \in \mathcal{X}^T\) leading to the the dynamic regret being defined as \[\mathfrak{R}^{\mathrm{dyn}}_{T}(u_{1:T})=\sum_{t=1}^{T}\bigl(f_{t}(x_{t})-f_{t}(u_{t})\bigr).\] In order to estimate the level of non-stationarity exhibited by the comparator sequence, the path length of the comparator sequence is defined as \(P_{T}(u_{1:T}) = \sum_{t=2}^{T}\|u_{t}-u_{t-1}\|.\)

We now present our main result for the dynamic regret in a non-stationary environment. The following theorem establishes a dynamic regret bound that depends on both the path-length \(P_{T}\), which measures the fluctuation of the comparator sequence, and the expectation of cumulative prediction error \(\bar {S}_{T}\).

Theorem 9. Assume that each loss function \(f_{t}\) is convex, \(L\)-Lipschitz, and \(\beta\)-smooth on \(\mathcal{X}\). Run TP-VR-Opt with fixed parameters \(\eta>0\) and \(\delta\in(0,r)\). Then, for any comparator sequence \(u_{1:T}\in \mathcal{X}^T\), the expected dynamic regret is bounded by \[\begin{align} &\mathbb{E}\bigl[\mathfrak{R}^{\mathrm{dyn}}_{T}(u_{1:T})\bigr]\le \frac{D^{2}+ 2D P_{T}}{2\eta}+\eta \Bigl( 4d\,\bar{S}_{T}+ (d^{2}/2 + 4d)\beta^{2}\delta^{2}T \Bigr) +\frac{D d \beta \delta T}{2}+ \Bigl( L + \frac{LD}{r}\Bigr) \delta T, \end{align}\] where \(P_{T}= P_{T}(u_{1:T})\) is the path-length. In particular, if \(\bar{S}_{T}\) and \(P_{T}\) are known, choosing \[\eta = \sqrt{\frac{D^{2}+ 2D P_{T}}{8d(\bar{S}_{T}+1)}},\quad \delta = \min\left\{ \frac{\sqrt{\bar{S}_{T}+1}}{d \beta T}, \; \frac{1}{\beta \sqrt{T}}, \; \frac{r}{2}\right\}\] yields the regret bound as \[\mathbb{E}\bigl[\mathfrak{R}^{\mathrm{dyn}}_{T}(u_{1:T})\bigr] =O\Bigl( \sqrt{d\,\bar{S}_{T}(D^{2}+ D P_{T})}\Bigr).\]

Theorem 9 demonstrates that TP-VR-Opt achieves a dynamic regret that scales with the path-length \(P_{T}\) and the prediction error \(\bar{S}_{T}\) as \(O\big(\sqrt{ d\bar{S}_T (1+P_T)}\big)\). However, similar to the static regret result shown in Theorem 5, the dynamic regret bound in Theorem 9 relies on prior knowledge of the path-length \(P_{T}\) to tune the step size \(\eta\).

To achieve the optimal dynamic regret rate without prior knowledge of the path-length \(P_{T}\), we introduce the TP-VR-Opt++ algorithm. This algorithm builds on the adaptive framework of TP-VR-Opt+ (Algorithm 3) by inheriting its nested phase-epoch structure along with the doubling schedule for the sensitivity budget \(S\) and time horizon \(H\). However, to effectively handle unknown non-stationarity, TP-VR-Opt++ replaces the fixed-step update within each epoch with a Meta-Expert subroutine. The learning model maintains a geometric grid of expert examples and combines their predictions using an optimistic Hedge meta-algorithm. The oracle choice of \(\eta\) in Theorem 9 depends on the unknown path-length \(P_T\). A single fixed stepsize cannot be simultaneously optimal for all levels of comparator variation: small \(P_T\) requires a more aggressive stepsize, while large \(P_T\) requires a more conservative one. TP-VR-OPT++ addresses this issue by maintaining a geometric grid of candidate stepsizes and aggregating the corresponding experts.

Importantly, the meta layer is used only to adapt to the unknown dynamic scale. Each expert still uses the same prediction-centered two-point estimator, and therefore retains the residual-variance control in terms of \(\bar S_T\). The optimistic meta-update uses the predicted linear losses induced by \(m_t\) before observing feedback and then updates the weights using the estimated losses induced by \(\widehat g_t\). This preserves the prediction-adaptive nature of the bound that the price of aggregation is logarithmic, rather than introducing a new \(\sqrt{T}\)-type term. Therefore, the learning model automatically adapts to the optimal step size \(\eta^{\star}\) with regard to local path-length using this technique. The specifics of the meta-expert approach are presented in Algorithm 4.

We note that, in contrast to the parameter-free Bandit Gradient Descent algorithm proposed in [13], our approach employs an optimistic meta-algorithm, which ensures that the meta-regret depends on \(\bar S_T\) rather than relying on the standard Hedge-based aggregation used in [13]. Moreover, each expert in our framework is instantiated with our proposed TP-VR-Opt+ algorithm, rather than the classical Bandit Gradient Descent procedure.

Theorem 10. Assume that the loss functions \(f_{t}\) are convex, \(L\)-Lipschitz, and \(\beta\)-smooth on the convex set \(\mathcal{X}\) with diameter \(D\). Running TP-VR-Opt++ guarantees that for any comparator sequence \(u_{1:T}\in \mathcal{X}^T\) of path-length \(P_{T} = \sum_{t=2}^{T} \|u_{t} - u_{t-1}\|\), the expected dynamic regret is bounded as: \[\mathbb{E}\bigl[\mathfrak{R}_{T}^{\mathrm{dyn}}(u_{1:T})\bigr] \le\widetilde{O} \left( \sqrt{d \bar{S}_{T} (D^{2} + D P_{T})}\right).\]

Theorem 10 highlights the adaptivity of TP-VR-Opt++. The algorithm provides a dynamic regret bound of the form \(\widetilde{O}(\sqrt{d \bar{S}_{T} (1+P_{T})})\) without requiring prior knowledge of the path-length \(P_{T}\). The result matches the optimally adjusted \(P_T\) of Theorem 9 for dynamic regret to within logarithmic terms, thereby resolving the problem caused by the non-stationarity.

6 Conclusion and Future Work↩︎

Our work studies the bandit convex optimization problem with gradient prediction adaptivity, moving beyond worst-case regret guarantees to achieve improved performance. By establishing the fundamental limitations of single-point feedback, we design TP-VR-Opt to overcome these barriers. We further extend our analysis to non-stationary environments via dynamic regret and develop fully adaptive variants that require less prior knowledge.

There are several avenues for future research. First, our lower bound in Theorem 3 shows that under single-point feedback, the regret is fundamentally lower bounded by \(\Omega( \sqrt{T})\) even when the cumulative prediction error is negligible. However, this barrier does not preclude a partial benefit from predictions. Since the worst-case regret for smooth convex losses under single-point feedback is \(O(T^{2/3})\), which already improves upon the \(O(T^{3/4})\) rate for Lipschitz losses, a natural question is whether predictions can further interpolate between this rate and the \(\Omega(\sqrt{T})\) floor. That is, whether there exist algorithms achieving \(\widetilde{O}(\min\{\sqrt{T},\, \bar{S}_T^a T^b\})\) with \(a + b = 2/3\). The main difficulty is that the competing terms \(\delta T + T/\delta^2\) in the single-point bias–variance tradeoff cannot be reduced by the prediction \(m_t\), since the absolute function value observation mixes the local first-order signal with zero-order offsets. Another promising direction is to extend this work to the strongly convex setting.

7 Proposition 11 ↩︎

Proposition 11. Let \(L>0\) and \(\delta\in(0,1)\). There exists a convex, \(L\)-Lipschitz function \(f:[-1,1]\to\mathbb{R}\) such that, for \(y=0\) and direction \(v=1\), the symmetric difference remainder defined as \[r(v)= f(y+\delta v)-f(y-\delta v)-2\delta \langle \nabla f(y),v\rangle\] satisfies \[|r(v)|=\frac{2}{3}L\delta.\] In other words, the normalized difference between the secant slope and the point gradient is constant: \[\left|\frac{f(\delta)-f(-\delta)}{2\delta}-f'(0)\right|=\frac{L}{3}.\]

Proof. Let \(g:[-1,1]\to\mathbb{R}\) with \[g(x)= \begin{cases} -L, & x\in[-1,-\delta],\\[1mm] \frac{L}{3}+\frac{4L}{3}\frac{x}{\delta}, & x\in[-\delta,0],\\[2mm] \frac{L}{3}, & x\in[0,1]. \end{cases}\] Then \(g\) is continuous, nondecreasing, and satisfies that for all \(x\) it holds that \(|g(x)|\le L\). Let \[f(x)=\int_{-\delta}^{x} g(s)\,ds.\] Since \(f\in C^1([-1,1])\) and \(g(x)=f'(x)\) is nondecreasing, \(f\) is convex. Additionally, since \(|f'(x)|\le L\), the function \(f\) is \(L\)-Lipschitz.

We have \(f(-\delta)=0\) and \(f'(0)=g(0)=L/3\). Also, \[f(\delta)-f(-\delta)=\int_{-\delta}^{\delta} g(s)\,ds =\int_{-\delta}^{0}\Big(\frac{L}{3}+\frac{4L}{3}\frac{s}{\delta}\Big)\,ds +\int_{0}^{\delta}\frac{L}{3}\,ds.\] It follows that \(f(\delta)=f(-\delta)\) which implies that \[r(1)=f(\delta)-f(-\delta)-2\delta f'(0)=0-2\delta\cdot \frac{L}{3}=-\frac{2}{3}L\delta.\] Thus, we have \(|r(1)|=\frac{2}{3}L\delta\) and \(\Big|\frac{f(\delta)-f(-\delta)}{2\delta}-f'(0)\Big|=\frac{L}{3}\). ◻

8 Omitted Details of Section 3 ↩︎

8.1 Useful definitions and notations↩︎

Definition 1 (Total Variation Distance). Given two probability distributions \(P\) and \(Q\) on the measurable space \((\Omega,\mathcal{F})\), the total variation distance (denoted by \(\mathrm{TV}(P,Q)\)) can be computed as follows: \[\mathrm{TV}(P, Q) = \sup_{A \in \mathcal{F}} |P(A) - Q(A)|.\] In the case where the distributions \(P\) and \(Q\) can be described by their density functions \(p\) and \(q\) with respect to a base measure \(\mu\), then we can express \(\mathrm{TV}(P,Q)\) as \[\mathrm{TV}(P, Q) = \frac{1}{2} \int |p(x) - q(x)| \, d\mu(x).\]

Definition 2 (Kullback-Leibler Divergence). Given two probability distributions \(P\) and \(Q\), the Kullback-Leibler (KL) divergence between these distributions can be calculated as follows: \[\mathrm{KL}(P \| Q) = \int \log\left(\frac{dP}{dQ}\right) dP.\]

Pinsker’s Inequality is used to provide a standard upper bound for the total variation distance in terms of the Kullback-Leibler Divergence.

Lemma 1 (Pinsker’s Inequality). Consider two probability distributions \(P\) and \(Q\), the following inequality holds: \[\mathrm{TV}(P, Q) \le \sqrt{\frac{1}{2} \mathrm{KL}(P \| Q)}.\]

In the following, we will provide a corollary about the Kullback-Leibler divergence between two Gaussian distributions. This will be useful for proving Theorem 3.

Corollary 2 (KL Divergence for Gaussians). Suppose that the two Gaussian distributions \(\mathcal{N}(\mu_1,\Sigma)\) and \(\mathcal{N}(\mu_2,\Sigma)\) have the same covariance matrix (i.e., \(\Sigma\)). Then, we have: \[\mathrm{KL}(\mathcal{N}(\mu_1, \Sigma) \| \mathcal{N}(\mu_2, \Sigma)) = \frac{1}{2} (\mu_1 - \mu_2)^\top \Sigma^{-1} (\mu_1 - \mu_2).\] In the case of univariate Gaussians with common variance \(\sigma^2\), this reduces to \(\frac{(\mu_1 - \mu_2)^2}{2\sigma^2}\).

8.2 Proof of Theorem 3 ↩︎

Let \(x_{+}\) and \(x_{-}\) be two points satisfying \(\|x_{+}-x_{-}\|=D\) in \(\mathcal{X}\), where the Euclidean diameter of \(\mathcal{X}\) is \(D\). Then define the direction vector \(v=(x_{+}-x_{-})/D\) and the midpoint \(x_0=\frac{x_{+}+x_{-}}{2}\). Thus, for all \(x\in \mathcal{X}\), we see that \[|\left\langle v, x-x_0 \right\rangle| \leq \frac{D}{2}.\]

Let \(M\) be a uniform Rademacher variable taking values in \(\{+1,-1\}\). Assume that the Gaussian noise sequence \(\{\xi_t\}_{t=1}^T\) are i.i.d (independent and identically distributed) Gaussian \(\mathcal{N}(0,\sigma^2)\). Define \(\varepsilon=\frac{\sigma}{2D\sqrt{T}}\). The assumption \(\sigma \leq 2LD\sqrt{T}\) implies \(\varepsilon \leq L\). Fix \(t\in[T]\), then conditioned on the event that we observe \(M=m\), we can consider the loss function as \[f_t^{(m)}(x)=-m\,\varepsilon\langle v,x-x_0\rangle+\xi_t .\] The loss function \(f_t\) has \(L\)-Lipschitz continuity since \(\|\nabla f_t^{(m)}(x)\|=\varepsilon \le L\) and is \(0\)-smooth (hence satisfies \(\beta\)-smoothness properties) since \(\nabla^{2}f_t^{(m)}(x)=0\).

Let \(P_+\) and \(P_-\) be the distributions over the sequence of observations in the worlds \(M=+1\) and \(M=-1\), respectively. Conditioned on the history \(\mathcal{H}_{t-1}\), the observation \(Y_t = f_t^{(M)}(x_t)\) is distributed as: \[Y_t \mid \mathcal{H}_{t-1} \sim \mathcal{N}(-m\varepsilon z_t, \sigma^2), \quad \text{where } z_t= \langle v, x_t - x_0 \rangle.\]

Utilizing Corollary 2, the conditional term at step \(t\) is computed as follows: \[\begin{align} \mathrm{KL}( \mathcal{N}(-\varepsilon z_t,\sigma^2) \| \mathcal{N}(+\varepsilon z_t,\sigma^2)) = \frac{((- \varepsilon z_t ) - (+ \varepsilon z_t ))^2}{2 \sigma^2} = \frac{(-2 \varepsilon z_t )^2}{2 \sigma^2} = \frac{2 \varepsilon^2 z_t^2}{\sigma^2}. \end{align}\] Substituting this Gaussian KL divergence back into the chain rule decomposition gives \[\mathrm{KL}(P_+ \| P_-) =\sum_{t=1}^T \mathbb{E}_{P_+}\left[ \mathrm{KL}(P_+(Y_t \;| \;\mathcal{H}_{t-1})\| P_-(Y_t \;| \;\mathcal{H}_{t-1})) \right] = \sum_{t=1}^T \mathbb{E}_{P_+}\left[ \frac{2 \varepsilon^2 z_t^2}{\sigma^2} \right] .\] Then, we rewrite this expression as follows: \[\mathrm{KL}(P_+ \| P_-) =\mathbb{E}_{P_+}\left[ \sum_{t=1}^T \frac{2 \varepsilon^2 z_t^2}{\sigma^2} \right].\] From the definition of \(|z_t| \leq \frac{D}{2}\), \[\mathrm{KL}(P_+ \| P_-) \leq \frac{2 \varepsilon^2}{\sigma^2} \cdot \frac{D^2}{4} \cdot T=\frac{\varepsilon^2 D^2 T}{2\sigma^2}.\] Substituting back in \(\varepsilon = \frac{\sigma}{2D\sqrt{T}}\), we get \(\mathrm{KL}(P_+ \| P_-) \leq \frac{1}{8}\), thus by Pinsker’s inequality shown in Lemma 1 then \[\label{eq:pinsker} \mathrm{TV}(P_+,P_-)\leq \sqrt{ \frac{1}{2} \mathrm{KL}(P_+ \|P_-)}\leq \sqrt{ \frac{1}{16}} =\frac{1}{4} .\tag{5}\]

Static regret is defined by measuring against the best possible decision made in hindsight, i.e., the decision that minimizes cumulative losses, \[x^{(m)} \in \text{argmin}_{x\in \mathcal{X}} \sum_{t=1}^{T} f_t^{(m)}(x) ,\] and since \[\sum_{t=1}^T f_t^{(m)}(x) = \sum_{t=1}^T \Big[ -m\varepsilon \langle v,x-x_0 \rangle + \xi_t \Big] = -m\varepsilon T\langle v,x-x_0 \rangle + \sum_{t=1}^T \xi_t,\] the term \(\sum_{t=1}^T \xi_t\) is unaffected by changing \(x\); hence the minimization of cumulative losses through the term \(\sum_{t=1}^T f_t^{(m)}(x)\) results in maximizing the projection in the direction of \(mv\), therefore the points \(x_m^* = x_0 +m \cdot \frac{D}{2} v\) represent a maximum.

Returning to our previous definition of regret, \[\begin{align} \mathfrak{R}_T^{(m)} &= \sum_{t=1}^T \Big[ -m\varepsilon z_t + \xi_t \Big] - \left(-m\varepsilon T\langle v,x_m^*-x_0\rangle + \sum_{t=1}^T\xi_t\right) \\ &= -m\varepsilon \sum_{t=1}^T z_t + m\varepsilon T \langle v ,x_m^* - x_0\rangle \\ &= -m\varepsilon Z + m\varepsilon T\cdot \Big(m\frac{D}{2}\Big) \\&= \frac{\varepsilon DT}{2} - m\varepsilon Z , \end{align}\] where \(Z = \sum_{t=1}^{T}z_t , z_t = \langle v,x_t - x_0\rangle\). Also note since \(|z_t| \leq \frac{D}{2} , |Z| \leq \frac{DT}{2}\).

Thus, we have found that the average regret over \(M\) is given by the following equation for the average regret: \[\mathbb{E}[\mathfrak{R}_T] = \frac{1}{2} \mathbb{E}_{P_+}\left[\mathfrak{R}_T^{(+)}\right] + \frac{1}{2} \mathbb{E}_{P_-}\left[\mathfrak{R}_T^{(-)}\right] = \frac{\varepsilon D T}{2} - \varepsilon \underbrace{\frac{1}{2}\left( \mathbb{E}_{P_+}[Z] - \mathbb{E}_{P_-}[Z]\right)}_{\mathbb{E}[M Z]}.\]

Let \(Z\) be a random variable with values in \([-K,K]\), then for \(|Z|\leq K\), \(|\mathbb{E}_{P_+}[Z]-\mathbb{E}_{P_-}\left[Z\right]|\leq 2K\cdot\mathrm{TV}(P_+,P_-)\). Since \(Z\) has a maximum absolute value of \(\frac{DT}{2}\), we put \(K=\frac{DT}{2}\). By applying the inequality \(\mathrm{TV}(P_+,P_-) \leq \frac{1}{4}\) from 5 gives: \[\left|\mathbb{E}_{P_+}[Z]-\mathbb{E}_{P_-}\left[Z\right]\right| \leq 2\cdot\left(\frac{DT}{2}\right)\cdot \frac{1}{4} = \frac{DT}{4}.\] Plugging this result into our previous equation, we find, \[\mathbb{E}[\mathfrak{R}_T] \ge \frac{\varepsilon D T}{2} - \varepsilon\left(\frac{1}{2}\cdot\frac{DT}{4}\right) = \frac{3}{8}\varepsilon D T.\] Substituting \(\varepsilon = \frac{\sigma}{2D\sqrt{T}}\) results in: \[\mathbb{E}[\mathfrak{R}_T] \geq \frac{3}{8}D T\cdot\left(\frac{\sigma}{2D\sqrt{T}}\right) = \frac{3}{16}\sigma\sqrt{T}.\]

9 Omitted Details of Section 4 ↩︎

9.1 Useful Lemmas in Section 4.1 ↩︎

Lemma 2 (Difference Approximation Error). Assume that \(f_{t}\) is \(\beta\)-smooth. For any point \(y_{t}\), direction \(v_{t}\in \mathbb{S}^{d-1}\) and perturbation radius \(\delta > 0\), the remainder in the difference approximation between points is defined as: \[r_{t}= f_{t}(y_{t}+ \delta v_{t}) - f_{t}(y_{t}- \delta v_{t}) - 2\delta \langle \nabla f_{t}(y_{t}), v_{t}\rangle.\] Then, the magnitude of this remainder is bounded by: \[|r_{t}| \le \beta \delta^{2}.\]

Proof. Let \(\phi(s)=f_t(y_t+sv_t)\). The difference in values of the functions along the direction of the unit vector \(v_{t}\) expressed as an integral of the directional derivative is: \[f_{t}(y_{t}+ \delta v_{t}) - f_{t}(y_{t}- \delta v_{t}) = \phi(\delta) - \phi(-\delta) = \int_{-\delta}^{\delta}\phi'(s) ds = \int_{-\delta}^{\delta} \langle \nabla f_{t}(y_{t}+ s v_{t}), v_{t}\rangle ds.\] The \(2\delta \langle \nabla f_{t}(y_{t}), v_{t}\rangle\) term can similarly be expressed as: \[2\delta \langle \nabla f_{t}(y_{t}), v_{t}\rangle = \int_{-\delta}^{\delta} \langle \nabla f_{t}(y_{t}), v_{t}\rangle ds.\] The above equations give us: \[r_{t}= \int_{-\delta}^{\delta}\left\langle \nabla f_{t}(y_{t}+ s v_{t}) - \nabla f_{t}(y_{t}), v_{t}\right\rangle ds.\] Applying the Cauchy-Schwarz inequality gives: \[\begin{align} |r_{t}| & \le \int_{-\delta}^{\delta}\left| \left\langle \nabla f_{t}(y_{t}+ s v_{t}) - \nabla f_{t}(y_{t}), v_{t}\right\rangle \right| ds \\ & \le \int_{-\delta}^{\delta}\left\| \nabla f_{t}(y_{t}+ s v_{t}) - \nabla f_{t}(y_{t}) \right\| \|v_{t}\| ds. \end{align}\] Because \(\|\nabla f_{t}(y_{t}+ sv_{t}) - \nabla f_{t}(y_{t})\| \le \beta \| y_{t}+ sv_{t} - y_{t}\| = \beta|s|\) for the \(\beta\)-smoothness of \(f_{t}\), and \(\|v_{t}\|=1\), we have: \[|r_{t}| \le \int_{-\delta}^{\delta}\beta |s| ds = 2\beta \int_{0}^{\delta} s ds = \beta \delta^{2}.\] This proves the lemma. ◻

Lemma 3 (Gradient Difference Between Query and Center Points). Denote \(g_t^x=\nabla f_t(x_t)\) and \(g_t^y=\nabla f_t(y_t)\). Assume \(f_{t}\) is \(\beta\)-smooth on \(\mathcal{X}\). Then the difference between gradients sampled at the query point \(x_{t}=y_{t}+\delta v_{t}\) and the center point \(y_{t}\) is proportionally smaller than \(\beta\delta\). In particular, we have bounds: \[\begin{align} \|g_{t}^{y}- m_{t}\|^{2} & \le 2\|g_{t}^{x}- m_{t}\|^{2}+ 2\beta^{2}\delta^{2}, \\ \|g_{t}^{x}- m_{t}\|^{2} & \le 2\|g_{t}^{y}- m_{t}\|^{2}+ 2\beta^{2}\delta^{2}. \end{align}\]

Proof. First, since \(f_{t}\) is \(\beta\)-smooth and \(\|x_{t}- y_{t}\| = \|\delta v_{t}\| = \delta\), we have: \[\|g_{t}^{x}- g_{t}^{y}\| = \|\nabla f_{t}(x_{t}) - \nabla f_{t}(y_{t})\| \le \beta\|x_{t}- y_{t}\| = \beta\delta.\] Then, by applying the inequality \(\|a+b\|^{2}\le 2\|a\|^{2}+ 2\|b\|^{2}\) on the error term, we can write the following: \[\begin{align} \|g_{t}^{y}- m_{t}\|^{2} & = \|(g_{t}^{y}- g_{t}^{x}) + (g_{t}^{x}- m_{t})\|^{2} \\ & \le 2\|g_{t}^{y}- g_{t}^{x}\|^{2}+ 2\|g_{t}^{x}- m_{t}\|^{2} \\ & \le 2\beta^{2}\delta^{2}+ 2\|g_{t}^{x}- m_{t}\|^{2}. \end{align}\] The bound on \(\|g_{t}^{x}- m_{t}\|^{2}\) follows symmetrically. ◻

9.1.0.1 Estimator Decomposition.

In the analysis of the variance-reduced estimator, we consider its error as consisting of two parts: a zero-mean term and a bias term. The prediction error at the center point is denoted as \(a_{t}= g_{t}^{y}- m_{t}\). Using the definitions of \(\hat{g}_{t}\) and \(r_{t}\) set forth in Lemma 2 above, we have: \[\hat{g}_{t}=m_{t}+ \frac{d}{2\delta}\left( 2\delta \langle a_{t}, v_{t}\rangle + r_{t}\right) v_{t}=m_{t}+ d\langle a_{t},v_{t}\rangle v_{t}+ \frac{d}{2\delta} r_{t}v_{t}. \label{eq:estimator-expanded}\tag{6}\] By simply rearranging, we have: \[\hat{g}_{t}- g_{t}^{y}= \underbrace{(d v_tv_t^\top - I)a_t}_{= Z_t \text{ (Zero-mean Term)}}+ \underbrace{\frac{d}{2\delta}r_t v_t}_{= B_t \text{ (Bias)}}. \label{eq:ZB}\tag{7}\] Here, we denote two terms as \(Z_{t} = (dv_{t}v_{t}^{\top}-I)a_{t}\) and \(B_{t}=\frac{d}{2\delta}r_{t}v_{t}\), respectively.

Lemma 4 (Covariance of Uniform Sphere Sampling). Let \(v_{t}\) be sampled uniformly from the unit sphere \(\mathbb{S}^{d-1}\). Then \(\mathbb{E}[v_{t}v_{t}^{\top}] = \frac{1}{d}I_{d}\).

Proof. Let \(A= \mathbb{E}[v_{t}v_{t}^{\top}]\) with entries \(A_{ij}=\mathbb{E}[v_{t,i}v_{t,j}]\). Since the uniform distribution on \(\mathbb{S}^{d-1}\) is invariant to any orthogonal transformation applied to it, then for any distinct indices \(i,j\), the transformation that maps \(v_{t,j}\) to \(-v_{t,j}\) while keeping the remaining coordinates fixed produces the same distribution of \(v_{t}\). Consequently, \[\mathbb{E}[v_{t,i}v_{t,j}] = \mathbb{E}[v_{t,i}(-v_{t,j})] = -\mathbb{E}[v_{t,i}v_{t,j}],\] this implies all off-diagonal entries of \(A_{ij}\) are zero.

For the diagonal entries of \(A\), the symmetry implies that the marginal distribution for each coordinate individually is the same, and therefore for all \(i,j\), we have \[\mathbb{E}[v_{t,i}^{2}] = \mathbb{E}[v_{t,j}^{2}].\] Let \(c\) denote this value, then since \(v_{t}\) lies on the surface of a unit sphere, we have with probability \(1\) that; \[1 = \mathbb{E}\left[\sum_{i=1}^{d}v_{t,i}^{2}\right] = \sum_{i=1}^{d}\mathbb{E} [v_{t,i}^{2}] = \sum_{i=1}^{d}c = d \cdot c.\] Hence, we can conclude that \(c=1/d\). Therefore, \(A\) becomes the diagonal matrix \(A = \frac{1}{d}I_{d}\). ◻

Lemma 5 (Bias Analysis). Assume \(f_{t}\) is \(\beta\)-smooth. Conditioned on the history \(\mathcal{H}_{t-1}\), \(Z_{t}=(d v_tv_t^\top - I)a_t\) is zero-mean \(\mathbb{E}[Z_{t}\mid \mathcal{H}_{t-1}] = 0\), and the bias term \(B_{t}=\frac{d}{2\delta}r_t v_t\) is bounded as: \[\|b_{t}\| \le \frac{d}{2} \beta\delta, \quad \text{where }b_{t}= \mathbb{E}[B_{t}\mid \mathcal{H}_{t-1} ].\] Hence, the expectation of estimated gradient conditioned on the history is: \[\mathbb{E}[\hat{g}_{t}\mid \mathcal{H}_{t-1}] = g_{t}^{y}+ b_{t}.\]

Proof. Since \(v_{t}\) is sampled uniformly from \(\mathbb{S}^{d-1}\) independently of \(\mathcal{H} _{t-1}\), we have the identity \(\mathbb{E}[v_{t}v_{t}^{\top}] = \frac{1}{d}I_{d}\) from Lemma 4. For the term \(Z_{t}\): \[\mathbb{E}[Z_{t}\mid \mathcal{H}_{t-1}]= \big(d\mathbb{E}[v_{t}v_{t}^{\top} ]-I_{d}\big)a_{t}= 0.\] For the bias term \(b_{t}\), we have \(|r_{t}|\le \beta\delta^{2}\) from Lemma 2 and the fact that \(\|v_{t}\|=1\): \[\|b_{t}\|\le\mathbb{E}\big[\|B_{t}\|\mid \mathcal{H}_{t-1}\big]= \mathbb{E} \left[ \frac{d}{2\delta}|r_{t}| \|v_{t}\| \;\Big|\;\mathcal{H}_{t-1}\right]\le \frac{d}{2\delta}\cdot \beta\delta^{2}=\frac{d}{2}\beta\delta.\] Also, we have: \[\mathbb{E}[\hat{g}_{t}\mid \mathcal{H}_{t-1}] = g_{t}^{y}+ b_{t}.\] ◻

Lemma 6 (Second Moment Bound). Assume \(f_{t}\) is \(\beta\)-smooth. Then the second moment of the estimator error around the prediction \(m_{t}\) is bounded by: \[\mathbb{E}\left[\|\hat{g}_{t}-m_{t}\|^{2}\mid \mathcal{H}_{t-1}\right]\le 2d\|g_{t}^{y}-m_{t}\|^{2}+ \frac{d^{2}}{2}\beta^{2}\delta^{2}.\]

Proof. From 6 , we can expand on the definition of the estimator as follows: \[\hat{g}_{t}- m_{t}\;=\; \left( d\langle a_{t}, v_{t}\rangle + \frac{d}{2\delta} r_{t}\right) v_{t}.\] Taking the squared norm and \(\|v_{t}\|=1\), we get the following: \[\|\hat{g}_{t}- m_{t}\|^{2}\;=\; \left( d\langle a_{t}, v_{t}\rangle + \frac{d}{2\delta} r_{t}\right)^{2}.\] By the fact that \((x+y)^{2}\le 2x^{2}+ 2y^{2}\), the right-hand side of the above equation is written as: \[\|\hat{g}_{t}- m_{t}\|^{2}\le 2d^{2}\langle a_{t}, v_{t}\rangle^{2}\;+\; 2 \left(\frac{d}{2\delta}\right)^{2}r_{t}^{2}.\] Since \(\mathbb{E}[\langle a_{t}, v_{t}\rangle^{2}] = \frac{1}{d}\|a_{t}\|^{2}\) and \(r_{t}^{2}\le \beta^{2}\delta^{4}\) from \(|r_{t}| \le \beta\delta^{2}\). Hence, we have \[\begin{align} \mathbb{E}\left[\|\hat{g}_{t}-m_{t}\|^{2}\mid \mathcal{H}_{t-1}\right] & \;\le\; 2d^{2}\left( \frac{\|a_{t}\|^{2}}{d}\right) \;+\; \frac{d^{2}}{2\delta^{2}}(\beta^{2}\delta^{4}) \\ & \;=\; 2d\|a_{t}\|^{2}\;+\; \frac{d^{2}}{2}\beta^{2}\delta^{2}. \end{align}\] By substituting \(a_{t}= g_{t}^{y}- m_{t}\), we complete this proof. ◻

Corollary 3 (Second Moment Bound with Gradient at \(x_{t}\)). Under the assumptions of Lemma 6, \[\mathbb{E}\left[\|\hat{g}_{t}-m_{t}\|^{2}\middle| \mathcal{H}_{t-1}\right ] \le 4d\,\mathbb{E}\left[\|g_{t}^{x}-m_{t}\|^{2}\;\middle|\; \mathcal{H} _{t-1}\right] + (d^{2}/2+4d)\beta^{2}\delta^{2}.\] And in particular, \[\sum_{t=1}^{T}\mathbb{E}\left[\|\hat{g}_{t}-m_{t}\|^{2}\right]\le 4d\bar S _{T}+ (d^{2}/2+4d)\beta^{2}\delta^{2}T.\]

Proof. We know that from Lemma 3, we have: \[\|g_{t}^{y}-m_{t}\|^{2}\le 2\|g_{t}^{x}-m_{t}\|^{2}+ 2\beta^{2}\delta^{2}.\] Taking the conditional expectation and substituting this into Lemma 6, we get: \[\begin{align} \mathbb{E}\left[\|\hat{g}_{t}-m_{t}\|^{2}\;\middle| \mathcal{H}_{t-1}\right] & \le 2d\left( 2\mathbb{E}\left[\|g_{t}^{x}-m_{t}\|^{2}\;\middle| \mathcal{H}_{t-1}\right] + 2\beta^{2}\delta^{2}\right) + \frac{d^{2}}{2}\beta^{2}\delta^{2} \\ & = 4d\,\mathbb{E}\left[\|g_{t}^{x}-m_{t}\|^{2}\;\middle| \mathcal{H}_{t-1}\right] + (d^{2}/2+4d)\beta^{2}\delta^{2}. \end{align}\] To get the total over the time horizon \(T\), we take two iterated expectations over the history \(\mathcal{H}_{t-1}\) on both sides by applying the law of total expectation. We have: \(\mathbb{E}[\mathbb{E}[\cdot|\mathcal{H}_{t-1}]] = \mathbb{E}[\cdot]\): \[\mathbb{E}\left[\|\hat{g}_{t}-m_{t}\|^{2}\right]\le 4d\,\mathbb{E}\left[\| g_{t}^{x}-m_{t}\|^{2}\right] + (d^{2}/2+4d)\beta^{2}\delta^{2}.\] Finally, adding this inequality up for all \(t=1,\dots,T\) gives us the final conclusion. ◻

Lemma 7 (Regret Decomposition for TP-VR-Opt). Assume that \(0 \in \mathcal{X}\) and each function \(f_{t}\) is convex and \(L\)-Lipschitz. Let \(x^{\star}\in \arg\min_{x\in \mathcal{X}}\sum_{t=1}^{T}f_{t}(x)\) denote the optimal comparator in the original set, and let \(y^{\star}= (1-\alpha)x^{\star}\) be its projection onto the set \(\mathcal{X}_{\alpha}\). Then, the regret of TP-VR-Opt is bounded by: \[\mathfrak{R}_{T}\le \sum_{t=1}^{T}\big(f_{t}(y_{t})-f_{t}(y^{\star})\big)+\left(L+\frac{LD}{r}\right)\delta T. \label{eq:regret-reduce}\tag{8}\]

Proof. By definition, we can write the regret of a player at time \(t\) as the sum of three terms: the perturbation cost, the regret relative to the shrunken comparator, and the approximation error of the comparator. \[f_{t}(x_{t}) - f_{t}(x^{\star})= \underbrace{\big(f_t(x_t) - f_t(y_t)\big)} _{\text{Term (A)}}+ \big(f_{t}(y_{t}) - f_{t}(y^{\star})\big)+ \underbrace{\big(f_t(y^\star) - f_t(x^\star)\big)}_{\text{Term (B)}}.\] For term (A), since \(\|x_{t}- y_{t}\| = \delta\), we have: \[f_{t}(x_{t}) - f_{t}(y_{t})\le L\|x_{t}- y_{t}\| = L\delta.\] For term (B), since \(y^{\star}= (1-\alpha)x^{\star}\) and \(0 \in \mathcal{X}\), we have \(\|y^{\star}- x^{\star}\| = \alpha \|x^{\star}\| \le \alpha D\). Then, due to \(\alpha = \delta/r\), we obtain: \[f_{t}(y^{\star}) - f_{t}(x^{\star}) \;\le\; L\|y^{\star}- x^{\star}\| \; \le\; L\alpha D \;=\; \frac{LD}{r}\delta.\] Combining the above for \(t=1,\dots,T\) gives us all terms on the right-hand side of 8 . ◻

Lemma 8 (Optimistic projected-gradient inequality). Given that any closed convex set \(C\subset\mathbb{R}^{d}\) is defined, \(\Pi_{C}\) is the projection onto set \(C\) and \(\eta\;>\;0\) is fixed constant. Let two update sequences be determined as follows for each value of \(t\): \[y_{t}= \Pi_{C}(y'_{t}-\eta m_{t}), \qquad y'_{t+1}= \Pi_{C}(y'_{t}-\eta \hat{g}_{t}).\] Assume that \(y'_{t}\in C\). For any fixed comparator \(y^{\star}\in C\) and an arbitrary horizon \(T\ge 1\), we get the following inequality: \[\sum_{t=1}^{T}\langle \hat{g}_{t}, y_{t}-y^{\star}\rangle \le \frac{\|y^{\star}-y'_{1}\|^{2}}{2\eta} + \eta\sum_{t=1}^{T}\|\hat{g}_{t}-m_{t}\|^{2}. \label{eq:optimistic-ogd}\tag{9}\]

Proof. Let \(x^{+}= \Pi_{C}(x-\eta g)\). By using the first-order conditions of optimality, for all \(z\in C\): \[\langle (x - \eta g) - x^{+}, z - x^{+}\rangle \le 0.\] The above inequality leads to: \[\eta \langle g, x^{+}- z \rangle \le \langle x - x^{+}, x^{+}- z \rangle.\] We can rewrite the inner product on the right-hand side as: \(2\langle a, b\rangle = \|a+b\|^{2}- \|a\|^{2}- \|b\|^{2}\), where \(a = x - x^{+}\) and \(b = x^{+}- z\). Therefore, \(a+b = x-z\), and we have: \[\langle x - x^{+}, x^{+}- z \rangle = \frac{1}{2}\left( \|x - z\|^{2}- \| x - x^{+}\|^{2}- \|x^{+}- z\|^{2}\right).\] By combining the two inequalities above, we obtain the following bound: \[\langle g, x^{+}-z\rangle \le \frac{\|z-x\|^{2}- \|z-x^{+}\|^{2}- \|x^{+}-x\|^{2}}{2\eta}. \label{eq:proj-step-ineq}\tag{10}\]

We apply 10 twice at each round \(t\). Applying 10 with \((x, g, x^{+}, z) = (y'_{t}, m_{t}, y_{t}, y'_{t+1})\), we obtain: \[\langle m_{t}, y_{t}-y'_{t+1}\rangle \le \frac{\|y'_{t+1}-y'_{t}\|^{2}- \|y'_{t+1}-y_{t}\|^{2}- \|y_{t}-y'_{t}\|^{2}}{2\eta}. \label{eq:step1}\tag{11}\]

Applying 10 with \((x, g, x^{+}, z) = (y'_{t}, \hat{g}_{t}, y'_{t+1}, y^{\star})\), we obtain: \[\langle \hat{g}_{t}, y'_{t+1}-y^{\star}\rangle \le \frac{\|y^{\star}-y'_{t}\|^{2}- \|y^{\star}-y'_{t+1}\|^{2}- \|y'_{t+1}-y'_{t}\|^{2}}{2\eta}. \label{eq:step2}\tag{12}\]

On the other hand, \[\|y_{t}-y'_{t+1}\| =\|\Pi_{C}(y'_{t}-\eta m_{t}) - \Pi_{C}(y'_{t}-\eta \hat{g}_{t})\| \le \|(y'_{t}-\eta m_{t}) - (y'_{t}-\eta \hat{g}_{t})\|= \eta\|\hat{g}_{t}-m_{t}\|.\] From the Cauchy-Schwarz inequality, we have: \[\langle \hat{g}_{t}-m_{t}, y_{t}-y'_{t+1}\rangle \le \|\hat{g}_{t}-m_{t}\| \cdot \|y_{t}-y'_{t+1}\| \le \eta\|\hat{g}_{t}-m_{t}\|^{2}. \label{eq:cross}\tag{13}\]

From the above equations, we can express the regret term at time \(t\) as: \[\langle \hat{g}_{t}, y_{t}-y^{\star}\rangle = \underbrace{\langle \hat{g}_t, y'_{t+1}-y^\star\rangle}_{\text{via } \eqref{eq:step2}}+ \underbrace{\langle \hat{g}_t-m_t, y_t-y'_{t+1}\rangle}_{\text{via } \eqref{eq:cross}}+ \underbrace{\langle m_t, y_t-y'_{t+1}\rangle}_{\text{via } \eqref{eq:step1}}.\] We note the term \(\frac{1}{2\eta} \|y'_{t+1}-y'_{t}\|^{2}\) appears in 12 with a negative sign and in 11 with a positive sign, leading to cancellation. Removing the remaining negative terms (\(-\|y'_{t+1}-y_{t}\|^{2}\) and \(-\|y_{t}-y'_{t}\|^{2}\)), we obtain: \[\langle \hat{g}_{t}, y_{t}-y^{\star}\rangle \le \frac{\|y^{\star}-y'_{t}\|^{2}- \|y^{\star}-y'_{t+1}\|^{2}}{2\eta}+ \eta\|\hat{g}_{t}-m_{t}\|^{2}.\] Finally, we can sum over \(t=1,\ldots,T\) to obtain: \[\sum_{t=1}^{T}\langle \hat{g}_{t}, y_{t}-y^{\star}\rangle \le \frac{\|y^{\star}-y'_{1}\|^{2}- \|y^{\star}-y'_{T+1}\|^{2}}{2\eta}+ \eta\sum_{t=1}^{T}\|\hat{g}_{t}-m_{t}\| ^{2}.\] Dropping the non-positive term \(-\frac{\|y^{\star}-y'_{T+1}\|^{2}}{2\eta}\) completes this proof. ◻

9.2 Proof of Theorem 4 ↩︎

Proof. We start with the regret decomposition given by Lemma 7: \[\mathfrak{R}_{T}\le \sum_{t=1}^{T}\big(f_{t}(y_{t})-f_{t}(y^{\star})\big) + \left(L+\frac{LD}{r}\right)\delta T.\] Using the convexity of \(f_{t}\), we establish the following: \[f_{t}(y_{t})-f_{t}(y^{\star}) \le \langle \nabla f_{t}(y_{t}), y_{t}-y^{\star} \rangle = \langle g_{t}^{y}, y_{t}-y^{\star}\rangle.\] Next, we decompose the term \(\langle g_{t}^{y}, y_{t}-y^{\star}\rangle\) into the following two terms: \[\langle g_{t}^{y}, y_{t}-y^{\star}\rangle=\underbrace{\langle \hat{g}_t, y_t-y^\star\rangle} _{\text{Algorithmic Regret}}+\underbrace{\langle g_t^y-\hat{g}_t, y_t-y^\star\rangle} _{\text{Estimation Bias}}.\]

Applying the bound from Lemma 8 to the convex set \(C=\mathcal{X}_{\alpha}\) gives us: \(\sum_{t=1}^{T}\langle \hat{g}_{t}, y_{t}-y^{\star}\rangle \le \frac{\|y^{\star}-y'_{1}\|^{2}}{2\eta}+ \eta\sum_{t=1}^{T}\|\hat{g}_{t}-m_{t}\|^{2}\). Since both \(y^{\star}\) and \(y'_{1}\) lie in \(\mathcal{X}_{\alpha}\subseteq \mathcal{X}\), we have \(\|y^{\star}-y'_{1}\|^{2}\le D^{2}\), which gives us: \[\sum_{t=1}^{T}\langle \hat{g}_{t}, y_{t}-y^{\star}\rangle\le \frac{D^{2}}{2\eta} + \eta\sum_{t=1}^{T}\|\hat{g}_{t}-m_{t}\|^{2}.\] Taking expectations of this expression gives the following bound using Corollary 3: \[\mathbb{E}\left[\sum_{t=1}^{T}\langle \hat{g}_{t}, y_{t}-y^{\star}\rangle\right] \;\le\; \frac{D^{2}}{2\eta}\;+\; \eta\left(4d\,\bar S_{T}+ \left(\frac{d^{2}}{2}+4d\right)\beta^{2}\delta^{2}T\right).\]

From Lemma 5, we know that \(\mathbb{E}[\hat{g}_{t}\mid \mathcal{H}_{t-1}] = g_{t}^{y}+ b_{t}\), which implies \(\mathbb{E}[g_{t}^{y}- \hat{g}_{t}\mid \mathcal{H}_{t-1}] = -b_{t}\). Therefore, we can use the tower property to find: \[\begin{align} \mathbb{E}\big[\langle g_{t}^{y}-\hat{g}_{t}, y_{t}-y^{\star}\rangle\big] & \;=\; \mathbb{E}\Big[\big\langle \mathbb{E}[g_{t}^{y}-\hat{g}_{t}\mid \mathcal{H}_{t-1}], y_{t}-y^{\star}\big\rangle\Big] \\ & = -\mathbb{E}\big[\langle b_{t}, y_{t}-y^{\star}\rangle\big]. \end{align}\] By the Cauchy-Schwarz inequality and the bound on \(\|b_{t}\| \le \frac{d}{2}\beta\delta\) shown in Lemma 5, we have: \[-\langle b_{t}, y_{t}-y^{\star}\rangle \leq |\langle b_{t}, y_{t}-y^{\star}\rangle|\leq \|b_{t}\| \cdot \|y_{t}-y^{\star} \| \le \frac{d}{2}\beta\delta \cdot D.\] Summing the above over \(t=1,\dots,T\) gives us a total expected bias bound by \(\frac{Dd\beta\delta T}{2}\).

Substituting the above into the regret decomposition including the perturbation cost gives us the final bound: \[\mathbb{E}[\mathfrak{R}_{T}]\le\frac{D^{2}}{2\eta}+\eta\left( 4d\,\bar S_{T}+ \left(\frac{d^{2}}{2}+4d\right)\beta^{2}\delta^{2}T \right) +\frac{Dd\beta\delta T}{2}+\left(L+\frac{LD}{r}\right)\delta T. \label{bmwsfzji}\tag{14}\] ◻

9.3 Proof of Theorem 5 ↩︎

Proof. The proof starts with the expected regret bound established in Theorem 4, as indicated below: \[\mathbb{E}[\mathfrak{R}_{T}] \le \underbrace{\frac{D^{2}}{2\eta} + 4d\eta \bar{S}_T} _{\text{Term (A)}}+ \underbrace{\eta\left(\frac{d^{2}}{2}+4d\right)\beta^2\delta^2T} _{\text{Term (B)}}+ \underbrace{\left[ \frac{Dd\beta}{2} + \left(L+\frac{LD}{r}\right) \right] \delta T}_{\text{Term (C)}}.\]

9.3.0.1 Term (A):

Substituting the learning rate \(\eta = \frac{D}{\sqrt{8d(\bar{S}_{T}+1)}}\) into it, we have: \[\begin{align} \frac{D^{2}}{2\eta}+ 4d\eta \bar{S}_{T} & = \frac{D^{2}}{2}\cdot \frac{\sqrt{8d (\bar{S}_{T}+1)}}{D}+ 4d \bar{S}_{T}\cdot \frac{D}{\sqrt{8d (\bar{S}_{T}+1)}} \\ & = \frac{D}{2}\sqrt{8d (\bar{S}_{T}+1)}+ D\sqrt{\frac{16 d^{2}\bar{S}_{T}^{2}}{8d (\bar{S}_{T}+1)}}\\ & \leq D\sqrt{2d (\bar{S}_{T}+1)}+ D\sqrt{2d \bar{S}_{T}}\\ &= O\left( D\sqrt{d\bar{S}_{T}}\right). \end{align}\]

9.3.0.2 Term (B):

Since \(\delta \le \frac{\sqrt{\bar{S}_{T}+1}}{d\beta T}\), we substitute \(\delta^{2}\le \frac{\bar{S}_{T}+1}{d^{2}\beta^{2}T^{2}}\) into Term (B): \[\begin{align} \eta\left(\frac{d^{2}}{2}+4d\right)\beta^{2}\delta^{2}T & \le \eta\left(\frac{d^{2}}{2}+4d\right)\beta^{2}T \cdot \frac{\bar{S}_{T}+1}{d^{2}\beta^{2}T^{2}} \\ & = \eta \left(\frac{1}{2}+ \frac{4}{d}\right) \frac{\bar{S}_{T}+1}{T}. \end{align}\] Substituting \(\eta = \frac{D}{\sqrt{8d (\bar{S}_{T}+1)}}\) gives us: \[\begin{align} \frac{D}{\sqrt{8d (\bar{S}_{T}+1)}}\left(\frac{1}{2}+ \frac{4}{d}\right) \frac{\bar{S}_{T}+1}{T}= O\left( \frac{D \sqrt{\bar{S}_{T}}}{T}\right). \end{align}\]

9.3.0.3 Term (C):

Also substituting \(\delta \le \frac{\sqrt{\bar{S}_{T}+1}}{d\beta T}\), we have: \[\begin{align} \left[ \frac{Dd\beta}{2}+ \left(L+\frac{LD}{r}\right) \right] \delta T & \le \left[ \frac{Dd\beta}{2}+ \left(L+\frac{LD}{r}\right) \right] \frac{\sqrt{\bar{S}_{T}+1}}{d\beta T}\cdot T \\ & = \left[ \frac{D}{2}+ \frac{L(1+D/r)}{d\beta}\right] \sqrt{\bar{S}_{T}+1}\\ & = O\left( D \sqrt{\bar{S}_{T}}\right). \end{align}\]

The perturbation radius \(\delta\) defined in Theorem 5 is defined as the minimum of the three quantities: \(\{ \frac{\sqrt{\bar{S}_{T}+1}}{d\beta T}, \frac{1}{\beta\sqrt{T}}, \frac{r}{2}\}\). The constraint \(\delta\leq \frac{r}{2}\) ensures that there is sufficient room for random perturbations while maintaining feasibility. Indeed, if \(\delta= r\), then \(\alpha=\delta/r=1\) and consequently \(\mathcal{X}_\alpha=\mathcal{X}\). In this case, to guarantee \(x_t=y_t+\delta v_t\in \mathcal{X}\) for \(\|v\|=1\), the point \(y_t\) would have to lie at the center of \(\mathcal{X}\), which is overly restrictive in general. Moreover, the condition \(\delta\leq 1/(\beta\sqrt{T})\) is imposed to control the accumulation of the second-order error term. Specifically, this ensures that the cumulative contribution \(\beta^2\delta^2 T\) remains uniformly bounded over the horizon \(T\). Since both Terms (B) and (C) are monotonically increasing in \(\delta\), if \(\delta\) is constrained by the second and third terms, the final regret should be smaller than the result by substituting \(\delta\leq \frac{\sqrt{\bar{S}_{T}+1}}{d\beta T}\). To derive the upper bound here, it is sufficient for us to substitute the first term \(\delta\leq \frac{\sqrt{\bar{S}_{T}+1}}{d\beta T}\)

Combining the bounds from Terms (A), (B), and (C), the total expected regret is written as: \[\mathbb{E}[\mathfrak{R}_{T}] = O\left( D \sqrt{d \bar S_{T}}\right).\] ◻

9.4 Omitted Details of Section 4.2 ↩︎

We first recall the definition of gradient variation proposed in [27] as: \[D_T=\sum_{t=1}^T \max_{x\in\mathcal{X}}\|\nabla f_t(x)-\nabla f_{t-1}(x)\|^2.\] By specializing our proposed TP-VR-Opt with restricting the sample distribution over \(\mathbb{S}^{d-1}\) to the standard basis vectors, i.e, \(v_t\sim \mathrm{Unif}(\{e_1,\dotsc,e_d\})\), the variant of TP-VR-Opt can be written shown as the following Algorithm 2. Our notation \(\Delta_{t,i_t}\) in TP-VR-Opt is written as \(\Delta_{t,i_t}=2\delta(\widehat{v}_{t,i_t}-m_{t,i_t})\) for convenience here.

Let \(\alpha_t=\max\{\tau<t: i_{\tau}=i_t\}\) with \(\alpha_t=0\) if the set is empty. By the definition of \(m_t\) whose \(i\)-th coordinate stores the most recent finite-difference observation on that coordinate, we have \(m_{t,i_t}=\widehat{v}_{\alpha_t,i_t}\).

Lemma 9. Assume each \(f_t\) is \(\beta\)-smooth. For any \(y_t\in\mathcal{X}_{\alpha}\) and any coordinate \(i\), we have \[|\widehat{v}_{t,i}(y_t)-\nabla_i f_t(y_t)|\leq \frac{\beta\delta}{2}.\] Then, \[\sum_{t=1}^T \mathbb{E}\left[\|\widehat{g}_t-m_t\|^2\right]\leq 3d^2\mathbb{E}\left[\sum_{t=1}^T\widehat{D}_t\right]+\frac{3}{2}d^2\beta^2\delta^2T,\] where \(\widehat{D}_t=\|\nabla_{i_t} f_t(y_t)-\nabla_{i_t}f_{\alpha_t}(y_{\alpha_t})\|^2\).

Proof. Replacing the \(v_t\) with \(e_{t,i}\) in Lemma 2 and dividing \(2\delta\), we have \[|\widehat{v}_{t,i}(y_t)-\nabla_i f_t(y_t)|\leq \frac{\beta\delta}{2}.\]

By the defintion of the esimator \(\widehat{g}_t\), we have \[\|\widehat{g}_t-m_t\|^2=d^2\|\widehat{v}_{t,i_t}-m_{t,i_t}\|^2\] Then, we can decompose \[\widehat{v}_{t,i_t}-m_{t,i_t}=\widehat{v}_{t,i_t}-\widehat{v}_{\alpha_t,i}=(\nabla_{i_t} f_t(y_t)-\nabla_{\alpha_t} f_t(y_t))+(\widehat{v}_{t,i_t}-\nabla_{\alpha_t} f_t(y_t))+(\nabla_{i_t} f_t(y_t)-\widehat{v}_{\alpha_t,i}).\]

Hence, we have: \[\|\widehat{v}_{t,i_t}-m_{t,i_t}\|^2\leq 3\|\nabla_{i_t} f_t(y_t)-\nabla_{\alpha_t} f_t(y_t)\|^2+\frac{3}{2}\beta^2\delta^2\] \[\sum_{t=1}^T \mathbb{E}\left[\|\widehat{g}_t-m_t\|^2\right]\leq 3d^2\mathbb{E}\left[\sum_{t=1}^T\widehat{D}_t\right]+\frac{3}{2}d^2\beta^2\delta^2T,\] where \(\widehat{D}_t=\|\nabla_{i_t} f_t(y_t)-\nabla_{i_t}f_{\alpha_t}(y_{\alpha_t})\|^2\). ◻

By applying Lemmas 8 and 12 in [27], we have \[\label{eq:hatD} \mathbb{E}\left[\sum_{t=1}^T\widehat{D}_t\right]\leq 4d^2 D_T+8d\beta^2\log T\cdot\mathbb{E}\left[\sum_{t=2}^T\|y_t-y_{t-1}\|^2\right]\tag{15}\]

Lemma 10. Let \(y_t=\Pi_{\mathcal{X}_\alpha}(y'_t-\eta m_t)\) and \(y'_{t+1}=\Pi_{\mathcal{X}_\alpha}(y'_t-\eta \widehat g_t)\). Then for any \(y^\star\in\mathcal{X}_\alpha\), \[\begin{align} \sum_{t=1}^T \langle \widehat g_t,\, y_t-y^\star\rangle &\le \frac{\|y^\star-y'_1\|^2}{2\eta} +\eta\sum_{t=1}^T \|\widehat g_t-m_t\|^2-\frac{1}{2\eta}\sum_{t=1}^T \Bigl(\|y_t-y'_t\|^2+\|y'_{t+1}-y_t\|^2\Bigr),\\ &\leq \frac{\|y^\star-y'_1\|^2}{2\eta} +\eta\sum_{t=1}^T \|\widehat g_t-m_t\|^2-\frac{1}{4\eta}\sum_{t=2}^{T}\|y_t-y_{t-1}\|^2. \end{align}\]

Proof. The first inequality above can be directly obtained by Lemma 8 by not dropping the two negative terms.

Then, we have \[\begin{align} \sum_{t=1}^T \Bigl(\|y_t-y'_t\|^2+\|y'_{t+1}-y_t\|^2\Bigr)&=\|y_1-y'_1\|^2+\sum_{t=2}^T(\|y_t-y'_t\|^2+\|y'_{t}-y_{t-1}\|^2)+\|y'_{T+1}-y_{T}\|^2\\ &\geq \sum_{t=2}^T(\|y_t-y'_t\|^2+\|y'_{t}-y_{t-1}\|^2)\\ &\geq \frac{1}{2}\sum_{t=2}^T \|y_t-y_{t-1}\|^2. \end{align}\] These complete the proof. ◻

By substituting the above lemmas and 15 into the proof of Theorem 5 as shown in Appendix 9.2, we have \[\mathbb{E}[\mathfrak{R}_{T}]\le\frac{D^{2}}{2\eta}+12\eta d^4 D_T+(\eta\cdot 24d^3\beta^2\log T-\frac{1}{4\eta})\sum_{t=2}^T \|y_t-y_{t-1}\|^2+\frac{3}{2}d^2\eta\beta^2\delta^2T +\frac{Dd\beta\delta T}{2}+\left(L+\frac{LD}{r}\right)\delta T.\]

By tuning the parameters with \[\eta=\min\left\{\frac{D}{4d^2\sqrt{D_T+1}},\frac{1}{16\beta d^{3/2}\sqrt{\log T}}\right\},\qquad \delta=\min\left\{\frac{\sqrt{D_T+1}}{\beta T},\frac{1}{\beta\sqrt{T}},\frac{r}{2}\right\},\] we have \[\mathbb{E}[\mathfrak{R}_{T}]\le\widetilde{O}(Dd^2 \sqrt{D_T})\] This recovers the result shown in [27].

9.5 Useful Lemmas in Section 4.3 ↩︎

Let \(T\) be the unknown time horizon. The algorithm runs in time phases, where the phases are indexed from \(k=1, \ldots, K\). Each time phase has an increasing length of \(H_{k}=2^{k-1}\). Let \(I_{k}\) denote the set of rounds executed in phase \(k\). We have \(|I_{k}|\le H_{k}\) and the phases partition the horizon such that \(\sum_{k=1}^{K}|I_{k}| = T\), which implies that \(K \le \lceil\log _{2}T\rceil+1 = O(\log T)\). For each phase \(k\), we define the phase-wise expected prediction-sensitivity as follows: \[\bar S_{k}= \mathbb{E}\bigg[\sum_{t\in I_k}\|\nabla f_{t}(x_{t})-m_{t}\|^{2}\bigg].\] From the definition, it can be seen that: \(\sum_{k=1}^{K}\bar S_{k}= \bar S_{T}\). Within each time phase \(k\), the sensitivity-doubling mechanism generates a set of epochs: \(e=1,\ldots,E_{k}\), where each epoch has a sensitivity budget of \(S_{k,e}=2^{e-1}\). Let us define the rounds executed in the epoch \((k,e)\) as \(J_{k,e}\subseteq I_{k}\), and let the accumulated epoch residual be defined as follows: \[R_{k,e}= \sum_{t\in J_{k,e}}\|\hat{g}_{t}-m_{t}\|^{2}.\]

Lemma 11. Assume each function \(f_{t}\) is \(L\)-Lipschitz on \(\mathcal{X}\) and the optimistic prediction \(m_{t}\) satisfies \(\|m_{t}\|\le L\). Then, for every round \(t\), the estimator error is bounded by: \[\|\hat{g}_{t}-m_{t}\| \le 2dL.\] For each epoch \((k,e)\), let \(J_{k,e}\) be the set of rounds in this epoch. If the epoch terminates because the residual threshold is exceeded, let \(\tau_{k,e}\) denote its last round and set \[O_{k,e}=\{\tau_{k,e}\}, \qquad J_{k,e}^{\circ}=J_{k,e}\setminus O_{k,e}.\] If the epoch terminates because the time budget is reached, set \(O_{k,e}=\emptyset\) and \(J_{k,e}^{\circ}=J_{k,e}\). Then \(|O_{k,e}|\le 1\) and \[\sum_{t\in J_{k,e}^{\circ}}\|\hat{g}_t-m_t\|^2 \le 8dS_{k,e}.\] Moreover, the full epoch residual satisfies \[\sum_{t\in J_{k,e}}\|\hat{g}_t-m_t\|^2 \le 8dS_{k,e}+4d^2L^2.\]

Proof. From the definition of the estimator \(\hat{g}_{t} = m_{t} + \frac{d}{2\delta}\Delta _{t} v_{t}\) with \[\Delta_{t} = f_{t}(y_{t}+\delta v_{t}) - f_{t}(y_{t}-\delta v_{t}) - 2\delta \langle m_{t},v_{t}\rangle,\] we have \[|\Delta_{t}|\le \big|f_{t}(y_{t}+\delta v_{t}) - f_{t}(y_{t}-\delta v_{t} )\big| + \big|2\delta\langle m_{t},v_{t}\rangle\big| \le 2L\delta + 2\delta \|m_{t}\|\|v_{t}\|.\] Since \(\|m_{t}\|\le L\) and \(\|v_{t}\|=1\), we have \(|\Delta_{t}| \le 4L\delta\). Substituting it back to \(\hat{g}_{t} = m_{t} + \frac{d}{2\delta}\Delta _{t} v_{t}\), we obtain: \[\|\hat{g}_{t}-m_{t}\|= \left\| \frac{d}{2\delta}\Delta_{t} v_{t} \right\| =\frac{d}{2\delta}|\Delta_{t}| \le\frac{d}{2\delta}(4L\delta)=2dL.\]

When we consider the stopping rule for this epoch \((k,e)\). Let \(\tau\) be the index of the last round executed in this epoch. The final round lasts until either the accumulated residual \(R_{k,e}\) becomes larger than the threshold or we have reached the end of the time phase; therefore, we can analyze these two different scenarios by doing the following:

Case 1 (Time Limit): If an epoch ends at the maximum length of the time phase \(H_{k}\), the accumulated residual did not exceed the threshold; therefore: \[R_{k,e}\le 8d S_{k,e}< 8d S_{k,e}+ 4d^{2}L^{2}.\]
Case 2 (Residual Exceed): If an epoch exceeded the accumulated residual before reaching \(H_{k}\), then we need to check out the last added term at round \(\tau\). If we had met or exceeded the residual threshold before reaching \(H_{k}\), then we can establish the preceding residual before adding term \(\tau\): \[\sum_{t \in J_{k,e} \setminus \{\tau\}}\|\hat{g}_{t} - m_{t}\|^{2} \le 8d S_{k,e}.\] Adding the final term and applying the per-round as shown above, we have: \[R_{k,e}= \sum_{t \in J_{k,e} \setminus \{\tau\}}\|\hat{g}_{t} - m_{t} \|^{2} \;+\; \|\hat{g}_{\tau} - m_{\tau}\|^{2} \le 8d S_{k,e}+ 4d^{2} L^{2}.\]

Combining both cases completes the proof. ◻

Lemma 12 (Epoch Regret Bound with Fixed Parameters). Assume each \(f_{t}\) is convex, \(L\)-Lipschitz, and \(\beta\)-smooth on \(\mathcal{X}\). Considering a specific epoch, for fixed time budget \(H\) and prediction-sensitivity budget \(S\), we set parameters \(\eta=D/\sqrt{8dS}\) and \(\delta =\min\{\frac{\sqrt{S}}{d\beta H},\frac{1}{\beta\sqrt{H}},\frac{r}{2}\}\). Let \(J\) be the set of rounds in this epoch. The expected regret \(\mathbb{E}[\mathfrak{R}(J)]\) on \(J\) is written as: \[\mathbb{E}[\mathfrak{R}(J)] \le 3\sqrt{2}\,D\sqrt{dS}+\frac{D}{2}\sqrt{S}+ \left(L+\frac{LD}{r}\right)\frac{\sqrt{S}}{d\beta}+LD.\]

Proof. To show this result, we apply the regret decomposition as our proof for TP-VR-Opt derived in Theorem 4, to the interval \(J\) and split the interval \(J\) into \(J=J^{\circ}\cup O\). We first consider \(t\in J^{\circ}\). Since the parameters \((\eta,\delta,\alpha)\) are fixed within the epoch, we have: \[\mathbb{E}[\mathfrak{R}(J^{\circ})]\le \underbrace{\frac{D^{2}}{2\eta} + \eta\,\mathbb{E}\bigg[\sum_{t\in J}\|\hat{g}_t-m_t\|^2\bigg]}_{\text{Term (A)}}+\underbrace{\left( \frac{Dd\beta}{2} + L + \frac{LD}{r} \right) \delta\,\mathbb{E}[|J^{\circ}|]}_{\text{Term (B)}}.\]

By Lemma 11, the accumulated residual is bounded by: \[\sum_{t\in J^{\circ}}\|\hat{g}_{t}-m_{t}\|^{2} \;\le\; 8dS.\] Substituting \(\eta = \frac{D}{\sqrt{8dS}}\), we have: \[\text{Term (A)}=3\sqrt{2}D\sqrt{dS}\] Since the stopping rule states \(|J^{\circ}| \le H\) and \(\delta\leq \frac{\sqrt{S}}{d\beta H}\), we have \[\begin{align} \frac{Dd\beta}{2}(\delta \mathbb{E}[|J^{\circ}|]) & \le \frac{Dd\beta}{2}(\delta H) \le \frac{Dd\beta}{2}\cdot \frac{\sqrt{S}}{d\beta}= \frac{D}{2}\sqrt{S}, \\ \left(L+\frac{LD}{r}\right) (\delta \mathbb{E}[|J^{\circ}|]) & \le \left(L+\frac{LD}{r}\right) \frac{\sqrt{S}}{d\beta}. \end{align}\] Besides, for \(t\in O\), we have \[\sum_{t\in O}(f_t(x_t)-f_t(x^\star))\leq LD|O|\leq LD.\] Thus, all terms combined yield the conclusion of the proof. ◻

Lemma 13. Let \(S_{k,1},\cdots,S_{k,E_k}\) denote the budgets of prediction sensitivity used during phase \(k\) where \(S_{k,e}=S_{\min}\cdot2^{e-1}\) for \(e=1,\ldots,E_k\). Then, we have the following result: \[\sum_{e=1}^{E_k}\sqrt{S_{k,e}} \le 4\sqrt{S_{k,E_k}}.\]

Proof. Since \(S_{k,e}=S_{\min}\cdot2^{e-1}\), we first have \[\begin{align} \sum_{e=1}^{E_k}\sqrt{S_{k,e}} &= \sqrt{S_{\min}} \sum_{e=1}^{E_k}2^{(e-1)/2} \\ &= \sqrt{S_{\min}} \sum_{j=0}^{E_k-1}(\sqrt{2})^j \\ &= \sqrt{S_{\min}}\, \frac{(\sqrt{2})^{E_k}-1}{\sqrt{2}-1}. \end{align}\] Using \((\sqrt{2})^{E_k}-1<(\sqrt{2})^{E_k}\), we obtain \[\begin{align} \sum_{e=1}^{E_k}\sqrt{S_{k,e}} &< \sqrt{S_{\min}}\, \frac{(\sqrt{2})^{E_k}}{\sqrt{2}-1} \\ &= \frac{\sqrt{2}}{\sqrt{2}-1} \sqrt{S_{\min}}(\sqrt{2})^{E_k-1} \\ &= (2+\sqrt{2})\sqrt{S_{k,E_k}} \le 4\sqrt{S_{k,E_k}} . \end{align}\] This completes the proof. ◻

Lemma 14. Let \(R^{\mathrm{obs}}_{k}= \sum_{t\in I_k}\|\hat{g} _{t}-m_{t}\|^{2}\) denote the accumulated observable residual in phase \(k\), and let \(S_{k,E_k}\) be the final sensitivity budget used during phase \(k\). Then, we have: \[S_{k,E_k}\le S_{\min} + \frac{R^{\mathrm{obs}}_{k}}{8d}.\]

Proof. Given the number of epochs \(E_k\) in phase \(k\), we will consider the proofs in two cases.

\(E_{k}=1\): The prediction-sensitivity budget is at its starting value of \(S_{k,1}=S_{\min}\). As \(R^{\mathrm{obs}}_{k} \ge 0\), we see \(S_{\min} \le S_{\min} + R^{\mathrm{obs}}_{k}/(8d)\) trivially.

\(E_{k} \ge 2\): The fact that the algorithm has progressed to epoch \(E_{k}\) implies that all previous epochs \(e=1,\dots,E_{k}-1\) were terminated because the residual threshold has been exceeded. For all \(e < E_{k}\), this gives \(R_{k,e}> 8 d S_{k,e}\). Summing these residuals, we obtain: \[R^{\mathrm{obs}}_{k} \ge \sum_{e=1}^{E_k-1}R_{k,e}> 8d \sum_{e=1}^{E_k-1} S_{k,e}.\] Since \(S_{k,e}= S_{\min}\cdot 2^{e-1}\), we obtain the telescopic series: \[\sum_{e=1}^{E_k-1}S_{k,e}= S_{\min}\cdot\sum_{e=1}^{E_k-1}2^{e-1}= S_{\min}\cdot(2^{E_k-1}- 1) = S_{k,E_k} - S_{\min}.\] Substituting this back, we obtain: \(R^{\mathrm{obs}}_{k} > 8d(S_{k,E_k}-S_{\min})\). Rearranging terms yields the desired bound. ◻

Lemma 15 (Observed residual in a phase). Let \(\mathfrak{R}_k^{\mathrm{obs}}= \sum_{t\in I_k}\|\hat{g}_t-m_t\|^2\) be the accumulated observable residual in phase \(k\). Suppose that the sensitivity budgets in phase \(k\) satisfy \[S_{k,e}=S_{\min}2^{e-1},\qquad e=1,\ldots,E_k,\] and that, within each epoch \((k,e)\), the perturbation radius is chosen as \[\delta_{k,e} = \min\left\{ \frac{\sqrt{S_{k,e}}}{d\beta H_k}, \frac{1}{\beta\sqrt{H_k}}, \frac{r}{2} \right\}.\] Then, we have \[\mathbb{E}[\mathfrak{R}_k^{\mathrm{obs}}] \le \frac{ 4d\,\bar S_k+\frac{9}{2}\frac{S_{\min}}{H_k} }{ 1-\frac{9}{16dH_k} }.\] In particular, since \(d\ge 1\) and \(H_k\ge 1\), \[\mathbb{E}[\mathfrak{R}_k^{\mathrm{obs}}] \le \frac{64}{7}d\,\bar S_k + \frac{72}{7}\frac{S_{\min}}{H_k}.\] Consequently, the final sensitivity budget in phase \(k\) satisfies \[\mathbb{E}[S_{k,E_k}] \le S_{\min} + \frac{1}{8d} \cdot \frac{ 4d\,\bar S_k+\frac{9}{2}\frac{S_{\min}}{H_k} }{ 1-\frac{9}{16dH_k} },\] and, in particular, \[\mathbb{E}[S_{k,E_k}] \le \frac{8}{7}\bar S_k + \frac{16}{7}S_{\min}.\]

Proof. Let \(Q_k=\mathbb{E}[\mathfrak{R}_k^{\mathrm{obs}}]\). From Corollary 3, for every round \(t\in I_k\), we have \[\mathbb{E}\!\left[ \|\hat{g}_t-m_t\|^2 \mid \mathcal{H}_{t-1} \right] \le 4d\|\nabla f_t(x_t)-m_t\|^2 + (d^2/2+4d)\beta^2\delta_t^2,\] where \(\delta_t\) is the perturbation radius used at round \(t\). Summing this inequality over all rounds \(t\in I_k\) and then taking total expectation gives \[\begin{align} Q_k &= \mathbb{E}\left[ \sum_{t\in I_k}\|\hat{g}_t-m_t\|^2 \right] \\ &\le 4d\, \mathbb{E}\left[ \sum_{t\in I_k}\|\nabla f_t(x_t)-m_t\|^2 \right] + (d^2/2+4d)\beta^2 \mathbb{E}\left[ \sum_{t\in I_k}\delta_t^2 \right] \\ &= 4d\,\bar S_k + (d^2/2+4d)\beta^2 \mathbb{E}\left[ \sum_{t\in I_k}\delta_t^2 \right]. \end{align}\] We now decompose the last sum epoch by epoch. Since the perturbation radius is fixed within each epoch \((k,e)\), we can write \[\sum_{t\in I_k}\delta_t^2 = \sum_{e=1}^{E_k}|J_{k,e}|\delta_{k,e}^2.\] For every epoch \((k,e)\), by the definition of \(\delta_{k,e}\), \[\delta_{k,e} \le \frac{\sqrt{S_{k,e}}}{d\beta H_k}.\] Therefore, \[\begin{align} (d^2/2+4d)\beta^2\delta_{k,e}^2 &\le (d^2/2+4d)\beta^2 \cdot \frac{S_{k,e}}{d^2\beta^2H_k^2} \\ &= \left(\frac{1}{2}+\frac{4}{d}\right) \frac{S_{k,e}}{H_k^2}. \end{align}\] Since \(d\ge1\), we have \(\frac{1}{2}+\frac{4}{d}\le \frac{9}{2}\). Hence, \[(d^2/2+4d)\beta^2\delta_{k,e}^2 \le \frac{9}{2}\frac{S_{k,e}}{H_k^2}.\] Substituting this bound into the epoch-wise decomposition yields \[\begin{align} (d^2/2+4d)\beta^2 \sum_{e=1}^{E_k}|J_{k,e}|\delta_{k,e}^2 &\le \frac{9}{2} \sum_{e=1}^{E_k} |J_{k,e}|\frac{S_{k,e}}{H_k^2}. \end{align}\] The budgets \(S_{k,e}\) are nondecreasing in \(e\), and hence \(S_{k,e}\le S_{k,E_k}\) for every \(e\le E_k\). Moreover, the total number of rounds in phase \(k\) is at most \(H_k\), so \[\sum_{e=1}^{E_k}|J_{k,e}|=|I_k|\le H_k.\] Therefore, pathwise, \[\begin{align} \sum_{e=1}^{E_k} |J_{k,e}|\frac{S_{k,e}}{H_k^2} &\le \sum_{e=1}^{E_k} |J_{k,e}|\frac{S_{k,E_k}}{H_k^2} \\ &= \frac{S_{k,E_k}}{H_k^2} \sum_{e=1}^{E_k}|J_{k,e}| \\ &\le \frac{S_{k,E_k}}{H_k}. \end{align}\] Combining the above estimates gives \[Q_k \le 4d\,\bar S_k + \frac{9}{2H_k}\mathbb{E}[S_{k,E_k}].\]

It remains to control the final sensitivity budget \(S_{k,E_k}\). By Lemma 14, we have the pathwise bound \[S_{k,E_k} \le S_{\min} + \frac{R_k^{\mathrm{obs}}}{8d}.\] Taking expectation on both sides gives \[\mathbb{E}[S_{k,E_k}] \le S_{\min} + \frac{Q_k}{8d}.\] Substituting this inequality into the previous estimate for \(Q_k\), we obtain \[\begin{align} Q_k \le 4d\,\bar S_k + \frac{9}{2H_k} \left( S_{\min} + \frac{Q_k}{8d} \right) = 4d\,\bar S_k + \frac{9}{2}\frac{S_{\min}}{H_k} + \frac{9}{16dH_k}Q_k. \end{align}\] Moving the last term to the left-hand side gives \[\left( 1-\frac{9}{16dH_k} \right)Q_k \le 4d\,\bar S_k + \frac{9}{2}\frac{S_{\min}}{H_k}.\] Therefore, \[Q_k \le \frac{ 4d\,\bar S_k+\frac{9}{2}\frac{S_{\min}}{H_k} }{ 1-\frac{9}{16dH_k} }.\] This proves the first claimed bound.

Since \(d\ge1\) and \(H_k\ge1\), we have \[1-\frac{9}{16dH_k} \ge 1-\frac{9}{16} = \frac{7}{16}.\] Thus, \[\begin{align} Q_k \le \frac{16}{7} \left( 4d\,\bar S_k + \frac{9}{2}\frac{S_{\min}}{H_k} \right) = \frac{64}{7}d\,\bar S_k + \frac{72}{7}\frac{S_{\min}}{H_k}. \end{align}\] This proves the simplified residual bound.

Finally, applying Lemma 14 once more, \[\mathbb{E}[S_{k,E_k}] \le S_{\min} + \frac{Q_k}{8d}.\] Using the explicit bound on \(Q_k\) gives \[\begin{align} \mathbb{E}[S_{k,E_k}] \le S_{\min} + \frac{1}{8d} \left( \frac{64}{7}d\,\bar S_k + \frac{72}{7}\frac{S_{\min}}{H_k} \right) = S_{\min} + \frac{8}{7}\bar S_k + \frac{9}{7dH_k}S_{\min}. \end{align}\] Since \(dH_k\ge1\), \[\frac{9}{7dH_k}S_{\min} \le \frac{9}{7}S_{\min}.\] Hence, \[\mathbb{E}[S_{k,E_k}] \le \frac{8}{7}\bar S_k + \frac{16}{7}S_{\min}.\] This completes the proof. ◻

Lemma 16. Let \(\Lambda_{k}= \bar S_{k}+ 2S_{\min}\). The expected regret associated with phase \(k\) is bounded by: \[\mathbb{E}[\mathfrak{R}(I_{k})] \le \widetilde{O}\left(D\sqrt{d\Lambda_k} \right).\]

Proof. The regret in phase \(k\) is the sum of the regrets incurred in each epoch \(e=1, \dots,E_{k}\). Based on Lemma 12, the regret for each epoch is bounded by terms proportional to \(\sqrt{S_{k,e}}\) and \(1/\sqrt{S_{k,e}}\). Summing these bounds over all epochs and applying the fact \(\sum \sqrt{S_{k,e}}\le 4\sqrt{S_{k,E_k}}\) from Lemma 13, we obtain: \[\sum_{e=1}^{E_k}\mathbb{E}[\mathfrak{R}(J_{k,e})] \le 12\sqrt{2}D\sqrt{d\,S_{k,E_k}} + 2 D\sqrt{S_{k,E_k}}+4\left(L+\frac{LD}{r}\right)\frac{\sqrt{S_{k,E_k}}}{d\beta}+LDE_k.\]

Taking the total expectation over \(S_{k,E_k}\) and applying Jensen’s inequality to the concave function \(\sqrt{x}\), we have: \[\mathbb{E}[\mathfrak{R}(I_{k})] \le 12\sqrt{2}\, D\sqrt{d\,\mathbb{E}[S_{k,E_k}]} + 2 D\sqrt{\mathbb{E}[S_{k,E_k}]}+4\left(L+\frac{LD}{r}\right)\frac{\sqrt{\mathbb{E}[S_{k,E_k}]}}{d\beta}+LD\log T.\]

From Lemma 15, we have \[\mathbb{E}[S_{k,E_k}] \le \frac{8}{7}\bar S_k+\frac{16}{7}S_{\min}.\] Substituting it into the regret bound, we have \[\mathbb{E}[\mathfrak{R}(I_{k})] \le \widetilde{O}\left(D\sqrt{d\Lambda_k}\right)\] This completes the proof. ◻

9.6 Proof of Theorem 6 ↩︎

Proof. The total time horizon \(T\) is partitioned into \(K\) phases, indexed by \(k=1, \dots, K\). Since the time budget doubles (\(H_{k} = 2^{k-1}\)), the number of phases is bounded by \(K \le \lceil \log_{2} T \rceil + 1 = O(\log T)\). The total expected regret is the sum of the expected regret in all phases: \[\mathbb{E}[\mathfrak{R}_{T}] = \sum_{k=1}^{K} \mathbb{E}[\mathfrak{R}(I_{k})].\] From Lemma 16, in each phase \(k\), we have: \[\mathbb{E}[\mathfrak{R}(I_{k})] \le \widetilde{O}\left( D\sqrt{d\,\Lambda_{k}}\right),\] where \(\Lambda_{k} = \bar S_{k}+ 2S_{\min}\) and \(\bar S_{k} = \mathbb{E}[\sum_{t \in I_k}\|\nabla f_{t}(x_{t}) - m_{t}\|^{2}]\). Then, by summing it over \(k=1, \dots, K\): \[\mathbb{E}[\mathfrak{R}_{T}] \le O\left( D\sqrt{d}\sum_{k=1}^{K} \sqrt{\Lambda_{k}}\right).\] Using the Cauchy-Schwarz inequality, i.e., \(\sum_{k=1}^{K} \sqrt{x_{k}}\le \sqrt{K \sum_{k=1}^{K} x_{k}}\) on the first term: \[\sum_{k=1}^{K} \sqrt{\Lambda_{k}}\le \sqrt{K \sum_{k=1}^{K} (\bar S_{k}+2S_{\min})}= \sqrt{K (\bar S_{T} + 2KS_{\min})}\le \sqrt{K \bar S_{T}}+ K\sqrt{2S_{\min}} ,\] where we apply the fact that \(\sum_{k=1}^K \bar S_{k} = \bar S_{T}\). Substituting \(K = O(\log T)\), this term becomes: \[\sum_{k=1}^{K} \sqrt{\Lambda_{k}}\le O\left(\sqrt{\bar S_{T} \log T}+ \log T\right).\] The total expected regret is bounded by: \[\mathbb{E}[\mathfrak{R}_{T}] \le O\left( D\sqrt{d\,\bar S_{T} \log T}+D\sqrt{d}\log T\right).\] ◻

9.7 Proof of Theorem 7 ↩︎

Proof. The proof proceeds by constructing a specific hard instance within the convex set \(\mathcal{X}\). There exist two points \(x_+, x_- \in \mathcal{X}\) such that \(\|x_+ - x_-\| = D\). Define the unit vector \(v= (x_+ - x_-)/D\) and the midpoint \(x_0 = (x_+ + x_-)/2\). By convexity, the line segment \(J = \{x_0 + \alpha v : \alpha \in [-D/2, D/2]\}\) is contained entirely in \(\mathcal{X}\).

Let \((\zeta_t)_{t=1}^T\) be a sequence of i.i.d.Rademacher random variables, i.e., \(\mathbb{P}(\zeta_t = +1) = \mathbb{P}(\zeta_t = -1) = 1/2\). We will define the linear loss function sequence by: \[f_t(x) = \langle g_t, x\rangle, \qquad \text{where} \quad g_t = \mu \zeta_t v,\] for a scaling parameter \(\mu \in (0, L]\) yet to be determined. The gradients satisfy \(\|\nabla f_t(x)\| = \|\mu \zeta_t v\| = \mu \le L\), ensuring the functions are \(L\)-Lipschitz.

We now verify the intrinsic prediction-error level. Let \(\Pi\) be the class of all admissible non-anticipating prediction policies. We next show that the zero predictor is optimal among all admissible non-anticipating predictors in the conditional mean-square sense. For every admissible policy \(\pi\), the prediction \(m_t^\pi\) is \(\mathcal{H}_{t-1}\)-measurable, whereas \(g_t=\mu\zeta_t v\) is independent of \(\mathcal{H}_{t-1}\) and satisfies \(\mathbb{E}[g_t\mid\mathcal{H}_{t-1}]=0\). Hence, we have \[\begin{align} \mathbb{E}\|g_t-m_t^\pi\|^2 &= \mathbb{E}\|g_t\|^2 + \mathbb{E}\|m_t^\pi\|^2 - 2\mathbb{E}\langle g_t,m_t^\pi\rangle \nonumber \\ &= \mu^2 + \mathbb{E}\|m_t^\pi\|^2 - 2\mathbb{E}\left[ \left\langle \mathbb{E}[g_t\mid\mathcal{H}_{t-1}], m_t^\pi \right\rangle \right] \nonumber \\ &= \mu^2+\mathbb{E}\|m_t^\pi\|^2 \ge \mu^2\label{eq:expectation95lower}. \end{align}\tag{16}\]

The lower bound in 16 is attained by the admissible prediction policy \(\pi^0\) that outputs \(m_t^{\pi^0}\equiv 0\) for all \(t\). Hence \(m_t\equiv0\) is the conditional mean-square optimal non-anticipating predictor for this hard instance. Consequently, \[\bar S_T^\star(\mathcal{D}_S,A) = \inf_{\pi\in\Pi} \bar S_T^\pi(\mathcal{D}_S,A) = T\mu^2 .\] Choosing \(\mu=\sqrt{\frac{S}{T}}\) and using \(S\le L^2T\), we have \(\mu\le L\), so the losses remain \(L\)-Lipschitz. With this choice, we have \[\bar S_T^\star(\mathcal{D}_S,A)=S .\]

It remains to prove the regret lower bound. Fix any admissible prediction policy \(\pi\in\Pi\), and let \(x_t^\pi\) denote the point at which the algorithm incurs loss at round \(t\) when using this prediction policy. Since \(x_t^\pi\) is \(\mathcal{H}_{t-1}\)-measurable, while \(\zeta_t\) is independent of \(\mathcal{H}_{t-1}\) and has mean zero, we obtain \[\begin{align} \mathbb{E}[f_t(x_t^\pi)] &= \mathbb{E} \left[ \mathbb{E}[ \langle \mu\zeta_t v,x_t^\pi\rangle \mid \mathcal{H}_{t-1} ] \right] \\ &= \mu\, \mathbb{E} \left[ \langle v,x_t^\pi\rangle \mathbb{E}[\zeta_t\mid\mathcal{H}_{t-1}] \right] = 0. \end{align}\] Hence, it follows that \[\mathbb{E}\Big[\sum_{t=1}^T f_t(x_t^\pi)\Big]=0.\]

We now lower bound the regret by showing that the best fixed comparator in hindsight can achieve a substantially negative cumulative loss. Let \(Z_T=\sum_{t=1}^T \zeta_t\). Since the segment \(J=\{x_0+\alpha v:\alpha\in[-D/2,D/2]\}\) is contained in \(\mathcal{X}\), the best comparator over \(\mathcal{X}\) is at least as good as the best comparator restricted to \(J\). Hence, \[\min_{x\in\mathcal{X}}\sum_{t=1}^T f_t(x) \le \min_{\alpha\in[-D/2,D/2]} \sum_{t=1}^T f_t(x_0+\alpha v). \label{eq:restrict95to95segment}\tag{17}\] For any \(\alpha\in[-D/2,D/2]\), using \(f_t(x)=\langle \mu\zeta_t v,x\rangle\) gives \[\begin{align} \sum_{t=1}^T f_t(x_0+\alpha v) &= \sum_{t=1}^T \langle \mu\zeta_t v,x_0+\alpha v\rangle \\ &= \mu\langle v,x_0\rangle Z_T + \mu\alpha Z_T . \end{align} \label{eq:loss95on95segment}\tag{18}\] The first term in 18 does not depend on \(\alpha\). Therefore, minimizing over \(\alpha\) only requires minimizing the linear term \(\mu\alpha Z_T\) over the interval \([-D/2,D/2]\). The minimizer is attained at the endpoint opposite to the sign of \(Z_T\): \[\alpha^\star = -\frac{D}{2}\,\operatorname{sign}(Z_T),\] with the convention \(\operatorname{sign}(0)=0\). Substituting this choice into 18 yields \[\min_{\alpha\in[-D/2,D/2]} \sum_{t=1}^T f_t(x_0+\alpha v) \le \mu\langle v,x_0\rangle Z_T - \frac{\mu D}{2}|Z_T|. \label{eq:segment95min95loss}\tag{19}\] Combining 17 and 19 , we obtain \[\min_{x\in\mathcal{X}}\sum_{t=1}^T f_t(x) \le \mu\langle v,x_0\rangle Z_T - \frac{\mu D}{2}|Z_T|. \label{eq:comparator95loss95upper}\tag{20}\]

We now take expectations. Since \(\mathbb{E}[Z_T]=0\), the first term on the right-hand side of 20 vanishes. Moreover, by Khintchine’s inequality [1], there exists a universal constant \(c_0>0\) such that \[\mathbb{E}|Z_T| = \mathbb{E}\left|\sum_{t=1}^T\zeta_t\right| \ge c_0\sqrt T .\] Therefore, we have \[\mathbb{E}\left[ \min_{x\in\mathcal{X}} \sum_{t=1}^T f_t(x) \right] \le - \frac{c_0\mu D}{2}\sqrt T . \label{eq:expected95comparator95loss}\tag{21}\]

Recall that for any admissible prediction policy \(\pi\in\Pi\), the learner’s decision \(x_t^\pi\) is \(\mathcal{H}_{t-1}\)-measurable, while \(\zeta_t\) is independent of \(\mathcal{H}_{t-1}\) and has mean zero. Hence we have already shown that \[\mathbb{E}\sum_{t=1}^T f_t(x_t^\pi)=0 .\] Thus, for every admissible prediction policy \(\pi\in\Pi\), \[\begin{align} \mathbb{E}[\mathfrak{R}_T(\mathcal{A})] &= \mathbb{E}\sum_{t=1}^T f_t(x_t^\pi) - \mathbb{E}\left[ \min_{x\in\mathcal{X}} \sum_{t=1}^T f_t(x) \right] \\ &\ge 0 - \left( -\frac{c_0\mu D}{2}\sqrt T \right) \\ &= \frac{c_0\mu D}{2}\sqrt T . \end{align} \label{eq:regret95lower95before95scaling}\tag{22}\] Finally, substituting \(\mu=\sqrt{S/T}\) into 22 gives \[\mathbb{E}[\mathfrak{R}_T(\mathcal{A})] \ge \frac{c_0D}{2}\sqrt S .\] The theorem follows with \(c=c_0/2\). ◻

Remark 12 (Nonzero Bayes predictors). The lower bound is not tied to the special case in which the Bayes-optimal predictor is zero. Indeed, one may add any predictable component to the gradient sequence without changing the residual hardness. For example, on a two-dimensional product domain, let \(\nabla f_t = \mu e_1 + \sigma \zeta_t e_2\), where \(\mu e_1\) is known before round \(t\), while \(\zeta_t\) is an independent Rademacher sign. The Bayes-optimal non-anticipating predictor is \(m_t^\star=\mu e_1\), and hence \(\sum_{t=1}^T \|\nabla f_t-m_t^\star\|^2=T\sigma^2\). The predictable component \(\mu e_1\) can be perfectly removed by the predictor, but the residual component \(\sigma\zeta_t e_2\) still induces the same standard randomized linear lower bound, yielding \[\mathbb{E}[\mathfrak{R}_T]\ge cD\sigma\sqrt T = cD\sqrt{S}.\] Thus the lower bound should be interpreted as a lower bound on the unpredictable residual, not merely on the total gradient energy.

10 Omitted Details of Section 5 ↩︎

10.1 Useful Lemmas in Section 5 ↩︎

Lemma 17 (Dynamic optimistic projected-gradient inequality). Suppose that the sequences \(\{y_{t}\}_{t=1}^{T}\) and \(\{y'_{t}\}_{t=1}^{T}\) were generated using the optimistic update as rule Algorithm 1 with stepsize \(\eta > 0\) on the set \(\mathcal{X}_{\alpha}\). Then, for any comparator sequence \((u'_{t})_{t=1}^{T} \subseteq \mathcal{X}_{\alpha}\), we have the inequality: \[\sum_{t=1}^{T} \langle \hat{g}_{t},\, y_{t}-u'_{t}\rangle \le\frac{D^{2}+2D\,P_{T}(u'_{1:T})}{2\eta} +\eta\sum_{t=1}^{T} \|\hat{g}_{t}-m_{t}\|^{2},\] where \(D\) is the diameter of the domain (\(\|\mathcal{X}_{\alpha}\|\leq\|\mathcal{X}\|\leq D\)) and \(P_{T}(u'_{1:T})=\sum_{t=2}^{T}\|u'_{t}-u'_{t-1}\|\) is the path-length of \(\{u'_{t}\}_{t=1}^T\).

Proof. For any fixed round \(t\) and any fixed comparator \(u'_{t} \in \mathcal{X}_{\alpha}\), Lemma 8 gives us the standard one-step analysis of the optimistic update for round \(t\), which yields the following inequality: \[\langle \hat{g}_{t},\, y_{t}-u'_{t}\rangle \le\frac{\|u'_{t}-y'_{t}\|^{2}-\|u'_{t}-y'_{t+1}\|^{2}}{2\eta} +\eta\|\hat{g}_{t}-m_{t}\|^{2}.\] Summing both sides of this inequality over all rounds gives us: \[\sum_{t=1}^{T} \langle \hat{g}_{t},\, y_{t}-u'_{t}\rangle \le\frac{1}{2\eta} \underbrace{\sum_{t=1}^T\Bigl(\|u'_t-y'_t\|^2-\|u'_t-y'_{t+1}\|^2\Bigr)} _{\Phi}+\eta\sum_{t=1}^{T}\|\hat{g}_{t}-m_{t}\|^{2}.\] Now let us compute the potential term \(\Phi\). The terms can be rearranged so that \(y'_{t+1}\) can be combined: \[\begin{align} \Phi & =\|u'_{1}-y'_{1}\|^{2} - \|u'_{T}-y'_{T+1}\|^{2} + \sum_{t=1}^{T-1}\|u'_{t}-y'_{t+1}\|^{2} - \sum_{t=2}^{T} \|u'_{t}-y'_{t}\|^{2} \\ & =\|u'_{1}-y'_{1}\|^{2} - \|u'_{T}-y'_{T+1}\|^{2}+ \sum_{t=2}^{T} \Bigl( \|u'_{t}-y'_{t}\|^{2} - \|u'_{t-1}-y'_{t}\|^{2} \Bigr). \end{align}\]

Note that \(\|u'_{T}-y'_{T+1}\|^{2}\le 0\) is non-positive, so we can omit it from \(\Phi\). The upper bound \(\|u'_{1}-y'_{1}\|^{2}\le D^{2}\). To compute the summation term, use the equality \(\|a\|^{2}-\|b\|^{2}=\langle a-b,\,a+b\rangle\). Thus, for \(a=u'_{t}-y'_{t}\) and \(b=u'_{t-1}-y'_{t}\), we find that \(a-b=u'_{t}-u'_{t-1}\) and \(a+b=(u'_{t}-y'_{t})+(u'_{t-1}-y'_{t})\). So we get: \[\begin{align} \|u'_{t}-y'_{t}\|^{2}-\|u'_{t-1}-y'_{t}\|^{2} & =\langle u'_{t}-u'_{t-1},\, (u'_{t}-y'_{t})+(u'_{t-1}-y'_{t})\rangle\\ & \le\|u'_{t}-u'_{t-1}\| \cdot \Bigl(\|u'_{t}-y'_{t}\|+\|u'_{t-1}-y'_{t}\|\Bigr) \\ & \le\|u'_{t}-u'_{t-1}\| \cdot (D+D) =2D\|u'_{t}-u'_{t-1}\|. \end{align}\] Using the fact that \(u'_{t},u'_{t-1},y'_{t}\in \mathcal{X}_{\alpha}\), we obtain that the diameter of \(\mathcal{X}_{\alpha}\) is at most \(D\). By summing this inequality over \(t=2,\ldots,T\), we obtain \[\Phi \le D^{2} + 2D \sum_{t=2}^{T} \|u'_{t}-u'_{t-1}\| = D^{2} + 2D\,P_{T}(u'_{1:T}).\] These complete the proof. ◻

Lemma 18. Let \(\mathcal{\mathcal{X}}_{\alpha} \subseteq \mathbb{R} ^{d}\) be a convex set with Euclidean diameter at most \(D\). We consider the optimistic updates applied to \(\mathcal{X}_{\alpha}\): \[y_{t} = \Pi_{\mathcal{X}_\alpha}(y'_{t} - \eta m_{t}), \qquad y'_{t+1}= \Pi _{\mathcal{X}_\alpha}(y'_{t} - \eta \hat{g}_{t}),\] where \(\eta>0\). For any choice of a comparator sequence \(\{u_t'\}_{t \in J} \subseteq \mathcal{X}_{\alpha}\) with respect to index set \(J\), \[\sum_{t \in J}\langle \hat{g}_{t}, y_{t} - u'_{t}\rangle \le\frac{\|u'_{t_0}-y'_{t_0}\|^{2}}{2\eta} +\eta\sum_{t \in J}\|\hat{g}_{t}-m_{t}\|^{2} +\frac{D}{\eta}\sum_{t\in J, t>t_0}\|u'_{t}-u'_{t-1}\|,\] where \(t_{0} = \min J\).

Proof. The proof is the same as in Lemma 17, except that we take our sum over the index set \(J\), not over all rounds. ◻

Definition 3 (Epoch Path-length). For any epoch \((k, e)\) in TP-VR-Opt++, let \(J_{k, e}\) be the set of the active rounds. The epoch path-length \(P_{k, e}\) is defined to be the total movement of the comparator sequence across the indices of \(J_{k,e}\). \[P_{k,e}= \sum_{t \in J_{k,e} \setminus \{\min J_{k,e}\}}\|u_{t} - u_{t-1}\|.\] For the good prefix \(J_{k,e}^{\circ}\), we use the same notation \(P_{k,e}\) as an upper bound on its path-length, since the path-length on \(J_{k,e}^{\circ}\) is no larger than that on \(J_{k,e}\).

Lemma 19 (Optimistic Hedge Regret). The Optimistic Hedge algorithm is defined on the simplex \(\Delta_{N}\) with a prior distribution \(w_1\) and a step-size \(\epsilon\). The loss vector at time \(t\) is denoted by \(\ell_{t}\) and the prediction vector at time \(t\) is given by \(M_{t}\). The regret to any expert \(i^{\star}\) at any time \(T\) is bounded by: \[\sum_{t=1}^{T} (\langle p_{t}, \ell_{t} \rangle - \ell_{t,i^\star}) \le \frac{\ln(1/w_{1,i^\star})}{\varepsilon} + \frac{\varepsilon}{2} \sum_{t=1}^{T} \|\ell_{t} - M_{t}\|_{\infty}^{2}.\] Specifically, for the setting of Algorithm 4 where \(\ell_{t,i} = \langle \hat{g}_{t}, y_{t,i}\rangle\), and \(M_{t,i}= \langle m_{t}, y_{t,i}\rangle\), we have the following: \[\|\ell_{t} - M_{t}\|_{\infty}^{2} \le D^{2} \|\hat{g}_{t} - m_{t}\|_{2}^{2}.\]

Proof. We note that the meta-algorithm is an example of Optimistic Mirror Descent (OMD) employing the regularizer \(\psi(w)=\sum_{i=1}^{N} w_{i} \ln w_{i}\) on the probability simplex \(\Delta_{N}\). The Bregman Divergence associated with this will be the KL Divergence, defined as \(D_{\psi}(p,q) = \sum_{i=1}^{N} p_{i} \ln(p_{i}/q_{i})\). We can interpret the computations performed by the algorithm as an equivalent two-step OMD process: First, we predict \[p_{t} = \mathop{\mathrm{argmin}}_{p \in \Delta_N}\{ \langle M_{t} , p \rangle + \frac{1}{\varepsilon}D_{\psi}(p, w_{t}) \}\] and then update \(w_{t+1}= \mathop{\mathrm{argmin}}_{w \in \Delta_N}\{ \langle \ell_{t}, w \rangle + \frac{1}{\varepsilon} D_{\psi}(w, w_{t}) \}\).

The regret of the optimistic meta-algorithm at time \(t\) is given by \(\langle p_{t} - e_{i^\star},\ell_{t} \rangle\), where \(e_{i^\star} \in \Delta_{N}\) is the standard basis vector corresponding to expert \(i^\star\). We can decompose the meta regret as: \[\langle \ell_{t}, p_{t} - e_{i^\star} \rangle = \langle \ell_{t}, p_{t} - w_{t+1}\rangle + \langle \ell_{t}, w_{t+1}- e_{i^\star} \rangle.\] The optimality condition for \(w_{t+1}\) leads to \[\langle \ell_{t}, w_{t+1}- e_{i^\star} \rangle \le \frac{1}{\varepsilon}(D_{\psi}(e_{i^\star}, w_{t}) - D_{\psi}(e_{i^\star}, w_{t+1}) - D_{\psi}(w_{t+1}, w_{t})).\] Plugging this term into the decomposition allow us to conclude that \[\langle p_{t} - e_{i^\star}, \ell_{t} \rangle \le \frac{D_{\psi}(e_{i^\star}, w_{t}) - D_{\psi}(e_{i^\star}, w_{t+1})}{\varepsilon}+ \langle p_{t} - w_{t+1}, \ell_{t} - M_{t} \rangle + \langle p_{t} - w_{t+1}, M_{t} \rangle - \frac{1}{\varepsilon}D_{\psi}( w_{t+1}, w_{t}).\] Similarly, the optimality condition for the prediction \(p_{t}\) gives \[\langle p_{t} - w_{t+1}, M_{t} \rangle \le \frac{1}{\varepsilon}(D_{\psi}(w_{t+1}, w_{t}) - D _{\psi}(w_{t+1}, p_{t}) - D_{\psi}(p_{t}, w_{t})).\] Then, by canceling \(\frac{1}{\varepsilon}D_{\psi}(w_{t+1}, w_{t})\) and dropping the non-positive term \(-\frac{1}{\varepsilon}D_{\psi}(p_{t}, w_{t})\) we have \[\langle p_{t} - e_{i^\star}, \ell_{t} \rangle \le \frac{D_{\psi}(e_{i^\star}, w_{t}) - D_{\psi}(e_{i^\star}, w_{t+1})}{\varepsilon}+ \langle p_{t} - w_{t+1}, \ell_{t} - M_{t} \rangle - \frac{1}{\varepsilon}D_{\psi}(w_{t+1}, p_{t}).\] Next, we bound the two terms \[\langle p_{t} - w_{t+1}, \ell_{t} - M_{t} \rangle - \frac{1}{\varepsilon}D_{\psi}(w_{t+1}, p_{t}).\]

The regularizer \(\psi\) is \(1\)-strongly convex with respect to the \(\ell_{1}\)-norm on the simplex and by Pinsker’s inequality (Lemma 1), we have \[D_{\psi}(w_{t+1}, p_{t}) \ge \frac{1}{2}\|w_{t+1}- p_{t}\|_{1}^{2}.\] By Holder’s inequality, we have: \[\langle p_{t} - w_{t+1}, \ell_{t} - M_{t} \rangle \le \|p_{t} - w_{t+1}\|_{1} \|\ell_{t} - M_{t}\|_{\infty}.\] Using the Young’s inequality \(ab \le \frac{a^{2}}{2\lambda}+ \frac{\lambda b^{2}}{2}\) with \(a=\|p_{t} - w_{t+1}\|_{1}\), \(b=\|\ell_{t} - M_{t}\|_{\infty}\), and \(\lambda = \varepsilon\), we obtain: \[\langle p_{t} - w_{t+1}, \ell_{t} - M_{t} \rangle \le \frac{1}{2\varepsilon} \|p_{t} - w_{t+1}\|_{1}^{2} + \frac{\varepsilon}{2}\|\ell_{t} - M_{t}\|_{\infty} ^{2}.\] Substituting this inequality for \(\langle p_{t}-w_{t+1},\ell_{t}-M_{t}\rangle\) into the decomposition of the regret yields the following by canceling the non-positive term \(\frac{1}{2\varepsilon}\|p_{t} - w_{t+1}\|_{1}^{2}\) as: \[\langle p_{t} - u, \ell_{t} \rangle \le \frac{D_{\psi}(u, w_{t}) - D_{\psi}(u, w_{t+1})}{\varepsilon}+ \frac{\varepsilon}{2} \|\ell_{t} - M_{t}\|_{\infty}^{2}.\] When sum over \(t=1,\dots,T\), the first term gives rise to a telescoping sum: \[\frac{1}{\varepsilon}(D_{\psi}(u, w_{1}) - D_{\psi}(u, w_{T+1})) \le \frac{D_{\psi}(u, w_{1})}{\varepsilon}.\]

Since \(D_{\psi}(e_{i^\star}, w_{1}) = \ln(1/w_{1,i^\star})\), we establish the first inequality of the lemma, where \(\langle \ell_{t}, p_{t} - e_{i^\star} \rangle=\langle p_{t}, \ell_{t} \rangle - \ell_{t,i^\star}\).

Next, we further bound \(\|\ell_{t} - M_{t}\|_{\infty}^{2}\). By definition, \[\ell_{t,i}= \langle \hat{g}_{t}, y_{t,i}\rangle, \qquad M_{t,i}= \langle m_{t}, y_{t,i}\rangle.\]

The \(\ell_{\infty}\)-norm is therefore \(\|\ell_{t}-M_{t}\|_{\infty} = \max_{i}|\langle \hat{g}_{t}-m_{t}, y_{t,i}\rangle|\). Using Cauchy-Schwarz inequality gives \(|\langle \hat{g}_{t}-m_{t},y_{t,i}\rangle| \le \|\hat{g}_{t}-m_{t}\|_{2}\|y_{t,i}\|_{2}\). Since \(0 \in \mathcal{X}_{\alpha}\) and all the expert instances \(y_{t,i}\) lies in \(\mathcal{X}_{\alpha}\), thus \(\|y_{t,i}\|_{2} \le D\) for all \(i\). We see consequently that for all time horizons \(t\), \(\|\ell_{t}-M_{t}\|_{\infty} \le D\|\hat{g}_{t}-m_{t}\|_{2}\). Therefore, by squaring our result, we have \(\|\ell_{t} - M_{t}\|_{\infty}^{2} \le D^{2}\|\hat{g}_{t}-m_{t}\|_{2}^{2}\). These complete the proof. ◻

Lemma 20 (Meta-Expert Epoch Regret). Fix an epoch \((k,e)\), where we write \(J_{k,e}\) to denote the time interval associated with an epoch, according to the Meta-Expert algorithm in Algorithm 4. Let \(R_{k,e} = \sum_{t \in J_{k,e}} \|\hat{g}_t - m_t\|^2\) be the total prediction error for that epoch. We also introduce \(P_{k,e}\) as the length of the epoch path and denote the sensitivity budget for this epoch by \(S_{k,e}\). The expected dynamic epoch regret can be bounded as follows: \[\begin{align} \mathbb{E}\bigl[\mathfrak{R}^{\mathrm{dyn}}(J_{k,e})\bigr] &\le 4 D \sqrt{8d S_{k,e} \ln N} + \frac{3}{\sqrt{2}}\sqrt{R_{k,e}^{\circ}\cdot(D^2 + 2D P_{k,e})} \\&+ 3D+\frac{D}{2}\sqrt{S_{k,e}}+\left(L+\frac{LD}{r}\right)\frac{\sqrt{S_{k,e}}}{d\beta}+LD. \end{align}\]

Proof. The proof follows from Lemma 12. If the epoch terminates because the phase time budget is reached, define \(O_{k,e}=\emptyset, J_{k,e}^{\circ}=J_{k,e}\). Thus \(O_{k,e}\) contains at most one round, and \(J_{k,e}^{\circ}\) is the good prefix of the epoch. Define the good-prefix observable residual as \(R_{k,e}^{\circ}=\sum_{t\in J_{k,e}^{\circ}}\|\hat{g}_t-m_t\|^2\). We decompose as follows: \[\mathfrak{R}^{\mathrm{dyn}}_{T}(J_{k,e})=\mathfrak{R}^{\mathrm{dyn}}_{T}(J_{k,e}^{\circ})+\mathfrak{R}^{\mathrm{dyn}}_{T}(O_{k,e}).\]

The \(\mathfrak{R}^{\mathrm{dyn}}_{T}(O_{k,e})\) part can be bounded as \[\mathfrak{R}^{\mathrm{dyn}}_{T}(O_{k,e})\leq LD.\] Then, we consider the \(\mathfrak{R}^{\mathrm{dyn}}_{T}(J_{k,e}^{\circ})\) part as follows: \[\mathfrak{R}^{\mathrm{dyn}}_{T}(J_{k,e}^{\circ}) \le\sum_{t \in J_{k,e}^{\circ}} \langle \hat{g}_t, y_t - u'_t \rangle+ \Bigl(\frac{Dd\beta}{2}+L+\frac{LD}{r}\Bigr)\delta |J_{k,e}^{\circ}|.\] The choice of \(\delta\) that is selected for TP-VR-Opt++ is identical to the that selected for TP-VR-Opt+, and thus we have: \[\Bigl(\frac{Dd\beta}{2}+L+\frac{LD}{r}\Bigr)\delta |J_{k,e}^{\circ}|\leq \frac{D}{2}\sqrt{S_{k,e}}+\left(L+\frac{LD}{r}\right)\frac{\sqrt{S_{k,e}}}{d\beta}\]

Using the general form of \(\ell_t(y_t)=\langle \hat{g}_t, y_t\rangle\) for use in TP-VR-Opt++, we can further decompose the \(\sum_{t \in J_{k,e}^{\circ}} \langle \hat{g}_t, y_t - u'_t \rangle\) term into Meta-Regret (A) and Best Expert Regret (B): \[\sum_{t \in J_{k,e}^{\circ}} \langle \hat{g}_t, y_t - u'_t \rangle = \underbrace{\sum_{t \in J_{k,e}^{\circ}} (\ell_t(y_t) - \ell_t(y_{t, i^\star}))}_{\text{(A)}} + \underbrace{\sum_{t \in J_{k,e}^{\circ}} (\ell_t(y_{t, i^\star}) - \ell_t(u'_t))}_{\text{(B)}},\] where \(i^\star\) is the index of the best expert in the grid.

Term (A) Meta Regret: The algorithm uses the prior \(w_{1,i} \propto \frac{1}{i(i+1)}\) and step size \(\varepsilon=\frac{\sqrt{\ln N}}{D\sqrt{V_{\max}}}\), where \(V_{\max}=8dS_{k,e}\). For any expert \(i^\star \le N\), we know that the prior satisfies \(\ln(1/w_{1,i^\star}) \le 2\ln(N+1)\). As a consequence, by applying the bound given as Lemma 19, we have: \[\text{Term (A)} \le \frac{2\ln(N+1)}{\varepsilon} + \frac{\varepsilon}{2} D^2 R_{k,e}^{\circ}.\] Substituting \(\varepsilon = \frac{\sqrt{\ln N}}{D\sqrt{V_{\max}}}\): \[\begin{align} \text{Term (A)} &= \frac{2\ln(N+1) D \sqrt{V_{\max}}}{\sqrt{\ln N}} + \frac{\sqrt{\ln N}}{2 D \sqrt{V_{\max}}} D^2 R_{k,e}^{\circ} \\&= D \sqrt{V_{\max}} \left( \frac{2\ln(N+1)}{\sqrt{\ln N}} + \frac{R_{k,e}^{\circ} \sqrt{\ln N}}{2 V_{\max}} \right). \end{align}\]

We also note that epochs terminate if the accumulated error is greater than \(8dS_{k,e}\). As demonstrated in Lemma 11, we have \[R_{k,e}^{\circ} \le 8dS_{k,e} = V_{\max}.\] Thus, the fraction \(\frac{R_{k,e}^{\circ}}{V_{\max}} \le 1\). Furthermore, since \(N \ge 2\), \(\ln(N+1)\le 1.6\ln N\), therefore \(\frac{2\ln(N+1)}{\sqrt{\ln N}}\le 3.2\sqrt{\ln N}\). Thus, we combine these: \[\text{Term (A)} \le D \sqrt{V_{\max}} \left( 3.2\sqrt{\ln N} + 0.5\sqrt{\ln N} \right) = 4 D \sqrt{V_{\max} \ln N}.\] Finally, by the definition of \(V_{\max}\), we know: \[\text{Term (A)} \le 4 D \sqrt{8dS_{k,e} \ln N}.\]

Term (B) Expert Regret: Let \(A_{k,e}=D^{2}+2DP_{k,e}\). By Lemma 18, we can bound the regret of any specific expert \(i\) by \(R_{i}(\eta_{i})\le\frac{A_{k,e}}{2\eta_{i}}+\eta_{i}R_{k,e}^{\circ}\). The optimal step size is defined by \(\eta^{\star}=\sqrt{\frac{A_{k,e}}{2R_{k,e}}}\).

Let us analyze cases, but first verify that our grid indicates that we have covered the region for the optimal step size from below. We have seen that the termination conditions of epochs are governed by the alteration schedule being sufficient to exceed the error budget, that is \(R_{k,e}^{\circ}\le V_{\max}\). Thus, we can also observe that \(A_{k,e}\ge D^{2}\), which implies that the optimal step size is lower-bounded by: \[\eta^\star = \sqrt{\frac{A_{k,e}}{2R_{k,e}^{\circ}}} \ge \sqrt{\frac{D^2}{2 V_{\max}}} = \eta_0.\] Therefore, we can begin by analyzing two cases based on the upper bound of our grid \(\eta_{\max}\).

Case 1 (Inside Grid Range, \(\eta_0 \le \eta^\star \le \eta_{\max}\)): As the grid is geometric with ratio 2, \(\eta_{i}=\eta_{0}2^{i-1}\), we know that there exists an expert \(i^\star \in \{1,\ldots,N\}\) such that \(\eta_{i^\star}\le\eta^{\star}\le2\eta_{i^\star}\). For this specific expert, we have that: \[\text{Term (B)} \le \frac{A_{k,e}}{2\eta_{i^\star}} + \eta_{i^\star} R_{k,e}^{\circ} \le \frac{A_{k,e}}{2(\eta^\star/2)} + \eta^\star R_{k,e}^{\circ} = \frac{A_{k,e}}{\eta^\star} + \eta^\star R_{k,e}^{\circ}.\] Substituting \(\eta^\star = \sqrt{\frac{A_{k,e}}{2R_{k,e}^{\circ}}}\) gives: \[\text{Term (B)} \le \sqrt{2 A_{k,e} R_{k,e}^{\circ}} + \sqrt{\frac{A_{k,e} R_{k,e}^{\circ}}{2}} = \left(\sqrt{2} + \frac{1}{\sqrt{2}}\right)\sqrt{A_{k,e} R_{k,e}^{\circ}} = \frac{3}{\sqrt{2}}\sqrt{A_{k,e} R_{k,e}^{\circ}}.\]
Case 2 (Exceeds Grid Range, \(\eta^\star > \eta_{\max}\)): The condition \(\eta^{\star}>\eta_{\max}\) indicates \(\sqrt{\frac{A_{k,e}}{2R_{k,e}^{\circ}}} > \eta_{\max}\), which implies \(R_{k,e}^{\circ} < \frac{A_{k,e}}{2\eta_{\max}^2}\). In this case, we consider the largest expert \(i=N\) having step size \(\eta_{\max}\). Term (B) for this expert becomes: \[\text{Term (B)} \le \frac{A_{k,e}}{2\eta_{\max}} + \eta_{\max} R_{k,e}^{\circ} < \frac{A_{k,e}}{2\eta_{\max}} + \eta_{\max} \left( \frac{A_{k,e}}{2\eta_{\max}^2} \right) = \frac{A_{k,e}}{\eta_{\max}}.\] We now utilize our specific choice of \(N = \lceil \log_2(DH/\eta_0) \rceil + 1\). This construction guarantees: \[\eta_{\max} = \eta_0 2^{N-1} \ge \eta_0 2^{\log_2(DH/\eta_0)} = DH.\] Given that \(H\) can be thought of as representing the total number of steps associated with the worst-case charging of the path length, then we have that \(P_{k,e}\leq HD\). Combining this with the fact that \(\eta_{\max}\ge H\), we have: \[\text{Term (B)} < \frac{D^2 + 2D P_{k,e}}{DH} \le \frac{D^2 + 2D(HD)}{DH} = \frac{D}{H} + 2D \le 3D.\]

Combining the two components gives us our overall regret, therefore completing the proof. ◻

Lemma 21 (Phase Regret Aggregation). Let \(k\) be the phase, and \(I_k\) be the corresponding round sequence, which can be partitioned into \(J_{k,1}, J_{k,2}, \dots , J_{k,E_k}\) through the doubling condition of the prediction-sensitivity budget being given by \(S_{k,e}=S_{\min}\cdot2^{e-1}\) with \(e=1,2,\dotsc,E_k\). The phase-wise cumulative expected prediction error is denoted as \(\bar S_k\), and the total path length taken by phase \(k\) is denoted as \(P_k\). The expected dynamic regret for phase \(k\) is bounded by:

\[\mathbb{E}\left[\mathfrak{R}^{\mathrm{dyn}}(I_k)\right] \le\widetilde{O}\!\left(\sqrt{d\bar S_k\,(D^2 + D P_k)}\right).\]

Proof. Let the epochs be collected into \(I_k\), and thus we have a summation over the different path elements: \[\mathfrak{R}^{\mathrm{dyn}}(I_k) = \sum_{e=1}^{E_k} \mathfrak{R}^{\mathrm{dyn}}(J_{k,e}).\] Using Lemma 20, we can write: \[\begin{align} \sum_{e=1}^{E_k} \mathbb{E}[\mathfrak{R}^{\mathrm{dyn}}(J_{k,e})] &\le \mathbb{E}\Bigl[\sum_{e=1}^{E_k} \underbrace{4 D \sqrt{V_{k,e} \ln N}}_{\text{Term (A)}} + \underbrace{\frac{3}{\sqrt{2}}\sqrt{R_{k,e}^{\circ} (D^2 + 2D P_{k,e})}}_{\text{Term (B)}}\Bigr] \\&+ \underbrace{(3D+LD)E_k}_{\text{Term (C)}}+ \mathbb{E}\Bigl[\underbrace{\frac{D}{2}\sqrt{S_{k,e}}+\left(L+\frac{LD}{r}\right)\frac{\sqrt{S_{k,e}}}{d\beta}}_{\text{Term (D)}} \Bigr], \end{align}\] where we denote \(V_{k,e} = 8d S_{k,e}\).

For Term (A): Using Lemma 13, we have \(\sum_{e=1}^{E_k}\sqrt{S_{k,e}}\leq 4\sqrt{S_{k,E_k}}\), thus we obtain: \[\sum_{e=1}^{E_k} 4 D \sqrt{V_{k,e} \ln N}\le 16 D \sqrt{8d S_{k,E_k} \ln N}.\]

For Term (B): Denote \(A_{k,e}=D^2 + 2D P_{k,e}\). By Cauchy–Schwarz, we have \[\begin{align} \sum_{e=1}^{E_k} \sqrt{A_{k,e}R_{k,e}^{\circ}} &\le \sqrt{ \sum_{e=1}^{E_k}A_{k,e} } \sqrt{ \sum_{e=1}^{E_k}R_{k,e}^{\circ} }. \end{align}\] We first bound the path-length factor. Therefore, we have \[\begin{align} \sum_{e=1}^{E_k}A_{k,e}= \sum_{e=1}^{E_k}(D^2+2DP_{k,e})= E_kD^2+2D\sum_{e=1}^{E_k}P_{k,e}. \end{align}\] The sum of the epoch path-lengths is at most the phase path-length, i.e., \(\sum_{e=1}^{E_k}P_{k,e}\le P_k\). Moreover, \(E_k\) is logarithmic in the phase length and sensitivity range, and therefore it is absorbed by \(\widetilde{O}(\cdot)\). Hence, pathwise, \[\sum_{e=1}^{E_k}A_{k,e} \le \widetilde{O}(D^2+DP_k).\] For the residual factor, since \(J_{k,e}^{\circ}\subseteq J_{k,e}\), we have \[\sum_{e=1}^{E_k}R_{k,e}^{\circ} \le \sum_{e=1}^{E_k} \sum_{t\in J_{k,e}}\|\hat{g}_t-m_t\|^2 = R_k^{\mathrm{obs}}.\] Combining these estimates yields \[\begin{align} \sum_{e=1}^{E_k} \sqrt{A_{k,e}R_{k,e}^{\circ}} &\le \widetilde{O}\left( \sqrt{(D^2+DP_k)R_k^{\mathrm{obs}}} \right). \end{align}\] Taking expectation and applying Jensen’s inequality to the concave function \(\sqrt{x}\) gives \[\begin{align} \mathbb{E}\left[ \sum_{e=1}^{E_k} \sqrt{A_{k,e}R_{k,e}^{\circ}} \right] &\le \widetilde{O}\left( \sqrt{ (D^2+DP_k)\, \mathbb{E}[R_k^{\mathrm{obs}}] } \right). \end{align}\] By Lemma 15, we have \[\mathbb{E}[R_k^{\mathrm{obs}}] \le \frac{64}{7}d\bar S_k + \frac{72}{7}\frac{S_{\min}}{H_k}.\] Therefore, it follows that \[\begin{align} \mathbb{E}\left[ \sum_{e=1}^{E_k} \sqrt{A_{k,e}R_{k,e}^{\circ}} \right] &\le \widetilde{O}\left( \sqrt{ (D^2+DP_k) \left( d\bar S_k+\frac{S_{\min}}{H_k} \right) } \right) \\ &\le \widetilde{O}\left( \sqrt{d\bar S_k(D^2+DP_k)} + \sqrt{ \frac{S_{\min}}{H_k}(D^2+DP_k) } \right). \end{align}\]

It remains to simplify the second term. Since all comparators lie in \(\mathcal{X}\), whose diameter is at most \(D\), the movement in one round is at most \(D\). Since phase \(k\) has length at most \(H_k\), we have \(P_k\le DH_k\). Thus, we have \[\begin{align} \sqrt{ \frac{S_{\min}}{H_k}(D^2+DP_k) } &\le \sqrt{ \frac{S_{\min}}{H_k}(D^2+D^2H_k) } \\ &= D\sqrt{ S_{\min}\left(\frac{1}{H_k}+1\right) } \\ &\le \sqrt2\,D\sqrt{S_{\min}}. \end{align}\] Since \(d\ge1\), this is bounded by \(\sqrt2\,D\sqrt{dS_{\min}}\). Therefore the best-expert contribution is also bounded by \[\widetilde{O}\left( \sqrt{d\bar S_k(D^2+DP_k)} + D\sqrt{dS_{\min}} \right).\]

For Term (D): From above and using \(\sum_{e=1}^{E_k} \sqrt{S_{k,e}} \le 4\sqrt{S_{k,E_k}}\), we have \[\sum_{e=1}^{E_k} \frac{D}{2}\sqrt{S_{k,e}}+\left(L+\frac{LD}{r}\right)\frac{\sqrt{S_{k,e}}}{d\beta} \le \widetilde{O}\left( D\sqrt{S_{k,E_k}}\right).\]

Combining Terms (A), (B), (C) and (D), and noting that terms with \(E_k\leq O(\log T)\) are absorbed into \(\widetilde{O}\), we have: \[\mathbb{E}\bigl[\mathfrak{R}^{\mathrm{dyn}}(I_k)\bigr] \le \widetilde{O}\left( \sqrt{d\mathbb{E}[S_{k,E_k}] (D^2 + D P_k)}\right).\] Substituting the condition \(\mathbb{E}[S_{k,E_k}] = O(\bar{S}_k + S_{\min})\) as shown in Lemma 16, the dominant term becomes: \[\mathbb{E}\bigl[\mathfrak{R}^{\mathrm{dyn}}(I_k)\bigr] \le \widetilde{O}\left( \sqrt{d\bar{S}_k (D^2 + D P_k)} \right).\] ◻

10.2 Proof of Theorem 9 ↩︎

Proof. The regret of the \(t\)-th round can be expressed using the following decomposition: \[f_{t}(x_{t})-f_{t}(u_{t}) =\underbrace{f_t(x_t)-f_t(y_t)}_{\text{Term (A)}} +\underbrace{f_t(y_t)-f_t(u'_t)}_{\text{Term (B)}}+\underbrace{f_t(u'_t)-f_t(u_t)} _{\text{Term (C)}}.\] The Terms (A) and (C) can be bounded using the \(L\)-Lipschitz property of the function \(f_{t}\), as described below:

For (A): Since \(x_{t} = y_{t} + \delta v_{t}\) with \(\|v_{t}\|_{2}=1\), we have \(\|x_{t}-y_{t}\|_{2} = \delta\), implying \(f_{t}(x_{t})-f_{t}(y_{t}) \le L\delta\).
For (C): Since \(u'_{t} = (1-\alpha)u_{t}\) with \(\alpha = \delta/r\), we have \(\|u'_{t}-u_{t}\|_{2} = \alpha\|u_{t}\|_{2} \le \alpha D = \frac{D}{r} \delta\). Thus, \(f_{t}(u'_{t})-f_{t}(u_{t}) \le \frac{LD}{r}\delta\).

Summing over all rounds \(t=1,\dotsc,T\), we have: \[\mathfrak{R}^{\mathrm{dyn}}_{T}(u_{1:T}) \le\sum_{t=1}^{T} \bigl(f_{t}(y_{t})- f_{t}(u'_{t})\bigr)+ \Bigl(L+\frac{LD}{r}\Bigr)\delta T.\]

Let \(g_{t}^{y} = \nabla f_{t}(y_{t})\). By the convexity of \(f_{t}\), \[f_{t}(y_{t})-f_{t}(u'_{t}) \le \langle g_{t}^{y},\, y_{t}-u'_{t} \rangle.\] Thus, we can rewrite our expression for regret given as: \[\mathfrak{R}^{\mathrm{dyn}}_{T}(u_{1:T}) \le\sum_{t=1}^{T} \langle g_{t}^{y},\, y_{t}-u'_{t} \rangle +\Bigl(L+\frac{LD}{r}\Bigr)\delta T.\]

We also know that: \[\langle g_{t}^{y},\, y_{t}-u'_{t} \rangle =\langle \hat{g}_{t},\, y_{t}-u' _{t} \rangle +\langle g_{t}^{y}-\hat{g}_{t},\, y_{t}-u'_{t} \rangle.\] For the first term on the right-hand side, we can use Lemma 17 to apply the bound.

For the second term, we apply Lemma 5. Recall that \(\mathbb{E}[\hat{g}_{t} \mid \mathcal{H}_{t-1}] = g_{t}^{y} + b_{t}\) with \(\|b_{t}\|_{2} \le \frac{d}{2} \beta\delta\). Taking an expectation of both sides gives: \[\mathbb{E}\Bigl[\langle g_{t}^{y}-\hat{g}_{t},\, y_{t}-u'_{t} \rangle\Bigr] = \mathbb{E}\Bigl[\langle -b_{t},\, y_{t}-u'_{t} \rangle\Bigr] \le \mathbb{E} \Bigl[\|b_{t}\|_{2} \|y_{t}-u'_{t}\|_{2}\Bigr] \le \frac{Dd\beta\delta}{2},\] where we used \(\|y_{t}-u'_{t}\|_{2} \le D\). To obtain the total contribution of this term, we sum over all rounds \(t\): \[\mathbb{E}\left[\sum_{t=1}^{T} \langle g_{t}^{y}-\hat{g}_{t},\, y_{t}-u'_{t} \rangle\right] \;\le\; \frac{Dd\beta\delta T}{2}. \label{eq:dyn95bias95term}\tag{23}\]

Therefore, we have \[\mathbb{E}[\mathfrak{R}^{\mathrm{dyn}}_{T}] \le\frac{D^{2}+2DP_{T}}{2\eta}+\eta \sum_{t=1}^{T} \mathbb{E}\|\hat{g}_{t}-m_{t}\|_{2}^{2} +\frac{Dd\beta\delta T}{2}+\Bigl(L+\frac{LD}{r}\Bigr)\delta T.\] Finally, we can bound \(\sum_{t=1}^{T}\mathbb{E}\|\hat{g}_{t}-m_{t}\|^{2}\) using Corollary 3. Plugging in the bound derived from the second moment expression gives us the main result: \[\begin{align} \mathbb{E}\bigl[\mathfrak{R}^{\mathrm{dyn}}_{T}(u_{1:T})\bigr] \le \frac{D^{2}+ 2D P_{T}}{2\eta}+\eta \Bigl( 4d\,\bar{S}_{T}+ (d^{2}/2 + 4d)\beta^{2}\delta^{2}T \Bigr) \nonumber+\frac{D d \beta \delta T}{2}+ \Bigl( L + \frac{LD}{r}\Bigr) \delta T. \end{align}\]

By applying bounds on \(\eta\) and \(\delta\) suitably chosen as in Theorem 9, we obtain our final bound on the regret. ◻

10.3 Proof of Theorem 10 ↩︎

Proof. We divide the total time horizon into \(K\) phases \(\{I_1,I_2,\ldots,I_K\}\). The expected dynamic regret is equal to the sum of the expected dynamic regrets in all \(K\) phases. Let \(\mathfrak{R}_k = \mathbb{E}\big[\mathfrak{R}^{\mathrm{dyn}}(I_k)\big]\). By using the linearity of expectation, we have:

\[\mathbb{E}\bigl[\mathfrak{R}_T^{\mathrm{dyn}}(u_{1:T})\bigr] = \sum_{k=1}^K \mathfrak{R}_k.\] From Lemma 21, we know the following for phase \(k\): \[\mathfrak{R}_k \le C \left(\sqrt{d\bar{S}_k(D^2 + D P_k)}\right) \cdot \text{polylog}(T),\] where \(C\) is a universal constant, \(\bar{S}_k = \mathbb{E}[\sum_{t \in I_k} \|\nabla f_t(x_t) - m_t\|^2]\) is the cumulative prediction error in phase \(k\), and \(P_k\) is the path-length of the comparator in phase \(k\).

Further, we can write: \[\begin{align} \sum_{k=1}^K \mathfrak{R}_k &\le \widetilde{O}(1) \sum_{k=1}^K \sqrt{d\bar{S}_k(D^2 + D P_k)} \\ &\le \widetilde{O}(1) \sqrt{\sum_{k=1}^K d\bar{S}_k} \cdot \sqrt{\sum_{k=1}^K (D^2 + D P_k)}. \end{align}\]

In \(\sum_{k=1}^K d\bar{S}_k\), we can replace the cumulative prediction errors with the overall prediction error \(\bar{S}_T\), and all constant terms sum to \(Kd^2\). Therefore, \[\sum_{k=1}^K d\bar{S}_k = d\bar{S}_T.\] Similarly, we see that the path lengths are additive across non-overlapping intervals, therefore \(\sum_{k=1}^K P_k = P_T\), and the \(K\) terms from the diameter squared sum to \(K D^2\): \[\sum_{k=1}^K (D^2 + D P_k) = K D^2 + D P_T \le O(D^2 \log T + D P_T).\]

We substitute the results back into the inequality to arrive at the following: \[\begin{align} \mathbb{E}\bigl[\mathfrak{R}_T^{\mathrm{dyn}}(u_{1:T})\bigr] &\le \widetilde{O}\left( \sqrt{d\bar{S}_T (\log T \cdot D^2 + D P_T)} \right). \end{align}\] We simplify the expression to the leading order term: \[\mathbb{E}\bigl[\mathfrak{R}_T^{\mathrm{dyn}}(u_{1:T})\bigr] \le \widetilde{O}\left( \sqrt{d \bar{S}_T (D^2 + D P_T)} \right).\] ◻

References↩︎

[1]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games.Cambridge University Press, 2006.

[2]

E. Hazan, “Introduction to online convex optimization,” Foundations and Trends in Optimization, vol. 2, no. 3-4, pp. 157–325, 2016.

[3]

F. Orabona, “A modern introduction to online learning,” arXiv preprint arXiv:1912.13213, 2019.

[4]

N. Cesa-Bianchi, A. Conconi, and C. Gentile, “On the generalization ability of on-line learning algorithms,” IEEE Transactions on Information Theory, vol. 50, no. 9, pp. 2050–2057, 2004.

[5]

A. D. Flaxman, A. T. Kalai, and H. B. McMahan, “Online convex optimization in the bandit setting: Gradient descent without a gradient,” arXiv preprint cs/0408007, 2004.

[6]

T. Lattimore, “Bandit convex optimisation,” arXiv preprint arXiv:2402.06535, 2024.

[7]

O. Shamir, “An optimal algorithm for bandit and zero-order convex optimization with two-point feedback,” Journal of Machine Learning Research, vol. 18, no. 52, pp. 1–11, 2017.

[8]

A. Saha and A. Tewari, “Improved regret guarantees for online smooth convex optimization with bandit feedback,” in Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, 2011, pp. 636–642.

[9]

C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu, “Online optimization with gradual variations,” in Proceedings of the Annual Conference on Learning Theory, 2012, pp. 6–1.

[10]

P. Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou, “Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization,” Journal of Machine Learning Research, vol. 25, no. 98, pp. 1–52, 2024.

[11]

A. Rakhlin and K. Sridharan, “Online learning with predictable sequences,” in Proceedings of the Annual Conference on Learning Theory, 2013, pp. 993–1019.

[12]

J. Steinhardt and P. Liang, “Adaptivity and optimism: An improved exponentiated gradient algorithm,” in Proceedings of the International Conference on Machine Learning, 2014, pp. 1593–1601.

[13]

P. Zhao, G. Wang, L. Zhang, and Z.-H. Zhou, “Bandit convex optimization in non-stationary environments,” Journal of Machine Learning Research, vol. 22, no. 125, pp. 1–45, 2021.

[14]

C. He, B. Jiang, and S. Zhang, “Non-stationary bandit convex optimization: An optimal algorithm with two-point feedback,” arXiv preprint arXiv:2508.04654, 2025.

[15]

A. Agarwal, O. Dekel, and L. Xiao, “Optimal algorithms for online convex optimization with multi-point bandit feedback,” in Proceedings of the Annual Conference on Learning Theory, 2010, pp. 28–40.

[16]

E. Hazan and K. Levy, “Bandit convex optimization: Towards tight bounds,” Advances in Neural Information Processing Systems, vol. 27, 2014.

[17]

S. Bubeck, O. Dekel, T. Koren, and Y. Peres, “Bandit convex optimization: \(\sqrt{T}\) regret in one dimension,” in Proceedings of the Annual Conference on Learning Theory, 2015, pp. 266–278.

[18]

S. Bubeck, R. Eldan, and Y. T. Lee, “Kernel-based methods for bandit convex optimization,” Journal of the ACM, vol. 68, no. 4, pp. 1–35, 2021.

[19]

T. Lattimore, “Improved regret for zeroth-order adversarial bandit convex optimisation,” Mathematical Statistics and Learning, vol. 2, no. 3, pp. 311–334, 2020.

[20]

O. Shamir, “On the complexity of bandit and derivative-free stochastic convex optimization,” in Proceedings of the Annual Conference on Learning Theory, 2013, pp. 3–24.

[21]

X. Hu, L. A. Prashanth, A. György, and C. Szepesvári, “Bandit convex optimization with biased noisy gradient oracles,” in Proceedings of the International Conference on Artificial Intelligence and Statistics, 2016, pp. 819–828.

[22]

S. Rakhlin and K. Sridharan, “Optimization, learning, and games with predictable sequences,” Advances in Neural Information Processing Systems, vol. 26, 2013.

[23]

O. Dekel, A. Flajolet, N. Haghtalab, and P. Jaillet, “Online learning with a hint,” Advances in Neural Information Processing Systems, vol. 30, 2017.

[24]

A. Bhaskara, A. Cutkosky, R. Kumar, and M. Purohit, “Online learning with imperfect hints,” in Proceedings of the International Conference on Machine Learning, 2020, pp. 822–831.

[25]

S. Sachs, H. Hadiji, T. van Erven, and C. Guzman, “Accelerated rates between stochastic and adversarial online convex optimization,” arXiv preprint arXiv:2303.03272, 2023.

[26]

S. Yang and M. Mohri, “Optimistic bandit convex optimization,” Advances in Neural Information Processing Systems, vol. 29, 2016.

[27]

C.-K. Chiang, C.-J. Lee, and C.-J. Lu, “Beating bandits in gradually evolving worlds,” in Proceedings of the Annual Conference on Learning Theory, 2013, pp. 210–227.

[28]

C.-Y. Wei and H. Luo, “More adaptive algorithms for adversarial bandits,” in Proceedings of the Annual Conference on Learning Theory, 2018, pp. 1263–1291.

[29]

C.-Y. Wei, H. Luo, and A. Agarwal, “Taking a hint: How to leverage loss predictors in contextual bandits?” in Proceedings of the Annual Conference on Learning Theory, 2020, pp. 3583–3634.

[30]

C. Wu, M. Heidari, A. Grama, and W. Szpankowski, “Regret bounds for log-loss via bayesian algorithms,” IEEE Transactions on Information Theory, vol. 69, no. 9, pp. 5971–5989, 2023.

[31]

F. Orabona and K.-S. Jun, “Tight concentrations and confidence sequences from the regret of universal portfolio,” IEEE Transactions on Information Theory, vol. 70, no. 1, pp. 436–455, 2023.

[32]

M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in Proceedings of the 20th International Conference on Machine Learning, 2003, pp. 928–936.

[33]

A. György and C. Szepesvári, “Shifting regret, mirror descent, and matrices,” in Proceedings of the International Conference on Machine Learning, 2016, pp. 2943–2951.

[34]

M. Zhang, P. Zhao, H. Luo, and Z.-H. Zhou, “No-regret learning in time-varying zero-sum games,” in Proceedings of the International Conference on Machine Learning, 2022, pp. 26 772–26 808.

[35]

L. Zhang, S. Lu, and Z.-H. Zhou, “Adaptive online learning in dynamic environments,” Advances in Neural Information Processing Systems, vol. 31, 2018.

[36]

A. György, T. Linder, and G. Lugosi, “Efficient tracking of large classes of experts,” IEEE Transactions on Information Theory, vol. 58, no. 11, pp. 6709–6725, 2012.

[37]

H. Yu, Y.-H. Yan, and P. Zhao, “Improved dimension dependence for bandit convex optimization with gradient variations,” arXiv preprint arXiv:2602.04761, 2026.

[38]

L. Lyu and W. C. Cheung, “Online resource allocation: Bandits feedback and advice on time-varying demands,” arXiv preprint arXiv:2302.04182, 2023.

[39]

A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright, “Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization,” IEEE Transactions on Information Theory, vol. 58, no. 5, pp. 3235–3249, 2012.

Bandit Convex Optimization with Gradient Prediction Adaptivity

Abstract

1 Introduction↩︎

1.1 Main Contributions↩︎

2 Problem Setup and Preliminaries↩︎

3 The Single-Point Feedback Barrier↩︎

4 Two-Point Feedback: Prediction-sensitive Variance Reduction↩︎

4.1 The TP-VR-Opt Algorithm↩︎

4.2 Connection to Gradually Evolving Worlds [27]↩︎

4.3 Parameter Tuning with Unknown Prediction Error and Time Horizon↩︎

4.4 Lower Bound in Terms of Prediction Error↩︎

5 Dynamic Regret for TP-VR-Opt↩︎

6 Conclusion and Future Work↩︎

7 Proposition 11 ↩︎

8 Omitted Details of Section 3 ↩︎

8.1 Useful definitions and notations↩︎

8.2 Proof of Theorem 3 ↩︎

9 Omitted Details of Section 4 ↩︎

9.1 Useful Lemmas in Section 4.1 ↩︎

9.1.0.1 Estimator Decomposition.

9.2 Proof of Theorem 4 ↩︎

9.3 Proof of Theorem 5 ↩︎

9.3.0.1 Term (A):

9.3.0.2 Term (B):

9.3.0.3 Term (C):

9.4 Omitted Details of Section 4.2 ↩︎

9.5 Useful Lemmas in Section 4.3 ↩︎

9.6 Proof of Theorem 6 ↩︎

9.7 Proof of Theorem 7 ↩︎

10 Omitted Details of Section 5 ↩︎

10.1 Useful Lemmas in Section 5 ↩︎

10.2 Proof of Theorem 9 ↩︎

10.3 Proof of Theorem 10 ↩︎

References↩︎

Subjects

Updated on Academus

Bandit Convex Optimization with Gradient Prediction Adaptivity

Abstract

1 Introduction↩︎

1.1 Main Contributions↩︎

1.2 Related Works↩︎

2 Problem Setup and Preliminaries↩︎

3 The Single-Point Feedback Barrier↩︎

4 Two-Point Feedback: Prediction-sensitive Variance Reduction↩︎

4.1 The TP-VR-Opt Algorithm↩︎

4.2 Connection to Gradually Evolving Worlds [27]↩︎

4.3 Parameter Tuning with Unknown Prediction Error and Time Horizon↩︎

4.4 Lower Bound in Terms of Prediction Error↩︎

5 Dynamic Regret for TP-VR-Opt↩︎

6 Conclusion and Future Work↩︎

7 Proposition 11↩︎

8 Omitted Details of Section 3↩︎

8.1 Useful definitions and notations↩︎

8.2 Proof of Theorem 3↩︎

9 Omitted Details of Section 4↩︎

9.1 Useful Lemmas in Section 4.1↩︎

9.1.0.1 Estimator Decomposition.

9.2 Proof of Theorem 4↩︎

9.3 Proof of Theorem 5↩︎

9.3.0.1 Term (A):

9.3.0.2 Term (B):

9.3.0.3 Term (C):

9.4 Omitted Details of Section 4.2↩︎

9.5 Useful Lemmas in Section 4.3↩︎

9.6 Proof of Theorem 6↩︎

9.7 Proof of Theorem 7↩︎

10 Omitted Details of Section 5↩︎

10.1 Useful Lemmas in Section 5↩︎

10.2 Proof of Theorem 9↩︎

10.3 Proof of Theorem 10↩︎

References↩︎

Subjects

Updated on Academus

7 Proposition 11 ↩︎

8 Omitted Details of Section 3 ↩︎

8.2 Proof of Theorem 3 ↩︎

9 Omitted Details of Section 4 ↩︎

9.1 Useful Lemmas in Section 4.1 ↩︎

9.2 Proof of Theorem 4 ↩︎

9.3 Proof of Theorem 5 ↩︎

9.4 Omitted Details of Section 4.2 ↩︎

9.5 Useful Lemmas in Section 4.3 ↩︎

9.6 Proof of Theorem 6 ↩︎

9.7 Proof of Theorem 7 ↩︎

10 Omitted Details of Section 5 ↩︎

10.1 Useful Lemmas in Section 5 ↩︎

10.2 Proof of Theorem 9 ↩︎

10.3 Proof of Theorem 10 ↩︎