Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously

Authors: stephen  pasteris
chris  hicks
vasilios  mavroudis
mark  herbster
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 18:29:46

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.

Main paper: 
 introduction: 
 We consider the classic problem of online convex optimisation: a problem with numerous real-world applications. In this problem we have an action set which is a bounded convex subset of some euclidean space. On each trial we select an action from this set 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 as the cumulative loss of the algorithm minus that of the best constant action in retrospect. It has been shown that the minimax static regret is Θ( √ T ) 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 is 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 is known a-priori then the minimax switching regret is Θ( k √ Λ k ) where Λ k 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, as far as we are aware, the best such bound until now was O( k Λ k ln(T )) which is a factor of O( ln(T )) higher than the optimal if 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( k √ Λ k ) for every possible segmentation simultaneously. Not only is our algorithm optimal, but it is also parameter-free and efficient: having both a space and per-trial time complexity of O(ln(T )).In fact, our algorithm RESET is a meta-algorithm which utilises any base algorithm for the online convex optimisation problem at hand. Using online gradient descent [9] as our base algorithm gives us the above O( k √ Λ k ) 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 [4] as our base algorithm yields the asymptotically optimal O(ln(N ) k √ Λ k ) switching regret (a novel result in itself).We note that although, like strongly adaptive algorithms [3] , we are adaptive to heterogeneous segment lengths, we are not necessarily strongly adaptive: in that we do not bound the static regret on any particular segment.Whilst switching regret models discrete changes in the environment, a continuously changing environment 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 O( (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 O( k (1 + P k )Λ k ) for any segmentation in which the path length in the k-th segment is P k . We note that this implies the O( k √ Λ k ) 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 [2] 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 [4] implementing a special case when the convex set is a simplex and the convex functions are linear (the so-called experts problem). The O( √ T ) static regret of Mirror descent was shown to be optimal in [1] . The work [5] studied the non-stationary case in the experts setting: modifying Hedge to give an algorithm Fixed share which takes a parameter Φ and has a switching regret of O( ΦT ln(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, [3] gave a strongly adaptive algorithm which achieved a static regret of O(ln(T ) √ Λ) on any segment of length Λ. This was improved to O( ln(T )Λ) in [6] . The work [7] ( k √ Λ k ).The work [9] showed that gradient descent achieves a dynamic regret of O(P √ T ), which was improved to O( √ P T ) in [8] . 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 0.Given A ∈ N we define [A] := {a ∈ N | a ≤ A}, we define ∆ A := {a ∈ [0, 1] A | i∈[A] a i = 1}, and we define AN to be the set of natural numbers that are multiples of A. Given a predicate P we define P := 0 if P is false and define P := 1 if P is true. 
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 algorithm RESET. Another common notion of regret, not necessarily bounded by RESET, is strongly adaptive regret which we discuss in Section 3.3.Here we describe the classic problem of online convex optimisation, which our 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 X into R and whose sub-gradients lie in G. The problem proceeds in T trials. On each trial t ∈ [T ] the following happens:1. We choose some action x t ∈ X . 2. We receive some loss function ℓ t ∈ L.Our aim is to minimise the cumulative loss:t∈[T ] ℓ t (x t ) .Without loss of generality we shall assume that for all t ∈ [T ] and all x ∈ X we have ℓ t (x) ∈ [0, 1]. This is without loss of generality as both X and the sub-gradients of ℓ t are bounded and our algorithm RESET, when using mirror descent as the base algorithm, is invariant to any constant addition to any loss function. Also, without loss of generality, assume that T is an integer power of two.An example of online convex optimisation is prediction with expert advice. Here we have some N ∈ N and a set of N experts: where on each trial each expert is associated with a 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 := ∆ N and G := [0, 1] N . On each trial t we draw our expert from the probability vector x t and define the loss function ℓ t to be the linear function such that for all i ∈ [N ] we have that ℓ t (e i ) (that is, the loss of the i-th basis element of R N ) is the loss associated with expert i on trial t. Note that ℓ t (x t ) is our expected loss on trial t.We now define the notion of switching regret. Given any pair of trials q, s ∈ [T ] with q ≤ s we define the static regret on the segment of trials [q, s] by: R(q, s) := maxx * ∈X s t=q (ℓ t (x t ) -ℓ t (x * ))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 sequence of the form:S = ⟨σ k | k ∈ [Φ + 1]⟩ ⊆ [T + 1] where: σ 1 = 1 ; ∀k ∈ [Φ] , σ k+1 > σ k ; σ Φ+1 = T + 1 .Given such a segmentation S, we define, for all k ∈ [Φ], the k-th segment of S to be the set [σ k , σ k+1 -1], noting that the segments partition the set of trials [T ]. The switching regret with respect to such a segmentation S is defined as:R † (S) := k∈[Φ] R(σ k , σ k+1 -1)which is the sum of the static regrets on each segment of S. Note that R † (S) is the total loss of the algorithm minus that which would have been obtained by the best sequence of 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:S = ⟨σ k | k ∈ [Φ + 1]⟩and any algorithm for the online convex optimisation problem, there exists (except in trivial cases) a sequence:⟨ℓ t | t ∈ [T ]⟩ ⊆ L of linear functions, in which: R † (S) ∈ Ω   k∈[Φ] σ k+1 -σ k  where the constant under the Ω is dependent only on X and G.Proof. Apply the static regret lower bound of [1] to 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 at hand. The base algorithm must take a parameter Λ ∈ [T ] and guarantee that R(1, Λ) ∈ O( √ Λ) if it were used directly. We note that online gradient descent [9] 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 . Theorem 2.2. Suppose γ ∈ R is such that for all Λ ∈ [T ], when the base algorithm is run with parameter Λ, it is guaranteed that: R(1, Λ) ≤ γ √ Λ . Then for any segmentation:S = ⟨σ k | k ∈ [Φ + 1]⟩ RESET achieves a switching regret of: R † (S) ≤ (cγ + d) k∈[Φ] σ k+1 -σ k where: c := √ 2/( √ 2 -1) ; d := 8 ln(2)/(3 -2 √ 2) .Proof. See Section 4.Clearly, theorems 2.1 and 2.2 show that, for any fixed pair (X , G), RESET has the asymptotically optimal switching regret for every segmentation simultaneously. However, our result is stronger in that if, for some family of pairs (X , G), the base algorithm has asymptotically optimal static regret (for the entire family) then RESET has the asymptotically optimal switching regret for the entire family at once. An example is prediction with expert advice (described above) where utilising HEDGE [4] as the base algorithm gives us γ ∈ O(ln(N )) which is asymptotically optimal (as proved in [1] ).RESET is also very efficient, as shown in the following theorem. Theorem 2.3. Given that the base algorithm runs in a time of ξ per trial and requires a space of ξ ′ , RESET has a per-trial time complexity of O(ξ ln(T )) and space complexity of O(ξ ′ ln(T ))Proof. Immediate from the RESET algorithm.Switching regret measures the performance of the algorithm against the best comparator sequence of actions that is constant in each segment. Dynamic regret, on the other hand, measures the performance of the algorithm against any comparator sequence. Specifically, given any sequence of actions:E = ⟨ϵ t | t ∈ [T ]⟩ ⊆ Xthen the dynamic regret with respect to E is defined as:R * (E) := t∈[T ] (ℓ t (x t ) -ℓ t (ϵ t )) .To bound the dynamic regret of RESET we introduce the following notion of path length. Specifically, given the above sequence E and trials q, s ∈ [T ] with q ≤ s , the path length of E in the segment [q, s] is defined as:P (E, q, s) = s-1 t=q ∥ϵ t+1 -ϵ t ∥ 2 .The current state of the art for dynamic regret is the algorithm ADER [8] which achieves a dynamic regret of:R * (E) ∈ O (1 + P (E, 1, T ))T .In this paper we significantly improve on this result, as shown in the following theorem.Theorem 2.4. When using online gradient descent [9] as the base algorithm, RESET achieves, for any comparator sequence E and any segmentation:⟨σ k | k ∈ [Φ + 1]⟩ a dynamic regret of: R * (E) ∈ O   k∈[Φ] (1 + P (E, σ k , σ k+1 ))(σ k+1 -σ k )  where the constant under the O is dependent only on X and G.Proof. See Section 4Note 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 our bound is a significant improvement on that of ADER since it is adaptive to variation in the rate of change of the comparator sequence.We note that, given a segmentationS = ⟨σ k | k ∈ [Φ + 1]⟩, the switching regret R † (S) is equal to the maximum dynamic regret R * (E) across all sequences E that are constant in each segment. For all k ∈ [Φ], the fact that such an E is constant on [σ k , σ k+1 -1] implies that the path length P (E, σ k , σ k+1 ) is in O(1). This means that Theorem 2.4 implies the switching regret bound of Theorem 2.2 up to a constant factor (dependent on γ, X and G). However, to obtain Theorem 2.4 we must use online gradient descent as our base algorithm. For some families of pairs (X , G) online gradient descent is not asymptotically optimal for the entire family at once. An example is prediction with expert advice, where Theorem 2.2 shows that we are asymptotically optimal for the entire family at once when using HEDGE as the base algorithm. Hence, when concerned only with switching regret, Theorem 2.2 is a stronger result. 
the algorithm: 
 In this section we describe our algorithm RESET (Recursion over Segment Tree). We first introduce the notation that we will use to describe the base algorithm.We now define the notation that we use to describe our base algorithm. The base algorithm utilises a data-structure D (which contains the parameter) and is composed of the following three subrountines:• Given Λ ∈ [T ], the subroutine INITIALISE(Λ) returns the initial data-structure with parameter Λ. • At the start of a trial, given the current data-structure D, the subroutine QUERY(D) returns the output action of the base algorithm for that trial. • At the end of a trial t, given the current data-structure D and the loss function ℓ t , the subroutine UPDATE(D, ℓ t ) returns the updated data-structure (ready for the next trial).The assumption in Theorem 2.2 implies the following. Suppose we have trials q, s ∈ [T ] with s ≥ q, and on each trial t ∈ [s, q] we do the following:1. If t = s then D t ← INITIALISE(q -s + 1) . 2. w t ← QUERY(D t ) . 3. D t+1 ← UPDATE(D t , ℓ t ) .Then we have:EQUATIONWe now introduce our algorithm RESET. First let τ := log 2 (T ) and define the functionψ : R × R × R × N → R by: ψ(ρ, a, b, Λ) := ρ exp(-a 2 ln(2)/Λ) ρ exp(-a 2 ln(2)/Λ) + (1 -ρ) exp(-b 2 ln(2)/Λ) .The pseudocode of RESET is given in Algorithm 1.Algorithm 1 RESET for i ∈ [τ ] ∪ {0} do µ i 1 ← 1/2 D i 1 ← INITIALISE(2 i ) end for for t ∈ [T ] do for i ∈ [τ ] ∪ {0} do w i t ← QUERY(D i t ) end for z 0 t ← w 0 t for i ∈ [τ ] do z i t ← µ i t w i t + (1 -µ i t )z i-1 t end for x t ← z τ t for i ∈ [τ ] ∪ {0} do if t ∈ 2 i N then µ i t+1 ← 1/2 D i t+1 ← INITIALISE(2 i ) else µ i t+1 ← ψ(µ i t , ℓ t (w i t ), ℓ t (z i-1 t ), 2 i ) D i t+1 ← UPDATE(D i t , ℓ t ) end if end for end forWe now describe RESET. We have a set of τ + 1 levels, where each level i ∈ [τ ] ∪ {0} hosts an instance of the base algorithm, with parameter 2 i . On each trial t, we denote the data-structure of the base algorithm associated with level i by D i t . 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 i by µ i t . We note that the mixing weight µ 0 t is not necessary. We now describe the creation of the action x t on trial t. Note first that each level i ∈ [τ ] ∪ {0} has an associated action w i t which is defined as the output of QUERY(D i t ), so is the action selected by the base algorithm for level i on trial t. We call these actions the base actions. The action x t is created by the following recursive process. For each level i in order we construct an action z i t called the propagating action. This action is constructed by a convex combination of the preceding propagating action z i-1 t and the base action w i t . Specifically, we start by setting: z 0 t ← w 0 t and then, for all levels i ∈ [τ ], once z i-1 t has been constructed we set:z i t ← µ i t w i t + (1 -µ i t )z i-1 t .Finally, we output:x t ← z τ t . We now turn to the update at the end of trial t. For all levels i ∈ [τ ] ∪ {0} we have the following two cases.If t ∈ 2 i N then we set:µ i t+1 ← 1/2 ; D i t+1 ← INITIALISE( 2 i )so that the mixing weight and instance of the base algorithm hosted by level i are reset. Note that the parameter of the base algorithm is 2 i . This is since it is reset every 2 i trials.On the other hand, if t / ∈ 2 i N then we set:µ i t+1 ← ψ( µ i t , ℓ t (w i t ) , ℓ t (z i-1 t ) , 2 i ) ; D i t+1 ← UPDATE( D i t , ℓ t ) .Note that the update of the mixing weight is based on the losses of w i t and z i-1 t . If z i-1 t has a higher loss than w i t , 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 w i t has a higher loss than z i-1 t then the opposite happens. RESET has some similarities to the SAOL algorithm of [3] . Unlike RESET, SAOL is strongly adaptive, in that it bounds the static regret on any segment. Specifically, for any pair of trials q, s ∈ [T ] with q ≤ s , SAOL achieves: R(q, s) ∈ O ln(T ) q -s + 1 .This, however, leads to a switching regret bound that is a factor O(ln(T )) off the optimal. This additional factor was improved to O( ln(T )) by [6] .Like RESET, SAOL has τ levels and utilises a base algorithm which constructs, for every trial t and level i, a base action w i t in exactly the same way as RESET. It then generates, for each trial t, the final action x t as a convex combination of the base actions. We note that in RESET, the action x t is also a convex combination of the base actions, where for each level i ∈ [τ ], the coefficient of w i t is equal to:µ i t τ j=i+1 (1 -µ j t ) .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. 
analysis: 
 Here we prove Theorem 2.2. We show how to modify this proof in order to prove Theorem 2.4 at the end of this section. All lemmas stated in this section are proved in Appendix A.S = ⟨σ k | k ∈ [Φ+1]⟩.We first define a comparator sequence ⟨ϵ t | t ∈ [T ]⟩ as follows. For all k ∈ [Φ] define the action:εk := argmin x * ∈X σ k+1 -1 t=σ k ℓ t (x * )and then, for all t ∈ [σ k , σ k+1 -1], define ϵ t := εk . Note that:EQUATIONIn addition let α := 2 ln(2)/( √ 2 -1). With these definitions in hand we now begin the analysis.The updates for our mixing weights follow the classic algorithm HEDGE [4] . In particular, for each level i ∈ [τ ] we maintain an instance of HEDGE (which restarts every 2 i trials) with two experts. On each trial t, the weight of the first expert is µ i t and the weight of the second is 1 -µ i t . The loss of the first expert is ℓ t (w i t ) and the loss of the second is ℓ t (z i-1 t). The action of the function ψ 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, s ∈ [T ] with q ≤ s , and a sequence ⟨(a t , b t ) | t ∈ [q, s]⟩ such that for all t ∈ [q, s] we have a t , b t ∈ [0, 1], and a sequence ⟨ρ t | t ∈ [q, s]⟩ defined recursively such that for all t ∈ [q, s -1] we have:ρ q := 1/2 ; ρ t+1 := ψ(ρ t , a t , b t , s -q + 1) then we have:s t=q (ρ t a t + (1 -ρ t )b t ) ≤ min s t=q a t , s t=q b t + 2 ln(2)(s -q + 1) .In this subsection we define the segment tree, which is the geometrical structure that our analysis is 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 ∈ B, let ◁(v) 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 r be the root of B. Given a vertex v ∈ B \ {r}, let ↑(v) be the parent of v. Given a vertex v ∈ B, let h(v) be equal to the height of v (that is, the height of the tree B minus the depth of v, so that leaves have height 0).Each vertex v ∈ B represents the segment of trials [◀(v), ▶(v)]. i.e. Each vertex represents a segment in the left hand side of Figure 1 (when t = 8). We call a vertex v ∈ B stationary iff there exists k ∈ [Φ] with σ k ≤ ◀(v) and ▶(v) < σ k+1 . Let H be the set of all stationary vertices. We call a vertex v ∈ B fundamental iff both:• v ∈ H . • v = r or ↑(v) / ∈ H .Let F be the set of all fundamental vertices. We call a vertex v ∈ B relevant iff it is an ancestor of a fundamental vertex. Let A be the set of all relevant vertices. For all relevant vertices v ∈ A we define Q(v) to be the set of descendants of v that are contained in F.We have, from the algorithm, the following lemma about vertices in the segment tree: Lemma 4.2. Given any vertex v ∈ B we have:▶(v) -◀(v) + 1 = 2 h(v) and: µ h(v) ◀(v) = 1/2 ; D h(v) ◀(v) = INITIALISE( 2 h(v)) and for all t ∈ [◀(v), ▶(v) -1] we have:µ h(v) t+1 = ψ µ h(v) t , ℓ t w h(v) t , ℓ t z h(v)-1 t , 2 h(v) ; D h(v) t+1 = UPDATE D h(v) t , ℓ t .Note that this lemma shows that for all v ∈ B we run a single instance of both the base algorithm and HEDGE over the segment [◀(v), ▶(v)], as illustrated in Figure 1 .We now derive the recursive equations that our analysis is based on. First note that for all v ∈ F there exists u ∈ X such that ϵ t = u for all t ∈ [◀(v), ▶(v)]. Hence, Lemma 4.2 and Equation ( 1), and the fact that w h(v) tis the output of QUERY(Dh(v) t) , lead to the following lemma. Lemma 4.3. For all v ∈ F we have:▶(v) t=◀(v) ℓ t w h(v) t ≤ ▶(v) t=◀(v) ℓ t (ϵ t ) + γ 2 h(v) .Note that, from the algorithm and the convexity of the loss functions, we have, for all t ∈ [T ] and all v ∈ B with h(v) ̸ = 0, that:ℓ t z h(v) t ≤ µ h(v) t ℓ t w h(v) t + 1 -µ h(v) t ℓ t z h(v)-1 t .So, by lemmas 4.2 and 4.1, we have the following lemma. Lemma 4.4. For all vertices v ∈ B with h(v) ̸ = 0 we have:▶(v) t=◀(v) ℓ t z h(v) t ≤ min    ▶(v) t=◀(v) ℓ t w h(v) t , ▶(v) t=◀(v) ℓ t z h(v)-1 t    + 2 ln(2)2 h(v) .Noting that z 0 t = w 0 t for all t ∈ [T ], lemmas 4.3 and 4.4 immediately imply the following recursive equations. For all v ∈ F we have:EQUATIONand for all v ∈ A \ F we have:EQUATIONWe now utilise equations ( 3) and (4) 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 F to the root. The reason it holds for vertices in F comes direct from Equation (3). For a vertex in A \ F, once the inductive hypothesis has been shown to hold for both its children, it 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 v ∈ A we have:▶(v) t=◀(v) ℓ t (z h(v) t ) ≤ ▶(v) t=◀(v) ℓ t (ϵ t ) + q∈Q(v)   γ + 2 ln(2) h(v)-h(q) k=0 √ 2 -k   2 h(q) .In particular, this inductive hypothesis holds for v = r. By Equation (2) this gives us the following. Lemma 4.6. We have: R † (S) ≤ (γ + α)q∈F 2 h(q) .We now have a bound on the switching regret. It is, however, not yet written in terms of the segment lengths. To write it in terms of the segment lengths we partition F into a sequence of sets⟨F k | k ∈ [Φ]⟩ such that, for all k ∈ [Φ],we define F k to be equal to the set of all v ∈ F such that σ k ≤ ◀(v) and ▶(v) < σ k+1 . We now have the following lemma.Lemma 4.7. For all k ∈ [Φ] we have:v∈F k 2 h(v) ≤ c σ k+1 -σ k .Combining lemmas 4.6 and 4.7 gives us:R † (S) ≤ (γ + α) v∈F 2 h(v) = (γ + α) k∈[Φ] v∈F k 2 h(v) = c(γ + α) k∈[Φ]σ k+1 -σ k as required. This completes the proof of Theorem 2.2.We now prove Theorem 2.4. Let the base algorithm be online gradient descent as in [9] . Take any segmentation ⟨σ j | j ∈ [Ψ + 1]⟩ and any comparator sequence E. Given any j ∈ [Ψ], note that we can choose a natural number: N j ≤ 1 + P (E, σj , σj+1 ) and a sequence ⟨φ j,i | i ∈ [N j + 1]⟩ of trials such that φ j,1 = σj and φ j,Nj +1 = σj+1 and for all i ∈ [N j ], we have φ j,i+1 > φ j,i and:EQUATION)Now concatenate the sequences ⟨φ j,i | i ∈ [N j ]⟩ for each j ∈ [Ψ] in order, to make a segmentation⟨σ k | k ∈ [Φ + 1]⟩.Note that Equation ( 5) implies that for all k ∈ [Φ] we have:EQUATION)We now modify the analysis of the switching regret as follows. In the analysis of the switching regret we defined a comparator sequence ⟨ϵ t | t ∈ [T ]⟩. In this analysis we instead define this comparator sequence as equal to E. Using the segmentation ⟨σ k | k ∈ [Φ + 1]⟩, 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 [9] , the following lemma. Lemma 4.8. Suppose we have trials q, s ∈ [T ] with s ≥ q, and on each trial t ∈ [s, q] we do the following:1. If t = s then D t ← INITIALISE(q -s + 1) .2. w t ← QUERY(D t ) .3. D t+1 ← UPDATE(D t , ℓ t ) .Then we have:s t=q (ℓ t (w t ) -ℓ t (ϵ t )) ∈ O (1 + P (E, q, s)) q -s + 1 .This lemma, along with Lemma 4.2 and Equation ( 6), gives us the following. Lemma 4.9. For all v ∈ F we have:▶(v) t=◀(v) ℓ t w h(v) t ≤ ▶(v) t=◀(v) ℓ t (ϵ t ) + O 2 h(v) .This lemma is essentially identical to Lemma 4.3. Following the rest of the analysis of the switching regret gives us:R * (E) ∈ O   k∈[Φ] σ k+1 -σ k   = O   j∈[Ψ] i∈[Nj ] φ j,i+1 -φ j,i   .Since:i∈[Nj ] φ j,i+1 -φ j,i ≤ N j i∈[Nj ] (φ j,i+1 -φ j,i ) = N j (σ j+1 -σj )we have proved Theorem 2.4.Note first that, since wh(v) t is the output of QUERY(D h(v) t) , Lemma 4.2 and Equation ( 1) immediately give us:EQUATIONSince v ∈ F we have that v ∈ H so there exists k ∈ [Φ] with σ k ≤ ◀(v) and ▶(v) < σ k+1 . This implies that for all t ∈ [◀(v), ▶(v)] we have t ∈ [σ k , σ k+1 -1] so that ϵ t := εk . Hence, we have:min x * ∈X ▶(v) t=◀(v) ℓ t (x * ) ≤ ▶(v) t=◀(v) ℓ t (ε k ) = ▶(v) t=◀(v) ℓ t (ϵ t ) .Substituting into Equation (7) gives us the result.A.4 Lemma 4.4Consider Lemma 4.1. In this lemma choose q := ◀(v) and s := ▶(v). For all t ∈ [q, s] choose:a t := ℓ t w h(v) t ; b t := ℓ t z h(v)-1 t.Then by Lemma 4.2 we have, for all t ∈ [q, s], that:ρ t = µ h(v) tso that, by the algorithm and the convexity of the loss functions we have, for all t ∈ [q, s], that:ℓ t z h(v) t ≤ µ h(v) t ℓ t w h(v) t + 1 -µ h(v) t ℓ t z h(v)-1 t = ρ t a t + (1 -ρ t )b tand hence, by Lemma 4.1, we have:s t=q ℓ t z h(v) t ≤ min s t=q a t , s t=q b t + 2 ln(2)(s -q + 1) .The result then follows from the fact that, by Lemma 4.2, we have s -q + 1 = 2 h(v) .A.5 Lemma 4.5For i, j ∈ N ∪ {0} with j ≥ i we define:λ j i := j-i k=0 √ 2 -kso our inductive hypothesis is that for all v ∈ A we have:▶(v) t=◀(v) ℓ t z h(v) t ≤ ▶(v) t=◀(v) ℓ t (ϵ t ) + q∈Q(v) γ + λ h(v) h(q) 2 ln(2) 2 h(q) .If v ∈ F then, by the definition of F, we have Q(v) = {v} so the inductive hypothesis holds by Equation (3) . Now suppose we have some ṽ ∈ A \ F. Note that, by the definition of F, we have ◁(ṽ), ▷(ṽ) ∈ A so all that is left to prove the inductive hypothesis is to prove that, if the inductive hypothesis holds for both v = ◁(ṽ) and v = ▷(ṽ) , then it also holds for v = ṽ. So suppose that the inductive hypothesis holds for v = ◁(ṽ) and v = ▷(ṽ). First note that:▶(ṽ)t=◀(ṽ)ℓ t z h(ṽ)-1 t = ▶(◁(ṽ))t=◀(◁(ṽ))ℓ t z h(◁(ṽ)) t + ▶(▷(ṽ))t=◀(▷(ṽ))EQUATIONand, by the definition of F, we have:q∈Q(ṽ) 2 h(q) = 2 h(ṽ)so that:q∈Q(ṽ)2 h(q) 2 h(q)-h(ṽ) = 2 -h(ṽ) q∈Q(ṽ)EQUATIONEquations ( 4), ( 8) and ( 9), imply:▶(ṽ)t=◀(ṽ)ℓ t z h(ṽ) t ≤ ▶(◁(ṽ))t=◀(◁(ṽ))ℓ t z h(◁(ṽ)) t + ▶(▷(ṽ))t=◀(▷(ṽ))ℓ t z h(▷(ṽ)) t + 2 ln(2)q∈Q(ṽ)2 h(q) 2 h(q)-h(ṽ) .Applying the inductive hypothesis to the terms:▶(◁(ṽ))t=◀(◁(ṽ))ℓ t z h(◁(ṽ)) t : ▶(▷(ṽ))t=◀(▷(ṽ))ℓ t z h(▷(ṽ)) tand noting that Q(ṽ) = Q(◁(ṽ)) ∪ Q(▷(ṽ)) and for all q ∈ Q(ṽ) we have:EQUATION+ 2 h(q)-h(ṽ)shows the inductive hypothesis holds for v = ṽ. We have hence proved that the inductive hypothesis holds for all v ∈ A.For all q ∈ Q(r) we have:h(r)-h(q) k=0 √ 2 -k ≤ ∞ k=0 √ 2 -k = √ 2/( √ 2 -1) = α/ 2 ln(2)so, since r ∈ A and Q(r) = F, Lemma 4.5 gives us:▶(r) t=◀(r) ℓ t (z h(r) t ) ≤ ▶(r) t=◀(r) ℓ t (ϵ t ) + (γ + α) q∈F 2 h(q) .Since ◀(r) = 1 , ▶(r) = T and, by the algorithm, z h(r) t = z τ t = x t for all t ∈ [T ], we then have, by Equation ( 2), that:R † (S) ≤ (γ + α) q∈F 2 h(q)as required.A.7 Lemma 4.7First let:ξ := 1/( √ 2 -1) .We take the inductive hypothesis that for all non-empty finite sets Z ⊆ N ∪ {0} we have:EQUATIONand we prove by induction on |Z|. In the case that |Z| = 1 we have Z = {i} for some i ∈ N ∪ {0} and hence:k∈Z √ 2 k = √ 2 i < ξ √ 2 i = ξ k∈Z 2 kso the inductive hypothesis holds for |Z| = 1. Now suppose we have some j ∈ N and that the inductive hypothesis holds for |Z| = j. We now show that it holds for |Z| = j + 1 which will prove that the inductive hypothesis holds always. Specifically, let i := max Z, let Z ′ := Z \ {i} and let i ′ := max Z ′ . Define:y := 2 -i k∈Z ′ 2 k .Note that:k∈Z ′ 2 k ≤ i ′ k=0 2 k < 2 i ′ +1 ≤ 2 iso that y < 1 and hence:1 + y - √ y ≥ √ 1 + 1 - √ 1 = √ 2 -1 = 1/ξ since the term on the left is monotonic decreasing with y. This implies that:k∈Z 2 k = 2 i + k∈Z ′ 2 k = √ 2 i 1 + y ≥ √ 2 i √ y + 1 ξ = k∈Z ′ 2 k + √ 2 i ξso that, by the inductive hypothesis (applied to the set Z ′ ), we have:k∈Z 2 k ≥ 1 ξ k∈Z ′ √ 2 k + √ 2 i ξ = 1 ξ k∈Z √ 2 kso 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:EQUATIONAssume, for contradiction, that there exists three distinct verticesv, v ′ , v ′′ ∈ F k with h(v) = h(v ′ ) = h(v ′′ ).Without loss of generality assume that v and v ′′ are the leftmost and rightmost of the three vertices respectively. Also without loss of generality assume that v ′ is the right child of its parent ↑(v ′ ). Then v must either be equal to or lie to the left of the left child of ↑(v ′ ) and hence:◀(↑(v ′ )) ≥ ◀(v) ≥ σ k and ▶(↑(v ′ )) = ▶(v ′ ) < σ k+1 so that ↑(v ′ ) ∈ H. But this contradicts the fact that v ′ ∈ F.We have hence shown that for any i ∈ [τ ] ∪ {0} there are at most two distinct vertices v, v ′ ∈ F k with h(v) = h(v ′ ) = i. This means that we can partition F k into two disjoint sets U k and V k such that for all i ∈ [τ ] ∪ {0} there exists at most one element v of U k with h(v) = i and at most one element v ′ of V k with h(v ′ ) = i. By Equation (10) we then have:v∈U k 2 h(v) ≤ ξ v∈U k 2 h(v) ; v∈V k 2 h(v) ≤ ξ v∈V k 2 h(v)so that:v∈F k 2 h(v) ≤ ξ v∈U k 2 h(v) + ξ v∈V k 2 h(v) .Noting that for all y, y ′ > 0 we have√ y + √ y ′ ≤ √ 2 √ y + y ′ and c = ξ √ 2, the above inequality, along with Equation (11), gives us:v∈F k 2 h(v) ≤ c v∈F k 2 h(v) = c σ k+1 -σ k as required.A.8 Lemma 4.8Direct from [9] .A.9 Lemma 4.9 By lemmas 4.2 and 4.8 we immediately have that:EQUATION)Since v ∈ F we have that there exists k ∈ [Φ] such that ◀(v) ≥ σ k and ▶(v) < σ k+1 . Hence, by Equation ( 6) , we have that: Justification: This paper conforms to the code of ethics.P (E, ◀(v), ▶(v)) ≤ P (E, σ k , σ k+1 ) ∈ O(1Guidelines:• 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is theoretical in nature and we cannot foresee any societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This work is theoretical in nature and we cannot foresee any risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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). 

For 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.
strength_weakness: strength_weakness: 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.

Minor Typo: Definition of Bregman Divergence in Section 3.1.
questions: 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: limitations: Yes, the authors have adequately addressed this.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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).
- 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.
- It would be better if the authors could provide more discussions about related works. See details in 'Questions'.

1. E. Hazan and C. Seshadhri. Efﬁcient learning algorithms for changing environments.
2. A. Daniely, A. Gonen, and S. Shalev-Shwartz. Strongly adaptive online learning.
questions: 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?
- 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?
- What is the relationship between the proposed segment tree and the geometric covering [2]?
- 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?
- 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?

3. H. Luo and R. E. Schapire. Achieving all with no parameters: Adanormalhedge.
limitations: limitations: NA
paper_summary: paper_summary: This paper provides an algorithm which achieves a strongly-adaptive*
switching regret guarantee, removing the logarithmic penalty
typically associated with efficient algorithms achieving strongly-adaptive guarantees.

--- 
*Update after rebuttal: The results are only for switching regret, *not* strongly-adaptive switching regret guarantees
strength_weakness: strength_weakness: It seems like the segment tree would still require $O(T)$ memory, would it not?
Whereas existing approaches achieve $O(\log(T))$ per-round memory and computation.
So it seems like the most interestin
So if the result is correct, perhaps the takeaway is that the log(T) penalty
is the cost of reducing the memory consumption of the algorithm.

The dynamic regret result doesn't seem particularly convincing since it only holds for
comparator sequences which do not move much, ie, for sequences that are essentially
just switching sequences. In fact it seems strange that any interesting
dynamic regret result could follow from a switching regret one, since the
optimal switching regret follows from the optimal $\sqrt{P_T T}$ dynamic regret
by throwing away information; if the comparator only changes at times
$\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}$



The presentation is hard to follow. This work would also probably benefit from having diagrams
demonstrating the segment tree in the notation given here.
questions: questions: - The approach seems very similar in spirit to the classic geometric covering intervals approach,
  which can also be seen as breaking up [1,T] according to a particular
  partition tree (see e.g. "Partition Tree Weighting" Veness et al. 2013).
  Could you explain what exactly the segment tree approach is doing to
  improve over the geometric covering intervals approach to avoid the log(T)
  penalty?
- Section 3.3 and Theorem 18 of Chen et al. (2021) ("Impossible Tuning Made Possible: A New Expert Algorithm and its Applications")
  seems to imply that a strongly-adaptive switching regret guarantee is not even possible in the first place.
  Could you comment on how this does not contradict the results presented here? Is this work leveraging some
  additional assumption?
- The result seems to forego all other types of adaptivity, and just accepts
  penalties of $\sqrt{b-a}$ on each interval $[b-a]$ instead of adapting to the
  losses of the experts. Do you think it is possible to get some form of
  adaptivity to the loss sequence as well, or is this a fundamental limitation of the approach?
limitations: limitations: The limitations are largely unaddressed. It's clear that some compromises are made to achieve this result,
but it's still very unclear to me what exactly they are, and these should have been laid out more clearly in the main text.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: This paper can be further improved by considering the following minor issues:
1. 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.
2. 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).
3. 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.
4. 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.
5. 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. 
6. 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.
7. 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.

References:
1. Strongly adaptive online learning, ICML 2015
limitations: limitations: The authors have adequately addressed the limitations and, if applicable, potential negative societal impact of their work.

Comments: title: Thanks for the detailed feedback
comment: Thank you - we will polish the paper and incorporate the suggestions of all the reviewers.
Thank you - we shall be incorporating all your suggestions into the camera-ready. As to the exp-concave question - let us read [3], think about it, and get back to you in the post-discussion period.
We thank you for the score increase and your encouraging words about our result. 

We will give, in the camera ready, the final dynamic regret result: that, given any segmentation such that the length of segment $j$ is $L_j$ and the path length (plus one) on segment $j$ is $P_j$, then our regret is $O(\sum_j\sqrt{P_jL_j})$. This makes the essence of the result much clearer and clearly shows our improvement over the state of the art (which is achieved by considering the segmentation which contains the entire trial sequence as its single segment). We will also give the example we gave in the rebuttal to demonstrate that we can radically outperform the previous state of the art.

With regards to the adaption to gradient variation… The base actions can made adaptive to gradient variation. However, the issue is with the aggregating step for constructing propagating actions, which (in its current form) introduces $O(\sqrt{L})$ factors (where $L$ is the length of a segment). We could use (instead of Hedge) for the aggregating step, an algorithm adaptive to gradient variation. Let $p_t$ and $q_t$ be the losses of the current base action and previous (i.e. lower level) propagating action on trial $t$ respectively. Then the goal of the aggregating step is to produce a normalised non-negative vector $(a,b)$, and the objective function on trial $t$ is $f_t(a,b)=ap_t+bq_t$. The derivative of the objective function is $(p_t,q_t)$. Hence, the aggregating step (for the node of the segment tree in question) will add a regret of $\mathcal{O}\left(\sqrt{\sum_{t\in S}((p_{t+1}-p_{t})^2+((q_{t+1}-q_t)^2)}\right)$ where $S$ is the segment associated with the node. This additional regret is based on the losses of the current base action and previous propagating action rather than the gradients of the loss functions. We will think on whether this can be further analysed.

We will be spending significant time improving the readability of the paper and incorporating the other things that the reviewers have suggested.
Thanks for your reply. I went through the author's responses to the other reviews and do not have any further questions. I appreciate the result, however, as other reviewers suggested, please consider polishing the paper in the subsequent revisions.
Thank you for the authors' detailed response. I now have a clearer understanding of how to aggregate base algorithms, which has increased my confidence about this paper. After reevaluating the results of this paper, I realize that the results are indeed interesting to the community. The paper studies another metric that interpolates between adaptive regret and dynamic regret, which prompted me to raise my score. I hope the author can improve the writing in future versions.

As noted by other reviewers, I believe the writing in this paper requires substantial revision to enhance its readability and impact. Given the close relevance of the paper's results and techniques to dynamic regret and adaptive regret, it is crucial to include a dedicated section discussing the connections and distinctions between these measures. It would be beneficial to emphasize early on that the aggregation method used here differs from that in SAOL [1]. To the best of my knowledge, [2] is the first paper to *sequentially* aggregate base algorithms to achieve adaptive regret and dynamic regret. It may be worthwhile to consider comparing the proposed methods with the approach in [2]. In Section 3, providing a formal algorithmic description would improve readability, at least for me. In the analysis sections, I suggest summarizing the analysis into specific lemmas, explaining the significance of each lemma, and how they collectively lead to the final conclusions. More explanation should be provided regarding the analysis of $\mathcal{Q}(v)$; in its current form, I found it challenging to catch the underlying idea.

Additionally, I have another question concerning the technique. Recent work has explored the dynamic regret of exp-concave functions [3], which include important functions in machine learning, such as logistic loss and log loss. I am interested in whether the techniques presented in this paper could be adapted to derive the switching regret bound for exp-concave functions as well.

1. Strongly adaptive online learning, ICML’15.
2. Parameter-free, dynamic, and strongly-adaptive online learning, ICML’20.
3. Optimal dynamic regret in exp-concave online learning, COLT’21.
Thanks to the authors for the detailed feedback. The authors have solved my major concerns. After carefully reading the paper once again, I am more convinced that this paper has made remarkable progress in the field of switching regret. Moreover, after reading the discussion of the authors with Reviewer #YiA9, I realize the significance of the results for the dynamic regret part. However, I think that Section 5 could be rewritten to make sure that Theorem 5.1 is not the final result for dynamic regret but an extension of the switching regret, which holds for **near-stationary** segmentations. And the authors could summarize another theorem (or maybe corollary) to illustrate that Theorem 5.1 suffices to achieve the desired $O(\sqrt{PT})$ dynamic regret, as explained in Question 7 above.

I am also curious about whether it is possible to achieve problem dependent guarantees in switching regret using the method proposed in this work. For example, consider the well-known gradient variation in modern online learning: $V_T = \sum_{t=2}^T \sup_x \\|\nabla f_t(x) - \nabla f_{t-1}(x)\\|^2$ (please refer to [1,2,3] below). Gradient variation is essential due to its profound connections with stochastic/adversarial optimization, game theory, etc [4,5]. Is it possible to achieve its switching regret version of $\sum_k \sqrt{V_k}$, where $V_k$ denotes the gradient variation in the $k$-th segment? If not, what is the main challenge in achieving this?

I raise my score to 7 and hope that the authors can make great efforts to improve the readability of this paper in the camera-ready version.

**References:**

[1] Online Optimization with Gradual Variations, COLT 2012

[2] Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach, NeurIPS 2023

[3] Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization, JMLR 2024

[4] Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness, NeurIPS 2022

[5] Fast Convergence of Regularized Learning in Games, NIPS 2015
We are sorry but we are still confused as to exactly what you mean when you say “particularly in its capacity to accommodate newly initialized experts”. We do indeed only require the standard bound of Hedge for our analysis, and each time we utilise an instance of Hedge it is for the standard Hedge problem with two experts (the experts are action-valued rather than loss-valued but this modification does not damage the Hedge bound due to the convexity of the loss functions). Each instance of Hedge we use is run over a segment corresponding to a node in the segment tree. On each trial in that segment we have (for the specific instance of Hedge) a prediction issued by each of the two experts.

We describe in detail the mechanics of the aggregating step, and how we utilise the Hedge bound, here. To analyse the aggregating step we need to look at it from the segment tree perspective. Each node of the segment tree corresponds to a segment of the trial sequence, and the segments associated with its two children partition its associated segment. We will use the words “segment” and “node” interchangeably in this description. Let’s say that a node is “active” if the current trial is within its corresponding segment. The active nodes correspond to the levels in the algorithm (the lowest level being the leaf). Whilst active, each node/segment contains a "base action" which changes from trial to trial. The base action is formed from mirror descent - which is started at the beginning of the segment (this corresponds to the reinitialisation in the algorithm) and ends at the end of the segment (which is the start of the next segment at that level of the tree and is hence the next reinitialisation). Each active node/segment also contains a "propagating action", which changes from trial to trial and is constructed (recursively via lower-level propagating actions) from the base actions of its descendants. Each active node/segment is associated with two experts (which issue actions as predictions). The first expert is the node/segment’s current base action. The second expert is the current propagating action of the child node that is currently active. Hence, whilst the node is active, there are always exactly two experts. We use Hedge (starting at the beginning of the segment and ending at the end of the segment) to form a convex combination of these two experts. This convex combination is the propagating action for the node/segment currently under discussion. So the (prediction sequence of the) second expert is formed from the concatenation (of the sequences of propagating actions) of the two child segments. This means that the cumulative loss of the second expert is the “cumulative loss of the propagating actions of the left child” plus the “cumulative loss of the propagating actions of the right child”. This can then be plugged into the Hedge bound to give a bound on the cumulative loss of the propagating actions of the node currently under discussion (with respect to those of its children). In our analysis we do this on all “relevant nodes” (defined on Line 175) that are not “fundamental nodes” (defined on Line 172). For fundamental nodes we also utilise the Hedge bound - but for the first expert (i.e. the base action) instead.  Via this methodology we obtain our recursive formula (Equations 5 and 6).

We hope that this has answered your question. We will be adding, to the paper, a full discussion of how and why the algorithm works and will include a complete description of the aggregating step. We would again like to thank you for your comments on unclear parts of our presentation  and we are happy to provide further clarifications as desired.
Thank you for your appreciative words about our result :-). We understand the difficulty to distinguish between our results and a fully strongly-adaptive one in the current manuscript, and we will clarify this explicitly for the camera-ready version. We can assure you and the other reviewers that we will bring the paper’s presentation fully up to standard, incorporating all the aspects raised in each of your reviews.
I thank the authors for their responses. I will restate the last question in my review. In Line 145, it appears that the base algorithm's decisions are reinitialized after certain rounds. Aggregating decisions from newly initialized experts usually requires the aggregating algorithm to provide stronger theoretical guarantees, such as a second-order bound [1]. I am confused about how the algorithm described after Line 128 could provide stronger theoretical guarantees than the classical Hedge algorithm, particularly in its capacity to accommodate newly initialized experts.

The author's rebuttal and responses to other reviewers have resolved some of my concerns and clarified the problem addressed by this paper. I would appreciate it if the author could answer to the question I raised above.

1. Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications, COLT 21.
Thank you for the detailed reply. After reading through it and the replies to the other reviewers, I am significantly more confident about the correctness of the results in this paper, and am convinced that this paper does indeed contain a breakthrough result, so I have decided to significantly raise my score. 

In addition to the clarifications given to my and others' reviews, I request the authors do more to distance this work from the notion of strongly-adaptive regret. Especially in the introduction, the discussion about "achieving $\sqrt{b-a}$ regret on all segments of length b-a simultaneously" implies strong adaptivity and is stronger than what is achieved here, because it implies independence of the segments: $R_{[a,b]}\le O(\sqrt{b-a})$ for any and all $a\le b$ simultaneously. 
In contrast, while the results here do indeed adapt to each of the segments, the guarantee is for the sum of these regrets, $R_{[1,T]}\le \sum_i R_{[a_i,b_i]}\le \sum_i \sqrt{b_i-a_i}$, not for each segment independently. 

From the responses, I do believe that presentation is a *major* concern for the draft submitted. I think making the revisions suggested by each of the reviewers would massively improve the clarity of the paper. Many of the explanations given to the reviewers were convincing and should have been more clear in the main text; I would suggest moving some of the technical details to the appendix to make space to better address the key discussions. However, I do not think this point is grounds for rejection, and will point out that by the camera-ready deadline the authors will have had nearly half a year from the submission deadline to polish the presentation. Given the significance of the result, I think it should be presented where it will can have the highest impact, and am willing to give the authors the benefit of the doubt that the presentation can be raised to an acceptable standard for the venue before the camera-ready deadline.