Online Convex Optimization with Continuous Switching Constraint
Authors: Guanghui Wang
Yuanyu Wan
Tianbao Yang
Lijun Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online convex optimization
Continuous switching constraint

Abstract: In many sequential decision making applications, the change of decision would bring an additional cost, such as the wear-and-tear cost associated with changing server status. To control the switching cost, we introduce the problem of online convex optimization with continuous switching constraint, where the goal is to achieve a small regret given a budget on the \emph{overall} switching cost. We first investigate the hardness of the problem, and provide a lower bound of order $\Omega(\sqrt{T})$ when the switching cost budget $S=\Omega(\sqrt{T})$, and $\Omega(\min\{\frac{T}{S},T\})$ when $S=O(\sqrt{T})$, where $T$ is the time horizon. The essential idea is to carefully design an adaptive adversary, who can adjust the loss function according to the cumulative switching cost of the player incurred so far based on the orthogonal technique. We then develop a simple gradient-based algorithm which enjoys the minimax optimal regret bound. Finally, we show that, for strongly convex functions, the regret bound can be improved to $O(\log T)$ for $S=\Omega(\log T)$, and $O(\min\{T/\exp(S)+S,T\})$ for $S=O(\log T)$.

Online Convex Optimization with Continuous Switching Constraint
Guanghui Wang', Yuanyu Wan 1.2 Tianbao Yang", Lijun Zhang
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China Peng Cheng Laboratory, Shenzhen, Guangdong, China Department of Computer Science, The University of lowa, Iowa City, USA (wanggh, wanyy, zhanglj j) @lamda anju.edu. en, tianbao-yang edd
Abstract
In many sequential decision making applications, the change of decision would bring additional cost, such as the wear-and-tear cost associated with chang- ing server status. To control the switching cost, we introduce the problem of online convex optimization with continuous switching constraint, where the goal is to achieve a small regret given a budget on the overall switching cost. We first investigate the hardness of the problem, and provide a lower bound of or- der D(vT) when the switching cost budget S S(VT), and ([min when S O(VT), where T is the time horizon. The essential idea is to fully design an adaptive adversary, who can adjust the loss function according to the cumulative switching cost of the player incurred far based the orthogo- nal technique. We then develop a simple gradient-base bassed algorithm which enjoys the minimax optimal regret bound. Finally, functions, the regret bound can be improved to O(log T) for S = M(log 7)), and (m/n ex)(S)- S, T)) for S O(log T.
show that, for strongly convex
1 Introduction
Online convex optimization (OCO) is a fundamental framework for studying sequential decision making problems Shwaev-Shwartz 201T). Its protocol can be an adversary: each round f, firstly, the player selects an action w, from a convex set C Rd. After submitting the answer, loss function fe D + IR is revealed, and the player suffers loss fe(w:). The goal to minimize the regret:
game between player and
R SiW.)
f((w))
min Σ ft(w), tm
which is the difference between the cumulative loss of the player and that of the best action in hindsight.
Over the past decades, the problem of OCO has been extensively studied, yielding various algo- rithms and theoretical guarantees (azan 2016 Orabona 2019). However, most of the existing ap- proaches allow the player to switch her action freely during the learning process. As a result, these methods become unsuitable for many real-life scenarios, such as the online shortest paths problem (Koolen el al. 2010,, and portfolio management (Dekel et al. 2014; Vittori et al. 2020). where the switching of actions brings extra cost, and the budget for the overall switching
strictly
Lijun Zhang is the corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

constrained. To address this problem, recent advances in OCO introduced the switching-constraile constrained problem (Altschuler & Talwar 2018 Chen al. 2020 where hard constraint is imposed to the number of the player's action shifts, I.e.,
Σ (w A A wi-1S K,
and the goal is to minimize regret under a fixed budget K. For this problem, Chen et al. (2020) have shown that, given any K, we could precisely control the the overall switching cost in 2 while achieving minimax regret bound of order (TT/VK).
One limitation of (2) is that it treats different amounts of changes between We-1 and w, equally, since the binary function is used as the penalty for action shifts. However, as observed by many practical applications, e.g., thermal management (Zanini de Veciana 2012) and
al.) 2010). video streaming (Joseph & control (Goel et al. 2017). the price paid for large and small action changes are not the same. Specifically, for these scenarios, the switching cost between two consecutive rounds is typically characterized by a f2-norm function, i.e., l/w, w Motivated by this observation, in this paper, we introduce a novel OCO setting, named OCO with continuous switching constraint (OCO-CSC), where the player needs to choose actions under hard constraint on the overall fz-norm switching cost, i.e.,
T w. - w- SS
where is a budget given by the environment. The main advantage of OCO-CSC is that, equipped with 3.. we could have a more delicate control on the overall switching cost compared to the binary constraint in
For the proposed problem, we firstly observe that, an O(T/vS) regret bound can be achieved by using the method proposed for the switching-constrained OCO (Cen al. 2020) under proper configuration of K. However, this bound is not tight, since there is a large gap from the lower bound established in this paper. Specifically, we provide a lower bound of order (((T) when S = ((VT), and (mmnn g.. (T) when S = O(VT). Our basic framework for constructing the lower bound follows the classical linear game (Abernethy et al., 2008), while we adopt novel cotiuuoos--oosstrin---eeeeee
dynamic policy for the adversary, which allows it to adaptively change the loss function according to the player's cumulative switching costs. Furthermore, we prove that the classical online gradient descent (OGD) with an appropriately chosen step size is able to obtain the matching upper bound. These results demonstrate that there a phase transition phenomenon between large and small switching budget regimes, which is in sharp contrast to the switching- constrained setting, where the minimax bound always decreases with ((1vVK) Finally, we pro- pose a variant of OGD for >-strongly convex functions, which can achieve an O (log T") regret bound when S 22log T', and an O(T/ exp(S) + S) regret bound when S Ollog T").
Related Work
In this section, we briefly review related work on online convex optimization.
2.1 Classical OCO
The framework of OCO is established by the seminal work of Zinkevich 2003 For general convex functions, Zinkevich (0033) shows that online gradient descent (OGD) with step size on the order of O(1/ enjoys an (VVT) regret bound. For X-strongly convex functions, Hazan et al. (207)h prove that OGD with step size of order (1/[))) achieves an Ollog T') regret bound. Both bounds have been proved to be minimax optimal (Abernethy et al. 2008). For exponentially concave func- tions, the state-of-the-art algorithm is online Newton step (Hazan et al. 2007), which enjoys an (ld log T') regret bound, where d is the dimensionality.

---

2.2 Switching-constrainng OCO
One related line of research is the switching-constraieed setting, where the player is only allowed to change her action no more than K times. This setting has been studied in various online learning scenarios, such as prediction with expert advice (Altschuler & Talwar 2018) and bandits prob- lems (Simchi-Levi & Xu 2019; Dong et al.] 2020; Ruan et al., 2021). In this paper, we focus on online convex optimization. Jaghargh et al. (2019) firstly consider this problem, and develop novel online algorithm based on the Poison Process, which can achieve an expected regret of order O [)] for any given expected switching budget E[K]. Therefore, the regret will become sublinear for E[K]= o(vT). Later, Chen al. (2020) propose a variant of the classical OGD based on the mini-batch approach. Specifically, the algorithm averagely divides the time horizon into K intervals, and only update the decision at the end of each interval based on OGD. The show that the simple algorithm enjoys an O(T/VK) regret bound for any given budget K. They also prove that this result is minimax optimal by establishing a matching QTT v K) lower bound. We note that, when the action set is bounded (i.e., max W2ED ||W] w2ll _ D), since
Iw w.- DK,
we could set K = [S/D] to satisfy 3 and immediately obtain an O(T/V5) regret for OCO- CSC, but there is still large gap from the lower bound we provide in this paper. Very recently, concurrent work (Sherman& & Koren 202T considered
constraine OCO under oblivious adversary setting, and derived G[ S) bounds. However, we note that: (i) lower bound for the switching-constral OCO does not translate to lower bound for our continuous switching cost setting; and (ii) their upper bound for oblivious only holds in expectation, and has an undesirable vd factor.
2.3 OCO with Ramp Constraints
Another related setting is OCO with ramp constraints, which is studied by Badiei et al. (015)) In this setting, at each round, the player must choose an action satisfying the following inequality:
We, w1-1.al S X.,
where Wh, denotes the i-th dimension of w., and X, is a constant factor. The constraint in limits the player's action switching in a per-round and per-dimension level. This very different from the constraint we proposed in B.) which mainly focus on the long-term and overall switching cost. Moreover, we note that, Badiei et al. (2055) assume the player could get access to a sequence of future loss functions before choosing w,, while this paper we follow the classical OCO framework in which the player can only make use of the historical data.
2.4
OCO with Long-term Constraints
Our proposed problem is also related OCO with long-term constraints Maahdav al. 2012 Jenatton et al. 2016 Yu et al. 2017). where the action set is written as m convex constraints, l.c.,
D
(w E IRd" g, (w) S 0, i [m]}.
(5)
and we only require these constraints to be satisfied in the long term, i.e., Σt (w,) S 0, E [m]. The goal is to minimize regret while keeping ΣT 9: (w:) small. We note that, in this setting, the action set is expressed by the constraint, which is in contrast to OCO-CSC, where the constraint and the decision set D are independent. Moreover, the constraint in OCO-CSC is iiriintriant and decided by the historical decisions, while the constraint in (5) is static (or stochastic, considered by Yu et al.] 2017). Recently, several work start to investigate OCO with long-term and time-variant constraints, but this task is proved to be impossible in general (Mannor et al. 2009). Therefore, existing studies have to consider more restricted settings, such as weaker definitions regret (Neely
& Yu 2017 Liakopoulos et al. 2019
Yi et al. 2020
Valls et al. 2020).
3

---

2.5 Smoothed OCO
The problem of smoothed OCO originally proposed in the dynamic right-sizing for power- proportional data centers (Lin et al. 2012b), and has received great research interests during the
past decade (Lin al. 2012a Bansal al. Antoniads Schewior, 2017 Chen et al. 2018 Goel et al. 2019: Goel & Wierman 2019) Zhang et al. 2021a). In smoothed OCO, at each round, the learner will incur a hitting cost fcl.) as well as switching cost ||w, w Ill- and the goal is to
minimize dynamni regret (Zinkevich) 2003) competitive ratio (Borodin & El- Yaniv 2005 with respect to fr(w:) + l|w, W Il. This setting closely related to but different from OCO-CSC, where the goal is to minimize regret with respect ft(-). and the overall switching cost is limited by a given budget. Additionally, we note that, similar to Badiei et al. (213)) studies for the smoothed
OCO typically assume the player could fe(-) or sometimes window of future loss functions (Chen et al. 2015 2016 Li et al. 2018) before choosing w, By contrast, in OCO-CSC the player not obtain these additional information.
Main Results
In this section, present the algorithms and theoretical guarantees for OCO-CSC. Before pro- ceeding to the details, following previous work, we introduce some standard definitions (Boyd & Vandenberghe 2004) and assumptions (Abernethy al. 2008).
Defination A function f : + IR is convex / E DD
f(w1) 2 f(w2) + f((2)) (w1 - W2).
(6)
Defination 2 A function
D R is X-strongly convex if VWI, W2 D.
f(w1) >f(w>) + (f((2) - -w2) W - -w2l??
2
Assumption 'D is a d-dimensional ball of radius D 2' ie., D= (w/ E // $ 21.
Assumption The gradients of all the online functions are bounded by G, ie..
max
f+((())l G, E
(8)
WED
3.1 Lower Bound for Convex Functions
Algorithm Adversary's 's Policy
1: 1, 1, =1
2: Observe the player's action wi
Choose m, such that m, W1
4: t 2 to I do
5: Observe the player's action w.
6: if -i l!w, w S then
7:
Choose m; m
8:
else
9:
Choose m, such that m, w. 2 0 and m E my)
20 0.
10:
=
11:
end if
12:
end for
We first describe the adversary's policy for obtaining the lower bound. Following previous work Abernethy et al, (2008), proposed policy is based the linear game, i.c., in each round, the adversary chooses from set of bounded linear functions:
F =f(()) D [[f(w) = m w, |||| G),

---

which is a subset of convex functions satisfying Assumptions ! and can be written as
2
For this setting, the regret
D w
E f((w)) min WED Σ [((w) Σ
m W. min
Σ
m
Σ
m
Σ m
WED
2
where the third equality is because the minimum is only obtained when
Σ T
w = - D 1=
m
2
m
According to 4 to get tight lower bound for R. we have to make both Σ m, w, and I mell as large as possible. One classical way achieve this goal is through the orthogonal technique (Abernethy et al. such that m, W. 2 0 and m, (E:= m.) 2 O. Note that such a can always be found for d 2 2. For this technique, it be easily shown that Σ m? W. O, while E me|l > GvT,
2008: Chen et al. 2020p, that is, in round i, the adversary chooses m.
which implies an (TDGVT) lower bound.
The above policy does not take the constraint on the player's action shifts into account. In the following, we show that, by designing a more adaptive adversary which automatically adjusts its action based on the player's historical switching costs, we can obtain a tighter lower bound when S small. The details is summarized in Algorithm [ Specifically, in the first round, after observing the player's action WI, I, the adversary just simply chooses Si (w) m w such that m, w; = 0 (Step 3). For round f. 2 2, the adversary divides the time horizon into several epochs. Let the number of epochs be N. For each round & in epoch t [N], after obtaining w., the adversary checks if the cumulative switching cost of the player inside epoch T exceeds threshold (Step 6). To be more specific, the adversary will check if
Σ j=1+1
Iw, - w C 5'
where 4, is the start point of epoch r, l1 = 1, and c >> 0 is a constant factor. If the inequality holds, then the adversary will keep the action unchanged (Step 7): otherwise, the adversary will find new m, based on the orthogonal technique, i.c., find m, such that m, w, 2 and m, M,-1 2 0, where
M = E my. and then start a new epoch (Steps 9-10).
The essential idea behind the above policy is that the adversary adaptively divides iterations into N epochs, such that for each epoch E [N], the cumulative switching cost inside of 7 is upper bounded by
41-1 Σ
[w, w.- 5.
f=1+1
and for each epoch [N 1),
Σ j=L+1
Iw, wy-ll>
The above two inequalities help us obtain novel lower bounds for the two terms at the R.H.S. of respectively which depend on S. Specifically, we prove the following two lemmas.
Lemma We have
T
cGT
m
W: 2
S
Lemma 2
We have
T
Tyc
m
2
VSa +c
5

---

By appropriately tuning the parameter we finally prove the following lower bound.
Theorem For any online algorithm, under any given switching cost budget S. Algorithm v can generate a series of loss functions fi(.)...,,ff fT(.)
satisfying Assumptions and
such that
0.5DGVT. DT 0.05DG
Se EDDV,, SE
R
0.05DGG, SE),DD).
Remark The above theorem implies that, when S S D. the lower bound for OCO-CSC is linear with respect to T; When S E [D, DvT), it's possible to achieve sublinear results, and the lower bound decreases with T/S; for sufficiently large S, i... when S (DDVT), the lower bound is Q(DGVT), which matches the lower bound for the general OCO problem (Abernethy et al. 2008 Note that in this case the lower bound will not further improve as S increases, which is very different from the switching-constraines setting, where the lower bound is ((TTV/K) which means that increasing the budget K' is always beneficial. Finally, we note that, since
T w. w.-1ll S
Σ D
Σ w. w
lower bound for the binary switching cost setting (Altschuler & Talwar 2018 Chen al. does not translate to lower bound for our continuous switching cost setting.
20200
We summarize our main ideas for proving Theorem D follows. For the proposed adversary, we firstly show that (Lemma 1, Eq. (66). inside of each batch, there exists negative error term caused by the possible oonoorrhogynality between the player's decisions and the adversary's choice. To maximize this eπror term and further the lower bound, the adversary should change its choice as many times as possible (thus require a small threshold); On the other hand, Lemma 2 (Fq. 330 indicates that, the lower bound is tighter when the number of batches is small (thus require a large threshold). Based on the two lemmas, in the proof of Theorem 1, we show that the final lower bound is function of the threshold. Very luckily, we find that the optimal lower bound can be derived by choosing a threshold that maximizes the function.
Remark 2
3.2 Upper Bounds
In this section, we provide the algorithm for obtaining the upper bound. Before introducing our method, we note that, as mentioned in Section 2.2 the mini-batch OGD algorithm proposed by Chen al. (2020) enjoys D(T/VS) regret bound for OCO-CSC, which is suboptimal based on the lower bound we constructed at the last section. In the following, we show that, perhaps a bit surprisingly, the classical online gradient descent with an appropriately chosen step size sufficient for obtaining the matching upper bound. Specifically, in round t, we update w, by
Wi+1 IIp [wo fww:)).
(10)
where 1Ip[p) denotes projecting p into D, i...
lb argmin(w p) T(w- (w- p).
wED
For this algorithm, we prove the following theoretical guarantee.
Theorem Suppose Assumptions I and hold, and all loss functions convex. Then, under any given switching cost budget S, OGD with step size
S DT]
GVT
(11)
(
GT:
satisfies and achieves the following regret:
DGVT,
Se DVT, DT Se DVD)
R R
DT
S
DGT,
Se (),

---

Minimax Regret
DGVT
D
DVT
DT
Figure 1: Minimax regret of OCO-CSC. Axies are plotted log-log scale.
Remark 3 Theorems and 2 show that our proposed algorithm enjoys O(GVV)) minimax
regret bound for S 92 DVVT) T), and ODDG m 7)) regret bound for S = O(DVT). We illustrate the relationship between the minimax regret and S in Figure | Finally, we note that the algorithm requires the paramter 7 input, but could be easily extended to an any-time algorithm by using the doubling trick Shalev-Shwartz 2011.
Although the analysis above implies that the theoretical guarantee for OCO-CSC is unimproveable in general, in the following, we show that tighter bounds still achievable when the loss functions are strongly convex. Specifically, when there are no constraints on the switching cost, the state-of- the-art algorithm is OGD with time variant step size пe 1/[Xt]. which enjoys an Oloo T') regret bound. For the OCO-CSC setting, in order to control the overall switching cost, we propose to add a uning parameter at the denominator of the step size. To be more specific, round i, we update w; by
W++1 = Hp (wo - 77 f(.:))
(12)
where c(++c)) and c > is a constant factor. By configuring c properly, we can obtain the following regret bound.
Theorem 3 Suppose Assumptions 1 and 2 holdd and all loss functions are X-strongly convex. Then, under any given switching cost budget S, the algorithm in
(2 with
0
S E 2G log + LT,
T
5 S [0,
2G
log (1)
(13)
expl
51-1
satisfies and achieves XD2
2G
log (T + 1) for S E 2 log(T + 1), DT), and
XTD²
R S min
+ GS, DGT
eep
A 5)
for S [0, 2G log(T' 1)).
Remark 4 Theorem implies that, when S > 2G
X log(T + 1), the proposed algorithm enjoys
an Ollog 7) optimal regret bound; for < 20 / (xs(()xpS)) + S) regret bound. obtain a sublinear regret bound, consider S 22 log(T + 1). In this case, we have
log(T 1), the proposed algorithm achieves
X
2G² log( + 1),
R AD
which is sublinar for E (0, 1].
4 Theoretical Analysis
In this section, we present the proofs for the main conclusions.
7

---

4.1 Proof of Theorem 11
When 2 DVT, the lower bound can be directly obtained by using the minimax linear game provided by (Abernethy al. 2008). When S E [D, DVT), by the definition of regret, we have
T
Σ
m Wt
min WED
m
w
1=1
Based on Lemmas
! and we get
0.5DT cGT
R =1 +
(14)
V +c
8
Let c = cDD², and we have
0.5DT dD S
0.5V2
d) 5) 2 GD: T S VI++c - c)
d'
0.5ve
R V +D
=GDTT
+eD $
where the second inequality due to < S. Note that the R.H.S. of the above inequality is a function of c'. To maximize the lower bound, should solve the following convex problem:
0.5
argmax z>0
V1+2 I,
which is equivalent finding the solution of the following equation:
16x 32. + 49x² 15x 1 0.
it can be easily shown that the optimal solution 0.056. Thus, by setting c' 0.056, we get
R 2 0.05GD
(15)
S'
For S E DJ, based on and setting 0.0565², we have
0.0565
0.056$²
0.028
R GT
2 GDT
0.056
2 0.05GDT.
VS2 0.0565
S
V1.056
where the second inequality is because < D.
4.2 Proof of Theorem
We first prove that by setting as in the constraint in always holds. Let w/
Wi-1
7/ V (w.-... have
T [
T
Σ w. w. <
w
( GT,
(16)
1=2
where the first incquality is based the following lemma, which describes the non-expansion property of the projection.
Lemma 3
McMahan & Streeter 2010 For the projection operation, we have Vw1, W2 E Rd
[T((w)) [T( < [|w w2
Based 16 for S E [DVT, DT), have
w. - w.- STT DVT SS.

---

For S [0, DVT), we have
S
w: we-1ll 1l GTT
GT S.
GT
Next, we turn to upper bound the regret. Let w. = argmin
WED Σ fi f((W). Based on the classical
analysis of OGD (azan 2016), we have
l| w.ll
< l|w w.ll2 -|| V/V
w
=| w. + 77² V V
-2n(We-1 w.) V
Thus
(w: w.) V.) [. W. w. W w. "
V S (w:))l..
21
Based on the convexity of the loss functions and summing the above inequality up from to T, we
get
R
T
W.
W.
W++1
w
17
Vf((w:))1
D2
G
(17)
27
2
2n
2
1=1
Thus, for S [DVT, DT), have
D2
nTP
R
+
DGVT.
(18)
21
For S DVT),
D2 GT
DT S
DT
VT
DT
DT
DT
R +
DDG
S
DG
S
DG
+
DG
2n
25
2D
25
2
2s
28
Finally, note that by Assumptions 1 and 2 and the convexity of the loss functions, always have R < DGT.
Conclusion and Future Work
In this paper, we propose variant of the classical OCO problem, named OCO with continuous switching constraint, where the player suffers a normm switching cost for each action shift, and the overall switching cost is constrained by given budget S. We first propose an adaptive mini-bater policy for the adversary, based which prove that the lower bound for this problem (VVT) when S2( TT), and M(min{ /. ()) when S O(VT). Next, we demonstrate that OGD with proper configuration of the step size achieves the minimax optimal regret bound. Finally, for X-strongly convex functions, we develop variant of OGD, which has a tunable parameter the denominator, and we show that it enjoys an O(log 7') regret bound when S = 2(log 7), and an (STT/xp((S== + 5) regret bound when = Olog
In the future, we would like to investigate how to extend the proposed constraint setting to other OCO scenarios, such as minimizing adaptive regret (Jun al. 2017 Zhang et al. 2019 dynamic
regret Zinkevich] 2003 Zhang et al. 2018) 8), and Universal OCO (van Erven & Koolen 2016 Wang
ct al. 2019 Zhang al. 2021bb. Moreover, is also interesting question study the switching constraint problem under other distance metrics such as the Bregman divergence.
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: National Key Research and Development Program of China (2018AAA010100)) 100), NSFC grant 61921006 and 61976112.

---

References
Abernethy, J., Bartlett, P. L., Rakhlin, A., and Tewari, A. Optimal stragies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference Learning Theory, pp. 415-423, 2008
Proceedings of the st Annual Conference on Learning Theory, pp. 1569-1573, 2018. Altschuler, J. and Talwar, K. Online learning over finite action set with limited switching. In
Antoniadis, A. and Schewior, K. A tight lower bound for online convex optimization with switching costs. International Workshop on Approximation and Online Algorithms, pp. 164-175, 2017.
Badiei, M., Li, N., and Wierman, A. Online convex optimization with ramp constraints. In 2015 54th IEEE Conference on Decision and Control, pp. 6730-6736, 2015.
Bansal, N., Gupta, A., Krishnaswamy, R., Pruhs, K., Schewior, K., and Stein, C. A 2-competitive algorithm for online convex optimization with switching costs. Algorithms and Techniques for Approximation, Randomization, and Combinatorial Optimization, 2015.
Borodin, A. and El-Yaniv, R. Online computation and competitive analysis. cambridge university press, 2005.
Boyd, S. and Vandenberghe, L., Convex Optimization. Cambridge University Press, 2004.
Chen, L., Yu, Q. Lawrence, H., and Karbasi, A. Minimax regret of convex optimization: No phase transition. In Advances in Neural Information Processing Systems 33, 2020.
online
Chen, N., Agarwal, A., Wierman, A., Barman, S., and Andrew, L. using predictions. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 191-204, 2015.
L. Online convex optimization
Chen, N., Comden, J., Liu, Z., Gandhi, A., and Wierman, A. Using predictions in online optimiza- tion: Looking forward with an eye on the past. ACM SIGMETRICS Performance Evaluation Review, 14(1):193-206, 2016.
Chen, N., Goel, G., and Wierman, A. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of the 31st Annual Conference on Learning Theory, pp- 1574-1594, 2018
Dekel, O., Ding, J., Koren, T., and Peres, Bandits with switching costs: 72/3 regret. Proceed- ings of the 46th anmual ACM symposium on Theory of computing, pp. 459-467, 2014.
Dong, K., Li, Y., Zhang. Q., and Zhou, Y. Multinomial logit bandit with low switching cost. In Proceedings of the 37th International Conference on Machine Learning, pp. 2607-2615, 2020.
Gaillard, P., Stoltz, G., and Van Erven, T. second-order bound with excess losses. In Proceedings of the 27th Annual Conference on Learning Theory, pp. 176-196, 2014.
Goel, G. and Wierman, A. An online algorithm for smoothed regression and lqr control. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2504-2513. PMLR, 2019.
Goel, G., Chen, N., and Wierman, A. Thinking fast and slow: Optimization decomposition across timescales. In Proceedings of the 56th IEEE Annual Conference Decision and Control, pp- 1291-1298, 2017.
Goel, G., Lin, Y.. Sun. H., and Wierman, A. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems 32, pp. 1875-1885, 2019.
Hazan, E. Introduction to online convex optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
10

---

Hazan, E.,, Agarwal, A., and Kale, S. Logarithmic regret algorithms for online convex optimization. Machine Learning. 69(2-3):169-199 2007.
Jaghargh, M. R. K., Krause, A., Lattanzi, S., and Vassilvtiskii, Consistent online optimization: Convex and submodular. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2241 2241-2250, 2019.
Jenatton, R., Huang, J., and Archambeau, C. Adaptive algorithms for online convex optimization with long-term constraints. In Proceedings of the 37th International Conference Machine Learning, pp. 402-411, 2016.
Joseph, V. and de Veciana, G. Jointly optimizing multi-user rate adaptation for video transport over tradeoff's In Proceedings the 31st Annual IEEE
wireless systems: feaun--arress-variiae International Conference on Computer Communications, pp. 567-575, 2012.
Jun, K.-.., Orabona, F., Wright, S., and Willett, R. Online learning for changing environments using coin betting. Electronic Journal of Statistics, 11(2):222-53100, 2017.
Koolen, W. M., Warmuth, M. K.,, Kivinen, J., al. Hedging structured concepts. In Proceedings of the 23rd Annual Conference on Learning Theory, pp. 93-105, 2010.
Li Y., Qu, G., and Li, N. Using predictions in online optimization with switching costs: A fast algorithm and fundamental limit. In 2018 Annual American Control Conference, pp. 3008- 3013, 2018.
Liakopoulos, N., Destounis, A., Paschos, G., Spyropoulos, T., and Mertikopoulos, P. Cautious regret minimization: Online optimization with long-term budget constraints. In Proceedings of the 39th International Conference on Machine Learning, pp. 1994-3955 2019.
Lin, M., Liu, Z.,, Wierman, and Andrew, I.. L.. Online algorithms for geographical load balancing. In International Green Computing Conference, pp. 1-10, 2012a.
Lin, M., Wierman, A., Andrew, L., and Thereska, E. Dynamic right-sizing for power-proportional data centers. JEEE/ACM Transactions on Networking, 21(5); 1378-1311, 2012b.
Mahdavi, M., Jin, R., and Yang, T. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1))2503-2528 2012.
Mannor, S., Tsitsiklis, J. N., and Yu, J. Y. Online learning with sample path constraints. Journal of Machine Learming Research, 10(3), 2009.
McMahan, H. B. and Streeter, M. Adaptive bound optimization for online convex optimization. In Proceedings of the 23rd Anmual Conference on Learning Theory, pp. 224-256, 2010.
Neely, M. J. and Yu, H. Online convex optimization with time-varying varying constraints. arXiv preprint arXiv: /t0i::/770.04444 04783, 1702.0443, 2017.
Orabona, F. A modern introduction to online learning. arXiv preprint arXiv: 1912.1111 2019.
Ruan, Y., Yang, J., and Zhou, Y. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Com- puting, pp. 74-87, 2021.
Shalev-Shwartz, S. Online learning and online convex optimization. Foundations and Trends in Machine Learning. 1(2):107-194, 2011.
Sherman, U. and Koren, T. Lazy oco: Online convex optimization on switching budget. Proceed- ings of the 34th Annual Conference on Learning Theory, 2021.
Simchi-Levi, D. and Xu, Y. Phase transitions and eyclie phenomena in bandits with switching constraints. In Advances in Neural Information Processing Systems 32, pp. 7523-7532, 2019.
Valls, V., Iosifidis, G., Leith, D.,, and Tassiulas, L. Online convex optimization with perturbed constraints: Optimal rates against stronger benchmarks. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, pp. 2885-2893 2020.

---

van Erven, T. and Koolen, W. M. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29, pp. 0666-3674, 2016.
Vittori, E., de Luca, M. B., Trovò, F,, and Restelli, M. Dealing with transaction costs in portfolio optimization: Online gradient descent with momentum. In ACM International Conference Al in Finance, pp. 1-8, 2020.
Wang, G., Lu, S., and Zhang, L. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence, 2019.
Yi, X., Li, X., Xie, L.. and Johansson, K. H. Distributed online convex optimization with time- varying coupled inequality constraints, IEEE Transactions on Signal Processing, 68:731-746, 2020.
Yu, H., Neely, M. J., and Wei, X. Online convex optimization with stochastic constraints, In Advances in Neural Information Processing Systems 30, pp. 1427-1437, 2017.
Zanini, F., Atienza, D., De Micheli, G., and Boyd, P. Online convex optimization- based algo- rithm for thermal management of mpsocs. In Proceedings of the 20th symposium on Great lakes symposium on VLSI, pp. 203-208, 2010.
Zhang, L., Lu, S., and Zhou, Z.-H. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, pp. 1323-1333, 2018.
Zhang, L., Liu, T.-Y., and Zhou, Z.-H. Adaptive regret of convex and smooth functions. Proceed- ings of the 36th International Conference on Machine Learning, pp. 7414-7422 2019.
Zhang, L.,, Jiang, W., Lu, S., and Yang. T. Revisiting smoothed online learning. In Advances in Neural Information Processing Systems 34, 2021a.
Zhang. L., Wang, G., Tu, W.-W., and Zhou, Z.-H. Dual adaptivity: A universal algorithm for min- imizing the adaptive regret of convex functions. In Advances in Neural Information Processing Systems 34, 2021b.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Pro- ceedings of the 20th International Conference Machine Learning, pp. 928-936, 2003.
12


Reviews:
[{"review_id": "yav0CXAyBss", "reviewer": "Reviewer_2rzB", "summary": "This paper studies online convex optimization with continuous switching constraints. The objective of the online agent is to minimize the static regret while keeping the total switching cost within some budget $S$. Under some standard assumptions, the authors establish a lower bound of the regret for all online algorithms by designing the adversary’s policy. They also show that the classical online gradient descent algorithm can match this lower bound if the step sizes are chosen appropriately. In addition, under stronger assumptions on the loss functions, the authors show the regret can be further improved to $O(\\log{T})$.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "This paper makes novel contributions to the online optimization literature. Although the proof techniques (e.g. linear games) and the OGD algorithm used in this paper is based on previous works, the authors make considerable changes to deal with the switching constraints. They compare their approach with previous works in details, and the intuitions behind these changes are discussed carefully.\n\nI go through all the claims and proofs in the main body. They are easy to follow and look technically sound to me. There are a few typos that do not affect the correctness. In line 7 in the abstract, the bound should be $\\Omega(\\min\\{T/S, T\\})$; In the inequality after line 193, $\\sum_{i=1}^{N-1}$ should be changed to $\\sum_{\\tau=1}^{N-1}$, and $L_i^2$ should be $L_\\tau^2$.\n\nThis paper is well organized and should be easy to follow for an expert reader.\n\nTo the best of my knowledge, the results presented in this paper are interesting and significant. The problem setting is a natural variant of smoothed OCO and switching-constrained OCO. The bounds are technically strong because they establish the optimality in the proposed setting. There is also considerable originality in the proof of the lower bound result. It is possible that I overestimate the significance of this work due to lack of familiarity. Thus, I choose a low confidence level.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors discussed some limitations in the future work section. As a suggestion, I think it is also interesting to study the lower bounds for strongly convex loss functions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "mjwbcvN8v5u", "reviewer": "Reviewer_2Yte", "summary": "The authors study online convex optimization with an L2 switching budget (S) on the actions chosen by the online algorithm. The authors propose a modification of the orthogonal technqiue of Abernathy et al to incorporate the switching constraint and propose a new lower bound on the regret achievable for this problem. The authors show a phase transition in the achievable regret for different values of S. The authors show that by setting the step size appropriately, vanilla OGD can match the lower bounds they present.", "questions": "", "limitations": "", "rating": 7, "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": "This papers makes main two contributions. First, it proposes a modification of the orthogonal technqiue of Abernathy et al to incorporate the switching constraint, leading to a new lower bound which exhibits a phase transition as S varies. Both the phase transition result and the modification of the orthogonal technique are new and interesting. Second, they show that vanilla OGD with appropriate step size matches this lower bound exactly. This observation is surprising, given the simplicity of OGD and the fact that it does not explicitly consider the switching budget. I like these results.\n\nI notice that in the related work section about smoothed OCO, the authors forget the paper \"An online algorithm for smoothed regression and lqr control\". I encourage the authors to add this citation. \n\nThe author's results all hold when the time horizon T is known in advance. It should be easy to convert their algorithm to an anytime algorithm using the doubling trick. This is a minor point, but the authors may wish to study this in future work. I also suspect that with a bit more work the authors could show that OGD matches the regret lower bounds all the way to the constant.\n\nThis paper shows new and interesting results for a problem which has attracted much recent attention. I vote accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No problem here.", "review_text": "", "extra_scores": {"ethical_concerns": "No problem here.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "PQv3TiyryWA", "reviewer": "Reviewer_fBbS", "summary": "This work studies the well-known Online Convex Optimization (OCO) problem under an additional $\\ell_2$-norm hard switching constraint of $\\sum_{t=2}^T |w_t - w_{t-1}| \\leq S$ where $w_t$'s are the actions of the algorithm and $S$ is the switching budget. They first provide hardness results to show that the regimes $S=\\Omega (\\sqrt{T})$ and $S=O(\\sqrt{T})$ are different and have varying regret lower bounds. Then, they show that Online Gradient Descent (OGD) with particular choices of step size is able to obtain matching regret upper bounds in both regimes. Finally, the analysis is extended to the strongly convex setting. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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 of the paper:\n- The authors have done a great job motivating the use of continuous switching constraint (instead of a constraint on the number of switches which is used in prior works) through providing real-life examples where the former makes more sense.\n- The related work section provides a comprehensive overview of all the prior works that share similar goals or techniques with this work and highlights the particular gap that this paper is going to cover.\n- Algorithm 1 (for proving the lower bounds) is described in an intuitive way and it is easy to follow the arguments and the proof.\n\nDrawbacks of the paper:\n- The paper lacks any sort of numerical examples (even on synthetic data) to highlight the two different regimes for this problem and their different regret bounds. In particular, a plot showing the trade-off between the choice of $S$ and the regret would be really interesting.\n- The smoothed OCO framework (and the Metrical Task System (MTS) problem in the competitive analysis setting) could be interpreted as the penalized formulation of OCO with continuous switching constraint. Therefore, the claim that these two settings are significantly different is not reasonable and it might be possible to draw some ideas from that literature to address this problem.\n- If we model the OCO with continuous switching constraint as an OCO with long term constraints problem, the constraints would actually be static because at round $t\\in[T]$, the constraint function is $|x-x_{t-1}|$ and so, the algorithm knows the exact form of the constraint before committing to action $x_t$. In this setting, the impossibility result of Mannor et al. does not apply and so, it might be possible to obtain meaningful results using this formulation.\n- The mini-batch OGD algorithm of Chen et al. has been mentioned several times throughout the paper without a sufficient description of the algorithm. So, for readers that are not familiar with the prior works, it is hard to follow the arguments regarding the shortcomings of that algorithm.\n- The details of the proofs (on pages 8 and 9) are not really insightful and most of them could have been moved to the appendix to provide enough space for numerical experiments in the paper.\n**********************\nPost-Rebuttal Update: Thanks to the authors for their detailed responses to the raised questions. With regards to OCO with long-term budget constraints, I'd like to note that given that this problem has two objectives (minimizing regret and constraint violation), it is always possible to minimize the constraint violation while incurring a larger regret and so, the notion of lower bound should be precisely defined. Also, prior works in this literature have provided Pareto-optimal curves for these two objectives.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work without any potential ethical concerns. The authors have done a good job describing the scope of their work and its limitations throughout the paper.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours"}, "extra_text": {}}, {"review_id": "GYui4qQ9Gfc", "reviewer": "Reviewer_uXtV", "summary": "The paper investigates the problem of online convex optimization under metric switching constraints in the non-stochastic setting. In particular, the goal is to minimize a convex loss function where the long-term cumulative switching cost is subject to a stringent budget constraint. A lower bound which accounts for switching constraint is obtained. It is shown that gradient-descent achieves the minimax optimal regret bound.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of this paper is to formulate the OCO problem with metric switching costs, and providing a lower bound for the regret. The main analysis tools seem to be straightforward, maybe except the adaptive adversary that bases its decisions on the history to achieve sharper lower bounds. The upper bound is achieved by the online gradient descent algorithm, which does not incorporate the switching cost dynamics but still achieves the minimax bound, thus the switching cost formulation does not yield a significant change in the algorithm behavior. This implies that the problem is somewhat simple, and limits the contribution of the paper.\n\n- The proposed optimization algorithm is pretty straightforward, i.e., online gradient descent (OGD) with projection, therefore there is not much novelty in the algorithm design part. According to the proof of Theorem 2 in the Supplementary Material, the proof also follows from well-known analysis techniques.\n\n- Interestingly, the only place where switching constraint $S$ comes into play is the step-size choice $\\eta$ in OGD. Other than that, the algorithm ignores the switching constraint, and it still achieves minimax regret by a straightforward analysis. This implies that, technically, incorporating the switching cost constraints does not lead to a big challenge in the algorithm design.\n\n- In case the switching constraint $S$ is not available a priori, could it be possible to find an adaptive policy to choose the step-size? Also, could it be possible to improve the regret coefficients by a different design which takes the history into account (similar to the lower bound)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies an interesting variant of OCO with continuous switching constraints. I have found the contributions of the paper quite interesting and novel. This is a very nice extension to the work by Chen et al 2020. So I recommend acceptance.  
Decision: Accept (Poster)