Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies online convex optimization in the strongly-adaptive regret setting. Essentially, this paper generalizes MetaGrad, an OCO algorithm which was able to adapt to the type of convexity of the losses, to the strongly adaptive regret setting.

This algorithm is build using the metagrad meta-regret structure, geometric covering, a new surrogate loss function, and a generalization of the sleeping experts analysis. By deriving second-order regret bounds on the sub-intervals, the authors are able to show strongly-adaptive regret guarantees. The proposed algorithms were also shown to have favorable performance in experiments. 

main_review: I think this is a good paper. It solves a natural problem -- the extension of universal OCO algorithms to strongly-adaptive regret -- and presents the new ideas in a clear manner. Generally, the explanations and writing are clear. The results are believable, and the analysis is sufficiently clear.

A few questions and suggestions for improvement:
1) Can you provide some intuition why the alternative surrogate function is needed?
2) Why spend so much time on PAE, as it is a special case of your main algorithm? Some important discussion, like the role and regret guarantees of the slave algorithms, could be a better use of the space in the main body.
3) Can you say anything about lower bounds?

post-rebuttal: Thanks for the clarification, and nice work! I remain positive about the paper.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of minimizing the adaptive regret together with being adaptive to the regularity of the loss function (exp-concavity, strong convexity, convexity,...). On one hand, algorithms and techniques to minimize the adaptive regret already exist but existing results are specific to the curvature of the losses. On the other hand, there exist universal algorithms that are adaptive to broad classes of loss functions (Metagrad and extensions). This paper combines both techniques and provides two algorithms (PAE and UMA) that get both guarantees simultaneously. In particular, it is adaptive to changes in the regularity of the losses. Finally, the authors provide some experiments to illustrate their results.
main_review: On one hand, the paper is generally well-written, and having a generic algorithm that automatically adapts to the regularity of the losses to enjoy the best possible guarantees and can deal with non-stationary environment is surely interesting for the community and can be very useful for applications. In particular, I like the result to be adaptive to changes in the regularity of the loss sequences.

Yet, on the other hand, the results did not surprise me and the contribution is somewhat incremental in my opinion. The technique of sleeping experts is widely used and known to transform any static algorithm into an adaptive regret algorithm (see among many others, Daniely et al. 15, Orabona et al. 2017, Zhang et al. 2018). The Metagrad algorithm and its variants are based on combining experts. Combining their analysis with the sleeping expert procedure seems fairly straightforward and does not provide any technical novelty. In case I missed a new technical difficulty in the analysis, I encourage the authors to highlight it. 

Moreover, I suspect that the results can be also obtained as follows. Second-order bounding algorithms that adapt to loss regularity already exist for the expert framework (see, for example, [1,2,3]). Using such algorithms as the meta-procedure for FLH (Zhang et al. 2018) with MetaGrad as subroutines should achieve this, doesn't it?


Another comment:
Another natural measure to deal with a non-stationary environment in online learning is dynamic regret. I do think that dynamic regret should be discussed in the introduction. As shown by Zhang et al 2018, there exists a reduction from adaptive regret to dynamic regret. Yet, it was shown that the rate obtained by Zhang et al. 2018 was suboptimal for exp-concave loss functions [4]. I would be surprised, but it would be interesting to see if the optimal rate of [4] could be recovered by your method for dynamic regret.


[1] A second-order bound with excess losses. Gaillard, Stoltz, Van Erven, 2014.  
[2] Second-order quantile methods for experts and combinatorial games. Koolen, Van Erven, 2015.  
[3] Optimal learning with Bernstein online aggregation. Wintenberger, 2017.  
[4] Optimal Dynamic Regret in Exp-Concave Online Learning. D Baby, YX Wang, 2021.  
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors develop a universal algorithm, namely UMA, that is able to minimize the adaptive regret of general convex, exp-concave and strongly convex functions simultaneously. The key idea is to modify MetaGrad to support sleeping experts and introduce additional surrogate losses for strongly convex functions and general convex functions. In this way, UMA can minimize the adaptive regret of multiple types of convex functions automatically, and thus is universal. Some experiments are done to evaluate the effectiveness of UMA.
main_review: From the technical viewpoint, UMA is a nice extension of MetaGrad to minimize the adaptive regret. Because MetaGrad has a small meta-regret, the authors are able to maintain the optimality of UMA for different types of functions. This result actually demonstrates that the meta-algorithm of MetaGrad can be used to replace existing meta-algorithms designed for adaptive regret [Hazan and Seshadhri, 2007, Daniely et al., 2015, Jun et al., 2017a].

Strengths:
1. To the best of my knowledge, UMA is the first universal algorithm for minimizing the adaptive regret. Due to the property of universality, UMA can be applied with less manual intervention.
2. For each type of functions, UMA achieves state-of-the-art adaptive regret, and can also handle the case that the type of functions may change.
3. The paper is well-written and the proofs are easy to follow.

Weaknesses:
1. As pointed out by the authors, the main limitation of UMA is that the number of experts is $O(\log^2 t)$, which is larger than previous method by a logarithmic factor.
2. UMA is built upon MetaGrad, and somehow incremental.

limitations_and_societal_impact: Questions:
1. All the adaptive regret bounds have a logarithmic dependence on $T$, which means that the regret over fixed-length intervals keeps increasing as $T$ increases. The logarithmic dependence is usually acceptable, but when $T$ becomes very large, this could be an issue. Is there any way to avoid the dependence on $T$?

2. In Line 50, the authors claim that UMA attains *second-order* regret bounds over any interval. On the other hand, Cutkosky [2020] also establishes a *second-order* bound for adaptive regret. Can the authors discuss the difference between them?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this papers, the authors tackle the problem of online optimization with unknown (or even changing) convex function types, which can be plain convex, exp-concave, or strongly convex. Their main goal is to design an algorithm that suffers asymptotically optimal regret on any time interval. 

To this end they extend the MetaGrad algorithm, a method that guarantees low static regret against plain convex or exp-concave functions, to also handle strongly convex functions and in a way that guarantees low adaptive regret, not only static regret. Their main technical contribution is showing that this can be done by incorporating sleeping experts in the meta algorithm of MetaGrad.
main_review: # Strengths and Weaknesses

## Strengths
- The main paper is well written and clearly poses the question and the challenges involved, what can be a bit hard in this case since there are so many moving pieces;
- Introducing the simpler version first that handles only exp-concave functions does help in the readability;
- Although no technique in isolation is novel, the clever combination of many different techniques to create a truly "universal algorithm" is a solid contribution.

## Weakenesses
- The proofs in the supplementary material are not very well organized and written.
- The experiments are not very well explained (more details later);

# Details and Questions for the Authors

The paper was a nice read and is a solid contribution. As I mentioned, no single piece in isolation is novel, but this is a good combination of many different techniques to devise an interesting "universal" algorithm. Two points I'd like the authors' thoughts are on the supplementary material writing and on the experiments.

The supplementary material has all the proofs, but while I tried to read it (skipping some parts since our time for review is limited), I often got lost. The problem is that the authors start by giving a brief overview of the proof of the main theorems, deferring the proof of a couple of lemmas for later. Yet, they never explicitly say they are going to do that, what makes the reader wonder if they simply omitted the proof or if the proofs are "well-known". Also, each subsection usually consists of one proof, but they often state the lemmas they will need before actually starting the proof. In the end, it is hard to figure out exactly where the statement of lemmas and discussion ends, and where the proofs actually begin.

About the experiments, there are some aspects of them that do not seem fair (or at least not well explained):
- The classical static algorithms (OGD and ONS) should have their parameters chosen by some kind of grid search. It is not clear from the text if the parameters were chosen to be the "theoretically optimal" or if the authors did pick the best parameters for OGD and ONS;
- Why is the interval set at 200? Changing the interval size changes the results by a lot? If not, discussing this (even if in the appendix) would be interesting;
- Different datasets change the results by a lot? You should at least give some reason for using only one single dataset;
- Since you are comparing with ONS and OGD, would it also make sense to compare with one of the adaptive algorithms for static regret (Metagrad or Maler)? Why none of these algorithms were used?
- It would be interesting to provide timing data and the laptop specs, if possible;

limitations_and_societal_impact: Mostly yes, I've only raised some concerns related to the experiments.
review_title: null

Meta-review: In agreement with the reviewers, I am happy to recommend acceptance of the paper. During the review process the authors promised several improvements to the paper (such as discussing and experimenting with the suggested simple black-box algorithm or clarifying that their references to sleeping experts are meant only in a restricted manner), which they must include in the final version of the paper.
Decision: Accept (Poster)