Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work investigates the best-case lower bounds in the online learning setting -- meaning a lower bound on the regret value of an algorithm. Even though an algorithm is usually concerned with minimizing the regret and thus upper bounds on regret are used to describe algorithm performance, information about lower bounds on the regret can also provide information about the algorithm performance, its adaptivity, and in some cases certain notions of fairness. In this submission, the authors consider the FTRL family of algorithms, anytime (no prior knowledge of $T$) and timeless (first-order bounds), with constant, time-varying or adaptive learning rates. The results mainly show that the magnitude of regret of such algorithms stays within the range of the upper bound (or is nonnegative sometimes) with some exceptions. An application to online learning with group fairness is provided as a use case for such bounds.
main_review: This work concerns itself with algorithm-specific regret lower bound in online learning, i.e. characterizing not only how low the regret of an algorithm is guaranteed to be but completing the range of it. It is true that the upper bounds are the important part of an algorithm's guarantee, they indicate how well the algorithm is sure to perform. These best-case lower bounds simply provide more information in regards to the algorithm's adaptivity -- a truly adaptive algorithm should be able to attain $-T$ regret for certain sequences. On the other hand, these results can be used in devising "fair" online algorithms, e.g. ones with group fairness as in this submission, in which case negative linear regret is not desirable at all (informally, one is aiming to balance mistakes out uniformly). Overall, this is work that can have sufficient significance in completing the community's knowledge about the online algorithms such as FTRL types that are used ubiquitously.

The paper is written clearly, is easy to follow, and the results are presented in an honest and straightforward fashion. The main criticism in my opinion can be its significance, but I believe such work can encourage more results in this direction and resolve most such questions in several years. Applications other than fairness might be born along the way too. I believe this submission is ready for publication and simply have some questions to the authors.

As shown, FTRL type algorithms can have $\geq 0$, $-\sqrt{T}$ and even $-T$ (linearized) regret while all have $\sqrt{T}$ regret upper bound. What is the end goal in characterizing such results then? Is the idea to exhaust all the algorithms that are around just to have the best-case lower bound results? Are there notions about what is desired? 

Seems like general minimax bounds can't be shown since $-T$ is achievable, so what can be said in a general manner that doesn't depend on a specific algorithm? And these results still don't rule out the possibility of an unknown algorithm having desired upper bound *and* lower bound properties, so pessimistically seems like there is nothing substantial to say in here.

The authors emphasize that their analysis applies to anytime algorithms: just a question, if you have analysis for known horizon algs, then can't you similarly analyze such the algorithm of alg + doubling trick which is anytime.


limitations_and_societal_impact: Societal impact was adequately addressed. Limitations of the work and possible future directions also discussed in a sufficient manner.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper establishes lower bounds on the best-case regret of the classical FTRL algorithm in online convex optimization. Specifically, the FTRL algorithm is considered in the general form where the regularizer can change over time (e.g., due to a time-varying learning rate). In the case of a fixed regularizer, it is known from earlier work that the regret is always non-negative, i.e., the algorithm never performs better than the best static expert. For time-varying regularizers, this is no longer the case, meaning that the best-case regret can be negative. The paper proves a simple generic lower bound theorem and applies it to several standard settings (Decreasing Hedge; a standard timeless method for decision-theoretic online learning (DTOL); an adaptive gradient version of FTRL), where it is found that the best-case lower bounds are roughly symmetrical to the known worst-case upper bounds on the regret (i.e., if A is a worst-case upper bound, then -O(A) is a best-case lower bound). In other words, these algorithms cannot outperform the best static expert by much, for any input. For DTOL with 2 experts, they show their lower bound to be tight.

For a different setting of the linearized FTRL algorithm, they show that an analogue result does not hold: Although the known regret upper bound is O(sqrt(T)), the best-case regret can be as low as -Omega(T).

An application and the original motivation for the work is in the setting of "group fairness" for DTOL: Here, time steps are partitioned into groups, and the algorithm knows which group the current time step belongs to. It is assumed that for each expert, the average loss per time step is balanced across the groups. Then recent work of Blum et al shows that the learning algorithm also has comparable loss in each group. This assumes that the time horizon T is known. This paper allows extending this result to an unknown time horizon, and shows an "anytime" extension of the result: If the assumption is strengthened so that for each expert, the losses are balanced across the groups not only after the last time step but also on every prefix of the input, then the learning algorithm also has balanced losses per group at all timesteps.
main_review: The results seem to be an interesting generalization of previous work by allowing time-varying regularizers. In particular, they show limitations on outperforming the best static expert in several standard settings (as would be necessary in a "shifting regret" settings) and the extension of previous group fairness results seem relevant. However, someone more familiar with the related work might be a better judge of the overall significance then me.

The paper is well-written and ideas easy to understand.

Minor comments:
- On pages 3-4, there are at least superscripts of w that should be subscripts.
- line 175: factor 2 is missing eta_t
- In the math after line 206 and after 209, it seems the terms on the LHS should be divided by the number of time steps in the group.
- line 365: "me" -> "be"
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the best-case lower bound, which characterizes the minimum regret that a specific algorithm can achieve in the most benign environments. The authors provide the best-case lower bound for the general FTRL algorithm and show that the bound can be applied for many instances, including Hedge with non-increasing step size, adaptive gradient FTRL. The best-case lower bound for the Hedge algorithm can be used to prove the group fairness in the prediction with expert advice setting. Case studies on the linearized FTRL and Hedge with two experts are also provided.
main_review: This paper provides a notion of best-case lower bound and analysis for the adaptive FTRL algorithm. The best-case bound is novel to me, and the analysis is simple yet general to be applied for many specific cases. In Section 3, the authors further show that the analysis can be applied to Hedge with time-varying step sizes, which can finally lead to group fairness in prediction with expert advice setting without knowing the time horizon in advance.

Although the analysis best-case lower bound can be used to ensure the group fairness for Interleaved Hedge algorithm, I still quite catch the significance of this study in a more general OCO setting. It seems that the best-case bound is neither a good measure for the performance of algorithms nor reflects the hardness of the problem. I think it would be nice for the author to illustrate more the significance of the study in a more general case.  For example, what would imply if we could obtain a best-case lower bound for adaptive gradient FTRL (Section 4.2)?  

Besides, I am confused by the title of Section 5. Why the $-\\Omega(T)$ best-case lower bound of linear FTRL is called "negative result." Low regret seems good news for the OCO problem. Perhaps, the result is negative for achieving group fairness. But, the case study in Section 5 is presented in the OCO setting, and there is no concern about fairness. The confusion might be related to the main concern of the significance of the best-case lower bound in the OCO setting,

Overall, although the paper shows that the proposed best-case lower bound can be used to achieve group fairness of Hedge, its significance in the OCO setting is unclear. It would be better if the authors can illustrate more about some more applications of the best-case lower bound.

=====update=====

Thank you for the response. After reading other reviews and the author's feedback, my concerns are largely addressed. I would like to raise my score to a positive evaluation (7).

My original concern is that the motivation for studying the best-case lower bound in general OCO problem is unclear. By point (1),(2) of the first answer, the authors show that the best-case lower bound can be used to achieve group fairness beyond the expert advice setting. Although group fairness is an important notion, the extension could be limited to a narrow scope of audience. This concern is somewhat addressed by the third point, where authors have shown that the best-case lower bound can be used to show some negative side of the adaptive algorithms. For example, the adaptive FTRL does not perform that well in extraordinarily benign environments (it seems that the adaptive FTRL even is even inferior to the linearized FTRL in such a case). So, I am convinced that the best-lower bound can indeed provide a unique view to understand the adaptivity of the online learning algorithms.

Regarding the second question, I think the confusion might come from a lack of further discussion about the best-case lower bound. For the fairness problem, the less negative regret bound means better results. But, that is not the case for regret minimization. So, I think it would be better to provide a more clear discussion about the signification of the best-case lower bound for both scenarios (especially for the regret minimziation part).
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Inspired by applications of fair online learning, the authors initiate the study of *lower bounds* on the regret of OCO algorithms. They provide a general lower bound for FTRL algorithms and show the implications for fixed regularizers and for some special kinds of time-varying regularizers (such as fixed regularizers with time-varying learning rates or regularizers dependent on the past losses). They also provide regret lower bounds on AdaGrad-like algorithms derived from the FTRL framework, and show how linearizing the losses can yield to algorithms with potentially $-\Omega(T)$ regret in $T$ rounds. They also explicitly build the best-case losses for the experts problem with 2 experts, giving sharp bounds for this special case;

Their main application is to fairness for decision theoretic online learning (experts' problem), strengthening previous fairness bounds. They show a way to get fairness guarantees without needing to know the size of the groups, and extending the fairness notion in online learning in a way that is independent of the length of the game.
main_review: # Strengths
- A solid theoretical paper, with a novel perspective on online optimization/learning and initiating a possibly fruitful direction of research;
- A solid contribution to fairness for DTOL, analyzing a natural fair algorithm that does not need to know the size of the groups ahead of time, and a good discussion on how the current notion of fairness from previous work is highly dependent on the time horizon;
- Very good characterization of the connection between fairness and lower-bounds on the regret;
- An example of an algorithm with a sublinear regret upper bound but with a linear regret lower bound, leaving open interesting questions about the characterization of algorithms that suffer from linear best-case lower-bounds. 

# Weaknesses
- Implicit assumption on boundedness of the feasible set in the more general analysis of FTRL and some hidden assumptions on the regularizers that are not mentioned anywhere (and can even render the results false), details later;
- A lack of motivation (very interesting theoretically, but the broad NeurIPS audience might have a hard time understanding the motivation of the work);
- Regret bounds for the AdaGrad-like algorithms have an (apparently) extra dependence on a bound on the gradients that is not present in the original AdaGrad algorithm;
- The result for 2 experts, although exact, seems to lack a bit of discussion/motivation;

# Summary of the decision

A solid theoretical contribution with strong connections to fairness. So I consider it to be a good paper (7), although not higher since the motivation and applications, although interesting, are still narrow. I still expect comments of the authors on some of my points (mainly (3)) to maintain my score, but I believe none of these are serious problems.

# Detailed discussion

1) I really believe this paper is a solid theoretical contribution and initiates a direction of research that, beyond the clear applications to fairness already discussed, can have connections to stability of online learning algorithms and give some intuition on algorithms that can perform "extraordinarily" well in practice. Of course, it is not a completely new field, but it is an interesting perspective. However, I think the authors should make an extra-effort to sell this theoretical work to a broader community. NeurIPS has a vast audience, and having a better discussion of why studying these best-case lower-bounds is interesting. Even the gist of the discussion on fairness is deferred to the appendix. Bringing some of that discussion to the main body might already give a broader and strong motivation for the work. I really enjoyed the discussion from the appendix.

2) On Section 3 the authors state that $\mathcal{W}$ is a closed set, but do not mention necessarily that it is bounded. However, in the definition of regret itself the supremum may easily be infinite if $\mathcal{W}$ is the whole space. On Theorem 1 something similar happens, where the authors assume that there is a optimal action in hindsight, which might not be true (again, take the feasible set as being the whole space). A more fine-grained analysis shows that the regret against some comparison point is dependent on the regularizer at this comparison point, so boundedness is not necessary for (at least some) results to follow. Since all the application in the paper only look at cases where the the feasible region is bounded, this is not a serious problem, but clearly stating these assumptions would be good. 

3) Another problem is that Theorem 1 requires the regularizers to be non-negative (not mentioned) and strongly convex (mentioned, but only inside the theorem, so it is not clear that the regularizers in the paper are assumed to be strongly convex throughout). These conditions **should** be explicitly stated and enforced, or at least the the statement of the FTRL regret bound should be adapted (subtracting the infimum of the last regularizer in the right hand side might be enough, but I haven't checked carefully). These assumptions on the regularizers and/or boundedness of $\mathcal{W}$ would help a lot in making the analysis in Section 2 less bumpy (without boundedness or strong-covexity, taking the infimum of the regularizer over the feasible set can lead to $-\infty$). In fact, if I'm not mistaken the authors themselves stumble onto these problems: on line 172 the authors *EXPLICITLY* use that the regularizer is non-positve on the entire feasible set. Applying this same regularizer to Theorem 1 we would have that the sup is also non-positive and we could get a logarithmic regret upper bound, and this is clearly false. Thus, this can make the readers very confused about which are the conditions required on the regularizers at each step for the results to hold. My suggestion is to adapt Theorem 1 for the case where the regularizers may be negative, but still strongly convex (and, thus, lower-bounded). But above all else, **make the assumptions on the regularizers clear**. (Another lesser point, the iterate from (1) might not be unique if the regularizers are not strictly convex).

4) On Sec 4.2 the authors should be a bit more explicit about the difference between AdaGrad and your algorithm (linear approx vs whole function). But something that is bugging me that I did not have the time to verify carefully is the dependence on bounds of the p-norms of the gradient in the regret bounds. I believe this FTRL-AdaGrad algorithm should get similar bounds to the original linearized version (in particular, if the functions are linear these algorithms match exactly). Although this is not the focus of the paper, this extra dependency is a bit unsettling, and I couldn't verify the proof since it is not provided in the appendix. So I suggest you to give the proof in the appendix, if time allows. But beyond that, I think a careful analysis (possibly using the strong FTRL Lemma from McMahan) should yield bounds without the extra dependency on the bounds of the gradients. I'd really love the thoughts of the authors on that.

5) The result on identifying exactly the best sequence for two experts is interesting, but I did not get much of the motivation for it. The discussion on why it shows that the previous result was tight is not clear (do you mean asymptotically only? Because the constants do not seem to match). But this part I might have simply misunderstood and is not a serious problem
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: Reviewers all liked the paper, which seems to provide an interesting new take on analysis of adaptive online learning.

Decision: Accept (Poster)