Dynamic Regret of Convex and Smooth Functions

Peng Zhao, Yu-Jie Zhang, Lijun Zhang, Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology,
Nanjing University, Nanjing 210023, China{zhaop, zhangyj, zhanglj, zhouzh}@lamda.nju.edu.cn

Abstract
We investigate online convex optimization in non-stationary environments andchoose the dynamic regret as the performance measure, defined as the difference
between cumulative loss incurred by the online algorithm and that of any feasible
comparator sequence. Let T be the time horizon and PT be the path-lengththat essentially reflects
p the non-stationarity of environments, the state-of-the-art
dynamic regret is O( T (1 + PT )). Although this bound is proved to be minimax
optimal for convex functions, in this paper, we demonstrate that it is possible
to further enhance the dynamic regret by exploiting the smoothness condition.
Specifically, we propose novel online algorithms that are capable of leveraging
smoothness and replace the dependence on T in the dynamic regret by problemdependent quantities: the variation in gradients of loss functions, the cumulativeloss of the comparator sequence, and the minimum of the previous two terms. These
quantities are at most O(T ) while could be much smaller in benign environments.
Therefore, our results are adaptive to the intrinsic difficulty of the problem, since
the bounds are tighter than existing results for easy problems and meanwhile
guarantee the same rate in the worst case.

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 a circumstance, which can be regarded as an
iterative game between a player and an adversary. At iteration t, the player selects a decision xt froma convex set X and the adversary reveals a convex function ft : X 7→ R. The player subsequently
suffers an instantaneous loss ft (xt ). The performance measure is the (static) regret [1],S-RegretT =TX

ft (xt ) − min
x∈X

t=1

T
X

ft (x),(1)t=1

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 isreasonably good over all the iterations. However, this is too optimistic and may not hold in changing
environments, where data are evolving and the optimal decision is drifting over time. To address thislimitation, dynamic regret is proposed to compete with changing comparators u1 , . . . , uT ∈ X ,D-RegretT (u1 , . . . , uT ) =

T
X
t=1

ft (xt ) −TXft (ut ),

(2)

t=1

which draws considerable attention recently [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]. The measure is also
called the universal dynamic regret (or general dynamic regret), in the sense that it gives a universal
34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

guarantee that holds against any comparator sequence. Note that static regret (1) can be viewed as
its special form by setting comparators as the fixed best decision in hindsight. Moreover, a variant
appeared frequently in the literature is the worst-case dynamic regret defined as
D-RegretT (x∗1 , . . . , x∗T ) =

T
X
t=1

ft (xt ) −TXft (x∗t ),

(3)

t=1

which specializes the general form (2) by setting ut = x∗t ∈ arg minx∈X ft (x). However, theworst-case dynamic regret is often too pessimistic, whereas the universal one is more adaptive to thenon-stationary environments. We refer the readers to [8] for more detailed explanations.
There are many studies on the worst-case dynamic regret [2, 3, 4, 5, 6, 7, 10, 13], but only few results
are known for thegradient descent (OGD)√ universal dynamic regret. Zinkevich [1] shows that onlinePTachieves an O( T (1 + PT )) universal dynamic regret, where PT = t=2 kut−1 − ut k2 is thepath-length of comparators u1 , . . . , uT and thus reflects the non-stationarity
p of the environments.
Nevertheless, there exists a large gap between this upper bound and the Ω( T (1 + PT )) minimax
lower bound establishedrecently by Zhang et al. [8], who further propose a novel online algorithm,pattaining an O( T (1 + PT )) universal dynamic regret, and thereby close the gap.
Although the rate is minimax optimal for convex functions, we would like to design algorithms withmore adaptive bounds, replacing the dependence on T by certain problem-dependent quantities thatare O(T ) in the worst case while could be much smaller in benign environments (i.e., easy problems).
In the study of static regret, we can attain such bounds when additional curvature like smoothness ispresented, including small-loss bounds [14] and variation bounds [15]. Thus, a natural question arises
whether it is possible to leverage smoothness to achieve more adaptive universal dynamic regret?
Our results. In this paper, we provide an affirmative answer by designing algorithms with problemdependent dynamic regret bounds. Specifically, we focus on the following two adaptive quantities:
the gradient variation of online functions VT and the cumulative loss of the comparator sequence FT ,
VT =

T
X

sup k∇ft−1 (x) − ∇ft (x)k22 , and FT =t=2 x∈X

TX

ft (ut ).

(4)

t=1

We propose a novel online approach for convex and smooth functions, named Smoothness-aware
online learning with dynamic regret (abbreviated as Sword). There are three versions, including
Swordvar , Swordsmall , and Swordbest . All of them enjoy problem-dependent dynamic regret bound:p• Swordvar enjoys a gradient-variation bound of O( (1 + PT + VT )(1 + PT ));p• Swordsmall enjoys a small-loss bound of O( (1 + PT + FT )(1 + PT ));p• Swordbest enjoys a best-of-both-worlds bound of O( (1 + PT + min{VT , FT })(1 + PT )).
p
Comparing to the minimax rate of O( T (1 + PT )), our bounds replace the dependence on T by the
problem-dependent quantity PT + min{VT , FT }. Since the quantity is at most O(T ), our bounds
become much tighter when the problem is easy (for example when PT and VT /FT are sublinear
in T ), and meanwhile safeguard the same guarantee in the worst case. Therefore, our results are
adaptive to the intrinsic difficulty of the problem and the non-stationarity of the environments.
Technical contributions. We highlight challenges and technical contributions of this paper. First,
we note that there exist studies showing that the worst-case dynamic regret can benefit from smoothness [5, 6, 13]. However, their analyses do not apply to our case, since we cannot exploit the
optimality condition of comparators u1 , . . . , uT , in stark contrast with the worst-case dynamic regret
analysis. Therefore, we adopt the meta-expert framework to hedge the non-stationarity while keeping
the adaptivity. We can use variants of OGD as the expert-algorithm to exploit the smoothness, but
it is difficult to design an appropriate meta-algorithm. Existing meta-algorithms and their variants
either lead to problem-independent regret bounds or introduce terms that are incompatible to thedesired problem-dependent quantity. To address the difficulty, we adopt the technique of optimistic
online learning [16, 17], in particular OptimisticHedge, to design novel meta-algorithms.
For Swordvar , we apply OptimisticHedge with carefully designed optimism, which allows us to exploit
the negative term in the regret analysis of OptimisticHedge [17]. In this way, the meta-regret only2

depends on the gradient variation. The construction of the special optimism is the most challenging
part of our paper. For Swordsmall , the design of meta-algorithm is simple, and we directly use thevanilla Hedge, which can be treated as OptimisticHedge with null optimism. Finally, for Swordbest ,we still employ OptimisticHedge as the meta-algorithm, but introduce a parallel meta-algorithm tolearn the best optimism to ensure a best-of-both-worlds dynamic regret guarantee.

2

Gradient-Variation and Small-Loss Bounds

We first list assumptions used in the paper, and then propose online algorithms with gradient-variationand small-loss dynamic regret bounds, respectively. All the proofs can be found in the full paper [18].
2.1

Assumptions

We introduce the following 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., k∇ft (x)k2 ≤ G, for all x ∈ X and t ∈ [T ].
Assumption 2. The domain X ⊆ Rd contains the origin 0, and the diameter of the domain X is at
most D, i.e., kx − x0 k2 ≤ D for any x, x0 ∈ X .
Assumption 3. All the online functions are L-smooth, i.e., for any x, x0 ∈ X and t ∈ [T ],k∇ft (x) − ∇ft (x0 )k2 ≤ Lkx − x0 k2 .

(5)

Assumption 4. All the online functions are non-negative.
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 [14].
Meanwhile, we treat double logarithmic factors in T as a constant, following previous studies [19, 20].
2.2

Gradient-Variation BoundWe design an approach in a meta-expert framework, and prove its gradient-variation dynamic regret.
2.2.1

Expert-Algorithm

In the study of static regret, Chiang et al. [15] propose the following online extra-gradient descent(OEGD) algorithm, and show that the algorithm enjoys gradient-variation static regret bound. The
OEGD algorithm performs the following update:bt+1 = ΠX [bxxt − η∇ft (xt )] ,xt+1 = ΠX [bxt+1 − η∇ft (bxt+1 )] ,(6)

b1 , x1 ∈ X , η > 0 is the step size, and ΠX [·] denotes the projection onto the nearest √where xpoint
in X . For convex and smooth functions, Chiang et al. [15] prove that OEGD achieves an O( VT )static regret. We further demonstrate that OEGD also enjoys gradient-variation type dynamic regret.
1
Theorem 1. Under Assumptions 1, 2, and 3, by choosing η ≤ 4L
, OEGD (6) satisfies
TX
t=1

ft (xt ) −

T
X
t=1

ft (ut ) ≤1 + P
D2 + 2DPTT+ ηVT + GD = O+ ηVT .
2ηηfor any comparator sequence u1 , . . . , uT ∈ X .
Theorem 1 shows that it is crucial to tune the step size to balance non-stationarity(path-length PT )p
and adaptivity (gradient variation VT ). Notice that the optimal tuning η ∗ = (D2 + 2DPT )/(2VT )requires the prior information of PT and VT that are generally unavailable. We emphasize that VT isempirically computable, while PT remains unknown even after all iterations due to the fact that thecomparator sequence is unknown and can be chosen arbitrarily as long as it is feasible in the domain.
Therefore, the doubling trick [21] can only remove the dependence on the unknown VT but not PT .
To handle the uncertainty, we adopt the meta-expert framework to hedge the non-stationarity while
keeping the adaptivity, inspired by the recent advance in learning with multiple learning rates [22,323, 8]. Concretely, we first construct a pool of candidate step sizes to discretize value range of the
optimal step size, and then initialize multiple experts simultaneously, denoted by E1 , . . . , EN . Eachexpert Ei returns its prediction xt,i by running OEGD (6) with a step size ηi from the pool. Finally,
predictions of all the experts are combined by a meta-algorithm as the final output xt to track the bestexpert. From the procedure, we observe that the dynamic regret can be decomposed as,
D-RegretT =TX

ft (xt ) −

t=1

T
X

ft (ut ) =

t=1

T
X

ft (xt ) − ft (xt,i ) +

t=1

|

T
X

ft (xt,i ) − ft (ut ),

t=1

{z

meta-regret

}

|

{z

expert-regret}

where {xt }t=1,...,T denotes the final output sequence, and {xt,i }t=1,...,T is the prediction sequenceof expert Ei . The first part is the difference between cumulative loss of final output sequence and thatof prediction sequence of expert Ei , which is introduced by the meta-algorithm and thus named asmeta-regret; the second part is the dynamic regret of expert Ei and therefore named as expert-regret.
The expert-algorithm is set as OEGD (6), and Theorem 1 upper bounds the expert-regret. The maindifficulty lies in the design and analysis of an appropriate meta-algorithm.
2.2.2

Meta-Algorithm

Formally, there are N experts and expert Ei predicts xt,i at iteration t, and the meta-algorithm requires
PN
to produce xt = i=1 pt,i xt,i , a weighted combination of expert predictions, where pt ∈ ∆N is theweight vector. It is natural to use Hedge [24] for weight update in order to track the best expert.
In order to be compatible to the gradient-variation√expert-regret, the meta-algorithm is required toincur a problem-dependent meta-regret of order O( VT ln N ). However, the meta-algorithms used inexisting studies [23, 8] cannot satisfy√
the requirements. For example, the vanilla Hedge (multiplicative
weights update) suffers from an O( T ln N ) meta-regret, which is problem-independent and thus
not suitable for us. To this end, we design a a novel variant of Hedge by leveraging the technique of
optimistic online learning with carefully designed optimism, specifically for our problem.
The optimistic online learning is developed by Rakhlin and Sridharan [16] and further expanded
by Syrgkanis et al. [17]. For the prediction with expert advice setting, they consider that at the
beginning of iteration (t + 1), in addition to the loss vector `t ∈ RN returned by the experts, thelearner can receive a vector mt+1 ∈ RN called optimism. The authors propose the OptimisticHedge
algorithm [16, 17], which updates the weight vector pt+1 ∈ ∆N by!
t
Xpt+1,i ∝ exp −ε`s,i + mt+1,i, ∀i ∈ [N ].
(7)s=1

Syrgkanis et al. [17] prove the following regret guarantee for OptimisticHedge.
Lemma 1 ([17, Theorem 19]). The meta-regret of OptimisticHedge is upper bounded byTX
t=1

hpt , `t i − `t,i ≤TTX
2 + ln N
1 X+εk`t − mt k2∞ −kpt − pt−1 k21 ,
ε
4ε
t=1
t=2

(8)

PT
2
which holds for any expert i ∈ [N ]. Denote by D∞ = t=1 k`t −√ mt k∞ to measure the adaptivity.
With proper learning rate tuning, OptimisticHedge enjoys an O( D∞ ln N ) meta-regret.
The optimistic online learning is very powerful for designing adaptive methods, in that the adaptivity
D∞ in Lemma 1 is very general and can be specialized flexibly with different configurations of the
feedback loss `t and optimism mt . Based on the OptimisticHedge, we propose VariationHedge, themeta-algorithm for Swordvar , by specializing OptimisticHedge as follows:• the feedback loss `t is set as the linearized surrogate loss, namely, `t,i = h∇ft (xt ), xt,i i;• the optimism mt is set with a careful design: for each i ∈ [N ]mt,i = h∇ft−1 (x̄t ), xt,i i, where x̄t =

N
X
i=1

4

pt−1,i xt,i .

(9)Algorithm 1 Swordvar : Meta (VariationHedge)
Input: step size pool Hvar ; learning rate ε1: Initialization: ∀i ∈ [N ], p0,i = 1/N
2: for t = 1 to T do
3:
Receive xt+1,i from expert Ei (ηi )4:Update weight pt+1,i by (10)PN
5:Predict xt+1 = i=1 pt+1,i xt+1,i
6: end for

Algorithm 2 Swordvar : Expert (OEGD)
Input: step size ηib1,i , x1,i be any point in X
1: Let x
2: for t = 1 to T do
bt+1,i = ΠX xb
3:x
 t,i − ηi ∇ft (xt,i )
bt+1,i − ηi ∇ft (b4:
xt+1,i = ΠX x
xt+1,i )5:
Send xt+1,i to meta-algorithm
6: end for

So the meta-algorithm of Swordvar (namely, VariationHedge) updates the weight by!
tXpt+1,i ∝ exp −εh∇fs (xs ), xs,i i + h∇ft (x̄t+1 ), xt+1,i i, ∀i ∈ [N ].

(10)

s=1

Algorithm 1 summarizes detailed procedures of the meta-algorithm, which in conjunction with theexpert-algorithm of Algorithm 2 yields the Swordvar algorithm.
Remark 1. The design of optimism in (9) (in particular, x̄t ) is crucial, and is the most challenging
part in this work. The key idea is to exploit the negative term in the regret of OptimisticHedge, as
shown in (8), to convert the adaptive quantity D∞ to the desired gradient variation VT . Indeed,(9)k`t − mt k2∞ = maxi∈[N ] h∇ft (xt ) − ∇ft−1 (x̄t ), xt,i i2≤ D2 k∇ft (xt ) − ∇ft−1 (x̄t )k22
≤ 2D2 (k∇ft (xt ) − ∇ft−1 (xt )k22 + k∇ft−1 (xt ) − ∇ft−1 (x̄t )k22 )≤ 2D2 supx∈X k∇ft (x) − ∇ft−1 (x)k22 + 2D2 L2 kxt − x̄t k22
where the last step makes use of smoothness. Therefore, D∞ can be upper bounded by the gradientvariation VT and the summation of kxt − x̄t k22 . The latter one can be further expanded as
kxt − x̄t k22 =NX2(pt,i − pt−1,i )xt,i

i=1

≤
2

N
X
2
|pt,i − pt−1,i |kxt,i k2 ≤ D2 kpt − pt−1 k21 ,i=1

which can be eliminated by the negative term in (8), with a suitable setting of the learning rate ε.
2.2.3

Regret Guarantees√
We prove that the meta-regret of VariationHedge is O( VT ln N ), compatible to the expert-regret.
TheoremAssumptions 1, 2, and 3, by setting the learning rate optimally as ε =p 2. Under p42min{ 1/(8D L ), (2 + ln N )/(2D2 VT )}, the meta-regret of VariationHedge is at mostpp√meta-regret ≤ 2D 2VT (2 + ln N ) + 4 2D2 L(2 + ln N ) = O( VT ln N ).
Note that the dependence on VT in the optimal learning rate tuning can be removed by the doubling
trick. Furthermore, actually we can set the optimal learning rate of the meta-algorithm with VbT =PT
2
t=2 k∇ft (xt ) − ∇ft−1 (xt )k2 instead of the original gradient variation VT via a more refinedbanalysis. The quantity VT can be regarded as an empirical approximation of VT , and it can becalculated directly without involving the inner problem of supx∈X k∇ft (x) − ∇ft−1 (x)k22 . Thereby,
we can perform the doubling trick by monitoring VbT with much less computational efforts. Combining
Theorem 1 (expert-regret) and Theorem 2 (meta-regret), we have the following dynamic regret bound.
Theorem 3. Under Assumptions 1, 2, and 3, setting the pool of candidate step sizes Hvar as
(
)
r
2
D
Hvar = ηi = 2i−1
, i ∈ [N1 ] ,
2GT
5

(11)

where N1 = d2−1 log2 (GT /(8D2 L2 ))e + 1.1 Then Swordvar (Algorithms 1 and 2) satisfies
TX

ft (xt ) −

t=1

T
X

ft (ut ) ≤ O

p(1 + PT + VT )(1 + PT )

t=1

for any comparator sequence u1 , . . . , uT ∈ X .
pRemark 2. Compared with the existing O( T (1 + PT )) dynamic regret [8], our result is more
adaptive in the sense that it replaces T by the problem-dependent quantity PT + VT . Therefore,
the bound will be much tighter in easy problems, for example when both VT and PT are o(T ).
Meanwhile, it safeguards the same minimax rate, since both quantities are at most O(T ).
Remark 3. 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 inPThindsight, i.e., u1 = . . . = uT = x∗ ∈ arg minx∈X t=1 ft (x). Under such a circumstance, thePTpath-length√ PT = t=2 kut−1 − ut k2 will be zero, so the regret bound in Theorem 3 actually implies
an O( VT ) variation static regret bound, which recovers the result of Chiang et al. [15].
2.3

Small-Loss BoundIn this part, we turn to another problem-dependent quantity, cumulative loss of the comparator
sequence, and prove the small-loss dynamic regret. We start from the online gradient descent (OGD),
xt+1 = ΠX xt − η∇ft (xt ) .
(12)
p ∗
P
T
Srebro et al. [14] prove that OGD achieves an O( FT ) static regret, where FT∗ = t=1 ft (x∗ ) is
the cumulative loss of the comparator benchmark x∗ . For the dynamic regret, since the benchmark
is changing, a natural replacement is the cumulative loss of the comparator sequence u1 , . . . , uT ,PT
namely FT = t=1 ft (ut ). We show that OGD indeed enjoys such a small-loss dynamic regret.
1
Theorem 4. Under Assumptions 2, 3, and 4, by choosing any step size η ≤ 4L
, OGD satisfies
TX

ft (xt ) −

t=1

T
X
t=1

ft (ut ) ≤T1 + P
2ηL X
D2 + 2DPTT+
ft (ut ) = O+ ηFT2η(1 − 2ηL) 1 − 2ηL t=1
η

for any comparator sequence u1 , . . . , uT ∈ X .
Similar to Swordvar , the step size needs to balance between non-stationarity (PT ) and adaptivity (FT ,this time). Notice that the optimal tuning depends on PT and FT , both of which are unknown evenafter all T iterations. Therefore, we again compensate the lack of this information via the meta-expert
framework to hedge the non-stationarity while keeping the adaptivity. The expert-algorithm
is set as√
OGD. The meta-algorithm is required to suffer a small-loss meta-regret of order O( FT ln N ). We
discover that vanilla Hedge with linearized surrogate loss is qualified, which updates the weight bytX
pt+1,i ∝ exp − εh∇fs (xs ), xs,i i , ∀i ∈ [N ].
(13)
s=1

Notice that vanilla Hedge can be treated as OptimisticHedge with√null optimism, i.e., mt+1 = 0.
Therefore, by Lemma 1 we know that its meta-regret is of order O( D∞ ln N ) and
D∞ =

T
X

maxi∈[N ] h∇ft (xt ), xt,i i2 ≤ D2

t=1

T
X
t=1

k∇ft (xt )k22 ≤ 4D2 L

TX

ft (xt ),

(14)

t=1

where the last inequality follows from the self-bounding
property of smooth functions [14, LemmapPT3.1]. As a result, the meta-regret is now O( FTx ln N ), where FTx = t=1 ft (xt ) is the cumulativeloss of decisions. Note that the term FTx can be further processed to the desired small-loss quantity
PT
FT = t=1 ft (ut ), the cumulative loss of comparators. We will present details in the proof.
To summarize, Swordsmall chooses OGD (12) as the expert-algorithm, and uses the vanilla Hedge
with linearized surrogate loss as the meta-algorithm shown in the update form (13). The theorem
below shows that the proposed algorithm enjoys the small-loss dynamic regret bound.
1

The number of candidate step sizes is denoted by N1 instead of N to distinguish it with that of Swordsmall .

6

Theorem 5. Under Assumptions 1, 2, 3, and 4, setting the pool of candidate step sizes Hsmall as()
rD
Hsmall = ηi = 2i−1
, i ∈ [N2 ] ,
(15)
16LGT
−1
where
pN2 = d2 log2 (GTx /(DL))e + 1. Setting the learning rate of meta-algorithm optimally as
ε = (2 + ln N2 )/(D2 FT ), then Swordsmall satisfies
TX

ft (xt ) −

t=1

T
X

ft (ut ) ≤ Op
(1 + PT + FT )(1 + PT ) .

t=1

for any comparator sequence u1 , . . . , uT ∈ X .
Note that the optimal learning rate tuning requires the knowledge of FTx , which can be easily removed
by doubling trickp
or self-confident tuning [25], since it is empirically evaluable at each iteration.
Moreover,theO((1 + PT + FT )(1 + PT )) universal dynamic regret in Theorem 5 specializes to√
the O( FT ) static regret [14] when setting the comparators as the fixed best decision in hindsight.

3Best-of-Both-Worlds BoundIn the last section, we propose Swordvar and Swordsmall that achieve variation and small-loss bounds
respectively. Due to different problem-dependent quantities are involved, these two bounds are
generally incomparable and are favored in different scenarios. Therefore, it is natural to ask for abest-of-both-worlds guarantee: the regret of the minimum of variation and small-loss bounds.
To this end, we require a meta-algorithm Table 1: Summary of expert-algorithms and meta-algorithms
that can enjoy both kinds of adaptiv- as well as different optimism used in the proposed algorithms
ity to pcombine all the experts, with (including three variants of Sword).
an O( min{VT , FT } ln N ) meta-regret.
MethodExpertMeta
Optimism
Based on the observation that both VariSwordvar
OEGD
VariationHedgeby (9)
ationHedge and vanilla Hedge are essenSwordsmall
OGDvanilla Hedge
mt+1 = 0
tially special cases of OptimisticHedge
Swordbest
OEGD & OGD OptimisticHedge by (18), (21)with different configurations of optimism,
we adopt the OptimisticHedge to be the meta-algorithm for Swordbest , where a parallel meta-algorithm
is introduced to learn the best optimism for OptimisticHedge to ensure best-of-both-worlds metaregret. In the following we describe the expert-algorithm and meta-algorithm of Swordbest .
Expert-algorithm. We aggregate the experts of Swordvar and Swordsmall , so there are N = N1 +N2
experts in total and the step size of each experts is set according to the pool H = Hvar ∪ Hsmall(cf. (11) and (15) for definitions). The first N1 experts run OEGD (6) with the step size chosen from
Hvar , and the other N2 experts perform OGD (12) with step size specified by Hsmall . At iteration t,
the final output is a weighted combination of predictions returned by the expert-algorithms, namely,
xt =

N
X

pt,i xt,i =

i=1

N1
X

pt,i xvt,i +

i=1

NX
1 +N2

pt,i xst,i ,(16)

i=N1 +1

where pt ∈ ∆N1 +N2 is the weight, xt,i = xvt,i for i = 1, . . . , N1 are predictions returned by theexpert-algorithms (OEGD) of Swordvar , and xt,i = xst,i for i = N1 + 1, . . . , N1 + N2 are predictions
returned by the expert-algorithms (OGD) of Swordsmall . It remains to specify the meta-algorithm.
Meta-algorithm. We adopt the OptimisticHedge algorithm along with the linearized surrogate loss
as the meta-algorithm, where the weight vector pt+1 ∈ ∆N1 +N2 is updated according to!
tXpt+1,i ∝ exp −εh∇fs (xs ), xs,i i + mt+1,i
,
(17)
s=1
N1 +N2where the optimism mt+1 ∈ R. In order to facilitate the meta-algorithm with both kinds ofadaptivity (VT and FT ), it is crucial to design best-of-both-worlds optimism.
7

Algorithm 3 Swordbest : Meta (OptimisticHedge) Algorithm 4 Swordbest : Expert (OEGD & OGD)
Input: step size ηi
Input: step size pool H; learning rate εb1,i , x1,i be any point in X
1: Let x
1: Let N = N1 + N2 , ∀i ∈ [N ], p0,i = 1/N
2: for t = 1 to T do
2: for t = 1 to T do
3:
if i ∈ {1, . . . , N1 } then3:
Receive prediction xt+1,i from expert Ei
v
s4:
Set Mt+1
and Mt+1
by (19) and (20)bt+1,i = ΠX x
bt,i − ηi ∇ft (xt,i )
4:
x


5:
Update the weight βt+1 by (22)bt+1,i − ηi ∇ft (b5:
xt+1,i = ΠX x
xt+1,i ) .
6:
Obtain the optimism Mt+1 (21)
6:
else


7:
Update the weight pt+1,i by (17) and (18)7:
xt+1,i = ΠX xt,i − ηi ∇ft (xt,i ) .
8:
Output the prediction
8:
end ifPN
xt+1 = i=1 pt+1,i xt+1,i
9:
Send prediction xt+1,i to meta-algorithm
9: end for
10: end for
We set the optimism mt+1 in the following way: for each i ∈ [N1 + N2 ]mt+1,i = hMt+1 , xt+1,i i,

(18)

d

where Mt+1 ∈ R is called the optimistic vector. So we are left with the task of determining the termof Mt+1 in (18). Inspired by the seminal work of Rakhlin and Sridharan [16], we treat the problem of
selecting the sequence of optimistic vectors as another online learning problem. The idea is to build aparallel meta-algorithm for learning the optimistic vector Mt+1 , which is then fed to OptimisticHedgeof (17) for combining multiple experts, to achieve a best-of-both-worlds meta-regret.
Specifically, consider the following learning scenario of prediction with two expert advice. At thevs∈ Rd , based on which
beginning of iteration (t + 1), we receive two optimistic vectors Mt+1
, Mt+1the algorithm determines the optimistic vector Mt+1 ∈ Rd for Swordbest . Then the online functionv
s
ft+1 is revealed, and we subsequently observe the loss of dt+1 (Mt+1) and dt+1 (Mt+1), where2vs
dt+1 (M ) = k∇ft+1 (xt+1 ) − M k2 . In above, the vectors of Mt+1 and Mt+1 aresv
Mt+1= ∇ft (x̄t+1 ), and Mt+1
= 0,
(19)
where x̄t+1 is the instrumental output. Similar to the construction of (9), it is designed as
XN1
XN1 +N2x̄t+1 =
pt,i xvt+1,i +
pt,i xst+1,i .
(20)
i=1

i=N1 +1

Notice that the function dt : Rd 7→ R is 2-strongly convex with respect to k · k2 -norm, we thus choose
Hedge of strongly convex functions [26, Chapter 3.3] as the parallel meta-algorithm for updating,vs
Mt+1 = βt+1 Mt+1
+ (1 − βt+1 )Mt+1,(21)
where the weight βt+1 ∈ [0, 1] for learning optimistic vectors is updated byexp(−2Dtv )βt+1 =(22)exp(−2Dtv ) + exp(−2Dts )Pt
Pt
with Dtv = τ =1 dτ (Mτv ) and Dts = τ =1 dτ (Mτs ).
Algorithm 3 summarizes the meta-algorithm of Swordbest . In the last two columns of Table 1, we
present comparisons of the meta-algorithms and optimism designed for different methods .
√Regret Analysis. Recall that the meta-regret of OptimisticHedge is of order O( D∞ ln N ). Fromthe setting of surrogate loss (17) and optimism (18), we have
D∞ =

T
X

2

maxi∈[N ] (h∇ft (xt ) − Mt , xt,i i) ≤ D2

TXk∇ft (xt ) − Mt k22 .

t=1

t=1

Besides, the regret analysis of Hedge for strongly convex functions [26, Proposition 3.1] implies
T
X

T
X


ln 2
dt (Mt ) ≤ min V̄T , F̄T +
,
2
t=1
t=1
PT
PT
where V̄T = t=2 k∇ft (xt ) − ∇ft−1 (x̄t )k22 and F̄T = t=1 k∇ft (xt )k22 . The two terms can befurther converted to the desired gradient variation VT and small loss FT , by exploiting the smoothness
and expert-regret analysis. We can thus ensure the following meta-regret bound.
k∇ft (xt ) − Mt k22 =8

Theoremp 6. Under Assumptions 1, 2, 3, and 4, by setting the learning rate optimally as ε =min{ 1/(8D4 L2 ), ε∗ }, the meta-algorithm of Swordbest satisfiesq√meta-regret ≤ 2D (2 + ln N )(min{2VT , F̄T } + ln 2) + 4 2D2 L(2 + ln N )pwhere ε∗ = (2 + ln N )/(D2 min{2VT , F̄T } + D2 ln 2).
Because VT and F̄T are both empirically observable, we can easily get rid of their dependence inthe optimal learning rate tuning. Also see the discussion below Theorem 2 about replacing thePT
original gradient variation VT by its empirical approximation VbT = t=2 k∇ft (xt ) − ∇ft−1 (xt )k22
to save computational costs. Besides, the F̄T term of meta-regret will be converted to the desired
small-loss quantity FT in the final regret bound. Combining above meta-regret analysis as well as theexpert-regret analysis of OEGD and OGD algorithms, we can finally achieve the best of both worlds.
Theorem 7. Under Assumptions 1, 2, 3, and 4, setting the pool of candidate step sizes as
H = Hvar ∪ Hsmall ,(23)

where Hvar and Hsmall are defined in (11) and (15). Then Swordbest (Algorithms 3 and 4) satisfies
TX

ft (xt ) −

t=1

T
X

ft (ut ) ≤ Op
(1 + PT + min{VT , FT })(1 + PT ) ,t=1

for any comparator sequence u1 , . . . , uT ∈ X .
Remark 4. The dynamic regret bound in Theorem 7 achieves a minimum of gradient-variation andsmall-loss bounds, and therefore combines
p their advantages and enjoys both kinds of adaptivity.
Moreover, the result also implies an O( min{VT , FT }) static regret by setting the sequence ofcomparators to be the best fixed decision in hindsight, where we note that FT is now the same as thenotation of FT∗ used below (12), the cumulative loss of the comparators benchmark.

4

Conclusion

In this paper, we exploit smoothness to enhancep the universal dynamic regret, with the aim to replace
the time horizon T in the state-of-the-art O( T (1 + PT )) bound by problem-dependent quantities
that are at most O(T ) but can be much smaller in easy problems. We achieve this goal by proposing
two meta-expert
algorithms: Swordvar which attains a gradient-variation dynamic regret bound of orp
der O( (1p+ PT + VT )(1 + PT )), and Swordsmall which enjoys a small-loss dynamic regret boundof order O( (1 + PT + FT )(1 + PT )). Here, VT measures the variation in gradients and FT is the
cumulative loss of the comparator sequence. They are at most O(T ) yet could be very small when
the problem is easy, and thus reflect the difficulty of the problem instance. As a result, our bounds
improve the minimax rate of universal dynamic regret by exploiting smoothness. Finally, we design
Swordbest to combine advantages of both gradient-variation
p and small-loss algorithms and achieve abest-of-both-worlds dynamic regret bound of order O( (1 + PT + min{VT , FT })(1 + PT )). We
note that all of attained dynamic regret bounds are universal in the sense that they hold against
any feasible comparator sequence, and thus the algorithms are more adaptive to the non-stationary
environments. In the future, we will investigate the possibility of exploiting other function curvatures,such as strong convexity or exp-concavity, into the analysis of the universal dynamic regret.

Acknowledgment
This research was supported by the National Key R&D Program of China (2018YFB1004300), NSFC
(61921006, 61976112), the Collaborative Innovation Center of Novel Software Technology andIndustrialization, and the Baidu Scholarship. The authors would like to thank Mengxiao Zhang forhelpful discussions. We are also grateful for the anonymous reviewers for their valuable comments.

Broader Impact
The work is mostly theoretical and the broader impact discussion is not applicable.
9References[1] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In
Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928–936,
2003.
[2] Omar Besbes, Yonatan Gur, and Assaf J. Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015.
[3] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online
optimization : Competing with dynamic comparators. In Proceedings of the 18th International
Conference on Artificial Intelligence and Statistics (AISTATS), pages 398–406, 2015.
[4] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In
Proceedings of the 55th IEEE Conference on Decision and Control (CDC), pages 7195–7201,
2016.
[5] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant:
Optimal dynamic regret of online learning with true and noisy gradient. In Proceedings of the
33rd International Conference on Machine Learning (ICML), pages 449–457, 2016.
[6] Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic
regret for non-degeneracy functions. In Advances in Neural Information Processing Systems 30(NIPS), pages 732–741, 2017.
[7] Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive
methods. In Proceedings of the 35th International Conference on Machine Learning (ICML),
pages 5877–5886, 2018.
[8] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments.
In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330–1340, 2018.
[9] Peter Auer, Yifang Chen, Pratik Gajane, Chung-Wei Lee, Haipeng Luo, Ronald Ortner, and
Chen-Yu Wei. Achieving optimal dynamic regret for non-stationary bandits without priorinformation. In Proceedings of the 32nd Conference on Learning Theory (COLT), pages
159–163, 2019.
[10] Dheeraj Baby and Yu-Xiang Wang. Online forecasting of total-variation-bounded sequences. In
Advances in Neural Information Processing Systems 32 (NeurIPS), pages 11071–11081, 2019.
[11] Jianjun Yuan and Andrew 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.
[12] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in
non-stationary environments. In Proceedings of the 23rd International Conference on Artificial
Intelligence and Statistics (AISTATS), pages 1508–1518, 2020.
[13] Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex andsmooth functions. ArXiv preprint, arXiv:2006.05876, 2020.
[14] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In
Advances in Neural Information Processing Systems 23 (NIPS), pages 2199–2207. 2010.
[15] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin,
and Shenghuo Zhu. Online optimization with gradual variations. In Proceedings of the 25th
Conference On Learning Theory (COLT), pages 6.1–6.20, 2012.
[16] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In
Proceedings of the 26th Conference On Learning Theory (COLT), pages 993–1019, 2013.
[17] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergenceof regularized learning in games. In Advances in Neural Information Processing Systems 28(NIPS), pages 2989–2997, 2015.
10

[18] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex andsmooth functions. ArXiv preprint, arXiv:2007.03479, 2020.
[19] Dmitry Adamskiy, Wouter M. Koolen, Alexey V. Chernov, and Vladimir Vovk. A closer look at
adaptive regret. In Proceedings of the 23rd International Conference on Algorithmic Learning
Theory (ALT), pages 290–304, 2012.
[20] Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: AdaNormalHedge. In
Proceedings of the 28th Annual Conference Computational Learning Theory (COLT), pages
1286–1304, 2015.
[21] Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire,and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485,
1997.
[22] Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. In
Proceedings of The 27th Conference on Learning Theory (COLT), pages 176–196, 2014.
[23] Tim van Erven and Wouter M. Koolen. Metagrad: Multiple learning rates in online learning. In
Advances in Neural Information Processing Systems 29 (NIPS), pages 3666–3674, 2016.
[24] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learningand an application to boosting. Journal of Computer and System Sciences, 55(1):119–139,
1997.
[25] Peter Auer, Nicolò Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line
learning algorithms. Journal of Computer and System Sciences, 64(1):48–75, 2002.
[26] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge
University Press, 2006.

11