Revisiting Smoothed Online Learning
Authors: Lijun Zhang
Wei Jiang
Shiyin Lu
Tianbao Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Smoothed online learning
competitive ratio
dynamic regret with switching cost
polyhedral functions
quadratic growth functions

Abstract: In this paper, we revisit the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost, and target two performance metrics: competitive ratio and dynamic regret with switching cost. To bound the competitive ratio, we assume the hitting cost is known to the learner in each round, and investigate the simple idea of balancing the two costs by an optimization problem. Surprisingly, we find that minimizing the hitting cost alone is $\max(1, \frac{2}{\alpha})$-competitive for $\alpha$-polyhedral functions and $1 + \frac{4}{\lambda}$-competitive for $\lambda$-quadratic growth functions, both of which improve state-of-the-art results significantly. Moreover, when the hitting cost is both convex and $\lambda$-quadratic growth, we reduce the competitive ratio to $1 + \frac{2}{\sqrt{\lambda}}$  by minimizing the weighted sum of the hitting cost and the switching cost. To bound the dynamic regret with switching cost, we follow the standard setting of online convex optimization, in which the hitting cost is convex but hidden from the learner before making predictions. We modify Ader, an existing algorithm designed for dynamic regret, slightly to take into account the switching cost when measuring the performance. The proposed algorithm, named as Smoothed Ader, attains an optimal $O(\sqrt{T(1+P_T)})$ bound for dynamic regret with switching cost, where $P_T$ is the path-length of the comparator sequence. Furthermore, if the hitting cost is accessible in the beginning of each round, we obtain a similar guarantee without the bounded gradient condition, and establish an $\Omega(\sqrt{T(1+P_T)})$ lower bound to confirm the optimality.

Revisiting Smoothed Online Learning
Lijun Zhang Wei Jiang', Shiyin Lu', Tianbao Yang²
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China "Peng Cheng Laboratory, Shenzhen, Guangdong. China 3 Department of Computer Science, The University of lowa, lowa City, IA 52242, USA {zhanglj, jiangw, Lusy>0lamda anj.aaaaa.......a.a..a.......u edu. cn, tianbao-yange Sunbbo-yyanghuiowa.cco edu
Abstract
In this paper, we revisit the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost, and target two per- formance metrics: competitive ratio and dynamic regret with switching cost. To bound the competitive ratio, we assume the hitting cost is known to the learner in each round, and investigate the simple idea of balancing the two costs by optimization problem. Surprisingly, we find that minimizing the hitting cost alone is max(1, >-copetiitive for a-polyhedral functions and X c-mopettiiive for X-quadratic growth functions, both of which improve state-of-the-ar results signi- ficantly. Moreover, when the hitting cost is both convex and X-quadratic growth, we reduce the competitive ratio to 1 + 2
7x. by minimizing the weighted sum of the hitting cost and the switching cost. To bound the dynamic regret with switching cost, we follow the standard setting of online convex optimization, in which the hitting cost is convex but hidden from the learner before making predictions. We modify Ader, an existing algorithm designed for dynamic regret, slightly to take into account the switching cost when measuring the performance. The proposed al- gorithm, named as Smoothed Ader, attains an optimal O ((VT(1 + Pr)) bound for dynamic regret with switching cost, where Pr is the path-length of the comparator sequence. Furthermore, if the hitting cost is accessible in the beginning of each round, we obtain a similar guarantee without the bounded gradient condition, and establish an 2i ((VT((1 Pr)) lower bound to confirm the optimality.
Introduction
Online learning is the process of making sequence of predictions given knowledge of the answer previous tasks and possibly additional information [Shalev-Shwarzz 2011]. While the traditional online learning aims make the prediction as accurate possible, in this paper, we study smoothed online learning (SOL), where the online learner incurs a switching cost for changing its predictions between rounds (Cesa-Bianchi many real-world applications, a change of action usually brings some additional cost. Examples include the dynamic right-sizing for data centers [Lin al.) [011]] geographical load balancing [Lin et al. 2012). real-time electricity pricing [Kim and Giannakis [2014), video streaming [Joseph and
al. 2013). SOL has received lots of attention recently because in
de Veciana 2012]. spatiotemporal sequence prediction [Kim et al. 2015), multi-timescale control [Goel et al. 2017 and thermal management [Zanini et al. 2010]
sequence of consecutive rounds, where round the learner is asked to select point x, from the decision set X', and suffers hitting cost fx Depending on the performance metric, the learner may be allowed to observe fe(-) when making decisions, which is different from the traditional online learning in which fe(-) is revealed to the learner after submitting the decision m x for changing decisions between successive rounds. The switching cost m m(x;, x;-1)
Specifically, SOL is performed
and Lugosi] 2006). Additionally, the learner also incurs switching cost
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

could be any distance function, such as the fz-norm distance -x--x(111 and the squared -n-m distance ||x, x /2 [Goel et al,, 2019). In the literature, there are two performance metries for SOL: competitive ratio and dynamic regret with switching cost.
Competitive ratio is popular in the community of online algorithms [Borodin and EI- Yaniv, 1998). It is defined as the worst-case ratio of the total cost incurred by the online learner and the offline optimal cost:
Et (f((x)) + m(x;, X; 1))
(I)
minl,: Us..., EX Et= (fr(us) (u:) + m(ue u)-1)
When focusing on the competitive ratio, the learner can observe fe(.) before picking x₃- The problem is still nontrivial due to the coupling created by the switching cost. On the other hand, dynamic regret with switching cost is generalization of dynamic regret-a popular performance metric in the community of online learning [Zinkevich] 2003). It is defined as the difference between the total cost incurred by the online learner and that of an arbitrary comparator sequence uo, M....., Ur X::
T Σ (fi(x)) + m(x,,
T
(fr(we) + mu(,, u,-1)).
(2)
Different from previous work [Chen et al. 2018 Goel et al. 2019). we did not introduce the
minimization operation over Uo. ,I,..., ur (2) The reason is that we want to bound ( by certain regularities of the comparator sequence, such as the path-length
(u up,..., ur) = Σ l u-
(3)
When focusing on (2) fe(-) is generally hidden from the learner before submitting x, The conditions for bounding the two metrics are very different, so we study competitive ratio and dynamic regret with switching cost separately. To bound the two metries simultancously, refer to Andrew et al. 2013) and Daniely and Mansour 2019]. especially the meta-algorithm in the latter work.
This paper follows the line of research stemmed from online balanced descent (OBD) [Chen et al. 2018, Goel and Wierman 2019]. The key idea of OBD to find an appropriate balance between the hitting cost and the switching cost through iterative projections. It has been shown that OBD and its variants are able to exploit the analytical properties of the hitting cost (e.g., polyhedral, strongly convex) to derive fimension-free competitive ratio. At this point, it would be natural to ask why not use the greedy algorithm, which minimizes the weighted sum of the hitting cost and the switching cost in each round, i.e..
min x
fe(x) + (mm(x, xx-1)
(4)
to balance the two costs, where 7 2 is the trade-off parameter. We note that the greedy algorithm is usually treated as the baseline in competitive analysis [Borodin and El- Yaniv 1998]. but its usage for smoothed online learning quite limited. One result is given by Goel et al. 2019]. who demonstrate that the greedy algorithm as a special case of Regularized OBD (R- (R-OBD), is optimal for strongly convex functions. Besides, [Lin et (2020) have analyzed the greedy algorithm with y 0. named as the naive approach below, for poly hhedral functions and quadratic growth functions.
In this paper, we make the following contributions towards understanding the greedy algorithm.
For a-polyhedral functions, the competitive ratio of the naive approach is max (1, 2), which is a significant improvement over the 3 + competitive ratio of OBD [Chen et al. 2018 and the 1 1 2 ratio proved by Lin et al. [2020] Lemma 1]. When a > 2, the ratio becomes
1. indicating that the naive approach is optmal in this scenario.
For X-quadratic growth functions, the competitive ratio of the naive algorithm is 1 +
which matches the lower bound of this algorithm [Goel et al. 2019 Theorem 5], and x better than the max(1 + 6 2.4) ratio obtained by Lin et al. [2000 Lemma 1].
If the hitting cost is both convex and X-quadratic growth, the greedy algorithm with y > attains 1 + 3x competitive ratio, which demonstrates the advantage of taking the switching
cost into considerations. Our 1 1+ 2 ratio is on the same order as Greedy OBD Goel et al. 2019 Theorem 3] but with much smaller constants.

---

Our analysis of the naive approach and the greedy algorithm is very simple. In contrast, both OBD and Greedy OBD rely on intricate geometric arguments.
While both OBD and R-OBD are equipped with sublinear dynamic regret with switching cost, they unsatisfactory in the following aspects:
The regret of OBD depends on an upper bound of the path-length instead of the path-length
itself [Chen et al. 2018 Corollary 11], making it nonadaptive.
The regret of R-OBD Is adaptive but it uses the squared f2-norm to measure the switching
cost, which may not be suitable for general convex functions (Goel et al. 2019 |
Both OBD and R-OBD observe f(()) before selecting x which violates the convention of online learning.
To avoid the above limitations, we demonstrate that a small change of Ader (Zhang et al. 201 8a
which is an existing algorithm designed for dynamic regret, is sufficient to minimize the dynamic regret with switching cost under the setting of online convex optimization (Shalev-Shwart/ 2011]. Ader runs multiple online gradient descent (OGD) [Zinkevich] 2003) with different step sizes as expert-algoritmms, and uses Hedge [Freund and Schapire 1997 as the meta-algorithm to aggre- gate predictions from experts. The only modification is to incorporate the switching cost into the loss of Hedge. The proposed algorithm, named as Smoothed Ader (SAder), attains the optimal O(TT(L+ + Pr)) dynamic regret, where Pr is the path-length defined in (3). Thus, our regret bound is adaptive because it automatically becomes small when the comparators change slowly. Finally, also investigate the case that the hitting cost is available before predictions, and establish a similar result without the bounded gradient condition. To this end, we design lookahead version of SAder, which chooses the greedy algorithm in 4 as the expert and utilizes the cost of the current round in Hedge. To show the optimality of this algorithm, we further establish an 22( (2(TT(11 + Pr)) lower bound under the lookahead setting.
2 Related work
This section reviews related work on smoothed online learning (SOL) and dynamic regret.
2.1 Smoothed online learning
SOL has been investigated under the setting of multi multii-armed bandits Aggawal et al. 1990 Guha and Munagala 2009 Dekel et al., 2014 Koren al. 2017a b), prediction with expert advice [Cesa Bianchi et al. 2013]. and online convex optimization [Lin et al. [ Bansal et al. 2015 Zhao et al. 20206 In the following, we mainly discuss smoothed online convex optimization (SOCO).
The early works on SOCO focus on designing competitive algorithms in the low-dimensional setting [Lin et al.) 2011]. In particular, [ansal et al. (2015) show that for SOCO the real line, the competitive ratio can be upper bounded by 2. which is proved to be optimal (Antoniadis and Schewworr 2018). They also establish competitive ratio of 3 under the memoryless setting. In the study of SOCO, it is common to assume that the learner has access to predictions of future hitting
costs. and several algorithms (Lin et al. 20122 Chen et al., 2015 2016 Li et al., 2018 Li and Li 2020) have been developed based on receding horizon control (RHC) Kwon and Han, (2005). In fact, the greedy algorithm in 44) can be treated
variant of RHC. However, previous results for RHC are limited to special problems, and (4) remains under-explored. For example, when the learner can observe the next W hitting costs, [i et al. (0188 demonstrate that both the competitive ratio and the dynamic regret with switching cost decay exponentially fast with W. But their analysis relies on very strong conditions, including strong convexity and smoothness.
One milestone is the online balanced descent (OBD) [Chen et al. 2018), which has dimension- free competitive ratio even when the learner can only observe the hitting cost of the current round. Specifically, OBD iteratively projects the previous point onto a carefully chosen level set of the hitting cost so as to balance the switching cost and the hitting cost. When the hitting cost is a-polyhedral and convex, and the switching cost is the lg fg-norm distance, OBD attains a 3 + & competitive ratio. Furthermore, OBD can also be tuned control the dynamic regret with switching cost. Let L be
We usually assume the convex function is Lipschitz continuous, and in this case choosing the fn-norm distance as the switching cost makes it on the same order the hitting cost.
3

---

an upper bound of the path-length of the comparator sequence, i.e.. Pr ui...., ur) S L. al. [2018] Corollary 11] have proved that
Chen
T
(f((x)) + +|x -
-x(x-xx(11]) -xx
min
(fe(we) + llu 110--u-1llly u--1ll 0 (V(TL)
(5)
Pr 1
leading to sublinear regret when L o(T). However, the upper bound is nonadaptive because depends on L instead of the actual path-length Pr.
Later, Goel and Wierman (019) demonstrate that OBD is 3 + ) ccompetitive for X-strongly convex functrons, when the switching cost is set to be the squared ---norm distance. In a subsequent work, [ool et al. [2019] Theorem 4] propose Regularized OBD (R-OBD), which improves the
competitive ratio to
V + X matching the lower bound of strongly convex functions exactly
[Goel et al. 2019 Theorem I]. R-OBD includes (4) as a special case, which also enjoys the optimal competitive ratio for strongly convex functions. Furthermore, Goel et al. [2019] Theorem 6] have
analyzed the dynamic regret of R-OBD and the following result can be extracted from that paper
T Σ
(1
Σ fxxx)) + 2 ||,,, x,- x1-111
f((u,)
1 fillu u. u.-111 =0
(
T Σ
u u 11
Compared with (). this bound adaptive because the upper bound depends on the switching cost of the comparator sequence. However, it chooses the squared fz-norm as the switching cost, which may not be suitable for general convex functions. When the hitting cost is both quasiconvex and quadratic growth, Goel al. 2019 Theorem 3] have demonstrated that their Greedy OBD algorithm attains an O(1/v X) competitive ratio, as X + O.
Lin et al. [2020] have analyzed the naive approach which ignores the switching cost and simply minimizes the hitting cost in each round, i.c., the greedy algorithm with y = 0. is a bit surprising that this naive approach is + 2 --oomettitive for a-polyhedral functions and max + 4) c-mpetiiiive
for X-quadratic growth functions, without any convexity assumption [Lin et al. 2020 Lemma 1]. Argue al. [220aa] have investigated a hybrid setting in which the hitting cost is both X-strongly convex and //-mooohh but the switching cost is the f--norm distance instead of the squared one.
They develop Constrained OBD, and establish 4 + 4/2H/A X competitive ratio. However, their analysis relies on strong condition that the hitting cost is non-negative over the whole space, i.e., minxeR4 (x) 0, as opposed to the usual condition minxex fi(x) = 0.
Finally, 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 20200] In this problem, the online learner receives sequence of convex bodies .i..... Xr R and must
select one point from each body, and the goal is to minimize the total movement between consecutive output points. Apparently, we can treat CBC as special case of SOCO by defining the hitting cost (e) as the indicator function of X, which means that the domains of hitting costs are allowed to be different. On the other hand, we can also formulate a d-dimensional SOCO problem as a d + 1-dimensional CBC problem [Lin et al.) 2020 Proposition 1J. For the general setting of CBC, the competitive ratio exhibits a polynomial dependence on the dimensionality, and the state-of-the-an result is O O (d, /d log I')) AArgu et al. 2020b Sellke 2020j. which nearly match the 2( lower bound [Friedman and Linial 1993]. Our paper aims derive wewnssiinaltt-indeeeeeeeee competitive ratios and sublinear dynamic regret for SOCO, under appropriate conditions.
2.2 Dynamic regret
Recently, dynamic regret has attained considerable interest in the community of online learning (Zhang 2020]. The motivation of dynamic regret is to deal with changing environments, in which the optimal decision may change over time. It is defined as the difference between the cumulative loss of the learner and that of sequence of comparators ui..... ur E X:
T
T
D-Regret(ui.... UT)
fi(x))
Σ fe(w.). 1=1
(6)
1=1

---

In the general form of dynamic regret, U1 My could be an arbitrary sequence Zinkevich 2003
Hall and Willett 2013 Zhang et al. 2018a
2020 Cutkosky, 2020 Zhao al. 2020a and the
restricted form, they are chosen as the minimizers of online functions, 1.e., u, xrgmin (x)
[Jadbabaie et al. 2015 Besbes et al. 2015 Yang et al.
et al. 2016 Zhang et al. 2017]
2018b Wan et al. ( and Zhang 2021]. While it is well-known that sublinear dynamic regret is unattainable the worst case, one can bound the dynamic regret in terms of some regularities of the comparator sequence. An instance is given by Zinkevich [2003] who introduces the notion of
path-length defined in (3) to measure the temporal variability of the comparator sequence, and derives an (VVT(1 + Pr)) bound for the dynamic regret of OGD. Later, Zhang et al. [2018a] develop adaptive learning for dynamic environment (Ader), which achieves the optimal O ( + Pr)) dynamic regret. In this paper, we show that a small change of Ader attains the same bound for dynamic regret with switching cost.
3 Competitive ratio
In this section, we focus on competitive ratio. Without loss of generality, we assume the hitting cost is non-negative, since the competitive ratio can only improve if this is not the case.
3.1 Polyhedral functions
We first introduce the definition of polyhedral functions.
Definition
A function f()) X + T. with minimizer v is a-polyhedral if
f(x) - f(v) 2 alIx vll, E
(7)
We note that polyhedral functions have been used for stochastic network optimization [Huang and Neely 2011 and geographical load balancing [Lin et al. 2012).
Following Chen et al. 20088), set the switching cost m(x,, x, ||x; x Intuitively, we may expect that the switching cost should be taken into consideration when making decisions. However, our analysis shows that minimizing the hitting cost alone yields the tightest competitive ratio so far. Specifically, we consider the following naive approach that ignores the switching cost and selects
X = argmin fe(x).
(8)
xeX
The theoretical guarantee of (8) is stated below.
Theorem Suppose each fe(-) X + R with minimizer v, is a-polyhedral. We have
Σ (f(())) + 1|xc x1-1 S max (1, Σ (f((w)) + || - -u-1ll), Vug. Ui...., up E X 1=1
where we assume Xo Ug-
Remark: Our max(1, 2) competitive ratio is much better than the 3 ratio of OBD Chen et al.
2018), and also better than the 1 ratio established by Lin et al. [2020] for (8). When > 2, the ratio becomes 1, indicating that the naive approach is optimal in this scenario. Furthermore, the proof of Theorem D is much simpler than that of OBD, and refines that of Lin al. 2020 Lemma 1].
We have analyzed the greedy algorithm 4 with 7 > O, but the competitive ratio does not improve. So, the current knowledge suggests that there is no need to consider the switching cost when facing polyhedral functions. It is unclear whether this is an artifact of our analysis or an inherent property, and will be investigated in the future. Due to space limitations, all the proofs are deferred to the supplementary.
3.2 Quadratic growth functions
In this section, we consider the quadratic growth condition.
5

---

max Definition 2 A function f() : + R with minimizer v is X X-quadratic growth if
X -(x) - f(v) 2 2 ||--v| - vIl V
The quadratic growth condition has been exploited by the optimization community [Druvvyasskiy
and Lewis 2018 Necoara et al. 2019 to establish linear convergence, and this condition is weaker
than strong convexity Hazan and Kale 2011].
Following Goel al. 2019]
x 113/2. We also set the switching cost m(x,, Xx-1) = ||x, -
consider the naive approach in (8) and have the following theoretical guarantee.
Theorem Suppose each (a(-) X + R with minimizer is X-quadratic growth. We have
1 Σ (1(x)) + 2 |xx -1x--xx-11 x1
1 =11lu fake-u--1? -1l111
fe(we) (0m)))+(100
for all uo, ui...., ur E X, where we assume X0
Ug-
The above theorem implies that the naive approach achieves competitive ratio of 1 + 4 which matches the lower bound of this algorithm [Goel et al. [2019] Theorem 5]. Furthermore, it is also much better than the max(1 L. 4) ratio established by Lin al. [2020] for (8). Similar the case of polyhedral functions, it seems safe to ignore the switching cost here.
Remark:
X-
3.3 Convex and quadratic growth functions
When fe(-) is both quasiconvex and X-quadratic growth, Goel et al. [2019] have established an O(1/VA) competitive ratio for Greedy OBD. Inspired by this result, introduce convexity to further improve the competitive ratio. In this case, the switching cost plays a role in deriving tighter competitive ratios. Specifically, we choose the greedy algorithm with y 0 to select Xx, i.e.,
(fx(x) + 3 21 xx-1
X argmin xEX
(10)
The theoretical guarantee of 110 stated below.
Theorem Suppose the domain X convex, and each fe(-) X I with minimizer Vt. X-quadratic growth and convex. By setting 7 = A/(2 + VA). we have
Σ [((xx)) + 1 -1 x-- x
2
1 - u--1l²) fc(us) +
1
for all Lo; u1..... ur E X, where assume X1) Ug-
The above theorem shows that the competitive ratio is improved to + 2 under the additional convexity condition. According the lower bound of strongly convex functions [Goel et al. 2019. Theorem 1]. the ratio in Theorem 3 optimal up to constant factors. Compared with Greedy OBD [Goel et al. 2019 Theorem 3], assumption is slightly stronger, since require convexity instead of quasiconvexity. However, our algorithm and analysis are much simpler, and the constants our bound much smaller.
Remark:
vx.
4 Dynamic regret with switching cost
When considering dynamic regret with switching cost, we adopt the common assumptions of online convex optimization (OCO) (Shalev-Shwartz 2011].
Assumption All the functions fü 's are convex over their domain X.
Assumption The gradients of all all functions are bounded by G, i.e.,
[t()]] < G, Vt E [T]. xEX
(II)

---

Algorithm SAder:
Meta-algorithm
Require: A step size and set H containing step sizes for experts
1: Activate a set of experts { {E>(y E H) by invoking the expert-algorithm for each step size v) E H.
2: Sort step sizes in ascending order 7h S 122 S ... S 7N, and set w(" = [(+1]
3: for t .,,,,, do
4: Receive x from each expert E7
5: Output the weighted average x; = E mEn "
6: Observe the loss function Si(.))
7: Update the weight of each expert by (14
8: Send gradient (xx) to each expert E"
9: end for
Assumption 3 The diameter of the domain X is bounded by D, i.e.,
max x.x' EX
|| xxI D.
(12)
Assumption iimplie that the hitting cost is Lipschitz continuous, so it is natural to set the switching cost as v Xt, Xt-1) ||x, xt-1
4.1 The standard setting
We first follow the standard setting of OCO in which the learner can not observe the hitting cost when making predictions, and develop an algorithm based on Ader (Zhang et al.) [018a]. Specifically, we demonstrate that small change of Ader, which modifies the loss of meta-algorithm to take into account the switching cost of experts, is sufficient to minimize the dynamic regret with switching cost. Our proposed method named as Smoothed Ader (SAder), and stated below
Meta-algorithm The meta-algorithm is similar to that of Ader (Zhang et al. 2018a| Algorithm 3,, and summarized in Algorithm | The inputs of the meta-algorithm are its own step size B, and of step sizes for experts. In Step I, we active set of experts {E>|n E H} by invoking the expert-algorithm for each E H. In Step 2, we set the initial weight of each expert. Let f); be the i-th smallest step size in H. The weight of E is chosen as
and C= 1
W1
(13)
i(i + 1)"
[7]]
In each round, the meta-algorithm receives set of predictions {xx] In E H) from all experts (Step 4), and outputs the weighted average (Step 5):
Σ wFx
X₁
MEH
where w is the weight assigned to expert E", After observing the loss function, the weights of experts are updated according to the exponential weighting scheme (Step 7) |Cesa-Bianchi and Lugosi 2006
w/ee-Bta -(,()
w E (xxx))(( (x.)
(14)
where
4(x7) = (VI((x)),
|x
x2-1l-
(15)
When set x for all n E H. As can be seen from 15 we incorporate the switching cost | x |l of expert E" to measure its performance. This is the only modification made to
Ader. In the last step. we send the gradient V (x(: to each expert E so that they can update their own predictions.
In concurrent work Zhao et al. 2021 independently develop similar algorithm for OCO with memory.
7

---

Algorithm 2 SAder: Expert-algorithm
Require: The step size ?)
1: Let x" be any point in X'
2: for t = ...... T do
3: Submit x" to the meta-algorithm
4: Receive gradient (x((x, from the meta-algorithm
5:
x
7xx [x [[())(
6: end for
The expert- allorrta is the same as that of Ader Zhang et al. 2018a Algorithm 4]. which is OGD over the linearized loss or the surrogate loss
Expert-algorithm
sx(x) (Vf((x)), x
(16)
For the sake of completeness, we present its procedure in Algorithm 2 The input of the expert is its step size 7). In Step 3 of Algorithm 2 each expert submits prediction x" the algoriagg and receives the gradient V fr (xx) in Step 4. Then, in Step 5, it performs gradient descent
x
IIx [x"
7/ (x)))
get the prediction for the next round. Here, x [+] denotes the projection onto the nearest point in X.
We have the following theoretical guarantee.
Theorem Set
D2 T(G² + 2G)
H
{ 11 = 2 2
V
i
(17)
where
2
2 log, (1 27')
1, and 3
(2G + 1)D V
5T
in Algorithm
7
Under Assumptions
2 and 3 for any comparator sequence Up
ur E X,
SAder satisfies
T
T
f((x)) + ||x: - -x xx-1ll
Σ
fi(u:)
(18)
1=1
3
T(G2 +2)
D2 + 2D
Σ
|u
un-211 (2G + (2C+1)Dg
5T 8
+ 2n + 1)]
2
1=1
=0
(VT(1+ + VT(1 + log log Pr)) = =0 =O(TT(I+ +P))
where we define Xy = 0, and
2Pr
k
loga
1+
+
(19)
D
Remark: Theorem shows that SAder attains an O(vT(1 ( Pr)) bound for dynamic regret with switching cost, which is on the same order as that of Ader for dynamic regret. From the
2 ((VT(1 + Pr.) lower bound of dynamic regret (Zhang et al. 201 Theorem 2], we know that our upper bound is optimal up to constant factors. Compared with the regret bound of OBD in (5) [Chen et al. 2018), the advantage of SAder is that its regret depends on the path-length Pr directly. and thus becomes tighter when focusing on comparator sequences with smaller path-lengths. Finally, note that in (88) we did not minus the switching cost of the comparator sequence, i.e., Pr. that is because it is always smaller than / DT Pr) and does not affect the order.

---

Algorithm 3 Lookahead SAder: Meta-algorithm
Require: A step size and set H containing step sizes for experts
1: Activate a set of experts {E*(n E H) by invoking the expert-algorithm for each step size v) E H.
2: Sort step sizes in ascending order 7 I 122 S ... S 7N, and set w 1(+1)
3: for t== .,,,, I" do
4: Observe the loss function f(()) and send each expert E
5: Receive x from each expert E"
6: Update the weight of each expert by 20)
7: Output the weighted average x, ME x/x
8: end for
Algorithm 4 Lookahead SAder: Expert-algorithm
Require: The step size ? ......,T' 1,...., do
1: for =
2: Receive the loss fa(-) from the meta-algorithm
3: Solve the optimization problem in (21) to obtain x!
4: Submit x to the meta-algorithm
5: end for
4.2 The lookahead setting
It is interesting to investigate whether this case, we propose a lookahead version SAder, and demonstrate that the regret bound remains on the same order, but Assumption 2 can be dropped. That is, the gradient of the function could be unbounded, and thus the function could also be unbounded.
do better if the hitting cost is available before predictions.
Meta-algorithm
We design a lookahead version of Hedge, and summarize it in Algorithm Compared with Algorithm make the following modifications.
In the t-th round, the meta-algorithm first sends fe(-) all experts so that they can also benefit from the prior knowledge of fx(-) (Step 4).
After receiving the prediction from experts (Step 5), the meta-algorithm makes use of f((-) to determine the weights of experts (Step 6):
w/ En w 1 (L,(x))
(20)
where (x²)) is defined in 15
Expert-algorithm
exploit the hitting cost of the current round, we choose an instance of the greedy algorithm in (4) as the expert-algorithm, and summarize it in Algorithm 4 The input of the expert its step size 77. After receiving fe(-) (Step 2), the expert solves the following optimization problem to obtain x" (Step 3):
min xEN
fa(x)
||x 113
(21)
2n
We have the following theoretical guarantee of the lookahead SAder.
Theorem Ser
D2
?i = 20-1
V
(22)
T
where
1 2
log, (1 + 2T)
+ 1, and 3 = D V T
2

---

in Algorithm| 3 Under Assumptions for any comparator sequence Up ui..... ur E A, the lookahead SAder satisfies
[e(xx)) ((xe)+(xxxx0 1xc- Σ fe(u.)
3
T Σ
- 1-1ll) + pV. T
T(D2 + +2D
[1 21n(k + 1)]
2
2
t=1
=0 [VT(1+ + Pr) V Pr)) =0 -00)==0((((t (VT(L Pr))
where 0, and k is defined in 19)
Remark: Similar to SAder, the lookahead SAder also achieves an Oly Pr) bound for dynamic regret with switching cost. In the lookahead setting, we do not need Assumption 2 any more, and the constants in Theorem are independent from
Lower Bound To show the optimality of Theorem 5 we provide the lower bound of dynamic regret with switching cost under the lookahead setting.
Theorem For any online algorithm with lookahead ability and any T E [o, TD, there exists sequence functions fi...., fr and sequence of comparators u1..... ur satisfying Assumptions] 7 andBsuch that (i) the path-length of U1....y Uy is at most T and (ii) the dynamic regret with switching cost W.E.t UI...., uy is at least 9 (DV + +D)).
Remark:
The above theorem indicates D2 T(1 + Pr)) lower bound, which implies that the lookahead SAder is optimal up to constant factors. Thus, even in the lookahead setting, it is impossible to improve the O(1T(1 + Pr)) upper bound.
Conclusion and future work
We investigate the problem of smoothed online learning (SOL), and derive constant competitive ratio or sublinear dynamic regret with switching cost. For competitive ratio, we demonstrate that the naive approach, which only minimizes the hitting cost, is max(1, >ccompettie for a-polyhedral functions and X- --oopetiitive for X-quadratic growth functions. Furthermore, greedy algorithm, which minimizes the weighted sum of the hitting cost and the switching cost, is VX -competitive for convex and X-quadratic growth functions. For dynamic regret with switching 1 1+ 2
show that the
cost, we propose smoothed Ader (SAder), which attains the optimal O O(vT(1 + Pr)) bound. We also develop lookahead version of SAder to make use of the prior knowledge of the hitting cost, and establish an 22 (TVI(( - Pr)) lower bound.
The research on SOL is still on its early stage, and there are many open problems.
Although we can upper bound the sum of the hitting cost and the switching cost, we do not have direct control over the switching cost. However, in many real problems, there may exist a hard constraint on the switching cost, motivating the study of switch-constrained online learning, in which the times of switches are limited [Altschuler and Talwar 2018 [Chen et al. 2020 It would be interesting to investigate how to impose a budget on the switching cost Wang et al. 2021].
2. This work investigates competitive ratio and dynamic regret with switching cost separately.
To bound the two metrics simultancously, one possible way is to create experts which are designed for competitive ratio and dynamic regret with switching cost respectively, and then
aggregate their predictions by the meta-algorithm of Daniely and Mansour (2019 Algorithm
2]. But we need to assume the hitting cost is bounded, because that meta- mlga--lgo cannot make use of the lookahead ability.
3. As aforementioned, for polyhedral functions and quadratic growth functions, the best competitive ratio is obtained by the naive approach which ignores the switching cost, and this fact is counterintuitive. To better understand the challenge, it is important to reveal the lower bound of polyhedral functions and quadratic growth functions.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Yuxuan Xiang for discussions about Theorem Funding in direct support of this work: NSFC grant 62122037 and 61921006, JiangsuSF grant BK20200064.
References
R. Agrawal, M. Hegde, and D. Teneketzis. Multi-armed bandit problems with multiple plays and switching cost. Stochastics and Stochastic Reports, 29(4):437 459, 1990.
Altschuler and K. Talwar. Online learning over a finite action set with limited switching. In Proceedings of the 31st Annual Conference on Learning Theory, pages 1569-1573, 2018.
L. Andrew, Barman, K. Ligett, M. Lin, A. Meyerson, Roytman, and A. Wierman. A tale of two metries: Simultancous bounds on competitiveness and regret. In Proceedings of the 26th Annual Conference on Learning Theory, pages 741-763, 2013.
A. Antoniadis and K. Schewior. tight lower bound for online convex optimization with switching costs. In Approximation and Online Algorithms, pages 164-175, 2018 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 Informatccs, pages 68-81, 2016.
C. Argue, Bubeck, M. B. Cohen, A. Gupta, and Lee. A nearly-linear bound for chasing nested convex bodies. In Proceedings of the 30th Annual ACM-SIAN 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, 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.
N. Bansal, A. Gupta, R. Krishnaswamy, K. Pruhs, K. 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ás, G. Koumoutsos, and S. W. Umboh. Nested convex bodies are chaseable, In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1253-1260, 2018
O. Besbes, Y. Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations Research, 63 25):1227-1244, 2015.
A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
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-866 2019.
S. Bubeck, B. Klartag, Y. T. Lee, Y. Li, and M. Selkke. Chasing nested convex bodies nearly optimally. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1496-1508, 2020.
N. Resa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
N. Cesa-Bianchi, O. Dekel, and Shamir. Online learning with switching costs and other adaptive adversarics. In Advances in Neural Information Processing Systems 26, pages 1160-1168, 2013.
11

---

L. Chen, Q. Yu, H. Lawrence, and A. Karbasi. Minimax regret of switching consttrinnnd online convex optimization: No phase transition. Advances in Neural Information Processing Systems 33, pages 3477-3486, 2020.
N. Chen, A. Agarwal, A. Wierman, S. Barman, and L. L. Andrew. Online convex optimization using predictions. Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 191-204, 2015.
N. Chen, J. Comden, Z. Liu, A. Gandhi, and A. Wierman. Using predictions in online optimization: Looking forward with an eye on the past. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, pages 193-206, 2016.
N. Chen, G. Goel, and A. Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of the 31st Conference on Learning Theory, pages 1594, 2018.
T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, second edition, 2006.
A. Cutkosky. Parameter-fie free,, dynamic, and strongly-adaptive online learning. In Proceedings of the 37th International Conference on Machine Learning, pages 2250-2259, 2020.
A. Daniely and Y. Mansour. Competitive ratio vs regret minimization: achieving the best of both worlds. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, pages 333-368, 2019.
O. Dekel, J. Ding, T. Koren, and Y. Peres. Bandits with switching costs: 12/3 regret. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 459-467, 2014.
D. Drusvyatskiy and S. Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43(3):919-994 2018.
J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57(3): 592-606, 2012.
Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-139 1997.
J. Friedman and N. Linial. On convex body chasing. Discrete & Computational Geometry, 9:293-321, 1993.
G. Goel and Wierman. An online algorithm for smoothed regression and lqr control. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 1504-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. In Advances in Neural Information Processing Systems 32, pages 1875-1885 2019.
S. Guha and K. Munagala. Multi-armed bandits with metric switching costs. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming, pages 496-507, 2009.
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 and S. Kale. Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. In Proceedings of the 24th Annual Conference on Learning Theory, pages 421-436, 2011.
12

---

L. Huang and M. J. Neely. Delay reduction via lagrange multipliers in stochastic network optimization. IEEE Transactions on Automatic Control, 56(4):842-857) -57422--77777 2011.
A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, pages 398-406; 4066, 2015.
V. Joseph and G. de Veciana. Jointly optimizing multi-uses -ueli rate adaptation for video transport over wireless systems: beean-fairness-variabbill tradeoffs. In Proceedings of the 31 Annual IEEE International Conference Computer Communications, pages 567-575, 2012.
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 Innovative Smart Grid Technologies, pages 1-5, 2014.
T. Kim, Y. Yue, S. Taylor, and I. Matthews. A decision tree framework for spatiotemporal sequence prediction. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 577-586, 2015.
Koren, R. Livni, and Y. Mansour. Multi- bandits with metric movement costs, In Advances in Neural Information Processing Systems 30, pages 4119-4128. 2017a.
T. Koren, R. Livni, and Y. Mansour. Bandits with movement costs and adaptive pricing. In Proceedings of the 30th Annual Conference on Learning Theory, pages 1242-1200 2017b.
W. H. Kwon and S. Han. Receding Horizon Control. Springer, 2005.
Y. Li and N. Li. Leveraging predictions 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 -008-3013, 2018
M. Lin, A. Wierman, L. L. Andrew, and E. Thereska. Dynamic right-sizing for power-proportioal data centers. In Proceedings of the 30th IEEE International Conference on Computer Communica- tions, pages 1098-1106, 106, 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:32 2020.
A. Mokhtari, S. Shahrampour, A. Jadbabaie, and A. Ribeiro. Online optimization dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control, pages 7195-7201, 2016.
I. Necoara, Y. Nesterov, and F. Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1))69-007, 2019.
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.
Y. Wan, B. Xue, and L. Zhang. Projection-free online learning in dynamic environments. In Proceedings of the 35th AAAI Conference Artificial Intelligence, pages 10067-10075. 2021. 2021.
G. Wang, Y. Wan, T. Yang, and I.. Zhang. Online convex optimization with continuous switching constraint. In Advances in Neural Information Processing Systems 34, 2021.
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.
F. Zanini, D. Atienza, G. De Micheli, and S. P. Boyd. Online convex optimization-base algorithm for thermal management of mpsocs. In Proceedings of the 20th Symposium on Great Lakes Symposium VLSI, pages 203-208, 2010.
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.
Zhang, Lu, and Z. Zhou, Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, pages 1323-1333, 201 8a.
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, 2018b.
L. Zhang, S. Lu, and T. Yang. Minimizing dynamic regret and adaptive regret simultaneously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 309-319, 2020.
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 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.
Zhao, Y.-.. Wang, and Z.-H. Zhou. Non-stationary online learning with memory and non-stochastic control. ArXiv e-prints, arXiv:2102.03758. 2021.
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 on 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-938 2003.
14


Reviews:
[{"review_id": "iNTejGqIv_", "reviewer": "Reviewer_Njc7", "summary": "This paper studies smoothed online learning and considers two performance metrics: the competitive ratio and the dynamic regret. For the competitive ratio part, the authors study the greedy algorithm which minimizes the weighted sum of the hitting costs and the switching cost. They improve the existing competitive ratio results by some constant factors in three different settings. For the dynamic regret part, the authors show that a small modification of Ader, SAder, can attain the same dynamic regret bound as the case without switching costs. They also show that if the agent can observe next step's hitting cost before making decisions, the Lookahead SAder algorithm can achieve the optimal dynamic regret bound without the bounded gradient assumption.\n\nUpdate: I partly agree with the points made in the response. So I adjust the score to 6.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "I have some concern with the originality of this work. Most algorithms considered in this paper have already been studied in similar settings, and the authors failed to convince me about the novelty of their proof techniques. I hope the authors can briefly clarify this in the rebuttal. Are these proofs trivial extensions of previous works? If not, what is the most significant challenge and how do you overcome it?\n\nThis paper is technically sound. All claims are supported by rigorous proofs. Although I did not check the details in the appendix, I think the results make sense.\n\nThe writing of this paper needs to be improved much. First, the overall organization is a bit messy. The authors present five different problem settings and analyze four different algorithms, but do not discuss much about their connections.  Second, the authors should focus more on the intuitions and novelties in their remarks, rather than only comparing the final bounds. I believe presentation issues can usually be fixed in the revision, but they may affect my evaluation of originality and significance.\n\nMy major concern is about the significance of this work. I hope the authors can help me understand the following issues better in the rebuttal:\n1. I do not think the improvements in Thm 1 and Thm 2 are significant from a theoretical perspective. It is clear from the form of the competitive ratio that the problem becomes more challenging as $\\alpha$ and $\\lambda$ converges to zero. The new results in this paper are in the order of $O(1/\\alpha)$ or $O(1/\\lambda)$, which are the same as previous results. Since there are no lower bound results to rule out competitive ratios in the order of $O(1/\\sqrt{\\alpha})$, the presented results may still be far from optimal for small $\\alpha$. Given this, the claim “It seems safe to ignore the switching cost” in line 211 looks weird to me.\n2. In Section 3.3, the proposed algorithm is a special case of the ROBD algorithm in [Goel et al., 2019]. The problem setting becomes slightly more general in this paper, but the proof technique looks similar with the ROBD proof in [Goel et al., 2019]. I hope the authors can clarify why they think the new setting (convex + quadratic growth hitting costs) is important, and what is new in the proof.\n3. In Section 4.1, the authors emphasize that “the only modification” they make to Ader is incorporating the switching costs. Does this lead to significant changes in the proof?\n\nIn summary, I suggest to reject this paper because I feel the contribution of this work is incremental, and the presentation is not good enough. I understand that the presentation issues may affect my evaluation of other aspects, so I am open to adjust the score if the authors can address some of my concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The two open problems at the end of the paper discuss the limitations of this work. I think they are appropriate.\n\nSome constructive suggestions: I feel the authors can consider more about the applications of smoothed online learning, and use them to justify the assumptions they make on the hitting and switching costs. The switching costs may have more complicated forms than $\\ell_2$ norm or $\\ell_2$ norm squared, and the hitting costs may become much simpler (e.g. quadratic).", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "eQgB6t64EGF", "reviewer": "Reviewer_MZJx", "summary": "This paper studies smoothed online learning by targeting two performance metrics: competitive ratio and dynamic regret with switching cost. The paper first improves the competitive ratio of the naive approach and the greedy algorithm. Then the paper proposes a novel algorithm called SAder which achieves optimal dynamic regret with switching cost under the lookahead setting.\n", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\nThe contribution of this paper is solid. It contains two parts. The first part (section 3) provides better competitive ratios for the naive approach and the greedy algorithm. The second part (section 4) includes a novel algorithm with optimal dynamic regret under the lookahead setting. \n\nWeakness:\n\n1. These two parts of the contribution are independent of each other to some extent. Is it possible to study one algorithm which can simultaneously improve both competitive ratio and the dynamic regret? Notice that the OBD and ROBD algorithms have theoretical guarantees on both competitive ratio and the dynamic regret, though their results are not optimal.\n\n2. The paper does not contain the lower bound of polyhedral functions and quadratic growth functions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "dBlJvZerS_V", "reviewer": "Reviewer_C2AR", "summary": "The authors study online convex optimization with switching costs, a well-known problem which has attracted much recent attention in the past few years, and which is closely related to convex body chasing. The authors make the following two contributions: first, they improve on some of the competitive ratio bounds presented in Goel et al and Lin et al, and second, they present an algorithm with optimal dynamic regret, along with a matching lower bound. ", "questions": "", "limitations": "", "rating": 6, "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": "Theorem 1 claims to improve on the competitive ratio presented in Lin et al, but the improvement is minor and the proof is trivial. I do not believe this theorem will be of interest to the broader ML community. Theorems 2 and 3 are more interesting, and use a careful analysis to simplify and improve results from Goel et al. The proofs are simple and clean, and they are also able to match a lower bound proved in Goel et al. It's nice to see the exact constants nailed down. Theorems 4 and 5 prove dynamic regret bounds for a modified version of the Ader algorithm introduced in Zhang et al; Theorem 6 proves a matching lower bound. The algorithm they propose is only a slight modification of vanilla Ader, so I think the main contribution here is the analysis and the new lower bound.\n\nI do have a suggestion for the authors - they write on line 141 that the squared L2 distance considered in the dynamic regret bounds of Goel et al is \"not suitable for general convex functions.\" It seems to me that the point the authors are making is that the dynamic regret bounds proved in Goel et al rely on strong convexity, whereas their regret bounds do not. While this is true, it does not imply that L2 switching cost is always a superior metric to squared L2 switching cost - different metrics are more relevant for different problems. One advantage of the squared L2 distance is that it is related to LQR control problems, as shown by Goel and Wierman. I think it would be helpful to add a paragrpah explaining the different roles that different choices of switching cost play, instead of writing as if one choice is strictly superior to other choices.\n\nOverall opinion: while the paper does not provide any new algorithmic insights per se, it does present small improvements on existing results on a problem that has attracted much recent attention in the ML community. The paper is well-written and acknowledges previous work properly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No problems here.", "review_text": "", "extra_scores": {"ethical_concerns": "No problems here.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SsVKxxbfXH", "reviewer": "Reviewer_A46c", "summary": "This work considers the problem of online learning with movement cost, and studies the metrics of competitive ratio and dynamic regret for polyhedral and quadratically-growing functions. For competitive ratio, while studying simple algorithms (a positive) that ignore switching costs, the upper bounds offered here improve over the best known in both settings (for distinct switching cost in each case). For dynamic regret, the paper suggests a modification of a dynamic-regret-guaranteeing algorithm to the switching cost setting with optimal dynamic regret.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "On the competitive ratio front, the paper presents concrete improvements for special cases of polyhedral and quadratically growing functions (~strong convexity around minimum).\n\nAs for dynamic regret: It is well-known that OGD gets the correct dynamic regret as long as the step size choice is allowed to depend on the path length of the comparator (an oracle quantity). Therefore, existing algorithms essentially run Mult Weights over guesses of choices of exponentially spaced learning rates. The modification here for accomodating movement cost is to penalize the experts (corresponding to learning rate guesses) for not just their decision, but also for their movement. This is natural choice.\n\nQuestions:\n1. Previous work in this setting could operate on locally polyhedral functions. Can such functions be accomodated here? If not, what is the precise obstruction to this?\n2. What is the claim of novelty in section 3.3? In the reviewer's reading, the upper bound in Goel et al (Beyond OBD) matches the lower bound exactly for squared l2 movement (see discussion below Theorem 4 there). Theorem 3 here seems to offer strictly worse bounds, contradicting \"the constants in our bound are much smaller.\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the analysis of competitive ratio/dynamic regret for problems with hitting cost and switching cost. They provide concrete improvements in terms of nailing down the constants for the ratios in the case of polyhedral function and quadratic growth functions achieving this with a relatively simple algorithm and a clean analysis. The reviewers have appreciated the clarity and simplicity of the paper and the approach, the concreteness of the improvements achieved as well as the right attribution and discussion of previous work. Nevertheless, the paper does not provide any novel algorithmic insights and analyses a well-known algorithm in various settings with improvements in guarantees. Overall while the paper is close to the borderline post the discussion, the reviewers unanimously agreed that the paper is slightly above the borderline due to the concrete improvements for well-known and well-studied problems and there by I am proposing an accept. 
Decision: Accept (Poster)