Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies Follow the Regularised Leader algorithms for the Hedge settings.

The paper starts with an overview of FTRL in adversarial settings. A frighteningly general setup is described and Theorem 1 for the adversarial regret is obtained. It is claimed that the theorem allows one to obtain bounds similar to some known bounds from the literature.

Then the semi-adversarial settings are discussed (the definition of semi-adversarial covers the adversarial settings on one end of the spectrum and purely stochastic on another).

The paper presents FTRL-CARL and obtains a performance bound on it in terms of effective stochastic gaps.

Then the paper discusses bounds in terms of f-divergence and obtains a lower bound matching upper bounds.
main_review: The paper is not very kind to the reader and the presentation is often very formal. For example, I understand the most important results were obtained for the case of finitely many experts. Was it really necessary to introduce the general framework with Radon-Nikodym derivatives?

It is hard for me to appreciate the importance of CARL bounds as the concept of effective stochastic gaps is not clear to me. Why are they important and how do they characterise the distribution class? 

The matching lower bound is something I can understand and appreciate and find very important.

Finally, I can't help thinking that discussing semi-stochastic settings and f-divergence bounds in one paper is somewhat artificial.
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 prediction with expert advice,
and focuses on quantile regret bounds that depend on the comparator distribution
and semi-adversarial paradigm,
which is an intermediate setting between stochastic one and adversarial one.
In the paper,
minimax optimal regret bounds for both paradigms are shown.
This bound is achieved by follow-the-regularized-leader (FTRL) algorithm with a newly designed root-logarithmic regularizers.
main_review: Originality: 

The originality of the contributions in the semi-adversarial paradigm seems somewhat limited.
The method of analysis appears to be almost the same as that in this literature [BNR20],
in which the semi-adversarial paradigm has been introduced.
In addition, the semi-adversarial setting with $N_0 = 1$ has already been treated in [GSv14] (as Assumption 1 in [GSv14] holds), and it has already been proved that an upper bound of $O(\log N / \Delta_0)$ can be achieved in this case.
We would like to note that the semi-adversarial setting is also a special case of adversarial regimes with a self-bounding constraint in [ZS21].

Quality:

As far as I can see, no technical errors have been found.
I think the authors are careful and honest about evaluating both the strengths and weaknesses of their work.

Clarity:

The technical part is clearly described.
However,
the comparison with existing studies is not very clear.
In particular,
I did not know if the proposed algorithm was more effective than the standard Hedge algorithm (in [MG19]) and algorithms with second-order regret bounds (in [GSv14], [CMS07])
in semi-adversarial paradigm.

Significance:

The theoretical results on quantile regrets will have a certain impact.
In particular, as far as I know, this is the first time that a lower bound for for quantile regret on finite expert classes has been given.
Compared to this, the impact of the results on semi-adversarial setting seem to be somewhat limited, for the reasons mentioned above.



[ZS21]: Zimmert, J., & Seldin, Y. (2021). Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits. J. Mach. Learn. Res., 22, 28-1.
limitations_and_societal_impact: I think limitations and societal impact have been well discussed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors tackle the problem of obtaining low semi-adversarial and quantile regret for the problem of prediction with expert advice with possibly uncountably many experts. To this end they develop a general technique to obtain methods for the problem based on the (measure-theoretical) FTRL meta-algorithm. They show that appropriate choices of regularizers can yield algorithms for the semi-adversarial (with improved dependency on the number of experts) and quantile settings (asymptotically matching state of the art). Finally, they give a lower-bound on the quantile regret, showing that their results are minimax optimal.
main_review: # Strengths

- The technique used (FTRL with uncountably many experts and a clever general technique to pick regularizers) is elegant, general, and effective;
- The lower-bound for the quantile setting, although not very well advertised, is a solid contribution to the field;

# Weakenesses

- The presentation of the paper is not optimal: it is at times hard to follow, some technical statements do not give much information to the reader, and the lack of examples (or at least their bad distribution through the paper) makes it hard to properly interpret some results.
- The measure theoretical generality is interesting, but the paper lacks a discussion of why such generality is actually worth the effort;
- The theoretical improvements on the regret seem marginal (although the experiments show that the improvements can be substantial even for a small number of experts). This by itself is not a serious weakness (incremental research can still be good and is important), but the lack of discussion on the interpretation of the result makes this weigh negatively in the paper. They seem to claim sometimes that their semi-adversarial regret bounds (Thm 2) are minimax optimal, but it is not clear if it is true;
- There is a "hidden" section: there are experiments in the appendix, but they are never mentioned in the main paper. And the big difference between the FTRL-CARL and previous algorithms is poorly discussed;

# Summary of the decision

 To fix some of the weaknesses the authors need to change a lot on the paper. Although I believe there are interesting contributions in the paper, it would deserve another round of reviews after the proposed changes, so I don't think it can be fixed for the camera-ready deadline. Of course, this decision is not necessarily final and can be changed based on the authors' response.

# Detailed discussion

I really enjoyed the techniques used, but I had a hard time going through the paper. The two main aspects that make the paper hard to read are the lack of well-placed examples and the lack of discussions of the results. For example, on section 2 it would have been great to see that we can get the Shannon entropy in eq. (1) (this is done only by the end of the paper). Also, the paper has almost no examples that exploit the measure-theoretical generality, so it is not clear why the authors go through this route. Even if the reason is purely theoretical novelty and generality, I feel this should have been better discussed.

One section that was poorly discussed was section 3, which apparently should be one of the main sections of the paper. Lemma 1 and Theorem 1 are hardly interpretable and the authors do not have any discussion trying to interpret these statements. For example, it is not clear how hard the iterate given by Lemma 1 is to compute! (The authors do claim that is a "simple task of finding the root of a 1-dimensional equation", but in the *last* section of the paper finally say it is hard to compute it. It then makes the reader wonder how useful these techniques really are. I still think these are very valuable, even if sometimes only theoretically, but the lack of up-front discussion makes the results very confusing, and leaving mention of hardness only to the end is fishy).   As another example, it is really hard to interpret the second summation in Theorem 1 and the authors do not try to explain when the summation can be reasonably bounded. In fact, nowhere in the main body of paper the authors actually use Theorem 1 (and hardly use Lemma 1), so these could have been easily deferred to the appendix, leaving more space for discussion.

For the semi-adversarial regret bounds on section 4.1, the case $T > T_0$ could have been deferred to the appendix (it could have been at least stated in a simplified way probably). It takes a lot of valuable space and there is little to no information we can obtain from it. Certainly seeing how the derivation of simpler bounds such as the one on Pg. 5 or on remark 1 follow from these general bound would help, but as it is it just takes valuable space from the authors. As an example of what could have been discussed, the regret bound for $T \leq T_0$ has no dependence on $\Delta_0$ or the additional $\log N$ term. Could this explain the excellent performance seen in the experiments? Also, it is not totally clear when $T_0$ is big or small, making it harder to understand when the first tighter bound holds. Also, although the authors do discuss some of the intuition behind $h_C$, it would have been great to know that it is a by-product of Lemma 1 from the start.

For root KL and quantile regret bounds, it is again hard to interpret the results. Corollary 2 is the main regret bounds but it is really hard to know what are some reasonable choices of $f$ so that constants $k_1$ and $k_2$ exist. A formal statement of the $\epsilon$-regret bounds the authors can get from Corollary 2 would have been extremely helpful. The lower-bound is a solid and good contribution, but it is hard for the reader to see if Corollary 2 indeed yields minimax optimal $\epsilon$-regret. Maybe this is exactly the point of Example 3, but the authors do not make it clear.

In fact, the examples from section 4.2.3 would have been extremely helpful earlier in the paper (even with the instantiations of the regret bounds deferred to the end). I strongly suggest bringing some of these examples earlier in the paper. Even in the examples some parts are not well explained (on example 2 it is not clear when/if $k_{t+1}^*$ is efficiently computable, and in fact it seems it can be relatively hard to compute). 

Finally, the experiments section is hidden and I found it out almost by accident. Even being in the appendix (and thus, not bounded by space), this sections still lacks discussion of the results. It is not clear why the difference of FTRL-CARL is so big if compared to META-CARE. Like I mentioned, it might be because of the case $T \leq T_0$ or even better constants, but the authors do not discuss these aspects.

# Comments Post Rebuttal

The authors provided concrete changes (with thorough discussion) that will improve the presentation. Furthermore, they showed I had misunderstood the contribution of one of the results, and the committee discussion helped me better appreciate the results, so I'm increasing my score to 7.

I still think the papers deserves and needs a better presentation, even more so for NeurIPS' wide audience. I again encourage the authors to apply the proposed changes and use the extra space to aid in the papers readability and to help the reader understand each of the results (some results are hard to parse for an outsider like me).

And thanks a lot for the authors for the very solid and thorough rebuttals! 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the classic expert problem and focuses on developing 
parameter-free algorithms with two specific guarantees: 1) better regret 
bounds for the semi-adversarial paradigm proposed by Bilodeau et al. 20; 
2) a KL-type regret bound similar to that achieved by NormalHedge 
(Chaudhuri et al. 09) and other variants, possibly for an uncountable 
set of experts. The authors achieve these two goals using the standard 
FTRL framework with two new root-logarithmic regularizers, inspired by 
their general analysis that requires some specific properties of the 
regularizer. A matching lower bound for the KL-type regret is also 
provided. 
main_review: Overall this paper makes solid contributions to a fundamental problem, 
and I support acceptance. What I particularly like is achieving the 
KL-type regret with an FTRL approach, different from all existing 
algorithms (NormalHedge, AdaNormalHege, Squint, Coin-betting, etc.). I 
believe at least several researchers have tried to do so but failed. 

However, I do have some concerns and questions:

1) In the semi-adversarial case, what happens when \Delta_0 is very tiny 
(or \Delta_i is simply 0 for every i)? Does FTRL-CARL insure some 
"safety" guarantee (ideally \sqrt{T\ln N}) always, besides the guarantee 
stated in Thm 2? 

2) Although achieving KL-type regret with yet another algorithm is nice, 
the guarantee in Corollary 2 is in fact strictly worse than that of 
AdaNormalHedge (Luo and Schapire 15) and Squint (Koolen and van Erven 
15), in the sense that the latter not only achieve the KL bound, but 
also some data-dependent bounds which have some nice implications. In 
fact, one implication is exactly an logarithmic bound for the stochastic 
setting or more generally logarithmic bound plus \sqrt{C} regret for a 
corrupted stochastic setting with C being the amount of corruption (this 
last result is not stated formally in these papers but the derivation is 
straightforward; one can see some examples in the bandit setting such as 
[1]). In fact, I personally think the corrupted setting is more natural 
than the semi-adversarial setting considered in this work as an 
intermediate setting between the stochastic case and the adversarial 
case. From this perspective, AdaNormalHedge and Squint appear to be much 
more appealing. In fact, there are also recent improvements over these 
works as well, such as [2]. 


On writing:
The paper is generally well-written, but I have some comments below.

1) While I appreciate presenting the result in the most general form 
using measure theory language, this also makes the results hard to 
interpret in most places. I would prefer presenting the finite case in 
the main text and deferring the general case to the appendix. The 
semi-adversarial results also seem to be specific to the finite case 
anyway? (BTW if this is true it should be mentioned at the beginning of 
Sec 4.1.) 

2) More explanations after some of the theorems/lemmas (such as Thm 1) 
would be very helpful.

3) I wonder whether the proposed algorithms are really that similar to 
NormalHedge (which the author claim). Looking at their update rules, I 
would only say that they are somewhat connected (maybe I am just not 
seeing the deeper connections).


[1] Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm 
for stochastic and adversarial bandits. JMLR 2021.

[2] Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Impossible Tuning Made 
Possible: A New Expert Algorithm and Its Applications. COLT 2021.
limitations_and_societal_impact: N/A. This is mostly a theoretical work.
review_title: null

Meta-review: The reviewers unanimously support acceptance of the paper. The writing of the paper requires improvement and I hope that the authors will implement changes promised to the reviewers.
Decision: Accept (Poster)