Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
Authors: Stephen Pasteris
Chris Hicks
Vasilios Mavroudis
Mark Herbster
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Online Convex Optimisation
Non-stationary Learning
Primary area: online_learning

Abstract: We consider the classic problem of online convex optimisation. Whereas the notion of static regret is relevant for stationary problems, the notion of switching regret is more appropriate for non-stationary problems. A switching regret is defined relative to any segmentation of the trial sequence, and is equal to the sum of the static regrets of each segment. In this paper we show that, perhaps surprisingly, we can achieve the asymptotically optimal switching regret on every possible segmentation simultaneously. Our algorithm for doing so is very efficient: having a space and per-trial time complexity that is logarithmic in the time-horizon. Our algorithm also obtains novel bounds on its dynamic regret: being adaptive to variations in the rate of change of the comparator sequence.

Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
Stephen Pasteris
Chris Hicks
Vasilios Mavroudis
The Alan Turing Institute
The Alan Turing Institute
The Alan Turing Institute
London UK
London UK w.hicks@turinggeee ac. uk
London UK
spasteris@turing.. ac
vmavroudis@@urinng... ac uk
Mark Herbster
University College London
London UK
m. www.sterrrsssc.oo uct.eeerrrrsuull...... acl.ac.uk uk
Abstract
We consider the classic problem of online convex optimisation. Whereas the notion static regret is relevant for stationary problems, the notion of switching regret is more appropriate for non-stationary problems. A switching regret is defined relative to any segmentation of the trial sequence, and is equal to the sum the static regrets of each segment. In this paper show that, perhaps surprisingly, achieve the asymptotically optimal switching regret on every possible segmentation simultaneously. Our algorithm for doing is very efficient: having space and per-trial time complexity that is logarithmic in the time-horizon. Our algorithm also obtains novel bounds on its dynamic regret: being adaptive variations in the rate of change of the comparator sequence.
Introduction
We consider the classic problem of online convex optimisation: problem with numerous real-world applications. In this problem we have an action set which is a bounded convex subset of some cuclidean space. On each trial we select an action from this and then receive a convex function of bounded gradient, which associates the action with a loss. The aim is to minimise the cumulative loss. The static regret is defined the cumulative loss the algorithm minus that of the best constant action in retrospect. It has been shown that the minimax static regret θ( where T is the time horizon, and that it is achieved by the classic mirror descent family of algorithms [2]. However, in dynamic environments a more sensible notion of regret the switching regret, which is defined relative to any segmentation of the trial sequence and is equal to the sum of the static regrets over all segments. Clearly, if the segmentation known a-priori then the minimax switching regret O vAg) where A is the length of the k-th segment, and it is obtained by running mirror descent independently on each segment. Tracking algorithms, instead, attempt to bound the switching regret on every possible segmentation of the trial sequence simultaneously. However, far
are aware, the best such bound until now was O VA In(T)) which is a factor of O [n[])) higher than the optimal we knew the segmentation a-priori. In this paper we (quite remarkably) get rid of this factor: hence obtaining the asymptotically optimal switching regret of O vAx) for every possible segmentation simultaneously. Not only is our algorithm optimal, but is also parameter-free and efficient: having both a space and per-trial time complexity of (In())).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In fact, our algorithm RESET is meta-algorithn which utilises any base algorithm for the online convex optimisation problem at hand. Using online gradient descent [TT] as our base algorithm gives us the above O k Vλx) switching regret bound. However, the constant under the O is dependent on the action set and the possible gradients. By choosing a more appropriate base algorithm that is tailored to the specific problem we can achieve lower constant factors. In particular, when faced with the classic problem of prediction with expert advice with N experts, using Hedge [3] as our base algorithm yields the asymptotically optimal (EE min(Ax, VIn(N)Aa) switching regret (a novel result in itself).
We note that although, like strongly adaptive algorithms 4 segment lengths, we are not necessarily strongly adaptive: in that we do not bound the static regret on any particular segment.
we are adaptive to heterogeneous
Whilst switching regret models discrete changes in the environment, a continuously changing envi- ronment is better modeled by the notion of dynamic regret, which is the difference between the loss of the algorithm and that of any comparator sequence of actions. It is known that algorithms exist which bound the dynamic regret by (( (1 + P)T) where P is the path length of the comparator sequence, However, this bound is not adaptive to variations in the rate that the comparator sequence is changing. RESET, with online gradient descent as the base algorithm, rectifies this: improving the dynamic regret to OEE, (11+ Pa)A&) for any segmentation in which the path length in the k-th segment is PE. We note that this implies the O(Ex VAx) bound on switching regret. However, since we are forced to use online gradient descent as our base algorithm here, this result is not strictly more general than our switching regret result.
Related works: Mirror descent was introduced in to find minimisers of convex functions in convex sets. The same algorithm, however, can also be applied to online convex optimisation: the Hedge algorithm of [5] implementing special case when the convex set a simplex and the convex functions are linear (the so-called experts problem). The O(VT) static regret of Mirror descent was shown to be optimal in [I]. The work [6] studied the non-stationary case in the experts setting: modifying Hedge give an algorithm Fixed share which takes a parameter & and has a switching regret of O( 4T (T) for any segmentation with segments. One issue with Fixed share, however, is that it does not adapt to heterogeneous segment lengths. In order to remedy this, 4 gave a strongly adaptive algorithm which achieved a static regret of (In(T) on any segment of length A. This was improved to Ol ((vIn(T)A) in [8. The work [9] took parameters a, b E N and achieved a static regret of O( ((V(I+ In A)) for any segment of length A E [a, b). However, this still leads to a switching regret of O VA, (T)) for general segmentations. Our work finally achieves the optimal OEEn VAx). The work [1] showed that gradient descent achieves a dynamic regret of O((1 + P)VT), which was improved to (1++))T) in [10] However, prior to both these works, the work t obtained the O ((V(1+ + PYT) bound subject to an optimal parameter tuning. Our work dramatically improves on this bound by being adaptive to variations in the rate of change of the comparator sequence.
(
Notation: Let N be the set of natural numbers excluding O. Given A E N we define [A] := {a e N|a & A}. we define A (a E [0, 1]4 Eie(aj a = 1}, , and we define AN to be the set of natural numbers that are multiples of A. Given predicate p we define [P] = if p is false and define [>] := 1 if is true. Given q, s E N with 2 g let (q = {a E N S a < s).
2 Problem and Results
In this section we introduce the online convex optimisation problem and state the results of this paper. In particular we define and compare the notions of switching and dynamic regret, giving the bounds obtained by our meta-algorithm RESET. Another common notion of regret, not necessarily bounded by RESET, is strongly adaptive regret which we discuss in Section 3.3
2.1 Online Convex Optimisation
Here we describe the classic problem of online convex optimisation, which our meta-algorithm RESET solves. In this problem we have known bounded convex subsets X, G of some euclidean

---

space. We define L to be the set of all convex functions that map A' into R and whose sub -ab-grrddents li in G. The problem proceeds in T' trials. On each trial & [2'] the following happens:
1. We choose some action Dt E X.
2. We receive some loss function & E L.
Our aim is to minimise the cumulative loss:
Ee(x)) ((x)).
tE[T]
Without loss of generality we shall assume that for all t [T] and all E X we have (xx) E [0, 1]. This is without loss of generality as both and the sub-gra bob-gradients RESET, when using mirror descent the base algorithm, is invariant to any constant addition to any loss function. Also, without loss of generality, assume that is an integer power two.
l are bounded and our algorithm
An example of online convex optimisation is prediction with expert advice. Here we have some N N and set of N experts: where on each trial each expert associated with loss in [0. 1]. On each trial we must select an expert (incurring the loss associated with that expert) and then observe the vector of losses for that trial. For this problem we choose X' := AN and G := [0, 1] On each trial & we draw our expert from the probability vector and define the loss function & to be the linear function such that for all E [A] we have that (ee), (that is, the loss of the i-th basis element of R is the loss associated with expert i on trial t. Note that (x(x;) is our expected loss trial t.
2.2 Switching Regret
We now define the notion of switching regret. A segmen! is any of the form (1,8) for q, [T] with 2 q. The static regret with respect to such a segment I is defined as:
R(I)
== max xe ="EX
[(((Z)) - l+(x)))
1EI
which is the total loss incurred on the segment minus that which would have been obtained by always choosing the best constant action in retrospect. A segmentation S is defined as any partition of (7]
into segments. The switching regret with respect to such segmentation S is defined as:
R())
Σ R(I) TES
which is the sum of the static regrets on each segment of S. Note that RT(S) is the total loss of the algorithm minus that which would have been obtained by the best sequence actions which is constant over each segment of S. The following theorem establishes a lower bound on the switching regret with respect to any fixed segmentation, even in the special case in which all the loss functions are linear:
Theorem 2.1. For any segmentation and any algorithum for the online convex optimisation problem. there exists (except in trivial cases) a sequence:
of linear functions, in which:
R') E
Σ VIT
IES
where the constant under the is dependent only on and G.
Proof. Apply the static regret lower bound of each segment independently.
In this paper we develop an algorithm RESET which has an upper-bound that matches this lower bound for every possible segmentation S simultaneously. RESET utilises any algorithm (called the base algorithm) for the online convex optimisation problem hand. The base algorithm must take parameter A E [T') and guarantee that R((A)) O(VA) if it were used directly. We note that online gradient descent [11 is always one such possibility. Computationally. to use online gradient descent, we must be able to compute subgradients of the loss functions and euclidean projections into the set X. The following theorem bounds the switching regret of RESET.

---

Theorem 2.2. Suppose E R is such that for all A E [T). when the base algorithm is run with parameter A, is guaranteed that:
R([A)) S TVA.
Then, for any segmentation S, RESET achieves switching regret of:
5 ( d)
Σ
IES
where:
c: 22/(22
d v (1n(2)/ 2V2).
Proof.
See Section
Clearly, theorems 2.1 and 2.2 show that, for any fixed pair (X, 9). RESET has the asymptotically optimal switching regret for every segmentation simultaneously. However, our result is stronger. For example, take the problem of prediction with expert advice defined above. Here the HEDGE algorithm attains:
R([A]) E O (min (A, vIn(NAA
which is shown be optimal via (the proof' of) theorems 3.6 and 3.7 of and by noting that can always force ((A) regret if A < In(N). Although there is a slight technicality here when segments have length less than (n(N). the proof of Theorem 2.2 still works exactly the same way show that (by applying RESET to HEDGE) we have the asymptotically optimal switching regret for every value of N and every segmentation simultaneously.
RESET is also very efficient, as shown the following theorem.
Theorem 2.3. Given that the base algorithm runs in time of & per trial and requires space of e RESET has a per-trial time complexity of O In(T)) and space complexity of O In(T)).
Proof. Immediate from the RESET algorithm.
2.3 Dynamic Regret
Switching regret measures the performance of the algorithm against the best comparator sequence of actions that constant in each segment. Dynamic regret, the other hand, measures the performance of the algorithm against any comparator sequence. Specifically, given any sequence of actions:
E = (c: it [ 1]} S X
then the dynamic regret with respect & is defined as:
R (E) = Σ (((()))
EE|T
To bound the dynamic regret RESET we introduce the following notion of path length. Specifically, given the above sequence E and a segment I, the path length of & in the segment I is defined as:
P(E,I)
Σ
|e+11 c1l12-
The current state of the art for dynamic regret is the algorithm ADER 10 which achieves a dynamic regret of:
(E) O (v(++ P(E, TDITT)
In this paper we significantly improve on this result, as shown in the following theorem.
Theorem 2.4. When using online grudient descent [[7] as the base algorithm, RESET achieves, for any compurator sequence E and any segmentation S, a dynamic regret of:
(*) E O +
IES
where the constant under the O is dependent only X and G.

---

Proof. See Section
Note that, for any segmentation, the dynamic regret bound of RESET is asymptotically equal to that of running ADER on each segment independently. To achieve this with ADER one would need to know the specific segmentation a-priori. As for the switching regret, RESET achieves this for every segmentation simultaneously. We note that bound is significant improvement on that of ADER since it adaptive to variation the rate change of the comparator sequence.
We note that, given segmentation S, the switching regret (S) is equal to the maximum dynamic regret R" (E) across all sequences that are constant each segment of S. For all Z E S, the fact that I implies that the path length P(E, I) is in (1). This means that Theorem 2.4 implies the switching regret bound of Theorem 2.2 up to a constant factor (dependent on y. and G). However, to obtain Theorem 2.4 we must use online gradient descent as our base algorithm. For prediction with expert advice, for example, online gradient descent not asymptotically optimal for every value of N simultaneouslyy. Hence, when considering switching regret only, Theorem a stronger result.
such & is constant
is
The Algorithm
In this section we describe our meta-algorithm RESET (Recursion over Segment Tree). We first introduce the notation that we will use to describe the base algorithm.
3.1 The Base Algorithm
We now define the notation that data-structure D (which contains the parameter) and is composed of the following three subrountines:
deseribe our base algorithm. The base algorithm utilises
Given [2',, the subroutine INITIALISE(A) returns the initial data-structure with parame- ter A.
At the start of a trial, given the current data-structure 2, the subroutine QUERY (D) returns the output action of the base algorithm for that trial.
At the end of trial f, given the current data-structure D and the loss function &, the subroutine UPDATE &,) returns the updated data-structure (ready for the next trial).
The assumption in Theorem 2.2 implies the following. Suppose have trials g. [T] with 4. and on each trial t E (s, q) we do the following:
1. If then D, INITIALISE(Q 1).
2. Wt (D,RY(DD).
3. D,+1 + &...
Then we have:
max 20 EX
(el()))- -
(1)
3.2 RESET
We now introduce meta-algorithm RESET. First let log:((T) and define the function
3 : x R R
(- (aa/21n((2/A)
pexp
(b,, a, b,
pexp -a 1a/22m222/// + +11 p) exp (-by (bby2
The pseudocode of RESET is given in Algorithm
We now describe RESET. We have set of + levels, where each level [r] U (0) hosts an instance of the base algorithm with parameter 2 and which will reset every 2' trials. On each trial t,
5

---

Algorithm RESET
for [ do 11 + 1/2
Di INITIALISE(2')
end for
for t
[T] do
for i E
[r] [0] do
w
QUFRY(D))
end for zi f- we
for i E [T] do
2 + miw! + (1 11)
end for
a; 2
for E [ do
if E N then
Mi+1 t 1/2
Di+1 - INITIALISE("))
else
Mi+1 < ( ((ww)), (((2)-1),
2*)
+1 + UPDATE( Di, (e)
end if
end for end for
we denote the data-structure of the base algorithm associated with level by Dj, Each level also has an associated number in [0, 1] called the mixing weight. On each trial t, we denote the mixing weight associated with level by p.. We note that the mixing weight de is not necessary.
We now describe the creation the action æ; on trial Note first that each level E [r] U {0} has an associated action wi which is defined the output of QUERY base algorithm for level on trial t. We call these actions the base actions. The action is created by the following recursive process. For each level in order we construct an action z called the propagating action. This action is constructed by a convex combination of the preceding propagating action 2 and the base action wi. Specifically, we start by setting:
is the action selected by the
zt f w
and then, for all levels E [r], once 2; has been constructed we set: 2 + p!wi (1 =
Finally, we output:
Dt 2T. We now turn the update the end of trial L. For all levels U have the following two cases.
If / E 2 then we set:
14 < 1/2
Di < INITIALISE(2
so that the mixing weight and instance of the base algorithm hosted by level are reset. Note that the parameter the base algorithm is 2 This is since is reset every 2 trials.
On the other hand, if t & 2 then we set:
1441 d (p: (ww)) (((x 2
Dis UPDATE( D/, 4
Note that the update of the mixing weight is based the losses of wi and 2 If 2 has higher loss than wi in that the base action performs better than the lower-level propagating action, then the mixing weight increases. This means that the weight of the base action, in the convex combination forming the propagating action of level i, increases. If wi has higher loss than z(-1 then the opposite happens.
Figure illustratees RESET.

---

3
2
2
1 0
2
4
5
6
7 8
Figure I: RESET with 8 trials.
Left: The generation of the base actions and mixing weights. Purple numbers denote levels and black numbers denote trials. Each segment (rectangle) the figure runs an instance the base algorithm (generating the base actions). The mixing weights for each level reset the start of each segment. Mixing weight updates are dependent on the segment length.
Right: The computation of the action æ; on trial t. Purple numbers denote levels. Blue balls denote base actions, red balls denote mixing weights, and black balls denote propagating actions. The final black arrow the output 2/..
3.3 Comparison to Strongly Adaptive Online Learner
RESET has some similarities to the SAOL algorithm of [4.. Unlike RESET, SAOL is strongly adaptive, in that it bounds the static regret on any segment. Specifically, for any segment I, SAOL achieves:
R(I) e O (In(T)
This, however, leads to a switching regret bound that is a factor (In(T)) off the optimal. This additional factor was improved to (VVI(TT) by [8.
Like RESET, SAOL has + levels and utilises base algorithm which constructs, for every trial and level a base action wi in exactly the same way as RESET. then generates, for each trial t, the final action 2, also a convex combination of the base actions, where for each level i E [7]. the coefficient of wof is equal to:
combination of the base actions. We note that RESET, the action at is
14 II
(1 (1-w²) m/). j=i+1
The crucial difference between SAOL and RESET is that, whilst SAOL updates each coefficient in the convex combination directly, the coefficients in RESET are updated by updating each mixing weight directly. It is due to this, and the particular way that the mixing weights are updated, that RESET attains, unlike SAOL, the optimal switching regret.
4 Analysis
Here we prove Theorem 2.2 We will show how to modify this proof in order to prove Theorem 2.4 the end of this section. All lemmas stated in this section proved in Appendix A
Choose any segmentation S. Let + == |S] and for all E [ + 1] define σ such that the k-th segment in S is (0x, Tk+1 1). We define comparator sequence (Ex (2') as follows. For all E [$] define the action:
E = argmin EX
Σ le(x²)
and then, for all t (ax, 0641 1), define e, : ct. Note that:
R'(S)= Σ (l((x)) ( -x (e:)))
(E(T]
In addition let = 2//n(2)/(V2 1). With these definitions in hand we begin the analysis.
7

---

4.1 Hedge
The updates for our mixing weights follow the classic algorithm HEDGE [5] In particular, for each level i [r] we maintain an instance of HEDGE (which restarts every 2' trials) with two experts. On each trial t, the weight of the first expert n4 and the weight of the second is 1 μ4. The loss of the first expert is & (ur)) and the loss of the second (1(2)=1). The purpose the function s is then to update the weights according to the HEDGE algorithm. The following lemma is a classic result about HEDGE.
Lemma 4.1. Given trials q, [T] with q 8, and sequence (aa, be) It E (g. s)) such that for all t E (q,8) 3 we have at, be E [0, 11, and a sequence (pel E (q,8) 8)) defined recursively such that for
all t E (q, 1) we have:
py: : 1/2
Pu+1 == rppr at, b 8 8-9+1)
then have:
Σ (pras pi)b.)
S min
Σ bi s t=g t=q
ae
/ 1/2 9 1).
4.2 The Segment Tree
In this subsection we define the segment tree, which is the geometrical structure that our analysis based on. The segment tree is a full, balanced, binary tree B whose leaves are the elements of
(T') in order from left to right. Given any internal vertex v E B, let <(u) and ((v) be its left and right child respectively. Given any vertex v B, let (v) and (v) be its left-most and right-most
descendent respectively (noting that these are both elements of [T].. Let be the root of B. Given
vertex u E B (r), let f(r) be the parent of v. Given vertex E B, let h(v) be equal to the height of v (that is, the height of the tree B minus the depth of so that leaves have height 0).
Each vertex e E B represents the segment
(u)). i.c. Each vertex represents segment in the
left hand side of Figure (when t = 8). We call a vertex v E B stationary iff there exists k E [Ø]
with d (v) and (0) < 0k+1- Let H be the set of all stationary vertices. We call vertex B
fundamental iff both:
v H.
* or ((v) H.
Let FF be the set of all fundamental vertices. We call a vertex v E B relevant iff it is an ancestor of fundamental vertex. Let A be the set of all relevant vertices. For all relevant vertices e E A we define @(v) to the set of descendants of e that are contained in F.
We have, from the algorithm, the following lemma about the vertices of the segment tree: Lemma 4.2. Given any vertex U we have:
+1+ 20)))
and:
h(o) (0)
= 1/2
Db(() (v)
INITIALISE 20())
and for all E [((), (v) 1] we have;
Pr+1 = ab ( (
h(v)
h(v) l (w) k(w)) le (2 24(1)
k(e) r+1
(Dh(o) .1).
= UPDATE
Note that this lemma shows that for all v E B single instance of both the base algorithm and HEDGE over the segment ( (v), (u)), as illustrated in Figure]
4.3 The Recursive Equations
We now derive the recursive equations that our analysis is based on. First note that for all E F there exists u E such that e, = u for all t E (x)), (v)). Hence, Lemma 4.2 and Equation (I). and the fact that w.
A(v) is the output of QUERY (D, k(e) lead to the following lemma.

---

Lemma 4.3. For all E F we have:
(v)
(0) ((()) + 2
Σ
Es wi
h(w)
Note that, from the algorithm and the convexity of the loss functions, we have, for E [7] and all E B with h(v) of O, that:
& 2t
A(v)
14 A(v)
(w, M(w)
(1- ( le (2(22 (2((0)-1)
So, by lemmas 4.2
4.] we have the following lemma.
Lemma 4.4. For all vertices B with h(v) # we have:
(v]
(v)
(v)
l
h(v) 2 )
I min Σ
ls W (
le 2
/ 2 In
Noting that z w. for all t E [T], lemmas equations. For all v F we have:
4.3 and 4.4 immediately imply the following recursive
(1)
Σ
l (z) h(v)
(((E)) + (7+ 221((2) v 22h(2)
(3)
and for all E A F we have:
(t)
le 2t
h(v)
S
le 2t ( + 22
4.4 Performing the Recursion
We now utilise equations (3) and ( to perform the recursion. Specifically, we have the following inductive hypothesis for vertices in A, which is proved by induction up the tree B from the vertices in to the root. The reason holds for vertices in comes direct from Equation (3). For a vertex in A F. F. once the inductive hypothesis has been shown to hold for both its children, is then shown to hold for the vertex itself by Equation 4 The inductive hypothesis is given in the following lemma.
Lemma 4.5. For all E A we have:
A(#)
Σ ((2))0))
Σ le(E:)
Σ GEQ(1)
7+ 2l
Σ
V2-k
22h(o).
In particular, this inductive hypothesis holds for = r. By Equation Lemma 4.6. We have:
this gives us the following.
RT( (7+ Σ 22(()
qEF
We now have a bound on the switching regret. is, however, not yet written in terms of the segment lengths. To write it in terms of the segment lengths partition F into sequence of sets (F& l: E [ such that, for all & E (+), we define Fx to be equal to the set of all v E F such that Ok S (0) and (v) dk+1- We now have the following lemma.
Lemma 4.7. For all [4b we have:
Σ DEFi
22(x) S Co/O411 - -0k
Combining lemmas 4.6 and 4.7 gives us:
Ri(S) S (7 + a)
24(() (7 a)
2h()
d7 + Σ
ak
BEF
kE( vEFi
kE
required. This completes the proof of Theorem 2.

---

4.5 Dynamic Regret Analysis
We now prove Theorem 2.4 Let the base algorithm be online gradient descent as [1 Take any segmentation S" and any comparator sequence &. Let v |S*| and for all j E [ let Zy be the j-th segment in S For all j [v], note that we can choose natural number:
N 1+ P(E,I,)
and partition Sj of Zj into Nj segments such that for all I Sj we have:
P(E,I) O(1)
(5)
Now define the segmentation:
S: U Sj
jElV
Note that Equation (5) implics that for all we have:
P(E,I)= O()).
(6)
We now modify the analysis of the switching regret follows. In the analysis of the switching regret we defined a comparator sequence (E: it [T]). In this analysis we instead define this comparator sequence equal E. Using the segmentation S, construct the segment tree and the sets A and F as in the analysis of the switching regret. Since our base algorithm is gradient descent we have, direct from [1], the following lemma.
Lemma 4.8. Suppose we have trials q, E [T] with s 2 9. and on each trial t E (s. g) we do the following:
1. Ift s then Dj < INITIALISE(Q 1).
2. Wt QUERY(D.).
3. D &P..
Then have:
(l((w)) - (e(c)) E (11+ ( P(E, (a s))) - s+1)
This lemma, along with Lemma 4.2 and Equation 6 gives the following.
Lemma 4.9. For all E F we have:
(u)
Σ
le w h(v)
Le(E.) +o (00(((22))))
This lemma is essentially identical to, and will be used instead of, Lemma 4.3 the analysis of the switching regret gives us:
Following the rest of
R² E O Σ
o
ΣΣ
V
JELN IES
Note that for all j E [T] we have |5 = N₂ and hence:
Σ
S N Σ 7 N,III S (1+ P(E,1)))))
LEST
IES
we have proved Theorem 2.4
Acknowledgements
Research funded by the Defence Science and Technology Laboratory (Dstl) which an executive agency of the UK Ministry of Defence providing world class expertise and delivering cutting-edge science and technology for the benefit of the nation and allies. The research supports the Autonomous Resilient Cyber Defence (ARCD) project within the Dstl Cyber Defence Enhancement programme.
10

---

References
[1] Jacob D. Abernethy, Alekh Agarwal, Peter L. Bartlett, and Alexander Rakhlin. A stochastic view of optimal regret through minimax duality. Conference Learning Theory, 2009.
[2] Charles E. Blair. Problem complexity and method efficiency in optimization (a. s. nemirovsky and d. b. yudin). Siam Review, 27:264 265, 1985.
[3] Nicolò Sesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. 2006.
[4] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. International Conference on Machine Learning, 2015.
[5] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application boosting. In European Conference on Computational Learning Theory, 1997.
[6] Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32:151- 178, 1995.
[7] Mark Herbster and Manfred Warmuth. Tracking the best linear predictor. J. Mach. Learn. Res., 1:281-309, 2001.
[8] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca M. Willett. Improved strongly adaptive online learning using coin betting. In International Conference on Artificial Intelligence and Statistics, 2016.
[9] Yuanyu Wan, TU Wei-Wei, and Lijun Zhang. Strongly adaptive online learning over partial intervals. Science China Information Sciences, 65, 2022.
[10] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou, Adaptive online learning in dynamic environments. Neural Information Processing Systems, 2018
[11] Martin A. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference Machine Learning, 2003.
A Proofs
Here we prove, in order, all the lemmas in the analysis.
A.1
Lemma
4.1
Direct from
using only two experts, were, on each trial I, we have that:
The loss of the first expert is a, and the loss of the second is b,.
The weight of the first expert is Pt and the weight of the second is 1 Pt.
A.2 Lemma 4.2
The equality:
(v) (v) + (w)
comes directly from the definition of h(v)). We also have that:
(v) E 24())
and for all & (v) 1] we have:
Hence, by the algorithm, the lemma holds.

---

A.3 Lemma
Note first that, since wi A(t) is the output of QUERY(D((()) Lemma 4.2 and Equation immediately give us:
le 10 (1op(o))) (((x0)) y 2V22( 2h(w).
2e EX
Since F we have that v E so there exists hs E ($) with 0k S (e) and > (v) < 0R+1- This implies that for all E
(v)) we have t (Øo, Ok+1 1) so that ég. Hence, we have:
(v)
(v)
min
(((x))
(((xx) Σ
E((e))
Substituting into Equation
gives the result.
A.4
Lemma
4.4
Consider Lemma 4.1 In this lemma choose q
(v) and 8: (v). For all E (q, 8) choose:
ax = & (w)" (
br =- le (2(100-11
Then by Lemma 4.2 we have, for all E s), that:
Pt Mr A(v)
so that, by the algorithm and the convexity of the loss functions we have, for all E {4, 8), that:
le (z( M(m))
S h(())
Le
h(0))
+ (1 He (1( ls (z/ (z)
prat + (1 pr)
and hence, by Lemma 4.1 we have:
Ee
h(v))
S
min
Σ at
Σ bt
(2) - a 1). +
t=q
The result then follows from the fact that, by Lemma
4.2 we have s - 2h())
A.5 Lemma 4.5
For l E NU (0) we define:
k
A = Σ V2-
1=0
so our inductive hypothesis that for all E have:
(e)
h(v) 2t
l((e)) +
Σ
(7+ Ag (2)())) V2h(a).
gEQ(v)
I IF then, by the definition of F, we have Q(v) = {v} so the inductive hypothesis holds by Equation 33) Now suppose have some ū E A F. Note that, by the definition of F. have a()), E A so all that is left to prove the inductive hypothesis is to prove that, if the inductive hypothesis holds for both v <()) and = =(0), then also holds for ö. So suppose that the inductive hypothesis holds for v = 4()) and v = -()). First note that:
(6)
(a()))
(D()))
(2)
(
Σ
(2 M((())
Σ
(e
le (2
(8)
(a()))
(P)))
and, by the definition of F. (and a simple induction up the tree B from the vertices in F), we have:
Σ
2h(g) = 2h(1)
QEQ(
12

---

so that:
2h(4) / 22( k(6) 222 2-0(())
2b(2) 2-h(()) 2h(0))
9E
(E
Equations
and imply:
6
(a(())
(b(8))
l 2t
h(D)
Σ l 2t
b((()))
Σ (b(6))
l
(z) 2t
(2(((1))
(q{)))
+ (2)
2h(a) v 22(())
(EQ(B)
Applying the inductive hypothesis the terms:
(q()))
(o()))
& A(((())
Σ 4e 22
(<()))
(o()))
and noting that Q(0) (()()) U (()()) and for all q @ we have:
Aa) ())) ()(a(())) b(qy) v 2h())))(()) A V 22
shows the inductive hypothesis holds for v = T. We have hence proved that the inductive hypothesis holds for all A.
A.6
Lemma 4.6
For all E (()) we have:
Mr)-M(()
20
Σ
V2-k $ > V2-k V2/(V2 = al122n(22
k=0
k=
so, since r E A and Q(r) F, Lemma 4.5
gives us:
(r)
l
zz
(r)
(1++a Σ
22(a))
GEF
Since (r) = 1, (r) T and, by the algorithm, 2;
M(r)
= = = D. for all E [T], we then have,
by Equation 2 that:
RT(S) < (7 a
224(g)
9E
as required.
A.7 Lemma
First let:
1/(2- 1).
We take the inductive hypothesis that for all non-empty finite sets 2 C NU (0) we have:
Σ V2h S
Σ 24
(10)
KEZ
KEZ
and we prove by induction on |Z]. In the case that IZ| and hence:
we have 2 = {i} for some i E NU {0}
Σ V2F = v22 < <\V2= E
Σ
2
kEZ
kez
13

---

so the inductive hypothesis holds for 2 1. Now suppose we have some j. E N and that the inductive hypothesis holds for |2] = j. We now show that holds for |2| = j + which will prove that the inductive hypothesis holds always. Specifically, let i max 2, let 2' = 2 \ {i] and let
i' == max 2', Define:
y==2 Σ
2
Z
Note that:
Σ KEZ
2
2 < 22'+1 22
so that y and hence:
V+ Vi
v 1111- v1 12
since the term on the left is monotonic decreasing with y. This implies that:
2 + V22
Σ
2
2
+ Σ
2-=
V2 (vo+ (5++5)=
Σ KEZ'
V
E
KEZ
kEZ'
so that, by the inductive hypothesis (applied to the set Z'), we have:
V2
2
+
2F
&
KEZ
kEZ
KEZ
so the inductive hypothesis holds for |Z| j+ + 1. We have hence proved that the inductive hypothesis
holds always.
Now note that, by the definition of F, we have that the set {( (v), (v)) |0 E Fk) is partition of
(ok; Tk+1 1) so that, by Lemma 4.2 we have:
20() =0+1 0
(11)
DEFt
Assume, for contradiction, that there exists three distinct vertices v, v', v" E F& with h(v) = h(v²) = h(v"). Without loss of generality assume that and v" are the leftmost and rightmost of the three vertices respectively. Also without loss of generality assume that o' is the right child of its parent t(y).. Then must either be equal to lie to the left of the left child of t(v') and hence:
(t(o)) Z 2
and
(t(x)) = (v') < OK-1
so that t(o') E H. But this contradicts the fact that o' E F.
We have hence shown that for any i E [r] U {0} there are at most two distinct vertices v, v' E F with fv(v) = h(2") i. This means that we can partition Fx into two disjoint sets U2 and V4 such that for all i [T] U {0} there exists at most element of the with h(v) i and at most one
element of of V2 with h(v') = By Equation (10) we then have:
/2h(2) SE
Σ
2h(1)
Σ VEVI
(2h(r) SE
Σ 2h(w)
V
DE
HEM
DEVi
so that:
Σ
22 SE
Σ 20(0) +
20(0).
VEFi
velli
NEV.
Noting that for all y, s/" > 0 we have vi + V S V22 + and c 2v2, the above inequality,
along with Equation 11I gives us:
Σ
V2h(2) Sc
Σ 2h(v) = / - dx
vEFi
DEFt
required.
14

---

A.8
Lemma 4.8
Direct from
A.9
Lemma 4.9
By lemmas 4.2 and 4.8 we immediately have that:
(e (wn E((Ee) EO ( P(E, (<()) (u)))) v 2
(1EP
(12)
Since E F we have that there exists l E (+) such that (v) 2 d and (v) < 7k+11 Hence, by Equation we have that:
P(E, (v))) P(E, (0k, 1)) 0(1).
Substituting into Equation
12 gives us the result.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: Our algorithm always achieves the stated bounds on regret and time-complexity and (when using the doubling trick) is parameter free.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification:
All theorems are either referenced proved.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttpe//gguudeeeeeeouuuummbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
18

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This paper conforms to the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This work theoretical in nature and we cannot foresee any societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work is theoretical in nature and we cannot foresee any risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
21


Reviews:
[{"review_id": "aWuOSqAKjM", "reviewer": "Reviewer_HMtq", "summary": "The paper considers the problem of switching and dynamic regret in online convex optimization (OCO). Given any segmentation of $[T]$, the switching regret is equal to the sum of static regrets on each segment. For the switching regret, the best-known bound obtained by prior works was $\\mathcal{O}(\\sum_{k}\\sqrt{\\Lambda_{k} \\ln T})$, where $\\Lambda_{k}$ is the length of the $k$-th segment. However, the lower bound is $\\Omega(\\sum_{k} \\sqrt{\\Lambda_{k}})$, which follows by independently applying the lower bound on the static regret of OCO with convex functions, on each segment. The current paper removes the extra $\\sqrt{\\ln T}$ factor by proposing an efficient algorithm RESET (Recursion over Segment Tree), which has a running time $\\mathcal{O}(\\ln T)$ per iteration (disregarding the cost associated with treating the feasible set). \n\nFor the dynamic regret, it is known from Zhang et al. that a dynamic regret bound of $\\mathcal{O}(\\sqrt{\\mathcal{P}T})$, where $\\mathcal{P}$ denotes the path-length of the comparator sequence, is possible. However, the bound is not sensitive to variation in the path-length. The current work improves upon this by showing that RESET achieves $\\mathcal{O}(\\sum_{k} \\sqrt{\\Lambda_k})$ dynamic regret for any segmentation that has $\\mathcal{O}(1)$ path length on each segment. When the segments have varying lengths, this bound is significantly better.", "questions": "Lines 183--184 are not very clear to me. If I imagine a full, balanced tree with 15 nodes ($T = 8$) with all levels except the leaf nodes being filled, I do not see how 183 holds when $v$ is the parent of the node with the number $7$. Is that a typo?", "limitations": "Yes, the authors have adequately addressed this.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The considered problem is theoretically interesting and the presented algorithm is quite simple with a clean analysis. The writing is to the point. The idea of having a segment tree is natural since segment trees are known to handle interval updates, e.g. sum-query updates over intervals in an array efficiently. The subroutines used by RESET are Mirror Descent and Hedge. The algorithm can be viewed as updates over the (level, time) space, i.e. at each time $t$ we update the parameters $w_{t} ^ {i}, \\mu_{t} ^ {i}, z_{t} ^ {i}$ by Mirror Descent, Hedge, a convex combination (with parameter $\\mu_{t} ^ i$) of $z_{t}^{i - 1}$ and $w_{t} ^ {i}$. However, the analysis proceeds by translating these updates to a recursion defined over the nodes of a segment tree; the recursion is obtained by the updates and the regret guarantees of Mirror Descent and Hedge. The dynamic regret guarantee follows straightforwardly from the analysis of switching regret.", "weaknesses": "I do not see any immediate weakness regarding the contribution of the work. Although the presentation of the paper is good, there is a scope for improvement. I suggest the authors use appropriate punctuation marks to end/continue equations and sentences.\n\nMinor Typo: Definition of Bregman Divergence in Section 3.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the theoretical importance of our results was acknowledged and thank you for your review.\n\n“I suggest the authors use appropriate punctuation”\n- We will ensure appropriate punctuation is used throughout the final camera-ready version of our manuscript.\n\n“Minor typo…”\n- We have fixed the definition of Bregman divergence to include prime on the u in the gradient.\n\n“Lines 183-184 are not very clear to me”\nWe have clarified lines 183-184 in our paper as follows.\n- Note that $\\blacktriangleleft(v)$ and $\\blacktriangleright(v)$ are the leftmost and rightmost descendants of $v$ respectively, and $h(v)$ is the height of $v$ (where the height of a leaf is $0$). Also note that $j\\mathbb{N}$ is the set of all positive multiples of $j$.\nFor your example we have $v$ as the parent of the 7th leaf (node 7). Since $v$ is the parent of a leaf we have $h(v)=1$ so that $2^{h(v)}=2$ and hence $2^{h(v)}\\mathbb{N}$ is the set of even numbers. The leftmost and rightmost descendants of $v$ are 7 and 8 respectively. So Line 183 states that 7-1=6 is even and Line 184 states that all $t\\in[7,8-1]$ (so just $t=7$) are odd.", "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": "", "extra_scores": {}}, {"review_id": "IqNgQCklqr", "reviewer": "Reviewer_KotF", "summary": "This paper studies online convex optimisation under a non-stationary environment. The authors focus on the switching regret, which evaluates the regret on every possible segment of the trials. This paper demonstrates that the additional logarithmic factor $O(\\log T)$ shown in previous results can be improved, and the authors obtain an algorithm with an optimal guarantee.", "questions": "- Does Theorem 4.1 hold for any bounded convex set and Lipschitz convex loss functions? What is the meaning of $\\gamma$ in Theorem 4.1?\n- In Theorem 4 of [3], it is shown that the adaptive regret guarantee can recover the dynamic regret guarantee. Could the author explain the difference between the results achieved in Section 5 and those?\n- What is the relationship between the proposed segment tree and the geometric covering [2]?\n- At Line 144, it seems that new algorithms are initialized at some specific trials. The analysis of such an algorithm can be reduced to analyzing the sleeping expert problem [3], which usually requires the aggregating algorithm to have specific properties for minimizing general convex functions. Does the aggregating algorithm used in this paper have such properties?\n- At Line 189, this paper analyzes the aggregating step in a black-box manner by using Theorem 3.2. The aggregating algorithm might be sensitive to the decision point at time $q$ in order to provide guarantees on any interval starting at time $q$. How does the proof avoid the analysis of this issue?\n\n3. H. Luo and R. E. Schapire. Achieving all with no parameters: Adanormalhedge.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "This paper studies online convex optimisation under more challenging scenarios, and focuses on an important theoretical question: whether the additional logarithmic factor can be improved.", "weaknesses": "- As a theoretical paper that claims to make fundamental improvements, it would be beneficial for the descriptions of theorems to be more precise, rigorous, and comprehensive. For example, I would expect the authors to clarify under which assumptions ($\\mathcal{X}$, loss functions) the theorems hold.\n- The terminologies used in this paper are ambiguous. The term \"switching regret\" or \"tracking regret\" might often be used in a prediction with experts' advice setting, which could be treated as a degenerated version of dynamic regret, a measure considered widely for general convex optimization. The authors do not introduce the term \"adaptive regret\" [1, 2], which seems to be the same optimization objective in this paper, to my understanding. In [2], it is demonstrated that adaptive regret is stronger than tracking regret (or switching regret).\n- There lacks a clear statement of the algorithm. It might improve the readability if the authors could explain the main idea and the key technique straightforwardly about how to achieve the optimal results.\n- It would be better if the authors could provide more discussions about related works. See details in 'Questions'.\n\n1. E. Hazan and C. Seshadhri. Efﬁcient learning algorithms for changing environments.\n2. A. Daniely, A. Gonen, and S. Shalev-Shwartz. Strongly adaptive online learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We will improve the presentation of our paper based on your feedback, as we detail below, and in our comments to the other reviewers.\n\n“it would be beneficial for the descriptions of theorems to be more precise...”\n- All the conditions on $\\mathcal{X}$ and the loss functions are given in the problem description (lines 69-71). The conditions are that $\\mathcal{X}$ is a bounded convex subset of a Euclidean space and that the loss functions are convex with bounded gradients. Algorithmically though (i.e. to utilise mirror descent), we need to be able to compute Bregman projections into the set $\\mathcal{X}$ (the euclidean projection will do to get the general bound) and compute sub-gradients (however, we only actually need to approximate these quantities to some degree). We will edit the theorem statements such that all requirements are contained inside them.\n\n“The terminologies used in this paper are ambiguous.”\n- Thank you. We will clarify the relationships between these different forms of regret in the camera-ready paper as follows.\nThe difference between switching regret and dynamic regret is that, whilst dynamic regret considers a continually changing comparator sequence, switching regret considers a comparator sequence that changes at at most M trials. We chose to focus on switching regret for two reasons: (a) we can use any algorithm as our base algorithm (not just gradient descent) and (b) the result seems more profound from a theoretical perspective. However, when using gradient descent as our base algorithm our dynamic regret bounds imply our switching regret bounds so are stronger.\nAdaptive (and strongly adaptive - which takes into account the segment length) regret is when one bounds the regret on any possible segment - which is different from switching regret which bounds the cumulative regret (over all segments) for any segmentation. We do talk about strongly adaptive regret in lines 53-54. Like strongly-adaptive algorithms we adapt to heterogenous segment lengths (but unlike such algorithms we get rid of the $O(\\ln(T))$ factor).\n\n\"In [2], it is demonstrated that adaptive regret...\"\n- The comparison to switching regret (a.k.a. tracking regret) in [2] is to the FixedShare bound which is not adaptive to heterogenous segment lengths (so is often very far from optimal). Our algorithm, however, is adaptive to heterogenous segment lengths.\n\n“It might improve the readability if the authors could explain the main idea and the key technique straightforwardly”\nWe agree that the paper will benefit from a straightforward verbal explanation of our algorithm and will add this to the paper. We will also include a straightforward summary of the proof, as the proof is needed to explain why the algorithm works.\n\n“provide more discussions about related works”\n- Agreed, thank you. We will prepare an extended related works section for the final paper.\n\nQuestions…\n\n“Does Theorem 4.1 hold for any bounded  convex set and Lipschitz convex loss functions?\n- Indeed!\n\n“What is the meaning of $\\gamma$?”\n- We can utilise any base algorithm (e.g. mirror descent) with O(\\sqrt{T}) static regret bound. $\\gamma$ is the constant factor under that O. We will clarify this. For mirror descent we define $\\gamma$ in Line 116.\n\n“Could the author explain the difference between the results achieved in Section 5 and those in Theorem 4 of [3]”\n- Their theorem contains the O(ln(T)) factor (which we remove) and is not adaptive to varying rates of change in the comparator sequence (which we are). However, we note that (unlike our switching regret bounds) our dynamic regret bounds hold only when using gradient descent as the base algorithm (which does not obtain the O(ln(N)) factor for experts). If the comparator sequence $\\boldsymbol{u}$ in their theorem changes arbitrarily at M trials then the problem is switching regret - where we dramatically outperform by losing the O(ln(T)) factor and by being adaptive to segment lengths.\n\n“What is the relationship between the proposed segment tree and the geometric covering [2]”\n- There is no difference - the segment tree structure itself is used in many works. What is novel about our work is how the computations are performed over the segment tree.\n\n“At Line 144, it seems that new algorithms are initialised…”\n- The mechanics of our algorithm are very different from using a specialist (i.e. sleeping expert) algorithm to aggregate the base actions (defined on Line 139 and constructed via mirror descent) - which would not remove the O(ln(T)) factor. Utilising a specialist algorithm would (implicitly) require a weight for each segment in the segment tree (an object only used in our analysis) which would reduce to maintaining a weight for each base action. The final action would then use these weights to construct a convex combination of the base actions. The weights would then each be updated directly. However, as stated above, this would not remove the O(ln(T)) factor. Our algorithm, however, recursively constructs what we call ``propagating actions’’ where each such action is formed by a linear combination of the respective base action and the previous (i.e. lower level) propagating action. It is the weights involved in these two-action linear combinations that we update. This novel methodology is what allows us to remove the O(ln(T)) factor. Our method does not run into issues when going from linear functions to general convex functions.\n\n“At Line 189, this paper analyses the aggregating step…”\n- We are unsure what you mean here - could you rephrase please? This aggregating step uses a weight to merge the current propagating action and the current base action into the next (higher-level) propagating action. The weight is updated by the losses of both the current propagating action and the current base action. We are not trying to bound the regret on any particular segment/interval but rather the cumulative regret over the whole trial sequence.", "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": "", "extra_scores": {}}, {"review_id": "O4Aagtx9Q5", "reviewer": "Reviewer_YiA9", "summary": "This paper provides an algorithm which achieves a strongly-adaptive*\nswitching regret guarantee, removing the logarithmic penalty\ntypically associated with efficient algorithms achieving strongly-adaptive guarantees.\n\n--- \n*Update after rebuttal: The results are only for switching regret, *not* strongly-adaptive switching regret guarantees", "questions": "- The approach seems very similar in spirit to the classic geometric covering intervals approach,\n  which can also be seen as breaking up [1,T] according to a particular\n  partition tree (see e.g. \"Partition Tree Weighting\" Veness et al. 2013).\n  Could you explain what exactly the segment tree approach is doing to\n  improve over the geometric covering intervals approach to avoid the log(T)\n  penalty?\n- Section 3.3 and Theorem 18 of Chen et al. (2021) (\"Impossible Tuning Made Possible: A New Expert Algorithm and its Applications\")\n  seems to imply that a strongly-adaptive switching regret guarantee is not even possible in the first place.\n  Could you comment on how this does not contradict the results presented here? Is this work leveraging some\n  additional assumption?\n- The result seems to forego all other types of adaptivity, and just accepts\n  penalties of $\\sqrt{b-a}$ on each interval $[b-a]$ instead of adapting to the\n  losses of the experts. Do you think it is possible to get some form of\n  adaptivity to the loss sequence as well, or is this a fundamental limitation of the approach?", "limitations": "The limitations are largely unaddressed. It's clear that some compromises are made to achieve this result,\nbut it's still very unclear to me what exactly they are, and these should have been laid out more clearly in the main text.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 4, "strengths": "If the result is correct, it seems like it could be a breakthrough result,\nremoving a logarithmic penalty from strongly-adaptive guarantees that\nseemed to be necessary.", "weaknesses": "It seems like the segment tree would still require $O(T)$ memory, would it not?\nWhereas existing approaches achieve $O(\\log(T))$ per-round memory and computation.\nSo it seems like the most interestin\nSo if the result is correct, perhaps the takeaway is that the log(T) penalty\nis the cost of reducing the memory consumption of the algorithm.\n\nThe dynamic regret result doesn't seem particularly convincing since it only holds for\ncomparator sequences which do not move much, ie, for sequences that are essentially\njust switching sequences. In fact it seems strange that any interesting\ndynamic regret result could follow from a switching regret one, since the\noptimal switching regret follows from the optimal $\\sqrt{P_T T}$ dynamic regret\nby throwing away information; if the comparator only changes at times\n$\\sigma_1,\\ldots,\\sigma_{S+1}$ then the path-length bound is $\\sum_t \\|u_t-u_{t-1}\\|=\\sum_i \\|u_{\\sigma_i}-u_{\\sigma_{i+1}}\\|\\le S$ for $u\\in\\Delta_{d-1}$\n\n\n\nThe presentation is hard to follow. This work would also probably benefit from having diagrams\ndemonstrating the segment tree in the notation given here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you, we appreciate that the importance of our work as a potential breakthrough was noted. We will improve the presentation of our paper, based on your feedback, as we detail below, and in our comments to the other reviewers.\n\n“If the result is correct, it seems like it could be a breakthrough…”\n- Thank you! :-) - we were very surprised ourselves when we did it. We can assure you that our proofs have been rigorously checked (as confirmed by Reviewer nGaq) and we are confident in our results.\n\n“It seems like the segment tree would still require…”\n- The segment tree is only used in the analysis and is not part of the algorithm, thus our memory requirement is only $O(\\ln(T))$.\n\n“The dynamic regret doesn’t seem particularly convincing…”\n- We can certainly handle comparator sequences that move a lot and are a strict improvement over the previous state of the art of $O(\\sqrt{PT})$ where $P$ is the path length (plus 1). To see why we outperform the the $O(\\sqrt{PT})$ result note that, given the path length is $P$, we can split the trial sequence into at most P segments each with path length $O(1)$. If the j-th segment length is $L_j$ then our bound is $O\\left(\\sum_{j\\in[P]} \\sqrt{L_j}\\right)$. This is never greater than $O\\left(\\sqrt{P\\sum_{j\\in[P]}L_j}\\right)=O(\\sqrt{PT})$.\nNote that we can massively improve on the $O(\\sqrt{PT})$ result. For instance, suppose we have some $S$ much less than $T$, a path length of $P$ in the first $S$ trials and a path length of $1$ in the last $T-S$ trials. Then (by segmenting the first $S$ trials into $P$ segments of path length $O(1)$) our regret bound is at most $\\mathcal{O}(\\sqrt{PS}+\\sqrt{T})$ - a massive improvement on $\\mathcal{O}\\sqrt{PT})$.\nWe will add such discussion to the paper.\n- Our dynamic regret bound is equivalent to the following: given a segmentation such that the length of segment $j$ is $L_j$ and the path-length (plus 1) on segment $j$ is $P_j$ then our regret is $O\\left(\\sum_j\\sqrt{P_jL_j}\\right)$. We will add this to the paper.\n\n“In fact it seems strange that any interesting dynamic regret…”\n- The dynamic regret result doesn’t follow from the switching regret result but is proved in much the same way. Essentially, we take the result that gradient descent over a (known) segment of length L gives a dynamic regret of $O(\\sqrt{L})$ when the path length is $O(1)$ - and substitute that into our analysis. We note that the optimal switching regret does not follow from the $O(\\sqrt{PT})$ dynamic regret bound as this bound is not adaptive to heterogeneous segment lengths.\n\n“…probably benefit from having diagrams…”\n- Thank you for suggesting this - we will include diagrams in the camera ready paper - also to show the recursive generation of propagating actions.\n\nQuestions…\n\n“The approach seems very similar in spirt…”\n- The segment tree structure itself is identical to the geometric covering intervals structure, a binary tree structure that appears in numerous works. What is novel about our algorithm is the computation over this tree. A use of e.g. specialist algorithms would maintain a weight for each of our base actions (constructed by mirror descent), play a convex combination (according to these weights) of the base actions, and then update the weights directly. However, we take a very different approach, recursively constructing “propagating actions” where each propagating action is defined by a convex combination of the previous (i.e. lower level) propagating action and the next (i.e. current level) base action. We then update the weights associated with these 2-action convex combinations. So we still in fact play a convex combination of base actions - it’s just that this convex combination is very different from other methodologies.\n\n“Section 3.3. of Chen et. al… seems to imply…”\n- This impossibility result is for the regret on any particular segment whereas our result is for the regret over the whole trial sequence. Note that the introduction of the seminal paper “strongly adaptive online learning” implies that the main reason for studying strongly adaptive regret (for any particular segment) was to obtain a bound on the whole trial sequence but with heterogenous segment lengths (as we do).\n\n“The result seems to forego all other types of adaptivity…”\n- We will certainly be able to incorporate other types of adaptivity. This is since our algorithm is based on two procedures: a base algorithm (e.g. mirror descent) and 2-expert Hedge - both of which can be made adaptive to various things. However, the final bound (whilst improving on our current bound) may not be able to be written so neatly as the current bound.\n\nLimitations…\n\n“It’s clear that some compromises are made…”\n- We solve the problem given at the start of Section 2.1 with no additional assumptions. We do of course need to be able to compute or approximate Bregman projections and sub-gradients if using mirror descent as our base algorithm, and have now clarified this limitation in the main text.", "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": "", "extra_scores": {}}, {"review_id": "q8tlQX5ldb", "reviewer": "Reviewer_nGaq", "summary": "This paper considers the problem of tracking regret (aka. switching cost). The previous start-of-the-art result has a $\\ln T$ dependence on the final regret bound. This paper claims to remove the extra $\\ln T$ (more specifically, an $\\sqrt{\\ln T}$ factor) and achieve the optimal switching regret.", "questions": "This paper can be further improved by considering the following minor issues:\n1. The investigation and citations of the literature are insufficient. For example, in Line 18, when mirror descent is mentioned for the first time, there should be a citation, but not and only listing the related citations in the related work part.\n2. Some writings are not consistent with standard practices. After the equation in Line 85, there should be a ',' followed by 'which' (not the capital 'Which' in the current version).\n3. I believe that Theorem 2.1 exists in the literature as it is pretty straightforward and simple (by using the lower bound for static regret to attain a lower bound for the switching regret). However, there is no citation on this theorem. I suggest that the authors conduct a more careful check of the literature to refine this part.\n4. The idea of 'multiple levels' in the proposed method is highly similar to the geometric covering proposed in [1], but without necessary discussions about the similarities or differences between them (I believe that the idea is the same). If they are similar, there should be a corresponding citation. The current presentation claims this idea to be one of the contributions of this work, which is misleading. Otherwise, if they are indeed different, I suggest that the authors could add a corresponding discussion in the next version.\n5. The Section 'Analysis' is highly mathematical with little intuition. This section is more like a proof which should be put in the appendix. In the main paper, there should be more discussions about the proof sketch of the analysis, the reason why this paper uses such an algorithm, etc. I suggest that the authors could carefully polish the paper to enhance its readability. \n6. The citations are somewhat inaccurate. For example, [3] (the index in the paper) is actually published at ICML 2015, but the current citation leads to arXiv. And [9] is actually published in NIPS 2018, but the current citation leads to arXiv.\n7. The last part of dynamic regret is a little confusing. Do the authors mean that under the condition that the path length on each segment is bounded by a constant, a switching-regret-type dynamic regret can be achieved? If so, it does not make much sense because under such a strong condition, each segment is nearly stationary, and the dynamic regret degenerates to switching regret in this case.\n\nReferences:\n1. Strongly adaptive online learning, ICML 2015", "limitations": "The authors have adequately addressed the limitations and, if applicable, potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The solution is clear and intuitive. I checked the whole proof and it seems to be correct. The combination way of $z_t^i = \\mu_t^i w_t^i + (1 - \\mu_t^i) z_t^{i-1}$ is impressive as it is different from the traditional weighted combination of $z_t^i = \\sum_i \\mu_t^i w_t^i$. This novel combination method has proven to play an important role in achieving the optimal switching regret. However, Neither the reason why this weighted combination method is able to achieve the desired optimal switching regret nor the comparison with the traditional combination method are explained in the paper. I suggest that the authors could revise the paper to add corresponding discussions.", "weaknesses": "I found the solution impressive. However, the current presentation of the paper is not satisfying enough. As stated in the above part, the reason why this weighted combination method is able to achieve the desired optimal switching regret and the comparison with the traditional combination method are explained in the paper, which are thought to be necessary from my point of view. I believe that the proofs are correct and the method is of importance. However, I am inclined that the current presentation does not meet the acceptance bar of NeurIPS and thus another round of polishment and review would be better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you. We appreciate that you found our solution impressive and will improve the presentation of our paper, based on your feedback, as we detail below and in our comments to the other reviewers.\n\n“However, neither the reason why this weighted combination…”\n- We will add a sketch of the proof which will enable the reader to quickly see why it works. We will also add a comparison to previous methodologies.\n\n“and thus another round of polishment…”\n- We will make significant improvements to the presentation of our paper (moving the full proof to the appendix to give us space to do this) and are certain we can achieve the required NeurIPS standard for the camera-ready deadline.\n\nQuestions:\n\n1,2) Thank you, we will fix these things.\n\n3) Theorems 2.1, 3.1 and 3.2 all exist in the literature and we state where they come from just before the theorem itself.\n\n4) The segment tree structure is identical to the geometric covering structure. We didn’t give a citation since creating this binary tree structure over a chain is a standard mathematical technique that is used in many works. We in no way intended to suggest that the tree structure is novel to us and will add example citations. We agree that we should have cited [1] about the fact we have an instance of the base algorithm for each segment and that the tree reduces to different levels when the chain is the trial sequence.\n\n5) Yes - as stated above we will include a clear and straightforward overview of how and why the algorithm works, deferring the analysis to the appendix.\n\n6) We will fix.\n\n7) Our dynamic regret definition is the same as in other works and our regret bound is a strict improvement over the current state of the art of $O(\\sqrt{PT})$ where $P$ is path length (plus one). This can be seen since, given a comparator sequence with path length of $P$, we can partition the trial sequence into at most $P$ segments each with path length $O(1)$. If the length of the j-th segment is $L_j$ then our regret bound is $\\mathcal{O}\\left(\\sum_{j\\in[P]}\\sqrt{L_j}\\right)$. This is no greater than $\\mathcal{O}\\left(\\sqrt{P\\sum_{j\\in[P]}L_j}\\right)=\\mathcal{O}\\left(\\sqrt{PT}\\right)$.\nNote that we can massively improve on the $O(\\sqrt{PT})$ result. For instance, suppose we have some $S$ much less than $T$, a path length of $P$ in the first $S$ trials and a path length of $1$ is the last $T-S$ trials. Then (by segmenting the first $S$ trials into $P$ segments of path length $O(1)$) our regret bound is at most $\\mathcal{O}(\\sqrt{PS}+\\sqrt{T})$ - a massive improvement on $\\mathcal{O}(\\sqrt{PT})$. Our dynamic regret bound is equivalent to the following: given a segmentation such that the length of segment $j$ is $L_j$ and the path-length (plus 1) on segment $j$ is $P_j$ then our regret is $O\\left(\\sum_j\\sqrt{P_jL_j}\\right)$. We will add such discussion to the paper.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of optimizing switching regret in online convex optimization and provides novel and interesting results. The proposed algorithm achieves optimal switching regret across all possible segmentations simultaneously with $\log T$ space and time complexity. The reviewers unanimously agreed that the approach is non-trivial and that the results are important for the community. Overall, the contribution is significant, but the reviewers have additional suggestions for further refining the presentation. The authors are requested to take these comments into consideration.
Decision: Accept (spotlight)