Abstract

We revisit the standard perturbation-based approach of [1] in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem. Our framework improves on prior work in several ways. First, we derive expected-regret guarantees when our perturbation scheme is combined with comparator-adaptive OLO algorithms, leading to new insights about the impact of different adversarial models on the resulting comparator-adaptive rates. We also extend our analysis to dynamic regret, obtaining the first guarantees with optimal \(\sqrt{P_T}\) path-length dependencies without prior knowledge of \(P_T\). We then develop the first high-probability guarantees for both static and dynamic regret in uBLO. Finally, we discuss lower bounds on the static regret, and prove the folklore \(\Omega(\sqrt{dT})\) rate for adversarial linear bandits on the Euclidean ball, which is of independent interest.

1 Introduction↩︎

Online convex optimization (OCO) provides a general framework for sequential decision-making under uncertainty, in which a learner repeatedly selects an action from a set \(\mathcal{W}\subseteq\mathbb{R}^d\) and receives feedback generated by an adversarial environment [2]–[4]. The standard measure of performance is regret, which compares the learner’s cumulative loss to that of some unknown benchmark strategy. The most general formulation is dynamic regret, defined by \[R_T(u_{1:T}) \;=\; \sum_{t=1}^T f_t(w_t)\;-\;\sum_{t=1}^T f_t(u_t),\] where \(f_t:\mathcal{W}\to\mathbb{R}\) denotes a \(G\)-Lipschitz convex loss function, each play \(w_t\in\mathcal{W}\) of the learner is based solely on its past observations, and \(\cmp_{1:T}=(u_t)_{t\in[T]}\) is a comparator sequence in \(\mathcal{W}\). The classical static regret is recovered as the special case \(u_1=\cdots=u_T\).

In this paper we focus on Bandit Linear Optimization (BLO) [5]–[9], where \(f_t\) is a linear function and the learner observes only the scalar output \(f_t(w_t)=\left\langle \ell_t,w_t \right\rangle\) for some vector \(\ell_t\in\mathbb{R}^d\) with \(\|\ell_t\|\le G\), rather than the full gradient \(\nabla f_t(\widetilde{)}=\ell_t\). We propose a modular reduction that enables the use of an arbitrary OLO learner under bandit feedback by feeding it suitably perturbed loss estimates. We focus in particular on unconstrained bandit linear optimization (uBLO), in which the action set is \(\mathcal{W}=\mathbb{R}^d\) [10]–[12]. A central objective in uBLO is to obtain comparator-adaptive guarantees, in which the regret against a static comparator \(u\) scales with \(\|u\|\), while simultaneously enforcing a risk-control constraint of the form \(R_T(0)\le \epsilon\), where \(\epsilon>0\) is a fixed, user-specified parameter.

This formulation is closely connected to parameter-free online learning and coin-betting [13]–[15]: controlling \(R_T(0)\) can be interpreted as allowing the bettor to reinvest a data-dependent fraction of an initial budget and its accumulated gains, rather than committing to a fixed betting scale [4]. This viewpoint highlights how uBLO complements the more standard linear bandit setting with a bounded action set. In the bounded case, the learner effectively plays with a fixed “unit budget” each round (since \(\|w_t\|\) is uniformly bounded), whereas in the unconstrained case the learner may increase its effective scale over time, but only if its total gains permit it. In applications where exploration must be performed under budget constraints, this built-in risk control can make the unconstrained model (perhaps counterintuitively) the more natural abstraction.

In this work we also broaden the standard notion of comparator-adaptivity by allowing the adversary to choose the comparator norm more strategically, e.g., at the end of the interaction, refining what “adaptive” guarantees entail.

Notation. We denote by \(\mathcal{F}_{t-1}\) the \(\sigma\)-field generated by the history up to the start of round \(t\), and we define \(\mathbb{E}_t[\cdot]=\mathbb{E}[\cdot|\mathcal{F}_{t-1}]\). We say a sequence of random variables \((X_t)_{t=1}^T\) is adapted to \((\mathcal{F}_t)_{t=0}^T\) if \(X_t\) is \(\mathcal{F}_t\) measurable for all \(t\). For any \(A,B\in \mathbb{R}\), we denote \(A\wedge B =\min\{A,B\}\), \(A\vee B=\max\{A,B\}\), and \((A)_+=A\vee 0\). Then, for (multivariate) functions \(f\) and \(g\), we use \(f=\mathcal{O}(g)\) (resp. \(f=\Omega(g)\)) when there exists a constant \(c>0\) s.t. \(f\leq cg\) (resp. \(\geq\)). We also use \(\widetilde{\mathcal{O}}\) and \(\widetilde{\Omega}\) respectively to further hide polylogarithmic terms (though we will occasionally still highlight \(\log(\|\cmp\|)\) dependencies when relevant). Unless stated otherwise \(\log\) is the natural logarithm and we denote \(\log_{+}(x) = \log(x)\vee 0\). A matrix \(A\in\mathbb{R}^{d\times d}\) is positive definite if it is symmetric and satisfies \(\left\langle x,Ax \right\rangle> 0\) for any \(x\in \mathbb{R}^d\).

Bandit Linear Optimization (BLO), also known as adversarial linear bandits, has a long history [1], [7], [16]–[19]. In these works, the action set \(\mathcal{W}\) is typically constrained to a bounded set, and minimax-optimal guarantees on the expected regret are known to be of order \(d\sqrt{T}\) or \(\sqrt{dT}\) depending on the geometry of the decision set [7], [20]. More recently, these results have also been extended to nearly-matching high-probability guarantees [21], [22].

Our work is most closely related to the works of [10]–[12], which investigate linear bandit problems with unconstrained action sets (uBLO). [10] provided the first approach for this setting, using a variant of the scale/direction decomposition from the parameter-free online learning literature [15]. As remarked by [11], using their approach with a direction learner admitting \(\widetilde{\mathcal{O}}(\sqrt{dT})\) regret on the unit ball [19], one can obtain a \(\widetilde{\mathcal{O}}(\|\cmp\|\sqrt{(d\vee \log(\|\cmp\|))T})\) static regret bound. Our work provides new insights into these results by highlighting a subtle dependency issue between the loss sequence and the comparator norm, addressed by our approach.

Later, [12] investigated dynamic regret in the uBLO setting, and achieved the first guarantees in the (oblivious) adversarial setting that adapt to the number of switches of the comparator sequence, \(S_T=\sum_t\mathbb{I}\left\{\cmp_t\ne\cmp_{t-1}\right\}\), while guaranteeing a \(\sqrt{S_T}\) dependence without prior knowledge of the comparator sequence. Besides this work, all existing works on dynamic regret under bandit feedback fail to obtain the optimal \(\sqrt{S_T}\) dependencies without leveraging prior knowledge of the comparator sequence [11], [23], [24], and in fact [24] show that \(\sqrt{S_T}\) dependencies are impossible against an adaptive adversary in many constrained settings. ¹ Our work is also related to the recent line of work in online convex optimization on comparator-adaptive (sometimes called parameter-free) methods. These are algorithms which, for any fixed \(\epsilon>0\), achieve guarantees of the form \[\begin{align} R_T(\cmp) =\widetilde{\mathcal{O}}\left(\epsilon +\|\cmp\|\sqrt{T\log\left(\tfrac{\|\cmp\|\sqrt{T}}{\epsilon}+1\right)}\right),\label{eq:pf} \end{align}\tag{1}\] uniformly over all \(\cmp\in\mathbb{R}^d\) simultaneously, matching the bound that gradient descent would obtain with oracle tuning (up to logarithmic factors) [13]–[15], [25]–[28]. The key feature of 1 is that the bound is adaptive to an arbitrary comparator norm, rather than the worst-case \(D=\sup_{x,y\in\mathcal{W}}\|x-y\|\), making these methods crucial for unconstrained settings. Comparator-adaptive methods have also recently been extended to dynamic regret [29]–[33], with guarantees that adapt to the path-length \(P_T\mathrel{\vcenter{:}}= \sum_{t=2}^T\|\cmp_t-\cmp_{t-1}\|\) and effective diameter \(M=\max_{t}\|\cmp_t\|\) in unbounded domains \[\begin{align} R_T(\cmp_{1:T})\le \widetilde{O}\left(\sqrt{(M^2+MP_T)T}\right)~.\label{eq:pf-dynamic} \end{align}\tag{2}\] In this work we use a less common generalization of this bound due to [29], which adapts to the path-length and each of the individual comparator norms to achieve \[\begin{align} \label{eq::indiv95norm95intro} R_T(\cmp_{1:T})\le \widetilde{O}\Big(\sqrt{(\|\cmp_T\|+P_T){\textstyle\sum_{t=1}^T} \|\ell_t\|^2\|\cmp_t\|}\Big). \end{align}\tag{3}\] Our results are the first of this form in the bandit setting.

ver@clrDraft? 1

I guess we should have a rather general introduction about OCO.
Then a more precise thing about OLO, maybe already introducing the base algorithms we are going to use, the kind of guarantees they get in the static/dynamic regret settings.
Then switch to adversarial Linear Bandits. Maybe talk a bit about some standard stuff in the constrained case, and then move to uBLO. Expand about the fact that in uBLO the main benchmark is the scale/direction regret decomposition introduced in [10] (and follow-up works?).
Maybe a teasing of the post-hoc stuff with some references of e.g. saddle-point pbs in optim where the comparator is data-dependent in a way that needs to be carefully adressed.

Online convex optimization (OCO) is a central abstraction for sequential decision-making under adversarially chosen convex losses. The standard performance criterion is (static) regret against a fixed comparator, for which first-order methods achieve the canonical \(\mathcal{O}(\sqrt{T})\)-type rates under Lipschitzness and boundedness assumptions. Foundational analyses include Online Gradient Descent and its variants (Zinkevich, 2003), and modern analyses emphasize the unifying role of mirror maps, Bregman geometry, optimistic and adaptive regularization [2]–[4].

An important specialization is online linear optimization (OLO), where losses \(\ell_t\) are linear and the algorithmic core is exposed most transparently—see, e.g., [6]. Classical algorithmic approaches include Follow-The-Regularized-Leader (FTRL) and Online Mirror Descent (OMD). Beyond “tuned” methods, a substantial literature develops parameter-free and comparator-adaptive guarantees—i.e., regret bounds that adapt (up to logarithmic factors) to unknown comparator norms or gradient scales—via coin-betting reductions and related potential-based constructions [15], [28], [29], [34]. Comparator adaptivity is essential in the unconstrained setting, where the natural decision set is \(\mathbb{R}^d\) and appropriate variants of OMD achieve regret bounds of the form \[R_T^{\mathrm{OLO}}(u) = \widehat \mathcal{O}\!\left(G + \|u\|\,\sqrt{\sum_{t=1}^T\|\ell_t\|^2\,\log\!\bigl(\|u\|\sqrt{T}\bigr)}\right)\] uniformly over \(u\in\mathbb{R}^d\), where \(G = \max_t\|\ell_t\|\) and the \(\widehat \mathcal{O}\) notation hides loglog factors [29]. These results also connect to dynamic or tracking notions of regret in nonstationary environments, where the benchmark is a sequence \(\cmp_{1:T} = (u_1,\ldots,u_T)\) of comparators and the rate depends on the path-length \(P_T = \sum_{t=2}^T \|u_t-u_{t-1}\|\) or other variation measures hall2013dynamical?, chiang2012online?. The above adaptive regret guarantees nicely extend to dynamic regret in unconstrained domains. For example, for all \(u_1,\ldots,u_T\in\mathbb{R}^d\), [29] achieves \[\begin{align} R_{T}(\cmp_{1:T}) &= \widetilde{O}\left(\sqrt{\left(\max_t\|u_t\|+P_T\right)\sum_{t=1}^T\|\ell_t\|^{2}\|\cmp_{t}\|}\right). \end{align}\] Bandit feedback substantially changes the landscape by restricting observations to a scalar loss \(\ell_t(w_t)\), thus precluding direct access to gradients. The broad setting of bandit convex optimization can be traced to one-point gradient estimation and smoothing techniques [5], with extensive follow-up works. In the linear case (bandit linear optimization), minimax optimal \(\widetilde{\mathcal{O}}(\sqrt{T})\) regret becomes achievable over bounded convex action sets [7]. For constrained domains, koolen2010hedging? introduce the Online Stochastic Mirror Descent (OSMD) approach—see also [19]. A key technique emerging in this setting is SCRiBLe [1], which leverages self-concordant barrier geometry to construct low-variance loss estimators and obtains optimal-order regret while remaining computationally efficient—see also the work by [22] on adversarial linear bandits, approaching minimax rates with a refined high-probability analysis. DB NCB

The unconstrained bandit linear optimization (uBLO) regime has only more recently been studied systematically. A central idea is to separate the problem into direction learning on a bounded set (e.g., the unit ball) and scale learning (a one-dimensional parameter-free OLO problem), yielding a scale/direction regret decomposition. This viewpoint is developed explicitly by [10], who provide comparator-adaptive linear bandit guarantees, offering a conceptual and technical bridge from parameter-free full-information methods to the bandit setting. Concretely, the decomposition highlights that the direction component can often reuse constrained-domain techniques (including SCRiBLe-style estimators), while the scale component inherits the requirement of robust, tuning-free control typical of unconstrained OLO.

Finally, it is worth flagging a methodological point that becomes increasingly important when seeking norm-dependent comparator guarantees. Namely, bounds that remain meaningful when the comparator’s norm potentially depends on the entire sequence of the learner’s random bets. In such situations, inserting a random comparator into expectation-based regret analyses can fail, because the comparator is no longer independent of the learner’s internal randomness. Related dependency issues are well-known in stochastic saddle-point and variational inequality optimization, where analyses often introduce auxiliary sequences (“ghost iterates”) or additional sampling/regularization to decouple stochastic gradients from the iterates they influence [35], juditsky20115?, mishchenko2020revisiting?, and where handling unbounded domains/gradients requires further stabilization [36]. These techniques provide a useful conceptual reference for treating norm-dependent benchmarks in bandit settings, where action-dependent sampling creates strong statistical couplings.

1.2 Contributions↩︎

In this paper we revisit the classic perturbation-based approach of [1] in the setting of unconstrained linear bandits (Section 2), under the name (Perturbation Approach for Bandit Linear Optimization). We show that this approach produces loss estimators with strong properties, enabling us to develop several novel results in the uBLO setting.

Adaptive comparators in expected-regret bounds. We propose a novel algorithm with expected-regret guarantees for both static regret (Section 3.1) and for dynamic regret (Section 3.2). A key novelty is that our bounds remain valid in an adversarial regime where the comparator may be data-adaptive. This exposes an oblivious comparator assumption that is often left implicit in prior work, which we discuss in Section 3.1. Notably, distinguishing between oblivious and data-adaptive comparator settings induces a \(\sqrt d\) separation in the dimension dependence of our bounds, while preserving the same \(\sqrt{T}\) scaling in the horizon. We show that this contrasts with direct adaptations of prior approaches, which can incur a worse dependence on \(T\) in the adaptive comparator regime. We leave as an open question to determine if this gap is unavoidable.

\(\sqrt{P_T}\)-adaptive dynamic regret. By relying on the framework, we develop the first algorithm for uBLO with an expected dynamic-regret guarantee exhibiting the optimal \(\sqrt{P_T}\) dependence without prior knowledge of \(P_T\). This contrasts with [12], who derive a comparable guarantee only for the weaker switching measure \(S_T\mathrel{\vcenter{:}}=\sum_t\mathbb{I}\left\{\cmp_t\ne\cmp_{t-1}\right\}\). Moreover, as detailed in Section 3.2, our analysis yields an even stronger bound, inspired by recent advances in OCO (see Eq. 3 ).

High-probability bounds. In 4, we develop the first high-probability bounds for static and dynamic regret in uBLO. Our static regret guarantee scales as \(R_T(\cmp)\le \widetilde{\mathcal{O}}(\|\cmp\|\sqrt{dT\log\left(1/\delta\right)})\), matching the best known rates from the bounded domain setting [21], [22]. Our dynamic regret bound generalizes this result, and leads to \(R_T(\cmp_{1:T})\le \widetilde{\mathcal{O}}(\sqrt{d(M^2+MP_T)T}+M\sqrt{dT\log\left(T/\delta\right)})\), where \(M=\max_t\|\cmp_t\|\), again without prior knowledge of \(P_T\) or \(M\).

Open discussion on lower bounds. In 5 we discuss the largely open problem of proving regret lower bounds for uBLO, with a focus on static regret. We establish intermediate results that motivate the conjecture that, when the comparator norm is non-adaptive, the minimax lower bound scales as \(\Omega\bigl(\|u\|\sqrt{T\,(d\vee \log\|u\|)}\bigr)\), and we briefly comment on the more challenging norm-adaptive regime.

As part of this investigation, we also provide a self-contained proof (Theorem 3) that the \(\widetilde{\mathcal{O}}(\sqrt{dT})\) static regret achievable on the unit Euclidean ball (see, e.g., [19]) is minimax-optimal. This complements existing characterizations of dimension-dependent minimax rates for adversarial linear bandits on bounded action sets [7], [20].

2 Perturbation-based approach↩︎

In this section we introduce a simple reduction that turns any algorithm for Online Linear Optimization (OLO) into an algorithm for Bandit Linear Optimization (BLO), inspired by the SCRiBLe algorithm of [1], [37]. We will refer to this approach as \(\!\), short for a Perturbed Approach to Bandit Linear Optimization. The pseudo-code of \(\!\) can be found in Algorithm 1. On each round \(t\), the algorithm operates in two steps. First, an OLO learner \(\mathcal{A}\) outputs a decision \(w_t \in \mathcal{W}\) based on past feedback. Then the algorithm applies a randomized perturbation to \(w_t\), observes the bandit feedback, and constructs an unbiased estimator \(\widetilde{\ell}_t\) of the loss \(\ell_t\), which is then passed back to \(\mathcal{A}\).

This is a modest generalization of SCRiBLe, decoupling the OLO update from the perturbation mechanism. In the original SCRiBLe algorithm, both components are tied to a single self-concordant barrier \(\psi\): the OLO step is implemented via FTRL with regularizer \(\psi\), and the perturbation is scaled using the local geometry induced by \(\nabla^2 \psi(w_t)\), which is replaced by a matrix \(H_t^{\frac{1}{2}}\) in \(\!\). As we show in Section 3, this coupling is not strictly necessary in the unconstrained setting, and it can be advantageous to tune the OLO algorithm and the perturbation level separately.

Properties. We now introduce some general properties on the loss estimators produced by Algorithm 1, according to the matrix chosen for the perturbation. Notably, the estimator is unbiased and its norm \(\|\widetilde{\ell}_t\|^2\) admits an almost-sure upper bound, as well as a (potentially) sharper bound in expectation. The almost-sure upper bound is the crucial property that allows us to apply sophisticated comparator-adaptive OLO algorithms as subroutines.

propositionCoordinateSampling Let \(H_t\in\mathbb{R}^{d\times d}\) be positive definite and let \(v_{1},\ldots,v_{d}\) be an orthonormal basis of eigenvectors of \(H_t\). Consider the set \(\mathcal{S}=\{\sigma v_i:\;\sigma\in\{-1,1\},\;i\in[d]\}\). Let \(s_t\) be sampled uniformly at random from \(\mathcal{S}\), and define \[\begin{align} \wtilde_t = w_t + H_t^{-\frac{1}{2}}s_t,\quad \text{and} \quad \elltilde_t = d\,H_t^{\frac{1}{2}}s_t\,\langle \wtilde_t,\ell_t\rangle. \end{align}\] Then \(\mathbb{E}[\elltilde_t \mid \mathcal{F}_{t-1}] = \ell_t\) and the following hold: \[\begin{align} \mathbb{E}[\|\elltilde_t\|_2^2 \mid \mathcal{F}_{t-1}] &= d\|\ell_t\|_2^2 + d\,\langle \ell_t,w_t\rangle^2\,\mathrm{Tr}\!\left(H_t\right), \\ \|\elltilde_t\|_2^2 &\le d^2\|\ell_t\|_2^2\big(\sqrt{\lambda_t}\,\|w_t\|+1\big)^2, \end{align}\] where \(\lambda_t\) is the eigenvalue of \(H_t\) associated with the eigenvector \(v_t\) sampled on round \(t\).

From this, we immediately get the following corollary, which will have important implications for the techniques we employ throughout the rest of the paper.

ver@clrVerboseGradientBound? 1

The proposition has two immediate consequences. First, if \(H_t\) is chosen so that its eigenvalues satisfy \(\lambda_i \le 1/\|w_t\|^2\), then the estimator is uniformly bounded. Indeed, \[\|\widetilde{\ell}_t\|_2^2 \le d^2\|\ell_t\|_2^2\big(\sqrt{\lambda_t}\|w_t\|+1\big)^2 \le 4d^2\|\ell_t\|_2^2 \le 4d^2G^2,\] so the linearized losses \(w\mapsto \langle \widetilde{\ell}_t, w\rangle\) are \(2dG\)-Lipschitz. Second, the conditional second moment satisfies \[\mathbb{E}\!\left[\|\widetilde{\ell}_t\|_2^2 \mid \mathcal{F}_{t-1}\right] = d\|\ell_t\|_2^2 + d\,\langle \ell_t,w_t\rangle^2\,\mathrm{Tr}\!\left(H_t\right).\] Moreover, strengthening the condition to \(\lambda_i \le 1/(d\|w_t\|^2)\) for all \(i\) and \(t\), yields \(\mathrm{Tr}\!\left(H_t\right)\le 1/\|w_t\|^2\) and hence \[\mathbb{E}\!\left[\|\widetilde{\ell}_t\|_2^2 \mid \mathcal{F}_{t-1}\right] \le d\|\ell_t\|_2^2 + d\,\|\ell_t\|_2^2 = 2d\|\ell_t\|_2^2,\] which yields the sharper bound \(\mathbb{E}[\|\widetilde{\ell}_t\|_2^2]\le 2d\|\ell_t\|_2^2\), which can (as we will see) translate into order optimal minimax regret bounds. In the next sections, we will see that this distinction leads to different guarantees depending on whether the adversary can adapt the comparator norm to the trajectory, or must commit to it in advance (\(\mathcal{F}_0\)-measurable).

corollarySimpleCoordinateSampling Under the same assumptions as [prop:coordinate-sampling], let \(\varepsilon\in (0,1)\) and suppose that for all \(t\) we set \[\begin{align} \label{eq::def95Ht} H_t\preceq\frac{1}{d(\|\widetilde{\|}^2\vee \varepsilon^{2})}I_d~. \end{align}\tag{4}\] Then the following hold almost-surely: \[\begin{align} \|\elltilde_t\|^2&\le 4d^2\|\ell_t\|^2\quad\text{and}\quad \mathbb{E}\big[\|\elltilde_t\|^2|\mathcal{F}_{t-1}\big]\le 2d\|\ell_t\|^2. \end{align}\]

The parameter \(\varepsilon>0\) will play a minor role in developing our high-probability guarantees in 4, though otherwise serves only to prevent division by zero when \(\widetilde{=}\mathbf{0}\) and can be set to any positive value.

[cor:simple-coordinate-sampling] has two important implications for our purposes. First, since the loss estimates are bounded uniformly by \(2d\|\ell_t\|\le2dG\), we will be able to apply modern comparator-adaptive OLO algorithms, which require uniformly bounded gradient norms. Second, the conditional second-moment bound yields a sharper bound which can, as we will see, translate into order-optimal minimax regret bounds. In the next sections, we see that this distinction leads to different guarantees depending on whether the adversary can adapt the comparator norm to the loss sequence, or must commit to it in advance.

In what follows, the oblivious setting refers to fully oblivious settings where both the loss sequence and the comparator sequence are \(\mathcal{F}_0\) measurable (e.g., determined before the start of the game). For ease of exposition, we also assume in the oblivious setting that all \(\mathcal{F}_0\)-measurable quantities are deterministic (equivalently, that \(\mathcal{F}_0\) is the trivial \(\sigma\)-algebra).

2.1 Generic Expected Regret Analysis for BLO↩︎

We now state a generic reduction showing how the expected-regret guarantees of follow from those of the underlying OLO routine \(\mathcal{A}\).

propositionExpectedReduction Let \(\mathcal{U}\) be a class of sequences ² in \(\mathbb{R}^d\) and suppose that \(\mathcal{A}\) guarantees that for any sequence \(\g_{1:T}=(\g_t)_{t=1}^T\) in \(\mathbb{R}^d\) and any sequence \(\cmp_{1:T} = (\cmp_t)_{t=1}^T\in\mathcal{U}\), \[\begin{align} R_T^\mathcal{A}(\cmp_{1:T}) &\le B_T^\mathcal{A}(\cmp_{1:T}, \g_{1:T}) \end{align}\] for some function \(B_T^\mathcal{A}:(\mathbb{R}^d)^{2T}\to\mathbb{R}_{\ge 0}\). Then, for any sequence of losses \(\ell_1,\ldots,\ell_T\) and any comparator sequence \(\cmp_{1:T}\in\mathcal{U}\), using \(\mathcal{A}\) for its OLO learner guarantees \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &\le \mathbb{E}\left[ B_T^\mathcal{A}\left(\cmp_{1:T}, \elltilde_{1:T}\right)+ B_T^\mathcal{A}\left(\cmp_{1:T}, \delta_{1:T}\right) \right] \end{align}\] where \(\delta_t = \ell_t-\elltilde_t\) for all \(t\), and \(\widetilde{\ell}_t\) is defined in Algorithm 1.

The proof is deferred to 7, and is based on a standard ghost-iterate trick (see, e.g., [35], [36]). More generally, the same reduction applies to any bandit algorithm that plays a randomized action whose conditional expectation equals the iterate produced by an OLO routine. Our perturbation scheme is one concrete instantiation of this principle, and has the particular advantage of having loss estimates that are both unbiased and bounded uniformly (for appropriately chosen \(H_t\) as in [cor:simple-coordinate-sampling]), enabling us to apply comparator-adaptive OLO algorithms which require bounded gradient norms.

3 Novel expected regret bounds for uBLO↩︎

In this section we present several applications of Proposition [prop:expected-reduction], leading to new algorithms and regret guarantees for the uBLO setting within the framework. A key feature of uBLO is that the action domain is unbounded, so the perturbation matrices \((H_t)_{t\geq 1}\) are not constrained by feasibility considerations, so we are free to set \(H_t\) according to the conditions of [cor:simple-coordinate-sampling]. In the remainder of the paper, we therefore adopt the simple isotropic choice in 4 , and focus on how different regret guarantees arise from different choices of the underlying OLO routine.

3.1 Static Regret via Parameter-free OLO↩︎

We first instantiate for uBLO by choosing, as an OLO subroutine, the parameter-free mirror descent (PFMD) algorithm of [29]. This choice is motivated by its strong static comparator-adaptive guarantee on the unconstrained domain: for any \(\epsilon>0\) and any sequence \((g_t)_{t\geq 1}\) with \(\|\gt\|\le G\) for all \(t\), its regret satisfies \(R_T^{\mathcal{A}}(u) = \widetilde{O}\!\Big(G\epsilon + \|u\|\,\sqrt{V_T\,\log_+\Big(\frac{\|u\|\sqrt{V_T}}{G\epsilon}}\Big)\Big),\) where \(V_T=\sum_{t=1}^T\|\gt\|^2_2\), uniformly over \(u\in\mathbb{R}^d\). To turn this into a guarantee for the bandit setting, we then apply Proposition [prop:expected-reduction] and obtain the following result. ver@clrExpectedV1? 1 ver@clrExpectedV2? 1

theoremExpectedStatic For any \(\cmp\in\mathbb{R}^d\), equipped with [29] with parameter \(\epsilon/d\) guarantees \[\begin{align} \mathbb{E}\left[ R_T(\cmp) \right]\!&= \widetilde{\mathcal{O}}\Bigg(\!G\epsilon + \frac{d}{\kappa}\mathbb{E}\left[ \|\cmp\|\sqrt{V_T\log_+\left(\tfrac{d\|\cmp\|\Lambda_T}{G\epsilon}\right)} \right]\Bigg), \end{align}\] where \(V_T=\sum_{t=1}^T\|\ell_t\|^2\), \(\Lambda_T=G\sqrt{T}\log^2(1 + T)\), and \(\kappa = \sqrt{d}\) in the oblivious setting and \(\kappa=1\) otherwise.

Remark 1. [thm:expected-static] actually holds more generally for a partially-oblivious* setting in which the comparator is \(\mathcal{F}_0\) measurable but \(\ell_{1:T}\) may be adaptive. In this setting, the guarantee scales as \(\mathbb{E}\|\cmp\|\sqrt{d\sum_t\mathbb{E}\left[ \|\ell_t\|^2\big|\mathcal{F}_0 \right]}\), which recovers the statement for the oblivious setting as a special case. We focus our discussion on the adaptive and oblivious settings in the main text for ease of presentation but provide a more general statement of the result in 8.*

Proof of [thm:expected-static] can be found in 8. A key subtlety, and the reason [thm:expected-static] yields two distinct guarantees, is that using Jensen’s inequality to obtain an upper bound of the form \[\mathbb{E}\!\left[\|u\|\sqrt{\sum_{t=1}^T \|\widetilde{\ell}_t\|_2^2}\right] \;\le\; \|u\|\sqrt{\sum_{t=1}^T \mathbb{E}\left[ \|\widetilde{\ell}_t\|_2^2 \right]}\] is only justified when the scale \(\|u\|\) is conditionally independent of the randomness generating \(\widetilde{\ell}_t\) (and thus does not depend on the realized trajectory through the losses and actions). When such independence holds (e.g., \(\|u\|\) is chosen obliviously at the start of the game), we can exploit the sharper in-expectation control of \(\|\widetilde{\ell}_t\|_2^2\). Otherwise, for norm-adaptive comparators, we must rely on the more conservative almost-sure bound from [cor:simple-coordinate-sampling] to bound \(\|\elltilde_t\|^2=\mathcal{O}(d^2\|\ell_t\|^2)\).

Note that this is generally not a concern in constrained settings: in the standard bounded domain setting, the worst-case comparator is typically on the convex hull of \(\mathcal{W}\), and its norm can be bounded by the diameter of \(\mathcal{W}\). However, in an unconstrained linear setting, no such finite worst-case comparator exists, and the goal becomes to ensure \(R_T(\cmp)\le B_T(\cmp)\) for all \(\cmp\in\mathbb{R}^d\) simultaneously, where \(B_T(\cmp)\) is some non-negative function. This makes the natural worst-case comparator have a data-dependent norm, e.g., \(\|\cmp\|\propto \exp\left(\frac{\|\sum_{t=1}^T\ell_t\|^2}{G^2T}\right)\) when choosing \(B_T(\cmp)\) to match the minimax optimal bound for OLO (see Appendix 14 for details). Because of this, from a comparator-adaptive perspective, it is not natural to treat the comparator norm as independent of the losses or the learner’s decisions without additional explicit assumptions.

Interestingly the above observation does not seem to be accounted for in prior works. Indeed, as far as we are aware all prior works in this setting are implicitly making the assumption that the comparator norm is oblivious rather than adaptive [10]–[12], and the stated guarantees can potentially be very different without this assumption, as detailed in the following discussion.

Comparison with existing work. We proved that combined with PFMD yields comparator-adaptive expected regret bounds under two adversarial regimes depending on when the norm of the comparator is selected. It is instructive to compare these guarantees to what can be obtained from the scale/direction decomposition of [10]. Concretely, consider a decomposition in which the scale is learned by Algorithm 1 of [15] and the direction is learned by OSMD specialized to the unit Euclidean ball [19]. If the norm \(\|u\|\) is oblivious, this combination yields the bound \[\begin{align} \label{eq::regret95scaleosmd} R_T(u) = \mathcal{O}\!\Bigg( \|u\|\sqrt{T\Bigl(\log\!\bigl(\tfrac{\|u\|\sqrt{T}}{\epsilon}\bigr)\,\vee\, d\Bigr)} \Bigg), \end{align}\tag{5}\] which can improve over Theorem [thm:expected-static] by up to a factor \(\sqrt d\) when the log term matches the dimension.

However, this advantage hinges on applying the in-expectation second-moment control for the direction estimator, and therefore does not extend to the norm-adaptive regime. In particular, the standard OSMD guarantee on the unit ball (namely, the \(\mathcal{O}(\sqrt{dT})\) term) does not directly translate when the comparator scale is allowed to be chosen adaptively and may be coupled with the realized trajectory. As we show in Appendix 13, obtaining regret bounds against such norm-adaptive adversaries requires re-tuning the algorithm, and the resulting rate degrades to \(\widetilde{\mathcal{O}}((dT)^{2/3})\). This highlights a key benefit of : it maintains \(\sqrt{T}\)-type regret guarantees in the horizon uniformly across both regimes, without requiring regime-dependent tuning.

3.2 Dynamic Regret in Expectation↩︎

To achieve dynamic regret guarantees, we now apply with a suitable OLO algorithm for unconstrained dynamic regret. The following result shows that the optimal \(\sqrt{P_T}\) dependence can be obtained by leveraging the parameter-free dynamic regret algorithm of [29]. We provide a modest refinement of their result which removes \(M=\max_t\|\cmp_t\|\) completely from the main term in the bound, and showcases a refined measure of comparator variability: the log-linear path-length \[\begin{align} P_T^\Phi=\sum_{t=2}^T\|\cmp_t-\cmp_{t-1}\|\log\left(\|\cmp_t-\cmp_{t-1}\|T^3/\epsilon+1\right) \end{align}\] which is an adaptive refinement of the \(P_T\log\left(MT^3/\epsilon+1\right)\) dependence reported by [29]. This result is of independent interest and is provided in 11.2. Then applying with this dynamic regret algorithm leads to the expected dynamic regret guarantee for uBLO presented in 2 below.

Proof of the following theorem can be found in 9. The closest result to ours is the recent work of [12], which also achieves adaptivity to the comparator sequence without prior knowledge. However, their result scales with the switching number \(S_T= \sum_{t=2}^T\mathbb{I}\left\{\cmp_t\ne\cmp_{t-1}\right\}\), which is closely related to \(P_T\) but is a weaker measure of variation, failing to account for the potentially heterogeneous magnitudes of the increments \(\|\cmp_t-\cmp_{t-1}\|\). Our result is therefore the first to achieve \(\sqrt{P_T}\) adaptivity to the genuine path-length \(P_T\). Moreover, their result is restricted to the oblivious adversarial setting, whereas our results remain meaningful even against fully-adaptive comparator and loss sequences.

theoremExpectedDynamic For any sequence \(\cmp_{1:T}=(\cmp_t)_{t=1}^T\) in \(\mathbb{R}^d\), equipped with 10 tuned with \(\epsilon/d\) guarantees \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &= \widetilde{\mathcal{O}}\Bigg(\mathbb{E}\Bigg[\frac{d}{\kappa}\sqrt{(\|\cmp_T\|+P_T)\mathcal{V}_T}\\ &\qquad\qquad +dG(\epsilon+\max_t\|\cmp_t\|+P_T)\Bigg]\Bigg). \end{align}\] where \(\mathcal{V}_T=\sum_{t=1}^T\mathbb{E}\left[ \|\ell_t\|^2\big|\mathcal{F}_0 \right]\|\cmp_t\|\) and \(\kappa = \sqrt{d}\) if the sequence \(\cmp_{1:T}\) is \(\mathcal{F}_0\)-measurable, while \(\mathcal{V}_T=\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|\) and \(\kappa=1\) otherwise.

Besides achieving the optimal \(\sqrt{P_T}\) dependence, we inherit another novelty from the algorithm of [29]: the bound of 2 is also adaptive to the individual comparator norms, with a variance penalty scaling with \(\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|\). This leads to a property which is similar in spirit to a strongly-adaptive guarantee [38], in the sense that if the comparator sequence is only active (non-zero) within a sub-interval \([a,b]\), then the regret automatically restricts to that same sub-interval, \(R_T(\cmp_{1:T})= \widetilde{\mathcal{O}}( \sqrt{P_{[a,b]}\left|b-a\right|})\), where \(P_{[a,b]}=\sum_{t=a+1}^b\|\cmp_t-\cmp_{t-1}\|\) is the path-length over the interval. While [29] show that one cannot obtain comparator-adaptive guarantees on all sub-intervals simultaneously (thereby extending the impossibility result of [38] to unbounded domains), the per-comparator adaptivity in 2 can be viewed as a natural, achievable analogue of strong adaptivity in the unbounded setting.

Finally, we again observe a \(\sqrt{d}\) discrepancy between the upper bounds obtained against a norm-oblivious or norm-adaptive adversary, leading to similar insights as observed in the previous section. Likewise, our result more generally holds for the partially-oblivious setting wherein \(\cmp_{1:T}\) is \(\mathcal{F}_0\) measurable but \(\ell_{1:T}\) may be adaptive, in which case the \(\|\ell_t\|^2\) dependencies are replaced by the more general \(\mathbb{E}\left[ \|\ell_t\|^2|\mathcal{F}_0 \right]\), as discussed in 1.

4 High-probability Bounds↩︎

In this section we derive novel high-probability bounds for both static and dynamic regret, for new instances of \(\!\). As in the previous setting, we begin with a general reduction to unconstrained OLO, and study the additional penalties that emerge due to the loss estimates. We again use \(H_t\) from Eq. 4 in all applications presented in this section, though in this section we will choose \(\varepsilon^{2} \propto 1 / T\); this will ensure that the perturbations \(H_{t}^{-1/2}\st\) in 1 have sufficiently nice concentration properties in the following reduction.

propositionHighProbRedux Let \(\mathcal{A}\) be an OLO learner, \(\delta\in(0,1/3]\), and for all \(t\) set \(H_{t}\) as in 4 for \(\varepsilon^{2} \propto 1/T\). Let \(\cmp_{1:T}=(\cmp_t)_{t=1}^T\) be an arbitrary \((\mathcal{F}_t)_{t=0}^T\)-adapted sequence in \(\mathbb{R}^d\). Then, guarantees that with probability at least \(1-3\delta\), \[\begin{align} R_T(\cmp_{1:T}) &\le \widetilde{\mathcal{O}}\Bigg( \widetilde{R}_T^\mathcal{A}(\cmp_{1:T}) + G\sqrt{d\sum_{t=1}^T\|\widetilde{\|}^2\log\left(\tfrac{1}{\delta}\right)}\\ &\qquad +G\sqrt{d\sum_{t=1}^T\|\cmp_t\|^2\log\left(\tfrac{1}{\delta}\right)}+dGP_T \Bigg)\;, \end{align}\] where \(\widetilde{R}_T^\mathcal{A}(\cmp_{1:T})\) is the regret of \(\mathcal{A}\) against the losses \((\elltilde_t)_t\).

Remark 2. Each of the results in this section in fact generalize to arbitrary* comparator sequences via the same “ghost-iterate” trick as in 3.1, though the statement of the result above becomes a bit more involved to state. We focus on the \((\mathcal{F}_t)_{t=0}^T\)-adapted case here for ease of exposition and discuss the extension to general comparator sequences in 10.3.1.*

Proof of the theorem can be found in 10.1. It shows that uBLO can also be effectively reduced to uOCO (with regard to high-probability bounds) at the expense of three additional terms. The latter two comparator-dependent terms are fairly benign and amount to a lower-order \(\mathcal{O}(GP_T)\) and a \(\widetilde{\mathcal{O}}(M\sqrt{dT\log\left(T/\delta\right)})\), both of which are expected in this setting. However, the term \(G\sqrt{d\sum_{t=1}^T\|\widetilde{\|}^2\log\left(1/\delta\right)}\) is algorithm dependent and could be arbitrarily large in an unbounded domain. Thus, the main difficulty to achieve high-probability bounds for stems from controlling the stability of the iterates \(\widetilde{None}\) from the OLO learner \(\mathcal{A}\).

Fortunately, a similar concern was recently addressed by [28] in the context of unconstrained stochastic optimization with heavy-tailed noise. Their approach is based on adding an additional composite penalty \(\varphi_t\) to the losses, which introduces an extra term \(\sum_{t=1}^T\varphi_t(\cmp)-\varphi_t(\widetilde{)}\) into the regret bound. With this, the goal is to choose \(\varphi_t\) in such a way that \(-\sum_{t=1}^T\varphi_t(\widetilde{)}\) is large enough to cancel with the \(\|\widetilde{\|}\)-dependent terms above, while also ensuring that \(\sum_{t=1}^T\varphi_t(\cmp)\) is not too large. [28] provide a Huber-like penalty which satisfies both of these conditions (see [lemma:dynamic-huber]).

The difficulty with the above approach is that by introducing the composite penalty, we change the OLO learner’s feedback: on round \(t\), the learner’s feedback becomes \(\tgt=\gt+\nabla\varphi_t(\widetilde{)}\) instead of just \(\gt\in\partial f_{t}(\widetilde{)}\), and the \(\nabla\varphi_t(\widetilde{)}\) dependence may itself lead to \(\|\widetilde{\|}\)-dependent penalties in the bound. This issue can be fixed using an optimistic update by setting hints \(h_t=\nabla\varphi_t(\widetilde{)}\), so that the usual \(\sum_{t=1}^T\|\tgt\|^2\) penalties in the final bound become \(\sum_{t=1}^T\|\tgt-h_t\|^2=\sum_{t=1}^T\|\gt\|^2\), thus removing the problematic dependence on \(\nabla\varphi_{t}(\widetilde{)}\).

Plugging this approach into our framework, and composing [prop:high-prob-redux] with [28], we obtain the following high-probability guarantee. Notably, the result matches the best-known results from the constrained setting [22] up to poly-logarithmic terms.

theoremHighProbStatic Let be implemented with [28], and \(\delta\in (0,1/3]\). Then for any \(\mathcal{F}_0\)-measurable \(\cmp\in\mathbb{R}^d\), with probability at least \(1-3\delta\), \[\begin{align} R_T(\cmp)\!\le\!\widetilde{\mathcal{O}}\Big(\!dG(\epsilon\!+\!\|\cmp\|)\log\left(\tfrac{T}{\delta}\right)\!+\!G\|\cmp\|\sqrt{dT\log\left(\tfrac{T}{\delta}\right)}\Big)~. \end{align}\]

Interestingly, a similar strategy leveraging composite regularization and optimism can also be used to obtain high-probability dynamic regret bounds. In 11.1 ([thm:optimistic-dynamic-base]), we provide an algorithm \(\mathcal{A}_\eta\) that guarantees that for any sequences \(\cmp_{1:T}\) and \(\elltilde_{1:T}\) in \(\mathbb{R}^d\), \[\begin{align} \sum_{t=1}^T\left\langle \elltilde_t,\widetilde{^}\eta-\cmp_t \right\rangle &\le \widetilde{\mathcal{O}}\Big(\frac{\|\cmp_T\|+P_T}{\eta} +\eta\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|\nonumber\\ &\qquad + \sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{^}\eta)\Big),\label{eq:dynamic-partial} \end{align}\tag{6}\] for any convex and \(H\)-Lipschitz function \(\varphi_t:\mathbb{R}^d\to\mathbb{R}_{\ge0}\) and \(\eta\) satisfying \(\eta(\|\elltilde_t\|+H)\le 1\). This bound matches the regret bound obtained in the expected dynamic regret setting when \(\eta\) is optimally tuned, but additionally exhibits a term \(\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{^}\eta)\). Note that achieving this bound requires developing a novel black-box optimistic reduction which obtains adaptivity to the individual comparator norms \(\|\cmp_t\|\), which is not possible using the optimistic reductions in [28] or [39], so this result is of independent interest. We then obtain the optimal trade-off in \(\eta\) using a standard technique for combining comparator-adaptive guarantees: by running the algorithm in parallel over a grid of values of \(\eta\) and playing \(\w_t=\sum_{\eta}\w_t^\eta\), we obtain the tuned bound \[\begin{align} \sum_{t=1}^T\left\langle \elltilde_t, \widetilde{-}\cmp_t \right\rangle &\le \widetilde{\mathcal{O}}\Bigg(d\sqrt{(\|u_T\|+P_T)\sum_{t=1}^T \|\ell_t\|^2\,\|u_t\|}\\ &\qquad +\sum_{t=1}^T\varphi_t(\cmp_t)-\sum_{\eta}\sum_{t=1}^T\varphi_t(\widetilde{^}\eta)\Bigg). \end{align}\] Finally, we show that for the Huber-like composite penalty \(\varphi_t\) defined by [28], the aggregate-iterate \(\|\widetilde{\|}=\|\sum_\eta\widetilde{^}\eta\|\) dependencies from [prop:high-prob-redux] are canceled out by the aggregate penalty \(-\sum_\eta\sum_{t=1}^T\varphi_t(\widetilde{^}\eta)\), while also ensuring that \(\sum_{t=1}^T\varphi_t(\cmp_t)= \widetilde{O}\Big(\sqrt{d\sum_{t=1}^T\|\cmp_t\|^2\log\left(T/\delta\right)}\Big)\). A detailed description of the algorithm, along with proof of its regret guarantee stated below, can be found in 10.3.

theoremHighProbDynamic

Let \(\delta\in(0,1/4]\). Then applied with 6 and appropriately-chosen parameters (depending only on \(G\), \(\delta\), \(T\), and \(d\), given explicitly in 10.3) guarantees that for any \((\mathcal{F}_t)_{t=0}^T\)-adapted sequence \(\cmp_{1:T}\) in \(\mathbb{R}^d\), with probability at least \(1-4\delta\) it holds that \[\begin{align} R_T(\cmp_{1:T})&\le \widetilde{\mathcal{O}}\Big( \sqrt{d(\Phi_T+P_T^\Phi)\big[d\mathcal{V}_T\wedge\Omega_T\big] }\\ &\qquad +G\sqrt{d{\textstyle\sum_{t=1}^T} \|\cmp_t\|^2\log\left(\tfrac{T}{\delta}\right)}\\ &\qquad +dG(\epsilon + M+\Phi_T+P_T^\Phi)\log\left(\tfrac{T}{\delta}\right)\Big)\;, \end{align}\] where \(M=\max_t\|\cmp_t\|\), \(\mathcal{V}_T=\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|\), \(\Omega_T=MG^2(T+d\log\left(\tfrac{1}{\delta}\right))\), and we denote \(\Phi_T=\|\cmp_T\|\log\big(\tfrac{\|\cmp_T\|T}{\epsilon}+1\big)\) and \(P_T^\Phi=\sum_{t=2}^T\|\cmp_t-\cmp_{t-1}\|\log\big(\tfrac{\|\cmp_t-\cmp_{t-1}\|T^3}{\epsilon}+1\big)\).

The full proof can be found in 10.3. To understand the bound, consider first taking \([d\mathcal{V}_T\wedge\Omega_T]\le \Omega_T\). In this case the bound reduces to \[\begin{align} R_T&(\cmp_{1:T}) \le \widetilde{\mathcal{O}}\Big(dG(\epsilon+M+P_T)\log\left(\tfrac{T}{\delta}\right)\\ &\qquad +GM\sqrt{dT\log\left(\tfrac{T}{\delta}\right)} +\sqrt{d(M^2+MP_T)T}\Big). \end{align}\] Therefore, the bound captures the same worst-case \(G\|\cmp\|\sqrt{dT}\) bound as [thm:high-prob-static] in the static regret (\(P_T=0\)) setting, matching the best-known result from the constrained setting up to poly-logarithmic terms as a special case [22]. At the same time, if instead we bound \([d\mathcal{V}_T\wedge\Omega_T]\le d\mathcal{V}_T\), we obtain a per-comparator adaptivity similar to the expected regret guarantee in [thm:expected-static], with \(R_T(\cmp_{1:T})\) bounded by \[\begin{align} &\widetilde{O}\!\Bigg( \!G\sqrt{\!d\sum_{t=1}^T\|\cmp_t\|^2\log\left(\tfrac{T}{\delta}\right)} \!+\!d\sqrt{\!(\Phi_T\!+\!P_T^\Phi)\!\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|}\\ &\qquad +dG(\epsilon+M+P_T)\log\left(\tfrac{T}{\delta}\right) \Bigg). \end{align}\] Hence the bound retains the strong-adaptivity-like property discussed in 3.2, in which the bound automatically restricts to a sub-interval \([a,b]\) when comparing against comparator sequences which are only active on \([a,b]\), and also avoids \(M=\max_t\|\cmp_t\|\) in all but lower-order terms in the bound.

5 Towards lower bounds for uBLO↩︎

This section provides some insights on lower bounds for unconstrained adversarial linear bandits. We present a conjecture for the static-regret minimax rate, guided by known OCO lower bounds and by a self-contained proof of the folklore \(\widetilde{\Theta}(\sqrt{dT})\) minimax bound on the unit Euclidean ball, which captures the intrinsic difficulty of identifying a favorable direction under mildly biased losses. We then discuss post-hoc comparator norm adaptivity, motivating lower-bound formulations that simultaneously control both the expected comparator norm and its worst-case magnitude.

We recall the scale/direction regret decomposition from [10]. Although none of our algorithms use this approach, it is central for the discussions in this section: at each step \(t\) we decompose the learner’s action \(x_t\) as \(x_t=v_t z_t\), where \(v_t\in \mathbb{R}\) is a scalar (“scale”) and \(z_t\in \mathbb{B}_d\) is a unit vector (“direction”). Then, it can be shown [15] that the full (unconstrained) regret \(R_T(u)\) can be written as \[\label{eq::scale95direction} R_T(u)=R_T^{\mathcal{V}}(\|u\|)+\|u\|\,R_T^{\mathcal{Z}}\!\left(\frac{u}{\|u\|}\right), \text{with}\tag{7}\] \(R_T^{\mathcal{V}}(\|u\|)\mathrel{\vcenter{:}}=\sum_{t=1}^T \bigl(v_t-\|u\|\bigr)\,\langle z_t,\ell_t\rangle\) (scale regret), and \(R_T^{\mathcal{Z}}\!\left(\frac{u}{\|u\|}\right) \mathrel{\vcenter{:}}=\sum_{t=1}^T \left\langle z_t-\frac{u}{\|u\|},\,\ell_t\right\rangle\) (direction regret).

5.0.0.1 “Scale” lower bound from uOLO.

We observe that one-dimensional online linear optimization (1D-OLO) is embedded in uBLO, if the adversary chooses to provide losses supported on a single coordinate. We may therefore invoke an existing 1D-OLO lower bound, stated below as a mild simplification of Thm. 7 in [34].

Theorem 1 (). For any uBLO algorithm \(\mathcal{A}\) satisfying \(R_T(0)\leq \epsilon\), if \(\|u\|\) is \(\mathcal{F}_0\)-measurable and satisfies \(\|u\|\leq \frac{\epsilon}{\sqrt{T}}10^\frac{T}{4}\), then there exists a sequence \(\ell_1,\dots, \ell_T\) such that \[R_T(u) \geq \frac{1}{3} \cdot \|u\|\sqrt{T\log\left(\tfrac{\|u\|\sqrt{T}}{\epsilon}\right)} \;.\]

Moreover, in the norm-adaptive case the same bound holds with \(\|u\|\) replaced by \(\mathbb{E}\|u\|\), by the same arguments as in [34], replacing the radius parameter (denoted \(R\) therein) by \(\mathbb{E}\|u\|\), since \(\mathbb{E}\|u\|\) is \(\mathcal{F}_0\)-measurable. Lower bound on the direction regret. Because it comes from a hard instance for scale learning, the lower bound from the previous paragraph does not help explain about the \(\sqrt{dT}\) component of the regret upper bounds obtained for the static regret (Thm. [thm:expected-static], Eq. 5 ). It is thus natural to assume that this \(d\)-dependency might come from the direction regret. To support this, we prove the folklore conjecture on the minimax regret for linear bandits constrained in the Euclidean ball, which is thus a result of independent interest. In the context of uBLO, it applies to the direction regret in the scale-direction regret decomposition (Eq. 7 ).

Proof sketch. We follow the outline of the proof of Theorem 24.2 in [8], based on the difficulty of distinguishing problem instances indexed by a parameter \(\theta\) drawn from a small hypercube around the origin, \(\theta\in\{\pm\Delta\}^d\) with \(\Delta=\Theta(T^{-1/2})\). We consider losses generated as \(\ell_t=\theta+\varepsilon_t\) with \(\varepsilon_t\sim\mathcal{N}(0,(2d)^{-1}I_d)\), and then compare pairs of environments \(\theta\) and \(\theta'\) that differ only in the sign of a single coordinate, and relate the resulting regret contributions via a Pinsker/KL argument up to a suitable stopping time. In our feedback model, the KL term involves the ratio \(x_{ti}^2/\|x_t\|^2\), the Gaussian noise being inside the inner product, which we control by noting that \(\|x_t\|\) shouldn’t be bounded away from \(1\) on many rounds, otherwise the learner incurs a linear regret \(\frac{T}{12d}\). Otherwise, \(\|x_t\|\) is typically close to \(1\) and the KL analysis proceeds. The \(1/d\) factor in the noise variance (which is \(1\) in [8]) is exactly what yields the \(\sqrt{dT}\) scaling (rather than \(d\sqrt{T}\)), and a standard randomization argument over \(\theta\) concludes that \(\sup_{\theta} R_T^\text{sto}(\mathcal{A},\theta)\gtrsim \sqrt{dT}\).

The second lower bound follows from an analogous construction, with an added truncation to ensure losses lie in the unit ball. Truncation induces a bias term in the analysis, and alters the information structure. Thus, using a chi-squared concentration bound from [40], we calibrate the noise so that truncation occurs with negligible probability, keeping the model close enough to the Gaussian case for the argument to proceed. We show that this is sufficient to also make the bias become negligible, and the result follows by extending the randomization argument to an adversarial loss sequence. ◻

The complete proof can be found in Appendix 12. The key takeaway of the construction is that the improved \(\sqrt d\) dependence on the Euclidean ball (as opposed to the \(d\) dependence in other geometries) is driven by a tighter noise-variance constraint, making a gap of order \(\sqrt{1/T}\) as hard as a gap of order \(\sqrt{d/T}\) in the model studied in [8].

This lower bound transfers directly to the direction term \(R_T^{\mathcal{Z}}(u/\|u\|)\) in 7 . When \(\|u\|\) is \(\mathcal{F}_0\)-measurable, the decomposition immediately yields a scale-up by \(\|u\|\). Moreover, it also yields a lower bound by \(\mathbb{E}\left[ \|u\| \right]\mathbb{E}\left[ R_T^\mathcal{Z}(u/\|u\|) \right]\) in the norm-adaptive setting, as the adversary can correlate \(\|u\|\) positively with the realized regret. However, we emphasize that this does not yield a lower bound on the full regret \(R_T(u)\), as nothing prevents the scale regret \(R_T^\mathcal{V}(\|u\|)\) from being large and negative.

Conjecture on the lower bound for uBLO. Based on the previous results, we conjecture that the regret bound presented in Equation 5 —obtained by combining a coin bettor with OSMD—is minimax optimal if the comparator norm is oblivious.

Conjecture 1. If the comparator norm is oblivious, the minimax static regret guarantee for uBLO is \[\begin{align} R_T(u)\;=\;\Theta\!\left(\|u\|\sqrt{T\bigl(d\vee \log\|u\|\bigr)}\right)\;. \end{align}\]

We leave a formal proof as an open problem, and briefly explain why it does not follow from the results of this section. The two lower bounds above capture complementary difficulties that can be interpreted through a stochastic-adversary lens: when losses exhibit only a weak average bias of order \(T^{-1/2}\) in some direction, the learner must both (i) control risk and refrain from scaling up too aggressively, and (ii) remain uncertain about the true direction, since the losses could plausibly be pure noise or biased elsewhere.

However, these statements do not directly combine. Theorem 3 only ensures the existence of a loss sequence that forces \(\Omega(\sqrt{dT})\) direction regret, but it does not guarantee that the same sequence is simultaneously hard for scale learning. For example, an algorithm may enforce \(\Omega(\sqrt{dT})\) exploration on every sequence, yet still accumulate enough gains on some sequences to scale up. In fact, it could even use different scales during exploration and exploitation.

Thus, proving the conjecture seems to require constructing a single loss sequence that simultaneously forces \(\Omega(\sqrt{dT})\) regret due to uniform exploration across all directions and prevents overly aggressive exploitation, in the sense of limiting how much the learner can scale up. Achieving this joint property appears non-trivial with standard randomization-hammer techniques, which underlie both lower bounds here.

Norm adaptivity. Our preliminary results do not explain the \(\sqrt d\) gap in the upper bounds between the oblivious and norm-adaptive comparator settings. Whether this gap is intrinsic remains open. More fundamentally, it is still unclear what assumptions on the adversary are appropriate for deriving lower bounds in the norm-adaptive setting.

To illustrate the difficulty, consider the idea of controlling only the expected comparator norm, say \(\mathbb{E}\|u\|=M\). We argue that this assumption is too weak to yield lower bounds that are meaningfully comparable with our upper bounds.

Consider, for simplicity, a policy that enforces uniform exploration with probability at least \(\gamma\) at each round³, and assume that the loss sequence and post-hoc comparator norms can be coupled with the realized learner’s internal randomness. Let \(E\) be the event that all rounds are exploratory, and write \(p\mathrel{\vcenter{:}}=\mathbb{P}(E)\geq \gamma^T\). Then, we can observe that the adversary can both enforce the learner’s expected cumulative reward to be zero⁴, and guarantee that \[\begin{align} \mathbb{E}\|u\|=M \quad \text{and} \quad \mathbb{E}\left[ R_T(u) \right]\geq \mathbb{E}\!\left[\frac{M}{p}\mathbb{I}\!\left(E\right)\cdot T\right]=MT. \end{align}\] This does not contradict comparator-dependent upper bounds such as 5 , since on the event \(E\) the realized comparator norm is \(M/p\), so \(\log\|u\|\) may be of order \(T\). However, the construction is uninformative, as it obtains a linear lower bound only by coupling an exponentially large comparator norm with an exponentially unlikely event. This suggests that sharper restrictions on \(\|u\|\) are needed to characterize the difficulty of uBLO in the norm-adaptive setting.

6 Future Directions↩︎

We leave open several directions for future work. As discussed in 5, novel techniques seem necessary to prove complete lower bounds for unconstrained BLO, both against norm-oblivious and norm-adaptive adversaries. It also remains to understand whether a dimension-dependent gap between the two settings can be avoided.

Our dynamic-regret guarantees also raise a natural question: under what conditions can one obtain non-trivial dynamic regret bounds in bandit settings without prior knowledge of, e.g., \(P_T\)? In many constrained problems, such guarantees are known to be impossible against adaptive adversaries (see for instance, [24]). The uBLO setting may be an extreme regime that evades these lower bounds by removing the domain constraints. An interesting direction is to identify more general assumptions under which \(\sqrt{P_T}\)-type dependencies remain achievable.

Finally, follow-up work could seek to extend our approach to the more general Bandit Convex Optimization setting, in which the losses are arbitrary convex functions.

Acknowledgements↩︎

NCB and AJ acknowledge the financial support from the EU Horizon CL4-2022-HUMAN-02 research and innovation action under grant agreement 101120237, project ELIAS (European Lighthouse of AI for Sustainability). This work was initiated while DB was visiting Università degli Studi di Milano. The visit was supported by Inria Grenoble and UK Research and Innovation (UKRI) under the UK government’s Horizon Europe funding guarantee [grant number EP/Y028333/1]. SI was supported by JSPS KAKENHI Grant Number JP25K03184 and by JST PRESTO, Japan, Grant Number JPMJPR2511.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

7 General Reduction to OLO for Expected Regret↩︎

In this section we detail the proof of our general reduction for expected regret guarantees. The statement is framed in terms of the regret guarantee which holds for a given class of comparator sequences \(\mathcal{U}\). For instance, Algorithms \(\mathcal{A}\) which only make static regret guarantees can also be applied in [prop:expected-reduction] by considering the class of sequences with \(\cmp_1=\ldots=\cmp_T=\cmp\) for some \(\cmp\in\mathbb{R}^d\); algorithms which make dynamic regret guarantees in a bounded domain or under a budget constraint can be captured by the class of sequences such that \(\|\cmp_t\|\le D\) for all \(t\) or sequences satisfying \(\sum_t\|\cmp_t-\cmp_{t-1}\|\le \tau\) for some \(\tau\); algorithms for unconstrained dynamic regret such as [29] can be applied with \(\mathcal{U}\) being the class of all sequences in \(\mathbb{R}^d\).

Proof. The proposition is just a statement of the standard "ghost-iterate" trick. We have that \(\widetilde{None}\) is \(\mathcal{F}_{t-1}\)-measurable and that \(\mathbb{E}\left[ \ell_t-\elltilde_t|\mathcal{F}_{t-1} \right]=0\) via [prop:coordinate-sampling], so \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &= \mathbb{E}\left[ \sum_{t=1}^T\left\langle \ell_t, \wtilde_t-\cmp_t \right\rangle \right]\\ &= \mathbb{E}\left[ \sum_{t=1}^T\left\langle \elltilde_t, \widetilde{-}\cmp_t \right\rangle+\sum_{t=1}^T\left\langle \ell_t-\elltilde_t,\widetilde{-}\cmp_t \right\rangle \right]\\ &\le \mathbb{E}\left[ B_T^\mathcal{A}(\cmp_{1:T},\elltilde_{1:T})+\sum_{t=1}^T-\left\langle \ell_t-\elltilde_t,\cmp_t \right\rangle \right], \end{align}\] where the last line uses the regret guarantee of \(\mathcal{A}\) applied to losses \(\w\mapsto\left\langle \elltilde_t,\w \right\rangle\). Now let \(\what_t\) be the iterates of a "virtual instance" of \(\mathcal{A}\) which is applied to losses \(\w\mapsto\left\langle \ell_t-\elltilde_t, \w \right\rangle\). Note that this virtual instance exists only in the analysis and doesn’t need to be implemented, so there is no issue running the algorithm against the losses \(\w\mapsto\left\langle \ell_t-\elltilde_t,w \right\rangle\), which would otherwise be unobservable to \(\mathcal{A}\). Then, since \(\what_t\) is \(\mathcal{F}_{t-1}\)-measurable, we have via tower-rule that \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &\le \mathbb{E}\left[ B_T^\mathcal{A}(\cmp_{1:T},\elltilde_{1:T}) + \sum_{t=1}^T\left\langle \ell_t-\elltilde_t, \pm\what_t-\cmp_t \right\rangle \right]\\ &\le \mathbb{E}\left[ B_T^\mathcal{A}(\cmp_{1:T},\elltilde_{1:T}) + B_T^\mathcal{A}\left(\cmp_{1:T}, \left(\ell_t-\elltilde_t\right)_{1:T}\right)-\sum_{t=1}^T\left\langle \ell_t-\elltilde_t,\what_t \right\rangle \right]\\ &\le \mathbb{E}\left[ B_T^\mathcal{A}(\cmp_{1:T},\elltilde_{1:T}) + B_T^\mathcal{A}\left(\cmp_{1:T}, \left(\ell_t-\elltilde_t\right)_{1:T}\right)-\sum_{t=1}^T\left\langle \mathbb{E}\left[ \ell_t-\elltilde_t|\mathcal{F}_{t-1} \right],\what_t \right\rangle \right]\\ &\le \mathbb{E}\left[ B_T^\mathcal{A}(\cmp_{1:T},\elltilde_{1:T}) + B_T^\mathcal{A}\left(\cmp_{1:T}, \left(\ell_t-\elltilde_t\right)_{1:T}\right) \right] \end{align}\] ◻

8 Proof of Theorem [thm:expected-static]↩︎

As discussed in 1, the proof of the following result would allow a slightly more general statement which covers a more general partially-oblivious setting, wherein the comparator norm \(\|\cmp\|\) is \(\mathcal{F}_0\) measurable but the loss sequence may be adaptive.

For any \(\cmp\in\mathbb{R}^d\), equipped with [29] with parameter \(\epsilon/d\) guarantees \[\begin{align} \mathbb{E}\left[ R_T(\cmp) \right]&= \widetilde{\mathcal{O}}\left(G\epsilon + \mathbb{E}\left[ d\|\cmp\|\sqrt{\sum_{t=1}^T\|\ell_t\|^2\log\left(\tfrac{d\|\cmp\|\Lambda_T}{G\epsilon}+1\right)} \right]\right), \end{align}\] where \(\Lambda_T=\sqrt{\sum_{t=1}^T\|\ell_t\|^2}\log^2\left(1 + \sum_{t=1}^T\|\ell_t\|^2/G^2\right)\). Moreover, if \(\|\cmp\|\) is \(\mathcal{F}_0\) measurable, then \[\begin{align} \mathbb{E}\left[ R_T(\cmp) \right]&= \widetilde{\mathcal{O}}\left(G\epsilon + \mathbb{E}\left[ \|\cmp\|\sqrt{d\sum_{t=1}^T\mathbb{E}\big[\|\ell_t\|^2|\mathcal{F}_0\big]\log\left(\tfrac{d\|\cmp\|\Lambda_T^+}{G\epsilon}+1\right)} \right]\right). \end{align}\] where \(\Lambda_T^+=G\sqrt{T}\log^2(T+1)\).

Proof. Let \(\mathcal{A}\) be an instance of [29]. Then via [29] we have that for any sequence of linear losses \((\gt)_t\) satisfying \(\|\gt\|\le G\) for all \(t\) and any \(\cmp\in\mathbb{R}^d\), \[\begin{align} \sum_{t=1}^T\left\langle \gt,\widetilde{-}\cmp \right\rangle &= \mathcal{O}\left(\underbrace{\epsilon G + \|\cmp\|\left[\sqrt{V_T\log\left(\frac{\|\cmp\|\sqrt{V_T}\log^2(V_T/G^2)}{G \epsilon}+1\right)}\right]\vee G\log\left(\frac{\|\cmp\|\sqrt{V_T}\log^2(V_T/G^2)}{\epsilon}+1\right)}_{=:B_T(\cmp, \g_{1:T})}\right) \end{align}\] where \(V_T = G^2+\sum_{t=1}^T\|\gt\|^2\). Hence, applying [prop:expected-reduction] and observing that \(\|\elltilde_t\|\le 2d\|\ell_t\|\le 2dG\) and \(\|\ell_t-\elltilde_t\|\le\|\ell_t\|+\|\elltilde_t\|\le (2d+1)\|\ell_t\|\le (2d+1)G\) for all \(t\), letting \(V_T=G^2+\sum_{t=1}^T\|\ell_t\|^2\), \(\widetilde{V}_T=\widetilde{G}^2+\sum_{t=1}^T\|\elltilde_t\|^2\) and \(\widetilde{G} = 3dG\) we have \[\begin{align} \mathbb{E}\left[ R_T(\cmp) \right] &\le \mathbb{E}\left[ B_T(\cmp, \elltilde_{1:T}) + B_T\left(\cmp, (\ell-\elltilde)_{1:T}\right) \right]\nonumber\\ &= \mathcal{O}\left(\mathbb{E}\left[ \epsilon \widetilde{G} + \|\cmp\|\left[\sqrt{\widetilde{V}_T\log\left(\frac{\|\cmp\|\sqrt{\widetilde{V}_T}\log^2(\widetilde{V}_T/\widetilde{G}^2)}{\widetilde{G} \epsilon}+1\right)}\right]\vee\widetilde{G}\log\left(\frac{\|\cmp\|\sqrt{\widetilde{V}_T}\log^2(\widetilde{V}_T/\widetilde{G}^2)}{G\epsilon}+1\right) \right]\right)\nonumber\\ &= \mathcal{O}\left(\mathbb{E}\left[ \epsilon dG + \|\cmp\|\sqrt{\widetilde{V}_T\log\left(\frac{\|\cmp\|\sqrt{V_T}\log^2(V_T/G^2)}{G \epsilon}+1\right)}+dG\|\cmp\|\log\left(\frac{\|\cmp\|\sqrt{V_T}\log^2(V_T/G^2)}{G\epsilon}+1\right) \right]\right)\label{eq:expected-static:1}, \end{align}\tag{8}\] where we’ve used the fact that \(\sum_{t=1}^T\|\ell_t-\elltilde_t\|^2=\mathcal{O}(\sum_{t=1}^T\|\ell_t\|^2+ \|\elltilde_t\|^2)=\mathcal{O}\left(d^2\sum_{t=1}^T\|\ell_t\|^2\right) = \mathcal{O}(d^2V_T)\) via [cor:simple-coordinate-sampling]. Now, if \(\|\cmp\|\) is \(\mathcal{F}_0\)-measurable, we have via tower rule and Jensen’s inequality that \[\begin{align} \mathbb{E}\left[ R_T(\cmp) \right] &= \mathcal{O}\Bigg(\mathbb{E}\Bigg[\epsilon dG + \|\cmp\|\sqrt{\sum_{t=1}^T\mathbb{E}\left[ \|\elltilde_t\|^2|\mathcal{F}_0 \right]\log\left(\frac{\|\cmp\|\Lambda_T^+}{G \epsilon}+1\right)}\\ &\qquad\qquad +dG\|\cmp\|\log\left(\frac{\|\cmp\|\Lambda_T^+}{G\epsilon}+1\right)\Bigg]\Bigg)\\ &= \mathcal{O}\Bigg(\mathbb{E}\Bigg[\epsilon dG + \|\cmp\|\sqrt{d\sum_{t=1}^T\mathbb{E}\left[ \|\ell_t\|^2|\mathcal{F}_0 \right]\log\left(\frac{\|\cmp\|\Lambda_T^+}{G\epsilon}+1\right)}\\ &\qquad\qquad +dG\|\cmp\|\log\left(\frac{\|\cmp\|\Lambda_T^+}{G\epsilon}+1\right)\Bigg]\Bigg), \end{align}\] where we’ve bound \(\sqrt{V_T}\log^2(1+V_T/G^2)\le G\sqrt{T}\log^2(1+T)\eqcolon\Lambda_T^+\) and used [cor:simple-coordinate-sampling] and tower rule to bound \(\mathbb{E}\left[ \|\elltilde_t\|^2|\mathcal{F}_0 \right]=\mathbb{E}\left[ \mathbb{E}\left[ \|\elltilde_t\|^2|\mathcal{F}_{t-1} \right]|\mathcal{F}_0 \right] = \mathcal{O}\left(d\mathbb{E}\Big[\|\ell_t\|^2|\mathcal{F}_0\Big]\right)\). Otherwise, for arbitrary \(\cmp\in\mathbb{R}^d\) (possibly data-dependent), we can naively bound \(\widetilde{V}_T = \mathcal{O}(d^2 V_T)\) to get \[\begin{align} \mathbb{E}\left[ R_T(\cmp) \right]= \mathcal{O}\left(\mathbb{E}\left[ \epsilon dG + d\|\cmp\|\sqrt{ V_T\log\left(\frac{\|\cmp\|\sqrt{V_T}\log^2(V_T/G^2)}{G \epsilon}+1\right)}+dG\|\cmp\|\log\left(\frac{\|\cmp\|\sqrt{V_T}\log^2(V_T/G^2)}{G\epsilon}+1\right) \right]\right). \end{align}\] The bound in the theorem statement follows via change of variables \(d\epsilon\mapsto\epsilon\). ◻

9 Proof of Theorem 2 ↩︎

In this section we prove our result for expected dynamic regret. As in our expected static regret result, here we state a more general form of the theorem which allows for partially-oblivious settings where the comparator sequence \(\cmp_{1:T}\) is oblivious but the loss sequence \(\ell_{1:T}\) may be adaptive, in which case the variance penalties become \(\sum_{t=1}^T\mathbb{E}\left[ \|\ell_t\|^2 |\mathcal{F}_0 \right]\|\cmp_t\|\). Note that this captures the fully-oblivious setting from the statement in the main text as a special case, since when the losses are also \(\mathcal{F}_0\) measurable we have \(\mathbb{E}\left[ \|\ell_t\|^2|\mathcal{F}_0 \right]=\|\ell_t\|^2\) almost-surely. As discussed in the main text, the following result also shows a refined path-length adaptivity, scaling with the log-linear penalties \(\sum_t\|\cmp_t-\cmp_{t-1}\|\log\left(\|\cmp_t-\cmp_{t-1}\|T^3/\epsilon+1\right)\) instead of the worst-case \(P_T\log\left(\max_t\|\cmp_t\|T^3/\epsilon+1\right)\) that would otherwise be obtained via direct application of [29]. As a result, our bound exhibits a dependence on \(\max_t\|\cmp_t\|\) only in the lower-order term, avoiding this worst-case factor entirely in the main term of the bound.

For any sequence \(\cmp_{1:T}=(\cmp_t)_{t=1}^T\) in \(\mathbb{R}^d\), applied with 10 tuned with \(\epsilon/d\) guarantees \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &= \mathcal{O}\left(\mathbb{E}\left[ dG(\epsilon+\max_t\|\cmp_t\|+\Phi_T+P_T^\Phi) + d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|} \right]\right) \end{align}\] where we denote \(\Phi_T=\|\cmp_T\|\log\left(\tfrac{\|\cmp_T\|T}{\epsilon}+1\right)\) and \(P_T^\Phi=\sum_{t=2}^T\|\cmp_t-\cmp_{t-1}\|\log\left(\tfrac{4\|\cmp_t-\cmp_{t-1}\|T^3}{\epsilon}+1\right)\). Moreover, if the comparator sequence \(\cmp_{1:T}\) is \(\mathcal{F}_0\) measurable, then \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &= \mathcal{O}\left(\mathbb{E}\left[ dG(\epsilon+\max_t\|\cmp_t\|+\Phi_T+P_T^\Phi) + \sqrt{d(\Phi_T+P_T^\Phi)\sum_{t=1}^T\mathbb{E}\big[\|\ell_t\|^2\big|\mathcal{F}_0\big]\|\cmp_t\|} \right]\right) \end{align}\]

Proof. Given any sequence \(f_1,\ldots,f_T\) of \(G\)-Lipschitz convex losses, 10 guarantees ([thm:dynamic-base-olo-tuned]) that \[\begin{align} R_T^\mathcal{A}(\cmp_{1:T}) &= \sum_{t=1}^Tf_t(\widetilde{)}-f_t(\cmp_t) \le 4G(\epsilon \left|\mathcal{S}\right|+M+\Phi_T+P_T^\Phi) + 2\sqrt{2(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|}, \end{align}\] where \(\gt\in\partial f_t(\widetilde{)}\), \(M=\max_t\|\cmp_t\|\), \(\mathcal{S}=\left\{\eta_i=\tfrac{2^i}{GT}\wedge\tfrac{1}{G}:i=0,1,\ldots\right\}\), and we denote \(\Phi_T=\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)\) and \(P_T^\Phi=\sum_{t=2}^T\Phi\left(\|\cmp_t-\cmp_{t-1}\|,\tfrac{4T^3}{\epsilon}\right)\) for \(\Phi(x,\lambda)=x\log\left(\lambda x+1\right)\). Hence, applying this algorithm to the \(3dG\) Lipschitz loss sequences \((\elltilde_t)_t\) and \((\ell_t-\elltilde_t)_t\) and plugging into [prop:expected-reduction], we have \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &= \mathcal{O}\Bigg(\mathbb{E}\Bigg[ dG(\epsilon \left|\mathcal{S}\right|+M+\Phi_T+P_T^\Phi) + \sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|} \\ &\qquad + \sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\elltilde_t-\ell_t\|^2\|\cmp_t\|}\Bigg] \Bigg). \end{align}\] Now via [cor:simple-coordinate-sampling], we have that \(\|\elltilde_t\|^2\le 4d^2\|\ell_t\|^2\) and likewise, \(\|\ell_t-\elltilde_t\|^2\le 2\|\ell_t\|^2+2\|\elltilde_t\|^2=\mathcal{O}(d^2\|\ell_t\|^2)\), so we can always bound \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &= \mathcal{O}\Bigg(\mathbb{E}\Bigg[ dG(\epsilon \left|\mathcal{S}\right|+M+\Phi_T+P_T^\Phi) + d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|} \Bigg] \Bigg). \end{align}\] On the other hand, if the comparator sequence is \(\mathcal{F}_0\) measurable, we can apply Jensen’s inequality and tower rule (twice) to get \[\begin{align} \mathbb{E}\left[ R_T(\cmp_{1:T}) \right] &\le \mathcal{O}\Bigg(\mathbb{E}\Bigg[dG(\epsilon \left|\mathcal{S}\right|+M+\Phi_T+P_T^\Phi) + \sqrt{(\Phi_T+P_T^\Phi)\mathbb{E}\left[ \sum_{t=1}^T\|\elltilde_t\|^2\Big|\mathcal{F}_0 \right]\|\cmp_t\|}\\ &\qquad + \sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\mathbb{E}\left[ \|\elltilde_t-\ell_t\|^2\Big|\mathcal{F}_0 \right]\|\cmp_t\|}\Bigg]\Bigg)\\ &\le \mathcal{O}\left(\mathbb{E}\left[ dG(\epsilon \left|\mathcal{S}\right|+M+\Phi_T+P_T^\Phi) + \sqrt{d(\Phi_T+P_T^\Phi)\sum_{t=1}^T\mathbb{E}\Big[\|\ell_t\|^2\Big|\mathcal{F}_0\Big]\|\cmp_t\|} \right]\right), \end{align}\] where we’ve applied [cor:simple-coordinate-sampling] to bound \(\mathbb{E}\left[ \|\elltilde_t\|^2|\mathcal{F}_{t-1} \right]=\mathcal{O}(d\|\ell_t\|^2)\) and \(\mathbb{E}\left[ \|\elltilde_t-\ell_t\|^2|\mathcal{F}_{t-1} \right]=\mathcal{O}\big(\mathbb{E}\big[\|\ell_t\|^2+\|\elltilde_t\|^2\big]\big)=\mathcal{O}(d\|\ell_t\|^2)\). Combining the bounds for the two cases gives the stated result. ◻

10 High-probability Guarantees↩︎

10.1 Reduction to OLO↩︎

In this section, we prove [prop:high-prob-redux], which shows that with high-probability, the regret of scales with the regret of the OLO algorithm \(\mathcal{A}\) deployed against the loss estimates \(\elltilde_t\), plus some additional stability terms. The result is framed in terms of a \((\mathcal{F}_t)_{t=0}^T\)-adapted comparator sequence, though in 10.3.1 we show that the results generalize straightforwardly to the fully-adaptive case using the same ghost-iterate trick as [prop:expected-reduction].

In the following theorem, we note that the lower-order \(G\omega\sqrt{\log\left(16/\delta\right)}\) can be replaced by a \(\delta\)-independent penalty of \(G\epsilon\) by setting \(\omega=\epsilon/\sqrt{\log\left(16/\delta\right)}\), and the resulting trade-off can be bound in terms of \(\log\left(1/\delta\right)\) since the remaining \(\omega\)-dependent terms are doubly-logarithmic in \(1/\omega\) and can be naively bound as \(\log\left(\frac{4}{\delta}\log\tfrac{C}{\omega}\right)=\mathcal{O}\left(\log\left(\tfrac{4\log (C/\epsilon)+2\log\left(1/\delta\right)}{\delta}\right)\right)=\mathcal{O}\left(\log\left(\tfrac{\log\left(C/\epsilon\right)}{\delta}\right)\right)\) using \(\log\left(1/\delta\right)\le \frac{1}{\delta}\) for \(\delta>0\). Hence, in the main text we drop the lower-order dependence on \(G\omega\sqrt{\log\left(16/\delta\right)}\) but leave \(\omega>0\) free here for generality.

Proof. Recalling that 1 plays \(\wtilde_t=\widetilde{+} H_t^{-\frac{1}{2}}s_t\) with \(s_t\) drawn uniformly from \(\left\{\pm e_i: i\in[d]\right\}\), we have \[\begin{align} R_T(\cmp_{1:T}) &= \sum_{t=1}^T\left\langle \ell_t, \wtilde_t-\cmp_t \right\rangle\nonumber\\ &= \sum_{t=1}^T\left\langle \ell_t, \widetilde{-}\cmp_t \right\rangle + \sum_{t=1}^T\left\langle \ell_t, H_t^{-\frac{1}{2}} s_t \right\rangle\nonumber\\ &= \underbrace{\sum_{t=1}^T\left\langle \elltilde_t, \widetilde{-}\cmp_t \right\rangle}_{\widetilde{R}_T^\mathcal{A}(\cmp_{1:T})} +\underbrace{\sum_{t=1}^T\left\langle \ell_t-\elltilde_t,\widetilde{\right}\rangle}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};} +\underbrace{\sum_{t=1}^T\left\langle \elltilde_t-\ell_t,\cmp_t \right\rangle}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};} + \underbrace{\sum_{t=1}^T\left\langle \ell_t, H_t^{-\frac{1}{2}} s_t \right\rangle}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};} \label{eq:high-prob-redux:initial}. \end{align}\tag{9}\] We proceed by bounding each of the noise terms \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};\), \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};\), and \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};\) with high probability.

Bounding \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};\): Let \(X_t=\left\langle \ell_t-\elltilde_t,\widetilde{\right}\rangle\) and observe by [prop:coordinate-sampling], tower rule, and the fact that \(\widetilde{None}\) is \(\mathcal{F}_{t-1}\) measurable we have \[\begin{align} \mathbb{E}\left[ X_t|\mathcal{F}_{t-1} \right]=\mathbb{E}\left[ \left\langle \ell_t-\elltilde_t,\widetilde{\right}\rangle|\mathcal{F}_{t-1} \right]=0. \end{align}\] Moreover, again by [prop:coordinate-sampling] we have \[\begin{align} \mathbb{E}\left[ X_t^2|\mathcal{F}_{t-1} \right] &\le \mathbb{E}\left[ \|\ell_t-\elltilde_t\|^2\|\widetilde{\|}^2|\mathcal{F}_{t-1} \right]\\ &\le \|\widetilde{\|}^2\left(\mathbb{E}\left[ \|\elltilde_t\|^2|\mathcal{F}_{t-1} \right]-\|\ell_t\|^2\right) \le 2d\|\widetilde{\|}^2\|\ell_t\|^2\\ &\le 2dG^2\|\widetilde{\|}^2. \end{align}\] and likewise, \[\begin{align} \left|X_t\right| &\le \|\ell_t-\elltilde_t\|\|\widetilde{\|} \le (\|\ell_t\|+\|\elltilde_t\|)\|\widetilde{\|} \le (1+2d)\|\ell_t\|\|\widetilde{\|}\le3dG\|\widetilde{\|} \end{align}\] almost-surely. Therefore, applying [thm:wt-concentration-scalar] with \(\sigma_t^2=2dG^2\|\widetilde{\|}^2\) and \(b_t=3dG\|\widetilde{\|}\), we have that with probability at least \(1-\delta\), \[\begin{align} \sum_{t=1}^T \left\langle \ell_t-\elltilde_t,\widetilde{\right}\rangle&\le 2G\sqrt{ 2d\sum_{t=1}^T\|\widetilde{\|}^2 \log\!\left( \frac{4}{\delta} \left[ \log_+\left( G\sqrt{2d\sum_{t=1}^T \|\widetilde{\|}^2/(2\nu^2)} \right)+2 \right]^2 \right)}\\ &\qquad+ 8\,\max\!\left(\nu,\max_{t\le T} 3dG\|\widetilde{\|}\right) \log\left( \frac{28}{\delta} \left[ \log_{+}\left( 3dG\max_t\|\widetilde{\|}/\nu\right)+2\right]^2\right) \intertext{ and hence setting \nu=3dG\omega, } &\le 3G\sqrt{ d\sum_{t=1}^T\|\widetilde{\|}^2 \log\!\left( \frac{4}{\delta} \left[ \log_+\left( \frac{\sqrt{2d}G}{3\sqrt{2}dG \omega}\sqrt{\sum_{t=1}^T \|\widetilde{\|}^2} \right)+2 \right]^2 \right)}\\ &\qquad+ 24dG\,\max\!\left(\omega,\max_{t\le T} \|\widetilde{\|}\right) \log\left( \frac{28}{\delta} \left[ \log_{+}\left( \max_t\|\widetilde{\|}/\omega\right)+2\right]^2\right)\\ &\le 3G\sqrt{ d\sum_{t=1}^T\|\widetilde{\|}^2 \log\!\left( \frac{4}{\delta} \left[\log_+\left( \frac{\sqrt{\sum_{t=1}^T \|\widetilde{\|}^2}}{\omega}\right)+2 \right]^2 \right)}\\ &\qquad+ 24dG\,\max\!\left(\omega,\max_{t\le T} \|\widetilde{\|}\right) \log\left( \frac{28}{\delta} \left[\log_{+}\left( \frac{\max_t\|\widetilde{\|}}{\omega}\right)+2\right]^2\right)\\ &=:\Sigma_T(\w_{1:T}) \end{align}\]

Bounding \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};\): For \(\mathcal{F}_t\)-measurable \(\cmp_t\), we could have correlations between \(\cmp_t\) and \(\ell_t-\elltilde_t\), so we first shift the comparator sequence by one index: \[\begin{align} \sum_{t=1}^T\left\langle \elltilde_t-\ell_t,\cmp_t \right\rangle &= \sum_{t=1}^T\left\langle \elltilde_t-\ell_t, \cmp_{t-1} \right\rangle + \sum_{t=1}^T\left\langle \elltilde_t-\ell_t, \cmp_t-\cmp_{t-1} \right\rangle \\ &\le \sum_{t=1}^T\left\langle \elltilde_t-\ell_t, \cmp_{t-1} \right\rangle + 3dG P_T \end{align}\] where we’ve used [cor:simple-coordinate-sampling] to bound \(\|\ell_t-\elltilde_t\| \le G + \|\elltilde_t\|\le G(1+2d)\le 3dG\), and defined \(\cmp_0=\mathbf{0}\). Now applying the same arguments as \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};\), the first summation can be bound with probability at least \(1-\delta\) as \[\begin{align} \sum_{t=1}^T\left\langle \elltilde_t-\ell_t,\cmp_{t-1} \right\rangle &\le 3G\sqrt{d\sum_{t=1}^T\|\cmp_{t-1}\|^2\log\left(\frac{4}{\delta}\left[\log_{+}\left(\frac{\sqrt{\sum_{t=1}^T\|\cmp_{t-1}\|^2}}{2\omega}\right)+2\right]^2\right)}\nonumber\\ &\qquad +16dG \max\left\{\omega,\max_{t\le T-1}\|\cmp_t\|\right\} \log\left(\frac{28}{\delta}\left[\log_{+}\left(\frac{\max_{t\le T-1}\|\cmp_t\|}{\omega}\right)+2\right]^2\right)\\ &\le 3G\sqrt{d\sum_{t=1}^T\|\cmp_t\|^2\log\left(\frac{4}{\delta}\left[\log_{+}\left(\frac{\sqrt{\sum_{t=1}^T\|\cmp_t\|^2}}{2\omega}\right)+2\right]^2\right)}\nonumber\\ &\qquad +24dG \max\left\{\omega,\max_{t\le T}\|\cmp_t\|\right\} \log\left(\frac{28}{\delta}\left[\log_{+}\left(\frac{\max_{t\le T}\|\cmp_t\|}{\omega}\right)+2\right]^2\right)\\ &= \Sigma_T(\cmp_{1:T}), \end{align}\] hence, with probability at least \(1-\delta\), \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B}; &\le \Sigma_T(\cmp_{1:T}) + 3dGP_T. \end{align}\]

Bounding \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};\): By definition we have \(H_t^{-\frac{1}{2}}=\sqrt{d}[\|\widetilde{\|}\vee\varepsilon] I_d\) and \(X_t:=\left\langle \ell_t, H_t^{-\frac{1}{2}}s_t \right\rangle = \sqrt{d}[\|\widetilde{\|}\vee\varepsilon]\left\langle \ell_t, s_t \right\rangle\). Hence, since \(s_t\) is drawn uniform random from \(\left\{\pm e_i:i\in[d]\right\}\), we have \(\mathbb{E}\left[ X_t|\mathcal{F}_{t-1} \right]= 0\) and \[\begin{align} \mathbb{E}\left[ X_t^2|\mathcal{F}_{t-1} \right] &= \mathbb{E}\left[ d[\|\widetilde{\|}^2\vee\varepsilon^{2}] \ell_t^\top \st\st^\top\ell_t|\mathcal{F}_{t-1} \right] = d[\|\widetilde{\|}^2\vee\varepsilon^{2}]\|\ell_t\|^2\frac{1}{d} = [\|\widetilde{\|}^2\vee\varepsilon^{2}]\|\ell_t\|^2\le[\|\widetilde{\|}^2\vee\varepsilon^{2}]G^2 \end{align}\] and \(\left|X_t\right| \le \sqrt{d}[\|\widetilde{\|}\vee\varepsilon]\|\ell_t\|\le \sqrt{d}G(\|\widetilde{\|}\vee\varepsilon)\) almost surely. Thus, we can again apply [thm:wt-concentration-scalar] with \(\sigma_t^2=G^2[\|\widetilde{\|}^2\vee\varepsilon^2]\) and \(b_t=\sqrt{d}[\|\widetilde{\|}\vee\varepsilon]\) to get \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C}; &\le 2G\sqrt{\sum_{t=1}^T(\|\widetilde{\|}^2+\varepsilon^2)\log\left(\frac{4}{\delta}\left[\log_+\left(G\sqrt{\sum_{t=1}^T\frac{\|\widetilde{\|}^2+\varepsilon^2}{2\nu^2} }\right)+2\right]^2\right)}\\ &\qquad +8\max\left\{\nu, \sqrt{d}G[\max_t\|\widetilde{\|}\vee\varepsilon]\right\} \log\left(\frac{28}{\delta}\left[\log_+\left(\frac{\sqrt{d}G[\max_t\|\widetilde{\|}\vee\varepsilon]}{\nu}\right)+2\right]^2\right)\\ \intertext{and recalling \varepsilon^2=\omega^2/ T,} &\le 2G\sqrt{\omega^2 + \sum_{t=1}^T\|\widetilde{\|}^2\log\left(\frac{4}{\delta}\left[\log_+\left(G\sqrt{\frac{\omega^2+\sum_{t=1}^T\|\widetilde{\|}^2}{2\nu^2}}\right)+2\right]^2\right)}\\ &\qquad +8\max\left\{\nu, \sqrt{d}G[\max_t\|\widetilde{\|}\vee\tfrac{\omega}{\sqrt{T}}]\right\} \log\left(\frac{28}{\delta}\left[\log_+\left(\frac{\sqrt{d}G\big[\max_t\|\widetilde{\|}\vee\tfrac{\omega}{\sqrt{T}}\big]}{\nu}\right)+2\right]^2\right)\\ \intertext{and setting \nu=\sqrt{d}G\omega,} &\le 2G\sqrt{\omega^2 + \sum_{t=1}^T\|\widetilde{\|}^2\log\left(\frac{4}{\delta}\left[\log_+\left(\sqrt{\frac{\omega^2+\sum_{t=1}^T\|\widetilde{\|}^2}{2 d\omega^2}}\right)+2\right]^2\right)}\\ &\qquad +8\max\left\{\sqrt{d}G\omega, \sqrt{d}G[\max_t\|\widetilde{\|}\vee\tfrac{\omega}{\sqrt{T}}]\right\} \log\left(\frac{28}{\delta}\left[\log_+\left(\frac{\sqrt{d}G\big[\max_t\|\widetilde{\|}\vee\tfrac{\omega}{\sqrt{T}}\big]}{\sqrt{d}G\omega}\right)+2\right]^2\right)\\ &\le \underbrace{2G\sqrt{2\left[\omega^2 \vee\sum_{t=1}^T\|\widetilde{\|}^2\right]\log\left(\frac{4}{\delta}\left[\log_+\left(\sqrt{\frac{\omega^2\vee\sum_{t=1}^T\|\widetilde{\|}^2}{d\omega^2}}\right)+2\right]^2\right)}}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut V};}\\ &\qquad +8\sqrt{d}G\max\left\{\omega, [\max_t\|\widetilde{\|}\vee\tfrac{\omega}{\sqrt{T}}]\right\} \log\left(\frac{28}{\delta}\left[\log_+\left(\frac{\sqrt{d}G\big[\max_t\|\widetilde{\|}\vee\tfrac{\omega}{\sqrt{T}}\big]}{\sqrt{d}G\omega}\right)+2\right]^2\right)\\ &\le \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut V}; +8\sqrt{d}G\max\left\{\omega, \max_t\|\widetilde{\|}\right\} \log\left(\frac{28}{\delta}\left[\log_+\left(\frac{\max_t\|\widetilde{\|}}{\omega}\right)+2\right]^2\right), \end{align}\] where the last line observes that if \(\max_t\|\widetilde{\|}\le \omega/\sqrt{T}\) then the \(\log_+\) in the last term simplifies to \(\log_+\left(\tfrac{1}{\sqrt{T}}\right)=0\). Now consider two cases: first, if \(\sum_{t=1}^T\|\widetilde{\|}^2\le \omega^2\), we also have \(\max_t\|\widetilde{\|}\le \omega\) and we can bound \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut V}; &\le 2G\omega\sqrt{2\log\left(\frac{4}{\delta}\left[\log_+\left(\sqrt{\frac{1}{d}}\right)+2\right]^2\right)}\\ &\le 2G\omega\sqrt{2\log\left(\frac{16}{\delta}\right)} \end{align}\] and otherwise, when \(\sum_{t=1}^T\|\widetilde{\|}^2\ge \omega^2\), we also have \(\tfrac{\omega}{\sqrt{T}}\le \sqrt{\sum_{t=1}^T\|\widetilde{\|}^2/T}\le \max_t\|\widetilde{\|}\) and \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut V}; &\le 2G\sqrt{2\sum_{t=1}^T\|\widetilde{\|}^2\log\left(\frac{4}{\delta}\left[\log_+\left(\sqrt{\frac{\sum_{t=1}^T\|\widetilde{\|}^2}{d\omega^2}}\right)+2\right]^2\right)}\\ \end{align}\] hence, combining these two cases, with probability at least \(1-\delta\) we have \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C}; &\le \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut V}; +8\sqrt{d}G\max\left\{\omega, \max_t\|\widetilde{\|}\right\} \log\left(\frac{28}{\delta}\left[\log_+\left(\frac{\max_t\|\widetilde{\|}}{\omega}\right)+2\right]^2\right)\\ &\le 2G\omega \sqrt{2\log\left(\tfrac{16}{\delta}\right)}+ 2G\sqrt{2\sum_{t=1}^T\|\widetilde{\|}^2\log\left(\frac{4}{\delta}\left[\log_+\left(\sqrt{\frac{\sum_{t=1}^T\|\widetilde{\|}^2}{d\omega^2}}\right)+2\right]^2\right)}\\ &\qquad +8\sqrt{d}G\max\left\{\omega, \max_t\|\widetilde{\|}\right\} \log\left(\frac{28}{\delta}\left[\log_+\left(\frac{\max_t\|\widetilde{\|}}{\omega}\right)+2\right]^2\right)\\ &\le 2G\omega \sqrt{2\log\left(\tfrac{16}{\delta}\right)}+\Sigma_T(\w_{1:T}) \end{align}\]

Thus, combining the bounds for \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};\), \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};\), and \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};\), we have with probability at least \(1-3\delta\) \[\begin{align} R_T(\cmp_{1:T}) &\le \widetilde{R}_T^\mathcal{A}(\cmp_{1:T}) + 2\Sigma_T(\w_{1:T})+ \Sigma_T(\cmp_{1:T}) + 3dGP_T+2G\omega\sqrt{2\log\left(\tfrac{16}{\delta}\right)} \end{align}\] ◻

10.2 High-probability Static Regret Guarantees↩︎

Figure 5: Sub-exponential Noisy Gradients with Optimistic Online Learning

In this section we briefly review the approach developed by [28] for developing high-probability guarantees in unconstrained settings.

In unconstrained settings, the usual Martingale concentration arguments alone are not enough to control the bias terms \(\sum_{t=1}^T\left\langle \ell_t-\elltilde_t,\widetilde{\right}\rangle\), since they will lead to terms on the order of \(\widetilde{\mathcal{O}}(\sqrt{\sum_{t=1}^T\|\widetilde{\|}^2})\), which could be arbitrarily large in an unbounded domain. The main idea is of [28] is to add an additional composite penalty \(\varphi_t\) to the update, which introduces an extra term \(\sum_{t=1}^T\varphi_t(\cmp)-\varphi_t(\widetilde{)}\) into the regret bound; with this, the goal is to choose \(\varphi_t\) in such a way that \(-\sum_{t=1}^T\varphi_t(\widetilde{)}\) is large enough to cancel with the \(\|\widetilde{\|}\)-dependent terms left over from the Martingale concentration argument, while also ensuring that \(\sum_{t=1}^T\varphi_t(\cmp)\) is not too large. [28] provide a Huber-like penalty which satisfies both of these conditions (see [lemma:dynamic-huber]).

The difficulty with the above approach is that by introducing the composite penalty, we change the OLO learner’s feedback: on round \(t\), the learner’s feedback becomes \(\tgt=\gt+\nabla\varphi_t(\widetilde{)}\) instead of just \(\gt\in\partial\ell_t(\widetilde{)}\), and the \(\nabla\varphi_t(\widetilde{)}\) dependence would itself lead to \(\|\widetilde{\|}\)-dependent penalties in the bound. This issue can be fixed using an optimistic update by setting hints \(h_t=\nabla\varphi_t(\widetilde{)}\), so that the usual \(\sum_{t=1}^T\|\tgt\|^2\) penalties in the final bound become \(\sum_{t=1}^T\|\tgt-h_t\|^2=\sum_{t=1}^T\|\gt\|^2\). Note that setting \(h_t\) this way requires solving an implicit equation for \(\widetilde{=}\xt-\yt\nabla\varphi_t(\widetilde{)}\). The full pseudocode is provided in 5, and it makes the following guarantee. ⁵

theoremOptimisticHeavyTailed [28] Suppose \(\left\{\gt\right\}\) are stochastic subgradients such that \(\mathbb{E}\left[ \gt \right]\in\partial\ell_{t}(\widetilde{)}\), \(\|\gt\|\le b\), and \(\mathbb{E}\left[ \|\gt\|^{2}|\widetilde{\right}]\le \sigma\) almost surely for all \(t\). Set the constants for \(\varphi_{t}(\w)\) as \[\begin{align} c_{1}&=2\sigma\sqrt{\log\left(\frac{32}{\delta}\left[\log\left(2^{T+1}\right)+2\right]^{2}\right)},~c_{2}=32b\log\left(\frac{224}{\delta}\left[\log\left(1+\frac{b}{\sigma}2^{T+2}\right)+2\right]^{2}\right)\\ p_{1}&=2,~p_{2}=\log\left(T\right),~\alpha_{1}=\epsilon/c_{1},~\alpha_{2}=\epsilon\sigma/(4b(b+H)), \end{align}\] where \(H=c_{1}p_{1}+c_{2}p_{2}\), and \(\|\nabla\varphi_{t}(\widetilde{)}\|\le H\). Then with probability at least \(1-\delta\), 5 guarantees \[\begin{align} R_{T}(\cmp)= \widetilde{\mathcal{O}}\left[\epsilon \log\left(T/\delta\right)+b\|\cmp\|\log\left(T/\delta\right)+\|\cmp\|\sigma\sqrt{T\log\left(T/\delta\right)}\right] \end{align}\]

Note that via [prop:coordinate-sampling], we have that \(\|\elltilde_t\|^2\le 4d^2G^2\), and \(\mathbb{E}\left[ \|\elltilde_t\|^2|\widetilde{\right}]\le 2dG^2\). Hence, to achieve static regret guarantees we can immediately apply the algorithm of [28] to get the following guarantee. The only modification we need to make is that we should multiply the \(c_1\) and \(c_2\) in [thm:optimistic-heavy-tailed] by 2, to account for the fact that we have an extra \(\|\widetilde{\|}\)-dependent concentration penalty coming from our perturbation \(\left\langle \ell_t,H_t^\frac{1}{2}s_t \right\rangle\).

10.3 High-Probability Dynamic Regret Guarantees↩︎

Figure 6: Dynamic Algorithm for Heavy-tailed Noise

In this section we provide an algorithm, detailed in 6, which achieves the bound stated in [thm:high-prob-dynamic]. The algorithm can be understood as a special case of a more general algorithm characterized in 8, which we develop separately in 11.1. The approach is similar to the one described in the previous section: the algorithm adds additional composite penalties \(\varphi_t\) to the update, which lead to additional factors of \(\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}\) in the regret, which are used to cancel out the \(\|\widetilde{\|}\)-dependent penalties from [prop:high-prob-redux]. In particular, 6 is constructed by combining several instances of a base algorithm (7), each applied with different learning rates \(\eta\) and with the Huber-like penalties discussed in 11.1.1, which ensure a negative penalty of \(\sum_{t=1}^T-\varphi_t(\widetilde{)} =\widetilde{\mathcal{O}}\Big(-\big(\sum_{t=1}^T\|w_t\|^p\big)^{1/p}\Big))\) appears in the bound at the expense of a problem-dependent penalty of \(\sum_{t=1}^T\varphi_t(\cmp_t)=\widetilde{\mathcal{O}}\Big(\big(\sum_{t=1}^T\|\cmp_t\|^p\big)^{1/p}\Big)\). Applying with 6 as the base algorithm then leads to the following high-probability regret guarantee in the uBLO setting.

Let \(\mathcal{A}\) be an instance of 6 applied with \(L=2dG\), \(\sigma^2=4dG^2\), and hyperparameters \[\begin{align} c_1&=6G\sqrt{d\left|\mathcal{S}\right|\log\left(\frac{4}{\delta}\left[T + \log_+\left(\tfrac{4\epsilon\sqrt{\left|\mathcal{S}\right|}}{\omega}\right)\right]^2\right)}\\ c_2&=48 dG\log\left(\frac{28}{\delta}\left[T+\log_+\left(\tfrac{2\epsilon\sqrt{\left|\mathcal{S}\right|}}{\omega}\right)\right]^2\right)\\ \alpha_1&=\epsilon,\qquad \alpha_2=\omega,\qquad p_1=2,\qquad p_2=\log\left(T+1\right). \end{align}\] Let \(\cmp_{1:T}=(\cmp_1,\ldots,\cmp_T)\) be an arbitrary \((\mathcal{F}_t)_{t=0}^T\)-adapted sequence in \(\mathbb{R}^d\). Then with probability at least \(1-4\delta\), applied with \(\mathcal{A}\) guarantees \[\begin{align} R_T(\cmp_{1:T}) &\le \min\Bigg\{8d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|},~ 8G\sqrt{2M(\Phi_T+P_T^\Phi)}\left[\sqrt{dT}+d\sqrt{\log\left(1/\delta\right)}\right]\Bigg\}\\ &\qquad +2G\sqrt{d\sum_{t=1}^T\|\cmp_t\|^2\log\left(\frac{4}{\delta}\left[\log_{+}\left(\frac{\sqrt{\sum_{t=1}^T\|\cmp_t\|^2}}{\omega}\right)+2\right]^2\right)}\nonumber\\ &\qquad +4c_1 \sqrt{\left(\epsilon^2+\sum_{t=1}^T\|\cmp_t\|^2\right)\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\epsilon^2}\right)}\\ &\qquad +3 c_2 \log^2(T+1)\max\left\{\omega, M\right\}\left[\log_+\left( \tfrac{3M}{\omega}\right)+3\right]\\ &\qquad +24dG \max\left\{\omega,\max_{t\le T}\|\cmp_t\|\right\} \log\left(\frac{28}{\delta}\left[\log_{+}\left(\frac{\max_{t\le T}\|\cmp_t\|}{\omega}\right)+2\right]^2\right)\\ &\qquad + 32(dG+H)(\epsilon\left|\mathcal{S}\right| + M+\Phi_T+P_T^\Phi)\\ &\qquad +c_1\epsilon+c_2\omega + 3dGP_T+2G\omega\sqrt{2\log\left(\tfrac{16}{\delta}\right)}\\ \end{align}\] where \(M=\max_t\|\cmp_t\|\), \(\Phi_T=\|\cmp_T\|\log\left(\tfrac{\|\cmp_T\|T}{\epsilon}+1\right)\) and \(P_T^\Phi=\sum_{t=2}^T\|\cmp_t-\cmp_{t-1}\|\log\left(\tfrac{4\|\cmp_t-\cmp_{t-1}\|T^3}{\epsilon}+1\right)\).

Proof. By [prop:high-prob-redux], we have that with probability at least \(1-3\delta\), \[\begin{align} R_T(\cmp_{1:T}) &\le \widetilde{R}_T^\mathcal{A}(\cmp_{1:T}) + 2\Sigma_T(\w_{1:T})+ \Sigma_T(\cmp_{1:T}) + 3dGP_T+2G\omega\sqrt{2\log\left(\tfrac{16}{\delta}\right)}\label{eq:sub-exponential-dynamic-1} \end{align}\tag{10}\] where \(\widetilde{R}_T^\mathcal{A}(\cmp_{1:T})=\sum_{t=1}^T\left\langle \elltilde_t,\widetilde{-}\cmp_t \right\rangle\) and \[\begin{align} \Sigma_T(\x_{1:T}) &:= 3G\sqrt{ d\sum_{t=1}^T\|\xt\|^2 \log\!\left( \frac{4}{\delta} \left[\log_+\left( \frac{\sqrt{\sum_{t=1}^T \|\xt\|^2}}{\omega}\right)+2 \right]^2 \right)}\nonumber\\ &\qquad+ 24dG\,\max\!\left(\omega,\max_{t\le T} \|\xt\|\right) \log\left( \frac{28}{\delta} \left[\log_{+}\left( \frac{\max_t\|\xt\|}{\omega}\right)+2\right]^2\right)~.\label{eq:high-prob-dynamic:Sigma} \end{align}\tag{11}\] To bound the regret \(\widetilde{R}_T^\mathcal{A}(\cmp_{1:T})\), we note that 6 is an instance of the algorithm characterized in 8 applied with a specific composite penalties \(\varphi_t\) and with Lipschitz constant \(L=2dG\). In particular, for each \(\eta\in\mathcal{S}\), let \(\mathcal{A}_\eta\) denote an instance of 7 applied with composite penalty \(\varphi_t^\eta(w)=r_t^\eta(w;c_1,\alpha_1,p_1)+r_t^\eta(w;c_2,\alpha_2,p_2)\) (for parameters \(\left\{c_1,c_2,\alpha_1,\alpha_2,p_1,p_2\right\}\) to be determined) where \(r_t^\eta\) is defined by \[\begin{align} r_{t}^\eta(\w;c,\alpha,p) &= \begin{cases} c\left(p\|\w\|-(p-1)\|\widetilde{^}\eta\|\right)\frac{\|\widetilde{^}\eta\|^{p-1}}{\left(\alpha^{p}+\sum_{s=1}^{t}\|\ws^\eta\|^{p}\right)^{1-1/p}} &\text{if }\|\w\|>\|\widetilde{^}\eta\|\\ c\frac{\|\w\|^{p}}{\left(\alpha^{p}+\sum_{s=1}^{t}\|\widetilde{^}\eta\|^{p}\right)^{1-1/p}} &\text{if }\|\w\|\le \|\widetilde{^}\eta\| \end{cases}, \end{align}\] and \(\widetilde{^}\eta\) is the output of \(\mathcal{A}_\eta\) on round \(t\). 6 is constructed by combining the outputs of the \(\mathcal{A}_\eta\) by playing \(\widetilde{=}\sum_{\eta\in\mathcal{S}}\widetilde{^}\eta\) on round \(t\), and its regret guarantee is given by 8. Now observe that via [cor:simple-coordinate-sampling], we have that \(\|\elltilde_t\|^2\le 4d^2\|\ell_t\|^2\) almost-surely, so we can apply 8 with Lipschitz constant \(L=2dG\ge \|\elltilde_t\|\) to bound \[\begin{align} \widetilde{R}_T^\mathcal{A}(\cmp_{1:T}) &\le 16(2dG+H)\left(\epsilon\left|\mathcal{S}\right|+M+\Phi(\|\cmp_T\|,\tfrac{T}{\epsilon})+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right)+4\sqrt{\left[\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right]\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|}\\ &\qquad +\max_{\eta^*\in\mathcal{S}}\sum_{\eta\in\mathcal{S}}\sum_{t=1}^T\varphi_t^\eta\Big(\cmp_t\mathbb{I}(\eta=\eta^*)\Big)-\varphi_t^{\eta}(\widetilde{^}\eta), \end{align}\] where \(M=\max_t\|\cmp_t\|\), \(\Phi(x,\lambda)=x\log\left(\lambda x+1\right)\), and \(P_T^\Phi(\lambda)=\sum_{t=2}^T\Phi(\|\cmp_t-\cmp_{t-1}\|,\lambda)\). The terms in the last line can be bound by observing that for any \(\eta\in\mathcal{S}\) we have \(\varphi_t^\eta(0)=0\) and that via [lemma:comparator-varphi] we have \[\begin{align} \sum_{t=1}^T\varphi_t^\eta(\cmp_t) &\le 4c_1 \sqrt{\left(\alpha_1^2+\sum_{t=1}^T\|\cmp_t\|^2\right)\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\alpha_1^2}\right)}\\ &\qquad +3 c_2 \log^2(T+1)\max\left\{\alpha_2, M\right\}\left[\log_+\left(3 M/\alpha_2\right)+3\right]. \end{align}\] Plugging these in above yields \[\begin{align} \widetilde{R}_T^\mathcal{A}(\cmp_{1:T}) &\le 4\sqrt{\left[\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right]\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|}\\ &\qquad +4c_1 \sqrt{\left(\alpha_1^2+\sum_{t=1}^T\|\cmp_t\|^2\right)\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\alpha_1^2}\right)}\\ &\qquad +16(2dG+H)\left(\epsilon\left|\mathcal{S}\right| + M+\Phi(\|\cmp_T\|,\tfrac{T}{\epsilon})+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right)\\ &\qquad +3 c_2 \log^2(T+1)\max\left\{\alpha_2, M\right\}\left[\log_+\left(3 M/\alpha_2\right)+3\right]\\ &\qquad -\sum_{\eta\in\mathcal{S}}\sum_{t=1}^T\varphi_t(\widetilde{^}\eta), \end{align}\] and plugging this back into the full regret bound in 10 we have \[\begin{align} R_T(\cmp_{1:T}) &\le 16(2dG+H)\left(\epsilon \left|\mathcal{S}\right|+ M+\Phi_T+ P_T^\Phi\right)\\ &\qquad + 4\sqrt{\left[\Phi_T+P_T^\Phi\right]\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|}\\ &\qquad +4c_1 \sqrt{\left(\alpha_1^2+\sum_{t=1}^T\|\cmp_t\|^2\right)\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\alpha_1^2}\right)}\\ &\qquad+ 3 c_2 \log^2(T+1)\max\left\{\alpha_2, M\right\}\left[\log_+\left(3 M/\alpha_2\right)+3\right]\\ &\qquad + \Sigma_T(\cmp_{1:T}) + 3dGP_T+2\omega G\sqrt{2\log\left(\tfrac{16}{\delta}\right)}\\ &\qquad + 2\Sigma_T(\w_{1:T})-\sum_{\eta\in\mathcal{S}}\sum_{t=1}^T\varphi_t^\eta(\widetilde{^}\eta). \end{align}\] Hence, The main terms to control are the \(\|\widetilde{\|}\)-dependent terms in the last line, \(2\Sigma_{T}(\w_{1:T})-\sum_{\eta\in\mathcal{S}}\sum_{t=1}^T\varphi_t^\eta(\widetilde{^}\eta)\), and \(4\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|}\) from the regret of \(\mathcal{A}\). We begin by bounding the latter term, and in particular we will bound it in two different ways. First, by [cor:simple-coordinate-sampling], we have that \(\|\elltilde_t\|^2\le 4d^2\|\ell_t\|^2\) almost-surely, so \[\begin{align} 4\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|} &\le 8d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|}. \end{align}\] Alternatively, we can first bound \(\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|\le M\sum_{t=1}^T\|\elltilde_t\|^2\) and then apply a concentration inequality to bound the summation with high-probability. In particular, by [28], we have that with probability at least \(1-\delta\) \[\begin{align} 4\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|} &\le 4\sqrt{M(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\elltilde_t\|^2}\\ &\le 4\sqrt{M(\Phi_T+P_T^\Phi)\left(\frac{3}{2} (2dG^2)T + \frac{5}{3}(4d^2G^2)\log\left(1/\delta\right)\right)}\\ &\le 4G\sqrt{M(\Phi_t+P_T^\Phi)\left(3dT + \frac{20}{3}d^2\log\left(1/\delta\right)\right)}\\ &\le 4G\sqrt{dM(\Phi_T+P_T^\Phi)\left(3T+ 8d\log\left(1/\delta\right)\right)}\\ &\le 8G\sqrt{2dM(\Phi_T+P_T^\Phi)\left[T+ d\log\left(1/\delta\right)\right]}. \end{align}\] Hence, combining these two bounds, we have that with probability \(1-\delta\), \[\begin{align} 4\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\elltilde_t\|^2\|\cmp_t\|} &\le \min\Bigg\{8d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|},\nonumber\\ &\qquad\qquad 8G\sqrt{2dM(\Phi_T+P_T^\Phi)\left[T+ d\log\left(1/\delta\right)\right]}\Bigg\}\nonumber\\ &\le \min\Bigg\{8d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|},\nonumber\\ &\qquad\qquad 8G\sqrt{2M(\Phi_T+P_T^\Phi)}\left[\sqrt{dT}+d\sqrt{\log\left(1/\delta\right)}\right]\Bigg\}\label{eq:ellt-sqr-bound} \end{align}\tag{12}\]

Next, we simplify the terms \(\Sigma(\w_{1:T})\). First, notice that by Cauchy-Schwarz inequality, it holds that \(\sum_{\eta\in\mathcal{S}}\|\widetilde{^}\eta\|\le \sqrt{\left|\mathcal{S}\right|\sum_{\eta\in\mathcal{S}}\|\widetilde{^}\eta\|^2}\), and so \[\begin{align} \Bigg\|\sum_{\eta\in\mathcal{S}}\widetilde{^}\eta\Bigg\|^2 &\le \left(\sum_{\eta\in\mathcal{S}}\|\widetilde{^}\eta\|\right)^2 \le \left|\mathcal{S}\right|\sum_{\eta\in\mathcal{S}}\|\widetilde{^}\eta\|^2, \end{align}\] so using this and the fact that \(\sqrt{a+b}\le \sqrt{a}+\sqrt{b}\), we can break \(\Sigma_T(\w_{1:T})\) apart as

\[\begin{align} \Sigma_T(\w_{1:T}) &\le \sum_{\eta\in\mathcal{S}}3G\sqrt{ d\left|\mathcal{S}\right|\sum_{t=1}^T\|\widetilde{^}\eta\|^2 \log\!\left( \frac{4}{\delta} \left[\log_+\left( \frac{\sqrt{\left|\mathcal{S}\right|\max_{\eta\in\mathcal{S}}\sum_{t=1}^T \|\widetilde{^}\eta\|^2}}{\omega}\right)+2 \right]^2 \right)}\nonumber\\ &\qquad+ \sum_{\eta\in\mathcal{S}}16dG\,\max\!\left(\omega,\max_{t\le T} \|\widetilde{^}\eta\|\right) \log\left( \frac{28}{\delta} \left[\log_{+}\left( \frac{\max_{\eta\in\mathcal{S},t\le T}\sqrt{\left|\mathcal{S}\right|}\|\widetilde{^}\eta\|}{\omega}\right)+2\right]^2\right)\nonumber\\ &\overset{(a)}{\le} \sum_{\eta\in\mathcal{S}}3G\sqrt{ d\left|\mathcal{S}\right|\sum_{t=1}^T\|\widetilde{^}\eta\|^2 \log\!\left( \frac{4}{\delta} \left[\log_+\left( \frac{\epsilon\sqrt{\left|\mathcal{S}\right|\sum_{t=1}^T 2^{2(t-1)}}}{\omega}\right)+2 \right]^2 \right)}\nonumber\\ &\qquad+ \sum_{\eta\in\mathcal{S}}24dG\,\max\!\left(\omega,\max_{t\le T} \|\widetilde{^}\eta\|\right) \log\left( \frac{28}{\delta} \left[\log_{+}\left( \frac{\epsilon\sqrt{\left|\mathcal{S}\right|} 2^{T-1}}{\omega}\right)+2\right]^2\right)\nonumber\\ &\overset{(b)}{\le} \sum_{\eta\in\mathcal{S}}3G\sqrt{ d\left|\mathcal{S}\right|\sum_{t=1}^T\|\widetilde{^}\eta\|^2 \log\!\left( \frac{4}{\delta} \left[\log_+\left( \frac{\epsilon\sqrt{\left|\mathcal{S}\right|4^T}}{\omega}\right)+2 \right]^2 \right)}\nonumber\\ &\qquad+ \sum_{\eta\in\mathcal{S}}24dG\,\max\!\left(\omega,\max_{t\le T} \|\widetilde{^}\eta\|\right) \log\left( \frac{28}{\delta} \left[\log_{+}\left( \frac{\epsilon\sqrt{\left|\mathcal{S}\right|} 2^{T-1}}{\omega}\right)+2\right]^2\right)\nonumber\\ &\overset{(c)}{\le} \sum_{\eta\in\mathcal{S}}3G\sqrt{ d\left|\mathcal{S}\right|\sum_{t=1}^T\|\widetilde{^}\eta\|^2 \log\!\left( \frac{4}{\delta} \left[T + \log_+\left( \frac{4\epsilon\sqrt{\left|\mathcal{S}\right|}}{\omega}\right) \right]^2 \right)}\nonumber\\ &\qquad+ \sum_{\eta\in\mathcal{S}}24dG\,\max\!\left(\omega,\max_{t\le T} \|\widetilde{^}\eta\|\right) \log\left( \frac{28}{\delta} \left[T+\log_+\left(\tfrac{2\sqrt{\left|\mathcal{S}\right|}\epsilon}{\omega}\right)\right]^2\right)\label{ejnficgd} \end{align}\tag{13}\] where \((a)\) uses the fact that the base-algorithms \(\mathcal{A}_\eta\) satisfy a comparator-adaptive guarantee, and hence have \(\|\widetilde{^}\eta\|\le \epsilon 2^{t-1}\) for any \(\widetilde{^}\eta\) via 1, and \((b)\) uses \(\sum_{t=1}^T a^{t-1} = (a^T-1)/(a-1)\le a^T\) for \(a\ge 2\) and \((c)\) uses \(\log_+\left(c 2^{T-2}\right)+2\le (T-2)\log\left(e\right)+\log_+(c)+2=T+\log_+(c)\) for \(c>0\). Therefore, we set each \(\varphi_t^\eta(w)\) using two components, one to cancel each of these summations. First, observe that with \(r_t^\eta(w;c_1,\alpha_1,2)\) in [lemma:dynamic-huber] (defined w.r.t. \(\widetilde{^}\eta\)), we have \[\begin{align} \sum_{t=1}^Tr_t^\eta(\widetilde{^}\eta;c_1,\alpha_1,2) \ge c_1\sqrt{\alpha_1^2 + \sum_{t=1}^T\|\widetilde{^}\eta\|^2}-c_1\alpha_1, \end{align}\] and so if we set \(c_1=6G\sqrt{d\left|\mathcal{S}\right|\log\left(\frac{4}{\delta}\left[T + \log_+\left(\frac{4\epsilon\sqrt{\left|\mathcal{S}\right|}}{\omega}\right)\right]^2\right)}\) we will cancel the first part of \(2\Sigma_T^\eta(\w_{1:T}^\eta)\) for each \(\eta\).

To cancel the second term of \(2\Sigma_T^\eta(\w_{1:T}^\eta)\) in 11 , suppose we add a term \(r_t^\eta(\w;c_2,\alpha_2,p_2)\) with \(p_2=\log\left(T+1\right)\). Then again using [lemma:dynamic-huber], we have \[\begin{align} \sum_{t=1}^Tr_t^\eta(\widetilde{^}\eta; c_2,\alpha_2,p_2) &\ge c_2\left(\alpha_2^{p_2}+\sum_{t=1}^T\|\widetilde{^}\eta\|^{p_2}\right)^\frac{1}{p}-c_2\alpha_2\ge c_2\max\left\{\alpha_2,\max_t\|\widetilde{^}\eta\|\right\} -\alpha_2c_2 \end{align}\] Therefore, setting \(c_2=48 dG\log\Big(\frac{28}{\delta}\Big[T+\log_+\left(\tfrac{2\epsilon\sqrt{\left|\mathcal{S}\right|}}{\omega}\right)\Big]^2\Big)\) and \(\alpha_2=\omega\), we cancel the remaining part of \(2\Sigma_T^\eta(\w_{1:T})\) for each \(\eta\). Finally, plugging this all back into the regret bound and expanding \(\Sigma_T(\cmp_{1:T})\) as in 11 , and choosing \(\alpha_1=\epsilon\), we have that with probability at least \(1-4\delta\) \[\begin{align} R_T(\cmp_{1:T}) &\le \min\Bigg\{8d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|},~ 8G\sqrt{2M(\Phi_T+P_T^\Phi)}\left[\sqrt{dT}+d\sqrt{\log\left(1/\delta\right)}\right]\Bigg\}\\ &\qquad +2G\sqrt{d\sum_{t=1}^T\|\cmp_t\|^2\log\left(\frac{4}{\delta}\left[\log_{+}\left(\frac{\sqrt{\sum_{t=1}^T\|\cmp_t\|^2}}{\omega}\right)+2\right]^2\right)}\nonumber\\ &\qquad +4c_1 \sqrt{\left(\epsilon^2+\sum_{t=1}^T\|\cmp_t\|^2\right)\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\epsilon^2}\right)}\\ &\qquad +3 c_2 \log^2(T+1)\max\left\{\omega, M\right\}\left[\log_+\left( \tfrac{3M}{\omega}\right)+3\right]\\ &\qquad +24dG \max\left\{\omega,\max_{t\le T}\|\cmp_t\|\right\} \log\left(\frac{28}{\delta}\left[\log_{+}\left(\frac{\max_{t\le T}\|\cmp_t\|}{\omega}\right)+2\right]^2\right)\\ &\qquad + 32(dG+H)(\epsilon\left|\mathcal{S}\right| + M+\Phi_T+P_T^\Phi)\\ &\qquad +c_1\epsilon+c_2\omega + 3dGP_T+2G\omega\sqrt{2\log\left(\tfrac{16}{\delta}\right)}\\ &\le \widetilde{O}\Bigg( \min\left\{d\sqrt{(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\ell_t\|^2\|\cmp_t\|},~ G\sqrt{M(\Phi_T+P_T^\Phi)}\left[\sqrt{dT}+d\sqrt{\log\left(1/\delta\right)}\right]\right\}\\ &\qquad +G\sqrt{d\sum_{t=1}^T\|\cmp_t\|^2\log\left(T/\delta\right)} +dG(\epsilon + M+\Phi_T+P_T^\Phi)\log\left(T/\delta\right) \Bigg) \end{align}\] where we’ve used that \(H=c_1p_1+c_2p_2 = \widetilde{\mathcal{O}}(dG)\) after hiding poly-logarithmic factors. ◻

10.3.1 Extension to Arbitrary Comparator Sequences↩︎

Our high-probability guarantees in the main text are framed in terms of \((\mathcal{F}_t)_{t=0}^T\)-adapted comparator sequences \((\cmp_t)_{t\in[T]}\). However, the same results can be obtained up to constant factors for arbitrary comparator sequences as well by using the same ghost-iterate trick used in [prop:expected-reduction], though the statement becomes a bit more complicated to state because the “ghost-iterates” enter into the proposition statement. The following lemma provides a generalization of [prop:high-prob-redux] to arbitrary comparator sequences.

propositionGeneralHighProbRedux Let \(\mathcal{A}\) be an OLO learner and let \(\widetilde{\in}\mathbb{R}^d\) denote its output on round \(t\). Let \(\widehat\mathcal{A}\) be a virtual instance of \(\mathcal{A}\), appearing only in the analysis, and let \(\what_t\in\mathbb{R}^d\) denote its output on round \(t\). Let \(\delta\in(0,1/3]\), \(\omega>0\), and \(\varepsilon^2 = \omega^2/T\), and let \(\cmp_{1:T}=(\cmp_t)_{t=1}^T\) be an arbitrary sequence in \(\mathbb{R}^d\). Then with \(H_t = \frac{1}{d[\|\widetilde{\|}^2\vee\varepsilon^{2}]}I_d\) guarantees that with probability at least \(1-3\delta\), \[\begin{align} R_T(\cmp_{1:T}) &\le \underbrace{\sum_{t=1}^T\left\langle \elltilde_t,\widetilde{-}\cmp_t \right\rangle}_{\widetilde{R}_T^\mathcal{A}(\cmp_{1:T})} + 2\Sigma_T(\w_{1:T})+ \underbrace{\sum_{t=1}^T\left\langle \ell_t-\elltilde_t, \what_t-\cmp_t \right\rangle}_{\widehat R_T^{\widehat\mathcal{A}}(\cmp_{1:T})}+\Sigma_T(\what_{1:T}) + 2G\omega\sqrt{2\log\left(\tfrac{16}{\delta}\right)} \end{align}\] where \(\Sigma_T:(\mathbb{R}^d)^T\to \mathbb{R}_{\ge0}\) is defined as in [prop:high-prob-redux].

Proof. Following a similar argument to [prop:high-prob-redux], we can decompose \[\begin{align} R_T(\cmp_{1:T}) &= \sum_{t=1}^T\left\langle \ell_t, \wtilde_t-\cmp_t \right\rangle\nonumber\\ &= \sum_{t=1}^T\left\langle \ell_t, \widetilde{-}\cmp_t \right\rangle + \sum_{t=1}^T\left\langle \ell_t, H_t^\frac{1}{2}s_t \right\rangle\nonumber\\ &= \underbrace{\sum_{t=1}^T\left\langle \elltilde_t, \widetilde{-}\cmp_t \right\rangle}_{\widetilde{R}_T^\mathcal{A}(\cmp_{1:T})} +\sum_{t=1}^T\left\langle \ell_t-\elltilde_t,\widetilde{\right}\rangle +\sum_{t=1}^T\left\langle \elltilde_t-\ell_t,\cmp_t \right\rangle + \sum_{t=1}^T\left\langle \ell_t, H_t^{-\frac{1}{2}} s_t \right\rangle\\ &= \widetilde{R}_T^\mathcal{A}(\cmp_{1:T}) +\underbrace{\sum_{t=1}^T\left\langle \ell_t-\elltilde_t,\widetilde{\right}\rangle}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};} +\underbrace{\sum_{t=1}^T\left\langle \ell_t-\elltilde_t,\what_t \right\rangle}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};} +\underbrace{\sum_{t=1}^T\left\langle \elltilde_t-\ell_t,\what_t-\cmp_t \right\rangle}_{\widehat R_T^{\widehat\mathcal{A}}(\cmp_{1:T})} +\underbrace{\sum_{t=1}^T\left\langle \ell_t, H_t^{-\frac{1}{2}} s_t \right\rangle}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};} \label{gpzjlctu}. \end{align}\tag{14}\] We proceed by bounding each of the noise terms \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};\), \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};\), and \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};\) with high probability. The terms \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};\) and \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};\) can be bound exactly the same as in [prop:high-prob-redux]. The new term, \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};\), can be bound using the exact same argument as \(\tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};\) but replacing \(\widetilde{None}\) with \(\what_{t}\). Overall, we get that with probability at least \(1-3\delta\) \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A}; &\le \Sigma(\w_{1:T}),\quad \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};\le \Sigma(\what_{1:T}),\quad \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut C};\le 2G\omega\sqrt{2\log(\tfrac{16}{\delta})} + \Sigma_{T}(\w_{1:T}), \end{align}\] for an overall bound of \[\begin{align} R_T(\cmp_{1:T})\le R_T^\mathcal{A}(\cmp_{1:T})+2\Sigma_T(\w_{1:T}) + \widehat R_T^{\widehat\mathcal{A}}(\cmp_{1:T}) + \Sigma_T(\what_{1:T}) + 2G\omega\sqrt{2\log(\tfrac{16}{\delta})} \end{align}\] with probability at least \(1-3\delta\). ◻

Now with the above reduction in hand, proof of the main result for arbitrary comparator sequences follows using a similar strategy to [thm:high-prob-dynamic]: we choose \(\mathcal{A}\) which provides an additional composite penalty \(\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}\), such that \(\sum_{t=1}^T\varphi_t(\widetilde{)} \ge \Sigma_T(\w_{1:T})\) while also ensuring that \(\sum_{t=1}^T\varphi_t(\cmp_t)\) is controlled. Importantly, the virtual version of \(\mathcal{A}\) will likewise also generate such a term capable of cancelling \(\Sigma_T(\what_{1:T})\). The main difference is that we should increase the Lipschitz constant to \(L=3dG\), so that we have both \(\|\elltilde_t\|\le 2dG\le L\) and \(\|\ell_t-\elltilde_t\|\le \|\ell_t\|+\|\elltilde_t\|\le G+2dG\le 3dG\le L\) (via [cor:simple-coordinate-sampling]), in which case we can apply the same arguments as in [thm:high-prob-dynamic] to bound each of the terms. The same arguments then lead to a bound that matches [thm:high-prob-dynamic] up to constant factors. An analogous argument can be made for our high-probability static regret bound to generalize the result to an arbitrary fixed comparator norm \(\|\cmp\|\) but using the algorithm of [28] as the base algorithm \(\mathcal{A}\).

11 Results for Online Convex Optimization↩︎

In this section we present auxiliary results for OCO which drive our dynamic regret guarantees for uBLO in 3.2 and 4. We present these results separately here since these results are of independent interest in OCO.

In particular, in 11.1 we show how a combination of composite regularization and implicit optimistic updates can introduce additional terms into the regret \(\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}\) which can be used as a means to control the stability of the iterates \(\|\widetilde{\|}\). This is crucial in our high-probability results in 4, where controlling the bias of our loss estimates leads to penalties scaling with \(\widetilde{\mathcal{O}}(\sqrt{\sum_t \|\widetilde{\|}^2})\). Our approach is inspired by the strategy used by [28], though our results require additional care to extend the approach to dynamic regret while also preserving the adaptivity to the individual comparator norms, which the optimistic reductions of [28], [39] cannot account for. In 11.2 we provide a refinement of the dynamic base algorithm of [29] which simplifies the analysis and exposes a more fine-grained measure of comparator variability than the \(P_T\log\left(MT/\epsilon+1\right)\) presented in the original work, while also avoiding the worst-case factors of \(M=\max_t\|\cmp_t\|\) from appearing in the main terms of the bound.

Throughout this section, we focus on a general OCO setting in which the losses \((f_{t})_{t\in[T]}\) are arbitrary \(L\)-Lipschitz convex functions. We denote the regret as \[\begin{align} R_T(\cmp_{1:T})=\sum_{t=1}^Tf_{t}(\widetilde{)}-f_{t}(\cmp_t) \end{align}\] and, when relevant, we denote the regret of a given algorithm \(\mathcal{A}\) by \(R_T^\mathcal{A}(\cmp_{1:T})\).

11.1 Online Learning with Optimistic Composite-penalty Cancellation↩︎

Figure 7: Online Learning with Optimistic Composite-Penalty Cancellation

In this section we develop an algorithm for dynamic regret which introduces additional penalties to the regret of \(\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}\), which will let us cancel out the \(\|\widetilde{\|}\)-dependent terms from [prop:high-prob-redux]. The key difficulty is that this changes the OLO learner’s feedback to be \(\gt + \nabla\varphi_t(\widetilde{)}\) which is problematic in our application of interest because the gradients of the composite penalty in 17 would again depend on \(\|\widetilde{\|}\). Fortunately, we can remove this factor from the feedback by using an optimistic update by setting the optimistic hint to be \(h_t=\nabla\varphi_t(\widetilde{)}\), so that \(\gt+\nabla\varphi_t(\widetilde{)}-h_t=\gt\). Note that the optimistic reduction in 7 incorporates the hints \(h_t=\eta\nabla\varphi_t(\widetilde{)}\) by playing \(\widetilde{=} \xt-\yt\eta h_t\), so when \(h_t=\nabla\varphi_t(\widetilde{)}\) this generally requires solving a fixed-point equation. We assume that \(\varphi_t\) is chosen in such a way that the solution to this fixed-point equation exists, and we note that this is indeed the case when \(\varphi_t\) is set according to the Huber-like penalty in 11.1.1, which is used in our high-probability results for uBLO (see [28]).

The following theorem shows that we can extend the per-comparator dynamic regret guarantee of [29] to include additional terms \(\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}\) in the bound without otherwise changing the original regret guarantee significantly. We will instantiate the result more concretely in [thm:optimistic-dynamic-base].

theoremDynamicOptimism Let \(\mathcal{A}_x\) and \(\mathcal{A}_y\) be online learning algorithms defined on convex domains \(\mathcal{W}_x=\mathbb{R}^d\) and \(\mathcal{W}_y=\mathbb{R}_{\ge0}\) respectively and let \(\widetilde{^}{\mathcal{A}_x}\in\mathcal{W}_x\) and \(\widetilde{^}{\mathcal{A}_y}\in\mathcal{W}_y\) denote their respective outputs on round \(t\). Suppose that for each \(z\in\left\{x,y\right\}\), \(\mathcal{A}_z\) guarantees that for any sequence of \(L\)-Lipschitz convex loss functions \(\widetilde{f}_1,\ldots,\widetilde{f}_T\) on \(\mathcal{W}_z\) and any sequence \(\cmp_{1:T}\) in \(\mathcal{W}_z\) that \[\begin{align} R_T^{\mathcal{A}_z}(\cmp_{1:T}) &\le A_{T}^{\mathcal{A}_z}(\cmp_{1:T})+\frac{P_T^{\mathcal{A}_z}(\cmp_{1:T})}{2\eta}+\frac{\eta}{2}\sum_{t=1}^T\|\tgt\|^2\|\cmp_t\|, \end{align}\] where \(\tgt\in\partial\widetilde{f}_t(\widetilde{^}{\mathcal{A}_z})\), for some non-negative functions \(A_T^{\mathcal{A}_z}:(\mathcal{W}_z)^T\to\mathbb{R}_{\ge0}\) and \(P_T^{\mathcal{A}_z}:(\mathcal{W}_z)^T\to\mathbb{R}_{\ge0}\). Then for any sequence of convex \(L\)-Lipschitz losses \(f_1,\ldots,f_T\) on \(\mathbb{R}^d\) and any comparator sequence \(\cmp_{1:T}=(\cmp_1,\ldots,\cmp_T)\) in \(\mathbb{R}^d\), 7 guarantees \[\begin{align} R_T(\cmp_{1:T}) &\le A_T^{\mathcal{A}_x}(\cmp_{1:T}) +A_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})+ \frac{P_T^{\mathcal{A}_x}(\cmp_{1:T})+P_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\| \\ &\qquad +\sum_{t=1}^T\varphi_t(\cmp_t) - \varphi_t(\widetilde{)} \end{align}\] where \(\gt\in\partial f_{t}(\widetilde{)}\).

Proof. We have by convexity of \(f_{t}\) that \[\begin{align} R_T(\cmp_{1:T}) &\le \sum_{t=1}^T\left\langle \gt,\widetilde{-}\cmp_{t} \right\rangle\\ &= \sum_{t=1}^T\left\langle \gt,\widetilde{-}\cmp_{t} \right\rangle\pm\left[\varphi_{t}(\widetilde{)}-\varphi_{t}(\cmp_{t})\right]\nonumber\\ &\le \underbrace{\sum_{t=1}^T\left\langle \gt+\nabla\varphi_{t}(\widetilde{)},\widetilde{-}\cmp_{t} \right\rangle}_{=:\widetilde{R}_{T}(\cmp_{1:T})} + \sum_{t=1}^T\varphi_{t}(\cmp_{t})-\varphi_{t}(\widetilde{)}\label{eq:dynamic-optimism:initial} \end{align}\tag{15}\] where \(\gt\in\partial f_{t}(\widetilde{)}\) and the last line uses convexity of \(\varphi_{t}\). Focusing on the first term, denote \(\tgt = \gt+\nabla\varphi_{t}(\widetilde{)}\) and observe that for \(\widetilde{=}\xt -\eta\yt\nabla\varphi_{t}(\widetilde{)}\) and any arbitrary sequence \(\mathring{y}_{1:T}\) in \(\mathbb{R}_{\ge0}\) we have \[\begin{align} \widetilde{R}_{T}(\cmp_{1:T}) &= \sum_{t=1}^T\left\langle \tgt,\widetilde{-}\cmp_{t} \right\rangle = \sum_{t=1}^T\left\langle \tgt, \xt-\cmp_{t} \right\rangle+\sum_{t=1}^T\left\langle -\eta\gt, \nabla\varphi_{t}(\widetilde{)} \right\rangle\yt\\ &= R_{T}^{\mathcal{A}_{x}}(\cmp_{1:T})+\sum_{t=1}^T\left(\left\langle -\eta\tgt, \nabla\varphi_{t}(\widetilde{)} \right\rangle\yt-\left\langle -\eta\tgt,\nabla\varphi_{t}(\widetilde{)} \right\rangle\mathring{y}_{t}\right)-\sum_{t=1}^T\left\langle \eta\tgt,\nabla\varphi_{t} \right\rangle\mathring{y}_{t}\\ &= R_{T}^{\mathcal{A}_{x}}(\cmp_{1:T})+R_T^{\mathcal{A}_y}(\mathring{y}_{1:T})-\eta\sum_{t=1}^T\left\langle \tgt,\nabla\varphi_{t}(\widetilde{)} \right\rangle\mathring{y}_{t}\\ &\overset{(a)}{=} R_{T}^{\mathcal{A}_{x}}(\cmp_{1:T})+R_T^{\mathcal{A}_y}(\mathring{y}_{1:T})+\frac{\eta}{2} \sum_{t=1}^T\left[\|\tgt-\nabla\varphi_t(\widetilde{)}\|^2-\|\tgt\|^2-\|\nabla\varphi_t(\widetilde{)}\|^2\right]\mathring{y}_t\\ &\overset{(b)}{=} R_{T}^{\mathcal{A}_{x}}(\cmp_{1:T})+R_T^{\mathcal{A}_y}(\mathring{y}_{1:T})+\frac{\eta}{2} \sum_{t=1}^T\left[\|\gt\|^2-\|\tgt\|^2-\|\nabla\varphi_t(\widetilde{)}\|^2\right]\left|\mathring{y}_t\right| \end{align}\] where \((a)\) uses the elementary identity \(-2\left\langle x,y \right\rangle=\|x-y\|^2-\|x\|^2-\|y\|^2\) and \((b)\) recalls that \(\tgt=\gt+\nabla\varphi_t(\widetilde{)}\) so that \(\tgt -\nabla\varphi_t(\widetilde{)} = \gt\), and writes \(\mathring{y}_t=\left|\mathring{y}_t\right|\) for \(\mathring{y}\ge 0\). Now from the regret guarantee of \(\mathcal{A}_x\) applied to the linear losses \(\w\mapsto\left\langle \tgt,\w \right\rangle\), we have \[\begin{align} R_T^{\mathcal{A}_x}(\cmp_{1:T})\le A_T^{\mathcal{A}_x}(\cmp_{1:T}) + \frac{P_T^{\mathcal{A}_x}(\cmp_{1:T})}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|\tgt\|^2\|\cmp_t\|, \end{align}\] for some \(A_T^{\mathcal{A}_x}(\cmp_{1:T}), P_T^{\mathcal{A}_x}(\cmp_{1:T})\ge0\) and \(0<\eta\le \frac{1}{L+H}\le \frac{1}{\|\tgt\|}\). Then choosing \(\mathring{y}_t = \|\cmp_t\|\) for all \(t\), we have \[\begin{align} \widetilde{R}_T(\cmp_{1:T}) &\le A_T^{\mathcal{A}_x}(\cmp_{1:T}) + \frac{P_T^{\mathcal{A}_x}(\cmp_{1:T})}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|\tgt\|^2\|\cmp_t\| +R_T^{\mathcal{A}_y}(\mathring{y}_{1:T})\\ &\qquad +\frac{\eta}{2} \sum_{t=1}^T\left[\|\gt\|^2-\|\tgt\|^2-\|\nabla\varphi_t(\widetilde{)}\|^2\right]\|\cmp_t\|\\ &\le A_T^{\mathcal{A}_x}(\cmp_{1:T}) + \frac{P_T^{\mathcal{A}_x}(\cmp_{1:T})}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\| +R_T^{\mathcal{A}_y}(\mathring{y}_{1:T}) -\frac{\eta}{2} \sum_{t=1}^T\|\nabla\varphi_t(\widetilde{)}\|^2\|\cmp_t\|. \end{align}\] Likewise, from the regret guarantee of \(\mathcal{A}_y\) applied to the linear losses \(y\mapsto \left\langle -\eta\tgt,\nabla\varphi_t(\widetilde{)} \right\rangle y\), we get \[\begin{align} R_T^{\mathcal{A}_y}(\mathring{y}_{1:T}) &\le A_T^{\mathcal{A}_y}(\cmp_{1:T}) + \frac{P_T^{\mathcal{A}_y}(\mathring{y}_{1:T})}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T\left\langle \eta\tgt,\nabla\varphi_t(\widetilde{)} \right\rangle^2 \left|\mathring{y}_t\right|\\ &\le A_T^{\mathcal{A}_y}(\cmp_{1:T}) + \frac{P_T^{\mathcal{A}_y}(\mathring{y}_{1:T})}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T\|\nabla\varphi_t(\widetilde{)}\|^2 \|\cmp_t\|, \end{align}\] where we’ve used \(\eta\|\tgt\|\le 1\), so plugging this back in above we have \[\begin{align} \widetilde{R}_T(\cmp_{1:T}) &\le A_T^{\mathcal{A}_x}(\cmp_{1:T}) +A_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})+ \frac{P_T^{\mathcal{A}_x}(\cmp_{1:T})+P_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|\qedhere \end{align}\] ◻

For concreteness, we instantiate this result with the algorithm characterized in [thm:dynamic-base-simple] for both \(\mathcal{A}_x\) on \(\mathbb{R}^d\) and \(\mathcal{A}_y\) on \(\mathbb{R}_{\ge0}\) to immediately get the following result.

theoremDynamicBase Under the same assumptions as [thm:dynamic-optimism], let both \(\mathcal{A}_x\) and \(\mathcal{A}_y\) be instances of 9 with \(\eta\le 1/L\) and \(k\ge 4\), applied on \(\mathbb{R}^d\) and \(\mathbb{R}_{\ge0}\) respectively. Then for any sequence of \(L\)-Lipschitz convex functions \(f_1,\ldots,f_T\) and any sequence \(\cmp_{1:T}=(\cmp_1,\ldots,\cmp_T)\) in \(\mathbb{R}^d\), 7 guarantees \[\begin{align} R_T(\cmp_{1:T}) &\le 2(L+H)(\epsilon+\max_t\|\cmp_t\|) + \frac{16 \left[\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right]}{2\eta}+\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|\\ &\qquad +\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}, \end{align}\] where \(\gt\in\partial f_{t}(\widetilde{)}\) and we define \(\Phi(x,\lambda)=x\log\left(\lambda x +1\right)\) and \(P_T^\Phi(\lambda)=\sum_{t=2}^T\Phi(\|\cmp_t-\cmp_{t-1}\|,\lambda)\).

Proof. The algorithm characterized by [thm:dynamic-base-simple] satisfies the condition of [thm:dynamic-optimism] with \(A_T^{\mathcal{A}_x}(\cmp_{1:T}) \le L(\epsilon+\max_t\|\cmp_t\|)\) and \(P_T^{\mathcal{A}_x}(\cmp_{1:T})=8\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+8P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\), where \[\begin{align} \Phi(x,\lambda)=x\log\left(\lambda x+1\right),\text{ and }P_T^\Phi(\lambda)=\sum_{t=2}^T\Phi(\|\cmp_t-\cmp_{t-1}\|,\lambda) \end{align}\] Likewise, \(A_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})=A_T^{\mathcal{A}_x}(\cmp_{1:T})\) and using reverse triangle inequality we have for any \(t\), \(\left|\|\cmp_t\|-\|\cmp_{t-1}\|\right|\le \|\cmp_t-\cmp_{t-1}\|\), so \(P_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})\le P_T^{\mathcal{A}_x}(\cmp_{1:T})\). Thus, applying [thm:optimistic-dynamic-base], we have \[\begin{align} R_T(\cmp_{1:T}) &\le A_T^{\mathcal{A}_x}(\cmp_{1:T}) +A_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})+ \frac{P_T^{\mathcal{A}_x}(\cmp_{1:T})+P_T^{\mathcal{A}_y}(\|\cmp\|_{1:T})}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\| \\ &\qquad +\sum_{t=1}^T\varphi_t(\cmp_t) - \varphi_t(\widetilde{)}\\ &\le 2(L+H)\epsilon + \frac{16\left[\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\frac{4T^3}{\epsilon}\right)\right]}{2\eta}+\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\| +\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}.\qedhere \end{align}\] ◻

Finally, we have the following simple hyperparameter tuning argument. The result simply shows that if we add the iterates of many instances of the above algorithm together with different step-sizes, we can get a regret guarantee which balances the trade-off in \(\eta\). For ease of exposition, in what follows we denote this trade-off as \[\begin{align} \mathcal{T}(\eta)\overset{\text{def}}{=}\frac{16\left[\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\frac{4T^3}{\epsilon}\right)\right]}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|.\label{eq:dynamic-trade-off} \end{align}\tag{16}\] The terms are balanced, up to lower-order terms, by selecting \(\eta^*=\operatorname{arg\,min}_{\eta\in\mathcal{S}} \mathcal{T}(\eta)\), as shown by the following theorem.

Proof. Observe that for any \(\eta\in \mathcal{S}\), we have via convexity of \(f_{t}\) that \[\begin{align} R_T(\cmp_{1:T}) &\le \sum_{t=1}^T\left\langle \gt, \widetilde{-}\cmp_t \right\rangle = \sum_{t=1}^T\left\langle \gt, \widetilde{^}\eta-\cmp_t \right\rangle + \sum_{\widetilde{\eta}\ne \eta}\sum_{t=1}^T\left\langle \gt, \widetilde{^}{\widetilde{\eta}} \right\rangle\\ &= R_T^{\mathcal{A}_\eta}(\cmp_{1:T}) + \sum_{\widetilde{\eta}\ne \eta}R_T^{\mathcal{A}_{\widetilde{\eta}}}(\mathbf{0})\\ &\overset{(a)}{\le} R_T^{\mathcal{A}_\eta}(\cmp_{1:T}) + 2(L+H)\epsilon(\left|\mathcal{S}\right|-1) + \sum_{\widetilde{\eta}\ne \eta}\sum_{t=1}^T\varphi_t^{\widetilde{\eta}}(0)-\varphi_t^{\widetilde{\eta}}(\widetilde{^}{\widetilde{\eta}})\\ &\overset{(b)}{\le} 2(L+H)(\left|\mathcal{S}\right|\epsilon+M)+\underbrace{\frac{16\left[\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right]}{2\eta}+\frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|}_{=:\mathcal{T}(\eta)}\\ &\qquad+ \sum_{t=1}^T\varphi_t^{\eta}(\cmp_t)-\sum_{\widetilde{\eta}\in\mathcal{S}}\sum_{t=1}^T\varphi_t^{\widetilde{\eta}}(\widetilde{^}{\widetilde{\eta}}) \end{align}\] where \(\gt\in\partial f_{t}(\widetilde{)}\), \(M=\max_t\|\cmp_t\|\), \((a)\) applies [thm:optimistic-dynamic-base] to bound \(R_T^{\mathcal{A}_{\widetilde{\eta}}}(0)\) for each of the \(\widetilde{\eta}\ne \eta\), and \((b)\) applies [thm:optimistic-dynamic-base] for \(\mathcal{A}_\eta\) against the comparator sequence \(\cmp_{1:T}\). Moreover, notice that the previous display holds for any arbitrary \(\eta\in\mathcal{S}\). Therefore, applying [lemma:tuning-lemma] we have \[\begin{align} R_T(\cmp_{1:T}) &\le 16(L+H)\left(\epsilon\left|\mathcal{S}\right|+M+\Phi(\|\cmp_T\|,\tfrac{T}{\epsilon})+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right)+4\sqrt{\left[\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right]\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|}\\ &\qquad +\sum_{\eta\in\mathcal{S}}\sum_{t=1}^T\varphi_t^\eta\Big(\cmp_t\mathbb{I}(\eta=\eta^*)\Big)-\varphi_t^{\eta}(\widetilde{^}\eta), \end{align}\] where \(\eta^* = \operatorname{arg\,min}_{\eta\in\mathcal{S}}\mathcal{T}(\eta)\). ◻

11.1.1 Useful Lemmas for Huber-like Penalties↩︎

Our main application of interest for 7 in this paper is to leverage the terms \(\sum_{t=1}^T\varphi_t(\cmp_t)-\varphi_t(\widetilde{)}\) to control certain \(\|\widetilde{\|}\)-dependent penalties that result from applying concentration arguments in our high-probability bounds. To this end, in this section we collect some useful auxiliary results for the Huber-like penalty originally proposed by [28], which is key to achieving our our high-probability bounds in 4. The crucial property of these penalties is that they let us cancel out certain algorithm-dependent penalties \(\widetilde{\mathcal{O}}\Big(\big(\sum_{t=1}^T\|\widetilde{\|}^p\big)^{1/p}\Big)\) and replace them with problem-dependent penalties on the order of \(\widetilde{\mathcal{O}}\Big(\big(\sum_{t=1}^T\|\cmp_t\|^p\big)^{1/p}\Big)\). The following lemma defines the composite penalty and provides upper bounds for the terms that the comparator and the learner will incur when adding these additional penalties to the objective. It is a mild generalization of [28] to a dynamic comparator sequence.

lemmaDynamicHuber Let \(c, \alpha>0\), \(p\ge 1\), and for all \(t\) let \[\begin{align} r_{t}(\w;c,\alpha,p) &= \begin{cases} c\left(p\|\w\|-(p-1)\|\widetilde{\|}\right)\frac{\|\widetilde{\|}^{p-1}}{\left(\alpha^{p}+\sum_{s=1}^{t}\|\ws\|^{p}\right)^{1-1/p}} &\text{if }\|\w\|>\|\widetilde{\|}\\ c\frac{\|\w\|^{p}}{\left(\alpha^{p}+\sum_{s=1}^{t}\|\widetilde{\|}^{p}\right)^{1-1/p}} &\text{if }\|\w\|\le \|\widetilde{\|}. \end{cases}\label{eq:huber} \end{align}\tag{17}\] Then \[\begin{align} \sum_{t=1}^Tr_{t}(\widetilde{)} &\ge c \left(\sum_{t=1}^T\|\widetilde{\|}^{p}+\alpha^{p}\right)^{1/p} - c\alpha\\ \sum_{t=1}^Tr_{t}(\cmp_{t})&\le cp\left(\alpha^p+\sum_{t=1}^T\|\cmp_{t}\|^{p}\right)^{1/p}\left[\log\left(1+\frac{\sum_{t=1}^T\|\cmp_{t}\|^{p}}{\alpha^{p}}\right)^{\frac{p-1}{p}}+1\right] \end{align}\]

Proof. Observe that \[\begin{align} \sum_{t=1}^Tr_{t}(\widetilde{)} = \sum_{t=1}^Tc\frac{\|\widetilde{\|}^{p}}{\left(\alpha^{p} + \sum_{s=1}^{t}\|\ws\|^{p}\right)^{1-1/p}}\ge\sum_{t=1}^Tc \frac{\|\widetilde{\|}^{p}}{\left(\alpha^{p}+\sum_{t=1}^T\|\widetilde{\|}^{p}\right)^{1-1/p}} \ge c\left(\alpha^{p}+\sum_{t=1}^T\|\widetilde{\|}^{p}\right)^{1/p}-c\alpha, \end{align}\] where the last line uses the fact that \(\alpha^p / (\alpha^p+\sum_{t=1}^T\|\widetilde{\|}^p)^{1-1/p}\le \alpha\). Moreover, for any sequence \(\cmp_{1:T}\) we can upper bound \[\begin{align} \sum_{t=1}^Tr_{t}(\cmp_{t}) &= \sum_{t:\|\cmp_{t}\|\le\|\widetilde{\|}}r_{t}(\cmp_{t})+\sum_{t:\|\cmp_{t}\|>\|\widetilde{\|}}r_{t}(\cmp_{t})\\ &\le c\Bigg[\sum_{t:\|\cmp_{t}\|\le\|\widetilde{\|}}\frac{\|\cmp_{t}\|^{p}}{\left(\alpha^{p}+\sum_{s=1}^{t}\|\ws\|^{p}\right)^{1-1/p}}+\sum_{t:\|\cmp_{t}\|>\|\widetilde{\|}}\frac{\|\cmp_{t}\|\|\widetilde{\|}^{p-1}}{\left(\alpha^{p}+c\sum_{s=1}^{t}\|\ws\|^{p}\right)^{1-1/p}}\Bigg]\\ &\le c\Bigg[\underbrace{\sum_{t:\|\cmp_{t}\|\le\|\widetilde{\|}}\frac{\|\cmp_{t}\|^{p}}{\left(\alpha^{p}+\sum_{s\le t: \|\cmp_s\|\le\|\ws\|}\|\ws\|^{p}\right)^{1-1/p}}}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A};}+\underbrace{\sum_{t:\|\cmp_{t}\|>\|\widetilde{\|}}\frac{\|\cmp_{t}\|\|\widetilde{\|}^{p-1}}{\left(\alpha^{p}+c\sum_{s\le t: \|\cmp_s\|>\|\ws\|}^{t}\|\ws\|^{p}\right)^{1-1/p}}}_{ \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B};}\Bigg] \end{align}\] The first term can be bounded as \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut A}; &= \sum_{t:\|\cmp_{t}\|\le\|\widetilde{\|}}\frac{\|\cmp_{t}\|^{p}}{\left(\alpha^{p}+\sum_{s\le t: \|\cmp_s\|\le\|\ws\|}\|\ws\|^{p}\right)^{1-1/p}}\\ &\le \sum_{t:\|\cmp_{t}\|\le\|\widetilde{\|}}\frac{\|\cmp_{t}\|^{p}}{\left(\alpha^{p}+\sum_{s\le t: \|\cmp_s\|\le\|\ws\|}\|\cmp_s\|^{p}\right)^{1-1/p}}\\ &\le p\left(\alpha^p + \sum_{t:\|\cmp_t\|\le \|\widetilde{\|}}\|\cmp_t\|^p\right)^{1/p} \le p\left(\alpha^p + \sum_{t=1}^T\|\cmp_t\|^p\right)^{1/p} \end{align}\] where the last line uses [lemma:p-bound]. The other term can be bound using Hölder inequality with \(q=p\) and \(q'=p/(p-1)\) so that \(1/q+1/q' = 1\) and \[\begin{align} \tikz[baseline=(X.base)] \node (X) [draw, shape=circle, inner sep=0] {\strut B}; &= \sum_{t:\|\cmp_{t}\|>\|\widetilde{\|}}\frac{\|\cmp_t\|\|\widetilde{\|}^{p-1}}{\left(\alpha^{p}+\sum_{s\le t:\|\cmp_s\|>\|\ws\|}^{t}\|\ws\|^{p}\right)^{1-1/p}}\\ &\le \left(\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\|\cmp_t\|^p\right)^{1/p}\left(\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\frac{\|\widetilde{\|}^{(p-1)\tfrac{ p}{p-1}}}{\left(\alpha^p+\sum_{s\le t:\|\cmp_s\|>\|\ws\|}\|\ws\|^p\right)^{\tfrac{p-1}{p}\tfrac{p}{p-1}}}\right)^{(p-1)/p}\\ &= \left(\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\|\cmp_t\|^p\right)^{1/p}\left(\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\frac{\|\widetilde{\|}^{p}}{\left(\alpha^p+\sum_{s\le t:\|\cmp_s\|>\|\ws\|}\|\ws\|^p\right)}\right)^{(p-1)/p}\\ &\overset{(*)}{\le} \left(\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\|\cmp_t\|^p\right)^{1/p}\log\left(1+\frac{\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\|\widetilde{\|}^p}{\alpha^p}\right)^{(p-1)/p}\\ &\le \left(\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\|\cmp_t\|^p\right)^{1/p}\log\left(1+\frac{\sum_{t:\|\cmp_t\|>\|\widetilde{\|}}\|\cmp_t\|^p}{\alpha^p}\right)^{(p-1)/p}\\ &\le \left(\sum_{t=1}^T\|\cmp_t\|^p\right)^{1/p}\log\left(1+\frac{\sum_{t=1}^T\|\cmp_t\|^p}{\alpha^p}\right)^{(p-1)/p} \end{align}\] where \((*)\) uses [lemma:log-bound]. Combining these bounds and over-approximating yields \[\begin{align} \sum_{t=1}^Tr_{t}(\cmp_{t}) &\le cp\left(\alpha^p + \sum_{t=1}^T\|\cmp_t\|^p\right)^{1/p}\left[\log\left(1+\frac{\sum_{t=1}^T\|\cmp_t\|^p}{\alpha^p}\right)^{(p-1)/p}+1\right] \end{align}\] ◻

Now using [lemma:dynamic-huber], the following lemma shows how to bound the cumulative penalty of the comparator sequence for the composite penalty used in 6, which sets \(\varphi_t\) as the sum of two Huber-like penalties.

lemmaComparatorVarphi For all \(t\) let \(r_t(w;c,\alpha,p)\) be defined as in [lemma:dynamic-huber] wrt some sequence \(\w_1,\ldots,\w_t\), and suppose we set \(\varphi_t(w) = r_t(\w;c_1,\alpha_1,p_1)+r_t(\w; c_2,\alpha_2, p_2)\) with \(p_1=2\) and \(p_2=\log\left(T+1\right)\). Then for any sequence \(\cmp_{1:T} = (\cmp_1,\ldots,\cmp_T)\) in \(\mathbb{R}^d\), \[\begin{align} \sum_{t=1}^T\varphi_t(\cmp_t) &= r_t(w;c_1,\alpha_1,p_1) + r_t(w;c_2,\alpha_2,p_2)\\ &\le 4c_1 \sqrt{\alpha_1^2+\sum_{t=1}^T\|\cmp_t\|^2\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\alpha_1^2}\right)}+ 3 c_2 \log^{2}(T+1)\max\left\{\alpha_2, M\right\}\left[\log_+\left(3 M/\alpha_2\right)+3\right]. \end{align}\] where \(M=\max_t\|\cmp_t\|\).

Proof. with \(p_1=2\), we have via [lemma:dynamic-huber] that \[\begin{align} \sum_{t=1}^Tr_t(\cmp_t;c_1,\alpha_1, p_1) &\le c_1 2\sqrt{\alpha_1^2+\sum_{t=1}^T\|\cmp_t\|^2}\left[\sqrt{\log\left(1+\frac{\sum_{t=1}^T\|\cmp_t\|^2}{\alpha_1^2}\right)}+1\right]\\ &\le 4c_1 \sqrt{\left(\alpha_1^2+\sum_{t=1}^T\|\cmp_t\|^2\right)\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\alpha_1^2}\right)}. \end{align}\] Likewise, for \(p_2=\log\left(T+1\right)\) we have via [lemma:dynamic-huber] that \[\begin{align} \sum_{t=1}^Tr_t(\cmp_t;c_2,\alpha_2,p_2) &\le p_2c_2\left(\alpha_2^{p_2} + \sum_{t=1}^T\|\cmp_t\|^{p_2}\right)^{1/p_2}\left[\log\left(1+\frac{\sum_{t=1}^T\|\cmp_t\|^{p_2}}{\alpha_2^{p_2}}\right)^{(p_2-1)/p_2}+1\right]\\ &\le p_2c_2 \max\left\{\alpha_2, \max_t\|\cmp_t\|\right\}(T+1)^{\tfrac{1}{\log\left(T+1\right)}}\left[\log\left(1+\frac{\sum_{t=1}^T\|\cmp_t\|^{p_2}}{\alpha_2^{p_2}}\right)^{(p_2-1)/p_2}+1\right]\\ &\le p_2e c_2 \max\left\{\alpha_2, M\right\}\left[\log\left(1+T\left(\frac{M}{\alpha_2}\right)^{p_2}\right)+1\right], \end{align}\] where we’ve abbreviated \(M=\max_t\|\cmp_t\|\). Now suppose that \(T(M/\alpha_2)^{p_2}\le e-1\), then the logarithm term is bounded by \(\log\left(1+T(M/\alpha_2)^{p_2}\right)\le \log\left(e\right)=1\). Otherwise, if \(T(M/\alpha_2)^{p_2}\ge e-1\), then using the elementary identity \(\log\left(1+x\right)=\log\left(x\right)+\log\left(1+1/x\right)\), we have \[\begin{align} \log\left(1+T(M/\alpha_2)^{p_2}\right) &= \log\left(\left(T^{1/p_2} M/\alpha_2\right)^{p_2}\right) + \log\left(1+\frac{1}{T(M/\alpha_2)^{p_2}}\right)\\ &\le p_2\log\left(e M/\alpha_2\right)+\log\left(e\right) = 1+\log\left(T+1\right)\log\left(eM/\alpha_2\right), \end{align}\] so we may bound the previous display as \[\begin{align} \sum_{t=1}^Tr_t(\cmp_t;c_2,\alpha_2,p_2) &\le 3 \log\left(T+1\right)c_2 \max\left\{\alpha_2, M\right\}\left[\log\left(T+1\right)\log_+\left(3 M/\alpha_2\right)+2\right]\\ &\le 3 \log^2(T+1)c_2 \max\left\{\alpha_2, M\right\}\left[\log_+\left(3 M/\alpha_2\right)+3\right], \end{align}\] where we’ve used that \(2/\log\left(T+1\right)\le 3\) for \(T\ge 1\). Hence, we have the stated bound: \[\begin{align} \sum_{t=1}^T\varphi_t(\cmp_t) &= r_t(w;c_1,\alpha_1,p_1) + r_t(w;c_2,\alpha_2,p_2)\\ &\le 4c_1 \sqrt{\alpha_1^2+\sum_{t=1}^T\|\cmp_t\|^2\log\left(e+\frac{e\sum_{t=1}^T\|\cmp_t\|^2}{\alpha_1^2}\right)}+ 3 c_2 \log^2(T+1)\max\left\{\alpha_2, M\right\}\left[\log_+\left(3 M/\alpha_2\right)+3\right]. \end{align}\] ◻

11.2 Refined Dynamic Regret Algorithm for OCO↩︎

In this section we provide a dynamic regret algorithm for OLO which satisfies the conditions of [thm:dynamic-optimism]. The result is modest adaptation of the dynamic base algorithm first proposed by [29], with minor adjustments in the constants to allow the desired cancellations required in [thm:dynamic-optimism] to occur. We present the base algorithm for the general constrained case for generality, though in our applications we will simply instantiate the algorithm unconstrained (\(\mathcal{W}=\mathbb{R}^d)\) and with \(\w_1=\mathbf{0}\), in which case the update in 9 reduces to \(\wtpp = \wtildetpp = \frac{\theta_t}{\|\theta_t\|}\alpha \left[\exp\left(\frac{k}{\eta}\left[\|\theta_t\|-\tfrac{\eta}{2}\|\gt\|^2-\gamma\right]\right)-1\right]_+\) and the guarantees in [thm:dynamic-base-simple] scales with \(M=\max_t\|\cmp_t\|\) and \(\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|\), as in [29].

Our result has a few other qualities which might be of independent interest. We provide a mild refinement of their result which avoids most factors of \(M=\max_t\|\cmp_t\|\) and replaces the global \(\mathcal{O}((M+P_T)\log\left(MT\right))\) penalties reported in [29] with a refined log-linear penalties \(\Phi_T(\lambda)+P_T^\Phi(\lambda)\), where \[\begin{align} \Phi_T(\lambda)=\|\cmp_T\|\log\left(\lambda\|\cmp_T\|+1\right),\qquad P_T^\Phi(\lambda)&:=\sum_{t=2}^T \|\cmp_t-\cmp_{t-1}\|\log\left(\lambda\|\cmp_t-\cmp_{t-1}\|+1\right). \end{align}\] Our analysis also streamlines the analysis of [29] by using simple fixed hyperparameter settings for \(\alpha\) and \(\gamma\), contrasting the time-varying choices used in the original work. The main appeal of their time-varying hyperparameter choices is that they result in a horizon-independent base algorithm; however, this benefit is limited in application since full algorithm has to maintain a collection of learners \(\left\{\mathcal{A}_{\eta_i}\right\}\) for \(\eta_i=2^i/L\sqrt{T}\), which makes the full algorithm horizon-dependent either way. Hence, here we focus on a simple fixed hyperparameter setting of \(\alpha\) and \(\gamma\).

Figure 9: Refined Dynamic Base Algorithm for OLO

theoremDynamicBaseSimple For any sequence \(f_1,\ldots,f_T\) of \(L\)-Lipschitz convex loss functions and any sequence \(\cmp_{1:T}=(\cmp_1,\ldots,\cmp_T)\) in \(\mathcal{W}\), 9 with \(\eta\le 1/L\) and \(k\ge 4\) guarantees \[\begin{align} R_T(\cmp_{1:T}) &\le \frac{2k\left[\Phi\left(\|\cmp_T-\w_1\|,\tfrac{1}{\alpha}\right)+P_T^\Phi\left(\tfrac{k}{\eta\alpha\gamma}\right)\right]}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t-\w_1\| +\gamma\sum_{t=1}^T\|\cmp_t-\w_1\| + \eta\alpha\sum_{t=1}^T\|\gt\|^2, \end{align}\] where \(\gt\in\partial f_{t}(\widetilde{)}\) for all \(t\) and we define \(\Phi(x,\lambda) = x\log\left(\lambda x+1\right)\) and the \(\Phi\)-path-length \(P_T^\Phi(\lambda)=\sum_{t=2}^T\Phi(\|\cmp_t-\cmp_{t-1}\|,\lambda)\). Moreover, for any \(\epsilon>0\), setting \(\alpha=\tfrac{\epsilon}{T}\), \(\gamma=\tfrac{L}{T}\), \(k=4\), and \(\tfrac{1}{LT}\le \eta\le \tfrac{1}{L}\) ensures that \[\begin{align} R_T(\cmp_{1:T}) &\le L(M+\epsilon)+\frac{8\left[\Phi\left(\|\cmp_T-\w_1\|, \tfrac{T}{\epsilon}\right)+ P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right]}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t-\w_1\|, \end{align}\] where \(M=\max_t\|\cmp_t-\w_1\|\).

Proof. We have via the dynamic regret guarantee of mirror descent (see, e.g., [29]) that \[\begin{align} R_T(\cmp_{1:T}) &\le \sum_{t=1}^T\left\langle \gt, \widetilde{-}\cmp_t \right\rangle\\ &\le \psi(\cmp_T) + \sum_{t=1}^T\varphi_t(\cmp_t) + \sum_{t=2}^T\left\langle \nabla\psi(\widetilde{)}-\nabla\psi(\w_1),\cmp_t-\cmp_{t-1} \right\rangle \\ &\qquad +\sum_{t=1}^T\left\langle \gt, \widetilde{-}\wtpp \right\rangle+D_\psi(\wtpp|\widetilde{)}-\varphi_t(\wtpp)\\ &= \psi(\cmp_T) + \sum_{t=1}^T\varphi_t(\cmp_t) + \sum_{t=2}^T\underbrace{\left\langle \nabla\psi(\widetilde{)},\cmp_t-\cmp_{t-1} \right\rangle-\gamma\|\widetilde{-}\w_1\|}_{=:\rho_t}\\ &\qquad +\sum_{t=1}^T\underbrace{\left\langle \gt, \widetilde{-}\wtpp \right\rangle+D_\psi(\wtpp|\widetilde{)}-\eta\|\gt\|^2\|\wtpp-\w_1\|}_{=:\delta_t} \end{align}\] where \(\gt\in\partial\ell_t(\widetilde{)}\) for each \(t\). The terms \(\rho_t\) can be bound using Fenchel-Young inequality. Let \(f(x) = \frac{k}{\eta}\int_0^x\log\left(\tfrac{k v}{\alpha\eta\gamma} + 1\right)dv\); by direct calculation we have \(f^*(\theta)=\alpha\gamma\left(\exp\left(\tfrac{\eta}{k}\theta\right)-\tfrac{\eta}{k}\theta\right)\). Hence, by Fenchel-Young inequality we have \[\begin{align} \sum_{t=2}^T\rho_t &\le \sum_{t=2}^T \|\nabla\psi(\widetilde{)}\|\|\cmp_t-\cmp_{t-1}\| -\gamma\|\widetilde{-}\w_1\|\le \sum_{t=2}^Tf(\|\cmp_t-\cmp_{t-1}\|)+f^*(\|\nabla\psi(\widetilde{)}\|)-\gamma\|\widetilde{-}\w_1\|\\ &\le \sum_{t=2}^Tf(\|\cmp_t-\cmp_{t-1}\|) + \alpha\gamma \left(\exp\left(\tfrac{\eta}{k}\tfrac{k}{\eta}\log\left(\|\widetilde{-}\w_1\|/\alpha+1\right)\right)-\tfrac{\eta}{k}\|\nabla\psi(\widetilde{)}\|\right)-\gamma\|\widetilde{-}\w_1\|\\ &\le \sum_{t=2}^Tf(\|\cmp_t-\cmp_{t-1}\|) + \alpha\gamma\left(\frac{\|\widetilde{-}\w_1\|}{\alpha}+1\right)-\gamma\|\widetilde{-}\w_1\| = \sum_{t=2}^T\left(f(\|\cmp_t-\cmp_{t-1}\|) +\alpha\gamma\right)\\ &\le (T-1)\alpha\gamma + \sum_{t=2}^T\frac{k\|\cmp_t-\cmp_{t-1}\|\log\left(\tfrac{k\|\cmp_t-\cmp_{t-1}\|}{\alpha\eta\gamma}+1\right)}{\eta} \end{align}\] where the last inequality uses \(\int_0^x F(v)dv\le x F(x)\) for non-decreasing \(F(x)\).

For the stability terms \(\sum_{t=1}^T\delta_t\), first observe that the regularizer is \(\psi(w)=\Psi(\|\w-\w_1\|)=\frac{k}{\eta}\int_0^{\|\w-\w_1\|}\log(x/\alpha+1)dx\), where \(\Psi\) satisfies \[\begin{align} \Psi'(x)&=\frac{k}{\eta}\log\left(x/\alpha+1\right)\\ \Psi''(x)&=\frac{k}{\eta(x+\alpha)}\\ \Psi'''(x)&=\frac{-k}{\eta(x+\alpha)^2}, \end{align}\] hence, for \(k\ge 4\) we have \(\left|\Psi'''(x)\right| \le \frac{\eta/2}{2}\Psi''(x)^2\) for all \(x\ge0\), so by [29] with \(\eta_t(\|\w-\w_1\|) := \eta/2\) we have that \[\begin{align} \sum_{t=1}^T\delta_t=\sum_{t=1}^T\left\langle \gt,\widetilde{-}\wtpp \right\rangle-D_\psi(\wtpp|\widetilde{)}-\eta\|\gt\|^2\|\wtpp-\w_1\|\le \frac{2\|\gt\|^2}{\Psi''(0)}=\sum_{t=1}^T\frac{2\eta\alpha}{k}\|\gt\|^2\le \frac{\eta\alpha}{2} \sum_{t=1}^T\|\gt\|^2. \end{align}\] Plugging the bounds for \(\sum_{t=1}^T\rho_t\) and \(\sum_{t=1}^T\delta_t\) back into the regret bound and expanding the definition of \(\varphi_t(\cmp_t)\) yields \[\begin{align} R_T(\cmp_{1:T}) &\le \psi(\cmp_T) + \sum_{t=1}^T\varphi_t(\cmp_t) + \sum_{t=2}^T\rho_t + \sum_{t=1}^T\delta_t\\ &\le \frac{k\|\cmp_T-\w_1\|\log\left(\tfrac{\|\cmp_T-\w_1\|}{\alpha}+1\right)+k\sum_{t=2}^T\|\cmp_t-\cmp_{t-1}\|\log\left(\tfrac{k\|\cmp_t-\cmp_{t-1}\|}{\alpha\eta\gamma}+1\right)}{\eta}\\ &\qquad+ \frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t-\w_1\|+\gamma\sum_{t=1}^T\|\cmp_t-\w_1\| + \frac{\eta\alpha}{2}\sum_{t=1}^T\|\gt\|^2+(T-1)\alpha\gamma\\ &\le \frac{k\left[\Phi\left(\|\cmp_T-\w_1\|,\tfrac{1}{\alpha}\right)+P_T^\Phi\left(\tfrac{k}{\alpha\eta\gamma}\right)\right]}{\eta}\\ &\qquad + \frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t-\w_1\| +\gamma\sum_{t=1}^T\|\cmp_t-\w_1\|+ \frac{\eta\alpha}{2}\sum_{t=1}^T\|\gt\|^2+(T-1)\alpha\gamma, \end{align}\] where we’ve defined \(\Phi(x,\lambda) = x\log\left(\lambda x+1\right)\) and the \(\Phi\)-path-length \(P_T^\Phi(\lambda)=\sum_{t=2}^T\Phi(\|\cmp_t-\cmp_{t-1}\|,\lambda)=\sum_{t=2}^T\|\cmp_t-\cmp_{t+1}\|\log\left(\lambda\|\cmp_t-\cmp_{t+1}\|+1\right)\). Moreover, for any \(\epsilon>0\), setting \(\alpha=\epsilon/T\), \(\gamma=L/T\), and \(\frac{1}{LT}\le \eta\le \tfrac{1}{L}\), we have \(k/\alpha\eta\gamma\le 4 T^3/\epsilon\) and \[\begin{align} R_T(\cmp_{1:T}) &\le \frac{k\left[\Phi(\|\cmp_T\|, \tfrac{\epsilon}{T})+P_T^\Phi\left(\tfrac{kT^3}{\epsilon}\right)\right]}{\eta} + \frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t-\w_1\| +\frac{L}{T}\sum_{t=1}^T\|\cmp_t-\w_1\|+ \frac{\epsilon}{2LT}\sum_{t=1}^T\|\gt\|^2+\frac{\epsilon}{T}\frac{L}{T}(T-1)\\ &\le L(M+\epsilon)\\ &\qquad +\frac{8\left[\|\cmp_T\|\log\left(\tfrac{\|\cmp_T\|T}{\epsilon}+1\right)+\sum_{t=1}^{T-1} \|\cmp_t-\cmp_{t+1}\|\log\left(\tfrac{4\|\cmp_t-\cmp_{t+1}\|T^3}{\epsilon}+1\right)\right]}{2\eta} + \frac{\eta}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t-\w_1\|.\qedhere \end{align}\] ◻

Figure 10: Dynamic Algorithm for Unconstrained OLO

For completeness we also provide the tuned guarantee for the unconstrained setting, obtained by running 9 with step-size \(\eta\) for each \(\eta\in\left\{2^i/LT\wedge 1/L, i=0,1,\ldots\right\}\) and adding the resulting iterates together.

theoremDynamicBaseOLOTuned For any sequence of \(L\)-Lipschitz convex functions \(f_1,\ldots,f_T\) and any sequence \(\cmp_{1:T}=(\cmp_1,\ldots,\cmp_T)\) in \(\mathbb{R}^d\), 10 guarantees \[\begin{align} R_T(\cmp_{1:T})\le 4L\left(\left|\mathcal{S}\right|\epsilon +M+\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right)+ 2\sqrt{2\left(\Phi\left(\|\cmp_T\|,\tfrac{T}{\epsilon}\right)+P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)\right)\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|} \end{align}\] where \(\Phi(x,\lambda)= x\log\left(\lambda x+1\right)\) and \(P_T^\Phi(\lambda)= \sum_{t=2}^T\Phi(\|\cmp_t-\cmp_{t-1}\|,\lambda)\).

Proof. Observe that for any \(\eta_i\in\mathcal{S}\), we have \[\begin{align} R_T(\cmp_{1:T}) &\le \sum_{t=1}^T\left\langle \gt,\widetilde{-}\cmp_t \right\rangle = \sum_{t=1}^T\left\langle \gt, \widetilde{^}{\eta_i}-\cmp_t \right\rangle + \sum_{\eta_j\ne \eta_i}\sum_{t=1}^T\left\langle \gt, \widetilde{^}{\eta_j} \right\rangle\\ &= R_T^{\mathcal{A}_{\eta_i}}(\cmp_{1:T}) + \sum_{\eta_j\ne \eta_i}R_T^{\mathcal{A}_j}(\mathbf{0}), \end{align}\] where \(\gt\in\partial\ell_t(\widetilde{)}\) for all \(t\) and \(R_T^{\mathcal{A}_j}(\cmp_{1:T})=\sum_{t=1}^T\left\langle \gt,\widetilde{^}{\eta_j}-\cmp_t \right\rangle\) denotes the dynamic regret of \(\mathcal{A}_j\). Hence, applying [thm:dynamic-base-simple] and observing that \(R_T^{\mathcal{A}_j}(\mathbf{0})\le L\epsilon\) for any \(\eta_j\), we have \[\begin{align} R_T(\cmp_{1:T}) &\le R_T^{\mathcal{A}_i}(\cmp_{1:T}) + (\left|\mathcal{S}\right|-1)L\epsilon\\ &\le L(\left|\mathcal{S}\right|\epsilon +M)+ \frac{8(\Phi_T+P_T^\Phi)}{2\eta_i} + \frac{\eta_i}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|, \end{align}\] where we denote \(\Phi_T=\Phi(\|\cmp_T\|,T/\epsilon)\) and \(P_T^\Phi = P_T^\Phi\left(\tfrac{4T^3}{\epsilon}\right)=\sum_{t=2}^T\Phi(\|\cmp_t-\cmp_{t-1}\|,4T^3/\epsilon)\). Now applying [lemma:tuning-lemma] we have \[\begin{align} R_T(\cmp_{1:T}) &\le L(\left|\mathcal{S}\right|\epsilon +M)+ 2\sqrt{2(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|} + \frac{8(\Phi_T+P_T^\Phi)}{2\eta_{\max}}+\frac{\eta_{\min}}{2}\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|\\ &\le L(\left|\mathcal{S}\right|\epsilon +M)+ 2\sqrt{2(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|} + 4L(\Phi_T+P_T^\Phi)+LM\\ &\le 4L\left(\left|\mathcal{S}\right|\epsilon +M+\Phi_T+P_T^\Phi\right)+ 2\sqrt{2(\Phi_T+P_T^\Phi)\sum_{t=1}^T\|\gt\|^2\|\cmp_t\|} \qedhere \end{align}\] ◻

12 Proof of Theorem 3 ↩︎

We recall the theorem before detailing its proof.

Proof. The proof follows the general outline of Theorem 24.2 of [8], which proves a \(\Omega(d\sqrt{T})\) lower bound on the regret for a slightly different feedback model. In their setting, at time \(t\geq 1\), after playing \(x_t\in \mathbb{B}_d\) the learner receives \[\ell_t(x_t) = \left\langle \theta, x_t \right\rangle+\epsilon_t, \quad \text{where} \; \epsilon_t \sim \mathcal{N}(0,1),\] and \(\theta \in \Theta\) is a fixed parameter from some class of parameters \(\Theta\). The proof uses that, up to horizon \(T\), it is difficult for the learner to distinguish parameters \(\theta\) from \(\theta'\), if \(\Theta\) is a small hypercube centered in the origin. In the following, we keep a similar class of parameters \(\Theta\), but introduce key changes in the arguments to tackle different feedback models and constraints on the losses.

12.0.0.1 Stochastic model

We fix a constant \(\Delta= \frac{1}{8\sqrt{T}}\), and consider the class of parameters \(\Theta = \{\pm \Delta\}^d\). By assumption, \(T\geq 4d\), so \(\|\theta\|^2\leq \frac{1}{2}\) for any \(\theta\in \Theta\). To satisfy the stochastic assumptions of the theorem, we assume that losses are generated as follows:

Before the interaction, the adversary chooses at random a parameter \(\theta \in \Theta\).
for each time step \(t\geq 1\), the adversary samples \(\ell_t=\theta+ \epsilon_t\), with \(\epsilon_t\sim \mathcal{N}\left(0, \frac{1}{2d}I_d\right)\), and the learner observes feedback \(\left\langle \ell_t, x_t \right\rangle\).

By construction, losses are sub-Gaussian and satisfy \(\mathbb{E}\left[ \|\ell_t\|^2 \right]\leq \|\theta\|^2 + \mathbb{E}\left[ \|\epsilon_t\|^2 \right]\leq 1\) for all \(t\geq 1\).

Then, similarly to [8], for any \(i\in[d]\) we define the stopping time \[\tau_i \mathrel{\vcenter{:}}= T \wedge \min\Bigl\{ t\ge 1 : \sum_{s=1}^t x_{si}^2 \ge \frac{T}{d}-1\Bigr\}.\] In their proof, the threshold \(\frac{T}{d}\) intuitively represents the quantity of information necessary to confidently identify the sign of \(\theta_i\) when \(|\theta_i|\propto \sqrt{\frac{d}{T}}\). In our case, the same intuition holds with a gap proportional to \(1/\sqrt{T}\) because the variance is smaller by a factor \(d\), so we don’t have to modify the definition of \(\tau_i\) (we just added \(-1\) to simplify computations).

For any algorithm \(\mathcal{A}\) and \(\theta \in \Theta\), we denote by \(R_T(\mathcal{A}, \theta)\) the regret of \(\mathcal{A}\) against the comparator \(u_\theta=-\frac{\text{sgn}(\theta)}{\sqrt{d}}\). It holds that \[\begin{align} R_T(\mathcal{A},\theta) &= \Delta \,\mathbb{E}_\theta\Biggl[\sum_{t=1}^T\sum_{i=1}^d \Bigl(\frac{1}{\sqrt d}+x_{ti}\,\text{sgn}(\theta_i)\Bigr)\Biggr] \nonumber \\ &\ge \frac{\Delta\sqrt d}{2}\, \mathbb{E}_\theta\Biggl[\sum_{t=1}^T\sum_{i=1}^d \Bigl(\frac{1}{\sqrt d}+x_{ti}\,\text{sgn}(\theta_i)\Bigr)^2\Biggr] \nonumber \\ &\ge \frac{\Delta\sqrt d}{2}\sum_{i=1}^d \mathbb{E}_\theta\Biggl[\sum_{t=1}^{\tau_i} \Bigl(\frac{1}{\sqrt d}+x_{ti}\,\text{sgn}(\theta_i)\Bigr)^2\Biggr], \label{eq::reg95lower95bound} \end{align}\tag{18}\] where the first inequality comes from the fact that for all steps \(t\geq 1\), \[\begin{align} \sum_{i=1}^d \left(\frac{1}{\sqrt{d}}+ x_{ti}\,\text{sgn}(\theta_i)\right)^2 &= 1+ \sum_{i=1}^d\frac{2}{\sqrt{d}} x_{ti}\,\text{sgn}(\theta_i)+\|x_t\|^2 \\ & \leq 2+ \sum_{i=1}^d\frac{2}{\sqrt{d}} x_{ti}\,\text{sgn}(\theta_i) \\ & = \frac{2}{\sqrt{d}}\sum_{i=1}^d \left(\frac{1}{\sqrt{d}}+x_{t,i}\;\text{sgn}(\theta_i)\right)\;. \end{align}\] Note that this inequality is an equality if \(\|x_t\|=1\).

Then, for any \(i\in[d]\) and \(\sigma\in\{\pm 1\}\) we define \[U_i(\sigma) \mathrel{\vcenter{:}}= \sum_{t=1}^{\tau_i}\Bigl(\frac{1}{\sqrt d}+\sigma \cdot x_{ti}\Bigr)^2,\] and we verify that \[\begin{align} U_i(\sigma) &\leq 2\sum_{t=1}^{\tau_i} \frac{1}{d} + 2 \sum_{t=1}^{\tau_i} x_{ti}^2 \\ & \leq 2\left(\frac{\tau_i}{d}+ \frac{T}{d}\right) \leq 4\frac{T}{d} \;. \end{align}\]

Let \(\theta'\in \Theta\) be such that \(\theta_j=\theta'_j\) for \(j\neq i\) and \(\theta'_i=-\theta_i\). Assume without loss of generality that \(\theta_i>0\). Let \(\mathbb{P}\) and \(\mathbb{P}'\) be the laws of \(U_i(1)\) under the bandit/learner interaction induced by \(\theta\) and \(\theta'\), respectively. Then, using Pinsker inequality we obtain that \[\begin{align} \mathbb{E}_\theta[U_i(1)] & \ge \mathbb{E}_{\theta'}[U_i(1)] -\text{essup} \; U_i(1) \cdot \text{TV}(\mathbb{P},\mathbb{P}') \tag{19} \\ &\ge \mathbb{E}_{\theta'}[U_i(1)] - \frac{4T}{d}\sqrt{\frac{1}{2}\,\text{KL}(\mathbb{P},\mathbb{P}')} \tag{20} \end{align}\] Then, we use that at each step \(t\) the distribution of the observation under \(\mathbb{P}\) follows a Gaussian distribution \(\mathcal{N}\left(\left\langle \theta, x_t \right\rangle, \frac{\|x_t\|^2}{2d} \right)\), while it follows a Gaussian distribution \(\mathcal{N}\left(\left\langle \theta', x_t \right\rangle, \frac{\|x_t\|^2}{2d} \right)\) under model \(\mathbb{P}'\). Thus, using the chain rule for the relative entropy up to a stopping time, we have \[\text{KL}(\mathbb{P}, \mathbb{P}')= \mathbb{E}_\theta\left[\sum_{t=1}^{\tau_i}\frac{d}{\|x_t\|^2} \left\langle \theta-\theta', x_t \right\rangle^2\right] = 4\Delta^2 d \cdot \mathbb{E}_{\theta}\left[\sum_{t=1}^{\tau_i}\frac{x_{ti}^2}{\|x_t\|^2}\right]\;.\] We can identify two differences compared to the analogous proof step for Theorem 24.2 of [8] (Eq. 24.4). First, we can observe a supplementary \(d\) factor due to the \(d^{-1}\) term in the noise variance, that will cause the scaling \(\sqrt{dT}\) instead of \(d\sqrt{T}\) in the final result. Secondly, the norm \(\|x_t\|^2\) prevents us for showing that the expectation term scales in \(T/d\) by using the definition of \(\tau_i\) directly. However, it is clear that in this bounded setting playing an action with a small norm is sub-optimal. We thus introduce \(S_{\tau_i}=\sum_{i=1}^{\tau_i} \mathbb{I}\!\left(\|x_t\|^2 \leq 2/3\right)\). On each round where \(\|x_t\|^2 \leq \frac{2}{3}\), the instantaneous regret against the comparator \(u_\theta\) must be at least \(1/6\): the comparator gets a reward of \(1\), while the learner gets a reward upper bounded by \(\sqrt{2/3}\leq 0.82 \leq 1-1/6\). So, it must hold that \(R_T(\mathcal{A},\theta) \geq \frac{1}{6}\mathbb{E}_{\theta}[S_{\tau_i}]\). Meanwhile, using the definition of \(S_{\tau_i}\) we can obtain that \[\text{KL}(\mathbb{P}, \mathbb{P}')\leq 4\Delta^2 d \cdot \left(\frac{3}{2}\mathbb{E}\left[ \sum_{t=1}^{\tau_i}x_{ti}^2 \right] + \mathbb{E}\left[ S_{\tau_i} \right] \right) \leq 4\Delta^2 d \cdot \left(\frac{3}{2}\frac{T}{d} + \mathbb{E}_\theta[S_{\tau_i}] \right)\;.\] Combining these two results, we can use that either \(\mathbb{E}_\theta[S_{\tau_i}] \geq \frac{T}{2d}\), in which case it holds that \(R(T, \theta)\geq \frac{T}{12d}\), or it must hold that \[\text{KL}(\mathbb{P}, \mathbb{P}') \leq 8\Delta^2 d \frac{T}{d} \;.\] The first case yields the term \(\frac{T}{12d}\) in the theorem, corresponding to an algorithm that would achieve linear regret because it can consistently play actions with too small of a norm under some instances. For the remainder of the proof, we focus on the second case. Plugging the above result in Eq. 20 , we obtain that \[\begin{align} &\mathbb{E}_\theta[U_i(1)] \ge \mathbb{E}_{\theta'}[U_i(1)] - 8\Delta\frac{T}{d}\sqrt{T}\\ \end{align}\] It follows that \[\begin{align} \mathbb{E}_\theta[U_i(1)] + \mathbb{E}_{\theta'}[U_i(-1)] &\ge \mathbb{E}_{\theta'}[U_i(1)+U_i(-1)] - 8\Delta\frac{T}{d}\sqrt{T} \nonumber\\ &= 2\,\mathbb{E}_{\theta'}\Biggl[\frac{\tau_i}{d} + \sum_{t=1}^{\tau_i}x_{ti}^2\Biggr] - 8\Delta\frac{T}{d}\sqrt{T} \nonumber \\ &\ge 2\left(\frac{T}{d}-1\right) - 8\Delta\frac{T}{d}\sqrt{T} = \frac{T}{d}-2 , \label{eq::lb95Ui} \end{align}\tag{21}\] since \(\Delta=\frac{1}{8\sqrt{T}}\) and \[U_i(1)+U_i(-1) = \sum_{t=1}^{\tau_i}\Bigl[\Bigl(\frac{1}{\sqrt d}+x_{ti}\Bigr)^2 + \Bigl(\frac{1}{\sqrt d}+x_{ti}\Bigr)^2\Bigr] = 2\sum_{t=1}^{\tau_i}\Bigl(\frac{1}{d} + x_{ti}^2\Bigr),\] and that \(\frac{\tau_i}{d}+\sum_{t=1}^{\tau_i}x_{ti}^2\ge \frac{T}{d}\) by the definition of \(\tau_i\). The proof is completed using the randomisation hammer, \[\begin{align} \sum_{\theta\in\{\pm\Delta\}^d} R_T(\mathcal{A},\theta) &\ge \frac{\Delta\sqrt d}{2}\sum_{i=1}^d\sum_{\theta\in\{\pm\Delta\}^d} \mathbb{E}_\theta\!\left[U_i(\text{sgn}(\theta_i))\right] \\ &= \frac{\Delta\sqrt d}{2}\sum_{i=1}^d \sum_{\theta_{-i}\in\{\pm\Delta\}^{d-1}} \sum_{\theta_i\in\{\pm\Delta\}} \mathbb{E}_\theta\!\left[U_i(\text{sgn}(\theta_i))\right] \\ &\ge \frac{\Delta\sqrt d}{2}\sum_{i=1}^d \sum_{\theta_{-i}\in\{\pm\Delta\}^{d-1}} \left(\frac{T}{d}-2\right) = 2^{d-2}\,(T-2d)\Delta\sqrt d \;. \end{align}\] Hence, assuming that \(T\geq 4d\), there exists \(\theta\in\{\pm\Delta\}^d\) such that \[R_T(\mathcal{A},\theta) \ge \frac{T}{2}\cdot \frac{\Delta\sqrt d}{4} = \frac{\sqrt{dT}}{64}.\] This gives the second lower bound on the constant \(C_{d, T}\) in the statement of the theorem.

12.0.0.2 Adversarial environment with bounded losses

The proof for this case is largely adapted from the previous proof, that we refer to as the “stochastic case” in the following for simplicity, although the proof still builds on stochastically generated losses. We still assume that

The adversary selects a parameter \(\theta \in \Theta\) before the interaction.
At step \(t\), it draws a loss \(\widetilde{\ell}_t = \theta + \epsilon_t\), where \(\epsilon_t \sim \mathcal{N}(0, \sigma_d^2 I_d)\), for some \(\sigma_d>0\).

but we make two changes. First we change the noise level \(\sigma_d^2\) from \(\frac{1}{2d}\) to something smaller. Secondly, we make the adversary select a clipped version of this random loss \(\ell_t=\widetilde{\ell}_t \mathbb{I}\!\left(\|\widetilde{\ell}_t\| \leq 1\right)\). The intuition is that clipping will enforce a bounded norm almost surely.

However, a core ingredient of the proof we will be to calibrate the noise level \(\sigma_d^2\) in order to make clipping very unlikely, so that the statistical properties of this model will be very close to the Gaussian stochastic model that we already studied. Furthermore, we will use that any rescaling of the variance propagates easily in the previous proof, as it only appears in the KL term induced after using Pinsker inequality, and thus propagates naturally to the choice of the gap \(\Delta\).

To start the proof, we first show that we can express the regret \(\widetilde{R}_T(\mathcal{A}, \theta)\) on the clipped environment, against the comparator \(u_\theta\), as a function of the regret \(R_T(\mathcal{A},\theta)\) as defined in the unclipped environment. Assume this time that \(\|\theta\|^2\leq \frac{1}{4}\). Under this condition, we can write that \[\begin{align} \widetilde{R}_T(\mathcal{A}, \theta) &= \mathbb{E}_\theta\left[\sum_{t=1}^T \left\langle x_t-u_\theta, \widetilde{\ell}_t \mathbb{I}\!\left(\|\widetilde{\ell}_t\|\leq 1\right) \right\rangle \right] \\ & = \mathbb{E}_\theta\left[\sum_{t=1}^T \left\langle x_t-u_\theta, \widetilde{\ell}_t \right\rangle \right] + \mathbb{E}_\theta\left[\sum_{t=1}^T \left\langle x_t-u_\theta, \widetilde{\ell}_t \mathbb{I}\!\left(\|\widetilde{\ell}_t\|\geq 1\right) \right\rangle \right] \\ & = R_T(\mathcal{A},\theta) + \mathbb{E}_\theta\left[\sum_{t=1}^T \left\langle x_t-u_\theta, \widetilde{\ell}_t \mathbb{I}\!\left(\|\widetilde{\ell}_t\|\geq 1\right) \right\rangle \right] \\ & \geq R_T(\mathcal{A},\theta) - 4\mathbb{E}_\theta\left[\sum_{t=1}^T \|\widetilde{\ell}_t\|^2\mathbb{I}\!\left(\|\widetilde{\ell}_t\|\geq 1\right) \right] \\ & \geq R_T(\mathcal{A},\theta) - 8\mathbb{E}_\theta\left[\sum_{t=1}^T (\|\theta\|^2 + \|\epsilon_t\|^2)\mathbb{I}\!\left(\|\widetilde{\ell}_t\|\geq 1\right) \right] \\ & \geq R_T(\mathcal{A},\theta) - 16T\cdot \mathbb{E}_\theta\left[\|\epsilon_1\|^2\mathbb{I}\!\left(\|\epsilon_1\|^2\geq \frac{1}{4}\right) \right], \end{align}\] where in the last line we used that all terms of the sum have the same expectation, and that \(\mathbb{I}\!\left(\|\widetilde{\ell}_1\|\geq 1\right)\leq \mathbb{I}\!\left(\|\epsilon_1\|^2\geq \frac{1}{4}\right)\) and that under this event \(\|\theta\|\leq \|\epsilon_1\|\). We leave this term for now, and focus on lower bounding \(R_T(\mathcal{A}, \theta)\) by using the proof outline introduced for the first lower bound we proved (in the stochastic model).

Then, we can again lower bound the term \(R_T(\mathcal{A}, \theta)\) with Eq. 18 and use the same terms \(U_i(\sigma)\). However, some care is needed to adapt Equation 19 .

We introduce the notation \(\mathbb{E}_{\widetilde{\theta}}[U_i(\sigma)]\) to denote the expectation of \(U_i(\sigma)\) if the learner was provided the untruncated losses \((\widetilde{\ell}_t)_{t\geq 1}\) at each time step under the environment defined by \(\theta\), and similarly for \(\mathbb{E}_{\widetilde{\theta}'}[U_i(\sigma)]\).

Using these definitions, our goal is to obtain an inequality involving \(\mathbb{E}_\theta[U_i(1)]\) and \(\mathbb{E}_{\theta'}[U_i(1)]\) is a similar way as Equation 20 . However, a subtlety is that algorithm \(\mathcal{A}\) may not be able to handle unbounded values for \(x_t^\top \widetilde{\ell}_t\). Thus, we need to further define an extension of algorithm \(\mathcal{A}\), that we denote by \(\overline{\mathcal{A}}\).

We define \(\overline{\mathcal{A}}\) as follows: whenever \(x_t^\top\widetilde{\ell}_t>1\), the algorithm skips its update and defines \(x_{t+1}=x_t\), and otherwise uses the same update rule as \(\mathcal{A}\). We then denote by \(\mathcal{G}\) the event that no loss is clipped during the interaction: \(\mathcal{G}= \{\forall t\in [T]: \ell_t = \widetilde{\ell}_t\}\). Under \(\mathcal{G}\), it further holds that the outputs of algorithms \(\mathcal{A}\) and \(\overline{\mathcal{A}}\) match, so \(\mathbb{E}_{\theta, \mathcal{A}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)]= \mathbb{E}_{\theta, \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)]\), and thus \[\mathbb{E}_{\theta, \mathcal{A}}[U_i(\sigma)]\geq \mathbb{E}_{\theta, \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)] \;.\] Then, using that \(\mathbb{E}_{\theta, \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)]= \mathbb{E}_{\widetilde{\theta}, \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)]\) we can further obtain that \[\begin{align} \mathbb{E}_{\theta, \mathcal{A}}[U_i(\sigma)] &\geq \mathbb{E}_{\widetilde{\theta}, \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)] \\ &=\mathbb{E}_{\widetilde{\theta}', \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)] + \mathbb{E}_{\widetilde{\theta}, \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)] - \mathbb{E}_{\widetilde{\theta}', \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)] \\ & \geq \mathbb{E}_{\widetilde{\theta}', \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)] + \underbrace{\mathbb{E}_{\widetilde{\theta}, \overline{\mathcal{A}}}[U_i(\sigma)] - \mathbb{E}_{\widetilde{\theta}', \overline{\mathcal{A}}}[U_i(\sigma)]}_{-V} - \mathbb{E}_{\widetilde{\theta}', \overline{\mathcal{A}}}[U_i(\sigma)\mathbb{I}\!\left(\overline{\mathcal{G}}\right)]\\ & = \mathbb{E}_{\theta', \mathcal{A}}[U_i(\sigma)\mathbb{I}\!\left(\mathcal{G}\right)] -V - \frac{2T}{d} \mathbb{P}(\mathcal{G}^c) \\ & \geq \mathbb{E}_{\theta', \mathcal{A}}[U_i(\sigma)] -V - \frac{4T}{d} \mathbb{P}(\mathcal{G}^c)\;, \end{align}\] where we used that \(U_i(\sigma)\) is non-negative and bounded by \(\frac{T}{d}\). We now remark that the term \(V\) can be upper bounded by following the exact same steps as in the unclipped Gaussian environment, since algorithm \(\overline{\mathcal{A}}\) can process unbounded feedback and receives losses of the form \(\left\langle x_t, \theta +\epsilon_t \right\rangle\), with \(\epsilon_t\sim\mathcal{N}(0, \sigma_d^2 I_d)\). The only difference is that the scaling factor \(\sigma_d^2\) will replace \(\frac{1}{2d}\).

Furthermore, while in previous proof \(\Delta\) was tuned to make this term smaller than \(\frac{T}{d}\), here we can choose it to ensure that \(V\leq \frac{T}{2d}\), and also choose \(\sigma_d^2\) so that \(\frac{4T}{d}\mathbb{P}(\mathcal{G}^c) \leq \frac{T}{2d}\) too, so we can exactly recover Equation 21 . It is clear that, assuming that the later bound holds, the desired result can be obtained by simply multiplying \(\Delta\approx 1/\sqrt{T}\) by a factor of order \(\sqrt{2d\sigma_d^2}\).

It remains to calibrate the noise level. By independence between time steps and Gaussianity of the noise, we have that \[\begin{align} \mathbb{P}(\mathcal{G}^c) & \leq T \mathbb{P}(\|\widetilde{\ell}_1\| \geq 1) \\ &= T \mathbb{P}(\|\theta+\epsilon_1\|^2 \geq 1) \\ &\leq T \mathbb{P}(2\|\theta\|^2 + 2\|\epsilon_1\|^2 \geq 1) \\ &\leq T \mathbb{P}\left(\|\epsilon_1\|^2 \geq \frac{1}{8}\right), \\ \end{align}\] if we assume that \(\|\theta\|^2\leq \frac{1}{4}\). The last arguments of the proof rely on the Laurent-Massart inequality for chi-squared random variables [40]. For all \(t\ge 0\), it holds that \[\label{eq:chisquare} \mathbb{P}\!\left(\|\varepsilon_1\|^2 \ge \sigma_d^2\big(d + 2\sqrt{dt} + 2t\big)\right) \le e^{-t}.\tag{22}\] To convert this bound for a fixed threshold \(x>0\), we define \(a:=x/\sigma_d^2\), and remark that if \(a\ge d\) we can set \[t_x \;:=\;\left(\frac{\sqrt{2a-d}-\sqrt d}{2}\right)^2 \quad, \quad\text{so that }a=d+2\sqrt{d t_x}+2t_x \;.\] Then, by 22 , \[\label{eq:tail-x} \mathbb{P}(\|\varepsilon\|^2 \ge x)\;\le\;\exp(-t_x) \;=\;\exp\!\left(-\left(\frac{\sqrt{2\frac{x}{\sigma_d^2}-d}-\sqrt d}{2}\right)^2\right), \qquad (\text{for } x\ge \sigma^2 d).\tag{23}\] We use this bound to first identify a variance level \(\sigma_d^2\) guaranteeing \(\frac{4T}{d}\mathbb{P}(\mathcal{G}^c)\leq \frac{T}{2d}\), so that this term fits easily in the proof framework of the stochastic case. To ensure this condition it suffices that \(\mathbb{P}\left(\|\varepsilon\|^2 \ge \frac{1}{8}\right) \leq \frac{1}{8T}\), which by Eq. 23 can be achieved by choosing \(\sigma_d^2\) as follows, \[\label{eq::tuning95sigma}\exp\!\left(-\left(\frac{\sqrt{\frac{1}{4\sigma_d^2}-d}-\sqrt d}{2}\right)^2\right)= \frac{1}{8T} \quad \Longleftrightarrow \quad \sigma_d^2 = \frac{1}{4}\cdot \frac{1}{d+(\sqrt{d}+2\sqrt{\log(8T)})^2} \;,\tag{24}\] which is of order \(\frac{1}{d\vee \log(T)}\), yielding the rescaling factor introduced in the theorem.

Thus, to lower bound \(\widetilde{R}_T(\mathcal{A}, \theta)\) it only remains to upper bound the term \[E \mathrel{\vcenter{:}}= 16T\cdot \mathbb{E}_\theta\left[\|\epsilon_1\|^2\mathbb{I}\!\left(\|\epsilon_1\|^2\geq \frac{1}{4}\right) \right] \;.\] We first rewrite the expectation as \[\begin{align} \mathbb{E}\left[ \|\epsilon_1\|^2\mathbb{I}\!\left(\|\epsilon_1\|^2\geq \frac{1}{4}\right) \right] &= \frac{1}{4}\,\mathbb{P}\left(\|\epsilon_1\|^2\ge \frac{1}{4}\right) + \int_{\frac{1}{4}}^\infty \mathbb{P}(\|\epsilon_1\|^2\ge u)\,\mathrm{d}u \\ & \leq \frac{1}{32T} + \int_{\frac{1}{4}}^\infty \mathbb{P}(\|\epsilon_1\|^2\ge u)\,\mathrm{d}u, \end{align}\] where we used that \(\mathbb{P}\left(\|\epsilon_1\|^2\ge \frac{1}{4}\right)\leq \mathbb{P}\left(\|\epsilon_1\|^2\ge \frac{1}{8}\right) \leq \frac{1}{8T}\), by our design. Furthermore, the fact that we could already apply Eq. 22 with threshold \(1/8\) guarantees that we can also apply it for any threshold \(u\) larger than \(1/4\), and the resulting concentration bound will be smaller than \(\frac{1}{8T}\). Hence, for any threshold \(u_0\geq \frac{1}{4}\), we can upper bound the remaining integral as follows, \[\begin{align} \int_{\frac{1}{4}}^\infty \mathbb{P}(\|\varepsilon_1\|^2\ge u)\,\mathrm{d}u &\leq \frac{u_0}{8T} + \int_{u_0}^\infty e^{-t_u}\,\mathrm{d}u \\ &\le \frac{u_0}{8T} + \int_{u_0}^\infty e^{- \frac{1}{4} \cdot \left(\sqrt{\frac{2u}{\sigma_d^2}-d}-\sqrt d\right)^2}\,\mathrm{d}u. \end{align}\] We then choose \(u_0\) in order to simplify the integral computation. More explicitly, we choose \(u_0\) to satisfy \[\sqrt{\frac{2u}{\sigma_d^2}-d}-\sqrt d \geq \sqrt{\frac{u}{\sigma_d^2}}, \; \text{for } u \geq u_0 \;.\] We then solve, for \(d>0\) and \(y\ge d/2\), \[\sqrt{2y-d}-\sqrt d \ge \sqrt y \quad\Longleftrightarrow\quad \sqrt{2y-d}\ge \sqrt y+\sqrt d.\] Squaring (both sides are nonnegative on the domain) gives \[2y-d \ge y+d+2\sqrt{yd} \quad\Longleftrightarrow\quad y-2d \ge 2\sqrt{yd}.\] In particular this forces \(y\ge 2d\). Squaring again yields \[(y-2d)^2 \ge 4yd \quad\Longleftrightarrow\quad y^2-8dy+4d^2 \ge 0.\] Solving the quadratic equation \(y^2-8dy+4d^2=0\) gives the roots \[y = \frac{8d\pm \sqrt{64d^2-16d^2}}{2} = d\,(4\pm 2\sqrt3).\] Keeping the positive solution, we get \[y \ge d(4+2\sqrt3) \Longleftrightarrow u \geq (4+2\sqrt{3})\cdot d\sigma_d^2 .\] Using these results, we can choose \(u_0=8d\sigma_d^2 \vee 4\sigma_d^2 \log(64T)\) and obtain that \[\begin{align} E & \leq \frac{1}{2} + 2u_0 + 16T\cdot\int_{u_0}^{+\infty} e^{-\frac{u}{4\sigma_d^2}} \mathrm{du} \\ & = \frac{1}{2} + 2u_0 + 64 \sigma_d^2 T e^{-\frac{u_0}{4\sigma_d^2}} \\ & \leq \frac{1}{2} + 16\sigma_d^2 \left\{d \vee \frac{1}{2}\log(64T)\right\} + \sigma_d^2 \\ & \leq \frac{1}{2} + 4\frac{ \left\{d \vee \log(8T)\right\} }{d+4\log(8T)} + \sigma_d^2 \\ & \leq 5 \;, \end{align}\] where we used in the final step that \(\sigma_d^2\leq \frac{1}{2}\). Hence, we proved that the tuning of \(\sigma_d^2\) from Equation 24 is sufficient to ensure that the bias term \(E\) is upper bounded by a constant. This concludes the proof. ◻

Remark 3. One might think that it could be possible to build hard instances based on simpler distributions, e.g. using Rademacher variables. However, the problem there is that simple constructions do not obtain the right properties. Everything is essentially in the balance between the maximum per-round regret/gain of the adversary and the difficulty to distinguish the instances (the KL term above).

For instance, if the adversary (1) sample a coordinate \(I_t\) uniformly at random, and (2) returns a loss \(\sigma e_{I_t}\) where \(\sigma\) is a Rademacher variable with mean \(\theta_i\) then:

The KL term becomes \(\mathcal{O}(\Delta^2\tau_i/d)=\mathcal{O}(\Delta^2T/d)\), while we had (\(\Delta^2 d/T \sum_{t=1}^{\tau_i}x_{ti}^2\leq \Delta^2T\) above).
But the gain of the adversary is defined by \(d\) (one coordinate showed at a time, but the optimal comparator still plays \(1/\sqrt{d}\) weight on each!).

So, overall balancing the two makes the \(d\) cancel and we even just get \(\sqrt{T}\). The same holds if instead of selecting a coordinate the adversary would just rescale the Rademacher variables by \(1/\sqrt{d}\) because now the expected regret becomes multiplied by \(1/\sqrt{d}\) (Eq. 18 has no more \(\sqrt{d}\)). Then, the KL becomes \(Td\Delta^2\) essentially, so it’s clear we get an even worse tradeoff.

And finally, Gaussian noise is the simplest distribution that allows us to use that \(\sum_{t=1}^{\tau_i}x_{ti}^2\leq \frac{T}{d}\)

13 Regret of OSMD against a norm-adaptive adversary↩︎

In this section we develop the computations leading to our claim from Section 3.1 that OSMD only yields an \(\mathcal{O}((dT)^{2/3})\) direction regret when used as a direction learner, under a norm-adaptive adversary. We can start the analysis from the first bound of their Theorem 6, which states that the regret of OSMD is upper bounded by \[R_T \leq \gamma T + \frac{\log(\gamma^{-1})}{\eta}+ \eta \sum_{t=1}^T \mathbb{E}\left[ (1-\|z_t\|) \|\widetilde{z}_t\|^2 \right],\] where \(\gamma\) and \(\eta\) are parameters chosen by the learner. When optimized, they yield \(R_T\leq 3\sqrt{dT\log(T)}\) in the \(\mathcal{F}_0\)-measurable regime.

However, in the norm-adaptive case the norm \(\|u\|\) must go inside the last expectation, giving a term \(\eta \sum_{t=1}^T \mathbb{E}\left[ \|u\|(1-\|z_t\|) \|\widetilde{z}_t\|^2 \right]\). This breaks the upper bound presented in the paper, because of the potential correlation between \(\|u\|\) and each of the realizations \(\widetilde{z}_t\). Because of this, we can only use the crude bound \[\sum_{t=1}^T \mathbb{E}\left[ \|u\|(1-\|z_t\|) \|\widetilde{z}_t\|^2 \right] \leq \mathbb{E}\left[ \|u\|\sum_{t=1}^T\frac{d^2 \|\ell_t\|^2}{1-\|x_t\|} \right] \leq \frac{d^2T}{\gamma} \mathbb{E}\left[ \|\cmp\| \right] \;,\] while the same term is upper bounded by \(dT\|u\|\) in the \(\mathcal{F}_0\)-measurable case. In this case, choosing \(\eta=\left(\frac{\log(T)}{dT}\right)^{\frac{2}{3}}\) and \(\gamma=d\sqrt{\eta}\) give a regret bound of order \((dT)^{\frac{2}{3}}(\log(T))^{1/3}\mathbb{E}\left[ \|u\| \right]\), which shows the degradation of the guarantees of OSMD as a direction learner, in the norm-adaptive setting. As a final remark, we highlight that this claim is based on plugging a conservative bound in the proof of [19], which doesn’t prove that this result can’t be improved with a more elaborate decomposition.

14 Fenchel Conjugate Characterization of Comparator-Adaptive Bounds↩︎

The connection between Fenchel conjugates and regret bounds in online learning is well-established; see, e.g., [4] for a textbook treatment and [15], [29], [41] for applications to parameter-free and comparator-adaptive algorithms.

Recall that the Fenchel conjugate of a function \(f: \mathbb{R}^d \to \mathbb{R}\) is defined as \[f^*(y) = \sup_{x \in \mathbb{R}^d} \left\{ \left\langle x, y \right\rangle - f(x) \right\}.\]

Consider the regret defined as \[R_T(u) = \sum_{t=1}^T \left\langle \ell_t,w_t-u \right\rangle= \sum_{t=1}^T \left\langle \ell_t^\top, w_t \right\rangle - \left\langle L_T,u \right\rangle,\] where \(L_T = \sum_{t=1}^T \ell_t\) denotes the cumulative loss vector.

Suppose we want to establish a comparator-adaptive bound of the form \(R_T(u) \leq B_T(u)\) for all \(u\), where \(B_T: \mathbb{R}^d \to \mathbb{R}_+\) is some bound function (e.g., \(B_T(u) = \mathcal{O}(\|u\|\sqrt{T \log(\|u\| T)}\))).

The condition “\(R_T(u) \leq B_T(u)\) for all \(u\)” can be rewritten as: \[\begin{align} &\forall u: \quad \sum_{t=1}^T \left\langle \ell_t,w_t \right\rangle - \left\langle L_T,u \right\rangle \leq B_T(u) \\ \iff \quad &\sum_{t=1}^T \left\langle \ell_t,w_t \right\rangle \leq \inf_u \left\{ \left\langle L_T,u \right\rangle + B_T(u) \right\} \\ \iff \quad &\sum_{t=1}^T \left\langle \ell_t,w_t \right\rangle \leq -\sup_u \left\{ \left\langle u, -L_T \right\rangle - B_T(u) \right\} \\ \iff \quad &\sum_{t=1}^T \left\langle \ell_t,w_t \right\rangle \leq -B_T^*(-L_T). \end{align}\] Thus, the comparator-adaptive regret bound is equivalent to \[\boxed{\sum_{t=1}^T \left\langle \ell_t,w_t \right\rangle \leq -B_T^*\left( -\sum_{t=1}^T \ell_t \right).}\]

Hence, the natural worst-case comparator in the unconstrained setting is \(\cmp\in\partial B_T^*(-\sum_t\ell_t)\), where \(B_T^*\) is the Fenchel conjugate of \(B_T\). If we for instance assume that the regret bound \(B_T\) admits the form \(B_T(u)=G\|\cmp\|\sqrt{T\log\left(\|\cmp\|\sqrt{T}/\epsilon+1\right)}\) as in the unconstrained OLO setting, this translates into a worst-case comparator having norm \[\|\cmp\|\propto \epsilon\exp\left(\frac{\|\sum_{t=1}^T\ell_t\|^2}{G^2T}\right),\] see for instance [25].

15 Supporting Lemmas↩︎

For completeness, this section collects various well-known lemmas, borrowed results, or otherwise tedius calculations we do not wish to repeat.

The following lemma is standard and included for completeness.

lemmaPBound Let \((\alpha_{t})_{t}\) be an arbitrary sequence of non-negative numbers and let \(p\ge 1\). Then \[\begin{align} \sum_{t=1}^T\frac{\alpha_{t}}{\left(\sum_{s=1}^{t}\alpha_{s}\right)^{1-1/p}}\le p\left(\sum_{t=1}^T\alpha_{t}\right)^{1/p} \end{align}\]

Proof. Let \(S_{t}=\sum_{s=1}^{t}\alpha_{s}\), and observe that by concavity of \(x\mapsto x^{1/p}\) for any \(p\ge 1\), we have \[\begin{align} S_{t}^{1/p}-S_{{t-1}}^{1/p}\ge \frac{S_{t}-S_{{t-1}}}{pS_{t}^{1-1/p}} = \frac{\alpha_{t}}{pS_{t}^{1-1/p}}=\frac{\alpha_t}{p\left(\sum_{s=1}^t\alpha_s\right)^{1-1/p}} \end{align}\] Hence summing over \(t\) yields \[\begin{align} \sum_{t=1}^T\frac{\alpha_{t}}{\left(\sum_{s=1}^{t}\alpha_{s}\right)^{1-1/p}}\le p\left(\sum_{t=1}^TS_{t}^{1/p}-S_{{t-1}}^{1/p}\right)=pS_{T}^{1/p} = p\left(\sum_{t=1}^T\alpha_{t}\right)^{1/p} \end{align}\] ◻

We also use the following standard integral bound

lemmaLogBound Let \((\alpha_{t})_{t}\) be an arbitrary sequence of non-negative numbers. Then \[\begin{align} \sum_{t=1}^T\frac{\alpha_{t}}{\alpha_0+\sum_{s=1}^{t}\alpha_{s}}\le \log\left(1+\frac{\sum_{t=1}^T\alpha_{t}}{\alpha_{0}}\right). \end{align}\]

Proof. We have via a standard integral bound (see, e.g., [4]) \[\begin{align} \sum_{t=1}^T\frac{\alpha_{t}}{\alpha_0+\sum_{s=1}^{t}\alpha_{s}}&\le \int_{\alpha_{0}}^{\alpha_0+\sum_{t=1}^T\alpha_{t}}\frac{1}{t}dt = \log\left(x\right)\Big|_{x=\alpha_{0}}^{\alpha_0+\sum_{t=1}^T\alpha_{t}} \\ &= \log\left(\alpha_0+\sum_{t=1}^T\alpha_{t}\right)-\log\left(\alpha_{0}\right)=\log\left(1+\frac{\sum_{t=1}^T\alpha_{t}}{\alpha_{0}}\right). \end{align}\] ◻

The following tuning lemma follows by observing that expressions of the form \(P/\eta + \eta V\) are minimized at \(\eta^*=\sqrt{P/V}\), and then applying simple case work to cover the edge cases \(\eta^*\) is outside of the range of candidate step-sizes.

lemmaTuningLemma Let \(b>1\), \(0<\eta_{\min}\le \eta_{\max}\) and let \(\mathcal{S}= \left\{\eta_{i}=\eta_{\min}b^{i}\wedge\eta_{\max} : i=0,1,\ldots\right\}\). Then for any \(P, V\in\mathbb{R}_{\ge 0}\), there is an \(\eta\in\mathcal{S}\) such that \[\begin{align} R(\eta):=\frac{P}{\eta}+ \eta V \le (b+1)\sqrt{PV} + \frac{P}{\eta_{\max}}+\eta_{\min}V \end{align}\]

We borrow the following concentration result from [28].

theoremwtConcentrationScalar ([28]) Suppose \(\{X_t,\mathcal{F}_t\}\) is a \((\sigma_t,b_t)\) sub-exponential martingale difference sequence. Let \(\nu\) be an arbitrary constant. Then with probability at least \(1-\delta\), for all \(t\) it holds that: \[\begin{align} \sum_{i=1}^t X_i &\le 2\sqrt{ \sum_{i=1}^t \sigma_i^2 \log\!\left( \frac{4}{\delta} \left[ \log\!\left( \left[\sqrt{\sum_{i=1}^t \sigma_i^2/(2\nu^2)}\right]_1 \right)+2 \right]^2 \right)}\\ &\qquad+ 8\,\max\!\left(\nu,\max_{i\le t} b_i\right) \log\!\left( \frac{28}{\delta} \left[ \log\!\left( \frac{\max(\nu,\max_{i\le t} b_i)}{\nu} \right)+2 \right]^2 \right)~. \end{align}\] where \([x]_1=\max(1,x)\).

We also use a mild modification of [28] which corrects a minor discrepancy in the “units” of the quantities involved.

Lemma 1. (Adapted from [28]) Suppose \(\mathcal{A}\) is an arbitrary OLO algorithm that guarantees regret \[R_T^{\mathcal{A}}(0)=\sum_{t=1}^T \langle g_t, w_t\rangle \le \epsilon G\] for \(T\ge 1\) and all sequences \((g_t)_{t\in[T]}\) with \(\|g_t\|\le G\). Then it must hold that \(\|w_t\| \le \epsilon2^{t-1}\) for all \(t\).

Proof. We first show that \[\begin{align} G\|\widetilde{\|}\le G\epsilon - R_{{t-1}}^\mathcal{A}(0).\label{eq:iterate-bound} \end{align}\tag{25}\] Indeed, suppose not; then on an arbitrary sequence of losses \(\g_1,\ldots,\g_{t-1}, \frac{\widetilde{}}{\|\widetilde{\|}}G}{None}\), we would have \[\begin{align} R_t^\mathcal{A}(0) = R_{t-1}^\mathcal{A}(0) + G\|\widetilde{\|} > G\epsilon, \end{align}\] contradicting the assumption \(\mathcal{A}\) guarantees that \(R_t^\mathcal{A}(0)\le G\epsilon\). Now with 25 established, observe that \[\begin{align} G\|\widetilde{\|}&\le G\epsilon - R^\mathcal{A}_{{t-1}}(0) = G\epsilon - R^\mathcal{A}_{t-2}(0) - \left\langle g_{t-1},w_{{t-1}} \right\rangle \le G\epsilon - R^\mathcal{A}_{t-2}(0) + G\|\w_{{t-1}}\|\\ &\le 2(G\epsilon - R^\mathcal{A}_{t-2}(0)) \le 2^2(G\epsilon - R^\mathcal{A}_{t-3}(0)) \le\ldots\le 2^{t-1}G\epsilon \end{align}\] hence dividing both sides by G we have \(\|\widetilde{\|}\le 2^{t-1}\epsilon\) ◻

References↩︎

[1]

Abernethy, J. D., Hazan, E., and Rakhlin, A. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pp. 263–274. Citeseer, 2008.

[2]

Shalev-Shwartz, S. Online learning and online convex optimization. Found. Trends Mach. Learn., 4 (2): 107–194, 2012. .

[3]

Hazan, E. et al. Introduction to online convex optimization. Foundations and Trends® in Optimization, 2 (3-4): 157–325, 2016.

[4]

Orabona, F. A modern introduction to online learning. CoRR, abs/1912.13213, 2019.

[5]

Flaxman, A. D., Kalai, A. T., and McMahan, H. B. Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 385–394, 2005.

[6]

Kalai, A. and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71 (3): 291–307, 2005.

[7]

Dani, V., Kakade, S. M., and Hayes, T. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20, 2007.

[8]

Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.

[9]

Lattimore, T. Bandit convex optimisation. CoRR, abs/2402.06535, 2024. .

[10]

van der Hoeven, D., Cutkosky, A., and Luo, H. Comparator-adaptive convex bandits. In Advances in Neural Information Processing Systems, volume 33, 2020.

[11]

Luo, H., Zhang, M., Zhao, P., and Zhou, Z.-H. Corralling a larger band of bandits: A case study on switching regret for linear bandits. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 3635–3684. PMLR, 02–05 Jul 2022.

[12]

Rumi, A., Jacobsen, A., Cesa-Bianchi, N., and Vitale, F. Parameter-free dynamic regret for unconstrained linear bandits. In The 29th International Conference on Artificial Intelligence and Statistics, 2026.

[13]

Mcmahan, B. and Streeter, M. No-regret algorithms for unconstrained online convex optimization. In Pereira, F., Burges, C. J. C., Bottou, L., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.

[14]

Orabona, F. and Pál, D. Coin betting and parameter-free online learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, pp. 577–585, Red Hook, NY, USA, 2016. Curran Associates Inc.

[15]

Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in banach spaces. In Bubeck, S., Perchet, V., and Rigollet, P. (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 1493–1529. PMLR, 2018.

[16]

McMahan, H. B. and Blum, A. Online geometric optimization in the bandit setting against an adaptive adversary. In International Conference on Computational Learning Theory, pp. 109–123. Springer, 2004.

[17]

Awerbuch, B. and Kleinberg, R. D. Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pp. 45–53, New York, NY, USA, 2004. Association for Computing Machinery. ISBN 1581138520. .

[18]

Dani, V. and Hayes, T. P. Robbing the bandit: less regret in online geometric optimization against an adaptive adversary. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, pp. 937–943, USA, 2006. Society for Industrial and Applied Mathematics. ISBN 0898716055.

[19]

Bubeck, S., Cesa-Bianchi, N., and Kakade, S. M. Towards minimax policies for online linear optimization with bandit feedback. In Mannor, S., Srebro, N., and Williamson, R. C. (eds.), COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pp. 41.1–41.14. JMLR.org, 2012.

[20]

Shamir, O. On the complexity of bandit linear optimization. In Grünwald, P., Hazan, E., and Kale, S. (eds.), Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pp. 1523–1551. JMLR.org, 2015.

[21]

Lee, C.-W., Luo, H., Wei, C.-Y., and Zhang, M. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33: 15522–15533, 2020.

[22]

Zimmert, J. and Lattimore, T. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 3285–3312. PMLR, 02–05 Jul 2022.

[23]

Agarwal, A., Luo, H., Neyshabur, B., and Schapire, R. E. Corralling a band of bandit algorithms. In Conference on Learning Theory, pp. 12–38. PMLR, 2017.

[24]

Marinov, T. V. and Zimmert, J. The pareto frontier of model selection for general contextual bandits. In Advances in Neural Information Processing Systems, 2021.

[25]

McMahan, H. B. and Orabona, F. Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. In Balcan, M. F., Feldman, V., and Szepesvári, C. (eds.), Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pp. 1020–1039, Barcelona, Spain, 13–15 Jun 2014. PMLR.

[26]

Orabona, F. and Pál, D. Parameter-free stochastic optimization of variationally coherent functions, 2021.

[27]

Mhammedi, Z. and Koolen, W. M. Lipschitz and comparator-norm adaptivity in online learning. In Abernethy, J. and Agarwal, S. (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2858–2887. PMLR, 09–12 Jul 2020.

[28]

Zhang, J. and Cutkosky, A. Parameter-free regret in high probability with heavy tails. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.

[29]

Jacobsen, A. and Cutkosky, A. Parameter-free mirror descent. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 4160–4211. PMLR, 2022.

[30]

Zhang, Z., Cutkosky, A., and Paschalidis, Y. Unconstrained dynamic regret via sparse coding. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 74636–74670. Curran Associates, Inc., 2023.

[31]

Jacobsen, A. and Cutkosky, A. Unconstrained online learning with unbounded losses. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 14590–14630. PMLR, 2023.

[32]

Jacobsen, A. and Orabona, F. An equivalence between static and dynamic regret minimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.

[33]

Jacobsen, A., Rudi, A., Orabona, F., and Cesa-Bianchi, N. Dynamic regret reduces to kernelized static regret. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.

[34]

Streeter, M. J. and McMahan, H. B. No-regret algorithms for unconstrained online convex optimization. In Advances in Neural Information Processing Systems, 2012.

[35]

Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19 (4): 1574–1609, 2009.

[36]

Neu, G. and Okolo, N. Dealing with unbounded gradients in stochastic saddle-point optimization. In Proceedings of the 41st International Conference on Machine Learning, pp. 37508–37530, 2024.

[37]

Abernethy, J. D., Hazan, E., and Rakhlin, A. Interior-point methods for full-information and bandit online learning. IEEE Transactions on Information Theory, 58 (7): 4164–4175, 2012.

[38]

Daniely, A., Gonen, A., and Shalev-Shwartz, S. Strongly adaptive online learning. In International Conference on Machine Learning, pp. 1405–1411. PMLR, 2015.

[39]

Cutkosky, A. Combining online learning guarantees. In Beygelzimer, A. and Hsu, D. (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 895–913, Phoenix, USA, 2019. PMLR.

[40]

Laurent, B. and Massart, P. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28 (5): 1302–1338, 2000.

[41]

Zhang, Z., Cutkosky, A., and Paschalidis, I. C. Pde-based optimal strategy for unconstrained online learning. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, 2022.

In particular, their lower bound holds for finite policy classes.↩︎
Concretely, common classes of sequences are the static comparator sequences, sequences satisfying some path-length or diameter constraint, or the class of all sequences in \(\mathbb{R}^d\).↩︎
The same idea can be extended to broader policy classes, but this assumption keeps the example transparent.↩︎
e.g. starting with a constant unit loss at first, and switching to \(0\) after the first non-exploratory round↩︎
The theorem statement in [28] is given in terms of \(\widetilde{\mathcal{O}}(\log\left(1/\delta\right))\), which hides a \(T\) dependency inside the logarithm, as can be observed from the parameter settings for \(c_{1}\) and \(c_{2}\) in [thm:optimistic-heavy-tailed]. We highlight this \(T\) dependence in our re-statement to facilitate a more direct comparison to the high-probability bounds of [22].↩︎

A Perturbation Approach to Unconstrained Linear Bandits

Abstract

1 Introduction↩︎

1.2 Contributions↩︎

2 Perturbation-based approach↩︎

2.1 Generic Expected Regret Analysis for BLO↩︎

3 Novel expected regret bounds for uBLO↩︎

3.1 Static Regret via Parameter-free OLO↩︎

3.2 Dynamic Regret in Expectation↩︎

4 High-probability Bounds↩︎

5 Towards lower bounds for uBLO↩︎

5.0.0.1 “Scale” lower bound from uOLO.

6 Future Directions↩︎

Acknowledgements↩︎

Impact Statement↩︎

7 General Reduction to OLO for Expected Regret↩︎

8 Proof of Theorem [thm:expected-static]↩︎

9 Proof of Theorem 2 ↩︎

10 High-probability Guarantees↩︎

10.1 Reduction to OLO↩︎

10.2 High-probability Static Regret Guarantees↩︎

10.3 High-Probability Dynamic Regret Guarantees↩︎

10.3.1 Extension to Arbitrary Comparator Sequences↩︎

11 Results for Online Convex Optimization↩︎

11.1 Online Learning with Optimistic Composite-penalty Cancellation↩︎

11.1.1 Useful Lemmas for Huber-like Penalties↩︎

11.2 Refined Dynamic Regret Algorithm for OCO↩︎

12 Proof of Theorem 3 ↩︎

12.0.0.1 Stochastic model

12.0.0.2 Adversarial environment with bounded losses

13 Regret of OSMD against a norm-adaptive adversary↩︎

14 Fenchel Conjugate Characterization of Comparator-Adaptive Bounds↩︎

15 Supporting Lemmas↩︎

References↩︎

Subjects

Updated on Academus

A Perturbation Approach to Unconstrained Linear Bandits

Abstract

1 Introduction↩︎

1.1 Related Works↩︎

1.2 Contributions↩︎

2 Perturbation-based approach↩︎

2.1 Generic Expected Regret Analysis for BLO↩︎

3 Novel expected regret bounds for uBLO↩︎

3.1 Static Regret via Parameter-free OLO↩︎

3.2 Dynamic Regret in Expectation↩︎

4 High-probability Bounds↩︎

5 Towards lower bounds for uBLO↩︎

5.0.0.1 “Scale” lower bound from uOLO.

6 Future Directions↩︎

Acknowledgements↩︎

Impact Statement↩︎

7 General Reduction to OLO for Expected Regret↩︎

8 Proof of Theorem [thm:expected-static]↩︎

9 Proof of Theorem 2↩︎

10 High-probability Guarantees↩︎

10.1 Reduction to OLO↩︎

10.2 High-probability Static Regret Guarantees↩︎

10.3 High-Probability Dynamic Regret Guarantees↩︎

10.3.1 Extension to Arbitrary Comparator Sequences↩︎

11 Results for Online Convex Optimization↩︎

11.1 Online Learning with Optimistic Composite-penalty Cancellation↩︎

11.1.1 Useful Lemmas for Huber-like Penalties↩︎

11.2 Refined Dynamic Regret Algorithm for OCO↩︎

12 Proof of Theorem 3↩︎

12.0.0.1 Stochastic model

12.0.0.2 Adversarial environment with bounded losses

13 Regret of OSMD against a norm-adaptive adversary↩︎

14 Fenchel Conjugate Characterization of Comparator-Adaptive Bounds↩︎

15 Supporting Lemmas↩︎

References↩︎

Subjects

Updated on Academus

9 Proof of Theorem 2 ↩︎

12 Proof of Theorem 3 ↩︎