Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents a generic reduction-based method for obtaining online learning algorithms with adaptive and/or dynamic regret guarantees that have low “projection complexity”, i.e., use the projection operation as few times per round as possible. In fact, subject to the condition that the reduced algorithm queries the gradient and evaluates the loss function at most once per round, it is demonstrated that this reduction results in the algorithm doing at most one projection per round. The relevance of this result is that the dynamic/adaptive regret literature has recently increasingly adopted a two-level hyper-expert setup where decisions of a substantial number of hyper-experts are aggregated every round, and such methods naively would do a projection per expert per round --- such projections being a computationally costly operation. In the paper, the approach is illustrated by applying it to several algorithms (Ader, SACS, AOA) with state-of-the-art dynamic/adaptive/interval dynamic regret bounds --- thus reducing these algorithms’ projection complexity while keeping their performance guarantees.
strengths_and_weaknesses: Overall, I consider this paper to be a high-quality submission: On the one hand, it thoroughly develops and applies, on state-of-the-art terrain, a framework for reducing the computational complexity of OCO algorithms. On the other hand, it exhibits high-quality writing/presentation --- providing a good, largely self-contained, overview of important related literature and results, and giving insight into the developed reduction methods and how to apply them in “practice”. 

In terms of originality, the backbone of the proposed reduction method (“replace the original domain by a Euclidean ball with an appropriately defined surrogate loss, and project back onto original domain”) to a substantial degree originates in a line of work by Cutkosky and Orabona on black-box reductions for parameter-free online learning. The main contribution of the current paper is in recognizing the generic potential of this type of reduction to generate low-projection-complexity state-of-the-art dynamic/adaptive regret algorithms, and showing how to get through the weeds of some complex recent algorithms like SACS in order to bring them into the appropriate shape for this reduction to result in one-per-round projection complexity (which essentially amounts to modifying these algorithms so that they have one gradient/function evaluation per round). I believe, on balance, that this is a high-quality and sufficiently original contribution to the online learning literature.
questions: I am overall happy with the paper’s presentation. As one suggestion, I would recommend --- for the purposes of further driving home the main message (that low projection complexity, as achieved through the proposed reduction, does substantial good for the runtime not just in theory, but also in practice) --- that the authors try to find a way to move some improved runtime plots from the appendix into the main part of the paper.
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies methods making online learning with non-stationary comparators more efficient in terms of the number of projections onto the feasible set in the OCO setting. The authors begin with a typical meta-algorithm for the dynamic/adaptive regret setting, where the meta-algorithm averages predictions over many base algorithms, but each base algorithm (of which there are typically O(log(T)) requires a projection step. The main idea is to replace the feasible set with the smallest Euclidean ball containing it (making the projection trivial) and the loss function with a surrogate loss that allows for the same regret guarantee, run the base algorithms with this easy projection, then do the projection onto the action set afterwards. Since  single projection can be shared by all the base algorithms, resulting in a log(T) reduction in the number of projections (assuming projections to Euclidean balls are free).


This reduction is applied to different algorithms to build projection-efficient algorithms for dynamic regret and small-loss dynamic regret. Finally, the authors also present a new algorithm for interval dynamic regret, which is nice; the SOTA algorithm for this setting, SACS, needs to be heavily modified to obtain the small-loss bound.

strengths_and_weaknesses: The authors make a compelling case for the applicability of their reduction technique and derive several algorithms with great computational properties. Three are presented in the paper. Even without the goal of reducing the number of projections, the surrogate function reduction seems to be a powerful technique and the authors give good reason to know about it. The range of results obtained are impressive.

There are some small presentation issues. It becomes difficult to keep track of all the meta or base algorithm substitutions, some some assistance (e.g. in the form of a table) would be appreciated.

I would also appreciate more discussion about the proof techniques, especially regarding what is novel. One of the main takeaways of this work is the utility of the surrogate loss, and some proof outlines would help.

A few other small presentation issues:
Use "twists" a bit too much, especially in the intro.
Small grammatical mistakes, i.e.
166: the feasibility -> feasibility
174 (and other places): 1 projection -> one projection
Since empirical experiments aren't in the main body, I would not reference them in the abstract.

questions: The authors make a compelling case for the applicability of their reduction technique and derive several algorithms with great computational properties. Three are presented in the paper. Even without the goal of reducing the number of projections, the surrogate function reduction seems to be a powerful technique and the authors give good reason to know about it. The range of results obtained are impressive.

There are some small presentation issues. It becomes difficult to keep track of all the meta or base algorithm substitutions, some some assistance (e.g. in the form of a table) would be appreciated.

I would also appreciate more discussion about the proof techniques, especially regarding what is novel. One of the main takeaways of this work is the utility of the surrogate loss, and some proof outlines would help.

A few other small presentation issues:
Use "twists" a bit too much, especially in the intro.
Small grammatical mistakes, i.e.
166: the feasibility -> feasibility
174 (and other places): 1 projection -> one projection
Since empirical experiments aren't in the main body, I would not reference them in the abstract.

limitations: I think a more thorough discussion of the algorithmic trade-offs needed to ensure single projections is necessary; see my earlier comments. No societal impact discussion is presented or expected.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper presents a reduction that achieves 1 projection complexity for algorithms with low dynamic regret and adaptive regret, which typically have $O(\log T)$ projection complexity, without degrading their regret guarantees. Since the projection operation can be a major bottleneck when the decision set is complicated, the reduction has significant computational advantages over the original algorithm. In cases where the reduction cannot be straightforwardly applied, the work specifies modifications under which 1 projection complexity can be achieved. 

strengths_and_weaknesses: Strengths
- The paper proposes a method to address the computational efficiency problem in dynamic regret/adaptive regret minimization, which has applications in many domains. The proposed method achieves significant computational savings when projecting onto the convex decision set is expensive.
- The reduction is novel as far as I know, and serves as the backbone of a series of algorithms that achieve 1 projection complexity without worsening regret guarantees. When the original algorithm doesn’t satisfy the conditions of the reduction, nontrivial changes are presented to accommodate the requirements, along with their theoretical justifications.
- The paper is very clearly written and concisely presented. 

Weaknesses
- See questions.
questions: To make the impact clear, it would be helpful to explicitly state some settings/problems where the projection step is expensive in the main paper.  

limitations: Yes.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work tackles the topic of time complexity in modern online algorithms. Indeed, to deal with dynamic environments, modern algorithms use a 2-layers structure to obtain strong predictions and it implies at each time step $O(\log(T)$ projections over a possibly complex convex set. Those projections may be time-expensive in practice, and not suitable for many real-life situations.
That is why authors propose a generic mechanism which only involves $O(1)$ projections at each time step. They apply their mechanism onto three distinct algorithms dedicated to minimise different types of regrets: dynamic regret, adaptive regret and interval dynamic regret.
Authors also propose in Appendix A a toy experiment illustrating the efficiency of their procedures.
strengths_and_weaknesses: Strengths: 

- A pedagogical work, clear and well-written.
- The goals of the paper are well stated. The theoretical results are, for me, impacting and come with a convincing toy experiment.
- Any new result or algorithm comes with welcomed explanations and discussions.
 

Weaknesses:
- It would have been good to mention more the existence of experiments within the main document. I believe they constitute an important point of this work but they seems to be quite hidden.
- I think it would have been good to mention a few learning problems which involves concrete complicated convex sets on which the projection step is costful.

Conclusion: 

I congratulate the authors for their work. To me,  they performed a significant step in online learning as they reduced time complexity of modern algorithms with the use of insightful surrogates without sacrificing any performance guarantee. The proposed experiment numerically attest this fact. Furthermore, the proposed work is not only impacting but also clear and well-written, it has been a pleasure to read this document. 
Finally I precise that I am not that familiar with the literature around the adaptive regret, thus I may overestimate the strength of some proposed results but I am confident in the fact that Alg.1, which is a twisted improved Ader is impacting in the dynamic regret field.
However, for all those positive reasons, I give this paper a 8. 




Remark: 
- As I am not familiar with Adaptive Regret literature, I only checked the proofs for Dynamic Regret which are for me, correct.
questions: - I am wondering about the lifetime of the base learners in Alg.2. In lines 8-10, how do we choose the ending points of a new base learner? Is it arbitrary?
- I am not sure to understand what have been the motivation to design $\Tilde{\mathcal{C}}$ in Eq. 10)? Is it possible to have more explanations?
- It is said that the code is available but I did not find any python file in the supplementary nor a link to an anonymous Github, did I miss something?
- An open question: authors state in their conclusion that it would be challenging to incorporate optimistic online learning within this work. But could not we incorporate, at each time, the optimistic information directly within the base algorithm and see where it goes?
limitations: None
review_title: null

Meta-review: metareview: The authors have successfully developed a powerful surrogate-based reduction framework for greatly reducing the projection complexity of online learning algorithms with low adaptive and dynamic regret while preserving regret bounds. They further demonstrate how to use this approach for several recent algorithms with the best-known regret bounds. An additional result is the first algorithm that enjoys a small-loss type bound for the interval dynamic regret (for convex, smooth functions), and the algorithm achieving this also requires only one projection onto the feasible set per round. The reviewers are unanimous in the high quality of this work. This is an impressive and welcome contribution to the proceedings. Congratulations on your fine work!
confidence: Certain
Decision: Accept