Abstract

1. Introduction
In many real-world applications, data are inherently accumulated over time, and thus it is of great importance to develop a learning system that updates in an online fashion. Online Convex Optimization (OCO) is a powerful paradigm for learning in such scenarios, which can be regarded as an iterative game between a player and an adversary. At iteration t , the player chooses a decision vector x t from a convex set X ⊂ R d . Subsequently, the adversary discloses a convex function f t : X → R, and the player incurs a loss denoted by f ( x t ). The standard performance measure is the (static) regret (Zinkevich, 2003),
which is the difference between cumulative loss incurred by the online algorithm and that of the best decision in hindsight. The rationale behind such a metric is that the best fixed decision in hindsight is reasonably good over all the iterations. However, this might be too optimistic and may not hold in changing environments, where data are evolving and the optimal decision is drifting over time. To address this limitation, dynamic regret is proposed to compete with changing comparators u1,..., uT E X,
which draws considerable attention recently (Zhang et al., 2018a; Zhao et al., 2020b; Cutkosky, 2020; Zhao et al., 2021a; Baby and Wang, 2021). The measure is also called the universal dynamic regret (or general dynamic regret), in the sense that it gives a universal guaran- tee that holds against any comparator sequence. Note that the static regret (1) can be viewed as its special form by choosing comparators as the fixed best decision in hindsight. Moreover, a variant appeared frequently in the literature is called the worst-case dynamic regret (Besbes et al., 2015; Jadbabaie et al., 2015; Mokhtari et al., 2016; Yang et al., 2016; Wei et al., 2016; Zhang et al., 2017; Baby and Wang, 2019; Yuan and Lamperski, 2020; Zhao et al., 2020a; Zhang et al., 2020a,b; Zhao and Zhang, 2021), defined as
which specializes the general form ( 2 ) with comparators u t = x i ∈ arg min x ∈ x f t ( x ). There- fore, universal dynamic regret is very general and can include the static regret (1) and the worst-case dynamic regret (3) as special cases by different instantiations of comparators. We further remark that the worst-case dynamic regret is often too pessimistic, whereas the universal one is more adaptive to non-stationary environments.  Actually, the changes of on- line functions usually come from two aspects: one is the sampling randomness and the other one is the environmental non-stationarity, and clearly the latter one is the main focus of non-stationary online learning. Optimizing the worst-case dynamic regret can be problem- atic in some cases. For example, considering the stochastic optimization task where f t 's are independently randomly sampled from the same distribution, then minimizing the worst- case dynamic regret is evidently inappropriate and will eventually lead to overfitting (Zhang et al., 2018a) because the minimizer of online loss function could be dramatically different from the minimizer of the expected loss function due to the sampling randomness. There are many studies on the worst-case dynamic regret (Besbes et al., 2015; Jadbabaie et al., 2015; Mokhtari et al., 2016; Yang et al., 2016; Zhang et al., 2017, 2018b; Baby and Wang, 2019; Zhang et al., 2020b; Zhao and Zhang, 2021), but only few results are known for the universal dynamic regret. Zinkevich (2003) shows that online gradient descent (OGD) with a step size η > 0 achieves an O ((1 + P T ) /η+ηT ) universal dynamic regret, where P T = Σ t = 2 || u t −1 − u t ||2 is the path length of comparators u 1 , . . . , u τ and thus reflects the non- stationarity of the environments. When the path length Pr was known, one could choose the optimal step size η ∗ = Θ( √ (1 + P T )/ T ) and attain an O ( √ T (1 + P T )) dynamic regret. However, this path length quantity is hard to know since the universal dynamic regret aims to provide guarantees against any feasible comparator sequence. The step size η = Θ(1/√T) commonly used in static regret would lead to an inferior O(√T(1 + Pr)) bound, which exhibits a large gap from the favorable bound with an oracle step size tuning. Zhang et al. ( 2018a ) resolve the issue by proposing a novel online algorithm to search the optimal step size η * , attaining an O ( √ T (1 + P T )) universal dynamic regret, and they also establish an Ω( √ T(1 + P T )) lower bound to show the minimax optimality. Although the rate is minimax optimal for convex functions, we would like to design algorithms with more adaptive bounds. Specifically, we aim to enhance the guarantee for some easy problem instances, particularly when the online functions are smooth, by replacing the dependence on T by certain problem-dependent quantities that are O ( T ) in the worst case while could be much smaller in benign environments. In the study of static regret, we can attain such results like small-loss bounds (Srebro et al., 2010) and gradient- variation bounds (Chiang et al., 2012). Thus, a natural question arises whether it is possible to achieve similar problem-dependent guarantees for the universal dynamic regret? In this paper, extending our preliminary work (Zhao et al., 2020b), we pro- Our results. vide an affirmative answer by designing online algorithms with problem-dependent dynamic regret bounds. Specifically, we focus on the following two adaptive quantities: the gradient variation of online functions V T , and the cumulative loss of the comparator sequence F T , defined as
The two problem-dependent quantities are both at most O ( T ) under standard assumptions of online learning, while could be much smaller in easier problem instances. We propose two novel online algorithms called Sword and Sword++ ("Sword" is short for Smoothness-aware online learning with dynamic regret) that are suitable for different feedback models. Our algorithms are online ensemble methods ( Zhou, 2012 ; Zhao, 2021 ), which admit a two-layer structure with a meta-algorithm running over a group of base-learners. We prove that they enjoy an O( \ /(1 + P r + min{ V r, F r })(1 + P r }) dynamic regret, achieving gradient- variation and small-loss bounds simultaneously.  Comparing to the O( √ T(1 + P T )) minimax rate, our result replaces the dependence on T by the problem-dependent quantity P T + min{VT,FT}. Our bounds become much tighter when the problem is easy (for example when P T and V T / F T are sublinear in T ), and meanwhile safeguard the same guarantee in the worst case.  Hence, our results are adaptive to the intrinsic difficulty of problem instances as well as the non-stationarity of environments. Our first algorithm, Sword, achieves the favorable problem-dependent guarantees under the multi-gradient feedback model, namely, the player can query gradient information mul- tiple times at each round. This algorithm is conceptually simple, but the gradient query complexity is O (log T ) at each round. Our second algorithm, Sword++, is an improved version that requires only one gradient per iteration, despite using a two-layer online en- semble structure. As a result, Sword++ is not only computationally efficient but also more attractive due to its reduced feedback requirements — Sword++ can be applied to the more challenging one-gradient feedback model, where the player only receives gradient ∇ f t ( x t ) as the feedback after submitting the decision x t . Furthermore, it is worth mentioning that Sword++ has the potential to be extended to more constrained feedback models, such as the two-point bandit convex optimization, by further leveraging the technique for gradient- variation static regret minimization presented in ( Chiang et al., 2013 ). Technical contributions.  Note that there exist studies showing that the worst-case dy- namic regret can benefit from smoothness (Yang et al., 2016; Zhang et al., 2017; Zhao and Zhang, 2021). However, their analyses do not apply to our universal dynamic regret, as we cannot exploit the optimality condition of comparators u 1 , . . . , u T , in stark contrast with the worst-case dynamic regret analysis. As a result, we propose an adaptive online ensemble method to hedge non-stationarity while extracting adaptivity. Specifically, we em- ploy the meta-base two-layer ensemble to hedge the non-stationarity and utilize optimistic online learning to reuse the historical gradient information adaptively. Two crucial novel ingredients are designed in order to achieve favorable problem-dependent guarantees. • We introduce optimistic mirror descent (OMD) as a unified building block for the algorithm design of dynamic regret minimization in both meta and base levels. We present generic and completely modular analysis for the dynamic regret of OMD, where the negative term is essential for achieving problem-dependent dynamic regret. • We propose the collaborative online ensemble framework.  In addition to employ- ing optimistic online learning to attain adaptivity and meta-base structure to hedge non-stationarity, we incorporate a novel decision-deviation correction term , which fa- cilitates effective collaborations within the two layers and is crucial for achieving the desired problem-dependent bound while requiring only one gradient per iteration. We emphasize that these ingredients are particularly important for achieving gradient- variation dynamic regret, which we will demonstrate to be more fundamental than the small-loss bound.  In particular, our overall solution (especially Sword++) effectively utilizes negative terms and introduces correction terms to ensure successful collaboration within the two-layer online ensemble. The overall framework of collaborative online ensemble is summarized in Section 5, and we believe that the proposed framework has the potential for broader online learning problems. Organization. The rest is structured as follows. Section 2 briefly reviews the related work. In Section 3, we introduce the problem setup and algorithmic framework, where a generic dynamic regret analysis of optimistic mirror descent is provided. Section 4 presents our main results, in which the gradient-variation dynamic regret bounds are established. Section 5 illustrates a generic framework called collaborative online ensemble that is highly useful for attaining problem-dependent dynamic regret. Section 6 provides some additional results. The major proofs are presented in Section 7. Furthermore, Section 8 reports the experiments to empirically support our theoretical findings. Finally, we conclude the paper in Section 9. Some omitted details and proofs are provided in the appendix.
2. Related Work
In this section, we present a brief review of static regret and dynamic regret minimization for online convex optimization.
2.1 Static Regret
Static regret has been extensively studied in online convex optimization. Let T be the time horizon and d be the dimension, there exist online algorithms with static regret bounded by O( √T ), O ( d log T ), and O (log T ) for convex, exponentially concave, and strongly convex functions, respectively (Zinkevich, 2003; Hazan et al., 2007). These results are proved to be minimax optimal (Abernethy et al., 2008).  More results can be found in the seminal books ( Shalev-Shwartz, 2012 ; Hazan, 2016 ) and references therein. In addition to exploiting the convexity of functions, there are studies improving static regret by incorporating smoothness, whose main proposal is to replace the dependence on T by problem-dependent quantities. Such problem-dependent bounds enjoy many benign properties, in particular, they can safeguard the worst-case minimax rate yet can be much tighter in easier problem instances.  There are usually two kinds of such bounds — small-loss bounds (Srebro et al., 2010 ) and gradient-variation bounds ( Chiang et al., 2012 ). Small-loss bounds are first introduced in the context of prediction with expert ad- vice (Littlestone and Warmuth, 1994 ; Freund and Schapire, 1997 ), which replace the de- pendence on T by cumulative loss of the best expert. Later, Srebro et al. ( 2010 ) show that in the online convex optimization setting, OGD with a certain step size scheme can achieve an O( √ 1 + F 7 ) small-loss regret bound when the online convex functions are smooth and non-negative, where F * is the cumulative loss of the best decision in hind- sight, namely, F ≠ = ∑ t =1 f t (x*) with x* chosen as the offline minimizer. The key technical ingredient in the analysis is to exploit the self-bounding properties of smooth functions. Gradient-variation bounds are introduced by Chiang et al. (2012), rooting in the devel- opment of second-order bounds for prediction with expert advice (Cesa-Bianchi et al., 2005) and online convex optimization (Hazan and Kale, 2008).  For convex and smooth functions, Chiang et al. (2012) establish an O( √ 1 + V T ) gradient-variation regret bound, where V τ = ∑ t=2 supx∈ x ||∇ f t (x) − ∇ f t − 1(x)|| 3 measures the cumulative gradient variation. Gradient-variation bounds are particularly favored in slowly changing environments where online functions evolve gradually. In addition, problem-dependent static regret bounds are also studied in the bandit on- line learning setting, including the gradient-variation bounds for two-point bandit convex optimization ( Chiang et al., 2013 ), as well as small-loss bounds for multi-armed bandits ( Al- lenberg et al., 2006; Wei and Luo, 2018; Lee et al., 2020b), linear bandits (Lee et al., 2020b), semi-bandits ( Neu, 2015 ), graph bandits (Lykouris et al., 2018 ; Lee et al., 2020a ), and con- textual bandits ( Allen-Zhu et al., 2018 ; Foster and Krishnamurthy, 2021 ), etc.
2.2  Dynamic Regret
Dynamic regret enforces the player to compete with time-varying comparators and thus is fa- vored in online learning in open and non-stationary environments (Sugiyama and Kawanabe, 2012; Zhao et al., 2021b; Zhou, 2022). The notion of dynamic regret is sometimes referred to as tracking regret or shifting regret in the prediction with expert advice setting (Herbster and Warmuth, 1998, 2001; Bousquet and Warmuth, 2002; Cesa-Bianchi et al., 2012; György and Szepesvári, 2016 ). It is known that in the worst case, a sublinear dynamic regret is not attainable unless imposing certain regularities on the comparator sequence or the function sequence (Besbes et al., 2015 ; Jadbabaie et al., 2015 ). This paper focuses the most common regularity called the path length introduced by Zinkevich (2003), which measures fluctuation of the comparators defined by
Note that we simply focus on the Euclidean norm throughout this paper, and it is straight- forward to extend the notions and results to general primal-dual norms. Other regularities include the squared path length introduced by Zhang et al. ( 2017 ), which is defined as ST = ∑ f=2||u έ –1 − u ℓ|| ž , and the function variation introduced by Besbes et al. (2015) that measures the cumulative variation with respect to the function value and is defined as Vf = Et=2 supxex|ft-1(x) — ft(x)|. There are two kinds of dynamic regret notions in the previous studies. The universal dynamic regret, as defined in ( 2 ), aims to compare with any feasible comparator sequence, while the worst-case dynamic regret defined in ( 3 ) specifies the comparator sequence to be the sequence of minimizers of online functions. In the following, we present the related works respectively.  Notice that we will use notations P T and S T for path length and squared path length of the comparator sequence { u t } t =1,..., T , while adopt the notations P t and S t for that of the sequence { x } t =1,...,r where x } is the minimizer of the online function f t ,
namely, P t = ∑ t =2 ∥ x t −1 − x t ∥ 2 and S t = ∑ t =2 ∥ x t −1 − x t ∥ z The seminal work of Zinkevich (2003) demonstrates that Universal dynamic regret. online gradient descent (OGD) enjoys an O ( √ T (1 + P r )) universal dynamic regret, which holds against any feasible comparator sequence. Nevertheless, the result is far from the Ω( √ T(1 + P r )) lower bound established by Zhang et al. (2018a), who further close the gap by proposing a novel online algorithm that attains an optimal rate of O( √ T(1 + P T )) for convex functions (Zhang et al., 2018a).  Our work further exploits the easiness of the problem instances and achieve problem-dependent regret guarantees, hence better than the minimax rate. Zhao et al. (2021a) study the universal dynamic regret for bandit convex optimization under both one-point and two-point feedback models. The universal dynamic regret is also studied for variants of the standard OCO model such as OCO with mem- ory (Zhao et al., 2022) and OCO with switching cost (Zhang et al., 2021). We note that the aforementioned works and ours are all building on the two-layer meta-base structure. Concurrent to our conference version paper (Zhao et al., 2020b), Cutkosky (2020) pro- poses a novel online algorithm that achieves the same minimax optimal dynamic regret for convex functions as (Zhang et al., 2018a), without relying on meta-base aggregation. Instead, their method employs the combination strategy developed in parameter-free online learning (Cutkosky and Orabona, 2018 ; Cutkosky, 2019 ). We note that it may be possible to modify the algorithm of Cutkosky (2020) to achieve small-loss bounds; however, it is generally challenging to attain gradient-variation bounds, especially under the one-gradient feedback model. More specifically, it is not hard to modify their framework to be compat- ible with optimistic online learning, but one usually needs to exploits additional negative terms to convert the optimistic quantity ‖∇ f t ( × t ) − ∇ f t − 1 ( × t − 1 )‖ 2 to the gradient varia- tion supxex||∇ f t (x) − ∇ f t − 1 (x)|| 3 , in order to eliminate the difference between decisions X t and X t − 1 . Our proposed algorithms are built upon the meta-base two-layer framework, which involves a careful exploitation of negative terms in the regret analysis of both meta and base algorithms, as well as the introduction of additional correction terms. However, as far as we can see, with only one gradient feedback per round, it is challenging for the framework of Cutkosky (2020) to achieve the gradient-variation bound due to the lack of negative terms in the regret analysis. Worst-case dynamic regret. There are many efforts devoted to studying the worst-case dynamic regret. Yang et al. (2016) prove that OGD enjoys an O( √ T(1 + P ¥ )) worst-case dynamic regret for convex functions when the path length P ≠ is known. For strongly con- vex and smooth functions, Mokhtari et al. (2016) show that an O(P年) dynamic regret is achievable, and Zhang et al. (2017) further propose the online multiple gradient descent algorithm with an O (min{ P *, S ≠}) guarantee.  Yang et al. (2016) show that O ( P ≠) rate is attainable for convex and smooth functions, provided that all the minimizers x * 's lie in the interior of the domain X . The above results mainly use the (squared) path length as the non-stationarity measure, which measures the cumulative variation of the compara- tor sequence. In another line of research, researchers use the variation with respect to the function values as the measure. Besbes et al. (2015) show that OGD with a restart- ing strategy attains an O ( T 2 / 3 V f 1 / 3 ) regret for convex functions when the function varia- tion Vf is available, which is improved to O(T1/3Vf2/3) for 1-dim square loss (Baby and Wang, 2019). Chen et al. ( 2019 ) extend the results of Besbes et al. ( 2015 ) to more general function-variation measures capable of capturing local temporal and spatial changes. To take advantage of variations in both comparator sequences and function values, (Zhao and Zhang, 2021) provide an improved analysis for online multiple gradient descent and prove an O (min P *, S *, V † ) worst-case dynamic regret for strongly convex and smooth functions. For convex and smooth functions, they also demonstrate that the simple greedy strategy (i.e., x t+1 = x t ∈ arg min x ∈ x f t (x)) can effectively optimize the worst-case dynamic re- gret (Zhao and Zhang, 2021 , Section 4.2).
3. Problem Setup and Algorithmic Framework
In this section, we first formally state the problem setup, then introduce the foundational algorithmic framework for dynamic regret minimization, and finally list several assumptions that might be used in the theoretical analysis.
3.1  Problem  Setup
Online Convex Optimization (OCO) can be modeled as an iterated game between the player and the environments. At iteration t ∈ [ T ], the player first chooses the decision x t from a convex feasible set X ⊆ R d , then the environments reveal the loss function f t : X → R and the player suffers the loss f t ( x t ) and observes a certain information about the function ft( ). According to the revealed information, the online learning problems are typically classified into full-information online learning and partial-information online learning (or called bandit online learning). In this paper, we focus on the full-information one, which can be further categorized into the following two setups: (i) multi-gradient feedback: the player can access the entire gradient function ∇ f t ( · and thus can evaluate the gradient multiple times; (ii) one-gradient feedback: the player can observe the gradient information ∇ f t ( χ t ) after submitting the decision x t . In Section 4.2 , we develop an online algorithm called Sword with gradient-variation dynamic regret bounds under the multi-gradient feedback model.  In Section 4.3 , we present an improved algorithm called Sword++ that can achieve the same guarantee under the more challenging one-gradient feedback model. The typical performance measure is the static regret, which benchmarks the algorithm with a fixed comparator. To handle non-stationary environments, we focus on the strength- ened measure called dynamic regret , which compares the online algorithm to a sequence of time-varying comparators u 1 , . . , u T ∈ X , as defined in ( 2 ). An upper bound of dynamic regret should be a function of comparators, and typically the bound depends on some reg- ularities that measure the fluctuation of the comparator sequence, such as the path length Pr = ∑ t =2‖ u t − u t −1‖ 2 . Throughout the paper, we focus on the Euclidean norm for simplicity, and it is straightforward to extend our results to general primal-dual norms. In addition to the regret measure, we further consider the gradient query complexity. Note that algorithms designed for the multi-gradient feedback model may query the gra- dients for multiple times at each round. However, most algorithms designed for the static regret minimization only require one gradient per iteration , namely, using ∇ f t ( x t ) for the next update only. Therefore, it is more desirable to achieve the favorable regret guarantees under the one-gradient feedback model. In other words, our aim is to develop first-order methods for dynamic regret minimization that require only one gradient query per iteration.
3.2  Optimistic Mirror Descent
We employ the algorithmic framework of Optimistic Mirror Descent (OMD) (Chiang et al., 2012 ; Rakhlin and Sridharan, 2013 ) as a generic building block for designing algorithms for non-stationary online learning. OMD is a methodology for optimistic online learning. Compared to the standard online learning setup, the player will now additionally receive an optimistic vector M t ∈ R d at each round, which serves as a hint of the future gradient. OMD starts from the initial point X 1 E X and performs the following two-step updates:
which firstly updates by the optimism and then updates by the received gradient. In above, η > 0 is a (potentially) time-varying step size, and D ψ (·, ·) denotes the Bregman divergence associated with the regularizer ψ defined as D ψ (x,y) = ψ (x) − ψ (y) − (∇ψ (y),x − y). We have the following general result regarding dynamic regret of optimistic mirror descent. Theorem 1. Suppose that the regularizer ψ : X ↔ R is 1-strongly convex with respect to the norm ‖ · ‖, and let ‖ · ‖ ∗ be the dual norm of ‖ · ‖. The dynamic regret of Optimistic Mirror Descent whose update rule is specified in (6) is bounded as follows:
which holds for any comparator sequence u 1 , . . . , u T ∈ X . Remark 1. The dynamic regret upper bound in Theorem 1 consists of three terms: (i) the first term ∑ t =1 η ||∇ f ( x t ) − M t || ž is the adaptivity term that measures the devi- ation between gradient and optimism; (ii) the second term ∑ t =1̸= (D ψ (u t , ˆ κ t ) − D ψ (u t , ˆ κ t +1)) reflects the non-stationarity of environments and will be converted to the path length of comparators; (iii) the last negative term − ∑ t − 1 m (D ψ ( δ t + 1 , × t ) + D ψ ( x t , X t )) is crucial and will be Moreover, we emphasize that the above regret guarantee is very general due to the flexibil- ity in choosing the regularizer ψ and comparators { u t } t =1,..., τ . For example, by choosing the negative-entropy regularizer and competing with the best fixed prediction, the result recovers the static regret bound of Optimistic Hedge (Syrgkanis et al., 2015 ); by choosing the Euclidean regularizer and competing with time-varying compactors, it recovers the dy- namic regret bound of Online Gradient Descent (Zinkevich, 2003). The versatility of this optimistic mirror descent framework motivates us to use it as a unified building block for both algorithm design and theoretical analysis.
3.3 Assumptions
In this part, we list several common assumptions that might be used in the theorems. Assumption 1. The norm of the gradients of online functions over the domain X is bounded by G , i.e., ||∇ f t ( x )||2 ≤ G , for all x ∈ X and t ∈ [ T ]. Assumption 2. The domain X ⊆ R d contains the origin 0 , and the diameter of the domain X is at most D , i.e., ||x – x'||2 ≤ D for any x,x' ∈ X . Assumption 3. All the online functions are L-smooth, i.e., ‖∇ ft(x) – ∇ ft(x')‖ ≥ L‖x – x'||2 for any x,x' ∈ R d and t ∈ [T]. Assumption 4. All the online functions are non-negative over R d . We have the following remarks regarding the assumptions. The generic dynamic regret of OMD (Theorem 1) does not require the smoothness assumption (Assumption 3). Never- theless, it is required in attaining the problem-dependent dynamic regret bounds. In fact, even in the static regret analysis, smoothness is demonstrated to be necessary for the first- order methods to achieve gradient-variation bounds (cf. Lemma 9 of Chiang et al. ( 2012 ) and Theorem 1 of Yang et al. (2014)). Therefore, throughout the paper we focus on the problem-dependent dynamic regret of convex and smooth functions. Moreover, note that in Assumption 4 we require the online functions to be non-negative outside the domain X , which is a precondition for establishing the self-bounding property for smooth functions and is commonly used to establish small-loss bounds (Srebro et al., 2010; Zhang et al., 2019; Zhang and Zhou, 2019). Meanwhile, we treat double logarithmic factors in T as a constant, following previous studies ( Adamskiy et al., 2012 ; Luo and Schapire, 2015 ).
4.  Gradient-Variation  Dynamic  Regret
Our paper aims to develop online algorithms that can simultaneously achieve problem- dependent dynamic regret bounds, which scale with two problem-dependent quantities: the gradient-variation term V T and the small-loss term F T , as defined in ( 4 ). As we will demonstrate in the next section, the gradient-variation bound is more fundamental than the small-loss bound. Consequently, we start by focusing on the gradient-variation dynamic regret in this section. In Section 6, we will then present the small-loss bound and the best- of-both-worlds bound as implications of the results obtained in this section.
4.1  A Gentle Start
In the study of static regret, Chiang et al. (2012) propose the online extra-gradient descent (OEGD) algorithm and prove that the algorithm enjoys gradient-variation static regret. Specifically, OEGD starts from ¥1,x1 E X and then updates by
We here consider the algorithm with a fixed step size η > 0 for simplicity, and Π x [ ] denotes the Euclidean projection onto the nearest point in X .  For convex and smooth functions, Chiang et al. ( 2012 ) prove that OEGD can achieve an O(√ 1 + V Γ ) static regret bound, where V T = E T =2 supx ∈ x ∥ ∇ f t (x) − ∇ f t −1(x) ∥ ≥ is the gradient variation. In the following, we further demonstrate that OEGD also enjoys the gradient-variation dynamic regret guarantee. Actually, OEGD can be viewed as a specialization of the opti- mistic mirror descent (6) presented in Section 3.2, by choosing the regularizer ψ(x) =ﾎ||x||2 and the optimism Mt = ∇ ft − 1 ( x t − 1 ) as well as a fixed step size η > 0. Then, the general result of Theorem 1 directly implies the following dynamic regret bound for OEGD, and the proof can be found in Appendix A. Lemma 1. Under Assumptions 1, 2, and 3, by choosing η ≤ OMD with a regularizer ψ(x) = ξ∥×∥ 2 and optimism M t = ∇ ft−1(xt−1) is bounded as
where VT = ∑ t =2 supx∈ x ∥ ∇ f t (×) − ∇ f t −1(×)‖ ≥ is the gradient variation and PT = ∑ t −2‖ u t −1− u t ‖ 2 is the path length. The result holds for any comparator sequence u 1 , . . . , u T ∈ X . Lemma 1 immediately implies a static regret bound. Specifically, by choosing compara- tors as the best decision in hindsight u 1 = . . . = u T ∈ arg min x ∈ x Σ †=1 f t (x) such that the path length P r = 0, we obtain the existing result (Chiang et al., 2012, Theorem 11): where the last step holds by setting the step size η = η* = min{ \ }. Note that the requirement on knowing V T in the optimal tuning can be removed by either doubling trick (Cesa-Bianchi et al., 1997) or self-confident tuning (Auer et al., 2002). However, it is more complicated when competing with a sequence of time-varying com- parators. The dynamic regret bound exhibited in Lemma 1 suggests that it is crucial to tune the step size to balance the non-stationarity (path length PT) and the adaptivity (gradient-variation V T ) in order to achieve a tight dynamic regret bound. Clearly, the op- timal tuning is η* = √( D 2 + 2DP τ )/( 2G 2 + 2V τ ), which unfortunately requires the prior information of P T and V T that are generally unavailable. We emphasize that V T is empir- ically observable in the sense that at round t ∈ [ T ] one can observe its internal estimate Vt = ∑ s=2 supx∈x ||∇ f s (x) − ∇ f s −1 (x)||≥. By contrast, P r = ∑ t=2 ||u t − u t−1 || 2 remains unknown even after all iterations, since the comparators u 1 , . . . , u T can be chosen arbitrar- ily as long as they are feasible in the domain and thus are entirely unknown. Consequently, we may use self-confident tuning to remove the dependence on the unknown gradient vari- ation V T , but the method cannot address the unknown path length P T . In fact, this is the fundamental problem of non-stationary online learning — how to deal with uncertainty due to unknown environmental non-stationarity, captured by path length of comparators P r in the language of dynamic regret minimization. To simultaneously handle the uncertainty arising from adaptivity and non-stationarity, in addition to using optimistic online learning to reuse the historical gradients, we further design an adaptive online ensemble method that can hedge the non-stationarity while ex- tracting the adaptivity. Our approach deploys a two-layer meta-base structure, in which multiple base-learners are maintained simultaneously and a meta-algorithm is used to track the best one. More concretely, we first construct a pool of candidate step sizes to discretize value range of the optimal step size, and then initialize multiple base-learners simultane- ously, denoted by B 1 , . . , B N . Each base-learner B i returns her own prediction x t,i by running the base-algorithm with a particular step size η i from the pool. Finally, the inter- mediate predictions of all the base-learners are combined by a meta-algorithm to produce the final output x t = ∑ i =1 Pt,iXt,i, where p t ∈ ∆ N is the weight distribution. According to the above procedure, we can decompose dynamic regret into two parts because of the two-layer meta-base structure.
where { x t } t =1,..., τ denotes the final output sequence, and { x t,i } t =1,..., τ is the prediction sequence of base-learner B i . Notably, the decomposition holds for any base-learner's index i ∈ [ N ]. The first part is the difference between cumulative loss of the final output sequence and that of the prediction sequence of base-learner Bi, which is introduced by the meta- algorithm and thus named as meta-regret ; the second part is the dynamic regret of base- learner B i and therefore called base-regret. As a result, we need to make the meta-regret and base-regret scaling with V T to achieve the desired gradient-variation dynamic regret. In the following, we present two solutions.  The first solution, developed in our conference paper (Zhao et al., 2020b), is conceptually simpler but requires N = O (log T ) gradient queries at each round, making it suitable only for the multi-gradient feedback model. The second solution is an improved algorithm based on a refined analysis of the problem's structure, which attains the same dynamic regret guarantee with only one gradient per iteration and hence suits for the more challenging one-gradient feedback model. Recall that the definitions of the multi/one-gradient feedback models are presented in Section 3.1.
4.2  Multi-Gradient  Feedback:  Sword
Our approach, Sword, implements a meta-base online ensemble structure, in which multiple base-learners are initiated simultaneously (denoted by B 1 , . . , B N ) and the intermediate predictions of all the base-learners are combined by a meta-algorithm to produce the final output. Below, we describe the specific settings of the base-algorithm and meta-algorithm. For the base-algorithm, we simply employ the OEGD algorithm (Chiang et al., 2012), where the base-learner B i shall update her local decision { x t,i}t =1,...,T by
where η i > 0 is the associated step size from the step size pool H = {η ι,...,η N} and the number of base-learner is chosen as N = O (logT).  Lemma 1 ensures an upper bound of base-regret scaling with the gradient variation, i.e., ∑ t =1 f t ( × t,i) − ∑ t =1 f t ( u t ) ≤ O( η i (1 + V τ ) + P τ /η i ), whenever the step size satisfies η i ≤ 1/(4L). The caveat is that each base-learner requires her own gradient direction for the update, so we need the gradient information of {∇ ft(xt,i)}i=1,...,N at round t ∈ [T]. Notably, the gradient query complexity is N = O (logT) per round instead of one as was desired, consequently, the method devel- oped in this part only suits for the multi-gradient feedback model. We leave the gradient query complexity issue for a moment and will resolve it and design an improved algorithm applicable for the one-gradient feedback model in Section 4.3 . The main difficulty lies in the design and analysis of an appropriate meta-algorithm. In order to be compatible to the gradient-variation base-regret, the meta-algorithm is re- quired to incur a problem-dependent meta-regret of order O( √ V T ln N ). However, the meta-algorithms used in existing studies (van Erven and Koolen, 2016; Zhang et al., 2018a) cannot satisfy the requirements. For example, the vanilla Hedge suffers an O( √ T ln N ) meta-regret, which is problem-independent and thus not suitable for us. To this end, we design a novel variant of Hedge by leveraging the technique of optimistic online learning with carefully designed optimism, specifically for our problem.  Consider the problem of prediction with expert advice. At the beginning of iteration ( t + 1), in addition to the loss vector ℓ t ∈ R N returned by the experts, the player can receive an optimism m t +1 ∈ R N . Optimistic Hedge updates the weight vector pt+1 € Δ N by
Here, ε > 0 is the learning rate of the meta-algorithm and we consider a fixed learning rate for simplicity. 1 The optimism m t+1 ∈ R N can be interpreted as an optimistic guess of the loss of round t + 1, and we thus incorporate it into the cumulative loss for update. It turns out that Optimistic Hedge can be regarded as an instance of OMD with the negative- entropy regularizer, as mentioned in Remark 1. Therefore, the general result of Theorem 1 implies the following static regret bound of Optimistic Hedge, and the proof can be found in Appendix A. Notably, the negative term shown in ( 13 ) will be of great importance in the algorithm design and regret analysis. Lemma 2. The regret of Optimistic Hedge with a fixed learning rate ε > 0 to any expert i ∈ [N] is at most
Let D T = ∑ †=1‖ℓ – m t‖ ∞ measure the deviation between optimism and gradient. With a proper learning rate tuning scheme, Optimistic Hedge enjoys an O( √ DT In N ) meta-regret. The framework of optimistic online learning is very powerful for designing adaptive methods, in that the adaptivity quantity DT = ∑ f = 1 ∥ ℓ t − m t ∥ 2 ∞ is very general and can be specialized flexibly with different configurations of feedback loss L t and optimism m t . To achieve the desired gradient-variation dynamic regret, we need to investigate the online ensemble structure carefully. To this end, we specialize Optimistic Hedge in the following way to make the meta-regret compatible with the desired gradient-variation quantity. • The feedback loss ℓ t ∈ R N is set as the linearized surrogate loss: for t ∈ [ T ] and each
• The optimism m t ∈ R N is set with a careful design: m 1 = 0 and for t ≥ 2 and each i ∈ [ N ],
We will explain the motivation of such designs in Remark 2. Note that this construction of optimism is legitimate as the instrumental variable x t only uses the information of p t –1 as well as the local decisions { Xt,i }i=1,...,N at time t. Thus, the meta-algorithm of Sword updates the weight Pt+1 E RN by
Algorithm 1 summarizes detailed procedures of the meta-algorithm, which in conjunction with the base-algorithm of Algorithm 2 yields the Sword algorithm. Remark 2 (design of optimism). The design of optimism in ( 15 ), particularly the con- struction of the instrumental variable x t , is crucial and is the most challenging part in this method. Our design carefully leverages the structure of two-layer online ensemble methods, specifically, the goal of designing optimism is to approximate the current gradient ∇ f ( x t ) (which is unknown) via the available knowledge till round t. We propose to use ∇ ft-1( å t) as the approximation, and the difference of online functions delivers the gradient-variation term sup x ∈ x ∥ f t ( x ) − f t − 1 ( x ) ∥ ≥ , while the difference between x t and x t can be upper bounded by the decision variation of the meta-algorithm,
which can be eliminated by the negative term in the regret bound of Optimistic Hedge as shown in ( 13 ), providing with a suitable setting for the learning rate of the meta-algorithm. Summarizing, the aforementioned configurations of feedback loss and optimism will convert the adaptive quantity D T to the desired gradient variation V T plus the decision variation of the meta-algorithm, concretely,
where the derivation makes use of the boundedness of the feasible domain, triangle inequal- ity, and the smoothness of online functions. The last term will be canceled by the negative term in the meta-regret, then we obtain the desired gradient-variation regret guarantee.  1 The following theorem shows that the meta-regret is at most O( V (1 + VT) In N ), which is nicely compatible to the attained base-regret. The proof can be found in Section 7.2. Theorem 2. Under Assumptions 1, 2, and 3, by setting the learning rate of the meta- algorithm (16) optimally as ε = min{1/(4D²L), √(In N)/(2D²(G² + VT))}, the meta-regret of Sword (Algorithm 1) is at most
Note that the optimal learning rate tuning of the meta-algorithm requires the knowl- edge of gradient variation V T = ∑ †=2 supx∈ x ||∇ f t (x) − ∇ f t − 1 (x)|| 2 . The undesired demand can be removed by the self-confident tuning method ( Auer et al., 2002 ), which employs a time-varying learning rate scheme for the meta-algorithm's update based on internal esti- mates, roughly, pt+1,i å exp ( − εt(∑ t =1 ℓ s,i + mt+1,i)),Vi ∈ [ N ] with εt = O (1/VI + V i) with an internal estimate Vt = Ls=1 supxex||Vfs(x) - Vfs-1(x)||2. Besides, notice that this V t is actually not easy to calculate due to the computation of instantaneous variation sup x ε x ||∇ f t (x) − ∇ f t −1(x)||3, which is a difference of convex functions programming and is not easy to solve even with the explicit form of functions f t and f t − 1 . Fortunately, we can use an alternative twisted quantity V T = ∑ t =2‖∇ f t ( x t ) − ∇ f t − 1 ( x t − 1 )‖ 3 for the learning rate configuration and also achieve the same regret bound via a refined analysis. Then, it suf- fices to perform the self-confident tuning over V T by monitoring the corresponding internal estimate V t = ∑ s =2‖∇ f s (× s ) − ∇ f s −1(× s −1)‖ 2 , which avoids the burdensome calculations of inner optimization problems and thereby significantly streamlines the computational efforts paid for the adaptive learning rate tuning. So far, the obtained base-regret bound (Lemma 1) and meta-regret bound (Theorem 2) are both adaptive to the gradient variation, and we can simply combine them to achieve the final gradient-variation dynamic regret as stated in Theorem 3, providing with an ap- propriate candidate step size pool. The proof is provided in Section 7.3. Theorem 3. Under Assumptions 1, 2, and 3, set the pool of candidate step sizes H as
where N = [2−1 log 2 (G 2 T /(2D 2 L 2 ))] + 1 is the number of candidate step sizes; and set the learning rate of the meta-algorithm as ε = min{1/(4 D 2 L ), √ (In N)/(2 D 2 ( G 2 + V τ ))}. Then, Sword satisfies that
which holds for any comparators u 1 , . . , u T ∈ X . In above, V T = ∑ t =2 supx ∈ x ∥ ∇ f t (x) − ∇ ft-1(x)||3 is the gradient variation, and PT = Ct-2||ut-1 - ut||2 is the path length. Remark 3. Compared with the existing O ( √ T (1 + P r )) dynamic regret (Zhang et al., 2018a), our result is more adaptive in the sense that it replaces T by the problem-dependent quantity Pr + Vr. Therefore, the bound will be much tighter in easy problems, for example when both V T and P T are o ( T ). Meanwhile, it safeguards the same minimax rate, since both quantities are at most O(T).  Furthermore, because the universal dynamic regret studied in this paper holds against any comparator sequence, it specializes the static regret by setting all comparators as the best fixed decision in hindsight, i.e., u 1 = . . . = u T = x * E arg minxex Lt=1 ft(x).  Under such a circumstance, the path length Pr = Lt=2||ut=1 – ut||2 becomes zero, so the regret bound in Theorem 3 implies an O( √ I + V T ) gradient-variation 1 static regret bound, recovering the result of Chiang et al. ( 2012 ).
4.3  One-Gradient Feedback: Sword++
So far, we have designed an online algorithm (Sword) with the gradient-variation dynamic regret. While it achieves a favorable regret guarantee, one caveat is that Sword runs N = O (log T ) base-learners simultaneously and each base-learner requires her own gra- dient direction for the update. Consequently, the overall algorithm necessitates O (log T ) gradient queries at each iteration, making it time-consuming and only applicable to the multi-gradient feedback model. In contrast, algorithms designed for static regret minimiza- tion typically work well under the more challenging one-gradient feedback model, namely, they only require the gradient information ∇ f t ( x t ) for updates. Given this, it is natural to ask whether it is possible to design online algorithms that can achieve favorable dynamic regret while only using one gradient query per iteration, making them applicable to the one-gradient feedback online learning. We resolve the question affirmatively by designing an algorithm that requires only one gradient query per iteration and provably enjoys the same gradient-variation dynamic re- gret as Sword. The new algorithm, called Sword++, also implements an online ensemble structure. Comparing to Sword presented in Section 4.2, the key novel ingredient is the framework of collaborative online ensemble. We carefully introduce correction terms to the online loss and optimism, forming a biased surrogate loss and a surrogate optimism, which are then fed to the meta-algorithm. By further exploiting the negative terms in the meta and base levels, the overall algorithm ensures effective collaboration within the meta and base two layers, thereby achieving the favorable gradient-variation dynamic regret with only one gradient query per iteration. In the following, we describe the details of Sword++. The algorithm maintains multiple base-learners denoted by B 1 , . . , B N , which are performed with different step sizes and then combined by a meta-algorithm to track the best one. An exponential step size grid is adopted as the schedule, denoted by H = { η i = c · 2 i | i ∈ [ N ]} with N = O (log T ) for some constant c > 0 (usually scaling with poly(1/T)), whose specific setting will be given later. Base-algorithm.   Instead of performing updates over the original loss f t as shown in ( 11 ), all the base-learners of Sword++ update over the linearized surrogate loss gt : X ↔ R defined gt(x) = (∇ ft(xt),x), and moreover, the optimism is chosen as Mt = ∇ 9t − 1(xt− 1,i) for each base-learner B i with i ∈ [ N ]. By definition, we have ∇ gt ( x t,i ) = ∇ ft ( xt ), so each base-learner B i essentially performs the following update at each iteration:
Using above update steps, we no longer need to evaluate the gradient ∇ f t ( x t,i ) over the local decisions for every base-learner, as was done by Sword (see its update rule in ( 11 )). Instead, a single call of ∇ f t ( x t ) is sufficient at each round for the update in Sword++. We note that although the linearized trick has previously been employed in the meta- base structure for achieving the minimax dynamic regret O ( √ T (1 + Pr )) with one gradient per iteration (Zhang et al., 2018a), this modification alone is far from enough to obtain problem-dependent dynamic regret. To see this, we can check the regret of the base-learner updated with the surrogate loss gt(x). A similar argument of Lemma 1 shows that the base-regret over the linearized loss (#) = ∑ t =1 9t(xt,i) - ∑ t =1 9t(ut) satisfies
In the analysis of Sword, because the gradient ∇ f t ( × t,i ) is evaluated on every base-learner's own decision x t,i, the additional positive term (the third one) is 4L 2 Σ f=2||xt,i − xt=1,i||2, which can be cancelled by the negative term − ∑ t = 2 ∥ × t,i − × t − 1,i ∥ 2 /η i whenever the step size is set appropriately. However, when the base-learner updates her decision over the surrogate loss, the additional positive term becomes 4L 2 ‖ x t − x t − 1 ‖ 2 , which cannot be handled by the negative term of any base-learner. Thus, more advanced mechanisms are required to achieve the problem-dependent dynamic regret under the one-gradient query model. To tackle the difficulty, our primary idea is to facilitate collaboration between the meta and base levels. Specifically, we aim to leverage negative terms from both levels to handle the positive term. However, it turns out that the positive term cannot be entirely offset by the combined negative terms from meta and base levels. To address this issue, we introduce correction terms to the feedback loss and optimism in the meta-algorithm. This generates a new negative term that, together with the negative term from the meta level, effectively cancels out the positive term. Nevertheless, another new positive term emerges due to the injected correction, which we ensure can be managed by the negative term from the base level. As a result, the overall undesired positive term is finally addressed. The above forms the main idea of our proposed collaborative online ensemble framework. In the following, we outline the specific setup of the meta-algorithm. We will provide a brief explanation of the design of corrections in Remark 4 and offer a more comprehensive elaboration on the general framework of collaborative online ensemble in Section 5. Meta-algorithm. We still employ Optimistic Hedge (OMD with the negative-entropy regularizer) as the meta-algorithm, but nevertheless require innovative design in the feed- back loss and optimism. Specifically, instead of simply using the linearized surrogate loss l t,i = (∇ f t ( x t ), x t,i ) as the feedback loss like Sword (see the update rule in ( 14 )), we carefully construct the surrogate loss in the following way and send it to the meta-algorithm. • The feedback loss ℓ t ∈ R N is constructed as follows: for each i ∈ [ N ], ℓ 1,i = (∇ fi (x 1 ), x 1 , i ) and for t ≥ 2, it composes the linearized surrogate loss (∇ fi (x t ), x t,i) with a decision-deviation correction term, namely,
• The optimism m t ∈ R N is similarly configured as follows: m 1 = 0 and for t ≥ 2 and i ∈ [ N ], the optimism also admits a decision-deviation correction term, namely,
Both feedback loss and optimism admit an additional correction term λ ‖ x t,i − x t − 1,i ‖ ≥ that measures the stability of the local decisions returned by the base-learner, where λ > 0 is the correction coefficient to be determined later. Overall, the meta-algorithm of Sword++ updates the weight Pt+1 E RN as follows: for any i E [N],
where ε > 0 is (for simplicity) chosen as a fixed learning rate of the meta-algorithm, and the feedback loss ℓ t and optimism m t are defined in ( 20 ) and ( 21 ), respectively. Notably, the meta-algorithm only requires the gradient information of ∇ f ( x t ) at round t and thus is feasible in the one-gradient feedback model. Remark 4 (design of correction term). We emphasize that the correction term λ ∥ x t i − × t –1,ill 2 , appearing in the construction of both feedback loss and optimism, is crucial for the design and is the most challenging part in this method. We briefly explain the moti- vation. As we mentioned earlier, the use of linearized surrogate loss gt (x) will introduce an additional term ∑͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡͡positive term and find that actually it can be further expanded as:
which concludes that
Consequently, it is crucial to exploit negative terms in both meta-regret and base-regret to cancel out the positive term. The second positive term (deviation of meta-algorithm's weights) can be readily canceled by the negative term of meta-regret. However, addressing the first positive term is more intricate, as it is essentially a weighted combination of the base-learners' decision variation. We tackle this positive term by algorithmically adding the decision-variation correction term in the feedback loss and optimism of the meta-algorithm, as well as leveraging the negative term of base-regret.  The underlying intuition is to penalize base-learners with large decision variations, so as to ensure a small enough variation of final decisions. As such, we have facilitated the collaborations between the base and meta levels
— the overall positive term (∑ t = 2 ∥ x t − x t − 1 ∥ 2 ) is jointly cancelled out by the negative term of meta-regret (− ∑ t =2 | Pt − Pt −1 || 2 ) and the one due to the injected corrections (− ∑ t=2 ∑ =1 Pt,;||×t,; − ×t−1,;||ž); and meanwhile, the injected corrections will introduce a base-regret ( − ∑ t = 2 ∥ × t,s − × t − 1,s ∥ ≥ ). Only through such collaborations within the two-layer online ensembles can the proposed Sword++ algorithm attain the desired gradient-variation dynamic regret, utilizing only one gradient per iteration. A more in-depth discussion on this collaborative online ensemble will be presented in Section 5. We summarize the procedures of Sword++ in Algorithm 3 (meta-algorithm) and Algo- rithm 4 (base-algorithm). Though multiple base-learners are performed with different step sizes to tackle the uncertainty of non-stationary environments, Sword++ requires the gradi- ent information of ∇ f t ( x t ) only at round t and then broadcasts it to all the base-learners for local update. Therefore, Sword++ is feasible for the one-gradient feedback model. More- over, the algorithm provably achieves the same gradient-variation dynamic regret as Sword, shown in Theorem 4 , whose proof is presented in Section 7.4 . Theorem 4. Under Assumptions 1, 2, and 3, set the pool of candidate step sizes H as
where N = [2−1 log 2 (G 2 T /(8D 2 L 2 ))] + 1 is the number of candidate step sizes; further set the correction coefficient as λ = 2L and the learning rate of the meta-algorithm as ε = min {1/(8D²L), √(ln N)/(D²(||∇f1(×1)||ž + Vτ))}.  Then, Sword++ satisfies for any comparator sequence u 1 , . . , u T ∈ X . In above, V T = L t =2 supx ∈ x ∥ ∇ f t (x) − ∇ ft−1(×)||≥ is the gradient variation, VT = ∑t−2||∇ ft(×t) − ∇ ft−1(×t−1)||≥ is the variant of
VT, and PT = ∑t−2||ut−1 − ut||2 is the path length. Note that the optimal learning rate tuning of the meta-algorithm requires the knowledge of Vr = ET=2||Vft(xt) - Vft-1(xt-1)||2. Actually, this unpleasant dependence can be removed by performing the self-confident tuning over V T by monitoring the internal estimate Vt = ∑ s=2||Vfs(xs) − ∇ fs−1(xs−1)||2. Importantly, this adaptive learning rate tuning can be realized under the one-gradient feedback model, namely, only ∇ f t ( x t ) available at round t. To avoid clutters, we here stick to a fixed learning rate with dependence on V T and defer an adaptive learning rate version to Appendix B . Up to now, we have shown that it is possible to design online methods to achieve stronger guarantees than static methods (recall that universal dynamic regret can immediately imply static regret) under the challenging one-gradient feedback online learning, and meanwhile suffer no computational overhead in terms of the gradient query complexity.
5. A Generic Framework: Collaborative Online Ensemble
In this section, we formally introduce the proposed collaborative online ensemble framework, a generic algorithmic template designed to achieve (problem-dependent) dynamic regret guarantees. This framework is particularly crucial for attaining gradient-variation bounds. As will be demonstrated shortly, our proposed Sword (in Section 4.2) and Sword++ (in Section 4.3 ) can both be considered as specific instantiations.
5.1 Algorithmic Template
We focus on the standard OCO setup as specified in Section 3.1. At iteration t ∈ [ T ], the player first chooses the decision x t ∈ X , then the environments reveal the loss function f t : X → R . Subsequently, the player suffers the loss f ( x t ) and observes certain gradient information of ∇ f t ( · ) according to the feedback model. The overall algorithmic template implements a meta-base two-layer online ensemble. There are three crucial ingredients in collaborative online ensemble: (i) the surrogate loss, (ii) the surrogate optimism, and (iii) the correction terms. Additionally, the negative terms, hidden in the analysis, play a significant role within the framework. To better present the algorithmic template, we introduce the following notations: •  for the base-algorithm, let gpase( · ) : X → R be the base surrogate loss and h fase( · ) : X → R be the base surrogate optimism; •  for the meta-algorithm, let gpeta(.) : X → R be the meta surrogate loss and hpeta(.) : X → R be the meta surrogate optimism, and let C t ∈ R d be the correction term. The base-algorithm updates the decisions { x t,i} = 1 by Optimistic OGD over the base surrogate loss and optimism, that is,
where η i > 0 is a fixed step size specified by the step size pool H = {η ι, . . ,η N } .  Subse-
quently, the player makes the final decision at this round by x t = ∑ i = 1 The meta-algorithm will then update the weight Pt+1 E Δ N by Optimistic Hedge over the feedback loss ℓ ∈ R d and optimism m t ∈ R d
where ε > 0 is (for simplicity) chosen as a fixed learning rate of the meta-algorithm and the feedback loss ℓ t ∈ R d and optimism m t ∈ R d are defined as
with λ ≥ 0 being the coefficient of the correction terms. Remark 5. The meta-base updates in ( 25 ) and ( 26 ) are quite versatile, as there are many options for constructing the surrogate (meta/base) loss, optimism, and the correction term. We remind that a feasible construction must adhere to the feedback model — in the multi- gradient feedback model, the entire gradient function ∇ f t ( · ) is available, while in the one- gradient feedback model, only the gradient ∇ f t ( x t ) is available to the player. In Section 5.2, we will present several concrete instantiations of the generic algorithmic template, including the proposed Sword and Sword++ in the earlier subsections.
5.2 Instantiations
In this part, we present three instantiations of the generic algorithmic template, including Sword, Sword++, and another important instantiation, which we refer to as Sword.optimism. For clarity, we provide a summary of these instantiations in Table 1. Recovering Sword.   We instantiate the algorithmic template as follows: setting • base surrogate loss as gbase(x) = ft(x) and base optimism as ht ase (x) = ft-1(x); • meta surrogate loss as g n eta (x) = (∇ f t (x t ),x) and meta optimism as h n eta (x) (∇ ft-1( ¯ x t ), x ), as well as correction term as C t = 0. Then, the template updates in the following way: the base-algorithm updates by
and the meta-algorithm updates by
The update procedures precisely recover Sword as presented in Algorithms 1 and 2. Note that in Sword, there is no correction terms, since the gradient-variation dynamic regret bound is attained by guaranteeing gradient-variation meta-regret for the meta-algorithm and gradient-variation base-regret for the base-algorithm, respectively. Recovering Sword++.   We instantiate the algorithmic template as follows: setting • base surrogate loss as g e ase (x) = (∇ f t (x t ),x) and base optimism as h e ase (x) =
Then, the template updates in the following way: the base-algorithm updates by
and the meta-algorithm updates by
The update procedures precisely correspond to Sword++ as presented in Algorithms 3 and 4. We emphasize once more that the algorithmic updates only necessitate querying the gradient ∇ ft(xt) at each round t ∈ [ T ]. Another important instantiation.  We further present another instantiation of the template that can be of independent interest.  The resulting algorithm can achieve an optimistic dynamic regret bound of order O( √ A T (1 + P T )), where A T = ∑ T = 1 ∥ ∇ f t (x t ) − M t ‖ 3 measures the quality of the optimistic vectors { M t } t = 1 .  We instantiate the algorithmic template as follows: setting • base surrogate loss as gbase(x) = {∇ ft(xt),x} and base optimism as htase(x) = {Mt, X};
Then, the template updates in the following way: the base-algorithm updates by
and the meta-algorithm updates by
We refer to the above meta-base updates, ( 28 ) and ( 29 ), as Sword.optimism. Its dynamic regret analysis detailed in Section 5.3. Notice that by setting the optimism as the last-round gradient, specifically, M t = ∇ f t − 1 ( x t − 1 ), Sword.optimism recovers Sword++ exactly.
5.3 Theoretical Guarantee
In this part, we present the dynamic regret analysis for Sword.optimism, which is arguably the most general instantiation of the collaborative online ensemble template. It is straight- forward to extend Theorem 5 for the generic template presented in Section 5.1 , specifically, the meta-base updates in ( 25 ) and ( 26 ). However, the various variables in the generic tem- plate may somewhat obscure the core ideas. Therefore, we choose to showcase the dynamic regret analysis for Sword.optimism, as its analysis effectively captures the essence and its algorithm is also sufficient general (for instance, it can specialize Sword++). Theorem 5. Under Assumptions 1 and 2, set the pool of candidate step sizes H as
where N = [2−1 log₂((8G²Tñ²)/D²)] + 1 is the number of candidate step sizes; further set the learning rate of the meta-algorithm as
Then, decisions returned by Sword.optimism (namely, meta-algorithm as (29) and base- algorithm as (28)) satisfy that for any comparators u 1 , . . . , u T E X ,
In above, A T = ∑ T=1 ∥ ∇ f t ( x t ) − M t ∥ ξ is the adaptivity term measuring the quality of op- timistic gradient vectors {Mt}{=1, and PT = ∑ t=2 || u t −1 − u t ||2 is the path length of com- Et=2 Ci=1 Pt,i || xt,i − xt − 1,i || 2 measures the stability of the decisions returned by the base- algorithm, meta-algorithm, and overall algorithm, respectively. The proof of Theorem 5 is in Section 7.5. Notice that by setting the correction coefficient λ = 0 and setting clipped parameters ī and ē as appropriate constants, Theorem 5 directly implies an O ( √ A T (1 + P T )) dynamic regret for Sword.optimism. As aforementioned, when setting the optimism as Mt = ∇ ft − 1 ( xt − 1 ), Sword.optimism recovers Sword++. Consequently, Theorem 5 serves as a preliminary analysis for Sword++ by substituting M t = ∇ f t − 1 ( x t − 1 ) in the upper bound (32). By further combining the analysis of ( 23 ) in Remark 4 , we can then prove the gradient-variation bound of Theorem 4 , see the detailed argument in Section 7.4.  The key element is to effectively cancel out the additional positive term using negative terms and correction terms jointly, which are strategically introduced due to the collaboration between the meta and base levels.
6. Implication, Significance, and Lower Bound
In this section, we present several additional results, including the implication to small- loss dynamic regret, the implication to the worst-case dynamic regret, the significance of problem-dependent bounds, and a lower bound.
6.1  Implication to Small-Loss Dynamic Regret
In this part, we investigate another problem-dependent quantity — the cumulative loss of comparators defined as FT = Et=1 ft(ut). In the conference version, we propose the Sword algorithm (presented in Section 4.2 ) to achieve the gradient-variation dynamic regret, and then propose a variant to attain the small-loss bound, which employs OGD as the base-algorithm and uses the vanilla Hedge with linearized surrogate loss as the meta-algorithm (i.e., choosing the optimistic vector M t = 0 for both meta- and base-algorithms). In the current paper, we demonstrate that the improved algorithm Sword++ designed in Section 4.3 itself provably achieves the small- loss dynamic regret without any algorithmic modification. In fact, we have the following theorem regarding the small-loss bound of Sword++, whose proof is in Section 7.6. Theorem 6. Set the parameters the same as those in Theorem 4. Under Assumptions 1, 2, 3, and 4, Sword++ satisfies that and hence achieves the best-of-both-worlds quarantee:
The bounds hold for any comparator sequence u 1 , . . . , u T ∈ X . In above, F T = ∑ t =1 f ( u i ) is the cumulative loss of comparators, VT = Et=2 supxEx||Vft(x) − ∇ ft−1(x)||2 is the gra- dient variation, and PT = ∑ t=2||Ut=1 − ut ||2 is the path length. Comparing with Theorem 4 , one more assumption ( Assumption 4 ) is required. This non-negativity assumption is a precondition for establishing the self-bounding property for convex and smooth functions (Srebro et al., 2010), and thus is commonly used in the small- loss analysis of online learning and stochastic optimization (Srebro et al., 2010; Cotter et al., 2011 ; Zhang et al., 2013 , 2019 ; Zhang and Zhou, 2019 ). Remark 6. Our conference version (Zhao et al., 2020b) achieves the best-of-both-worlds bound in a different way, in which we use a heterogeneous model selection method of learning an optimism (Rakhlin and Sridharan, 2013 ) since different optimistic vectors are used for the small-loss and gradient-variation bounds. As such, three algorithms (Sword var, Sword small, and Sword pest ) are designed to achieve the three different bounds (gradient-variation, small- loss, and best-of-both-worlds bounds) respectively. By contrast, Theorem 6 indicates that the Sword++ algorithm can achieve all the three problem-dependent dynamic regret bounds without any modifications, owing to its one-gradient query complexity property. Remark 7. Comparing to the O( √ T(1 + Pr)) minimax rate, Theorem 6 replaces the dependence on T by the problem-dependent quantity Pr + min{ Vr, Fr } and thus achieves dual adaptivity in terms of both gradient variation V T and the small-loss quantity F T . Furthermore, one may wonder whether it is possible to replace T by min{VT,FT} only. This requires a lower bound argument and we only have a partial answer. Specifically, we prove an Ω( P T ) lower bound (see Theorem 8 in Section 6.4 ) by constructing a problem instance via probabilistic methods, in which the small-loss quantity satisfies FT = 0. As a result, an O( √ (1 + F T )(1 + P T ) ) upper bound will contradict with the lower bound, hence eliminating the general possibility of attaining this result. Nevertheless, we fail to provide a similar reasoning for the gradient-variation bound.  Indeed, we have the following conjectures on the tightness of the gradient-variation dynamic regret. For the multi-gradient feedback model, we lean to believe that the O( √ (1 + P τ + V τ )(1 + P τ )) rate is not optimal but the optimal one might be O( √ (1 + V τ )(1 + P τ )).  For the one-gradient feedback model, we conjecture that our obtained rate is already optimal. Note that the latter setup is actually the one we are mostly concerned with, and we will study the optimality in the future.
6.2 Implication to Worst-Case Dynamic Regret
In this part, we present the implication of the universal dynamic regret to the worst-case dynamic regret.  As discussed in Section 2.2, there are two kinds of worst-case dynamic regret bounds, with different regularities: the path-length bound with P* = ∑ t =2 ∥ × t −1 − × t ∥ 2 and the function-variation bound with V f = E t =2 supxex | ft − 1(x) − ft(x)|. The following theorem provides a unified reduction to both of them. Theorem 7. Let A T E R+ be a certain adaptivity term. Suppose there exists an algorithm A that guarantees
for any comparator sequence u1,...uT ∈ X with path length Pr = ∑ t = 2 ∥ ut − ut − 1 ∥ 2, then the algorithm A enjoys the following worst-case dynamic regret bounds:
Theorem 7 demonstrates that an O( √ A τ(1 + P τ )) universal dynamic regret bound can directly imply an O(√Aτ + min{√AτPf, (TAτVf)1/3}) worst-case dynamic regret bound.
A typical choice of this adaptivity term is Aτ = Στ = 1 | ∇ ft(×t) − Mt || 2 that measures quality of optimistic gradient vectors { Mt } f =1. Then, the implication matches the best- known optimistic worst-case dynamic regret bound presented in (Jadbabaie et al., 2015; Zhang et al., 2020b), taking the best of the path-length and function-variation regularities. It is worth noting that Jadbabaie et al. (2015) achieve this result through a novel and sophisticated doubling trick scheme, which will introduce a potentially non-convex inner optimization sup x ∈ x | f t ( x ) − f t − 1 ( x ) | at iteration t ∈ [ T ]. In contrast, our Theorem 7 demonstrates that when the algorithm achieves an O ( √ A T (1 + P T ) universal dynamic regret, it automatically obtains the desired worst-case dynamic regret bounds. Notably, our proposed Sword.optimism algorithm (see the last instantiation in Section 5.2 ) already satisfies this requirement using the collaborative online ensemble framework. The proof of Theorem 7 can be found in Section 7.7.  Given the universal dynamic regret bound (33), one can immediately derive an O ( √ A T + √ A T P ≠ ) worst-case path- length bound by setting u t = x t for any t ∈ [T], but it is less straightforward to obtain the O( √ A T + T 1 / 3 A 1 / 3 ( V f ) 1 / 3 ) function-variation bound. To achieve so, we need to introduce a reference comparator sequence that exhibits piecewise-stationary behavior. The desired function-variation bound is then achievable by optimally tuning the stationary length of the sequence during the analysis. The idea was introduced in Zhang et al. (2020b, Appendix A.2), but an explicit reduction was not provided. We offer a clear presentation of the results. Moreover, in Theorem 7, we focus on the O( √ A T (1 + P T )) universal dynamic regret bound, which incorporates the general adaptivity term A T . Employing a similar proof methodology, we can also convert the gradient-variation/small-loss universal dynamic regret bounds, attained by Sword and Sword++, into the context of worst-case dynamic regret. We omit the details, as the universal dynamic regret has already been established as a more reasonable performance measure for non-stationary online convex optimization.
6.3  Significance of Problem-Dependent Bounds
In this part, we justify the significance of our problem-dependent dynamic regret bounds. We present two concrete problem instances to demonstrate that it is possible to achieve a constant dynamic regret bound instead of the minimax rate O( \ /T(1 + PT)) by exploiting the problem's structure. We consider the quadratic loss function of the form ft(x) = ft(at · x − bt) 2 , where at ≠ 0 and x ∈ X = [−1, 1].  Clearly, the online function f t : R → R is convex and smooth.  Denote by T the time horizon. The coefficients a t and b t will be specified below in each instance. Instance 1 (V T ≪ F T ). Let the time horizon T = 2K + 1 be odd with K > 2. We set the coefficients at = 0.5 −ｷﾗ1 and bt = 1 for all t ∈ [ T ]. We set the comparator u t to be the minimizer of f t , i.e, u t = x t = arg min x ∈ x f t ( x ). Clearly, u t = 1 for t ∈ [ K + 1], and u t = − 1 for t = K + 2, . . . , T . A direct calculation shows
We can observe that the gradient variation V T = O (1) is significantly smaller than the small- loss quantity F T = Θ( T ) (as well as the problem-independent quantity T ) in this instance; and meanwhile, the path length is P T = O (1). Then, the minimax dynamic regret bound is O(√T(1 + Pr)) = O(√T); the small-loss bound is O(√T) + Pr + Fr)(1 + Pr)) = O(√T); and the gradient-variation bound is O( √ (1 + Pr + Vτ)(1 + Pτ )) = O(1). As a result, by exploiting the problem's structure, Sword++ can enjoy a constant dynamic regret in this scenario, significantly improving upon the problem-independent bound of order O ( √ T ). Instance 2 ( FT ≪ VT ). Let the time horizon T = 2K be even. During the first half iterations, ( a t , b t ) is set as (1,1) on odd rounds and (0.5,0.5) on even rounds. During the remaining iterations, ( α t , b t ) is set as (1, −1) on odd rounds and (0.5, −0.5) on even rounds. We set the comparator u t to be the minimizer of f t , i.e, u t = x t = arg min x ∈ x f t ( x ). Clearly, u t = 1 for t ∈ [ K ], and u t = −1 for t = K + 1, . . . , T . A direct calculation shows
We can see that the small-loss quantity FT = 0 is considerably smaller than the gradient variation V T = Θ( T ) (as well as the problem-independent quantity T ) in this scenario; and meanwhile, the path length is PT = O (1). Then, the minimax dynamic regret bound is O( √ T(1 + Pr )) = O( √ T); the gradient-variation bound is O( √ (1 + Pr + V τ)(1 + Pr )) = O( √T ); and the small-loss bound is O( √ (1 + Pr + Fr )(1 + Pr )) = O(1). As a result, by exploiting the problem's structure, Sword++ can enjoy a constant dynamic regret in this scenario, significantly improving upon the problem-independent bound of order O ( √ T ).
6.4  A Lower Bound
We here present a lower bound for dynamic regret of convex and smooth functions. Theorem 8. For any online algorithm A, there always exists a sequence of convex and smooth functions f 1 , . . . , f r and a sequence of comparators u 1 , . . . , u r , such that
The proof of Theorem 8 can be found in Section 7.8. The theorem is proved by the probabilistic method, and in the constructed problem instance, the small-loss quantity is FT = ∑ t=1 ft(ut) = 0. As a result, an O(\/[1 + FT)(1 + PT)) upper bound would contra- dict with the Ω( P r ) lower bound, as one can verify that O( √ (1 + F r )(1 + P r )) = O( √ P r ), which can be smaller than the Ω( PT ) lower bound.  Hence, the lower bound eliminates the general possibility of attaining a better small-loss dynamic regret. Nevertheless, as the gradient variation VT = LT=2 supxex ||∇ ft(x) − ∇ ft−1(x)||2 is larger than 0 in this instance, we cannot rule out the possibility of the O( √ (1 + V T )(1 + P T )) upper bound.
7. Proofs
This section presents the proofs of main results, including Theorem 2 and Theorem 3 of Section 4.2 , as well as Theorem 4 and Theorem 6 of Section 4.3 .
7.1  Proof of Theorem 1
Proof  The instantaneous dynamic regret can be decomposed in the following way:
lemma (Lemma 5) to bound term (a) and appeal to the Bregman proximal inequality (Lemma 4) to bound term (b) and term (c). Below we present the precise arguments. We first investigate term (a). Intuitively, the prediction x t should be close the when the optimistic vector M t is close to the gradient of the next iteration ∇ f t ( x t ). The intuition is formalized in the stability lemma (Chiang et al., 2012 , Propostion 7), as restated in Lemma 5 of Appendix C. Indeed, the stability lemma implies ‖× t − Xt+1‖ ≤ ηt‖∇ ft(xt) − Mt ‖ ⋆ and consequently,
We now analyze term (b) and term (c). By the Bregman proximal inequality (Lemma 4 ) and the OMD update step x t = arg min x ∈ x π 〈 M t, x 〉 + Dφ 〈 x, R t 〉 , we have
Combining the three upper bounds completes the proof.
7.2  Proof of Theorem 2
Proof  Recall the definitions of feedback loss ℓ t ∈ R N in (14) and optimism m t ∈ R N in ( 15 ), which are restated below for ease of reading: ℓ t,i = 〈∇ f t ( x t ), X t,i 〉 and m t,i = (V ft_1 ( x t ), x t,i ) where x t = ∑ i =1 Pt_1,i × t,i . Substituting them into Lemma 2 yields
where the inequality ( 37 ) holds because of the following fact Substituting ( 37 ) into ( 36 ) and exploiting the boundedness of the gradient norm, we get
By setting ε = min{1/(4D 2 L ), √ (In N)/(2D 2 (G 2 + V T)/} , by Lemma 7, we obtain
which completes the proof as f t ( x t ) − f t ( x t,i ) ≤ (∇ f t ( x t ), x t − x t,i ⟩ holds for any t ∈ [ T ] due to the convexity of loss functions.
7.3  Proof of Theorem 3
Proof  As stated in ( 10 ), dynamic regret can be decomposed into two parts:
which holds for any base-learner's index i ∈ [ N ]. We now presents the upper bounds of the meta-regret and base-regret, respectively. Theorem 2 shows that the meta-regret against any base- Upper bound of meta-regret. learner's index i ∈ [ N ] can be bounded by
Upper bound of base-regret. Lemma 1 indicates that for any index i ∈ [ N ], the dynamic regret of the base-learner is at most
where η i ∈ H is the step size associated with the i -th base-learner. Recall in Lemma 1, we require the step size η ; ≤ 1/(4L) to leverage the negative term in the regret analy- sis. Denote by η* = √ ( D 2 + 2DPr )/( G 2 + 2Vr ) the optimal step size without consider- ing the constraint and by η† = min{1/(4L),η*} the clipped one. Notice that we have ηι = √D²/(8G²T), η N = 1/(4L), and ηι ≤ η † ≤ η N , due to path length Pr = Σt = 2||ut − 1) by Assumption 1 and Assumption 2. More importantly, owing to the construction of the step size pool H in ( 18 ), we can assure that there exists an index i* ∈ [ N ] such that η i+ ≤ η † ≤ η i++1 = 2η i+. As a result, we pick i = i* in ( 40 ) and get
In above, ( 42 ) holds because η † is either η * or 1/(4L) and •  when η† = η*, R.H.S of (41) = 2√(G² + 2Vτ)(D² + 2DPτ); • when η† = 1/(4L), we have η* = √(D² + 2DPr)/(G² + 2Vr) ≥  ∑ , which implies that ∑(G² + V T ) ≤ 4L(D² + 2DP T ). Under such a case, R.H.S of (41) = 4L(D² + 2DPT) +式(G² + 2VT) ≤ 8L(D² + 2DPT). Combining the two upper bounds yields ( 42 ). Moreover, ( 43 ) follows from √ α + √ b ≤ 4 √2(a + b), ∀a, b > 0. Upper bound of overall dynamic regret.   Note that the meta-base regret decomposi- tion (38), meta-regret upper bound (39), and base-regret upper bound (40) all hold for any index i ∈ [ N ]. Hence, we can choose the index as i* as specified above and get
where the second inequality is by ( 43 ). Hence, we complete the proof of Theorem 3.
7.4  Proof of Theorem 4
Proof  It is important to note that Sword++ is essentially an instantiation of the unified online ensemble framework presented in Section 5, as specified in Section 5.2. Therefore, for simplicity, we will prove the dynamic regret of Sword++ by building upon the general theorem for the collaborative online ensemble (namely, Theorem 5). Indeed, we can obtain a dynamic regret upper bound of Sword++ by substituting M t = ∇ ft-1(x t-1) into (32) of Theorem 5. And we focus on the adaptivity term AT, which can be further expanded as
where the third inequality is by smoothness of online functions and the last inequality holds by the same argument of deriving ( 23 ) and definitions of V T , Smix and S P . As a result, the first term of ( 32 ) can be further bounded by
where the second inequality is due to the fact that √ a + b ≤ √ α + √ b for any α, b > 0 and the last inequality is a consequence of the AM-GM inequality. Using a similar argument, we can bound the second term of ( 32 ) by
Plugging ( 45 ) and ( 46 ) into ( 32 ), we get the following dynamic regret bound,
We complete the proof by dropping the last three negative terms, which is guaranteed by the parameter configurations λ = 2L, ñ = 1/(8L) and ε = 1/(8D 2L ). We finally mention that in above derivations, the term ln N = O (log log T ) is a double logarithmic factor in T , which is treated as a constant throughout the paper (see the statement at the end of Section 3.3) following previous studies ( Adamskiy et al., 2012 ; Luo and Schapire, 2015 ).² ■
7.5  Proof of Theorem 5
Proof  The proof shares the same spirit with that of Theorem 3, where we decompose the overall dynamic regret into the meta-regret and base-regret. The difference is that we now use a linearized surrogate loss function to substitute the original loss function. Indeed,
Notably, the above meta-base regret decomposition holds for any base-learner's index i E [ N ]. In the following, we upper bound these two terms respectively. Upper bound of meta-regret.   According to the definitions of the feedback loss ℓ t and the optimism m t , see the definition below ( 26 ), we can rewrite the meta-regret as
As the meta-algorithm is an instance of OMD, we can exploit Lemma 2 to get that
where A T = ∑ t =1 || ∇ f t ( x t ) − M t || ≥ is the adaptivity term measuring the quality of op- timistic gradient vectors. The last inequality is true due to the setting of step size ε = min{ε, √(ln N )/( D 2 A T )} and Lemma 7. Combining above two inequalities, we obtain
Upper bound of base-regret.  Since the base-algorithm can be seen as an instance of OMD running over linearized surrogate loss gt(x) = (∇ ft(xt),x) with ψ(x) = f||x||2, we can apply Lemma 1 to obtain the base-regret for any index i ∈ [ N ] as
where the first inequality is a direct consequence of Lemma 1 with a fixed step size. Upper bound of overall dynamic regret.  Combining the meta-regret ( 48 ) and the base-regret (49) with (47), for any i ∈ [ N ], we arrive at the following result:
possible. Note that the optimal step size is η* = √( D 2 + 2DP τ )/A τ , but nevertheless, the step size we should identify is actually η† = {η*, ཀ} due to the threshold in the construction of the step size pool (30). Indeed, it can be verified that the candidate step sizes range from 3G27 to η N = η . We discuss the upper bound in two cases. m = • when η † = √ ( D 2 + 2DP T )/A T , the optimal step size η * provably lies in the range of

7.6  Proof of Theorem 6
Proof  The proof shares the same spirit as that of Theorem 4 , whereas we upper bound the adaptivity term in a different way to achieve the small-loss bound. Specifically, we convert the adaptivity term to the cumulative loss of decisions defined by F ¥ = ∑ f =1 f t ( x t ) .
the parameter configurations λ = 2L, ñ = 1/(8L) and ε = 1/(8D 2L) indicates that the dynamic regret can be bounded by
It remains to convert the dynamic regret bound with respect to the cumulative loss of predictions F X to that of the comparator F T = E t =1 f t ( u t ). According to the definition of Fr and FX , the above inequality implies that
where the first inequality is due to the fact that √ α + √ b ≤ √ 2(α + b ) holds for any α, b ≥ 0, and the second inequality comes from Lemma 9. We have completed the proof.
7.7  Proof of Theorem 7
Proof  By choosing u t = x t and the universal dynamic regret bound of D-Regret T (u 1 , . . , u T ) ≤ √AT(D + PT), we can directly obtain
which is the path-length worst-case dynamic regret bound. In the following, we focus on the function-variation type bound. This is achieved by following the arguments of Zhang et al. ( 2020b ), we introduce a virtual piece-wise stationary comparator sequence that only changes every ∆ ∈ [1, T ] iterations. Specifically, denoting by I m = [(m − 1)Δ + 1,min{ mΔ,T}] ⊆ [1,T] the m -th interval, we define the comparator over the interval I m as x žm = arg min x ∈ x Σ t ∈ I m ft (x). There are in total M = [T/Δ] intervals. Then, we can decompose the worst-case dynamic regret as
For term (a), since the piece-wise stationary comparator sequence only change M – 1 times over the time horizon, its path length is at most D ( M – 1). As a consequence, the universal dynamic regret guarantee ( 33 ) of the algorithm ensures
Moreover, the argument in Besbes et al. (2015, Proposition 2) shows that
Combining the upper bounds for term (a) and term (b), we obtain
The optimal choice of the interval length is ∆ ∗ := ( DTA τ ) 1/3 ( V ž ) −2/3, which will lead to an O(√AT + AžT ) (Vf) ) worst-case dynamic regret. However, a caveat is that the interval length △ ∈ [ T ] should be a positive integer. We thus use the clipped version △† := min {[△*],T}. We show that the desired bound (34) is achievable with △† by considering the following three cases. • Case 1 (1 ≤ Δ* ≤ T): in such a case, Δ† = [Δ*] and we have Δ* ≤ Δ† ≤ 2Δ*. Then, the dynamic regret is bounded by
We complete the proof for case 1 by combining the result with the path-length worst- case dynamic regret bound in ( 52 ).
We complete the proof for case 2 by combining the result with the path-length worst- case dynamic regret bound in (52). • Case 3 (Δ* ≤ 1): in such a case, Δ t = 1 and √ D A T T ≤ V t . Since P t ≤ D T , we have /ATP4 < √DATT < D$ A$T$(Vf)$, indicating that the path-length bound (52) is tighter than the desired result ( 34 ), which completes the proof for case 3. Overall, the proof is completed by combining the above three cases.
7.8  Proof of Theorem 8
Proof  The theorem is proved by the probabilistic method, following the proof of Zhang et al. (2017, Theorem 5). For iterations t = 1, . . . , T , we randomly sample a convex and smooth function ft : R d → R from the distribution P . More specifically, we construct the function as ft(x) = ||x – σεt||2, where σ > 0 and E t ∈ R d is a random vector with components sampled independently from the Rademacher distribution, i.e., ε t (i) = 1 or −1 with equal probability of 50%. We further set the com- parator u t = x t ∈ arg min x ∈ x f t (x) = σ ε t . Denote by x t the decision returned by any deterministic online algorithm A. Then the expected dynamic regret is defined as
where the last inequality holds since σ ( x t, ε t ) ≥ 0 and E [ σ 2 ||ε t || ≥ ] ≥ dσ 2 for any t ≥ 1. On the other hand, we have
where δ t (i) = E t (i) − E t −1 (i). By choosing σ ≥ 2 ⁄ √ d, we can ensure that E [ D-Regret τ ] ≥ E[PT(u1, . . . , uT)].  We note that the choice of σ might lead to a violation of the assumption of domain boundedness, which can be easily fixed by the rescaling.  So the probabilistic argu- ment implies that for any algorithm A there exists a sequence of online functions f 1 , . . . , f T such that D-Regret T ≥ PT ( u 1 , . . , u T ), which concludes the proof.
8. Experiments
In this section, we provide empirical studies to validate the effectiveness of our proposed algorithm and support the theoretical findings. We simulate the online prediction environments as follows. The player sequen- Settings. tially receives the feature of an instance and is then required to make the prediction. We focus on the problem of online regression, where at each round an instance ( x t, y t ) is received with X t ∈ X ⊂ R d being the feature and y t ∈ Y ⊂ R being the corresponding label. At each round, the player first receives the feature x t and is required to make the prediction by ˆYt = x i W t based on the learned model w t ∈ W ⊂ R d ; then, the ground-truth label y t ∈ R is revealed and the player suffers a loss of ℓ( yt, ft ), where in the simulation we choose the Huber loss defined as
As a result, the online function can be regarded as a composition of the loss function and the data item, that is, f t : W → R with f t ( w ) = l ( yt , f t ). It can be verified that the functions are convex, and satisfy the condition of non-negativity and smoothness. The player will receive the feedback of the online function and subsequently update her model. Datasets. We compare the performance on both synthetic and real-world datasets. First, the synthetic data are generated as follows: at each round, the feature x t ∈ R d is randomly generated from a ball with a radius of Γ, i.e., B = {x ∈ R d | ||×||2 ≤ Γ}; the associated label is set as y t = x T w t + ε t , where ε t is the random noise drawn from [0, 0.1] and w t ∈ R d is the underlying model. The underlying model w * is randomly sampled from a ball with a radius of D/2 (recall that D is the diameter of the feasible domain throughout the paper), and it is forced to be stationary within a stage and will be changed every S rounds to simulate the non-stationary environments with abrupt changes. In our simulation, we set Γ = 1, D = 2, d = 5, T = 5000, S = 1000, and δ = 2. Next, we employ a real-world dataset called Sulfur recovery unit (SRU) (Zhao et al., 2021b ), which is a regression dataset with slowly evolving distribution changes. There are in total 10,081 data samples representing the records of gas diffusion, where the feature consists of five different chemical and physical indexes and the label is the concentration of SO 2 . We compare the proposed algorithm Sword++ with the following three Contenders. contenders:  (i) OGD ( Zinkevich, 2003 ), online gradient descent, which is an OCO algorithm designed for optimizing static regret; (ii) Ader (Zhang et al., 2018a), an OCO algorithm designed for optimizing dynamic regret yet with only problem-independent guarantee; (iii) Sword, the algorithm proposed in Section 4.2 , which achieves problem-dependent dynamic regret guarantees yet requires multiple gradients per iteration. We repeat the experiments for five times and report the mean and the standard Results. deviation in Figure 1 and Figure 2. In Figure 1, we examine the performance in terms of cumulative loss. First, we can observe that OGD incurs a large cumulative loss over the horizon and is not able to effectively learn from the non-stationary environments. By contrast, both Ader and our approach (Sword, Sword++) achieve a satisfactory performance in present of distribution changes. Moreover, Sword and Sword++ exploit the adaptivity of the problem instance and thus achieve an encouraging empirical behavior than Ader, which demonstrates the empirical effectiveness. Figure 2 reports the running time comparison, where the y-axis uses a logarithmic scale for a better presentation.  We can observe that OGD is the most computationally efficient; besides, Ader and Sword++ are also comparable. By contrast, Sword requires significantly more running time. The result accords to our theory well, in that the gradient computation is the most time-consuming in our simulations. Theoretically, both Sword++ and Ader (with linearized surrogate loss) only require one gradient query per iteration, which shares the same gradient query complexity with OGD. On the contrary, Sword needs to query N = O (logT) gradients at each round and is thus much more computational inefficient.  To summarize, the empirical results validate the advantage of Sword++, which behaves well and is also computationally lightweight.
9. Conclusion
In this paper, we exploit the easiness of problem instances to enhance the universal dynamic regret. We propose two novel online ensemble algorithms, Sword and Sword++, for convex and smooth online learning. Both algorithms achieve a best-of-both-worlds dynamic regret of order O( \ /(1 + Pr + min{Vr, Fr})(1 + Pr}), where Vr measures the gradient variation and F T is the cumulative loss of comparators.  These quantities are at most O(T) yet can be very small when the problem is easy, hence reflecting the difficulty of problem in- stance. Consequently, our bounds can outperform the O( √ T (1 + P T )) minimax dynamic regret (Zhang et al., 2018a) by exploiting smoothness.  Our results are accomplished by several crucial technical ingredients. We adopt optimistic mirror descent as a unified build- ing block for both base and meta algorithms, and carefully exploit the negative terms in the regret analysis. Moreover, in the design of Sword++, we introduce the framework of collaborative online ensemble , which emphasizes the construction of surrogate loss in the algorithm design and devises a decision-deviation correction term in conjunction with the linearized loss to facilitate collaboration within the meta-base two layers. By incorporating these elements, we can finally achieve favorable problem-dependent dynamic regret guaran- tees under the one-gradient feedback model. All of attained dynamic regret bounds are universal in the sense that they hold against any feasible comparator sequence, making the algorithms adaptive to non-stationary envi- ronments. An important future work is to investigate the optimality of the our attained problem-dependent dynamic regret bounds. We now only have very preliminary understand- ings for small-loss dynamic regret (see the lower bound in Theorem 8 and also discussions in Remark 7 ) and some conjectures regarding the gradient-variation bound (see Remark 7 ), but a complete understanding requires refined lower bounds that take problem-dependent quantities into account. Moreover, it is important to investigate the possibility of exploit- ing other function curvatures for the analysis of universal dynamic regret, such as strong convexity, exp-concavity, and self-concordance.
Acknowledgment
This research was supported by NSFC (61921006, 61976112) and the Collaborative Innova- tion Center of Novel Software Technology and Industrialization. The authors would like to thank Mengxiao Zhang and Ashok Cutkosky for helpful discussions. We are also grateful for anonymous reviewers for their valuable comments. J. D. Abernethy, P. L. Bartlett, A. Rakhlin, and A. Tewari. Optimal stragies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory (COLT) , pages 415–424, 2008. D. Adamskiy, W. M. Koolen, A. V. Chernov, and V. Vovk.  A closer look at adaptive regret. In Proceedings of the 23rd International Conference on Algorithmic Learning Theory (ALT), pages 290–304, 2012. Z. Allen-Zhu, S. Bubeck, and Y. Li.  Make the minority great again:  First-order regret bound for contextual bandits. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 186–194, 2018. C. Allenberg, P. Auer, L. Györfi, and G. Ottucsák. Hannan consistency in on-line learn- ing in case of unbounded losses under partial monitoring. In Proceedings of the 17th International Conference on Algorithmic Learning Theory (ALT) , pages 229–243, 2006. P. Auer, N. Cesa-Bianchi, and C. Gentile.  Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences , 64(1):48–75, 2002. D. Baby and Y.-X. Wang.  Online forecasting of total-variation-bounded sequences.  In Advances in Neural Information Processing Systems 32 (NeurIPS) , pages 11071–11081, 2019. D. Baby and Y.-X. Wang.  Optimal dynamic regret in exp-concave online learning.  In Proceedings of the 34th Conference on Learning Theory (COLT), pages 359–409, 2021. O. Besbes, Y. Gur, and A. J. Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015. O. Bousquet and M. K. Warmuth. Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3:363–396, 2002. N. Cesa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold, R. E. Schapire, and M. K. Warmuth. How to use expert advice. Journal of the ACM , 44(3):427–485, 1997. N. Cesa-Bianchi, Y. Mansour, and G. Stoltz. Improved second-order bounds for prediction with expert advice. In Proceedings of the 18th Annual Conference on Learning Theory (COLT), pages 217–232, 2005. N. Cesa-Bianchi, P. Gaillard, G. Lugosi, and G. Stoltz. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems 25 (NIPS), pages 989–997, 2012. G. Chen and M. Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538–543, 1993. X. Chen, Y. Wang, and Y.-X. Wang. Non-stationary stochastic optimization under L p,g- variation measures. Operations Research , 67(6):1752–1765, 2019. C. Chiang, C. Lee, and C. Lu. Beating bandits in gradually evolving worlds. In Proceedings of the 26th Annual Conference on Learning Theory (COLT), pages 210–227, 2013. C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu. Online optimization with gradual variations. In Proceedings of the 25th Conference On Learning Theory (COLT), pages 6.1–6.20, 2012. A. Cotter, O. Shamir, N. Srebro, and K. Sridharan.  Better mini-batch algorithms via accelerated gradient methods. In Advances in Neural Information Processing Systems 24 (NIPS), pages 1647–1655, 2011. A. Cutkosky. Combining online learning guarantees. In Proceedings of the 32rd Conference on Learning Theory (COLT) , pages 895–913, 2019. A. Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In Proceed- ings of the 37th International Conference on Machine Learning (ICML) , pages 2250–2259, 2020. A. Cutkosky and F. Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Proceedings of the 31st Conference on Learning Theory (COLT), pages 1493–1529, 2018. H. Fang, N. Harvey, V. S. Portella, and M. P. Friedlander. Online mirror descent and dual averaging: keeping pace in the dynamic case. In Proceedings of the 37th International Conference on Machine Learning (ICML) , pages 3008–3017, 2020. D. J. Foster and A. Krishnamurthy. Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 18907–18919, 2021. Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of Computer and System Sciences , 55(1):119–139, 1997. A. György and C. Szepesvári. Shifting regret, mirror descent, and matrices. In Proceedings of the 33nd International Conference on Machine Learning (ICML), pages 2943–2951, 2016. E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Opti- mization, 2(3-4):157–325, 2016. E. Hazan and S. Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 57–68, 2008. E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex opti- mization.  Machine Learning, 69(2-3):169–192, 2007. M. Herbster and M. K. Warmuth. Tracking the best expert.  Machine Learning, 32(2): 151–178, 1998. M. Herbster and M. K. Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, 1:281–309, 2001. A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online optimization : Com- peting with dynamic comparators. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS) , pages 398–406, 2015. C. Lee, H. Luo, and M. Zhang. A closer look at small-loss bounds for bandits with graph feedback.  In  Proceedings of the 33th Conference on Learning Theory (COLT), pages 2516–2564, 2020a. C.-W. Lee, H. Luo, C.-Y. Wei, and M. Zhang.  Bias no more:  high-probability data- dependent regret bounds for adversarial bandits and MDPs.  In Advances in Neural Information Processing Systems 33 (NeurIPS) , pages 15522–15533, 2020b. N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation , 108(2):212–261, 1994. H. Luo and R. E. Schapire.  Achieving all with no parameters:  AdaNormalHedge. In Proceedings of the 28th Annual Conference Computational Learning Theory (COLT), pages 1286–1304, 2015. T. Lykouris, K. Sridharan, and É. Tardos. Small-loss bounds for online learning with partial information. In Proceedings of the 31st Conference on Learning Theory (COLT) , pages 979–986, 2018. A. Mokhtari, S. Shahrampour, A. Jadbabaie, and A. Ribeiro. Online optimization in dy- namic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control (CDC) , pages 7195–7201, 2016. G. Neu.  First-order regret bounds for combinatorial semi-bandits.  In  Proceedings of the 28th Conference on Learning Theory (COLT) , pages 1360–1375, 2015. F. Orabona. A modern introduction to online learning. ArXiv preprint , arXiv: 1912.13213, 2019. R. Pogodin and T. Lattimore. On first-order bounds, variance and gap-dependent bounds for adversarial bandits. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI), pages 894–904, 2019. A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference On Learning Theory (COLT) , pages 993–1019, 2013. S. Shalev-Shwartz.  Online Learning:  Theory, Algorithms and Applications.  PhD  Thesis, 2007. S. Shalev-Shwartz.  Online Learning and Online Convex Optimization.  Foundations and Trends in Machine Learning , 4(2):107–194, 2012. N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems 23 (NIPS) , pages 2199–2207, 2010. M. Sugiyama and M. Kawanabe. Machine Learning in Non-stationary Environments: In- troduction to Covariate Shift Adaptation. The MIT Press, 2012. V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28 (NIPS), pages 2989–2997, 2015. T. van Erven and W. M. Koolen. Metagrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29 (NIPS) , pages 366–3674, 2016. C.-Y. Wei and H. Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the 31st Conference on Learning Theory (COLT) , pages 1263–1291, 2018. C.-Y. Wei, Y.-T. Hong, and C.-J. Lu. Tracking the best expert in non-stationary stochastic environments. In Advances in Neural Information Processing Systems 29 (NIPS) , pages 3972–3980, 2016. T. Yang, M. Mahdavi, R. Jin, and S. Zhu. Regret bounded by gradual variation for online convex optimization. Machine Learning, 95(2):183–223, 2014. T. Yang, L. Zhang, R. Jin, and J. Yi. Tracking slowly moving clairvoyant: Optimal dy- namic regret of online learning with true and noisy gradient. In Proceedings of the 33rd International Conference on Machine Learning (ICML) , pages 449–457, 2016. J. Yuan and A. G. Lamperski. Trading-off static and dynamic regret in online least- squares and beyond. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 6712–6719, 2020. L. Zhang and Z.-H. Zhou. Stochastic approximation of smooth and strongly convex func- tions: Beyond the O (1/T) convergence rate. In Proceedings of the 32nd Conference on Learning Theory (COLT), pages 3160–3179, 2019. L. Zhang, T. Yang, R. Jin, and X. He. O (logT) projections for stochastic optimization of smooth and strongly convex functions. In Proceedings of the 30th International Confer- ence on Machine Learning (ICML) , volume 28, pages 1121–1129, 2013. L. Zhang, T. Yang, J. Yi, R. Jin, and Z.-H. Zhou. Improved dynamic regret for non- degenerate functions. In Advances in Neural Information Processing Systems 30 (NIPS), pages 732–741, 2017. L. Zhang, S. Lu, and Z.-H. Zhou.  Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31 (NeurIPS) , pages 1330–1340, 2018a. L. Zhang, T. Yang, R. Jin, and Z.-H. Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning (ICML) , pages 5877–5886, 2018b. L. Zhang, T.-Y. Liu, and Z.-H. Zhou. Adaptive regret of convex and smooth functions. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 7414–7423, 2019. L. Zhang, S. Lu, and T. Yang. Minimizing dynamic regret and adaptive regret simultane- ously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS) , pages 309–319, 2020a. L. Zhang, W. Jiang, S. Lu, and T. Yang. Revisiting smoothed online learning. In Advances in Neural Information Processing Systems 34 (NeurIPS) , pages 13599–13612, 2021. Y.-J. Zhang, P. Zhao, and Z.-H. Zhou.  A simple online algorithm for competing with dynamic comparators. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), pages 390–399, 2020b. P. Zhao. Online Ensemble Theories and Methods for Robust Online Learning. PhD thesis, Nanjing University, Nanjing, China, 2021. Advisor: Zhi-Hua Zhou. P. Zhao and L. Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Proceedings of the 3rd Conference on Learning for Dynamics and Control (L4DC), pages 48–59, 2021. P. Zhao, L. Zhang, Y. Jiang, and Z.-H. Zhou. A simple approach for non-stationary linear bandits. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS) , pages 746–755, 2020a. P. Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou.  Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS) , pages 12510–12520, 2020b. P. Zhao, G. Wang, L. Zhang, and Z.-H. Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research , 22(125):1 – 45, 2021a. P. Zhao, X. Wang, S. Xie, L. Guo, and Z.-H. Zhou. Distribution-free one-pass learning. IEEE Transaction on Knowledge and Data Engineering , 33:951–963, 2021b. P. Zhao, Y.-X. Wang, and Z.-H. Zhou. Non-stationary online learning with memory and non-stochastic control. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS) , pages 2101–2133, 2022. Z.-H. Zhou. Ensemble Methods:  Foundations and Algorithms. Chapman & Hall/CRC Press, 2012. Z.-H. Zhou. Open-environment machine learning. National Science Review, 9(8), 07 2022. M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML) , pages 928–936, 2003. As discussed in Section 3.2, the versatility of optimistic mirror descent (OMD) makes it very general to derive many existing results in a unified view. In this section, we provide two specific implications of the general dynamic regret results presented in Theorem 1 , which essentially serves as the proofs of Lemma 1 (dynamic regret of OEGD) and Lemma 2 (static regret of Optimistic Hedge). First, by choosing the regularizer as ψ(x) = ξ ‖ x‖ ε , we obtain the dynamic regret bound for the OEGD algorithm as stated in Lemma 1. Proof [of Lemma 1] We first show a general result for the OMD algorithm with arbitrary M t ∈ R d and the regularizer ψ(x) =ﾎ||x|| 2 , and then prove Lemma 1 by choosing M t = ∇ ft-1(xt-1). It is easy to verify that the regularizer ψ(x) = ξ ‖ x‖ 2 is 1-strongly convex with respect to the Euclidean norm || · ||2 and the induced Bregman divergence is D ψ (x,y) = ξ ||x − γ ||2 As a consequence, Theorem 1 gives
Notice that the second term can be upper bounded as follows.
where we use the triangle inequality and the boundedness of the feasible domain.  We further
in which the last inequality holds due to the fact a 2 + b 2 ≥ (α + b ) 2 /2. Hence, combining all the three inequalities, we get the following result for general OMD with ψ(x) = φ || x || 2 Furthermore, when choosing the optimism as the last-round gradient as M t = ∇ ft-1( ×t-1), the adaptivity term η ∑ t =1 || ∇ f t ( x t ) − M t || ≥ can be upper bounded in the following way:
result back yields where the setting of step size η ≤ 1/(4L) ensures the last term in the first inequality be non-positive. We hence complete the proof. Next, by choosing the regularizer as ψ( p ) = ∑ i = 1 P i ln P i , the loss function as f t ( P t ) = ⟨ p t , ℓ t ⟩ and optimism M t = m t , OMD recovers Optimistic Hedge (Rakhlin and Sridharan, 2013). Here, with a slight abuse of notations, we now use p ∈ Δ N to denote the variable. Theorem 1 implies the static regret for Optimistic Hedge algorithm by choosing compara- tors as a fixed one in the simplex. Proof [of Lemma 2] When choosing the negative-entropy regularizer ψ( p ) = ∑ i =1 p i ln p i , it is not hard to verify that ψ is 1-strongly convex with respect to ‖ · ‖ 1 and the induced Bregman divergence is D ψ ( p, q ) = ∑ i =1 p i ln( p i /q i ). As a result, by choosing comparators as ẹTheorem 1 gives Consider the second term on the right hand side. The telescoping structure of the second term implies
Moreover, by Pinsker's inequality, we have D φ (p,q) = KL(p,q) = ∑ i =1 p i ln(p i /q i ) ≥ ž‖p – q‖ ? . Therefore, the last term can be lower bounded as
where the last inequality is got by regrouping the sum and applying triangle inequality like (53). Combining all above these, we achieve
which ends the proof. Note that the negative term in the regret bound (54) is very essential, which is quite useful in a variety of problems requiring adaptive bounds. Our analysis is based on the unified view of OMD (Theorem 1), and is simpler and easier to understand than the original proof due to Syrgkanis et al. (2015), who interpret the update from the lens of FTRL (Follow-the-Regularized-Leader) and prove the result based on mathematical induction. In the main text, our proposed algorithms (Sword and Sword++) both employ a fixed learning rate for the meta-algorithm, which greatly simplifies the presentation and re- gret analysis. The learning rate configurations require the knowledge of gradient variation VT = ∑ t=2 supxex ||∇ f t (x) − ∇ f t=1 (x)|| ≥ (for Sword) or its variant ∇ T = ∑ t=2 ||∇ f t (x t) − ∇ ft-1(xt-1)|| 2 (for Sword++). In this section, we present an adaptive version using the self-confident learning rate tun- ing (Auer et al., 2002) such that the meta-algorithm does not require such information ahead of time. 3  Before presenting the details, we first extend the collaborative online ensemble framework in Section 5 to an adaptive version.  We then use it to prove the gradient-variation and small-loss dynamic regret bounds for the adaptive version of Sword++. In this part, we provide the adaptive learning rate version of the unified framework presented in Section 5. Comparing with the fixed learning rate version, the only difference is that we run the optimistic Hedge with a time-varying learning rate for the meta-algorithm,
where the loss vector ℓ t and m t share the same configurations as ( 26 ). For any i -th base- algorithm, we use the same update rule as the fixed learning rate version
Then, we can generate the prediction for iteration t by x t = ∑ i =1 pt,ix t,i and have the following guarantee. Theorem 9. Under the same assumptions and parameter configurations as Theorem 5 and setting the learning rate of the meta-algorithm as
Then, decisions specified by (55) and (56) satisfy that for any comparators u 1 , .
In above, Ã = max t ∈ [ τ ] ||∇ f i ( x ) − M t || 2, A τ = ∑ t − 1 ||∇ f t ( x t ) − M t || 2 is the adaptivity term measuring the quality of optimistic gradient vectors { M t } ξ =1, and P τ = C t =2 || u t −1 − is the path length of comparators. The terms Sx,i = ∑ t − 2 ∥ xt,i − xt − 1,i ∥ 2, Sp = ∑ t − 2 ∥ pt − returned by the base-algorithm, meta-algorithm, and overall algorithm, respectively. We remark that, in the fixed learning rate case, one can show that the Optimistic Hedge (22) is identical to the optimistic OMD with the negative-entropy regularizer. How- ever, the adaptive learning rate version ( 55 ) can only be interpreted as a follow the regular- ized leader (FTRL) algorithm. Thus, it is hard to directly apply Theorem 1 to obtain the meta-regret. We choose a FTRL-type meta-algorithm instead of an OMD-type algorithm, in that OMD with time-varying learning rates would suffer linear regret in the worst case when using the negative-entropy regularizer. Although one can fix this issue with the sta- bilization technique (Fang et al., 2020), we just use the FTRL-type update for simplicity. We present the proof of Theorem 9 as follows. Proof [of Theorem 9] The proof is almost identical to that of Theorem 5.  The main difference is that we use a counterpart of Lemma 2 to bound the meta-regret for the adaptive learning rate version (55).  Specifically, since (55) is identical to the Optimistic FTRL algorithm Pt+1 = arg min PEA (P, C t =1 ℓ s + mt+1) + ψ t+1(p) with the regularizer ψ t+1(p) = ε, (∑ n =1 p i ln p i + ln N ), 4 a direct application of Orabona (2019, Theorem 7.35) shows that Lemma 3 (Theorem 7.35 of Orabona (2019)). The regret of Optimistic Hedge with a time- varying learning rate ε t > 0 (see the update specified in (55)) to any expert i ∈ [ N ] satisfies
||ℓ t − mt||∞||Pt − Pt+1||1 and the fact that ab ≤ εt−1α 2 + − b 2 – holds for any α, b, εt –1 > 0. The third inequality is by definitions of ℓ t and m t . The last inequality is a consequence of the inequality ln N/ετ ≤ ln N/ε + √ D 2 ln N Σ t = 1 ∥ ∇ f t (x) − M t ∥ 3 by learning rate config- uration ( 60 ) and Lemma 11 , which provides a clipped version of the self-confident tuning. Then, by the same argument to obtain the meta-regret in the proof of Theorem 5, see (48), we have
in the proof of Theorem 5, we can identify an optimal base-algorithm indexed by i* ∈ [ N ], whose base-regret is bounded by
Finally, combining the meta-regret and the base-regret of the i*-th base-learner we have
where S x,i = ∑ T=2 ∥ x t,i − x t−1,i ∥ 2, S p = ∑ t=2 ∥ Pt − Pt−1 ∥ 2 and S mix = ∑ t=2 ∑ i=1 Pt,i ∥ x t,i Xt-1,ill2 measures the stability of the decisions. We show that the adaptive learning rate version of the framework (55) and (56) with M t = ∇ f t − 1 ( x t − 1 ) for t ≥ 2 ( M 1 = 0 ) achieves the same problem-dependent dynamic regret bound as that in Theorem 6. Theorem 10. Under the same assumptions and parameter configurations as Theorem 6 and set the learning rate of the meta-algorithm as
with Mt = ∇ ft-1(xt-1) for t ≥ 2 (M1 = 0). Then, decisions specified by (55) and (56) satisfy that for any comparators u 1 , . . . , u T ∈ X ,
Under the parameter configurations λ = 2L, ή = 1/(8L) and ε = 1/(8D²L), the Proof dynamic regret bound of the unified algorithm with the adaptive learning rate (c.f. Theo- rem 9 ) is almost the same as that of the fixed learning rate (c.f. Theorem 5 ) with difference up to constant factors. Thus, the same arguments in the proof of Theorem 4 and Theorem 6 lead to the best-of-both-worlds bound. This section collects several useful technical lemmas frequently used in the proofs.  The first one is the Bregman proximal inequality, which is crucial in the analysis of first-order optimization methods based on Bregman divergence. Lemma 4 (Bregman proximal inequality (Chen and Teboulle, 1993, Lemma 3.2)). Let X be a convex set in a Banach space. Let f : X → R be a closed proper convex function on X . Given a convex regularizer ψ : X ↔ R, we denote its induced Bregman divergence by D i (·, ·). Then, any update of the form
satisfies the following inequality
for any u ∈ X . The second one is the stability lemma, which is very useful in analyzing online algorithms based on FTRL or OMD frameworks. Lemma 5 (stability lemma (Chiang et al., 2012, Proposition 7)).  Consider the following two updates: (i) x ∗ = arg min x ∈ x ⟨ a, x ⟩ + D ψ (x, c), and (ii) x ′ ∗ = arg min x ∈ x ⟨ a ′ , x ⟩ + D ψ (x, c). When the regularizer ψ : X ↔ R is a 1-strongly convex function with respect to the norm || · ||, we have ||x* – x*|| ≤ ||(∇ψ(c) – a) – (∇ψ(c) – a')||* = ||a – a'||*. The self-bounding property of smooth functions is crucial and frequently used in proving small-loss bounds for convex and smooth functions. Lemma 6 (self-bounding property (Srebro et al., 2010, Lemma 3.1)). For an L-smooth and non-negative function f : X ↔ R + , we have ∥∇ f (x)‖ 2 ≤ √4Lf(x), ∀x ∈ X . Notably, from the analysis of original paper (Srebro et al., 2010 , Lemma 2.1 and Lemma 3.1), we can find that actually both the non-negativity and smoothness are required outside the domain X , and this is why we require the function f t ( · ) to be non-negative and smooth outside the domain X . Finally, we present several useful inequalities. Lemma 7. Let a,b > 0 and x 0 > 0 be three positive values. Suppose that L ≤ ax + ξ holds for any x ∈ (0, x 0].  Then, by taking x * = min{ √ b /α, x 0}, we ensure that
Proof  Suppose √ b / α ≤ x 0 , then x * = √ b / a and we have L ≤ ax * + x = 2√ ab . Otherwise, x* = x 0 and we have L ≤ ax* + ξ = αx 0 + x 0 . Notice that in latter case x 0 ≤ √ b /a holds, Lemma 8 (Lemma 19 of Shalev-Shwartz (2007)). For any x, y, a ∈ R+ that satisfy x − y ≤ √αx,
Lemma 9. For any x, y, a, b ∈ R + that satisfy x − y ≤ √ ax +
Lemma 10 (Lemma 3.5 of Auer et al. (2002)). Let a1,a2,...,a7 be non-negative real numbers.  Then where 0/√0 = 0. Lemma 11. Let α 1 ,α 2 , . . . ,ατ , b and c be non-negative real numbers and α t ∈ [0, B] for any t ∈ [T]. Let the step size be
Then, we have
Proof  This proof shares the same spirit with that of Pogodin and Lattimore (2019, Lemma 4.8). We assume ∑ t =1 α t ≤ B , otherwise we can directly have ∑ t =1 ct−1 α t ≤ c B . When ∑ t=1 α t > B, let t' = min{t ∈ [T] : ∑ t=1 α s ≥ B}. We can decompose the target by
For the first term we have ∑ t =1 ct−1 αt = ∑ t =1 ct−1 αt + c v−2 αt ′−1 ≤ 2 ∂ B . As for the second term, we have
where the second inequality is due to ∑ s=1 α s ≤ B + ∑ s=1 α s ≤ 2 ∑ s=1 α s and the last ■ inequality comes from Lemma 10 . We complete the proof by combining the two terms.