Online Convex Optimization with Continuous Switching Constraint
Year: 2022

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 overall switching cost. We first investigate the hardness of the problem, and provide a lower bound of order ⌦( p T ) when the switching cost budget S = ⌦( p T ), and ⌦(min{T/S, T}) when S = O( p 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 = ⌦(log T ), and O(min{T/ exp(S) + S, T}) for S = O(log T ).

text: p T ) when the switching cost budget S = ⌦( p T ), and ⌦(min{T/S, T})
when S = O( p 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 = ⌦(log T ), and O(min{T/ exp(S) + S, T}) for S = O(log T ).

heading: 1 Introduction
text: Online convex optimization (OCO) is a fundamental framework for studying sequential decision making problems (Shalev-Shwartz, 2011). Its protocol can be seen as a game between a player and an adversary: In each round t, firstly, the player selects an action wt from a convex set D ✓ Rd. After submitting the answer, a loss function ft : D 7! R is revealed, and the player suffers a loss ft(wt). The goal is to minimize the regret:
R = TX
t=1
ft(wt) min w2D
TX
t=1
ft(w), (1)
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 algorithms and theoretical guarantees (Hazan, 2016; Orabona, 2019). However, most of the existing approaches 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 et 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 cost is strictly
⇤Lijun Zhang is the corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
constrained. To address this problem, recent advances in OCO introduced the switching-constrained problem (Altschuler & Talwar, 2018; Chen et al., 2020), where a hard constraint is imposed to the number of the player’s action shifts, i.e.,
TX
t=2
{wt 6= wt 1}  K, (2)
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 a minimax regret bound of order ⇥(T/ p K).
One limitation of (2) is that it treats different amounts of changes between wt 1 and wt 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 et al., 2010), video streaming (Joseph & de Veciana, 2012) and multi-timescale 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 `2-norm function, i.e., kwt wt 1k. 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 a hard constraint on the overall `2-norm switching cost, i.e.,
TX
t=2
kwt wt 1k  S, (3)
where S 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 (2). For the proposed problem, we firstly observe that, an O(T/ p S) regret bound can be achieved by using the method proposed for the switching-constrained OCO (Chen et al., 2020) under a 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 ⌦( p T ) when S = ⌦( p T ), and ⌦(min{TS , T}) when S = O( p T ). Our basic framework for constructing the lower bound follows the classical linear game (Abernethy et al., 2008), while we adopt a novel continuous-constraint-related 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 is a phase transition phenomenon between large and small switching budget regimes, which is in sharp contrast to the switchingconstrained setting, where the minimax bound always decreases with ⇥(1/ p K). Finally, we propose a variant of OGD for -strongly convex functions, which can achieve an O(log T ) regret bound when S = ⌦(log T ), and an O(T/ exp(S) + S) regret bound when S = O(log T ).

heading: 2 Related Work
text: In this section, we briefly review related work on online convex optimization.

heading: 2.1 Classical OCO
text: The framework of OCO is established by the seminal work of Zinkevich (2003). For general convex functions, Zinkevich (2003) shows that online gradient descent (OGD) with step size on the order of O(1/ p t) enjoys an O( p T ) regret bound. For -strongly convex functions, Hazan et al. (2007) prove that OGD with step size of order O(1/[ t]) achieves an O(log T ) regret bound. Both bounds have been proved to be minimax optimal (Abernethy et al., 2008). For exponentially concave functions, the state-of-the-art algorithm is online Newton step (Hazan et al., 2007), which enjoys an O(d log T ) regret bound, where d is the dimensionality.

heading: 2.2 Switching-constrained OCO
text: One related line of research is the switching-constrained 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 problems (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 a novel online algorithm based on the Poison Process, which can achieve an expected regret of order O(T 3/2/E[K]) for any given expected switching budget E[K]. Therefore, the regret will become sublinear for E[K] = o( p T ). Later, Chen et 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/ p K) regret bound for any given budget K. They also prove that this result is minimax optimal by establishing a matching ⌦(T/ p K) lower bound. We note that, when the action set is bounded (i.e., maxw1,w22D kw1 w2k  D), since
TX
t=2
kwt wt 1k  DK,
we could set K = bS/Dc to satisfy (3) and immediately obtain an O(T/ p S) regret for OCOCSC, but there is still a large gap from the lower bound we provide in this paper. Very recently, a concurrent work (Sherman & Koren, 2021) considered switching-constrained OCO under oblivious adversary setting, and derived ⇥(T/S) bounds. However, we note that: (i) lower bound for the switching-constraint OCO does not translate to a lower bound for our continuous switching cost setting; and (ii) their upper bound for oblivious only holds in expectation, and has an undesirablep d factor.

heading: 2.3 OCO with Ramp Constraints
text: Another related setting is OCO with ramp constraints, which is studied by Badiei et al. (2015). In this setting, at each round, the player must choose an action satisfying the following inequality:
|wt,i wt 1,i|  Xi, (4)
where wt,i denotes the i-th dimension of wt, and Xi is a constant factor. The constraint in (4) limits the player’s action switching in a per-round and per-dimension level. This is very different from the constraint we proposed in (3), which mainly focus on the long-term and overall switching cost. Moreover, we note that, Badiei et al. (2015) assume the player could get access to a sequence of future loss functions before choosing wt, while in this paper we follow the classical OCO framework in which the player can only make use of the historical data.

heading: 2.4 OCO with Long-term Constraints
text: Our proposed problem is also related to OCO with long-term constraints (Mahdavi et al., 2012; Jenatton et al., 2016; Yu et al., 2017), where the action set is written as m convex constraints, i.e.,
D = {w 2 Rd : gi(w)  0, i 2 [m]}, (5)
and we only require these constraints to be satisfied in the long term, i.e., PT
t=1 gi(wt)  0, i 2 [m]. The goal is to minimize regret while keeping PT t=1 gi(wt) 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 time-variant 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 of regret (Neely & Yu, 2017; Liakopoulos et al., 2019; Yi et al., 2020; Valls et al., 2020).

heading: 2.5 Smoothed OCO
text: The problem of smoothed OCO is originally proposed in the dynamic right-sizing for powerproportional data centers (Lin et al., 2012b), and has received great research interests during the past decade (Lin et al., 2012a; Bansal et al., 2015; Antoniadis & 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 ft(·) as well as a switching cost kwt wt 1k, and the goal is to minimize dynamic regret (Zinkevich, 2003) or competitive ratio (Borodin & El-Yaniv, 2005) with respect to ft(wt) + kwt wt 1k. This setting is closely related to but different from OCO-CSC, where the goal is to minimize regret with respect to ft(·), and the overall switching cost is limited by a given budget. Additionally, we note that, similar to Badiei et al. (2015), studies for the smoothed OCO typically assume the player could see ft(·) or sometimes a window of future loss functions (Chen et al., 2015, 2016; Li et al., 2018) before choosing wt. By contrast, in OCO-CSC the player can not obtain these additional information.

heading: 3 Main Results
text: In this section, we present the algorithms and theoretical guarantees for OCO-CSC. Before proceeding to the details, following previous work, we introduce some standard definitions (Boyd & Vandenberghe, 2004) and assumptions (Abernethy et al., 2008).
Defination 1 A function f : D 7! R is convex if 8w1,w2 2 D,
f(w1) f(w2) +rf(w2)>(w1 w2). (6)
Defination 2 A function f : D 7! R is -strongly convex if 8w1,w2 2 D,
f(w1) f(w2) +rf(w2)>(w1 w2) + 2 kw1 w2k2. (7)
Assumption 1 D is a d-dimensional ball of radius D2 , i.e., D = {w|w 2 R d , kwk  D2 }.
Assumption 2 The gradients of all the online functions are bounded by G, i.e.,
max w2D krft(w)k  G, 8t 2 [T ]. (8)

heading: 3.1 Lower Bound for Convex Functions
text: Algorithm 1 Adversary’s Policy 1: ⌧ = 1, l⌧ = 1 2: Observe the player’s action w1 3: Choose m1 such that m>1 w1 = 0 4: for t = 2 to T do 5: Observe the player’s action wt 6: if
Pt j=l⌧+1
kwj wj 1k  cS then 7: Choose mt = mt 1 8: else 9: Choose mt such that m>t wt 0 and m>t ⇣Pt 1 j=1 mj ⌘ 0.
10: Set ⌧ = ⌧ + 1, l⌧ = t 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), our proposed policy is based on the linear game, i.e., in each round, the adversary chooses from a set of bounded linear functions:
F = {f(·) : D 7! R|f(w) = m>w, kmk = G},
which is a subset of convex functions satisfying Assumptions 1 and 2. For this setting, the regret can be written as TX
t=1
ft(wt) min w2D
TX
t=1
ft(w) = TX
t=1
m>t wt min w2D
TX
t=1
mt
!> w = TX
t=1
m>t wt + D
2
TX
t=1
mt ,
(9)
where the third equality is because the minimum is only obtained when
w = D PT t=1 mt
2k PT t=1 mtk .
According to (9), to get a tight lower bound for R, we have to make both PT
t=1 m > t wt and
k PT
t=1 mtk as large as possible. One classical way to achieve this goal is through the orthogonal technique (Abernethy et al., 2008; Chen et al., 2020), that is, in round t, the adversary chooses mt such that m>t wt 0 and m>t ( Pt 1 i=1 mi) 0. Note that such a mt can always be found for d 2. For this technique, it can be easily shown that PT
t=1 m > t wt 0, while k PT t=1 mtk G p T ,
which implies an ⌦(DG p T ) 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 is small. The details is summarized in Algorithm 1. Specifically, in the first round, after observing the player’s action w1, the adversary just simply chooses f1(w) = m>1 w such that m>1 w1 = 0 (Step 3). For round t 2, the adversary divides the time horizon into several epochs. Let the number of epochs be N . For each round t in epoch ⌧ 2 [N ], after obtaining wt, the adversary checks if the cumulative switching cost of the player inside epoch ⌧ exceeds a threshold (Step 6). To be more specific, the adversary will check if
tX
j=l⌧+1
kwj wj 1k  c
S ,
where l⌧ is the start point of epoch ⌧ , `1 = 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 a new mt based on the orthogonal technique, i.e., find mt such that m>t wt 0 and m>t Mt 1 0, where Mt 1 = Pt 1 j=1 mj , and then start a new epoch (Steps 9-10).
The essential idea behind the above policy is that the adversary adaptively divides T iterations into N epochs, such that for each epoch ⌧ 2 [N ], the cumulative switching cost inside of ⌧ is upper bounded by
l⌧+1 1X
j=l⌧+1
kwj wj 1k  c
S ,
and for each epoch ⌧ 2 [N 1], l⌧+1X
j=l⌧+1
kwj wj 1k > c
S .
The above two inequalities help us obtain novel lower bounds for the two terms at the R.H.S. of (9) respectively which depend on S. Specifically, we prove the following two lemmas.
Lemma 1 We have TX
t=1
m>t wt cGT
S .
Lemma 2 We have
TX
t=1
mt
G T p cp
S2 + c .
By appropriately tuning the parameter c, we finally prove the following lower bound.
Theorem 1 For any online algorithm, under any given switching cost budget S, Algorithm 1 can generate a series of loss functions f1(·), . . . , fT (·) satisfying Assumptions 1 and 2, such that
R
8 <
:
0.5DG p T , S 2 [D p T ,DT ] 0.05DGDTS , S 2 [D,D p T ) 0.05DGT, S 2 [0, D).
Remark 1 The above theorem implies that, when S  D, the lower bound for OCO-CSC is linear with respect to T ; When S 2 [D,D p T ), it’s possible to achieve sublinear results, and the lower bound decreases with T/S; for sufficiently large S, i.e., when S = ⌦(D p T ), the lower bound is ⌦(DG p T ), 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-constrained setting, where the lower bound is ⌦(T/ p K), which means that increasing the budget K is always beneficial. Finally, we note that, since
1
D
TX
t=2
kwt wt 1k  TX
t=2
{wt 6= wt 1},
lower bound for the binary switching cost setting (Altschuler & Talwar, 2018; Chen et al., 2020) does not translate to lower bound for our continuous switching cost setting.
Remark 2 We summarize our main ideas for proving Theorem 1 as follows. For the proposed adversary, we firstly show that (Lemma 1, Eq. (26)), inside of each batch, there exists a negative error term caused by the possible non-orthogonality between the player’s decisions and the adversary’s choice. To maximize this error 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 (Eq. (30)) 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 a function of the threshold. Very luckily, we find that the optimal lower bound can be derived by choosing a threshold that maximizes the function.

heading: 3.2 Upper Bounds
text: 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 et al. (2020) enjoys an O(T/ p S) 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 is sufficient for obtaining the matching upper bound. Specifically, in round t, we update wt by
wt+1 = ⇧D [wt ⌘rft(wt)] , (10) where ⇧D[p] denotes projecting p into D, i.e.,
⇧D[p] = argmin w2D
(w p)>(w p).
For this algorithm, we prove the following theoretical guarantee.
Theorem 2 Suppose Assumptions 1 and 2 hold, and all loss functions are convex. Then, under any
given switching cost budget S, OGD with step size
⌘ =
( D
G p T , S 2 [D
p T ,DT ]
S GT , S 2 [0, D
p T )
(11)
satisfies (3), and achieves the following regret:
R 
8 <
:
DG p T , S 2 [D p T ,DT ]
DG DT S , S 2 [D,D
p T )
DGT, S 2 [0, D).
Remark 3 Theorems 1 and 2 show that our proposed algorithm enjoys an O(GD p T ) minimax regret bound for S = ⌦(D p T ), and O(DGmin{DT/S, T}) regret bound for S = O(D p T ). We illustrate the relationship between the minimax regret and S in Figure 1. Finally, we note that the algorithm requires the paramter T as input, but it 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 is still achievable when the loss functions are strongly convex. Specifically, when there are no constraints on the switching cost, the state-ofthe-art algorithm is OGD with a time variant step size ⌘t = 1/[ t], which enjoys an O(log T ) regret bound. For the OCO-CSC setting, in order to control the overall switching cost, we propose to add a tuning parameter at the denominator of the step size. To be more specific, in round t, we update wt by wt+1 = ⇧D [wt ⌘trft(wt)] , (12) where ⌘t = 1 (t+c) , and c > 0 is a constant factor. By configuring c properly, we can obtain the following regret bound.
Theorem 3 Suppose Assumptions 1 and 2 hold, and all loss functions are -strongly convex. Then, under any given switching cost budget S, the algorithm in (12) with
c =
( 0, S 2 [ 2G log(T + 1), DT ]
T exp( 2GS) 1
1, S 2 [0, 2G log(T + 1)) (13)
satisfies (3), and achieves R  D2 + 2G 2 log (T + 1) . for S 2 [ 2G log(T + 1), DT ], and
R  min (
TD 2
exp( 2GS) 1 +GS,DGT
)
for S 2 [0, 2G log(T + 1)).
Remark 4 Theorem 3 implies that, when S 2G log(T + 1), the proposed algorithm enjoys an O(log T ) optimal regret bound; for S  2G log(T + 1), the proposed algorithm achieves an O(T/ exp(S)+S) regret bound. To obtain a sublinear regret bound, consider S = 2G log(T
↵+1). In this case, we have
R  D2T 1 ↵ + 2G 2 log(T↵ + 1),
which is sublinar for ↵ 2 (0, 1].

heading: 4 Theoretical Analysis
text: In this section, we present the proofs for the main conclusions.

heading: 4.1 Proof of Theorem 1
text: When S D p T , the lower bound can be directly obtained by using the minimax linear game provided by (Abernethy et al., 2008). When S 2 [D,D p T ), by the definition of regret, we have
R = TX
t=1
m>t wt
| {z } a1
min w2D
TX
t=1
mt
!> w
| {z } a2
.
Based on Lemmas 1 and 2, we get
R = a1 + a2 G 0.5DT p cp
S2 + c cGT S . (14)
Let c = c0D2, and we have
R G0.5DT p c0D2p
S2 + c0D2 c
0 D 2 GT
S =GD2T
0.5 p c0p
S2 + c0D2 c
0
S
! GD2T
S
0.5 p c0p
1 + c0 c0
! .
where the second inequality is due to D  S. Note that the R.H.S. of the above inequality is a function of c0. To maximize the lower bound, we should solve the following convex problem:
argmax x>0
0.5 p xp
1 + x x,
which is equivalent to finding the solution of the following equation:
16x4 + 32x3 + 49x2 + 15x 1 = 0.
it can be easily shown that the optimal solution x⇤ ⇡ 0.056. Thus, by setting c0 = 0.056, we get
R 0.05GD2T S . (15)
For S 2 (0, D], based on (14) and setting c = 0.056S2, we have
R GT 0.5D p 0.056S2p
S2 + 0.056S2 0.056S
2
S
! GDT ✓ 0.028p 1.056 0.056 ◆ 0.05GDT.
where the second inequality is because S  D.

heading: 4.2 Proof of Theorem 2
text: We first prove that by setting ⌘ as in (11), the constraint in (3) always holds. Let w0t = wt 1 ⌘rft 1(wt 1). We have
TX
t=2
kwt wt 1k  TX
t=2
kw0t wt 1k (10) =
TX
t=2
k⌘rft 1(wt 1)k (8)  ⌘GT, (16)
where the first inequality 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 8w1,w2 2 Rd,
k⇧D(w1) ⇧D(w2)k  kw1 w2k.
Based on (16), for S 2 [D p T ,DT ], we have
TX
t=2
kwt wt 1k  ⌘GT = D p T S.
For S 2 [0, D p T ), we have
TX
t=2
kwt wt 1k  ⌘GT = S
GT GT = S.
Next, we turn to upper bound the regret. Let w⇤ = argminw2D PT
t=1 ft(w). Based on the classical analysis of OGD (Hazan, 2016), we have
kwt w⇤k2  kw0t w⇤k2 =kwt 1 ⌘rft 1(wt 1) w⇤k2
=kwt 1 w⇤k2 + ⌘2krft 1(wt 1)k2
2⌘(wt 1 w⇤)>rft 1(wt 1).
Thus
(wt w⇤)>rft(wt)  kwt w⇤k2 kwt+1 w⇤k2
2⌘ +
⌘ 2 krft(wt)k2.
Based on the convexity of the loss functions and summing the above inequality up from 1 to T , we get
R  TX
t=1
kwt w⇤k2 kwt+1 w⇤k2
2⌘ +
⌘
2
TX
t=1
krft(wt)k2  D
2
2⌘ +
⌘G 2 T
2 . (17)
Thus, for S 2 [D p T ,DT ], we have
R  D 2
2⌘ +
⌘G 2 T
2 = DG
p T . (18)
For S 2 [0, D p T ),
R  D 2
2⌘ +
⌘G 2 T
2 =DG
✓ DT
2S +
S
2D
◆  DG DT
2S +
p T
2
!  DG ✓ DT
2S +
DT
2S
◆ = DG DT
S .
Finally, note that by Assumptions 1 and 2 and the convexity of the loss functions, we always have R  DGT .

heading: 5 Conclusion and Future Work
text: In this paper, we propose a variant of the classical OCO problem, named OCO with continuous switching constraint, where the player suffers a `2-norm switching cost for each action shift, and the overall switching cost is constrained by a given budget S. We first propose an adaptive mini-batch policy for the adversary, based on which we prove that the lower bound for this problem is ⌦( p T ) when S = ⌦( p T ), and ⌦(min{TS , T}) when S = O( p T ). Next, we demonstrate that OGD with a proper configuration of the step size achieves the minimax optimal regret bound. Finally, for -strongly convex functions, we develop a variant of OGD, which has a tunable parameter at the denominator, and we show that it enjoys an O(log T ) regret bound when S = ⌦(log T ), and an O(T/ exp(S) + S) regret bound when S = O(log T ).
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 et al., 2017; Zhang et al., 2019), dynamic regret (Zinkevich, 2003; Zhang et al., 2018), and Universal OCO (van Erven & Koolen, 2016; Wang et al., 2019; Zhang et al., 2021b). Moreover, it is also an interesting question to 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 (2018AAA0101100), NSFC grant 61921006 and 61976112.

Review summaries:
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. 

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.

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.

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})$.