A Simple Online Algorithm for Competing with Dynamic Comparators

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

Abstract
Online learning in dynamic environments has
recently drawn considerable attention, where
dynamic regret is usually employed to compare decisions of online algorithms to dynamic
comparators. In previous works, dynamic regret bounds are typically established in terms ofregularity of comparators CT or that of online
functions VT . Recently, Jadbabaie et al. [2015]
propose an algorithm that can take advantageof√e 1 + DT +both regularities and enjoy an O(p
1/3min{ (1 + DT )CT , (1+DT )1/3 VT T 1/3 })dynamic regret, where DT is an additional
quantity to measure the niceness of environments. The regret bound adapts to the smaller
regularity of problem environments and istighter than all existing dynamic regret guarantees. Nevertheless, their algorithm involves
non-convex programming at each iteration, andthus requires burdensome computations. In thispaper, we design a simple algorithm based on
the online ensemble, which provably enjoys thesame (even slightly stronger) guarantee as thestate-of-the-art rate, yet is much more efficientbecause our algorithm does not involve any nonconvex problem solving. Empirical studies also
verify the efficacy and efficiency.

Afterwards, a convex function ft : X 7→ R is revealed by
the environments and the learner suffers an instantaneous
loss ft (xt ). The classical measure for an online algorithm
is the regret [Zinkevich, 2003],
RegsT =TX

ft (xt ) − min

t=1

x∈X

T
X

ft (x),

t=1

which compares learner’s decisions against a single best
decision in hindsight. The measure is often referred toas the static regret since the comparator is time-invariant.
For convex functions, Zinkevich√[2003] shows that online
gradient descent enjoys an O( T ) static regret, which
is further proved to be the minimal regret that can beachieved in the worst case [Abernethy et al., 2008].
Notwithstanding the minimax optimality, the rate can befurther improved by exploiting the niceness of the environments, which aims to design algorithms that can
automatically adapt to easier problem environments, yetsafeguard the worst-case rate. There are many ways to
exploit the niceness of environments. Rakhlin and Sridharan [2013] develop a general framework to unify previous
works by introducing the notion of predictable sequences{Mt }Tt=1 , which can be regarded as external knowledge
on the√gradients of the online functions. They show thatan O( DT ) static regret is attainable, where DT measures the quality of the predictable sequences defined as
DT =

T
X
k∇ft (xt ) − Mt k2∗ .

(1)

t=1

1

INTRODUCTION

Online Convex Optimization (OCO), in which an online
learner iteratively makes the decision against the environments, has demonstrated powerful modeling capability in many real-life applications [Shalev-Shwartz, 2012,
Hazan, 2016]. The basic protocol of OCO is as follows:at each iteration t ∈ {1, . . . , T }, the learner first chooses
a decision xt from some convex feasible set X ⊆ Rd .
Proceedings of the 36th Conference on Uncertainty in Artificial
Intelligence (UAI), PMLR volume 124, 2020.

The term is at most O(T ) under certain standard assumptions, yet it could be quite small when Mt approximatesthe gradient well. Therefore, the attained regret√ bound istighter than the minimax optimal rate of O( T ).
Another way to strengthen the theoretical guarantees is tocompare the learner’s decisions with time-varying comparators. This is often desired, particularly for learning in
the non-stationary environments [Sugiyama and Kawanabe, 2012, Gama et al., 2014, Zhao et al., 2019], wherethere is no single fixed decision that performs well over
all the iterations. Under such a circumstance, dynamic
regret is introduced to measure the performance of an
online algorithm [Zinkevich, 2003, Besbes et al., 2015,
Yang et al., 2016, Zhang et al., 2017, Baby and Wang,2019, Zhao and Zhang, 2020], defined as
RegdT =TX

ft (xt ) −

t=1

T
X

ft (x∗t ),t=1

where x∗t ∈ arg minx∈X ft (x) is the minimizer of theonline function at each iteration. It is known that a sublinear dynamic regret bound is not possible unless imposing
certain restrictions on the environments. In the literature,
two types of regularities are introduced. The first is thepath-length [Zinkevich, 2003, Yang et al., 2016, Mokhtari
et al., 2016, Zhang et al., 2018],
CT =

T
X
kx∗t − x∗t−1 k,

(2)

t=2

measuring the fluctuation of comparators. Another regularity is the temporal variability [Besbes et al., 2015,
Chen et al., 2019, Baby and Wang, 2019],
VT =

T
X

sup |ft (x) − ft−1 (x)|,(3)

carefully designing a novel doubling trick scheme. Nevertheless, their method requires the empirical version of
temporal variability VT for checking the doubling condition. Therefore, it will introduce a non-convex inner optimization problem of supx∈X |ft (x) − ft−1 (x)| at each
iteration. By exploiting the special propriety of this problem, difference of convex functions programming can beused for solving it, however, is very time-consuming.
In this paper, we discover that a simple and efficient approach provably achieves the same (even slightly stronger)
dynamic regret bound (4) as Jadbabaie et al. [2015]. Ourcontribution is that the proposed algorithm avoids thetime-consuming inner optimization problem, and thus is
more computationally efficient. The crucial advantage
roots in a novel step size tuning approach via the online
ensemble rather than the doubling trick, where a master
algorithm is employed to search over base algorithms
with multiple learning parameters. Meanwhile, for exploiting the niceness of environments, we build a newmaster algorithm based on optimistic Hedge [Rakhlin and
Sridharan, 2013] with properly designed optimism, whichmakes compatible regret bounds for both master and basealgorithms, and finally leads to the desired result. Moreover, we provide novel analysis of the temporal variability
dynamic regret bound for running online algorithms overthe surrogate linearized loss, which could be of interest.

t=2 x∈X

which captures the variation of the function values.
Thus, it is natural to ask whether the niceness of environments DT can also be exploited in the dynamic regret
analysis; and meanwhile, as CT and VT capture different
properties of the environments, is it possible to achieve
the best of the two regularities? The problem has beenstudied by the remarkable work of Jadbabaie et al. [2015].
They affirmatively answer the question by designing analgorithm with the fully adaptive dynamic regret,p
e 1 + DT + min{RC , RV } , (4)RegdT ≤ Oewhere O(·)
hides logarithmic terms in T , RC =p
1/3
(1 + DT )(1 + CT ) and RV = (1 + DT )1/3 VT T 1/3
are path-length and temporal variability bounds, respectively. The regret bound in (4) is adaptive in the sense thatit makes use of both regularities CT , VT , and adaptivity
DT . Thus, it can adapt to the smaller regularity of problem environments and is tighter than all existing dynamic
regret guarantees.
The key challenge of designing an online algorithm withadaptive bound is how to tune the learning parameters interplaying among the complexity measures (DT , CT , VT ),when their exact quantities are unknown in advance. Jadbabaie et al. [2015] successfully address the issue by

2

RELATED WORK

We review related work about online convex optimizationin the following two aspects.
2.1

STATIC REGRET

Significant efforts have been devoted to designing algorithms for static regret minimization. For convex functions, Zinkevich [2003] proves√ that online gradient descent (OGD) ensures an O( T ) static regret, and the rate
can be improved to O(log T ) for strongly convex functions [Hazan et al., 2007]. Besides, Hazan et al. [2007]
prove that a logarithmic regret O(d log T ) is also achievable for exp-concave functions by the online Newton stepalgorithm, where d is the dimensionality. All these results
are minimax optimal [Abernethy et al., 2008].
One direction to improve the guarantee is to exploit theniceness of environments. Hazan and Kale [2008] establish a bound relative toq
the variation of the gradiPT2¯
ent sequences of order O(
t=1 k∇ft (xt ) − ∇T )k∗P
T¯T = 1for convex functions, where ∇t=1 ∇ft (xt ).
T
When the online functions are convex and smooth, Chiang et al. [2012] show that the regret bound scaleswith the variation of consecutive gradients in the rate

Table 1: Comparisons of our results and existing dynamic regret bounds for convex functions.
complexity measurepath-length boundtemporal variability boundadaptive boundfully adaptive boundregret boundp
O( T (1 + CT ))1/3
O(T 2/3 VT )p
1/3
O(min{ T (1 + CT ), T 2/3 VT })p√
1/3
O( DT + min{ (1 + DT )(1 + CT ), (1 + DT )1/3 T 1/3 VT })

qP
T
2
of O(
t=1 supx∈X k∇ft (x) − ∇ft−1 (x)k∗ ). Afterwards, Rakhlin and Sridharan [2013] propose a generalframework to unify and generalize these results by introducing the notion of predictable sequences {Mt }Tt=1 .
They propose the optimistic
mirror descent which prov√
ably enjoys an O( DT ) static regret, where DT =PT
2
t=1 k∇ft (xt ) − Mt k∗ . The framework is very powerful as it can recover previous regret bounds by different
configurations of predictable sequences.
2.2

DYNAMIC REGRET

Roughly, there are two types of dynamic regret bounds
in terms of different regularities, the path-length CT , andtemporal variability VT .
Path-length Bound. The path-length is introducedby Zinkevich [2003], measuring the fluctuation of theonline minimizers, as defined in (2). When the pathlength CT is known
pin advance, Zinkevich [2003] shows
OGD enjoys an O( T (1 + CT )) dynamic regret for convex functions. This rate can be enhanced to O(CT ) forstrongly convex and smooth functions [Mokhtari et al.,2016], and the O(CT ) rate is also attainable for convex
and smooth functions if all the minimizers lie in the interior of X [Yang et al., 2016]. AnotherPT similar regularity
called squared path-length ST = t=1 kx∗t−1 − x∗t k2 isintroduced by Zhang et al. [2017], and authors propose analgorithm for strongly convex and smooth functions, with
O(min{CT , ST }) dynamic regret, and the regret rate isrecently improved to O(min{CT , ST , VT }) by Zhao andZhang [2020]. Since this paper focuses on convex functions, we do not take the squared path-length into account.
Temporal Variability Bound. The temporal variability is introduced by Besbes et al. [2015], capturing thevariation of function values, as defined in (3). When
VT is known in advance, Besbes et al. [2015] propose
the restarted OGD and derive minimax optimal regret
1/3
e 1/2 V 1/2 ) for convex
bounds of O(T 2/3 VT ) and O(TT
and strongly convex functions respectively. The algorithm
and analysis are further generalized by later studies [Chenet al., 2019, Baby and Wang, 2019].
Adaptive Bound. The two regularities CT and VT are in
general incomparable, as they capture different aspects

reference[Zinkevich, 2003, Zhang et al., 2018][Besbes et al., 2015][Jadbabaie et al., 2015] & this paper[Jadbabaie et al., 2015] & this paperof the environmental changes. Therefore, it is desired toattain an adaptive guarantee, which is able to track theminimum of path-length and temporal variability bounds.
Actually, Jadbabaie et al. [2015] propose a variant of
optimistic mirror descent called adaptive optimistic mirror descent (AOMD),
which achievesa more general rep√
sult of order O( DT + min{ (1 + DT )(1 + CT ), (1 +1/3
DT )1/3 T 1/3 VT }). The term DT is the cumulative deviation of gradients to the predictable sequences, as defined in (1). Note that the regret bound implies the desiredp
1/3
O(min{ T (1 + CT ), T 2/3 VT }) bound since the term
DT is at most O(T ), yet could be tighter when the predictable sequences are in a high quality.
Finally, we would like to point out that Jadbabaie et al.
[2015] achieve the fully adaptive bound by carefully designing a doubling trick mechanism, which demands theinstantaneous quantities Ct , Vt and Dt at every iteration.
Although Dt can be computed directly, the acquisition of
Ct , and Vt requires solving optimization problems. Particularly, in order to calculate the temporal variability Vt ,a non-convex problem of supx∈X |ft (x) − ft−1 (x)| will
be involved at each iteration, which is time-consuming,
even employing the concave-convex procedure [Yuilleand Rangarajan, 2003] to solve this difference of convex
functions programming. Our paper proposes a simple
online algorithm that is able to achieve the same regret
guarantee with Jadbabaie et al. [2015], yet is much more
efficient to implement. We list the comparisons of existing
dynamic regret bounds for convex functions in Table 1.

3

THE PROPOSED ALGORITHM

In this section, we propose our algorithm, which enjoys
a fully adaptive bound without involving burdensome
computations for non-convex problem solving. To achieve
this goal, we face the following two challenges:• how to incorporate the niceness of environments(DT ) in the dynamic regret analysis?
• how to make the algorithm adapt to various regularities (VT , CT ) and track the best of them?
To address the first problem, similar to [Jadbabaie et al.,2015], we start with the optimistic mirror descent (OMD)
algorithm [Rakhlin and Sridharan, 2013], which performs

an extra gradient step to update the model with the predictable sequences {Mt }Tt=1 ,x
bt+1 = arg min ηt h∇ft (xt ), xi + DR (x, x
bt ),
x∈X

xt+1 = arg min ηt+1 hMt+1 , xi + DR (x, xbt+1 ),(5)

Lemma 2. Under the same condition in Lemma 1,
running OMD with the fixed step size η =p(C1 + C2 dT /∆e)/(1 + DT ) satisfies
RegdT ≤p
(1 + DT )(C1 + C2 dT /∆e) + 2∆VT ,x∈X

where xbt+1 is an intermediate output and xt+1 is the final
decision at iteration t + 1. The notation DR (·, ·) refers to
the Bregman divergence with respect to the convex function R : X 7→ R. By setting R(·) as a 1-strongly
p convex function and setting ηt = Rmax · min{1,
Dt−2 +p
−1
Dt−1}, Rakhlin and Sridharan [2013] show thatOMD enjoys the following static regret,p
RegsT ≤ 4Rmax ( DT + 1),
2
where Rmax
= supx,y∈X DR (x, y) and Dt is the empiriPt
cal version of DT as Dt = s=1 k∇fs (xs ) − Ms k2∗

OMD algorithm can be seen as a variant of online mirror descent with an additional update guessing about thegradient of the next iteration. This framework provides away to incorporate the niceness of the environments. For
example, the learner can set Mt = ∇ft−1 (xt−1 ) when
the online functions are known to vary gradually, which
recovers the update scheme of Chiang et al. [2012].
In the following, we present the dynamic regret bounds
for variants of OMD in terms of different regularities.
3.1

DYNAMIC REGRET WITH NICENESS

Path-length Bound. We first show that by running OMDwith a fixed step size, we can obtain a dynamic regretbound relative to CT and DT .
Lemma 1. When R(·) is a 1-strongly convex function,
running OMD with any fixed step size η > 0 satisfies
RegdT ≤

ηDT
R2 + γCT
+ max
,
2
2η

provided DR (x, z)−DR (y, z) ≤ γkx−yk, ∀x, y, z ∈ X .
This lemmap implies that the dynamic regret of OMD is at
most O( p(1 + CT )(1 + DT )) by setting the step size as
∗
2
ηpath
= (Rmax+ γCT )/(1 + DT ). However, the optimal tuning is infeasible as quantities of CT and DT are
unknown in advance. The standard doubling trick technique is not applicable due to the non-monotone behaviorof the step size. Different from the special doubling mechanism used in AOMD [Jadbabaie et al., 2015], we gridsearch the optimal step size, which will be described in
the next subsection.
Temporal Variability Bound. The OMD algorithm witha fixed step size also enjoys the temporal variability bound,which is shown as the following lemma.

which holds for any parameter√ ∆ ∈ [T ]. The constants2
are C1 = Rmax
and C2 = γ 2Rmax .
Note that the parameter ∆ can be interpreted as the restarting period, similar to the restarted OMD proposed by Besbes et al. [2015]. Actually, OMD with a fixed step size
can be regarded as a kind of restarted OMD. The difference is that we here have only one parameter to specify(η depends on ∆), while the restarted OMD of previous
studies needs to set two parameters. In the dynamic regret
analysis, we will exploit this key fact.
According to Lemma 2, by setting ∆∗ = (C2 )2/3 (1 +−2/3
1/3
DT )1/3 (1) and running OMD with
p + T ) VT∗
ηvar = (C1 + C2 dT /∆∗ e)/(1 + DT ), we can obtain
1/3
an O((1 + DT )1/3 T 1/3 VT ) dynamic regret bound1 .
However, the obstacle is that the optimal ∆∗ requires
the knowledge of VT , which is also unknown in advance.
3.2

ADAPTIVE BOUND

Until now, we have separately incorporated the nicenessof environments (DT ) with various regularities (CT andVT ) in the dynamic regret analysis. There are still two
steps to obtain an adaptive bound: (i) tuning the learning∗∗parameters ηpathand ηvar; (ii) designing a mechanism totrack the minimum of the regularities CT and VT .
Inspired by the recent works [van Erven and Koolen, 2016,
Zhang et al., 2018, Zhao et al., 2020], we adopt the online
ensemble to tune the unknown step size and track the best
regularity simultaneously. Our approach is essentially an
ensemble method [Zhou, 2012]. Concretely, we initiate
multiple base algorithms, each running an OMD witha specific learning parameter, and then employ a master
algorithm to aggregate their predictions. We show that the
aforementioned goals can be handled in this frameworkwith a carefully designed master algorithm to search over
the OMDs with multiple step sizes.
Tuning Parameters. We first deal with the step size
issue on the path-length
p bound. The optimal step size∗
2parameter is ηpath= (Rmax+ γCT )/(1 + DT ), since
the quantities of terms CT and DT are upper bounded,
we can specify a pool Ppath containing the optimal one
and search over the pool to identify it.
1

The parameter ∆ is constrained in [T ]. We show in thee = max{1, min{T, ∆∗ }},proof of Theorem 2 that by setting ∆dynamic regret in the similar order is achievable.

Concretely, as a consequence of the boundedness of Xin√ terms of Bergman divergence, we have kx − yk ≤2Rmax√, for all x, y ∈ X , which leads to the fact
CT ≤ 2Rmax T . Meanwhile, assuming the gradientand predictable sequence are bounded by G, then theterm DT is bounded by 4G2 T . Thus, we have2
ηL = √

pRmax∗≤ ηpath≤ Rmax (1 + γT ) = ηH .
1 + 4G2 T

Then, we can specify a parameter pool in the range of[ηL , ηH ], and run several OMDs with the parameters in
the pool. Specifically, the parameter pool is constructedwith a logarithmic grid asno2i−1 Rmax| i ∈ [Npath ] ,Ppath = ηi = √1 + 4G2 T
where Npath = d 12 log((1 + γT )(1 + 4G2 T ))e + 1. By
the construction of Ppath , we can see that there exists a∗∗
parameter η 0 ∈ Ppath satisfying ηpath/2 ≤ η 0 ≤ ηpath.
Hence, once the output of the algorithm with the parameter p
η 0 is selected as the final decision, the regret bound ofO( (1 + DT )(1 + CT )) is achievable.
In the previous study [Zhang et al., 2018], Hedge algorithm [Littlestone and Warmuth, 1994] is a common choice for the master algorithm. Denoting xit
by prediction of the base algorithm running with step
size ηi , the Hedge algorithm combines the bases byitheir
P weightsi wt iand output the finali decision xt+1 =i∈[Npath ] wt+1 xt+1 . The weight wt+1 is updated according to the previous performance of base algorithms
exp(−Fti ),ii∈[Npath ] exp(−Ft )

i
wt+1
=P

Pt
where Fti = s=1 ft (xit ) is the cumulative loss of thei-th base algorithm at iteration t and  > 0 is the step sizeof the Hedge algorithm.
The Hedge algorithm ensures
to track any base algorithm√with regret at most O( T ln N ). Thus, by taking Hedge
as the master and OMDs with parameter pool Ppath asbase algorithms, we can obtain the path-length bound,p√RegdT ≤ O T + (1 + CT )(1 + DT ) .
Following a similar argument, we can derive the dynamic
regret bound in terms of temporal variability without
knowing the quantities of VT . Since the parameter ∆is constrained in [T ], we havep
C + C2∗√ 1≤ ηvar≤ (C1 + C2 T ).
2
1 + 4G T
2

Without loss of generality, we assume Rmax > 1.

Thus, we can specify the parameter poolon2i−1 (C1 + C2 )| i ∈ [Nvar ] ,Pvar = ηi = √1 + 4G2 T∗
to searchηvar, where Nvar = the optimal parameter(C1 +C2 T )(1+4G2 T )1
e + 1. We should notice thatd 2 log
C1+C2

since Lemma 2 holds only for ∆ ∈ [T ], what we search
e = max{1, min{T, ∆∗ }}, which can also
is actually ∆yield the following dynamic regret bound√
1/3
RegdT ≤ O T + max{(1 + DT )1/3 T 1/3 VT , VT } .
Although an additional term VT is introduced due tothe constraint of the feasible interval length pool, it canbe eliminated when aggregating the temporal variability
bound with the path-length bound.
Aggregating Base Algorithms. We can run SN =Npath + Nvar OMDs with the pool P = Ppath Pvar
and use Hedge to combine them. The scheme ensures thefollowing dynamic regret guarantee.
Theorem 1. When the predictable sequences satisfy
kMt k∗ ≤ G for all t ∈ [T ], and R(·) is 1-strongly convex, running Hedge as the master with N OMDs as basealgorithms with the pool P satisfies√
RegdT ≤ O( T + min{RC , RV }),(6)
where RC = (1 + DT )(1 + CT ) and RV = (1 +1/3
DT )1/3 T 1/3 VT , provided DR (x, z) − DR (y, z) ≤γkx − yk, ∀x, y, z ∈ X .
Remark 1. Since DT is at most O(T ), the dynamic rep
1/3
gret is bounded by O(min{ T (1 + CT ), T 2/3 VT }),which successfully tracks the minimum of various regularities including path-length and temporal variability.
3.3

FULLY ADAPTIVE BOUND

Note that Theorem 1 is not fully adaptive√ in the sensethat it suffers an extra term of O( T ) aside fromO(min{RC , RV }). The former term will override the
DT term in the latter one, which makes the bound cannot
fully exploit the niceness of environments, for instances,when the predictable sequence is in a high quality. This
inadequacy comes from the master algorithm. To see this,we can decompose the dynamic regret RegdT as,TX

ft (xt ) −

t=1

|

T
X

ft (xit ) +t=1√
O( T ){zTX

ft (xit ) −

t=1

}

|

T
X

ft (x∗t ),

t=1

{z

O(min{RC ,RV })}which holds for any base algorithm indexed by i ∈ [N ].
The first term is the regret of the master algorithm, while

Algorithm 1 Master Algorithm

Algorithm 2 OMD (Base Algorithm)

Input: step size , parameter pools P
1: Initiate N base algorithms S = {Si | i ∈ [N ]} byrunning Algorithm 2 with each step sizeηi ∈ P
2: Initialize: Li0 = 0 for all i ∈ [N ], and receive M1
3: for t = 1 to T do
4:
Receive xitP
from base and update weights by (9)5:Play xt = i∈[N ] wti xit
Observe the function ft (·), query the gradient6:∇ft (xt ) and receive Mt+1
7:
Update Lit = Lit−1 + h∇ft (xt ), xit − xt i
8:Send ∇ft (xt ) and Mt+1 to base algorithms
9: end for

Input: step size ηi ∈ P
1: Let xi1 be any point in X
2: for t = 1 to T do
Submit xit to the master, then receive the gradient3:∇ft (xt ) and current predictable sequence Mt+1
4:
Prepare the prediction for the next iteration as,

the second√ is the dynamic regret of the base algorithm.
The O( T ) term comes only from the master algorithm
regret. Thus, to derive a fully adaptive bound, we require
to substitute Hedge by one that can exploit the niceness.

The rationale behind is that mit is the guess about ft (xit ),which can be substituted by the linearized surrogate loss`t (xit ) = h∇ft (xt ), xit − xt i.3 Thus, following similar
spirit, it is natural to approximate mt as (8), since Mt isa guess about ∇ft (xt ). By reducing the common term
hMt+1 , xt+1 i, the weight update procedure with the linearized surrogate loss `t (x) and mt becomes,
i
wt+1∝ exp −(Lit + hMt+1 , xit+1 i) ,(9)

To incorporate DT in the master regret, our initial idea is
to use optimistic Hedge [Rakhlin and Sridharan, 2013] toaggregate predictions from the N base algorithms xt+1 =PNii
i=1 wt+1 xt+1 with the weight update procedurei
wt+1∝ exp − (Fti + mit+1 ) ,(7)
where the optimism mit+1 can be seen as a guess about
the loss suffered by the i-th base algorithm at iterationt + 1, and enjoys the following regret guarantee [Chiang
et al., 2012, Rakhlin and Sridharan, 2013].
Lemma
p 3. By updating the weights as (7) and setting = (ln N + 2)/DT∞ , for any base algorithm indexedby i ∈ [N ], the optimistic Hedge enjoys
TX

hwt , ft i −t=1

where DT∞ =TXx
bit+1 = arg min ηi h∇ft (xt ), xi + DR (x, x
bit ),x∈Xi
xt+1 = arg min ηi hMt+1 , xi + DR (x, x
bit+1 )x∈X

5: end for

Pt
where Lit = s=1 `t (xit ) is the cumulative surrogate loss
for i-th base algorithm. Note that the predictions for basealgorithm xit+1 is achievable at the beginning of iterationt + 1, since its update only requires the information overpast t iterations and Mt+1 .
Let `t be the loss vector taking `t (xit ) as its i-th entry. By
introducing the surrogate loss, we havek`t − mt k∞ = max {h∇ft (xt ) − Mt , xit − xt i}i∈[N ]√(10)≤ 2Rmax k∇ft (xt ) − Mt k∗q
ft (xit ) ≤ 2 (2 + ln N )DT∞ ,

t=1

PT

2
t=1 kft − mt k∞ . With a slight abuse ofNnotation, we denote by ft ∈ R the loss vector sufferedby the N base algorithms, which takes ft (xit ) as its i-th
entry. Similarly, wt ∈ RN is used for the weight vector
and mt ∈ RN is for the optimism vector.

The step size  can be tunned by doubling trick since
the value of DT∞ is monotone in the learning process.
Combining Lemma 3 with aforementioned analysis andthe fact that ft (xt ) ≤ hwt , ft i by Jensen’s inequality,
wep
can derivep a dynamic regret bound in the rate ofO( DT∞ + (1 + CT )(1 + DT )). However, the boundis incompatible, as DT∞ is defined in terms of optimism
mt rather than the accessible predictable sequences Mt .
PT
2
To associate DT∞ =t=1 kft − mt k∞ with DT =PT
2
t=1 k∇ft (xt ) − Mt k∗ , we specify mt with Mt as
mit = hMt , xit − xt i.

(8)where the last inequality holds due to the CauchySchwartz inequality and the boundedness of X . Thus,2
the term DT∞ is bounded by 2Rmax
DT .
By taking the optimistic Hedge with surrogate loss function as the master algorithm, the fully adaptive bound is
obtained immediately. However, a direct combination
would be time-consuming, particularly when the gradient acquisition requires heavy computations since we run
N = O(log T ) base algorithms and have to query the gradients for each one. This can be relieved by additionallyincorporating the surrogate loss function to the base algorithm, where models are updated with ∇`t (xit ) instead of∇ft (xit ). Since ∇`t (xit ) = ∇ft (xit ) for all i ∈ [N ], thetimes of querying gradients are reduced from N to 1 at
3

The regret w.r.t ft (x) is upper bounded by that w.r.t. `t (x)Thus, the online algorithm can learn with `t (x) instead of ft (x).

every iteration. We summarize the master algorithm in Algorithm 1 and the base algorithms, OMD in Algorithm 2.
Theorem 2. Under the same condition of Theorem 1,
running the master algorithm (Algorithm 1) with N base
OMDs (Algorithm 2) satisfiesp
RegdT ≤ O( DT + min{RC , RV }),pwhere RC =(1 + DT )(1 + CT ) and RV = (1 +1/3 1/3 1/3
DT ) T VT .
Theorem 2 is the main result of this paper, whose proof
is provided in Appendix A. We leave proofs of the rest
lemmas and theorems in the supplementary material.
Remark 2. The result in Theorem 2 is the same as the
fully adaptive bound in Jadbabaie et al. [2015]. Comparing with the bound in Theorem
1, the fully adaptive√
one improves the
term
O(
T
)
introducedby the master√
algorithm to O( DT ). The improvement enables the algorithm to exploit niceness of environments, particularly
when high-quality predictable sequences are provided.
3.4

COMPARISON WITH PRECEDING WORK

Both our algorithm and AOMD [Jadbabaie et al., 2015]
are built upon the optimistic mirror descent algorithm.
The main difference is that AOMD tunes the optimal step
size by the doubling trick, which involves a non-convex
program at every iteration and requires burdensome calculations; while our approach avoids the heavy computations by searching over multiple OMDs. Due to theconstruction of the parameter pool, we only introduce
O(log T ) additional OMDs. Besides, by introducing surrogate loss to base algorithms, the acquisition of gradientsis reduced from O(log T ) to 1 at each iteration, which further accelerates the algorithm as the gradient evaluationis arguably the most time-consuming step in OMD.
Meanwhile, since our algorithm does not require the exact
value of regularities CT , it actually ensures a general
dynamic regret bound, which supports the comparison
against any sequence. By specifying the comparators forthe worst case ones {x∗t }Tt=1 as the best fixed decision inhindsight, our result can adjust automatically from thefully adaptive
dynamic bound to the static regret bound√of O( DT ), which facilitates another type of adaptivity.

4

EXPERIMENTS

In this section, we examine the efficacy and efficiencyof our proposal on the matrix regression problem with
the nuclear norm [Bach, 2008]. Empirical studies onclassification tasks are also investigated, and we present
results in the supplementary material due to page limits.

For the matrix regression problem, at iteration t, a sample(Zt , yt ) arrives with predictable sequence Mt , where Zt ∈Rp×q is a feature matrix and yt ∈ R is the label. Thenthe learner makes the prediction Xt ∈ Rp×q and suffers


1 1
2
ft (Xt ) =(yt − Tr(hZt , Xt i)) + bkXt knu ,a 2
where a, b > 0 are constants and k · knu is the nuclear
norm, defined as the sum of singular values of the matrix.
Contenders. To verify the efficiency of our algorithm,
we compare our method with AOMD and the vanilla
OMD with the static regret guarantee. We set R(x) =1
2
2 kxkF for both algorithms, where k·kF is the Frobenius
norm. For AOMD, we use the concave-convex procedure
to handle the non-convex program, which is solved by asequence of quadratically constrained quadratic program.
Setting. All contenders are compared in dynamic environments, where the potential optimal decision changes
abruptly. Specifically, we consider a 3-stage scenariocontaining 2000 iterations in each iteration. Denotingby X∗k the potentially best decision for k-th stage, thelabel is assigned as yt = Tr(hZt , X∗k i) + ν, where thedata point Zt is randomly sampled from [−1, 1]20×20 andν ∼ N (0, 10) is the random Gaussian noise.
Meanwhile, to see the effectiveness of our algorithm in
exploiting the niceness of environments. We simulate predictable sequences as Mt = λ · ∇ft (xt ), where λ ∈ [0, 1]
is a parameter adjusting the quality of the predictable sequence between the ideal case where Mt = ∇ft (xt ) (i.e.,
DT = 0) and the basic case where Mt = 0. A larger λimplies a higher quality of the predictable sequences.
Results. We focus on the efficacy first. Figure 1(a)shows the mean and standard deviation of instantaneous
loss over a moving time window of 100 iterations when
λ = 0.4. We can see that both AOMD and our approach
perform better than the vanilla OMD, which validates theadvantage of adaptive algorithms. It is also interesting to
notice that AOMD converges better in the stationary period than ours. The reason might be that AOMD runs withthe fixed step size until the doubling condition is satisfied,
while our method maintains multiple step sizes, where theprice has to pay for hedging the non-stationarity. Besides,
Figure 1(b) presents comparisons on the running time ina logarithmic scale, where our method (24 seconds) isslightly slower than vanilla OMD but significantly fasterthan AOMD (around 6 hours), which validates the efficiency of our method. Last, Figure 1(c) reports thatthe performance of our method improves with better predictable sequences, which shows that it can efficiently
and adaptively exploit the niceness of environments.

1500
1250
1000
750
500
250
0

1400

104

instantaneous loss

OMD
AOMD
Ours

1750

running time

instantaneous loss

2000

103
102
101
100
10

OMD
AOMD
Ours

−1

10−2
1000 2000 3000 4000 5000 6000

1000
800
600
400
200
0

1000 2000 3000 4000 5000 6000

iterations

λ=0
λ = 0.2
λ = 0.4
λ = 0.6
λ = 0.8

12001000 2000 3000 4000 5000 6000

iterations

iterations(a) Comparison on instantaneous loss(c) Different qualities of Mt(b) Comparison on running time

Figure 1: The dynamic regret divided by iteration of three methods with the quality of hint varying from poor to ideal

5

CONCLUSION

where the first term is regret of the master algorithm while
the second dynamic regret of the base algorithm.

In this paper, we design a simple algorithm enjoying thefully adaptive bound in Jadbabaie et al. [2015], which
achieves the minimizer of previous results in terms of different regularities CT , VT and can benefit from the niceness of environments measured by DT . By employing theonline ensemble and designing a new master algorithm,
our algorithm avoids solving the non-convex program andis more computationally efficient. Experiments validate
the effectiveness and efficacy of our proposed algorithm.

As for the master regret, our algorithm runs a new variantof optimistic Hedge, where the loss suffered by each basealgorithm is `t (xit ) = h∇ft (xt ), xit − xt i and predictablesequences mit = hMt , xit − xt i are offered. Thus, due toLemma 3 and the argument in (10), for any base algorithm
indexed by i and each iteration t, we have`t (xt ) − `t (xit ) =X

wti `t (xit ) − `t (xit )i∈[N ]rAcknowledgements≤ 2Rmax

This research was supported by the National Key
R&D Program of China (2018YFB1004300) and NSFC
(61921006). We are grateful for the anonymous reviewers
for their helpful comments.

A

PROOF OF THEOREM 2

Proof. In this section, we first present the proof of thepath-length bound, followed by that of the temporal variability bound. The combination of these two types ofresults implies the fully adaptive bound in Theorem 2.
Path-length Bound. First, we can see that the dynamic
regret w.r.t the original loss ft (x) can be bounded by thatof the surrogate loss `t (x) = h∇ft (xt ), x − xt i asTX

ft (xt ) −

t=1

T
X

ft (x∗t ) ≤

t=1

T
X

`t (xt ) −

t=1

T
X

`t (xt ) −

t=1

|

T
X

`t (xit ) +

t=1

{z

Reg-Mas(i)TX`t (x∗t ),

t=1`t (xit ) −

t=1

}

|

T
X

XT
t=1

k∇ft (xt ) − Mt k2∗

Summing over T iterations, we obtain
Reg-Mas(i) ≤ 2Rmaxp(4 + 2 ln N )DT .

Then, we proceed to analyze the base regret for pathlength bound. The optimal
step size for the path-lengthp∗2bound is ηpath=(Rmax+ γCT )/(1 + DT ). Dueto the construction of Pη , there must exist a base algorithm indexed by p ∈ [N ], whose step size satisfies
∗
∗
ηpath
/2 ≤ ηp ≤ ηpath. Therefore, for the p-th base algorithm, by applying Lemma 5 in the supplementary material, a counterpart of Lemma 1 incorporating the surrogate
loss function, we know that the base regret is bounded by
ηp DT
R2 + γCT
+ max
2
2ηp
∗
2
ηpath
DT
R
+ γCT
≤
+ max∗
2ηpath
3p2(1 + DT )(γCT + Rmax
=
).
|2
{z
}
Path-Base

Reg-Base(p) ≤where the inequality holds due to the Jensen’s inequality
ft (xt ) − ft (x∗t ) ≤ h∇ft (xt ), xt − x∗t i and the fact that`t (xt ) = 0. Then, for any base algorithm indexed byi ∈ [N ], we can decompose the dynamic regret asTX(4 + 2 ln N )`t (x∗t ) .

Choosing the p-th base algorithm as the intermediate termin the decomposition, we obtain the path-length bound as,

t=1

{z

Reg-Base(i)}RegdT ≤ 2Rmaxp(4 + 2 ln N )DT + Path-BaseTemporal Variability Bound. We first note that the argument in the proof of path-length bound does not directly
apply for proving the temporal variability bound, due tothe introduction of the surrogate loss. Specifically, previous arguments canP
only yield a temporal variability boundTin terms of VT` = t=2 supx∈X |`t (x)−`t−1 (x)|, whichis hard to be converted to the desired VT w.r.t. the originalfunction ft . To address the difficulty, we decompose thedynamic regret as follows.
dT /∆edT /∆eX X

X X

RegdT =ft (xt ) −i=1 t∈Ii

{z

}
(11)

dT /∆edT /∆eX X+

ft (x∗Ii )term Aft (x∗Ii ) −ft (x∗t ),i=1 t∈Ii

i=1 t∈Ii

|

X X

{z

}

term B

where Ii = [si , ei ] is the i-th interval with the length∆, and si = (i − P
1) · ∆ + 1, ei = i · ∆. Notationx∗Ii = arg minx∈X t∈Ii ft (x) refers to the best fixed
decision in interval Ii .
The term A is the regret of learner’s decisions comparing to the best decisions over consecutive intervals w.r.t.
the original loss, which can be bounded by that of thesurrogate loss by the Jensen’s inequality asterm A ≤dT /∆edT /∆eX X

X X

i=1 t∈Ii`t (xt ) −

1/3

.

e
• Casep 2 (∆∗ < 1): by setting ∆ = 1 and the fact
C2 (1 + DT )(1 + T ) < VT , we havepp
Var-Base ≤ C1 (1 + DT ) + 2(1 + C2 / C2 )VT .

Although the temporal variability bound behaves differently in various cases, we can aggregate it with the pathlength bound to yield the desired regret bound.
Combining Base Algorithms. Our algorithm enjoys
both path-length and temporal variability bound, namely,p
RegdT ≤ 2Rmax (4 + 2 ln N )DT(14)+ min{Path-Base, Var-Base}.
We show that (14) actually implies the following claimpp
RegdT ≤ O DT ln N + min{ (1 + DT )(1 + CT ),1 
11(1 + DT ) 3 (1 + T ) 3 VT3 } ,(15)which is proved by considering the following three cases.
1`t (x∗Ii ).

i=1 t∈Ii

As shown by Lemma 6 in the supplementary material, theabove inequality can be further bounded bypterm A ≤ 2Rmax (4 + 2 ln N )DT(12)p+ 2 (1 + DT )(C1 + C2 dT /∆e),for any parameter ∆ ∈ [T ]. As for term B, following thesame argument in Besbes et al. [2015], we ensure thatterm B ≤ 2∆VT .

2/3+ 2C2 (1 + DT )1/3 (1 + T )1/3 VTe• Case 3 (∆∗ ≥√ T + 1): by setting ∆ = T and thefact that : C2 1 + DT ≥ (1 + T )VT , we haveppp
Var-Base ≤ ( C1 + 2C2 + 2 2C2 ) 1 + DT .

i=1 t∈Ii|e = ∆∗ , we have
• Case 1 (∆∗ ∈ [T ]): by setting ∆p
Var-Base ≤ C1 (1 + DT )(13)

Note that here we can achieve a temporal variability term VT w.r.t. the original function ft . Come wherebining (12), (13) and setting ∆ = ∆e∆= max{1, min{T, (C2 )2/3 (1 + DT )1/3 (1 +T )1/3 VT −2/3 )}, we can obtain thatp
RegdT ≤ 2Rmax (4 + 2 ln N )DTq
e + 2∆Ve T.
+ 2 (1 + DT )(C1 + C2 dT /∆e)|{z}
Var-Basee rather than ∆∗ ,Since what we are searching is actually ∆we discuss the result in the following three cases.

• Case 1 (∆∗ ∈ [T ]): Var-Base = O((1 + DT ) 3 (1 +
1
3

1
3

T ) VT ), so (14) and (15) are in the same order.
• Case 2 (∆p∗ < 1): Var-Base = O(VT ), since
VT > C2 (1 + DT )(1 + T ). Combining with the√e Tfact CT ≤ 2Rmax T , we have Path-Base ≤ CVewhere C is a constant. Therefore, (14) is at mostppO DT ln N + min{ (1 + DT )(1 + CT ), VT }pp
= O DT ln N + (1 + DT )(1 + CT ) ,pwhich implies (15) as VT & (1 + DT )(1 + T ).
√• Case 3: (∆∗ ≥ T + 1): C2 1 + DT ≥ (1 + T )VT .
In this case, (15) becomesp1
1
1
RegdT ≤ O DT ln N + (1 + DT ) 3 (1 + T ) 3 VT3p= O( DT ln N ).
√Since Var-Base= O( 1 + DT ), (14) becomes√
RegdT ≤ O( DT ln N ), which implies (15).
Notice that we treat the double logarithmic factors in T as
constants, following previous studies [Luo and Schapire,
2015, Adamskiy et al., 2016].
We complete the proof of the fully adaptive bound in
Theorem 2 by combining all above three cases.

References
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, pages 415–424, 2008.
D. Adamskiy, W. M. Koolen, A. V. Chernov, and V. Vovk.
A closer look at adaptive regret. Journal of Machine
Learning Research, 17:23:1–23:21, 2016.
D. Baby and Y.-X. Wang. Online forecasting of totalvariation-bounded sequences. In Advances in Neural Information Processing Systems 32, pages 11071–11081,
2019.
F. R. Bach. Consistency of trace norm minimization.
Journal of Machine Learning Research, 9:1019–1048,
2008.
O. Besbes, Y. Gur, and A. J. Zeevi. Non-stationary
stochastic optimization. Operations Research, 63(5):1227–1244, 2015.
X. Chen, Y. Wang, and Y.-X. Wang. Non-stationary
stochastic optimization under Lp,q -variation measures.
Operations Research, 67(6):1503–1782, 2019.
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu,
R. Jin, and S. Zhu. Online optimization with gradualvariations. In Proceedings of the 25th Conference On
Learning Theory, pages 6.1–6.20, 2012.
J. Gama, I. Zliobaite, A. Bifet, M. Pechenizkiy, and
A. Bouchachia. A survey on concept drift adaptation.
ACM Computing Surveys, 46(4):44:1–44:37, 2014.
E. Hazan. Introduction to online convex optimization.
Foundations and Trends in Optimization, 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, pages 57–68, 2008.
E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret
algorithms for online convex optimization. Machine
Learning, 69(2-3):169–192, 2007.
A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online optimization : Competing with dynamic
comparators. In Proceedings of the 18th International
Conference on Artificial Intelligence and Statistics,
pages 398–406, 2015.
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,
pages 1286–1304, 2015.

A. Mokhtari, S. Shahrampour, A. Jadbabaie, andA. Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on
Decision and Control, pages 7195–7201, 2016.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference On Learning Theory, pages 993–1019, 2013.
S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107–194, 2012.
M. Sugiyama and M. Kawanabe. Machine Learning in
Non-stationary Environments: Introduction to Covariate Shift Adaptation. MIT Press, 2012.
T. van Erven and W. M. Koolen. Metagrad: Multiple
learning rates in online learning. In Advances in Neural
Information Processing Systems 29, pages 3666–3674,
2016.
T. Yang, L. Zhang, R. Jin, and J. Yi. Tracking slowly
moving clairvoyant: Optimal dynamic regret of online
learning with true and noisy gradient. In Proceedings ofthe 33rd International Conference on Machine Learning, pages 449–457, 2016.
A. L. Yuille and A. Rangarajan. The concave-convex
procedure. Neural Computation, pages 915–936, 2003.
L. Zhang, T. Yang, J. Yi, R. Jin, and Z.-H. Zhou. Improved dynamic regret for non-degeneracy functions.
In Advances in Neural Information Processing Systems
30, 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, pages 1330–1340,
2018.
P. Zhao and L. Zhang. Improved analysis for dynamic
regret of strongly convex and smooth functions. ArXiv
preprint, arXiv:2006.05876, 2020.
P. Zhao, X. Wang, S. Xie, L. Guo, and Z.-H. Zhou.
Distribution-free one-pass learning. IEEE Transaction
on Knowledge and Data Engineering, 2019.
P. Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou. Dynamic
regret of convex and smooth functions. ArXiv preprint,
arXiv:2007.03479, 2020.
Z.-H. Zhou. Ensemble Methods: Foundations and Algorithms. CRC Press, 2012.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the20th International Conference on Machine Learning,
pages 928–936, 2003.

Supplementary Material of “A Simple Online Algorithm
for Competing with Dynamic Comparators”

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

Abstract
This is the supplementary material of the manuscript “A Simple Online Algorithm for Competing with
Dynamic Comparators”. In Section A, we present the proofs of path-length and temporal variability bounds.
Then, we provide the proof of Lemma 3 in Section B. Meanwhile, we provide additional experimental results
on classification tasks in Section C. Section D presents the technical lemmas. Notice that the adaptive boundof Theorem 1 can be directly obtained from Theorem 2, since the vanilla Hedge is essentially a special caseof the optimistic Hedge when no predictable sequences are provided.

A

Proofs of Path-length and Temporal Variability Bounds

Before showing the proofs of path-length and temporal variability bounds, we present a general dynamic regret boundfor OMD with the fixed step size, which supports the comparison between learner’s decisions and any sequences{ut }Tt=1 , where ut can be any point in the decision domain X .
Lemma 4. When R(·) is a 1-strongly convex function, running OMD with any fixed step size η > 0 satisfies,
PT
T
T
2
X
X
Rmax
+ γ t=2 kut − ut−1 kηDTft (xt ) −ft (ut ) ≤
+
,
2
2η
t=1
t=1
provided DR (x, z) − DR (y, z) ≤ γkx − yk, ∀x, y, z ∈ X , where ut can be any comparator in the feasible domain X .
Proof of Lemma 1. According to the update procedure of OMD (5) with the fixed step size η and Lemma 8, we havehxt − xbt+1 , ηMt i ≤ DR (bxt+1 , xbt ) − DR (bxt+1 , xt ) − DR (xt , x
bt )

(16)

hb
xt+1 − ut , η∇ft (xt )i ≤ DR (ut , xbt ) − DR (ut , x
bt+1 ) − DR (bxt+1 , x
bt ).

(17)

Each iteration of the dynamic regret can be decomposed as,
ft (xt ) − ft (ut ) ≤ h∇ft (xt ), xt − ut i
= h∇ft (xt ) − Mt , xt − x
bt+1 i + hMt , xt − x
bt+1 i + h∇ft (xt ), x
bt+1 − ut i,
|
{z
} |
{z
} |
{z
}
term Aterm B(18)

term C

where the first inequality holds for Jensen’s inequality. Then, we proceed to bound the each term. First, we can see thatterm A ≤ kxt − x
bt+1 k · k∇ft (xt ) − Mt k∗ ≤

η1k∇ft (xt ) − Mt k2∗ + kxt − x
bt+1 k2 ,
2
2η

(19)

1 2
where the first inequality satisfies due to Hölder inequality and the second holds due to the fact that ab ≤ η2 a2 + 2ηb
for a, b ∈ R and any η > 0. According to (16) and (17), term B and term C can be bounded asterm B ≤1(DR (bxt+1 , xbt ) − DR (bxt+1 , xt ) − DR (xt , x
bt ))
η

(20)

term C ≤1
(DR (ut , xbt ) − DR (ut , x
bt+1 ) − DR (bxt+1 , x
bt ))
η

(21)

Due to the strong convexity of regularizer R, we have DR (x, y) ≥ 12 kx − yk2 for any x, y ∈ X [Mohri et al., 2018].
Therefore, by plugging (19), (21) and (20) into (18), we obtain thatft (xt ) − ft (ut ) ≤η1k∇ft (xt ) − Mt k2∗ + kxt − x
bt+1 k2
2
2η


1
1
1
2
2
DR (ut , xbt ) − DR (ut , x
bt+1 ) − kb
xt+1 − xt k − kxt − x
bt k .
+
η2
2

Summing over the index from t = 1 to T , we haveTX

ft (xt ) −

t=1

T
X

ft (ut ) ≤

t=1

≤

T
X
DR (ut , xbt ) − DR (ut , x
bt+1 )
η
DT +
2
η
t=1
T
−1
2
X
η
DR (ut+1 , x
bt+1 ) − DR (ut , x
bt+1 ) Rmax
DT +
+
2
η
η
t=1

Under the condition that DR (x, z) − DR (y, z) ≤ γkx − yk, ∀x, y, z ∈ X , we can further bound the above inequality as
PT
T
−1
2
2
X
+ γ t=2 kut − ut−1 kRmax
γkut+1 − ut k Rmaxηη+
≤ DT +,ft (xt ) −ft (ut ) ≤ DT +
2
η
η
2
η
t=1
t=1
t=1

T
X

T
X

which completes the proof.
Since the base algorithm that we run is Algorithm 2, which is the OMD incorporating surrogate loss function, we offer
a counterpart of Lemma 4 for these base algorithms.
Lemma 5. When R(·) is a 1-strongly convex function, the i-th base algorithm running Algorithm 2 with a fixed step
size ηi enjoys
PT
T
T
2
X
X
Rmax
+ γ t=2 kut − ut−1 k
ηi D Ti`t (xt ) −`t (ut ) ≤
+
,
(22)
2
2ηi
t=1
t=1
provided DR (x, z) − DR (y, z) ≤ γkx − yk, ∀x, y, z ∈ X , where ut can be any comparator in the feasible domain X .
Proof of Lemma 5. The proof of Lemma 5 is almost the same with that of Lemma 4 as we can just substitute theprediction xt with xit and x
bt with x
bit . First, according to the update procedure of OMD with the surrogate loss, we candecompose each iteration of the dynamic regret following (18),`t (xit ) − `t (ut ) ≤ h∇ft (xt ) − Mt , xit − x
bit+1 i + hMt , xit − x
bit+1 i + h∇ft (xt ), x
bit+1 − ut i,
|
{z
} |
{z
} |
{z
}
term Aterm B(23)

term C

where term A, term B and term C can be bounded by,
ηi1k∇ft (xt ) − Mt k2∗ + kxit − x
bit+1 k222η1
term B ≤DR (bxit+1 , xbit ) − DR (bxit+1 , xit ) − DR (xit , x
bit )
ηi

1
term C ≤DR (ut , xbit ) − DR (ut , x
bit+1 ) − DR (bxit+1 , xbit )ηiterm A ≤

(24)
(25)
(26)

By plugging (24), (26) and (25) into (23) and the fact that DR (x, y) ≥ 12 kx − yk2 for any x, y ∈ X , we obtain`t (xt ) − `t (x∗t ) ≤ηi1k∇ft (xt ) − Mt k2∗ +kxi − xbit+1 k2
2
2ηi t


1 i
1
1
DR (ut , xbit ) − DR (ut , x
bit+1 ) − kb
xt+1 − xit k2 − kxit − x
bit k2 .
+ηi22Summing over T iterations and following the same argument in the proof of Lemma 4, we can obtain the dynamic
regret bound
PT
T
T
2
X
X
Rmax
+ γ t=2 kut − ut−1 k
ηi D Ti+,(27)`t (xt ) −`t (ut ) ≤
2
2ηi
t=1
t=1
which completes the proof.
A.1

Proof of the Path-length Bound (Lemma 1)

Proof of Lemma 1. Lemma 1 can be seen as a corollary of Lemma 4. We can complete the proof by setting thecomparator ut = x∗t .
A.2

Proof of Temporal Variability Bound (Lemma 2 and Lemma 6)

In this section, we first derive the temporal variability bound for OMD with fixed step size (Lemm 2), followed by the
analysis on the our algorithm where optimistic Hedge is employed to aggregate multiple OMDs running on surrogate
loss (Lemma 6).
Proof of Lemma 2. First, we can decompose the dynamic regret RegdT as,
RegdT =T
X

T
X

ft (xt ) −|ft (ut ) +

t=1

t=1

{z

term AT
X

T
X

ft (ut ) −

t=1

}

|

ft (x∗t ) .

(28)

t=1

{z

}

term B

Since ut can be any comparator in the feasible set, we can specify {ut }tt=1 as sequences changing every ∆ ∈ [T ]iterations. Concretely, denoting by Ii = [si , ei ] the i-th interval with the length ∆,P
where si = (i − 1) · ∆ + 1 andei = i · ∆, for all t ∈ Ii , we specify ut as the best fixed decision x∗Ii = arg minx∈X t∈Ii ft (x) of the corresponding
interval Ii .
In such a case, according to Lemma 4, term A is bounded by√2
Rmax+ γ 2Rmax dT /∆eηDT+,term A ≤
2
2η

(29)

since the sequences {ut }Tt=1 changes at most dT /∆e√ times and the deviation is bounded due to the boundedness of X
in terms of Bergman divergence that kx − yk ≤ 2Rmax , for all x, y ∈ X .
Then we proceed to analyze the term B. By the construction of the comparator sequences {ut }Tt=1 , term B is thedifference between the cumulative loss of best decisions within each interval and that of the worst case comparators,
which can be bounded following the argument in Besbes et al. [2015].
For contentedness, we present the proof here. At first, we first bound this difference on the interval Ii ,X
X
ft (x∗Ii ) −ft (x∗t )
t∈Ii

=

X

t∈Ii

ft (x∗Ii ) −

t∈Ii

≤

X
t∈Ii

X

fsi (x∗si ) +t∈Iift (x∗si ) −

X
t∈Ii

X

fsi (x∗si ) −t∈Ii

fsi (x∗si ) +

X
t∈Ii

X

ft (x∗t )t∈Ii

fsi (x∗t ) −Xt∈Iift (x∗t )

≤ 2∆

X
t∈Ii

sup |ft+1 (x) − ft (x)|,

(30)

x∈X

∗
∗
where the first inequality comes
P from the optimality of xIi over Ii and xsi = arg minx∈X fsi (x). The last inequality
holds as fsi (xt ) − ft (xt ) ≤ t∈Ii supx∈X |ft+1 (x) − ft (x)| for all t ∈ Ii for all x ∈ X . Thus, by summing over all
intervals, we haveterm B ≤ 2∆VT ,By plugging (29) and (30) into (28), we obtain
ηDT
RegdT ≤
2

By setting η =

q

√
2
Rmax
+ γ 2Rmax dT /∆e++ 2∆VT
2η

√
2
(Rmax
+ γ 2Rmax dT /∆e)/(1 + DT ), we obtain thatq√2
+ γ 2Rmax dT /∆e) + 2∆VT ,RegdT ≤ (1 + DT )(Rmax

which completes the proof.
However, the base algorithm we run is Algorithm 2, which incorporates the surrogate loss function in the learning
process. Lemma 2 canbe expanded for analyzing the regret for these base algorithms, as their entemporal variability
PnotT
term becomes VT` = t=2 supx∈X |`t (x) − `t−1 (x)|, which is hard to be converted to the desired VT term in terms oforiginal function ft .
Thus, instead of analyze the dynamic regret of the single base algorithm, as shown in Appendix A of the main paper,
we bound the overall dynamic regret of the whole algorithm, where term A of (11) is bounded as Lemma 6.
Lemma 6. Under the same condition of Theorem 1, running the master algorithm (Algorithm 1) with N base OMDs
(Algorithm 2), we havedT /∆eX X

dT /∆e`t (xt ) −i=1 t∈Ii

X X`t (x∗Ii ) ≤ 2Rmaxp(4 + 2 ln N )DT + 2p(1 + DT )(C1 + C2 dT /∆e),i=1 t∈Ii

holds for any ∆ ∈ [T ]where P
Ii = [si , ei ] is the i-th interval with the length ∆, and si = (i − 1) · ∆ + 1, ei = i · ∆.
Notation x∗Ii = arg minx∈X t∈Ii ft (x) refers to the best fixed decision in interval Ii .
Proof of Lemma 6. First we can decompose the dynamic regret asdT /∆eX X

dT /∆e`t (xt ) −i=1 t∈Ii

X X
i=1 t∈Ii

dT /∆edT /∆e

X X

X X

≤

`t (xt ) −i=1 t∈Ii|`t (x∗Ii )dT /∆eX X`t (xit ) +i=1 t∈Ii{z

Reg-Mas(i)dT /∆e`t (xit ) −i=1 t∈Ii

}

|

X X

`t (x∗Ii )i=1 t∈Ii{z

Reg-Base(i)}for any i ∈ [N ], where the first term is regret of the master algorithm while the second term is the regret of the i-th basealgorithm.
According to Lemma 3, the master regret w.r.t any base algorithm indexed by i can be bounded asp
Reg-Mas(i) ≤ 2Rmax (4 + 2 ln DT ).
As for the regretof base algorithm, according to Lemma 4, by setting ut as the best fixed decision x∗Ii =P
arg minx∈X t∈Ii ft (x) of the corresponding interval Ii , we have
PdT /∆e2
Rmax+ γ i=2 kx∗Ii − x∗Ii−1 k
ηi DT
Reg-Base(i) ≤
+
,
2
2ηi

holds for any i ∈ [N ]. Due to the boundedness of X in terms of Bergman divergence, we have kx − yk ≤for all x, y ∈ X . Thus, the base regret can be further bounded as
√
2
ηi DT
Rmax
+ γ 2Rmax dT /∆e
Reg-Base(i) ≤
+
,
2
2ηi

√

2Rmax ,. Combining Reg-Mas(i) with Reg-Base(i), we havedT /∆edT /∆eX X`t (xt ) −i=1 t∈Ii

X X`t (x∗Ii )i=1 t∈Ii√p
ηi D TR2 + γ 2Rmax dT /∆e≤ 2Rmax 4 + 2 ln DT +
+ max
2
2ηi
∗
∗
satisfiesq
for any i ∈ [N ]. Since ∆ ∈ [T ], there must exist a step size η 0 ∈ P satisfies ηvar
/2 ≤ η 0 ≤ ηvar
, where√∗2
ηvar = (Rmax+ γ 2Rmax dT /∆e)/(1 + DT ) is the optimal tunning. Thus, we can choose the base algorithm0
running with η as the intermediate term, where the dynamic regret can be further bounded by,
dT /∆eX X

dT /∆e`t (xt ) −i=1 t∈Ii

X X`t (x∗Ii )i=1 t∈Ii

√
∗
2
p
DT
+ γ 2Rmax dT /∆e
ηvar
Rmax
≤ 2Rmax 4 + 2 ln DT +
+
∗
2
ηvar
p
p
≤ 2Rmax 4 + 2 ln DT + 2 (1 + DT )(C1 + C2 dT /∆e),which completes the proof.

B

Proof of Lemma 3

For self-containedness, we present the proof of Lemma 3 here, which is a counterpart of Lemma 4 in Rakhlin and
Sridharan [2013a] without exploiting the local norm. Lemma 4 in Rakhlin and Sridharan [2013a] requires the step size
satisfying kft − mt k∞ ≤ 1/4 at any iteration. This limitation can be eliminated based on Theorem 19 in Syrgkanis
et al. [2015] by taking optimistic Hedge as a special case of Optimistic Follow the Regularized Leader (OFTRL).
Proof of Lemma 3. Note that the update procedure of optimistic Hedge is actually the solution of* T+X
wt+1 = arg min 
ft + mt+1 , w + RH (w),
w∈∆N

(31)

t=1

PN
where ∆N ⊆ RN is the probability simplex and RH (wt ) = i=1 wti log wti is a 1-strongly convex function withrespect to k·k1 . The update procedure (31) is known as optimistic FTRL [Rakhlin and Sridharan, 2013a, Syrgkanis
et al., 2015], whose static regret can be bounded by the following lemma.
Lemma 7 (Theorem 19 in Syrgkanis et al. [2015] ). The regret of a player under optimistic FTRL and with respect toany w ∈ ∆N is upper bounded by:TXTln N + 2 X
hft , wt − wi ≤+kft − mt k∞ kwt − w
bt+1 k1 ,

t=1
t=1
PT +1
where wbt+1 = arg minw∈∆N h t=1 ft , wi + RH (w).

(32)

The right hand side of (32) can be further bounded by the stability of the FTRL type algorithm . Since RH is 1-strongly
convex with respect to k·k1 , according to Lemma 9, we havekwt − wbt+1 k1 ≤ kft − mt k∞ .

(33)

Plugging (33) into (32)pand setting w as the vector with i-th entry being 1 and the rest being 0, we complete the proof
with the step size  = (2 + ln N )/D∞ .

CAdditional Experiments

In this section, we offer additional experimental results to further justify the effectiveness and efficiency of our proposal,
where binary classification tasks with squared hinge loss are considered. Specifically, at iteration t, a sample (zt , yt )arrives with predictable sequences Mt , where zt ∈ Rd is the feature vector and yt ∈ {+1, −1} is the label. Then thelearner makes prediction xt and suffers the squared loss ft (xt ) = (1 − yt · hzt , xt i)2 .
Setting. The experimental setup is similar to that in the main paper, where OMD, AOMD and our proposal with
R(x) = 21 kxk22 are compared. We use three classification datasets 1 : IJCNN1, mushroom and svmguide1 to simulate
the non-stationary environments, whose labels flip 9 times over 1200 iterations. All configurations are repeated 5 times
and we normalize the features of the datasets to range from [0, 1] at the beginning of the learning process.
Results. Table 1 and Table 2 report contenders’ cumulative loss and running time in seconds, when predictablesequences of middle quality are provided (λ = 0.4). The results show the same tendency as those in the main paper,
where our proposal achieves comparable performance with AOMD and reduces the computational burden dramatically.
Table 1: Mean and standard deviation of contenders’ cu- Table 2: Mean and standard deviation of contenders’ runmulative loss, where the best algorithms are emphasized ning time in seconds, where the best algorithms are emin bold (paired t-test at 95% significance level)
phasized in bold (paired t-test at 95% significance level)
Dataset

OMD

AOMD

Ours

Dataset

OMD

AOMD

Ours

IJCNN1
svmguide1
mushroom

778 ± 31918 ± 112234 ± 63

583 ± 15720 ± 111968 ± 73

590 ± 17763 ± 111850 ± 99

IJCNN1
svmguide1
mushroom

0.02 ± 0.011
0.02 ± 0.011
0.02 ± 0.013

5541 ± 173
6258 ± 167
5001 ± 171

0.43 ± 0.200
0.27 ± 0.064
0.37 ± 0.070

DTechnical Lemmas

In this section, we first introduce the lemma on the property of Bregman divergence.
Lemma 8 (Beck and Teboulle [2003]). Let X be a convex set in a Banach space B, and regularizer R : X 7→ R be a
1-strongly convex function on X with respect to a norm k·k, and let DR (·, ·) be the Bregman divergence induced by R.
Then, any update of the formx∗ = arg min{ha, xi + DR (x, c)}x∈Xsatisfies the following inequalityhx∗ − d, ai ≤ DR (d, c) − DR (d, x∗ ) − DR (x∗ , c),for any d ∈ X .
Next, the following lemma shows the stability of the FTRL algorithm.
Lemma 9 (Lemma 20 in Syrgkanis et al. [2015]). If w∗ = arg minw∈X hw, F i + RH (w) and w∗0 =arg minw∈X hw, F 0 i + R(w) for a λ-strongly convex regularizer R : W 7→ R with respect to a norm k · k andsome F ∈ Rd and F 0 ∈ Rd . Then we have
λkw∗ − w∗0 k ≤ kF − F 0 k∗ .

References
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization.
Operation Research Letter, 31(3):167–175, 2003.
1

The datasets are downloaded from https://www.csie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/

O. Besbes, Y. Gur, and A. J. Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244,
2015.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. The MIT Press, second edition,
2018.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference On
Learning Theory, pages 993–1019, 2013a.
A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural
Information Processing Systems 26, pages 3066–3074, 2013b.
V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advancesin Neural Information Processing Systems 28, pages 2989–2997, 2015.