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

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.

“However, neither the reason why this weighted combination…”

• 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.

“and thus another round of polishment…”

• 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.

Questions:

1,2) Thank you, we will fix these things.

3. 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.

4. 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.

5. 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.

6. We will fix.

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

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

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.

“If the result is correct, it seems like it could be a breakthrough…”

• 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.

“It seems like the segment tree would still require…”

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

“The dynamic regret doesn’t seem particularly convincing…”

• 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})$. Note 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})$. We will add such discussion to the paper.
• 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.

“In fact it seems strange that any interesting dynamic regret…”

• 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.

“…probably benefit from having diagrams…”

• Thank you for suggesting this - we will include diagrams in the camera ready paper - also to show the recursive generation of propagating actions.

Questions…

“The approach seems very similar in spirt…”

• 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.

“Section 3.3. of Chen et. al… seems to imply…”

• 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).

“The result seems to forego all other types of adaptivity…”

• 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.

Limitations…

“It’s clear that some compromises are made…”

• 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.

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.

“it would be beneficial for the descriptions of theorems to be more precise...”

• 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.

“The terminologies used in this paper are ambiguous.”

• Thank you. We will clarify the relationships between these different forms of regret in the camera-ready paper as follows. The 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. Adaptive (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).

"In [2], it is demonstrated that adaptive regret..."

• 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.

“It might improve the readability if the authors could explain the main idea and the key technique straightforwardly” We 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.

“provide more discussions about related works”

• Agreed, thank you. We will prepare an extended related works section for the final paper.

Questions…

“Does Theorem 4.1 hold for any bounded convex set and Lipschitz convex loss functions?

• Indeed!

“What is the meaning of $\gamma$?”

• 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.

“Could the author explain the difference between the results achieved in Section 5 and those in Theorem 4 of [3]”

• 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.

“What is the relationship between the proposed segment tree and the geometric covering [2]”

• 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.

“At Line 144, it seems that new algorithms are initialised…”

• 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.

“At Line 189, this paper analyses the aggregating step…”

• 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.

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.

We appreciate that the theoretical importance of our results was acknowledged and thank you for your review.

“I suggest the authors use appropriate punctuation”

• We will ensure appropriate punctuation is used throughout the final camera-ready version of our manuscript.

“Minor typo…”

• We have fixed the definition of Bregman divergence to include prime on the u in the gradient.

“Lines 183-184 are not very clear to me” We have clarified lines 183-184 in our paper as follows.

• 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$. For 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.