Year: 2020

Abstract:
We study the problem of online convex optimization, where a learner makes sequential decisions to minimize an accumulation of strongly convex costs over time. The quality of decisions is given in terms of the dynamic regret, which measures the performance of the learner relative to a sequence of dynamic minimizers. Prior works on gradient descent and mirror descent have shown that the dynamic regret can be upper bounded using the path length, which depend on the differences between successive minimizers, and an upper bound using the squared path length has also been shown when multiple gradient queries are allowed per round. However, they all require the cost functions to be Lipschitz continuous, which imposes a strong requirement especially when the cost functions are also strongly convex. In this work, we consider Online Multiple Mirror Descent (OMMD), which is based on mirror descent but uses multiple mirror descent steps per online round. Without requiring the cost functions to be Lipschitz continuous, we derive two upper bounds on the dynamic regret based on the path length and squared path length. We further derive a third upper bound that relies on the gradient of cost functions, which can be much smaller than the path length or squared path length, especially when the cost functions are smooth but fluctuate over time. Thus, we show that the dynamic regret of OMMD scales linearly with the minimum among the path length, squared path length, and sum squared gradients. Our experimental results further show substantial improvement on the dynamic regret compared with existing alternatives.

heading: 1 INTRODUCTION
text: Online optimization refers to the design of sequential decisions where system parameters and cost functions vary with time. It has applications to various classes of problems, such as object tracking (Shahrampour & Jadbabaie, 2017), networking (Shi et al., 2018), cloud computing (Lin et al., 2012), and classification (Crammer et al., 2006). It is also an important tool in the development of algorithms for reinforcement learning (Yuan & Lamperski, 2017) and deep learning (Mnih et al., 2015).
In this work, we consider online convex optimization, which can be formulated as a discrete-time sequential learning process as follows. At each round t, the learner first makes a decision xt ∈ X , where X is a convex set representing the solution space. The learner then receives a convex cost function ft(x) : X → R and suffers the corresponding cost of ft(xt) associated with the submitted decision. The goal of the online learner is to minimize the total accrued cost over a finite number of rounds, denoted by T . For performance evaluation, prior studies on online learning often focus on the static regret, defined as the difference between the learner’s accumulated cost and that of an optimal fixed offline decision, which is made in hindsight with knowledge of ft(·) for all t:
RegsT = T∑ t=1 ft(xt)−min x∈X T∑ t=1 ft(x).
A successful online algorithm closes the gap between the online decisions and the offline counterpart when normalized by T , i.e., sustaining sublinear static regret in T . In the literature, there are various online algorithms (Zinkevich, 2003; Cesa-Bianchi & Lugosi, 2006; Hazan et al., 2006; Duchi et al., 2010; Shalev-Shwartz, 2012) that guarantee a sublinear bound on the static regret.
However, algorithms that guarantee performance close to that of a static decision may still perform poorly in dynamic settings. Consequently, the static regret fails to accurately reflect the quality of decisions in many practical scenarios. Therefore, the dynamic regret has become a popular metric in recent works (Besbes et al., 2015; Mokhtari et al., 2016; Yang et al., 2016; Zhang et al., 2017), which allows a dynamic sequence of comparison targets and is defined by
RegdT = T∑ t=1 ft(xt)− T∑ t=1 ft(x ∗ t ),
where x∗t = argminx∈X ft(x) is a minimizer of the cost at round t.
It is well-known that the online optimization problem may be intractable in a dynamic setting, due to arbitrary fluctuation in the cost functions. Hence, achieving a sublinear bound on the dynamic regret may be impossible. However, it is possible to upper bound the dynamic regret in terms of certain regularity measures. One of the measures to represent regularity is the path length, defined by
CT = T∑ t=2 ‖x∗t − x∗t−1‖, (1)
which illustrates the accumulative variation in the minimizer sequence. For instance, the dynamic regret of online gradient descent for convex cost functions can be bounded by O( √ T (1 + CT )) (Zinkevich, 2003). 1 For strongly convex functions, the dynamic regret of online gradient descent can be reduced to O(CT ) (Mokhtari et al., 2016). When the cost functions are smooth and strongly convex, by allowing the learner to make multiple queries to the gradient of the cost functions, the regret bound can be further improved to O(min(CT , ST )), where ST represents the squared path length, defined by
ST = T∑ t=2 ‖x∗t − x∗t−1‖2, (2)
which can be smaller than the path length when the distance between successive minimizers is small. All the aforementioned studies require the cost functions to be Lipschitz continuous. However, there are many commonly used cost functions, e.g., the quadratic function that do not meet the Lipschitz condition. In addition, the above works rely on measuring distances using Euclidean norms, which hinders the projection step in gradient descent update for some constraint sets, e.g., probability simplex (Duchi, 2018).
Besides gradient descent, mirror descent is another well-known technique of online convex optimization (Hall & Willett, 2015; Jadbabaie et al., 2015). Mirror descent uses the Bregman divergence, which generalizes the Euclidean norm used in the projection step of gradient descent, thus acquiring expanded applicability to a broader range of problems. In addition, the Bregman divergence is only mildly dependent on the dimension of decision variables (Beck & Teboulle, 2003; Nemirovsky & Yudin, 1983), so that mirror descent is optimal among first-order methods when the decision variables have high dimensions (Duchi et al., 2010). In this work we focus on the mirror descent approach.
In previous works on online mirror descent, the learner queries the gradient of each cost function only once, and performs one step of mirror descent to update its decision (Hall & Willett, 2015; Shahrampour & Jadbabaie, 2017). In this case, the dynamic regret has an upper bound of order O( √ T (1 + CT )), which is the same as that of online gradient descent in (Zinkevich, 2003). In this work, we investigate whether it is possible to improve the dynamic regret when the learner performs multiple mirror descent steps in each online round, while relaxing the Lipschitz continuity condition on the cost functions.
To this end, we analyze the performance of the Online Multiple Mirror Descent (OMMD) algorithm, which uses multiple steps of mirror descent per online round. When the cost functions are smooth and strongly convex, we show that the upper bound on the dynamic regret can be reduced from
1A more general definition of the dynamic regret was introduced in (Zinkevich, 2003), which allows comparison against an arbitrary sequence {ut}Tt=1. We note that the regret bounds developed in (Zinkevich, 2003) also hold for the specific case of ut = x∗t .
O( √ T (1 + CT )) to O(min(CT , ST , GT )), where GT represent the sum squared gradients, i.e.,
GT = T∑ t=1 ‖∇ft(xt)‖2∗, (3)
where ‖.‖∗ denotes the dual norm. The sum squared gradients GT can be smaller than both the path length and squared path length, especially when the cost functions fluctuate drastically over time. In contrast to the aforementioned works, our analysis does not require the cost functions to be Lipschitz continuous. Furthermore, our numerical experiments suggest substantially reduced dynamic regret compared with the best known alternatives, including single-step dynamic mirror descent (Hall & Willett, 2015), online multiple gradient descent (Zhang et al., 2017), and online gradient descent Zinkevich (2003).

heading: 2 ONLINE MULTIPLE MIRROR DESCENT
text: In this section, we describe OMMD and discuss how the learner can improve the dynamic regret by performing multiple mirror descent steps per round. Before delving into the details, we proceed by stating several definitions and standard assumptions.

heading: 2.1 PRELIMINARIES
text: Definition 1: The Bregman divergence with respect to the regularization function r(·) is defined as Dr(x, y) = r(x)− r(y)− 〈∇r(y), x− y〉.
The Bregman divergence is a general distance-measuring function, which contains the Euclidean norm and the Kullback-Leibler divergence as two special cases.
Using the Bregman divergence, a generalized definition of strong convexity is given in (ShalevShwartz & Singer, 2007).
Definition 2: A convex function f(·) is λ-strongly convex with respect to a convex and differentiable function r(·) if
f(y) + 〈∇f(y), x− y〉+ λDr(x, y) ≤ f(x), ∀x, y ∈ X .
Following many prior studies on mirror descent, we assume that the cost functions are λ-strongly convex, where the above generalized strong convexity definition is used. We further assume that the cost functions are L-smooth, and the regularization function r(·) is Lr-smooth and 1-strongly convex with respect to some norm (refer to App. A for definitions). We note that these are standard assumptions commonly used in the literature after the group of studies began by (Hazan et al., 2006; Shalev-Shwartz & Singer, 2007), to provide stronger regret bounds by constraining the curvature of cost functions.
We further make a standard assumption that the Bregman divergence is Lipschitz continuous as follows:
|Dr(x, z)−Dr(y, z)| ≤ K‖x− y‖, ∀x, y, z ∈ X , where K is a positive constant. We note that this condition is much milder than the condition of Lipschitz continuous cost functions required in (Zhang et al., 2017; Mokhtari et al., 2016; Hall & Willett, 2015). There is a notable weakness in such bounds. Since the sequence of cost functions are revealed to the learner, the learner has no control over it. If these cost functions happen to not meet the Lipschitz condition, earlier analyses that require this condition become inapplicable. In this work, we do not require the cost functions to be Lipschitz continuous. Instead, we move the Lipschitz continuity condition from the cost functions to the Bregman divergence to broaden the application of our work. The main benefit of this is that the regularization function and the corresponding Bregman divergence is within the control of the learner. The learner can carefully design this regularization function to satisfy the Lipschitz continuity of the associated Bregman divergence with a small factor. For example, in the particular case of the KL divergence, which is obtained by the choosing negative entropy as the regularization function, on the set X = {x| ∑d i=1 xi = 1;xi ≥ 1 D}, the constant K is of O(logD). Other examples of many widely used Bregman divergences that satisfy this condition are given in (Bauschke & Borwein, 2001).
Algorithm 1 Online Multiple Mirror Descent Input: Arbitrary initialization of x1 ∈ X ; step size α; time horizon T . Output: Sequence of decisions {xt : 1 ≤ t ≤ T}. 1: for t = 1, 2, . . . , T do 2: submit xt ∈ X and receive ft(·) 3: set y1t = xt 4: for i = 1, 2, . . . ,M do 5: yi+1t = argminy∈X {〈∇ft(yit), y〉+ 1αDr(y, y i t)}
6: end for 7: set xt+1 = yM+1t 8: end for

heading: 2.2 ONLINE CONVEX OPTIMIZATION WITH OMMD
text: We consider online optimization over a finite number of rounds, denoted by T . At the beginning of every round t, the learner submits a decision represented by xt, which is taken from a convex and compact set X . Then, an adversary selects a function ft(·) and the learner suffers the corresponding cost ft(xt). The learner then updates its decision in the next round. With standard mirror descent, this is given by
xt+1 = argmin x∈X
{〈∇ft(xt), x〉+ 1
α Dr(x, xt)} (4)
where α is a fixed step size, andDr(·, ·) is the Bregman divergence corresponding to the regularization function r(·). The update in equation 4 suggests that the learner aims to stay close to the current decision xt as measured by the Bregman divergence, while taking a step in a direction close to the negative gradient to reduce the current cost at round t.
OMMD uses mirror descent in its core as the optimization workhorse. However, in contrast to classical online optimization methods, where the learner queries the gradient of each cost function only once, OMMD is designed to take advantage of the curvature of cost functions by allowing the learner to make multiple queries to the gradient in each round. This is especially important when the successive cost functions have similar curvatures. In particular, in order to track x∗t+1 the learner needs to access the gradient of the cost function, i.e.,∇ft+1(·). Unfortunately, this information is not available until the end of round t+ 1. However, if the successive functions have similar curvatures, the gradient of ft(·) is a reasonably accurate estimate for the gradient of ft+1(·). In this case, every time that the learner queries the gradient of ft(·), it finds a point that is likely to be closer to the minimizer of ft+1(·). Hence, it may benefit the learner to perform multiple mirror descent steps in each round.
Thus, the learner generates a series of decisions, represented by y1t , y 2 t , . . . , y M+1 t , via the following updates:
y1t = xt, y i+1 t = argmin y∈X {〈∇ft(yit), y〉+
1 α Dr(y, y i t)}, i = 1, 2, . . . ,M. (5)
Then, by setting xt+1 = yM+1t , the learner proceeds to the next round, and the procedure continues. Note that M is independent of T .
Applying multiple steps of mirror descent can reveal more information about the sequence of minimizers. It can reduce the dynamic regret, but only if the series of decisions in equation 5 helps decrease the distance to the minimizer x∗t+1. Therefore, quantifying the benefit of OMMD over standard mirror descent requires careful analysis on the impact of the fluctuation of ft(·) over time. To this end, we provide an analysis to bound the dynamic regret of OMMD in the next section.

heading: 3 THEORETICAL RESULTS
text: The following lemma paves the way for the proposed analysis on the dynamic regret of OMMD. It bounds the distance of the learner’s future decision from the current optimal solution, after a single step of mirror descent.
Lemma 1 Assume that ft(·) is λ-strongly convex with respect to a differentiable function r(·), and is L-smooth. Single-step mirror descent with a fixed step size α ≤ 1L guarantees the following:
Dr(x ∗ t , xt+1) ≤ βDr(x∗t , xt),
where x∗t is the unique minimizer of ft(·), and β = 1− 2αλ1+αλ .
Lemma 1 is proved in App. B in the supplementary material.
Remark 1. Lemma 1 states that a mirror descent step reduces the distance (measured by the Bregman divergence) of the learner’s decisions to the current minimizer. This generalizes the results in (Mokhtari et al., 2016; Zhang et al., 2017), where similar bounds were derived for online gradient descent when the distance was measured in Euclidean norms. In particular, those results correspond to the special choice of r(x) = ‖x‖22, which reduces the Bregman divergence to Euclidean distance, i.e., Dr(x, y) = ‖x− y‖2. Lemma 1 indicates that the distance between the next decision xt+1 and the minimizer x∗t is strictly smaller than the distance between the current decision xt and the minimizer at round t. This implies that if the minimizers of the functions ft(·) and ft+1(·), which are x∗t and x∗t+1 respectively, are not far from each other, applying mirror descent multiple times enables the online learner to more accurately track the sequence of optimal solutions x∗t .
The succeeding theorems provide three separate upper bounds on the dynamic regret of OMMD, based on path length CT (as defined in equation 1), squared path length ST (as defined in equation 2), and sum squared gradients (as defined in equation 3).
Theorem 2 Assume that r(·) is Lr-smooth and 1-strongly convex with respect to some norm ‖ · ‖ and that the cost functions are L-smooth and λ-strongly convex with respect to r(·). Let xt be the sequence of decisions generated by OMMD with a fixed step size 12λ < α ≤ 1 L and M ≥ d ( 1 2 + 1 2αλ ) logLre mirror descent steps per round. The dynamic regret satisfies the following bound: T∑ t=1 ft(xt)− ft(x∗t ) ≤ ( Kλ 2αλ− 1 (1 + √ LrβM ) (1− √ LrβM ) ) (CT + ‖x∗1 − x1‖).
where β is the shrinking factor derived in Lemma 1, and K is the Lipschitz constant associated with Dr(·, ·).
The proof of Theorem 2 is given in App. C in the supplementary material.
Remark 2. It has been shown in (Hall & Willett, 2015) that single-step mirror descent guarantees an upper bound of O( √ T (1 + CT )) on the dynamic regret for convex cost functions. With that bound, a sublinear path length is not sufficient to guarantee sublinear dynamic regret. In contrast, Theorem 2 implies that OMMD reduces the upper bound to O(CT ) when the cost functions are strongly convex and smooth, which implies that a sublinear path length is sufficient to yield sublinear dynamic regret.
Remark 3. The range of M where the bound in Theorem 2 holds is usually wide. For example, it is M ≥ 3 and M ≥ 5 for the two experiments shown in Section 4.
Theorem 3 Under the same convexity and smoothness conditions stated in Theorem 2, let xt be the sequence of decisions generated by OMMD with a fixed step size α ≤ 1L and M ≥ d ( 1 2 + 1 2αλ ) log 2Lre mirror descent steps per round. For any arbitrary positive constant θ, the dynamic regret is upper bounded by T∑ t=1 ft(xt)− ft(x∗t ) ≤ T∑ t=1 ‖∇ft(x∗t )‖2∗ 2θ + ( LLr + θ 1− 2LrβM )( ST + ‖x∗1 − x1‖2 2 ) .
Theorem 3 is proved in App. D in the supplementary material.
Since the gradient at x∗t is zero if x ∗ t is in the relative interior of the feasibility set X , i.e., ‖∇ft(x∗t )‖ = 0, the above theorem can be simplified to the following corollary.
Corollary 4 If x∗t belongs to the relative interior of the feasibility set X for all t, the dynamic regret bound in Theorem 3 is of order O(ST ).
When the cost functions drift slowly, the distances between successive minimizers are small. Hence, the squared path length ST , which relies on the square of those distances, can be significantly smaller than the path length CT . In this case, Theorem 3 and Corollary 4 can provide a tighter regret bound than Theorem 2.
Theorem 5 Under the same convexity and smoothness conditions stated in Theorem 2, let xt be the sequence of decisions generated by OMMD with a fixed step size α > 12λ . The following bound holds on the dynamic regret:
T∑ t=1 ft(xt)− ft(x∗t ) ≤ α2λ 4αλ− 2 GT .
The proof of Theorem 5 is given in App. E in the supplementary material.
Remark 4. Interestingly, Theorem 5 implies that sublinear dynamic regret can be achieved when the gradient of the cost functions shrink over time. For instance, if ‖∇ft(x)‖∗ = O(1/tγ) for some γ > 0, Theorem 5 guarantees O(T 1−2γ) dynamic regret. This is especially important when the cost functions decrease while the minimizers fluctuate. In this scenario, the path length CT and squared path length ST may grow linearly, whereas diminishing gradients ensure sublinear GT .
Theorem 2, Corollary 4, and Theorem 5, respectively, state that the dynamic regret of OMMD is upper bounded linearly by path length CT , squared path length ST , and sum squared gradients GT . This immediately leads to the following result.
Corollary 6 Under the same convexity and smoothness conditions stated in Theorem 2, the dynamic regret of OMMD with suitably chosen α and M has an upper bound of O(min(CT , ST , GT )).
Remark 5. We note that (Mokhtari et al., 2016) and (Zhang et al., 2017) provide upper bounds of O(CT ) and O(min(CT , ST )), respectively, on the dynamic regret of online gradient descent with single and multiple gradient queries, while (Hall & Willett, 2015) presents an upper bound of O( √ T (1 + CT )) on the dynamic regret of online single-step mirror descent. Corollary 6 shows that OMMD can improve the dynamic regret bound to O(min(CT , ST , GT )). Furthermore, in contrast to these studies, our analysis does not require the cost functions to be Lipschitz continuous.
The quantities Ct, ST , and GT represent distinct aspects of an online learning problem and are not generally comparable. The following example demonstrates the benefit of having multiple upper bounds and taking their minimum. Consider a sequence of quadratic programming problems of the form ft(x) = ‖Atx− bt‖2 over the d-dimensional probability simplex. Assume that for any t ≥ 1, we have the parameter sequence of
At = { diag( 1tp1 , 0, 0, . . . , 0), if t is odd diag(0, 1tp1 , 0, . . . , 0), if t is even,
and b = [ 1tp2 , 1 tp2 , . . . , 1 tp2 ] ′, where p1 and p2 are positive constants such that p2 ≤ p1. In this setting, we observe that CT = O(T ) and GT = O(T 1−p1−p2). Thus, GT can be considerably smaller than CT . On the other hand, it is also possible that CT is smaller than GT in other cases. For example, let At = diag(1/2, 0, . . . , 0) on odd rounds and At = diag(0,−1/2, . . . ,−1/2) , and bt be the unity vector for all t. In this case, we observe that CT = O(1), while the sum gradient scales linearly with time, i.e., GT = O(T ). Thus, neither CT nor GT alone can provide a small regret bound for all cases. Similar examples can be found in comparison between ST and GT but are omitted for brevity.

heading: 4 EXPERIMENTS
text: We investigate the performance of OMMD via numerical experiments in two different learning scenarios (with further experiments presented in App. G in the supplementary material). First, we consider a ridge regression problem on the CIFAR-10 dataset (Krizhevsky, 2009). Then, we study a case of online convex optimization where the difference between successive minimizers diminishes as time progresses. We compare OMMD with the following alternatives: Online Gradient Descent (OGD) (Zinkevich, 2003), Online Multiple Gradient Descent (OMGD) (Zhang et al., 2017), and Dynamic Mirror Descent (DMD) (Hall & Willett, 2015).
In the first experiment, we consider multi-class classification with ridge regression. In this task, the learner observes a sequence of labeled examples (ω, z), where ω ∈ Rd, and the label z, denoting the class of the data example, is drawn from a discrete space Z = {1, 2, . . . , c}. We use the CIFAR-10 image dataset, which contains 5 × 104 data samples. Each data sample ω is a color image of size 32× 32 pixel that can be represented by a 3072-dimensional vector, i.e., d = 3072. Data samples correspond to color images of objects, including airplanes, cars, birds, cats, deer, dogs, frogs, horses, ships, and trucks. Hence, there are c = 10 different classes. For ridge regression, the cost function associated with batch of data samples at round t, i.e., (ω1,t, z1,t), . . . , (ωb,t, zb,t), is given by
f(x, (ωt, zt)) = ‖ωTt x− zt‖22,
where x is the optimization variable, which is constrained by the set X = {x : x ∈ Rd+, ‖ x ‖1= 1}, and (ωt, zt) compactly represents the batch of data samples at round t, i.e., ωt = [ω1,t, ω2,t, . . . , ωb,t]
T and zt = [z1,t, z2,t, . . . , zb,t]T . The goal of the learner is to classify streaming images online by tracking the unknown optimal parameter x∗t . We use the negative entropy regularization function, i.e., r(x) = ∑d j=1 xj log(xj), which is strongly convex with respect to the l1-norm. Then, the mirror descent update in equation 4 leads to the following update:
yi+1t,j = yit,j exp(−α∇ft(yit,j))∑d j=1 y i t,j exp(−α∇ft(yit,j)) , (6)
where xt,j and ∇ft(xt)j denote the j-th component of xt and ∇ft(xt) respectively. The proof of the above closed-form update is given in App. F in the supplementary material. In our experiment, we set batch size to 20 data samples per online round, and set α = 0.1.
In Fig. 1, we compare the performance of OMMD with DMD, OGD, and OMGD in terms of the dynamic regret. We see that the methods based on mirror descent perform better than those based on gradient descent as generally expected. Furthermore, OMMD with M = 10 can reduce the dynamic regret up to 30% in comparison with DMD. The dynamic regret associated with all algorithms grow linearly with the number of rounds. This is because the sequence of minimizers x∗t depend on batches of samples that are independent over time, so that they do not converge. We note that this is common for online optimization in dynamic settings where steady fluctuation in the environment results in linear dynamic regret.
Next, we study the performance of OMMD in solving a sequence of quadratic programming problems of the form ft(x1, x2) = ρ‖x1 − at‖2 + ‖x2 − bt‖2, where ρ is a positive constant, at and bt are time-variant vectors, and the decision variable are x1 ∈ Rd1 , x2 ∈ Rd2 , such that d1 + d2 = d. In our experiment, we set ρ = 10, d1 = 500, and d = 1000. We assume that bt is time-invariant and for all rounds t we have bt = 2, while at satisfies the recursive formula at+1 = at + 1/ √ t with initial value a1 = −1.5. We further set the step size α = 0.03. We use the same regularization function and constraint set as in the previous experiment.
From Fig. 2, we observe that the performance advantage of OMMD is even more pronounced. As time progresses and the difference between the successive cost functions becomes less significant, the difference between the minimizers decreases. In this case, OMMD can significantly improve the performance of online optimization by reducing the gap between the learner’s decisions and the minimizers sequence. In particular, compared with DMD, OMMD with M = 10 reduces the dynamic regret up to 80% after 2500 rounds.

heading: 5 RELATED WORKS
text: The problem of online convex optimization has been extensively studied in the literature since the seminal work of (Zinkevich, 2003). Most prior works study various online algorithms that guarantee a sublinear bound on the static regret (Zinkevich, 2003; Cesa-Bianchi & Lugosi, 2006; Hazan et al., 2006; Duchi et al., 2010; Shalev-Shwartz, 2012). Here we review the most relevant works with a focus on the dynamic regret.

heading: 5.1 DYNAMIC REGRET OF ONLINE GRADIENT DESCENT
text: Dynamic regret was first introduced in (Zinkevich, 2003) for the analysis of online gradient descent, where anO( √ TCT ) bound on the dynamic regret was derived for convex functions. When the learner
has knowledge of the path length beforehand, the dynamic regret can be upper bounded byO( √ TCT )
(Yang et al., 2016). For strongly convex cost functions, the upper bound on the dynamic regret can be reduced to O(CT ) (Mokhtari et al., 2016). The above works make only a single query to the gradient of the cost functions in every round. By allowing the learner to make multiple gradient queries per online round, the regret bound can be improved to O(min(CT , ST )) when the cost functions are smooth and strongly convex (Zhang et al., 2017). The analysis in all aforementioned studies requires the cost functions to be Lipschitz continuous. However, many commonly used cost functions do not satisfy this condition over an unbounded feasible set, e.g., the quadratic function, and even when the feasible set is bounded the Lipschitz factor can be excessively large, especially when the cost functions are strongly convex. Therefore, Lipschitz continuity of the cost functions is not assumed in our analysis. Instead, we move this condition from the cost functions to the Bregman divergence, which the learner can control and design. In addition, the above works rely on measuring distances using Euclidean norms, while the updates with Euclidean distance are challenging for some constraint sets, e.g., probability simplex (Duchi, 2018). It is known that gradient descent does not perform as well as mirror descent, especially when the input dimension is high (Nemirovsky & Yudin, 1983; Beck & Teboulle, 2003).

heading: 5.2 DYNAMIC REGRET OF ONLINE MIRROR DESCENT
text: The dynamic regret of online single-step mirror descent was studied in (Hall & Willett, 2015), where an upper bound of O( √ T (1 + CT )) was derived for convex cost functions. To take advantage of smoothness in cost functions, an adaptive algorithm based on optimistic mirror descent (Rakhlin & Sridharan, 2013) was proposed in (Jadbabaie et al., 2015), which contains two steps of mirror descent per online round. However, different from our work, in that variant the learner is allowed to make only a single query about the gradient. The algorithm further requires some prior prediction of the gradient in each round, which is used in the second mirror descent step. The dynamic regret bound was given in terms of a combination of the path length CT , deviation between the predictions and the actual gradients DT , and functional variation FT = ∑T t=1 maxx∈X |ft(x)− ft−1(x)|. 2 Unfortunately, to achieve this bound, the algorithm requires the design of a time-varying step size that depends on the optimal solution in the previous step, which prevents direct numerical comparison with OMMD. Therefore, in Section 4 we have experimented only with the method of (Hall & Willett, 2015).
All aforementioned works make only a single query to the gradient of the cost functions in every online round. In contrast, in this work, we allow the learner to make multiple gradient queries per round. The learner then uses this information to update its decision via multiple steps of mirror descent. In this way, we show the dynamic regret can be upper bounded linearly by the minimum among the path length, squared path length, and sum squared gradients. Furthermore, as opposed to the aforementioned works, our analysis does not require the cost functions to be Lipschitz continuous.
Finally, there is also recent work in the literature on distributed online mirror descent (Shahrampour & Jadbabaie, 2017). As expected, it is more challenging to achieve performance guarantee in distributed optimization. We focus on centralized online convex optimization in this work.
2We note that the regret bounds derived in (Jadbabaie et al., 2015) is under the same definition of (Zinkevich, 2003).

heading: 6 CONCLUSION
text: We have studied online convex optimization in dynamic settings. By applying the mirror descent step multiple times in each round, we show that the upper bound on the dynamic regret can be reduced significantly from O( √ T (1 + CT )) to O(min(CT , ST , GT )), when the cost functions are strongly convex and smooth. In contrast to prior studies (Hall & Willett, 2015; Zhang et al., 2017; Mokhtari et al., 2016), our analysis does not require the cost functions to be Lipschitz continuous. Numerical experiments with the CIFAR-10 dataset, and sequential quadratic programming, and additional examples show substantial improvement on the dynamic regret compared with existing alternatives.

heading: A ADDITIONAL DEFINITIONS
text: Definition 3: A function f(·) is L-smooth, if there exists a positive constant L such that
f(y) ≤ f(x) + 〈∇f(x), y − x〉+ L 2 ‖y − x‖2, ∀x, y ∈ X .
Definition 4: A convex function f(·) is λ-strongly convex with respect to some norm ‖ · ‖, if there exists a positive constant λ such that
f(y) + 〈∇f(y), x− y〉+ λ 2 ‖x− y‖2 ≤ f(x), ∀x, y ∈ X .
Definition 5: A function f(·) is Lipschitz continuous with factor G if for all x and y in X , the following holds:
|f(x)− f(y)| ≤ G‖x− y‖, ∀x, y ∈ X .

heading: B PROOF OF LEMMA 1
text: Consider single-step mirror descent update as follows:
x = argmin y∈X
{ ft(x ′) + 〈∇ft(x′), y − x′〉+ 1
α Dr(y, x
′) } . (7)
Strong convexity of the above minimization objective implies
ft(x ′) + 〈∇ft(x′), x− x′〉+
1 α Dr(x, x ′) ≤ (8)
ft(x ′) + 〈∇ft(x′), y − x′〉+
1 α Dr(y, x ′)− 1 α Dr(y, x), ∀y ∈ X .
Furthermore, from the smoothness condition, we have
ft(x) ≤ ft(x′) + 〈∇ft(x′), x− x′〉+ L
2 ‖x− x′‖2. (9)
Substituting equation 9 into equation 8, and setting y = x∗t , we obtain
ft(x)− L 2 ‖x− x′‖2 + 1 α Dr(x, x ′) ≤ (10)
ft(x ′) + 〈∇ft(x′), x∗t − x′〉+
1 α Dr(x ∗ t , x ′)− 1 α Dr(x ∗ t , x).
Since α ≤ 1L , and regularization function r(·) is 1-strongly convex, we have 1
α Dr(x, x
′) ≥ LDr(x, x′) ≥ L
2 ‖x− x′‖2. (11)
Next, we exploit the strong convexity of the cost function, i.e.,
ft(x ′) + 〈∇ft(x′), x∗t − x′〉 ≤ ft(x∗t )− λDr(x∗t , x′). (12)
Combining equation 10, equation 11, and equation 12, we obtain
ft(x) ≤ ft(x∗t )− λDr(x∗t , x′) + 1
α Dr(x
∗ t , x ′)− 1
α Dr(x
∗ t , x). (13)
Next, we use the result of (Hazan & Kale, 2014), which states that for evey λ-strongly convex function ft(.), the following bound holds:
ft(x)− ft(x∗t ) ≥ λDr(x∗t , x), (14) where x∗t = argminx∈X ft(x). Combining the above with equation 13, we obtain
Dr(x ∗ t , x) ≤ βDr(x∗t , x′), (15)
where β = 1− 2λα1+λα .

heading: C PROOF OF THEOREM 2
text: C.1 KEY LEMMAS
The following two lemmas pave the way for our regret analysis leading to Theorem 2. Lemma 7 presents an alternative form for the mirror descent update.
Lemma 7 Suppose there exists zt+1 that satisfies ∇r(zt+1) = ∇r(xt) − α∇ft(xt), for some strongly convex function r(·), and step size α. Then, the following updates are equivalent
xt+1 = argmin x∈X Dr(x, zt+1), (16)
xt+1 = argmin x∈X
{ 〈∇ft(xt), x〉+ 1
α Dr(x, xt)
} . (17)
Proof. We begin by expanding equation 16 as follows:
xt+1 = argmin x∈X {r(x)− r(zt+1)− 〈∇r(zt+1), x− zt+1〉}
= argmin x∈X {r(x)− 〈∇r(zt+1), x〉}
= argmin x∈X {r(x)− 〈∇r(xt)− α∇ft(xt), x〉}
= argmin x∈X {α〈∇ft(xt), x〉+ r(x)− r(xt)− 〈∇r(xt), x− xt〉}
= argmin x∈X
{〈∇ft(xt), x〉+ 1
α Dr(x, xt)}. (18)
Thus, the update in equation 16 is equivalent to equation 17.
Lemma 8 Under the same convexity and smoothness condition stated in Theorem 2, let xt be the sequence of decisions generated by OMMD. Then, the following bound holds:
‖xt+1 − x∗t ‖ ≤ √ LrβM‖xt − x∗t ‖, (19)
where Lr is the smoothness factor of the regularization function r(·), and β is the shrinking factor obtained in Lemma 1.
Proof. Using the result of Lemma 1, OMMD with M mirror descent steps guarantees
Dr(x ∗ t , xt+1) ≤ βMDr(x∗t , xt). (20)
Since the regularization function r(·) is 1-strongly convex, we have
‖x∗t − xt+1‖2
2 ≤ r(x∗t )− r(xt+1)− 〈∇r(xt+1), x∗t − xt+1〉. (21)
Next, we exploit the smoothness condition of the regularization function r(·), i.e.,
r(x∗t )− r(xt)− 〈∇r(xt), x∗t − xt〉 ≤ Lr 2 ‖x∗t − xt‖2. (22)
By combining the above with equation 20, and equation 21, and using the definition of Bregman divergence, we obtain
‖xt+1 − x∗t ‖2 ≤ LrβM‖xt − x∗t ‖2. (23)
Taking the square root on both sides of equation 23 completes the proof.
C.2 PROOF OF THE THEOREM
Now, we are ready to present the proof of Theorem 2. In this proof, we will use the following properties of Bregman divergence.
(a) By direct substitution, the following equality holds for any x, y, z ∈ X , 〈∇r(z)−∇r(y), x− y〉 = Dr(x, y)−Dr(x, z) +Dr(y, z). (24)
(b) If x = argminx′∈X Dr(x ′, z), i.e., x is the Bregman projection of z into the set X , then for any arbitrary point y ∈ X , we have Dr(y, z) ≥ Dr(y, x) +Dr(x, z). (25)
To bound the dynamic regret, we begin by using the strong convexity of the cost function ft(·), i.e., ft(xt)− ft(x∗t ) ≤ 〈∇ft(xt), xt − x∗t 〉 − λDr(x∗t , xt)
≤ 1 α 〈∇r(xt)−∇r(zt+1), xt − x∗t 〉 − λDr(x∗t , xt) ≤ 1 α ( Dr(x ∗ t , xt)−Dr(x∗t , zt+1) +Dr(xt, zt+1) ) − λDr(x∗t , xt) ≤ 1 α ( Dr(x ∗ t , xt)−Dr(x∗t , xt+1)−Dr(xt+1, zt+1) +Dr(xt, zt+1) ) − λDr(x∗t , xt)
≤ ( 1 α − λ ) Dr(x ∗ t , xt) + 1 α ( Dr(xt, zt+1)−Dr(xt+1, zt+1) ) ≤ ( 1 α − λ )(ft(xt)− ft(x∗t ) λ ) + 1 α ( Dr(xt, zt+1)−Dr(xt+1, zt+1) ) , (26)
where in the second line we have used the alternative mirror descent update stated in Lemma 7, i.e., ∇ft(xt) = (1/α)(∇r(xt) − ∇r(zt+1)). To obtain the third line, we have utilized the Bregman divergence property in equation 24. We have used the Bregman projection property in equation 25 in the fourth line. By omitting some negative terms, and using equation 14, we obtain the right-hand side of equation 26.
Thus, if α > 12λ , we have
ft(xt)− ft(x∗t ) ≤ λ
2αλ− 1
( Dr(xt, zt+1)−Dr(xt+1, zt+1) ) (a) ≤ λK 2αλ− 1 ‖xt+1 − xt‖
≤ λK 2αλ− 1
( ‖xt+1 − x∗t ‖+ ‖xt − x∗t ‖ ) (b) ≤ λK 2αλ− 1 (1 + √ LrβM )‖xt − x∗t ‖, (27)
where we have used the Lipschitz continuity of Bregman divergence to obtain inequality (a), and we have applied Lemma 8 to obtain inequality (b). Summing equation 27 over time, we have
RegdT = T∑ t=1 ft(xt)− ft(x∗t ) ≤ λK 2αλ− 1 (1 + √ LrβM ) T∑ t=1 ‖xt − x∗t ‖. (28)
Now, we proceed to bound ∑T t=1 ‖xt − x∗t ‖ as follows:
T∑ t=1 ‖xt − x∗t ‖ = ‖x1 − x∗1‖+ T∑ t=2 ‖xt − x∗t ‖
≤ ‖x1 − x∗1‖+ T∑ t=2 ‖xt − x∗t−1‖+ ‖x∗t−1 − x∗t ‖
(a) ≤ ‖x1 − x∗1‖+ T∑ t=2 √ LrβM‖xt−1 − x∗t−1‖+ T∑ t=2 ‖x∗t − x∗t−1‖, (29)
where we used the result of Lemma 8 to obtain inequality (a). If M ≥ d ( 1 2 + 1 2αλ ) logLre, we have
βM = ( 1− 2αλ
1 + αλ
)M ≤ exp ( −2Mαλ 1 + αλ ) < 1 Lr , (30)
which implies LrβM < 1. Therefore, by combining equation 29 and equation 30, we have
T∑ t=1 ‖xt − x∗t ‖ ≤ ‖x1 − x∗1‖ 1− √ LrβM + ∑T t=2 ‖x∗t − x∗t−1‖ 1− √ LrβM . (31)
Finally, substituting equation 31 into equation 28 completes the proof.

heading: D PROOF OF THEOREM 3
text: In order to bound the dynamic regret, we begin by the smoothness condition of the cost function ft(.), i.e.,
ft(xt)− ft(x∗t ) ≤ 〈∇ft(x∗t ), xt − x∗t 〉+ L
2 ‖xt − x∗t ‖2
≤ ‖∇ft(x∗t )‖∗‖xt − x∗t ‖+ L
2 ‖xt − x∗t ‖2. (32)
Next, we use the fact
‖∇ft(x∗t )‖∗‖xt − x∗t ‖ ≤ ‖∇ft(x∗t )‖2∗ 2θ + θ‖xt − x∗t ‖2 2 , (33)
for any arbitrary positive constant θ > 0. Thus, we have
ft(xt)− ft(x∗t ) ≤ ‖∇ft(x∗t )‖2∗
2θ +
(L+ θ)‖xt − x∗t ‖2
2 . (34)
Summing equation 34 over time, we obtain
RegdT = T∑ t=1 ft(xt)− ft(x∗t ) ≤ T∑ t=1 ‖∇ft(x∗t )‖2∗ 2θ + L+ θ 2 T∑ t=1 ‖xt − x∗t ‖2. (35)
Now, we proceed by bounding ∑T t=1 ‖xt − x∗t ‖2 as follows:
T∑ t=1 ‖xt − x∗t ‖2 = ‖x1 − x∗1‖2 + T∑ t=2 ‖xt − x∗t−1 + x∗t−1 − x∗t ‖2
≤ ‖x1 − x∗1‖2 + T∑ t=2 ( 2‖xt − x∗t−1‖2 + 2‖x∗t−1 − x∗t ‖2 ) ≤ ‖x1 − x∗1‖2 + 2βMLr
T∑ t=1 ‖xt − x∗t−1‖2 + 2 T∑ t=2 ‖x∗t−1 − x∗t ‖2. (36)
We note that if M ≥ d ( 1 2 + 1 2αλ ) log 2Lre, then 2βMLr < 1. Therefore, from equation 36 we can obtain
T∑ t=1 ‖xt − x∗t ‖2 ≤ ‖x1 − x∗1‖2 1− 2βMLr +
2
1− 2βMLr T∑ t=2 ‖x∗t − x∗t−1‖2. (37)
Substituting equation 37 into equation 35 completes the proof.

heading: E PROOF OF THEOREM 5
text: The proof of Theorem 5 initially follows the first half of the proof of Theorem 2, which is repeated here for completeness.
To analyze the dynamic regret, we first use the strong convexity of the cost function ft(·), i.e.,
ft(xt)− ft(x∗t ) ≤ 〈∇ft(xt), xt − x∗t 〉 − λDr(x∗t , xt)
≤ 1 α 〈∇r(xt)−∇r(zt+1), xt − x∗t 〉 − λDr(x∗t , xt) ≤ 1 α ( Dr(x ∗ t , xt)−Dr(x∗t , zt+1) +Dr(xt, zt+1) ) − λDr(x∗t , xt) ≤ 1 α ( Dr(x ∗ t , xt)−Dr(x∗t , xt+1)−Dr(xt+1, zt+1) +Dr(xt, zt+1) ) − λDr(x∗t , xt)
≤ ( 1 α − λ ) Dr(x ∗ t , xt) + 1 α ( Dr(xt, zt+1)−Dr(xt+1, zt+1) ) ≤ ( 1 α − λ )(ft(xt)− ft(x∗t ) λ ) + 1 α ( Dr(xt, zt+1)−Dr(xt+1, zt+1) ) , (38)
where in the second line we have used the alternative mirror descent update stated in Lemma 7, i.e., ∇ft(xt) = (1/α)(∇r(xt) − ∇r(zt+1)). To obtain the third line, we have utilized the Bregman divergence property in equation 24. We have used the Bregman projection property in equation 25 in the fourth line. By omitting some negative terms, and using equation 14, we obtain the right-hand side of equation 38.
Therefore, if α > 12λ , we have
ft(xt)− ft(x∗t ) ≤ λ
2αλ− 1 (Dr(xt, zt+1)−Dr(xt+1, zt+1)) . (39)
Now we continue to bound Dr(xt, zt+1). By the definition of Bregman divergence, we have
Dr(xt, zt+1) +Dr(zt+1, xt) = 〈∇r(xt)−∇r(zt+1), xt − zt+1〉 = 〈α∇ft(xt), xt − zt+1〉 ≤ ‖α∇ft(xt)‖∗‖xt − zt+1‖
≤ α 2
2 ‖∇ft(xt)‖2∗ +
‖xt − zt+1‖2
2 . (40)
The strong convexity of the regularization function implies
‖xt − zt+1‖2
2 ≤ r(zt+1)− r(xt)− 〈∇r(xt), zt+1 − xt〉 = Dr(zt+1, xt). (41)
Combining the above with equation 40, we obtain
Dr(xt, zt+1) ≤ α2
2 ‖∇ft(xt)‖2∗. (42)
By substituting equation 42 into equation 40, and summing over time, we have
RegdT = T∑ t=1 ft(xt)− ft(x∗t ) ≤ α2λ 4αλ− 2 ‖∇ft(xt)‖2∗. (43)

heading: F CLOSED-FORM UPDATE FOR MIRROR DESCENT
text: In this section, we derive the close-form mirror descent update in equation 6.
Let r(y) = ∑d j=1 yj log(yj) be the negative entropy. Then, we have
Dr(y, y i t) = d∑ j=1 [ yj log(yj)− yit,j log(yit,j)− (log(yit,j) + 1)(yj − yit,j) ] =
d∑ j=1 yj log( yj yit,j ) + 〈1, y − yit〉 = DKL(y, yit), (44)
where yit,j denotes the j-th component of the decision vector y i t, and DKL(y, y i t) represents the KL divergence between y and yit.
Now consider the update in equation 5, which can be written as follows:
minimizey∈X 〈∇ft(yit), y〉+ 1
α d∑ j=1 yj log( yj yit,j ) (45)
subject to 〈1, y〉 = 1, y ≥ 0.
The Lagrangian of the above problem is given by
L(y, λ, γ) = 〈∇ft(yit), y〉+ d∑ j=1 [ 1 α yj log( yj yit,j ) + λyj − γjyj ] − λ, (46)
where λ ∈ R and γ ∈ Rd+ are Lagrange multipliers corresponding to the constraints. Next, we take derivative with respect to y to obtain
∂
∂yj L(y, λ, γ) = ∇ft(yit)j +
1 α log(yj) + 1 α − 1 α log(yit,j) + λ− γj . (47)
Setting the above to zero results in the following closed-form update:
yi+1t,j = yit,j exp(−α∇ft(yit,j))∑d j=1 y i t,j exp(−α∇ft(yit,j)) . (48)

heading: G ADDITIONAL EXPERIMENTS
text: In this section, we present additional experiments to study the performance of OMMD. In the first experiment, we use the MNIST dataset. In the second experiment, we consider a switching problem where the cost function switches between two quadratic functions after a specific number of rounds.
First, we consider the well-known MNIST digits dataset, where every data sample ω is an image of size 28× 28 pixel that can be represented by a 784-dimensional vector, i.e., d = 784. Each sample corresponds to one of the digits in {0, 1, . . . , 9}, and thus, there are c = 10 different classes. The goal of the learner is to classify streaming digit images in an online fashion.
We consider a robust regression problem, where the cost function for the batch of data samples at time t is given by
f(x, (ωt, zt)) = ‖ωTt x− zt‖21,
where x is the optimization variable, belonging to the constraint set is X = {x : x ∈ Rn+, ‖ x ‖1= 1}. We use the negative entropy regularization function, i.e., r(x) = ∑d i=1 xi log(xi), which is strongly convex with respect to the l1−norm. We set the step size α = 0.1 and use a batch size of 20 data examples per round.
From Fig. 3, we again observe that OMMD consistently outperforms the other alternatives. In particular, compared with DMD, applying M = 10 steps of mirror descent can reduce the dynamic regret up to 20%. We also see that the dynamic regret grows linearly with the number of rounds,
which is a natural consequence of steady fluctuation in the sequence of dynamic minimizers x∗t as explained before.
Next, we consider the case where the cost function switches between two functions. Both functions are in the quadratic form ft(x) = ‖Atx− bt‖22, where At ∈ Rd×d, and bt ∈ Rd. In particular, we assume that the parameter At is chosen among
A (1) t = diag(
1 tp1 , 1 tp1 , . . . , 1
tp1︸ ︷︷ ︸ d1 , 0, 0, . . . , 0︸ ︷︷ ︸ d2 ), and A(2)t = diag(0, 0, . . . , 0︸ ︷︷ ︸ d1 , 1 tp1 , 1 tp1 , . . . , 1 tp1︸ ︷︷ ︸ d2 ),
such that d1 + d2 = d, and bt = [ 1tp2 , . . . , 1 tp2 ] ′. Therefore, at each round the cost function is either f (1) t (x) = ‖A (1) t x− bt‖22 or f (2) t (x) = ‖A (2) t x− bt‖22. We assume that the cost function switches between f (1)t (·) and f (2) t (·) every τ rounds. In our experiment, we set d1 = 10, d = 1000, p1 = 0.9, and p2 = 0.1. We further set the switching period τ = 10, and parameter α = 0.02. The dynamic regret roughly reflects the accumulated mismatch error over time.
In Fig. 4, we compare the performance of OMMD with that of other alternatives in terms of the dynamic regret. OMMD with M = 10 nearly halves the dynamic regret of DMD after 300 rounds. Furthermore, the benefit of applying multiple steps of mirror descent can be significant even for smaller values of M .

Review summaries:
This paper studies the dynamic regret of online multiple mirror descent, which is online mirror descent with M repeated steps on each of T sequential loss functions. The authors show three bounds for the dynamic regret of OMMD, which generalizes OMGD [Zhang et al. '17]: C_T (the path length of the minimizer sequence), S_T (the sum of squared segment lengths), and G_T (the squared dual gradient norm of the points played).

This work derives a new upper bound on the dynamic regret for online convex optimization in the restricted setting where the comparison sequence is made up of the minimizers x^_1,...,x*_T of the loss sequence. There are three main parameters that control regret in this case: the path length C_T = ||x*_2-x*_1||+...+||x*_T-x*_{T-1}||. The squared path length C_T = ||x*_2-x*_1||^2+...+||x*_T-x*_{T-1}||^2. And the sum G_T of squared loss gradient norms evaluated at x*_1,...,x*_T.