On the Dynamic Regret of Online Multiple Mirror Descent
Authors: Nima Eshraghi
and Ben Liang
Venue:  (2021)
Keywords: Online learning
Online Convex Optimization
Mirror Descent

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.

Under review as a conference paper at ICLR 2021
ON THE DYNAMIC REGRET OF ONLINE MULTIPLE MIRROR DESCENT
Anonymous authors Paper under double-bling review
ABSTRACT
We study the problem of online convex optimization, where learner makes se- quential 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 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 be- tween 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 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.
INTRODUCTION
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 Yuaan & Lamperski 2017) and deep learning (Mnih al. 2015).
In this work, we consider online convex optimization, which can be formulated as discrete-time sequential learning process follows. At each round the learner first makes decision dą E X, where X' is a convex set representing the solution space. The learner then receives a convex cost function f<(x)) X + IR and suffers the corresponding cost of fe((r) 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 's accumulated cost and that of an optimal fixed offline decision, which made hindsight with knowledge of fe(-) for all
Reg = E
min Σ f((x). DEX
t=1
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 various online algorithms (Zinkevich) Cesa-CesaBBBiin Bianchi & Lugosi] 2006 Hazan et al. 2006; Duchi et al. 2010 Shalev-Shwartz 2012 that guarantee sublinear bound on the static regret.

---

Under review as a conference paper at ICLR 2021
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., (017), which allows dynamic sequence of comparison targets and defined by
T
T - Σ f(()), t=1
Regī = f((s))
t=1
where x (() is minimizer of the cost round t.
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 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 Σ |0 x1-1lb
(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(vT + CT)) (Zinkevich) 2003). [ For strongly convex functions, the dynamic regret of online gradient descent can be reduced to (CT) (Mokhtari et al., 2016). When the cost functions
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 Ommin(r ST)), where ST represents the squared path length, defined by
ST Σ
a J. 11
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 optimiza- tion (Hall& Willeti 2015 Jadbabaie et al.) (015). Mirror descent uses the Bregman divergence, which generalizes the Euclidean norm used in the projection step of gradient descent, thus acquiring expanded applicability to broader range of problems. addition, the Bregman divergence is only mildly dependent on the dimension of decision variables (Beck & Teboulle 2003 Nemirovsky & Yudin [983). 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 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(vT(1 + Cr)), which is the same as that of online gradient descent in (Zinkevich) 2003). In this work, investigate whether it is possible 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
A more general definition of the dynamic regret was introduced in Zinkevich 2003). which allows comparison against arbitrary sequence {ue]T IT We note that the regret bounds developed in 7inkevvich 2003) also hold for the specific case of u4 = 2/.
2

---

Under review as a conference paper at ICLR 2021
O(VT(1+C;) to (mminCCr, Sr. Gr)), where GT represent the squared gradients, i.e.,
GT [Vf((.))1.
(3)
where ||-II+ denotes the dual norm. The sum squared gradients GT be smaller than both the path length and squared path length, especially when the cost functions fluctuate drastically over time. In contrast the aforementioned works, our analysis does not require the cost functions 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 & Willetr 2015), online multiple gradient descent (Zhang et al. 2017). and online gradient descent Zinkevich (2003).
ONLINE MULTIPLE MIRROR DESCENT
In this section, 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.
2.1 PRELIMINARIES
Definition 1: The Bregman divergence with respect to the regularization function r(-) is defined as D,(,,y) r(x) r(y) - (Vr(y). y)-
The Bregman divergence is general distance-measuring function, which contains the Euclidean norm and Kullback-Leibler divergence as two special cases.
Using the Bregman divergence, generalized definition of strong convexity is given in (Shalev Shwartz & Singer 2007).
Definition 2: A convex function f(-) is X-strongly convex with respect to convex and differentiable function r(-) if
f(y) + (V/(),
(2, S f(x), Vz, X.
Following many prior studies on mirror descent, we assume that the cost functions are X-strongly convex, where the above generalized strong convexity definition used. We further assume that the cost functions are L-smooth, and the regularization function r(-) is L,-smooth and 1-strongly note that these are standard
convex with respect to some norm (refer to App. A for definitions). assumptions commonly used in the literature after the group of studies began by (Hazan et al. 2006 Shalev-Shwarte & Singer 2007), to provide stronger regret bounds by constraining the curvature of cost functions.
We further make standard assumption that the Bregman divergence is Lipschitz continuous as follows:
2z) s K||= wll. Vz, 2. X,
where K 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 & Willew 2015). There is a notable weakness in such bounds. Since the sequence of cost functions revealed to the learner, the learner has control over it. If these cost functions happen to not meet the Lipsehitz condition, earlier analyses that require this condition become inapplicable. In this work, we do not require the functions 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 small factor. For example, in the particular case of the KI. divergence, which is obtained by the choosing negative entropy the regularization function, on the set X' {al Σ 2, 1; 2 1 ). the constant K is of (log D). Other examples of many widely used Bregman divergences that satisfy this condition given in (Bauschke & Borwein 2001).
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Online Multiple Mirror Descent
Input: Arbitrary initialization of æ1 E X; step size a; time horizon T. Output: Sequence of decisions (Ia S t < T}.
1: for 1,2..... . do
2: submit E A' and receive fi(-)
3: set V/ = 4t
4:
for
..., M do .....
5: Vi ++ = argmin ( fe(v)). D.
6:
end for
7: set T++1 = yi
M+1
8:
end for
2.2 ONLINE CONVEX OPTIMIZATION WITH OMMD
We consider online optimization over a finite number rounds, denoted by T. At the beginning of every round t, the learner submits decision represented by 2t. which is taken from a convex and compact set X. Then, an adversary selects a function fe(.) and the learner suffers the corresponding cost (xx). The learner then updates its decision in the round. With standard mirror descent, this is given by
argmin ( 1 D, (x, *EX
Z++1
(4)
where a is a fixed step size, and (- is the Bregman divergence corresponding to the regularization function r(-). The update in equation suggests that the learner aims stay close to the current decision as measured by the Bregman divergence, while taking a step in direction close to the negative gradient reduce the current cost at round f.
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 especially important when the successive cost functions have similar curvatures. In particular, in order to track 2i41 the learner needs to access the gradient the cost function, i.c., V (-). Unfortunately, this information not available until the end of round 1. However, if the successive functions have similar curvatures, the gradient of f-(-) is reasonably accurate estimate for the gradient of f++1()). In this case, every time that the learner queries the gradient of fc(.), it finds point that is likely to be closer to the minimizer of (+). 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 yi .....,, M +1 via the following updates:
1 D. w() .,,....,M. M. a
11 = It,
i+1
(5)
yEX
Then, by setting xz-1 Vt M+1 the learner proceeds to the next round, and the procedure continues. Note that M independent 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 helpp decrease the distance to the minimizer 2 Therefore, quantifying the benefit of OMMD over standard mirror descent requires careful analysis on the impact of the fluctuation of fe(-) over time. To this end, we provide an analysis bound the dynamic regret of OMMD in the next section.
THEORETICAL RESULTS
The following lemma paves the way for the proposed analysis 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.
4

---

Under review as a conference paper at ICLR 2021
Lemma Assume that fo() is X-strongly convex with respect to differentiable function r(:), and L-smooth. Single-step mirror descent with a fixed step size a S guarantees the following:
; Fc+1) S ,D, (x7 ;z),
where of is the unique minimizer of ft(.), and 3 = 1 I+aX
20
Lemma proved in App. in the supplementary material.
Remark 1. Lemma 1 states that 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 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 the special choice of r(z) = ||=112, which reduces the Bregman divergence Euclidean distance, i.e., (z,, = || vl
Lemma I Lindicates that the distance between the next decision 2++1 and the minimizer 2; strictly smaller than the distance between the current decision and the minimizer at round I. This implies that the minimizers not far from each other, applying mirror descent multiple times enables the online learner more accurately track the sequence of optimal solutions z7.
the functions f((-) and f++1()), which are oy and F141 respectively, are
The succeeding theorems provide three separate upper bounds the dynamic regret of OMMD, based on path length CT (as defined in equation [ squared path length Sy (as defined in equation and sum squared gradients (as defined in equation 3)
Theorem Assume that ((-) is L, Smosth 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 x be the sequence of decisions generated by OMMDD with fixed step size 2X mirror descent steps per round. The dynamic regret satisfies the following bound:
1 and M > [[} zax) log Iyp
KA (1 TT,.MM)
-
(CI + 1=]- 2ıll).
2ad
111 - V TT,.MM)
where 3 is the shrinking factor derived in Lemma] and K is the Lipschitz constant associated with D,(-.).
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( O(VT(1 Cr)) 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 implies that OMMD reduces the upper bound to (CCT) when the cost functions 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, is M 2 3 and M 2 for the two experiments shown in Section
Theorem Under the same convexity and smoothness conditions stated Theorem 2 let xe be the sequence of decisions generated by OMMD with fixed step size a S & and M 2 I(= + zux) log 2L,1 mirror descent steps per round. For any arbitrary positive constant 0, the dynamic regret upper bounded by
T
[((())) 20
(1
(1
LL, +0 21,
(Sx
+ || -x11-1
Σ f((m))
-
2
Theorem is proved in App. in the supplementary material.
Since the gradient at xt zero if ot is in the relative interior of the feasibility set X, i.e. [+))+ = 0, the above theorem can be simplified to the following corollary.
Corollary If 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).
5

---

Under review as a conference paper at ICLR 2021
When the cost functions drift slowly, the distances between successive minimizers small. Hence, the squared path length Sy, which relies on the square of those distances, can be significantly smaller than the path length Cr. In this case, Theorem B and Corollary 4 can provide tighter regret bound than Theorem 2
Theorem Under the same convexity and smoothness conditions stated in Theorem 2 let xe be the sequence of decisions generated by OMMD with a fixed step size a > 2x" The following bound holds on the dynamic regret:
T
a²x 4a 2 Gr. Gr.
Σ -
The proof of Theorem given in App. 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 [z)]] O(1/t²) for some > 0, Theorem guaranttes O(T 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 Sr may grow linearly, whereas diminishing gradients ensure sublinear Gr-
Theorem 2 Corollary 4 and Theorem 5] respectively, state that the dynamic regret of OMMD is upper bounded linearly by path length Cr, squared path length Sy, and sum squared gradients Gr- This immediately leads the following result.
Corollary Under the same convexity and smoothness conditions stated in Theorem the dynamic regret of OMMD with suitably chosen a and M has upper bound of (mmin(CT, ST, GT)).
Remark 5. We note that (Mokhtari al. 2016) and (Zhang et al. 2017) provide upper bounds of ((Cr) and O(min(C7: respectively, on the dynamic regret of online gradient descent with single and multiple gradient queries, while (Hall & Willeu 2015) presents an upper bound of O(VT(1 + Cr)) on the dynamic regret of online single-step mirror descent. Corollary 6 shows that OMMD can improve the dynamic regret bound to Ommin(Cr Cr, Sr, Gr)). 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 fa(x)) = || bbll over the d-dimensional probability simplex. Assume that for any 2 we have the parameter sequence of
diag 0,0, ...., 0), if / is odd diag (0, ZPT O, .,....,), if f is even,
A =
PPg 1 where P1 and P2 are positive constants such that P2 S P1- In this setting, observe that Cr = (T) and GT 1P1--- Thus, GT can be considerably smaller than Cr. On the other hand, it is also possible that Cr is smaller than GT in other cases. For example, let A, diag(1 (1/2 /2, 0, ... 0) on odd rounds and A, diag(0, -1/2,......... -1/2). and be the unity vector for all t. In this case, we observe that Cr = ((), while the sum gradient scales linearly with time, i.e., Gr (T)) Thus, neither Cr nor Gr alone can provide small regret bound for all cases. Similar examples can be found in comparison between Sy and GT but are omitted for brevity.
and b
4 EXPERIMENTS
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 ridge regression problem on the CIFAR-10 dataset (Krizhevsky 2009). Then, we study 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 & Willeti 2015).

---

Under review as a conference paper at ICLR 2021
In the first experiment, consider multi-class classification with ridge regression. In this task, the learner observes a sequence of labeled examples (wi 2), where w E R and the label 2, denoting the class of the data example, is drawn from discrete space Z ......... c}. We use the CIFAR-10 image dataset, which contains 5 x 10a data samples. Each data sample w 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 e 10 different classes. For ridge regression, the cost function associated with batch of data samples at round t. i.e., (W1,1; 21,1),.... (Wb,r, 26,1), is given by
fæz (wr, z)) = | x - 2
where x is the optimization variable, which is constrained by the set X = fz I E R4,1 ||2= 1}. and (w), 21) compactly represents the batch of data samples at round i.e., Wt The goal of the learer is to classify streaming images online by tracking the unknown optimal parameter 2;. We use the negative entropy regular- ization function, i.e., r(x)= = Σッ 1 zj log(z;), which is strongly convex with respect to the [1-norm. Then, the mirror descent update in equation [ leads to the following update:
[W1,s, w2. wb.] ]" and 2, = [z1.0: #2....... .........,6.1l. -b,el"
Vi. exp(-aVfi(v..))
++1 Mt.
(6)
Σj= vi., exp( exp(-e V
where Tt,j and V fare)y denote the j-th component of 2, and f((e) 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 a = 0.1.
In Fig. 1 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 2? 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 (z) = |||-| a 1| [ by 11 where p is positive constant, dr and b, are time-variant vectors, and the decision variable are æi E IRd,, x2 E Rdd, such that di + d2 = d. In experiment, we set p 10, d1 500, and d 1000. We assume that b, is time- inverinvaiiant and for all rounds t we have by = 2, while a satisfies the recursive formula 0++1 at + / with initial value 0 = 11.5. We further set the step size a = 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 learnrr' decisions and the minimizers sequence. In particular, compared with DMD, OMMD with M = 10 reduces the dynamic regret up to 80% after 2500 rounds.
RELATED WORKS
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 sublinear bound on the static regret (Zinkevich 2003, Cesa-Bianchi & Lugosi 2006 Hazan et al.)
2006; Duchi et al.) 2010 Shalev-Shwartz 2012) focus on the dynamic regret.
Here we review the most relevant works with
5.1 DYNAMIC REGRET OF ONLINE GRADIENT DESCENT
Dynamic regret was first introduced in (Zinkeicch 2003) for the analysis of online gradient descent, where an O O(VTCr) 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 by OVVTCr)
7

---

Under review as a conference paper at ICLR 2021
2.5-
ORCD, OMGD, OMGD.
OMGD.
DVD
OWND. 2
2.5
OHHO,
OMMD. 5
OWNO,
Dyment
OHHI.
0.0
1500
Figure 1: Dynamic regret comparison on CIFAR-10 dataset.
Figure 2: Dynamic regret of slowly drifting cost functions.
YYng et al. 2016). For strongly convex cost functions, the upper bound the dynamic regret be reduced to O(CT) Mokhtarr 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 ((min(Cr, Sr)) when the cost functions are smooth and strongly convex (Zhang et al. (017). 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 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, c.g., probability simplex (Duchil 2018). is known that gradient descent does not perform as well mirror descent, especially when the input dimension high (Nemirovsky & Yudin 1983 Beck & Teboulle 2003).
5.2 DYNAMIC REGRET OF ONLINE MIRROR DESCENT
The dynamic regret of online single-step mirror descent was studied in (Hall & Willett 2015), where an upper bound of ((VT(1 + Cr)) 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 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 Cr, deviation between the predictions and the actual ft- (x))- Unfortunately, to
gradients Dr. and functional variation Fr Di=1 max 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 single query 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 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 squared gradients. Furthermore, as opposed to the aforementioned works, our analysis does not require the cost functions to be Lipschitz continuous.
update its decision via multiple steps of mirror
Finally, there is also recent work in the literature on distributed online mirror descent (Shahrampour Jadbabaic 2017). As expected, it is more challenging to achieve performance guarantee in distributed optimization. We focus on centralized online convex optimization in this work.
We note that the regret bounds derived in Jadbabaie et al. 2015 is under the same definition of Zinkevich
2003
8

---

Under review as a conference paper at ICLR 2021
CONCLUSION
We have studied online convex optimization in dynamic settings. By applying the mirror descent step multiple times in each round, show that the upper bound on the dynamic regret can be reduced significantly from O(vT(1+ Cr)) (min((T, Sr, GT)), when the cost functions strongly convex and smooth. In contrast to prior studies (Hall & Willett 2015 Zhang et al., 2017] Mokhtari al.] (201)). our analysis does not require the cost functions 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.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Heinz H Bauschke and Jonathan M Borwein. Joint and separate convexity of the bregman distance.
Studies in Computational Mathematics, 8:22-36, 2001.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, ((55):12271122) 2015.
Nicolo Besa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge university press, 2006.
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551-585, 2006.
John Duchi. Introductory lectures on stochastic optimization. The mathematics of data, 25:99, 2018.
John C Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In Proceedings of the Conference on Learning Theory, 2010.
Eric C. Hall and Rebecca M Willett. Online convex optimization in dynamic environments. IEEE Journal of Selected Topics in Signal Processing, 94)):477-662) 2015.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1):2489- 2512, 2014.
Elad Hazan, Adam Tauman Kalai, Satyen Kale, and Amit Agarwal. Logarithmic regret algorithms for online convex optimization. In Proceedings of the Conference on Learning Theory, 2006.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimiza- tion:Competing with dynamic comparators. Proceedings of the International Conference on Arlificial Intelligence and Statistics, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
URL http:
/ //www. toronto.oo........ wttp://ooeeaaa/kk////aaaaaaaaeee Learniiig/eringgg features 2009 TR. pdf
Minghong Lin, Adam Wierman, Lachlan LH Andrew, and Eno Thereska. Dynamic right-sizing for power- proporpropottional data centers. IEEE/ACM Transactions Networking, 11785)1378-1399 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Joannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):599-53.. 2015.
Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the IEEE Conference on Decision and Control, 2016.
Arkadii Nemirovsky and David Yudin. Problem Complexity and Method Efficiency Optimization. Wiley, 1983.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Proceedings of the International Conference on Advances in Neural Information Processing Systems, 2013.
Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control, 6343),714-72,,2000 2017.
Shai Shalev- Shwarr-S Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
10

---

Under review as a conference paper at ICLR 2021
Shai
and Yoram Singer. Logarithmic Regret Algorithms for Strongly Convex Repeated Games. The Hebrew University, 2007.
Ming Shi, Xiaojun Lin, Sonia Fahmy, and Dong-Hoon Shin. Competitive online convex optimization with switching costs and ramp constraints. In Proceedings of the IEEE Conference on Computer Communications, 2018.
Tianbao Yang. Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. Proceedings of International Conference Machine Learning, 2016.
Jianjun Yuan and Andrew Lamperski. Online control basis selection by regularized actor critic algorithm. Proceedings of the IEEE American Control Conference, 2017.
Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. In Proceedings of the International Conference on Advances Neural Information Processing Systems, 2017.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the International Conference on Machine Learning, 2003.

---

Under review as a conference paper at ICLR 2021
A ADDITIONAL DEFINITIONS
Definition 3: function f() is I-smooth, there exists positive constant such that
f(v) ((x + (V](z) - ll- - =11 Vx, E X.
Definition 4: A convex function f(-) is X-strongly convex with respect to some norm exists positive constant À such that
|| ||. if there
> 1 vl & f(z), Va,y X.
f(u) (Vf()). -9) y)
Definition 5: A function f(-) is Lipschitz continuous with factor G if for all and y in X, the following holds:
[f(x) f(v) G||z vll. X.
B PROOF OF LEMMA
Consider single-step mirror descent update as follows:
fe(=')) (Vf((x'), x²) - + D...
argmin yEN
(7)
Strong convexity the above minimization objective implies
1 a
f((x)) + (Vfe(='), x') D,(x,2's
(8)
felx') (Vic(='), - x') (r 1 Dr(y,)), Vy X
a
Furthermore, from the smoothness condition, coniittionsooiiiiinnn we have
f+(x)) x f+(x) + (V[(z))) x²) + 1 1211?.
(9)
Substituting equation 9 into equation and setting y 27, we obtain
T, || - 2'112 Dr (2,,'') f((x)
(10)
2
a
f((2)) + (Vfi(''),, =1')) - D,
-) D.
a
a
Since S 1. and regularization function r(-) is 1-strongly convex, we have
1 (x 2 LD,(x,x') 2 || 2²112.
L _
(11)
2
Next, we exploit the strong convexity of the cost function, i.e.,
f((x') + (Vi((z)), x; x') S f((x)) AD,
(12)
Combining equation equation 11 and equation 12 we obtain
f((x) < fe(z)) (D, Da x') -x
(13)
Next, we use the result of (Hazan & Kale 2014), which states that for evey A-strongly convex function fe(-), the following bound holds:
(x fa(x;) 2 (D,
(14)
where x² argmin ex fe f((x). Combining the above with equation we obtain
D,(x; (z,,
(15)
where 3 = 2)a
0
T+
12

---

Under review as a conference paper at ICLR 2021
C PROOF OF THEOREM 2
C.I KEY LEMMAS
The following lemmas pave the way for our regret analysis leading to Theorem 2 presents an alternative form for the mirror descent update.
Lemma
Lemma Suppose there exists 2+1 that satisfies Vr(2++1) Vr(x,) a fe(re) for some strongly convex function r()), and step size Then, the following updates are equivalent
3++1 argmin D, (1,
(16)
aEX
2+41 argmin (V.f( + 1 - (x,
(17)
aEx
Proof. We begin by expanding equation 16 as follows:
F(4 argmin r(z+1) (Vr(z411, 2+1))
#Ex
argmin (r(z)) (Vr(2+1).2)}
=eX
argmin(r(z) (Vr(x)) [V
xEx
(egmin(((V[f(())))) r(x) - r(x)) (Vr(x,), z1)
=EX
( 2) + xx,))
(18)
xEX
Thus, the update in equation
16 is equivalent to equation 17
Lemma Under the same convexity and smoothness condition stated in Theorem 2 let øt be the sequence of decisions generated by OMMD. Then, the following bound holds:
|| - =1il S V L,,3M |x xills
(19)
where L, is the smoothness factor of the regularization function r(-), and B is the shrinking factor obtained in Lemma 7
Proof. Using the result of Lemma
OMMD with M mirror descent steps guarantees
Dx xx+1) s 3M D,
(20)
Since the regularization function r(-) is 1-strongly convex, we have
| - xe+1l?
2 < <(())) - r(1e+1) - (Vr(2411, - r(41).
(21)
Next, we exploit the smoothness condition of the regularization function r(.), i.c.,
(()))-(())))))))))))) r( (Vr(z))) πx) 1 || 12.12.
(22)
By combining the above with equation 20 and equation 21 and using the definition of Bregman divergence, we obtain
| - 21 < L,
M
||, - -x;
(23)
Taking the square root both sides of equation
23 completes the proof.
13

---

Under review as a conference paper at ICLR 2021
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, x, E X,
(Vr(z)- - Vr(y), - y) = D. v) D, (z, 2) + (y,
(24)
(b) If x = argmin EX (a 2), i.e., x the Bregman projection of into the set X, then for any arbitrary point L, we have
D,(y,2) 2 (r(y, (x)
(25)
To bound the dynamic regret, we begin by using the strong convexity the cost function fc(-), i.e.,
f((x)) - fi(=))) - fi(a))) - 2;) (D,
(rr(x)) vr(z++), 25)) (D,
2
(,(,), (x 2411 1) D1 2011) AD, (x7, xx))
(r(ai, v1) ) (r(,,, - (,(1 2411) + Dr (1i4, (11, - (D,(
-2) D, s4) + (r(111, - -D((111, 1) - + (D.( -
(26)
where in the second line we have used the alternative mirror descent update stated in Lemma 7 (z.)) (1/a)(Vr(zz) vr(z++1). To obtain the third line, have utilized the Bregman divergence property in equation 24] We have used the Bregman projection property in equation the fourth line. By omitting some negative terms, and using equation 14
i.c.,
we obtain the right-hand
side of equation 26
Thus, if
2x have
f
S
À
(D,( 2411) (1(01,1,
2ad
(a)
XK
| - xzll
2ad
XK
(| - x +1l1+ ||,5 - =ī1l
20d
XK
2a (1+ v L,B ||
x; ||+
(27)
where we have used the Lipschitz continuity of Bregman divergence obtain inequality (a), and we have applied Lemma 8 to obtain inequality (b). Summing equation 27 over time, we have
XK
Regd
Σ f((e)) fx(x;) < 2ad (1 + / M
| x; ||.
(28)
Now, we proceed to bound ΣT ||
zil
follows:
T
T
c - zi = |||] - z1 +
Σ
| - xill
t=2
|| - 2ill +
Σ
|| x 1| + || - xi'l
1=2
zill
L 1 27-1l
Σ
|, 1l.
(29)
1=2
14

---

Under review as a conference paper at ICLR 2021
where used the result of Lemma 8 to obtain inequality (a). If M [(2
2ax)
log Lr1, we have
g 1 2ad
M
-2Ma 1+at
1+ad
exx
exp
(30)
L
which implies L
1. Therefore, by combining equation 29 and equation 30 we have
Σ
| 21
|
xill
T E1=2
2 VI
27
(31)
L,,
3.
Finally, substituting equation 31 into equation
28 completes the proof.
D PROOF OF THEOREM
In order to bound the dynamic regret, we begin by the smoothness condition of the cost function ft()).ie. i.e.
L xz 2/11
f((x)) - f((x)) (V.((z)) -2) +
(=;(())) - 2ill + マ 11 2111?
(32)
Next, we use the fact
0100, - x;11?
[V - ==ill S
(33)
20
2
for any arbitrary positive constant 0. Thus, we have
(T. + 0)] x2 - x:712
fe(xe) f((x)) <
(34)
20
2
Summing equation 34 over time, we obtain
v((2))112
L 8
Reg
f((x)) -
+
2
|| - x;
(35)
20
2
Now, we proceed by bounding E(=1 ||
x 1| as follows:
T
T
bo x; 112 1= =1111 - xīll2
|| x;-1 + x7-1- - =x;
T
$ 1| - -i112 +
(2| - x2-11 +12 - 12)
< ||ا 2
2 L,
| x4_ 2 +2
2;11
(36)
t=1
t=2
We note that M 2 [[] + _ log 2L, obtain
then 2.3 L, < 1. Therefore, from equation 36 we can
|.n x 1
2
p x <
+
| x 11.
(37)
M L,
23M L,
Substituting equation 37 into equation 35 completes the proof.
15

---

Under review as a conference paper at ICLR 2021
E PROOF OF THEOREM 5
The proof of Theorem 5 iiniiilly follows the first half of the proof of Theorem 2 which is repeated here for completeness.
To analyze the dynamic regret, first the strong convexity of the cost function f((+), i.e.,
f((z)) - f (V((()), - 2;) (2,
(Vr(xt) vr(z++1, x;) (D,
2
(x( (1 4+1) (r( 2c+1) (D (x),, xz)
(x) (1 - (T(T++1, 2+11) + Dr (104, (102; - (D,
1 -1) 2) Dr xτ) + -D((1)
3 1) (((t))-fle -((o))) +
(38)
where in the second line have used the alternative mirror descent update stated in Lemma i.e., (x,) = (1/x)(Vr(zz) - vr(2+41)) To obtain the third line, we have utilized the Bregman divergence property equation 24 We have used the Bregman projection property in equation 25 in the fourth line. By omitting some negative terms, and using equation [4
we obtain the right-hand
side of equation
Therefore, if a 2X we have
A
f((x)) - f((z)) -
2ad - (D,( 241) - ((14))
(39)
Now we continue to bound D, (1 1). By the definition of Bregman divergence, we have
(,(21,2411) D, (2(41, (Vr(a.)) 1, z++1)
(aV fxr)) 2++1)
$ (orVa((z)))l-e 22+1/l
a²
| 2211
2 [V
(40)
The strong convexity of the regularization function implies
| 2+11l2
<((z)))) - r(xe) - (Vr(x:), xx) = Dr(2441,
(41)
Combining the above with equation 40
we obtain
D,
(42)
2
By substituting equation 42 into equation
40 and summing over time, we have
a² A
Reg df
Σ - fe(x)) <
4ad 2 [fe(xt)]1.
(43)
t=1
F CLOSED-FORM UPDATE FOR MIRROR DESCENT
In this section, derive the close-form mirror descent update in equation 6
16

---

Under review as a conference paper at ICLR 2021
Let Levr Ez=1 Uy log(y;) be the negative entropy. Then, we have
Mi log(us) - wi. log(vi,)) (log(vi,) + 1) - vigh
Σ j=1
yj log(
3 + (1, - wi) = DKI(y,vi,,
(44)
Vi.j
where vi., denotes the j-th component of the decision vector vl. and DEL (v, vf) represents the KL divergence between and vi.
Now consider the update equation which can be written follows:
minimize
(V f((()) y) Σ
y
log( V1
(45)
Vi.
j=1
subject to (). 1, 2 0.
The Lagrangian of the above problem is given by
My, (V (VS+())) + Ui log
M1 Xyj
T5ルs] X
(46)
Vi.j
where À E R and E IR are Lagrange multipliers corresponding to the constraints, Next, we take derivative with respect to to obtain
① oy,
L(y, Vf(())) (og((,) 1 log(vi.)) + 7--
(47)
a
Setting the above to results in the following closed-form update:
vi. eijee((aaViiii exp( -
.+1 Vi.
(48)
G ADDITIONAL EXPERIMENTS
In this section, we present additional experiments to study the performance of OMMD. In the first experiment, we use the MNIST dataset. 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 w is image of size 28 28 pixel that can be represented by a 784-dimensional vector, i.e., d = 784. Each sample corresponds one of the digits in {0, 1.... , 9}, and thus, there are 10 different classes. The goal of the learner is to classify streaming digit images in online fashion.
We consider a robust regression problem, where the cost function for the batch of data samples at time is given by
[ar (wi, =)) || - =11.?
where is the optimization variable, belonging to the constraint set (z RT, , x ||== 1}. We use the negative entropy regularization function, i.c., r(x) = ='a æ, log(x;), which is strongly convex with respect to the 11 norm. We set the step size 0.1 and use batch size of 20 data examples per round.
From Fig. 3] 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 20%. We also that the dynamic regret grows linearly with the number of rounds,
17

---

Under review as a conference paper at ICLR 2021
OG3
ORGG. M-
GM/D, Mi
CM/GD, Mi 10
DWP
Dynemt Sag
OMND, --
0.8
OWNO. 5
OMND, W 10
OCD
OMGD N
OMG0. N
OM6G. H
DMD
OMHD. =
OMHDD =-5
OMHDD
200
500
600
803
Round
Figure 3: Dynamic regret comparison on MNIST dataset.
Figure 4: Dynamic regret comparison for switching cost.
which is a natural consequence of steady fluctuation the sequence of dynamic minimizers zi as explained before.
Next, we consider the case where the cost function switches between two functions. Both functions
in the quadratic form (x) ||- by 112, where A, E [dddd and b, E Rd. In particular,
assume that the parameter A, is chosen among
A diag(
0,0, 0), and A diag (0, 0, 00.....,,0 O
IP1
PP
d1
d2
such that di + d2 and b, 822
Therefore, at each round the cost function is either || x bel.. We assume that the cost function switches
F2
1 (x) || x b1 ((
between l (.) and s!²)( every T rounds. In our experiment, we set di 10, = 1000, P1 = 0.9, and P2 0.1. We further set the switching period
10, and parameter a 0.02. The dynamic regret roughly reflects the accumulated mismatch eтrоr over time.
In Fig. 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.
18


Reviews:
[{"review_id": "wsS232r33Tz", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nPrevious work by Zhang showed that when the loss functions are simultaneously strongly convex and strongly smooth w.r.t. the Euclidean norm, then Online Gradient Descent with multiple updates per step (OMGD) achieves regret of order min{C_T,S_T} whenever G_T < T G^2 for some G > 0 (i.e., the gradient norm of the loss is uniformly bounded). Note that this algorithm invokes the first-order oracle a constant number of times per step.\n\nThis work extends Zhang's results in two main directions. First, OMGD is replaced by OMMD (which is Online Multiple Mirror Descent). Accordingly, strong convexity and strong smoothness are now computed w.r.t. the Bregman divergence induced by the mirror map. Second, the condition G_T < T G^2 is dropped. The resulting bound is of order min{C_T,S_T,G_T}. Experiments with quadratic losses compare OMMD against OMGD and Dynamic Mirror Descent (DMD) by Hall and Willet. Both these algorithms have worse upper bounds than OMMD.\n\nI have some concerns about the significance of the results. I wonder what are interesting examples of loss functions that are simultaneously strongly convex and strongly smooth with respect to a Lipschitz continuous Bregman divergence induced by a regularization function which ---in turn--- is simultaneously strongly convex and strongly smooth with respect to some norm? We know that quadratic losses and regularized logistic losses satisfy these assumptions w.r.t the squared Euclidean mirror map (as shown by Zhang). I suspect that the generalization proposed in this work does not lead to include additional interesting losses.\n\nSince OMMD improves on the OMGD regret bound, it would be interesting to know whether OMMD reduces to OMGD when the regularizer is Euclidean.\n\nThe experiments use a decision set (the simplex) where OMD with entropic regularization is known to work better than OGD. This advantage appears to be simply transferred to the dynamic setting. Indeed, OMMD performs only marginally better than DMD, which also uses the entropic regularization.\n\nIt is not even clear whether the theory applies to the setting used in the experiments. The quadratic losses used in the experiments are strongly convex and smooth only with respect to Euclidean regularization and not with respect to entropic regularization (the regularization used by OMMD in the experiments).\n\nThe assumptions require Lipschitz continuity of the Bregman divergence. Does this condition apply to KL divergence? What is K in this case? \n\nIn the ridge regression experiment, z_i is defined as a scalar but treated as a vector in the definition of the loss.", "extra_scores": {}, "extra_text": {}}, {"review_id": "te-w8Ry5B6_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "For strongly convex & smooth functions, this work considers regret against the best sequence of points in hindsight, and gives an algorithm that achieves regret that is linear in path length and square path length while making multiple gradient queries every round.\n\nComments:\n+ While discussing related work, the paper conflates two notions of \"dynamic regret\" which are quite distinct both in the nature of guarantee and techniques needed to achieve them. The first is the one paper explains -- regret against the sequence x_t^* typically scaling with the path length of x_t^*, where x_t^* are minimizers. The second is regret against ANY arbitrary sequence z_t^* with regret scaling as path length of z_t^* (again, z_t^*'s are arbitrary). A guarantee of the second kind is strictly stronger in that it implies the first (and not vice versa). Indeed, Zinkevich and Jadbabaie et al consider the second notion. Hence, the picture the paper paints of the state of prior work is not entirely accurate.\n+ Now, let us just focus on the first objective as this paper does. Here, a very simple strategy -- choosing x_t = x_{t-1}^* to be the minimizer of the last function -- works. Indeed, this immediately gives regret bounds of L (Lipschitz constant) * path length, and (smoothness) beta * squared path length. Obtaining these with single step of GD offer a challenge, but allowed multiple gradient calls, one can use them to compute x_{t-1}^* offline. In this view, I don't find the results compelling.\n+ The work mentions that previous works required a Lipschitz constant bound. In presence of smoothness, isn't a Lipschitz constant bound of beta * Diameter implied?\n+ The first experiment seems to constrain iterates to positive orthant (for regression) via update 6. Is there a reason for this choice?", "extra_scores": {}, "extra_text": {}}, {"review_id": "31Ew_uNiVqp", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis 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).\n\nPros:\n- This work fills a gap in the literature left by [Zhang et al. '17], which considers the analogous gradient descent algorithm, and derives the min(C_T, S_T) bound that this paper generalizes. It is natural to ask whether to corresponding mirror descent algorithm enjoys the benefits of mirror descent in classical online learning, in which the choice of regularizer allows for a statistical rate to adapt to the geometry of the decision set.\n- The paper is well-written, and the analyses are crisp. There is a great deal of effort placed in including intuitive discussions along with the key results.\n\nCons:\n- I'm not quite convinced by the motivation for G_T. Multiple points below in the detailed comments, where clarifications would be appreciated.\n- Thus, overall, given my current understanding, I don't think this paper fully answers the research question in a way that is a sufficiently large delta compared to [Zhang et al. '17].\n\nDetailed comments:\n- Unlike C_T and S_T, G_T depends on the learner's decisions. So, if a learner makes very bad decisions and thus experiences large gradients (this is necessarily true by strong convexity), the G_T term becomes vacuous, and the regret bound is dominated by min(C_T, S_T).\n- The discussion at the top of page 3 (\"G_T can be smaller than both C_T and S_T, especially when the cost functions fluctuate drastically over time\") is confusing: if cost functions fluctuate drastically over time, shouldn't the gradients experienced always be large? Seems like the opposite statement is the usual motivation for path length-based regret: \"C_T and S_T can be smaller than G_T, if the functions fluctuate a lot but it's not worst-case because the minimizers are stable\". A clarification, example, or mathematical statement would be helpful.\n- Remark 4 is also confusing: if f needs to be strongly convex with a constant lambda, then its gradient dual norm can't shrink uniformly. Could the authors clarify?\n- The fact that the Lipschitzness of the loss functions isn't assumed is also not necessarily a feature. At points where f_t is highly non-Lipschitz, the gradient is large, and thus G_T (the upper bound claimed to be the novelty) is large. While it's true that the regularizer r can be chosen more freely than the losses, a poor choice leads to large L_r, so it's not clear what claim that discussion (at the end of 2.1) is making.\n\n*** post-response ***\n\nThanks for the clarifications and revisions in the manuscript.\n\n- A2: Lemma 1 (and its M-step repetition) show that the outputs of mirror descent x_{t+1} are guaranteed to be close to the minimizers of f_t. But the loss of x_{t+1} is measured on f_{t+1}; this is what I meant by \"bad decisions\". Thus I'm confused about the statement \"the learner is not expected to make bad decisions\"; Lemma 1 does not imply this. It only implies this when the consecutive minimizers are close (which is captured by C_T and S_T being small).\n- A3: This example makes sense (though in this example, the function is L-Lipschitz, not L-smooth). I also noticed that the example in Remark 5 isn't both smooth and strongly convex in any norm.\n- A4: Understood; thanks.\n- A5: I now understand (from the addendum in the paper as well) that this \"user control of L_r\" is basically referring to the standard selling point of OMD that the user can specify a regularizer that adapts to the geometry of the decision set and loss functions; I buy this point. This is separate from the ability to handle Lipschitz constants being large (which gradient descent can also handle, by having a smaller learning rate).\n\nAdditionally, I'm confused about the response to R2's \"simple strategy\". The convergence rates of GD and MD are stated in incompatible ways. The right comparison would be to pick M so that the RHS of Lemma 8 in the appendix to be smaller than \\eps. I agree that this work strictly generalizes [Zhang et al. '17], but I don't agree that this work bypasses computational difficulties of approximately minimizing a smooth & strongly convex f_t; as the authors point out themselves in a different reply, when r is quadratic, OMMD reduces to running OMGD.\n\nIn my opinion, this algorithm and analysis are potentially worthy of publication at a top venue, but the manuscript evidently needs an overhaul in its justification of the setting and G_T. Thus my overall score is unchanged.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers questioned the significance of the result, in the sense that the qualitatively it is not clear how much of an improvement it is to replace "min(S_T,C_T) with Lipschitz assumption" by "min(S_T,C_T,G_T)". The authors' response on this point did not convince the reviewers. If the authors were to resubmit this work to a future conference, we encourage them to significantly expand on this point.
Decision: Reject