Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor
Authors: Lijun Zhang
Wei Jiang
Jinfeng Yi
Tianbao Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Smoothed Online Convex Optimization
Adaptive regret with switching cost
Dynamic regret with switching cost
Discounted-Normal-Predictor

Abstract: In this paper, we investigate an online prediction strategy named as Discounted-Normal-Predictor [Kapralov and Panigrahy, 2010] for smoothed online convex optimization (SOCO), in which the learner needs to minimize not only the hitting cost but also the switching cost. In the setting of learning with expert advice, Daniely and Mansour [2019] demonstrate that Discounted-Normal-Predictor can be utilized to yield nearly optimal regret bounds over any interval, even in the presence of switching costs. Inspired by their results, we develop a simple algorithm for SOCO: Combining online gradient descent (OGD) with different step sizes sequentially by Discounted-Normal-Predictor. Despite its simplicity, we prove that it is able to minimize the adaptive regret with switching cost, i.e., attaining nearly optimal regret with switching cost on every interval. By exploiting the theoretical guarantee of OGD for dynamic regret, we further show that the proposed algorithm can minimize the dynamic regret with switching cost in every interval.

Smoothed Online Convex Optimization Based on Discounted-Vormal-Prrcicoo
Wei Jiang', Jinfeng Yi Tianbao Yang* National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China Peng Cheng Laboratory, Shenzhen 51 8055, China
Lijun Zhang 2.2,
3JD AI Research, Beijing, China DDpartment of Computer Science and Engineering, Texas A&M University, College Station, USA {zhanglj, jiangw> (arggww@llmmdlee amda. nju. edu. cn, yijinfeng@jd com, tianbao yangbaaaaaangtmmmmm.... edu
Abstract
In this paper, we investigate an online prediction strategy named as Discounted- Normal-Predictor (Kapralov and Panigrahy 2010] for smoothed online convex optimization (SOCO), which the learner needs minimize not only the hitting cost but also the switching cost. In the setting of learning with expert advice, Daniely and Mansour [2099] demonstrate that
Soreeteed--ooo---reeeee be utilized to yield nearly optimal regret bounds over any interval, even in the presence of switching costs. Inspired by their results, we develop a simple algorithm for SOCO: Combining online gradient descent (OGD) with different step sizes sequentially by Discounted-Norme Normmll-Predictor Despite its simplicity, we prove that it is able to minimize the adaptive regret with switching cost, i.c., attaining nearly optimal regret with switching cost on every interval. By exploiting the theoretical guarantee of OGD for dynamic regret, further show that the proposed algorithm can minimize the dynamic regret with switching cost in every interval.
can
Introduction
Recently, a variant of online convex optimization (OCO), named as smoothed OCO (SOCO) has received lots of attention in the machine learning community (Goel et al.) 2019 Li and Li] 2020 In each round f, the learner chooses an action w, from a convex domain W, and a convex loss function fe(-): W + R is selected by an adversary. While in the traditional OCO, the learner only suffers a hitting cost fe(w)), in SOCO, it further pays switching cost m Wr, Wr-1), which penalizes the learner for changing its actions between rounds. SOCO has found wide applications in real-world problems where the change of states brings additional costs [Lin et al. 2012 Kim and Giannakis 2014 Goel et al., (017)) such the wear-and- tear cost switching servers [Lin et 2011
For general convex functions, a natural choice of the switching cost the distance between successive actions, i.e., m( (WW, w,-1) ||w, w.-1ll. Then, the total loss in the f-th round becomes
f((w)) ) + AG - wt-1ll
(1)
where À is the trade-off parameter, and G is the upper bound of the G is introduced to ensure that the two terms weighted by À are on the same order. Following the convention of online learning (Cesa-Bianchi and Lugosi 2006), we choose regret measure the performance, and meanwhile take into account the switching cost. Let 1' be the total number of iterations. The standard metric would be regret with switching cost:
of gradients. Here,
(fi(w) + AG][w, wi-1ll) min Σ f((w)
(2)
wEW
1=1
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

defined as the difference between the cumulative loss of the learner and that of the best fixed decision in hindsight. It is easy verify that online gradient descent (OGD) ZZinkevich [003] attains an (1 + X) bound for regret with switching cost (c.f. Theorem which can be proved to be optimal GGradu et al. 2020, Theorem 4].
However, regret is not suitable for changing environments in which the best decision may vary over time. To address this limitation, new performance measures, including adaptive regret and dynamic regret have been proposed [Zhang 2020 Cesa-Bianchi and Orabona 2021]. Adaptive regret enforces the algorithm to have small regret over every interval [Hazan and Seshadhri 2007 Daniely et al.)
2015). which essentially measures the performance w.r.t. changing comparator. By extending adaptive regret to SOCO, we obtain adaptive regret with switching cost:
A-R-S(T,-)= max R-S(r, rsT+1-7
where 7 is the length of the interval, and
R-S(r, s) = Σ (fi(we) + AG - wi-1ll)
min WEW
fe f((w)
1=r
is the regret with switching cost over interval [r, s]. To cope with changing environments, dynamic regret directly compares the learner against a sequence of comparators uI...., ur E W [Zinkevich] 2003). Similarly, we can incorporate the switching cost into dynamic regret, and obtain dynamic regret with switching cost:
Σ (fi(w)) + AG||w; wi-1ll) Σ f((w)).
In the literature, there are only two works that investigate adaptive regret with switching cost. However, one of them relies on strong convexity [Gradu et al.) [020]. and the other one makes use of sophisticated techniques [Zhang al. 2022]. There also exist preliminary studies dynamic regret with switching cost, but are limited to the special case that A 15=1/ 1// [Zhang et al., 2021a] or follow different settings (Li et al. 2018 Goel et al. 2019). Besides, all of previous works only target one performance measure. Notice that for OCO, we do have algorithms that are able to minimize
adaptive regret and dynamic regret simultaneously (Zhang al. 2020 Cutkosky 2020
In this paper, we develop a simple algorithm for SOCO based on Discounted-Normen Normal-Predictor [Kapralov and Panigrahy 2010 2011), which is designed for online bit prediction and can be used to combine two experts. In a recent study, Daniely and Mansour (2019) reveal that Discounted- Normal-Predice automatically controls the switching cost, and with the help of projection, can be extended to support adaptive regret. Motivated by their observations, we first analyze a variant of Discounted-Nomee Normal- Prediictorr with conservative updating (abbr. DNP-cu), and prove that it suffers a small loss on every interval, even in the presence of switching costs. To ensure adaptivity, we choose conservative updating instead of projection because the former one can be analyzed more easily. Then, we create multiple OGD with different step sizes, and combine them sequentially by DNP-cu. Theoretical analysis shows that the proposed method achieves an O /11 + A)T log T) bound for adaptive regret with switching cost. Furthermore, based on the fact that OGD is also equipped with dynamic regret bounds, we establish nearly optimal guarantees for dynamic regret with switching cost in every interval. Specifically, for any interval [r, s] with length t, our method attains an ((1(1 + A) + Pr,s) log T) bound for dynamic regret with switching cost, where
Pr..
I u.t1l
(5)
is the path-length of an arbitrary comparator sequence Ur...., U, E W.
Compared with state-of-the-art results [Zhang et al., 2021a 2022 this paper has the following advantages.
Our O (1 + A)T log T) adaptive regret bound is on the same order as that of Zhang et al. [2022] but our method is more simple. In contrast, their algorithm pieces together several techniques, including online coin betting, geometric covering intervals, and the reduction from unconstrained online learning to constrained online learning.
2

---

2. Although Zhang et al. [202 establish an ( Pir)) dynamic regret bound with switching cost, they only consider the case that À 1/G and the whole interval [1, By comparison, our dynamic regret bound holds for any À 2 0 and any interval.
3. To the best of our knowledge, this is the first effort to minimize both adaptive regret and dynamic regret, under the setting of SOCO.
Finally, we would like emphasize the strength of Aascounte-NoormalPeehhleee opinion, was not getting enough attention. The results of Daniely and Mansour (2019) and this paper demonstrate that methodology) to minimize both adaptive regret and dynamic regret, with or without switching cost, under the setting of learning with expert advice (LEA) or OCO.
which, in our
provides an elegant way (and very different
2
Related Work
We briefly review the related work on OCO and SOCO, as well as Discounted-Normall -or-na--Podditttot
2.1 Online Convex Optimization (OCO)
During the past decades, OCO has been extensively studied, and various algorithms have been proposed to minimize the regret, i.c. 2 with À (Shalev-Shwartz] 2011 Hazan 2016). It is
well-known that OGD Zinkevich, 2003 achieves an O(VT) bound which is minimax optimal [Abemethy et al. 2008 We can obtain tighter regret bounds if the loss function satisfies specifical
curvature properties, such as strong convexity [Shalev- Saalev-Swwarz et al.) 20077] exponential concavity
Haaznn et al. 2007 Orabona al. 2012), and smoothness (Srebro et al.) [0100] Chiang et al. 2012).
Adaptive regret has been explored under the setting of LEA [Littlestone and Warmuth, 1994 Freund
et 1997 Adamskiy et al. /2012, György et al. [012 Luo and Schapire| 22015) and OCO [Hazan
and Seshadhri] 2007] 2009]] Jun et al.
2017b Zhang et al. 2019 202 Wan et al. 2022 We follow the definition of Daniely et al. [2015] which is given by (3) with x = O. For general convex functions,
Jun et al. 7a] establish an O(VT log T) bound, which holds for any interval length T.
Dynamic regret is proposed by Ziinevicch [2003). , and its definition can be found by setting À = 0 in ④ Existing works have analyzed two types dynamic regret: (i) the general version where the
comparator sequence is arbitrary (Hall and Willett 2013 Zhang et al.) 2018b Zhao et al. 2020a
|Bayy and Wang 2021), and (ii) the worst-case version where u, is chosen as the minimizer f((-
Jadbabate et al.
2015 Besbes et al. 2015 Yang et al.) 2016 Mokhtari et al. 2016 /Zhang et al. 2017
Zhao and Zhang 2021 J. For general convex functions, Ader attains an optimal O O(vT(1 + Pi, P),)))
bound, where PT. is the path-length of uj, ur [Zhang et al. 2018b).
Both adaptive regret and dynamic regret are designed for changing environments, but our under- standing of their relationship quite limited. Currently, we know that it is possible to bound the worst-case dynamic regret by adaptive regret [Zhang et al. [2018c), and minimize adaptive regret and the general dynamic regret simultaneously [Zhang et al. 2020 Cutkosky 2020).
2.2 Smoothed Online Convex Optimization (SOCO)
The research of SOCO is motivated by real-world applications where the switching cost plays a crucial role [Lin et al., 2 2012]. Besides regret, competitive ratio is another popular metric for SOCO, and a large number of algorithms have been proposed to yield dimension-free competitive ratio. However, all of them are limited to the lookahead setting where the learner can observe the hitting cost f-(-) before deciding its action Wt. and rely on strong conditions [Bansal et al. 2015
Antoniadis and Schewior 2018 Chen et al. 2018 Goel et al. 2019 Goel and Wierman 2019 Argue ct al. 2020a We note that SOCO is closely related to convex body chasing (CBC) Friedman and
Linial 1993 Antoniadis et al. 2016 Bansal et al. 2018 Argue et al.
2019 Bubeck et al. 2019
2020 Argue et al. 2020b
Sellke 2020 For more details, please refer to Lin et al. [202]]
In the study of online control, Gradu et al. (200) and /Zhang et al. (002 have developed adaptive
algorithms for OCO with memory, which can be applied to bounding adaptive regret with switching
cost. However, Gravv et al. 22200] need to assume the hitting cost is strongly convex. Although Zhang
et al. 2022 successfully deliver an O(v(1 log T' bound, their method is rather complex.
3

---

Algorithm Discounted-Normll-Pee Prediicorr
Require: Two parameters: and Z
1: Set #1 = 0, and p = 1/n
2: for = 1......
do
3: Predict (
4: Receive b,
5: Set 1++1 patt + bt.
6: end for
Specifically, they make of online coin betting (Orabona and Pál 2016 geometric covering intervals (Daniely et al. 2015), and the reduction from unconstrained online linear optimization to constrained online linear optimization [Cutkosky and Orabona 2018).
For dynamic regret with switching cost. Zhang et al. 202 extend Ader to support switching costs, and prove an optimal O /T(1 + Pi,r)) bound, but they only consider the case that = 1/G. Other works dynamic regret with switching cost incomparable to our paper, because they either rely on strong convexity [Li et al. 2018 and Li 2020]. set the switching cost as the squared distance [Goel et al. 2019]. or assume upper bound of the total switching cost is given in advance [Chen et al. 2018
Zhao et al. 2020b].
2.3 Discounted- Prreiii-
Following the terminology of Kapralov and Panigrahy [2010). we introduce Riscounted-Normall Predictor the context of the bit prediction problem. Let bj, ..... by be an adversarial sequence of bits, where b. E [-1, can take real values. In each round f, the algorithm is required to output confidence level & E 1- 1], then observes the value of br, and finally gets a payoff Cbb, The goal to maximize the cumulative payoff of the algorithm E Ceby.
Let be parameter for the interval length, and define the discount factor p 1/n. As the name suggests, Discounted-Norme Mortiidd--ooa---reeee Predicor maintains discounted deviation x, Σ 1 each round and the prediction determined by g(x+)) for a confidence function g(-) defined as
g(x) sign(2) (z) min
Z erf
(6)
where Z > O is a parameter, and erf =
2 Se e -= ds is the error function. The complete
v
procedure is summarized in Algorithm 14] have proved that Discounted-Normal Predictor satisfies
[ For any Z S 1/e, Kapralov and Panigrahy (200 Theorem
T Σ
T
(b, 2 max
Σ
by - -0(TTbb((/2) j-1
where we set 71 = 7 in Algorithm| By choosing Z = o(1T)), we observe that it has O O(VTlo T) regret against the strategy that predicts the majority bit (whose payoff is E, byD) as well as subconstant o(1) loss. To address the problem of learning with two experts, we can define by as the difference between the losses of experts and restrict e, [0. 1]. It follows that the algorithm suffers OlyTlog T) and o(1) regret w.r.t. the two experts, respectively (Kapralov and Panigrahy 2010 Lemma 15). Miccounted-Norma-PPree
can be applied to the general setting of N experts, by aggregating experts one by one. We note that the problem of trading off regret to the best expert for regret to the "special" expert stems from the study of Even- Dar et al. [2007]. and is later investigated by Sani et al. 2014].
Kapralov and Panigrahy 2010 Theorem 5] also investigate a variant of the adaptive regret, which uses an infinite window with geometrically decreasing weighting. To this end, they propose conservative updating rule to control the value of the deviation æ4. Let (n) = O log(1/2) (1/Z)) be a constant such that [g(x)] for |ar| > (n). The current bit b, is utilized to update only when the confidence of the algorithm low i.e., |asg| < U()) or when the algorithm predicts incorrectly i... ((x))., 0. Otherwise, they will ignore b, and set Z1+1 paz. However, it remains open

---

whether their conservative updating works with the standard adaptive regret [Daniely et al. 2013].
which is answered affirmatively by our Theorem !|
Daniely and Mansour [2019] extend Discounted- Sertounted-Norma-PPeeeeee Nrrmct-Predictor to support the switching cost and the adaptive regret. The confidence function is modified slightly as
g(x) 1I 1. [=(x]]]
where
V n Z erf
((x)
(8)
v8n
and 1/+ denotes the projection operation onto the set [0, 1]. First, by more careful analysis. they demonstrate that SorpuuteddNormal-Prrre switching costs. Second, they introduce projection operation prevent z; from being too large, and then derive tight bounds for the standard adaptive regret. Specifically, the updating rule for It becomes
has similar regret bounds even in the presence of
J++1 = 22,U [pxx be]
99)
where
1 16n log Z
- S
(10)
Our work is inspired by Daniely and Mansour 2019). but with the following differences.
While Daniely and Mansour (2019) consider the setting of LEA,, we investigate OCO.
To bound the adaptive regret. Daniely and Mansour [2019) introduce the projection operation. as shown in (9. In contrast, we make use of the conservative updating (Kapralov and Panigrahy 2010], and provide more simple analysis.
We study not only the adaptive regret, but also the dynamic regret. Our algorithm is equipped with nearly optimal bounds for both metries, in the presence of switching costs.
3
Main Results
We take Coroouttdd-oomml-Prrddeee
with conservative updating (DNP-cu) as our meta-algorithm, and present its performance by taking the switching cost into consideration. Then, we use DNP-cu to combine multiple OGD sequentially, and show its adaptive regret and dynamic regret with switching cost. Due to space limitations, all the proofs are deferred Appendix A
3.1 The Meta-algorithm
To consist with previous studies, we describe DNP-cu from the perspective of bit prediction, and require the prediction lie in [0, 1] so that it be used later meta-algorithm to combine experts. The detailed procedure is summarized in Algorithm 2 Compared with the original algorithm
Kapralov and Panigrahy 2010). make two modifications.
We choose the confidence function g(-) in 77.. whose property has been revealed by Daniely and Mansour [2099] Lemmas 18 and 19] more formally.
2. We adapt the updating rule to the fact that g()) belongs to [0, 1] instead of [-1, 1]. Spe- cifically, perform the standard updating in Line 6, when the confidence is low i.e.,
æ, E [0, (n)], or when the algorithm predicts incorrectly i..,
< 0&b, 0 Un))&b, < 0.
Otherwise, we follow Line which only shrinks x, and ignores b,-
To analyze the performance of DNP-cu, we consider both the payoff and the switching cost, referred to as reward below. We have the following theorem which exploits the possibility that the magnitude of the bit sequence may be smaller than 1.
'Thiir definition of the error function drops the constant
5

---

Algorithm 2 Discounted-VormalPPeddiii with conservative updating (DNP-cu)
Require: Two parameters: and Z
1: Set 21 = 0, = 1/n, and (n) = (1)
2: for t l....., do
3: Predict g(xx) where g(-) defined in
4: Receive by
5: if Ii E [0, (n)] or It < O&b, > Oo x3 > U(1)&bb < <0 then
6: Set p.t
7: else
8: Set It+1 p
9: end if'
end for
Theorem Suppose Z S 1 and 2 max{Se, 16 1o }. For any bit sequence b1...., by such that
1bl S p S 1, the cumulative reward of Algorithm 2
over any interval [r, s) with length satisfies
g(xx)); - - (((r)))(((+))))
(11)
max 0, by n
(U(m) + 2p) - Un)) 11 U(m) - 1-- ZT
where (n) is defined in 10 Furthermore, for intervals starting from 1. we have
Σ [g(u))be (lo(a)) - s(oeti)) max 0. b
(U(n))+2p) U(r)) -ZT. (12)
n
And the change of successive predictions satisfies
Zp 4
(g(xx) g(x++1)) S HV log
(13)
n
First, the above theorem reveals that DNP-cu controls the switching cost automatically. and the trade-off between the payoff and the switching cost determined by the magnitude of the bit sequence. Second, thanks to the conservative updating, we are able to bound the cumulative reward over any interval, which can be exploited support adaptive regret.
Remark:
Recall that in the total loss ( the trade-off parameter À could be arbitrary. As a result, to utilize DNP-cu for SOCO, also need flexible way balance the payoff and the switching cost. To this end, we introduce À and define the reward the l-round as g(x,)h Alg(x,) - g(xx-1)). Then, our goal is to maximize
Σ (g(x:)b. Alg(x)) g(
(14)
for every interval [r, s) Based Theorem straiihtforward way is to multiply the bit sequence by 1/X, and then pass to Algorithm 2
But in this way, the lower bound will scale linearly with
To improve the dependence on A, we will multiply the bit sequence by 1/vī Danicly and Mansour 2019 and have the following corollary based on and (3) of Theorem
Corollary 2 Suppose Z < 1 max(8e, 16 log }. and bi...., bT is bit sequence such that |b,| < I. Running Algorithm 2
over the scaled bit sequence
b
bt max (VX,1)
max (V,1)
We actually focus on Σi., (g(x;)) )b. - Alg(z.) g( which differs from by a constant factor.
We omit (12). because not used in the subsequent analysis.

---

for any interval [r, s) with length we have
Σ
(o(z))b- Al((2))) g(x++1)))
(g(ar)br
tmr
max (VX, (n) +n) 2r + nb
(15)
2 max
0,
be
maxx ()) max Vx, 1)
And the change of successive predictions satisfies
Iø(xa)) - g(((+1)) max VA,1)
Vvn log
1 + 2=4
(16)
Z
Remark:
From the definition of (n) in 10p. we have
(g(x))6r - -lg(ax)) g(x++1)l) = -0
(1++ 7 + v(1 1jzz)
(17)
2=0 ( (1n
for any interval (r, s]. Notice that the bound in is independent of the interval length т, so it holds even when is larger than On the other hand, for any interval [r..] whose length is no larger than n, i.e., 7/n S 1, we also have the following regret bound of Algorithm w.r.t. the baseline strategy which always outputs 1:
Σ (g(ax)be Alg(x))) g((++1))) 2=0(1/7)
Σ b. -0.-O((C A)n
(18)
As elaborated in the analysis (c.f. Lemma when using Algorithm to combine multiple algorithms, there are two issues that need to be addressed.
1. We do not destroy the theoretical guarantee of early algorithms, which is ensured by (17)
2. We can inherit the theoretical guarantee of the current algorithm, which is archived by (18)
3.2 Smoothed OGD
We introduce the following common assumptions for OCO Shalev-Shwartz 2011
Assumption All the functions fi 's convex over the domain W. Assumption The gradients of all functions are bounded by G, i.e.
max
[[))] G, Vt E [T).
(19)
WEW
Assumption 3 The diameter of the domain W is bounded by D, ie.,
max w.w' WW
| w D.
(20)
Without loss of generality, assume
fi(w) E (,G Vw E W, LE
(21)
since we can always redefine f((w) as fi(w) - min fc(w) which belongs to [0, GD) according to (19) and (20).
First, we explain how use DNP-cu combine predictions of two algorithms designed for OCO. Let A and A² be two online learners, and denote their predictions in the 1-th round by w| and w respectively. Let A be meta-algorithm which outputs convex combination of wł and w i.e.
= (1 wy w/] + we w
(22)
where the weight w; [0, 1]. We have the following lemma regarding the meta meta-regret of A.
7

---

Algorithm 3 Combiner
Require: Three parameters: M, and Z
Require: Two algorithms: A and A²
1: Let D be instance of DNP-cu, i.e. Algorithm with parameter and Z
2: Receive w and w from A and AA² respectively
3: Receive the prediction Wi from D
4: for I. ,, do
5: Predict w, according 22
6: Send the loss function [.( ] to AA' and .22
Receive w and w from A and A²² respectively
8: Send the bit max(v/.1)
D, where & is defined in (28)
9: Receive the prediction W1+1 from D
10: end for
Lemma Assume the outputs of At and A move slowly such that
MD and [|w - -
MD
|w - whtill S
Vt
[7]
(23)
X
where M some constant. Under Assumptions ! 2 andd any interval [r, s) satisfies
the meta-regret of A w.t. A over
Σ (f((w)) + AGI(W; -we11l) Σ t=
(fi(w)) + AGIlW! - -w/+il
E=
(24)
--(1 Σ (wrle A/w; w(+1l)
and the meta-regret of A w.r.t A? satisfies
Σ (f((w.) + AGIl w++1ll) Σ
(fe(w?) + - -wi+ll)
(25)
s 31+MMGD Σ (wrle- A/ws we+1l -e)
where
4. = f((w?) AGI(w! w/alll
[0, M)GD,
(26)
6 = ((w?)) + >?] w
MGGDD,
(27)
E. E
4 (1 + M)GD
[-1.1].
(28)
Remark: By mapping and & in Lemma I to g(æz) and b, in Corollary 2 we immediately see that the weight w, in (22) can be determined by invoking DNP-cu, i.c. Algorithm process the scaled bit sequence
bT
max V
max(VA,
Then, can utilize lower bounds in Corollary establish upper bounds for the regret in Lemma We name the strategy of aggregating two algorithms by DNP-cu as Combiner, and summarize its procedure in Algorithm
In the following, we will use online gradient descent (OGD) with constant step size Zinkevich 2003 as our expert-algorithm. OGD performs gradient descent to update the current solution
W 11w [we V f((:.)

---

Algorithm 4 Smoothed OGD
Require: Three parameters: K, M and Z
1: for = 1,.. .....,,,, K,KK do
2: ne 722
3: Let .4' be an instance of OGD with step size s7 defined 29
4: if 1 then
5: Set 8 A
6: else
7:
Let B be an instance of Combiner, i.e., Algorithm which combines B and A'' with parameters M, nt and Z
8: end if
9: end for
for
T do do
11: Run ,.....,................. B sequentially for one step
12: Predict the output of BK, denoted by w,
13: end for
where >> O is the step size, and 1+wl-] denotes the projection onto W. Notice that it is important to choose constant step size, which makes it easy analyze the regret, as well as the dynamic regret, over any interval [r, s).
First, create K instances of OGD, denoted by determined later. The step size of A' is set to be
where the value of K will be
(29)
(1+ (1)n( G
where
n 1-1
(30)
Then, we use Combiner, i.c., Algorithm to aggregate them sequentially, We will create a sequence of algorithms B², ...., ,...,,K. BK where B' is obtained by combining B with A', and B A The
parameter in Algorithm 3 is set to be (6) when forming B In each iteration 4, we invoke B¹ B!...., BK sequentially for one step, and return the output of 3* as the prediction w,. The completed procedure is named as smoothed OGD, and summarized in Algorithm
Remark: Our method has similar structure with those Cutkosky [2020) and Zhang et al. 2022 in the sense that we all combine multiple experts sequentially. In contrast, other approaches for adaptive regret use two-level framework, where meta-algorithm aggregates multiple experts
(which is allowed to sleep) simultaneously [Hazan and Seshadhri] 2007 Daniely et al. 2015 Jun al.) b Zhang al. 2019 20216]. On the other hand, all the previous works, including Cutkosky (2200] and Zhang et al. 2022]. need to construct set of sub-intervals, and maintain sub-routine for each one. this way, they can use a small number of sub-intervals to cover any possible interval, and attain a small regret on that interval. By comparison, our method does not rely on any special construction of sub-intervals, making more elegant.
3.3 Theoretical Guarantees
Next, we provide the theoretical guarantee of smoothed OGD. We first characterize its regret with switching cost over any interval.
Theorem 3 Assume
T > max Xnax(VAloo) VAlog, T,
(31)
and set
T
loga 32 max(A, (2, 1) log 1/2
+ +1,
(32)

---

= = and Z = 1/T in Algorithm 4 Under Assumptions 7
2 and
we have
Σ (fe(wa) AGI(w; We41 || -f((w)
<2GDV 113GD max( VA, 1) 1) log -0 (v log log
for any interval [r, s] with length and any W.
Remark:
Our (V((1 + A)T log 7) bound is on the same order as that of Zhang et al. [022]. When
= O, we get the D(VTlog'1 T) adaptive regret for general convex functions (Jun et al. 2017a
Our proposed method is also equipped with nearly optimal dynamic regret with switching cost over any interval, as stated below.
Theorem Under the condition of T'heorem S
we have
Σ (fe(we) + AGIl - -witlll f((w))
S2GD ((1 21 +1ss/// 120GD max( VX, 1) DV 2D),
=o -o( (1(+1) Pris) log
where T the interval length, and Pr.s, defined in S is the path-length of an arbitrary comparator sequence u,,..., E W.
U,
Remark: The above theorem shows that method can minimize the dynamic regret with switching cost over any interval. According to the D v
lower bound of dynamic regret [Zhang et al. 2018b Theorem 2), we know that our upper bound is optimal, up to a logarithmic Tactor. Theorem is very general and be simplified in different ways.
If we choose a fixed comparator such that Pr.. = 0, Theorem reducess to Theorem 3 and matches that Zhang et al. [2022].
2. If we ignore the switching cost and set À = 0, we obtain an O( Pr.s log T bound for dynamic regret over any interval, which recovers the results /Zhang al. 2020
Theorem 4] and Cutkosky 22020, Theorem 7].
3. When both Pr, and À 0, we obtain the O(vTlogT) adaptive regret of Jun ct al. [2017a]
4 Conclusion and Future Work
Based variant of Biscounted-Normal-Preeeee as smoothed OGD for SOCO. Our algorithm combines multiple instances of OGD sequentially by DNP-cu, and thus is very simple. Theoretical analysis shows that it attains nearly optimal bounds for both adaptive regret and dynamic regret over any interval, in the presence of switching costs. We also conduct preliminary experiments to verify our theories, and present the results in Appendix B
(DNP-cu), we design novel algorithm, named
For adaptive regret and dynamic regret, we can obtain tighter bounds when the hitting cost exhibits additional curvature properties such as exponential concavity [Hazan and Seshadhri 2007 [Bayy and
Wang [021] and smoothness [Zhang et al., 2019 Zhao et al. 2020a] It remains unclear whether DNP-cu can exploit such information further improve the performance. For SOCO, it is common to consider the lookahead setting, and the problem still nontrivial due to the coupling created by the switching cost [Chen et al. 2018). For dynamic regret with switching cost, Zhang et al. [2021a] have demonstrated that Assumption iss unnecessary in the lookahead setting. It would be interesting to develop a lookahead version of DNP-cu, and investigate whether we can drop Assumption well.
Acknowledgments and Disclosure of Funding
This work was partially supported by NSFC (62122037, 61976112) and the Major Key Project of PCL (PCL2021A12).
10

---

References
Abernethy, P. L. Bartlett, A. Rakhlin, and A. Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory, pages 413-423, 2008.
D. Adamskiy, W. M. Koolen, A. Chernov, and Vovk. closer look at adaptive regret. In Proceedings of the 23rd International Conference Algorithmic Learning Theory, pages 290-304, 2012.
A. Antoniadis and K. Schewior. A tight lower bound for online convex optimization with switching costs. In Approximation and Online Algorithms, pages 164-175, 2018.
A. Antoniadis, N. Barcelo, M. Nugent, K. Pruhs, K. Schewior, and M. Scquizzato. Chasing convex bodies and functions. In Proceedings of the 12th Latin American Symposium on Theoretical Informatics, pages 68-81, 2016.
C. Argue, S. Bubeck, M. B. Cohen, A. Gupta, and Y. T. Lee. A nearly-linear bound for chasing nested convex bodies. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 117-122, 2019.
C. Argue, A. Gupta, and G. Guruganesh. Dimension-free bounds for chasing convex functions. In Proceedings of 33rd Conference on Learning Theory, pages 219-241, 2020a.
C. Argue, A. Gupta, G. Guruganesh, and Z. Tang. Chasing convex bodies with linear competitive ratio. In Proceedings of the 31st Annual ACM-SIAM Symposium Discrete Algorithms, pages 1519-1524, 2020b.
D. Baby and Y.-X. Wang. Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Conference on Learning Theory, pages 359-409, 2021.
N. Bansal, A. Gupta, R. Krishnaswamy, K. Pruhs, Schewior, and C. Stein. A 2-competitive algorithm for online convex optimization with switching costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 96-109, 2015.
N. Bansal, M. Böhm, M. Eliáš, G. Koumoutsos, and S. W. Umboh. Nested convex bodies are chaseable. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithmss pages 1253-1260, 2018.
O. Besbes, Y. Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations Research, 63 (5):1227-124,, 2015.
S. Bubeck, T. Lee, Y. Li, and M. Sellke. Competitively chasing convex bodies. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 861-868, 2019.
S. Bubeck, B. Klartag, Y. T. Lee, Y. Li, and M. Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1496-1508, 2020.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
N. Cesa-Biande and F. Orabona. Online learning algorithms. Annual Review of Statistics and Its Application, 811):65-1190 2021.
N. Chen, G. Goel, and Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of the 31 Conference on Learning Theory, pages 1574-1594, 2018
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, Jin, and S. Zhu. Online optimization with gradual variations. In Proceedings of the 25th Annual Conference on Learning Theory, pages 6. 6.100, 2012.
A. Cutkosky. Parameter-free, dynamic, and strongly- online learning. Proceedings of the 37th International Conference on Machine Learning, pages 2250-2259, 2020.
11

---

A. Cutkosky and F. Orabona. Black-box reductions for parameter-free freee online learning in Banach spaces. In Proceedings of the 31st Conference On Learning Theory. pages 1493-1529, 2018.
A. Daniely and Y. Mansour. Competitive ratio vs regret minimization: achieving the best of both worlds. In Proceedings of the 30th International Conference Algorithmic Learning Theory, pages 333-368, 2019.
A. Daniely, A. Gonen, and S. Shalev-Shwarde Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning, pages 1405-1411, 2015.
E. Even-Dar, M. Kearns, Y. Mansour, and J. Wortman. Regret to the best regret to the average. In Proceedings of the 20th Annual Conference on Learning Theory, pages 233 227-247,4 2007.
Y. Freund, R. E. Schapire, Y. Singer, and M. K. Warmuth. Using and combining predictors that specialize, In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 334-343, 1997.
Friedman and Linial. On convex body chasing. Discrete & Computational Geometry, 9:293-321 1993.
G. Goel and A. Wierman. An online algorithm for smoothed regression and lqr control. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 2504-2513, 2019.
G. Goel, N. Chen, and A. Wierman. Thinking fast and slow: Optimization decomposition across timescales. In Proceedings of the 56th IEEE Conference on Decision and Control, pages 1291- 1298, 2017.
G. Goel, Y. Lin, H. Sun, and A. Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems 32, pages 1875-1885 1885, 2019.
Gradu, Hazan, and Minasyan. Adaptive regret for control of time-varying dynamics. ArXiv e-prints, arXiv:2007.0453 004993, 2020.
A. György, T. Linder, and G. Lugosi. Efficient tracking of large classes of experts. IEEE Transactions on Information Theory, 58(1 (16709-67233 2012.
E. C. Hall and R. M. Willett. Dynamical models and tracking regret in online convex programming. In Proceedings of the 30th International Conference on Machine Learning, pages 579-587, 2013.
E. Hazan. Introduction online convex optimization. Foundations and Trends in Optimization, 13-4)355 2016.
E. Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium on Computational Complexity, 88, 2007.
E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 393-400, 2009.
E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-199) 2007.
A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference on Artificial Intelligence and Statisties, pages 398-406, 2015.
K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 943-99 951, 2017a.
K.-S. Jun, Orabona, Wright, and Willett. Online learning for changing environments using coin betting. Electronic Journal of Statistics, 11(2):5282-5310. 2017b.
12

---

M. Kapralov and R. Panigrahy. Prediction strategies without loss. ArXiv e-prints, arXiv: 1008.367. 2010.
M. Kapralov and R. Panigrahy. Prediction strategies without loss. In Advances in Neural Information Processing Systems 24, pages 228-836.20 2011.
S.-J. Kim and G. B. Giannakis. Real-time electricity pricing for demand response using online convex optimization. In Proceedings of the 2012 IEEE PES Conference on Innovative Smart Grid Technologies, pages 1-5, 2014.
Y. li and N. Li. Leveraging predictions in smoothed online convex optimization via gradient-based algorithms. In Advances in Neural Information Processing Systems 33, pages 14520-14531, 2020.
Y. Li, G. Qu, and N. Li. Using predictions in online optimization with switching costs: fast algorithm and a fundamental limit. In the 2018 Annual American Control Conference, pages 3008-300 1008-3013,0111
M. Lin, Wierman, L. L. Andrew, and E. Thereska. Dynamic right-sizing for power-proponte proporrrooot data centers. In Proceedings of the 30th IEEE International Conference on Computer Communica- tions, pages 1098-1106, 2011.
M. Lin, Z. Liu, A. Wierman, and L. Andrew. Online algorithms for geographical load balancing. In Proceedings of the 2012 International Green Computing Conference, pages 1-10, 2012.
Y. Lin, G. Goel, and A. Wierman. Online optimization with predictions and non-convex losses. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):18:1-18:33 2020.
N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212 261, 1994.
H. Luo and R. E. Schapire. Achieving all with no parameters: Adanormalhedge. In Proceedings of the 28th Conference on Learning Theory, pages 1286-1304, 2015.
A. Mokhtari, S. Shahrampour, A. Jadbabaie, and A. Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control, pages 7195-7201, 2016.
Orabona and D. Pál. Coin betting and free online learning. In Advances in Neural Information Processing Systems 29, pages 577-585, 2016.
Orabona, Cesa-Bianchi and C. Gentile. Beyond logarithmic bounds in online learning. In Proceedings of the 15th International Conference Artificial Intelligence and Statistics, pages 823-831, 2012.
A. Sani, G. Neu, and A. Lazaric. Exploiting easy data in online optimization. In Advances in Neural Information Processing Systems 27, pages 810-818, 2014.
M. Sellke. Chasing convex bodies optimally. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1509-1518, 2020.
S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Shalev-Shwarzz, Singer, and N. Srebro. Pegasos: primal estimated sub- aub-gradient solver for SVM. In Proceedings of the 24th International Conference on Machine Learning, pages 807-814, 2007.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low-noise and fast rates. Advances Neural Information Processing Systems 23, pages 2199-2207, 2010.
Y. Wan, W.W. Tu, and I.. Zhang Strongly adaptive online learning over partial intervals. SCIENCE CHINA Information Sciences, 65(10))00200,, 2022.
13

---

T. Yang. L. Zhang, R. Jin, and J. Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with and noisy gradient. In Proceedings of the 33rd International Conference on Machine Learning, pages 449,457, 2016.
L. Zhang. Online learning in changing environments. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pages 5178-5182, 2020. Early Career.
L. Zhang, T. Yang, J. Yi, R. Jin, and Z.-H. Zhou. Improved dynamic regret for non-degenerate functions. In Advances Neural Information Processing Systems 30, pages 732-741, 2017.
L. Zhang, S. Lu, and Z.-H. Zhou. Adaptive online learning in dynamic environments. ArXiv e-prints, arXiv: 10815, 15, 2018a.
L. Zhang, S. Lu, and Z.-H. Zhou, Adaptive online learning in dynamic environments, In Advances in Neural Information Processing Systems 31, pages 1323-1333, 2018h.
L. Zhang, T. Yang, R. Jin, and Z.-H. Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning, pages 5882-5891, 2018c.
L. Zhang, T.-Y. Liu, and Z.-H. Zhou. Adaptive regret of convex and smooth functions. In Proceedings of the 36th International Conference on Machine Learning, pages 7414-7423, 2019.
L. Zhang, S. Lu, and T. Yang. Minimizing dynamic regret and adaptive regret simultancously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 309-319, 2020.
I.. Zhang, W. Jiang, S. Lu, and T. Yang. Revisiting smoothed online learning. In Advances in Neural Information Processing Systems 34, pages 13599-13612, 2021a.
Zhang, G. Wang, W.WW. Tu, W. Jiang, and Z.-H. Zhou. Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. In Advances in Neural Information Processing Systems 34, pages 24968-24980, 2021b.
Z. Zhang, A. Cutkosky, and I. C. Paschalidis. Adversarial tracking control via strongly adaptive online learning with memory. In Proceedings the 25th International Conference on Artificial Intelligence and Statistics, pages 8458-8492, 2022.
P. Zhao and L. Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Proceedings of the 3rd Annual Learning for Dynamics and Control Conference, pages 48-59, 2021.
P. Zhao, Y.J. Zhang, L. Zhang, and Z.-H. Zhou. Dynamic regret of convex and smooth functions, In Advances in Neural Information Processing Systems 33, pages 12510-12520, 2020a.
Y. Zhao, Q Zhao, X. Zhang, E. Zhu, X. Liu, and J. Yin. Understand dynamic regret with switching cost for online decision making. ACM Transactions Intelligent Systems and Technology, 11(3), 2020b.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-936. 2003.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? (Yes] See the future work in Section I
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work mainly theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the assumptions in Section 3.2]
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs can be found in Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "ojoyrC9PYb7", "reviewer": "Reviewer_m3LC", "summary": "In this paper, the authors study algorithms for smoothed online convex optimization (SOCO). Compared to classical online convex optimization (OCO), in SOCO the player also suffer a switching cost between rounds depending on how much the iterates changed from one round to another. In this work the authors propose an algorithm the incurs low dynamic and adaptive regret simultaneously. To do so, they instantiate around $O(\\log T)$ instances of online gradient descent with different step-sizes, and combine these algorithms using a technique called \"Discounted-Normal-Predictor\" originally developed for online bit prediction. Their results either match previous guarantees (in the case of adaptive regret), or are the one of the first of its kind for SOCO (for dynamic regret), matching the known lower-bounds up to logarithmic factors.", "questions": "- Could you help me understand which works on bit prediction were with bits on $[-1,1]$ and which ones were on $[0,1]$;\n- Could the authors try to give intuition behind (10)? The presence of $U(n)$ and $\\mu$ make it a bit harder to digest (and maybe with more time to read the paper I'd be able to get the intuition);", "limitations": "The authors do a good discussion, afaik, of related work and how their work can be placed on the literature. Maybe some discussion of computational efficiency/cost of the algorithm would have been interesting, but it certainly is not crucial.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The technique uses in a sleek method from online bit prediction to combine different OCO algorithms. Although this bit prediction method is a bit mysterious, the high-level idea of the final algorithm is well-explained and intuitive;\n- The fact that one single algorithm manages to control both dynamic and adaptive regret simultaneously is neat;\n- The paper is quite well-written, with an excellent literature review\n\n### Weaknesses \n- I noticed the authors did try to explain the main ideas behind the bit prediction strategy, but I had a very hard time parsing the bounds in Theorem 1. This influences later on the understanding of the remainder of the algorithm and the intuition behind some of its construction;\n- I was a bit confused about when the $b_t$'s should be in $[0,1]$ and when they should be in $[-1,1]$. The beginning of sec 2.3 talks about it being in $[-1,1]$. But when describing the work of Daniely and Mansour, the predictions (coming from eq (7) according to Alg 1) end up in $[0,1]$. At the beginning of sec 3.1 the authors also say \"(...) but require the prediction to lie in [0,1] (...)\", what made me believe previous work was mostly on $[-1,1];\n- Related to the confusions above, the remark on line 222 was not quite immediate.\n\n### Minor observations\n- In (9) you use $\\hat{g}$ but never defined it. Was it supposed to be (7)?\n- Line 165: what do you mean that the \"property\" of $g$ has been \"revealed\"?\n- Line 216: you use \"meta-regret\" without defining it, which caused a bit of confusion when I was reading. Maybe something that sounds less formal like \"the difference in the costs between the sub-algorithms and the main one\" would avoid this;\n- In Lemma 1 $\\mathcal{A}$ is the final algorithm and in Algorithm 3 it is the bit prediction algorithm, which is confusing since Lemma 1 is about Algorithm 3;\n- Using $\\cap$ to denote \"AND\" was a bit unusual for me. If other reviewers find it weird as well, consider changing, but it may be just me in this case;\n- It is a bit \"unsettling\" to call a real number a bit; ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QsfBA6LavQk", "reviewer": "Reviewer_itGk", "summary": "This paper proposes a new algorithm based on Discounted-Normal-Predictor to combine multiple experts for SOCO.  First, a modified Discounted-Normal-Predictor (DNP-cu) which uses a conservative update instead of the traditional projected update is proposed as the meta algorithm, followed by the prediction performance bound. Then a combiner based on DNP-cu is proposed to predict the combining weight for multi-expert SOCO. With OGD as the experts, the smoothes OGD in Algorithm 4 combines multiple experts by the proposed combiner. The authors give nearly optimal bounds for both the adaptive regret and dynamic regret for any lambda and any interval.", "questions": "The proposed expert combiner is really interesting and the theoretical results can recover many recent SOCO and even general online optimization works. I like this work while I have some minor questions:\n1. Comparing with the expert combiner for SOCO in Zhang et al. [2021a], the dynamic regret bound of this paper is up to a logarithmic factor. Could the authors discuss more about the comparisons with the combiner in Zhang et al. [2021a]?\n2. I noice that the dynamic regret bound nearly match the lower bound. Is it possible to derive a lower bound regret of the proposed algorithm to show what performance the algorithm can achieve?", "limitations": "The limitations are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality \\& Significance**\n\nAn effective design to better exploit multiple experts in online optimization is really important and desirable. The idea to combine the experts by predicting the combining weight based on DNP-cu is novel and very inspiring. \n\n**Quality**\n\nThe regret analysis in this paper is solid. Both the dynamic regret and the more fundamental adaptive regret are bounded to match the state-of-the-art regret bound.\n\n**clarity**\n\nThe paper is well-written and easy to follow. \n\nTypos:  Line 532 in appendix, Theorem 6,  the output of OGD is $w_t$ in stead of $x_t$?\n\nLine 551 in appendix, Eqn. (47), there should be a sum notation after the first \"$\\leq$\".\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CFx8m28YsCc", "reviewer": "Reviewer_ijEX", "summary": "This paper studies smoothed online convex optimization. In particular, the authors proposed an online GD method with different step size predicted by the discounted normal predictor. The proposed combination is claimed to be simpler than previous literature while maintaining a similar regret bound. ", "questions": "NA", "limitations": "NA", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: This paper is well written and easy to follow. The proposed algorithm is clear and simpler than the previous literature. Merging the DNP into the online gradient descent sounds novel to me.\n\nWeakness: \n1. No experiments are added to justify the advantage of the result. \n2. It would be better demonstrated which role DHP is playing in the main algorithm to better highlight the contribution of this paper.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AgQgkZ_6mWP", "reviewer": "Reviewer_CVs7", "summary": "In this paper, the authors propose a simple algorithm for smoothed online convex optimization (SOCO), which aims to minimize both the hitting cost and the switching cost. The key idea is to use a variant of Discounted-Normal-Predictor to combine different instances of online gradient descent (OGD). Based on the advantageous properties of Discounted-Normal-Predictor and OGD, they prove that the proposed algorithm attains nearly optimal (static and dynamic) regret bounds on every interval, even when the switching cost is present.", "questions": "1. In this paper, the authors choose the $\\ell_2$-norm to measure the switching cost. Can the results be extended to other switching costs such as $\\ell_1$-norm and $\\ell_\\infty $-norm? \n\n2. The switching cost of $u_t$ is ignored in Theorem 4. Please explain the reason.\n\n3. Currently, all the proofs are provided in the supplementary. It'd be better if the authors could highlight the sketch of analysis in the main content.\n\n4. Competitive ratio is a popular performance measure for SOCO. The authors may need to explain why they have not used a competitive ratio.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The writing of this paper is good, and the authors compare their bounds with previous results clearly. The proposed algorithm is the first attempt to simultaneously minimize adaptive regret and dynamic regret.\n\n2. Although the analysis of Discounted-Normal-Predictor is quite involved, after we understand its property (Theorem 1) and usage (Lemma 1), it can be used as a black-box meta-algorithm, and the rest analysis is easy to follow. In this sense, the algorithm/analysis in this paper is simpler than that of Zhang et al. [2021c].\n\n3. The theoretical guarantee of this paper is stronger than existing studies, since the proposed algorithm can minimize the dynamic regret with switching costs in every interval. For comparison, the dynamic regret bound of Zhang et al. [2021a] is non-adaptive, and the adaptive regret bound of Zhang et al. [2021c] only supports static regret.\n\nWeaknesses:\n1. As stated in the abstract, this paper is motivated by Kapralov and Panigrahy [2010] and Daniely and Mansour [2019], and thus the technical novelty is a bit limited. On the other hand, I do admit that the authors have made some modifications in Algorithms 2 and 3.\n\n2. The authors have not discussed the competitive ratio of their algorithm.\n\nSummary:\nAlthough this paper is somehow incremental, the results are new and significant. It is still important to reveal the fact that Discounted-Normal-Predictor can be applied to SOCO and achieves better bounds, which may advance the theoretical and algorithmic developments of SOCO.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept