Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Most majority vote learning algorithms based on the PAC-Bayesian bound minimization focus on a first order bound. That is, the "factor two" oracle bound: the majority vote risk is lower than twice the (weighted) expected loss of its voters. The recent work of Masegosa et al. (2020) is a notable exception, and shows that great empirical accuracy and generalization bounds are obtained by taking into account the "tandem loss" (or "joint error," as coined by Lacasse et al. 2007). Their approach is surprisingly elegant and simple, using the sole fact that the majority vote risk is lower than four times the tandem loss. But there is a caveat, as the oracle bound of Masegosa et al. (2020) is less tight than the C-bound, that takes into account both the expected loss and the tandem loss thanks to the Chebyshev inequality. Until now, few learning algorithms have successfully optimized the PAC-Bayes C-bound, mainly because its fractional nature is prone to numerical instabilities and causes the associated PAC-Bayes generalization guarantees to degrade. In the current manuscript, the authors study the optimization of a parametric relaxation of the C-bound that does not contain the malign fractional term.
main_review: The paper is well written and presents interesting ideas for the PAC-Bayesian community that pursues the objective of providing principled learning algorithms outputting both accurate predictors and tight generalization guarantees.  

From a theoretical side, the first contribution (Theorems 7 and 12) is a nice incremental result based on Lacasse et al. (2007); Germain et al. (2015). However, the idea of minimizing a parametric relaxed version of the Cantelli-Chebyshev inequality to alleviate optimization problems does not turn out to provide improved empirical results, which weaken the importance of this first contribution. The theoretical novelty of the second contribution is (in my opinion)  the highlight of the paper. Indeed, Theorems 9 and 15 are obtained by an original analysis that introduce a new (translated) "\mu-tandem-loss," allowing combining the C-bound inequality and the PAC-Bayes-Bennett result of Tolstikhin and Seldin (2013). 


Unfortunately, the empirical results based on the minimization of the two new PAC-Bayesian theorems do not turn out to be really successful learning algorithms. The results seem to further confirm the surprising effectiveness of the algorithm proposed by Masegosa et al. (2020), especially in terms of bound values.  Considering this, the current manuscript would be more useful to the PAC-Bayesian community if it were providing a detailed analysis of the results, in order to draw conclusions that can foster future research. Here are some unanswered questions:
- Why is the first order oracle bound often the best? 
- Can we identify some regime where the proposed algorithms would perform better? (maybe with weaker voters)
- What are the observed values of the proposed C-bound, the expected loss, the tandem loss, and the selected value of \mu? 
- What are the values of the original C-bound (Lacasse et al.) for the observed results? (For binary classification, the PAC-Bayes bound value could possibly be improved by bounding simultaneously the expected loss and the tandem loss.) 
- Should we conclude that the C-bound is not the good oracle inequality to minimize, or should we work harder to find tighter PAC-Bayesian inequalities? 

It is also noticeable that the work is heavily based on the PAC-Bayes bound minimization techniques of Thieman et al. (2017). An interesting alternative would be to directly minimize the kl-bound. Although this has been considered as a difficult task, some recent works present simple strategies based on gradient descent (see Reeb et al. 2018, Letarte et al. 2019) 


Other comments:
- When it comes to learning algorithms based on the PAC-Bayesian C-bound optimization, the authors should also mention the recent papers of Bauvin et al. (2020) and Viallard et al. (2021)
- It is worth mentioning than the term "C-bound" have been used by the PAC-Bayes community since Lacasse et al. (2007) for the use of the (one-sided) Chebyshev inequality for majority vote learning, this has been discussed previously in the seminal paper of Breiman (2001) on Random Forests.
- In Theorem 12, I doubt that it is necessary to use the union bound and a parameter grid for the \mu value, as the expected loss bounds don't rely on \mu, and Theorems 7 and 11 are uniformly valid for all values of \mu and \rho. 


References
- Bauvin et al. Fast greedy C-bound minimization with guarantees. Machine Learning 2020
- Letarte et al. Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks. NeurIPS 2019
- Reeb et al.  Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds. NeurIPS 2018
- Viallard et al. Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a
Tight PAC-Bayesian C-Bound. ECML/PKDD 2021

limitations_and_societal_impact: The authors did not mention any societal impact in their paper.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies multiclass classification, one of the most elementary supervised PAC learning problems.
The main contribution is a new generalization bound for the weighted majority (with weights $\rho$) which simultaneously:
(1) leverages the fact that variance / centered 2nd moment of $\rho$ can be much less than the non-central 2nd moment
(2) gives a bound which can be readily estimated from samples
main_review: This paper studies multiclass classification, one of the most elementary supervised PAC learning problems.
The learner receives labeled examples $(X_i,y_i)$ drawn from some distribution $D$, where $y$ takes discrete values.
The goal is to correctly predict the label $y$ of a freshly drawn sample $X$, according to the $0-1$ loss.

One of the basic techniques in supervised learning is to combine multiple hypotheses (i.e. classification rules) into a single one, ideally with higher accuracy than the hypotheses one started with.
The most basic way to do this is with a (weighted) majority vote.

This paper studies generalization bounds for weighted majority classifiers.
The main contribution is a new generalization bound for the weighted majority (with weights $\rho$) which simultaneously:

(1) leverages the fact that variance / centered 2nd moment of $\rho$ can be much less than the non-central 2nd moment
(2) gives a bound which can be readily estimated from samples

Prior works giving generalization bounds for weighted-majority classifiers either give bounds with so-called "oracle" quantities in the denominator (meaning optimize with respect to $\rho$ and/or to estimate from samples), or don't exploit the advantages of the variance over the raw 2nd moment.

I am not very familiar with this area of learning theory, so my evaluation has very low confidence.
However, it seems to me that this might be a technical follow-up to the paper Masegosa et al. 2020, which is heavily cited by the authors.
It is not clear to me if it will be of sufficiently broad interest for the NeurIPS audience.
At very least, the writing does not really make clear enough to me, a reasonable proxy for the average theory-literate NeurIPS audience member, why the results are very exciting.
Theorems 6, 7, and 8 seem to be slight modifications of existing bounds, while the later bounds in the paper (especially in section 5) are quite complex and difficult to absorb.

That said, the paper seems to make progress on a very basic setting, and they do provide some nice experimental results.
limitations_and_societal_impact: This is a theory paper with limited direct societal impact.
Treatment of the limitations of the theory results is, however, somewhat slim.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a Chebyshev-Cantelli oracle bound for the true error of a majority vote classifier, whose empirical PAC-Bayesian generalization bound is more amenable to optimization than the C-Bounds.
The obtained second-order bounds are based on the \mu-tandem loss (the joint error with a \mu margin/offset) and do not involve statistical quantities in the denominator which make the minimization of the classical PAC-Bayesian C-bounds unstable and loose. 

By rewriting the oracle bound into two forms, the paper further proposes two different empirical bounds: one involves the variance of the \mu-tandem loss and leverages an improved PAC-Bayesian-Bernstein inequality that is also derived in the paper (I haven't checked its derivation); the other involves the second and first moments of the error. 
In practice, the empirical bounds are optimized by relaxing them via Thiemann's PAC-Bayes-\lambda inequality.
An empirical comparison with the first order and [Masegosa]'s second order bounds is provided on several real datasets, using as set of base classifiers either a random forest or a set of heterogeneous classifiers (e.g. k-nn, decision tree).
main_review: a. The paper is well written and overall easy to follow. All assumptions are well stated and proofs of the main theorems are provided. 
The contributions and scope of the paper are clearly provided in the abstract and introduction.

b. An unclear point of the work is its novelty w.r.t. margin-based oracle bounds. As clearly stated, this work builds upon [Masegosa] as it proposes a relaxed form of the tandem loss (or joint error, the parabole upper bounding the 0-1 loss). An additional parameter \mu is included, which is the margin/offset of the loss that recenters the parabole in \mu (instead of 0) and adapts its slope, and for which a theoretical optimal value exists. However, the literature on margin/offset losses, such as the work in [Laviolette], is never discussed in the paper, which makes it hard to judge the novelty of the contributions.

c. The empirical evaluation shows no significant difference between [Masegosa]'s test error and the test errors obtained by the two bounds proposed in the paper (see Tables in the appendix and Minors 1 in the review) and in most datasets the generalization bounds degrade (Figure 1 of appendix). Moreover they don't allow to obtain guarantees that are better than the ones obtained through the first order bound (Table E3, E5). 
In this sense, the paper provides little insight into why the empirical results do not improve at least upon [Masegosa]'s ones.
It could be a problem of having to deal with too many hyper-parameters (\mu, \lambda, \gamma) when optimizing the PAC-Bayesian bounds (see Minor 2 for a suggestion of alternative optimization) or also a problem due to the choice of base classifiers.
Indeed, Figure 1 (on the theoretical improvement of the bound with varying \mu) is very interesting, and it suggests that the most improvement should be achieved when errors made by the base classifiers are decorrelated. 
Hence, it would be interesting to study the obtained performance with varying degree of correlation between classifier predictions. 
For instance, following [Lorenzen], one could study the tightness of the bounds as a function of the strengths of the voters, e.g. training decision trees with bounded maximal depth. For weaker classifiers, one would expect to obtain better guarantees with the proposed bounds than with the first order and [Masegosa]'s ones.

## Minors
1. In the tables, standard deviations are reported but are not used to determine the significance of the differences between performance. The best results should not be determined only based on the averages. In the same line, using a log scale in Figure 2 makes it hard to compare the scale of improvement vs degradation, as the former is magnified.

2. A limitation of the work is its dependence on several parameters (\mu, \lambda, \gamma) for the optimization of its empirical bounds, which makes the algorithm heavy and the bounds looser. A suggestion for improving on this point would be to optimize the empirical bound of Theorem 10 directly, by evaluating the kl inverse via the bisection method as done in [Reeb].

3. The paragraph in lines 173-181, about the comparison of the bound of Theorem 9 with the bound of [Seldin 2012], is confusing. Isn't simply (e-2) \gamma tighter than \frac{\phi(\gamma bi)}{\gamma b^2}  for \gamma > 1/b and loser otherwise? Also, it should be explained why Seldin's result is applicable only to upper bounded losses and for gamma < 1/b.

## Recommendation
I recommend a revision of the paper. I am willing to increase my score if novelty w.r.t. works on margin losses is clarified and more insightful empirical analyses are provided into the reasons why the derived bounds do not improve upon state-of-the-art second order bounds, even though the oracle bound is tighter.

### References
[Laviolette], et al: Risk upper bounds for general ensemble methods with an application to multiclass classification, Neurocomputing 2017

[Lorenzen], et al:  On PAC-Bayesian bounds for random forests, Machine Learning 2019

[Masegosa], et al: Second order PAC-Bayesian bounds for the weighted majority vote, NeurIPS 2020

[Reeb], et al: Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds, NeurIPS 2018

### UPDATE
Having read the other reviews and rebuttal, I confirm my initial rating. I find the paper well written and its theoretical contributions interesting, but incremental. I think that a stronger empirical analysis would be required for acceptance. I agree with reviewers Mc3o and ZLiP that the paper does not provide really new insights into the differences between optimizing first order or second order bounds, nor into why the proposed bound does not improve upon state-of-the-art results. I believe that the empirical analysis should study in particular settings where base classifiers are weak and have low correlation, at the very least on toy datasets, and that the statistics of Figure 1 for the settings already studied should be reported. This would allow to check whether the lack of improvement is due to the looseness introduced by going from the oracle to the empirical bounds and if there are concrete settings where the proposed bounds would be useful.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Viewed at a high level, this paper is interested in majority-vote classifiers for binary classification tasks. The authors present both oracle and empirical risk bounds for such classifiers. In particular, since the empirical risk bounds are derived using (empirical) PAC-Bayes inequalities, one obtains high-probability bounds that hold uniformly over the choice of the weighting distribution (or "posterior") $\rho$, meaning that the bounds can in principle be used as objective functions to be minimized with respect to the candidate weighting scheme.

As I understand it, the main "take-aways" from this work are the empirical PAC-Bayes bounds on the risk of MV under $\rho$, namely Theorems 12 and 15, plus the empirical insights into their tightness and utility as objective functions.

If my understanding it correct, the main new idea here is to use a looser Chebyshev inequality (with shift parameter $\mu$ not restricted to its optimal value) in order to get inequalities that have simpler dependence on $\rho$. This basic idea is summarized in their Theorem 6, from which Theorems 7 and 8 directly follow. Theorems 12 and 15 respectively are based on Theorems 7 and 8, with the key difference being that the former uses the "tandem loss" used in the cited literature, whereas the latter uses the "$\mu$-tandem loss." The authors introduce a PAC-Bayes-Bennett inequality which refines the well-known PAC-Bayes-Bernstein inequality of Seldin et al., and the role of this inequality in their story is to handle their $\mu$-tandem loss.
main_review: The paper is written clearly, and it takes the reader step-by-step through the chain of inequalities used to obtain their Theorems 12 and 15. As such, the paper is somewhat "mechanical" in nature; the various bits and pieces involved in their formal arguments are presented clearly, but it is questionable whether any new real insights have been obtained. While some readers may benefit from the idea of leaving $\mu$ unspecified to obtain a simpler function of $\rho$, we pay the price in terms of looser bounds and an extra parameter to set, though I felt this issue was swept under the rug by introducing the grid $\{\mu_1,\ldots,\mu_k\}$ out of nowhere (same goes for Theorem 15).

I also felt the authors could have done a better job of linking the empirical section to the theory; the terms C$\mu$TND and COTND appear for the first time in section 6, and the naming seems wrong; why is Theorem 12's bound called the $\mu$-tandem bound, despite the fact that it is Theorem 15 in which the $\mu$-tandem risk appears? The empirical tests seem to be well-done, though the evidence in favor of the new bounds is not particularly strong.

Taking these points together, I believe the paper is well-written and has clear contributions, but the significance of these contributions, and the resulting insights available to the reader are rather limited.

**Update:** I thank the authors for their response, which provided some additional context for their work. Having read the other reviews and the reviewer discussion, I am not opposed to the paper appearing at the conference, but I still remain borderline on this one. 
limitations_and_societal_impact: Please see the main review above.
review_title: null

Meta-review: While some reviewers pointed to merits of the submission, the contributions appear too incremental to deserve a publication at NeurIPS: reviewers expressed concerns about the significance of the results, comparison with earlier works, and the numerical validation of the proposed scheme, which is not deemed conclusive. I would invite the authors to carefully revise their manuscript in accordance with the reviews.
Decision: Accept (Poster)