Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose an algorithm for learning a *stochastic* weighted majority vote classifier, by optimizing a (PAC-Bayesian) generalization bound. They consider Dirichlet distributions over classifiers as well as general measures, and derive analytical and numerical schemes, respectively, for optimizing both. They empirically evaluate the algorithm for several datasets and model classes (decision stumps and random forest). They also compare against deterministic weighted majority vote classifiers learned by optimizing Gibbs classifiers via existing PAC-Bayes bounds (first order, secord order, C-bounds, etc). The resulting stochastic predictor achieves competitive performance and bound tightness compared to ones obtained by minimizing alternative bounds.
main_review: In my opinion, the paper presents fairly incremental ideas, combining data-dependent priors, a few other existing tricks in PAC-Bayes, like splitting the datasets in half, etc. From the technical perspective, the authors work out a closed form for stochastic Dirichlet predictors. This is a nice contribution, but appears to be relatively straightforward. Since the non-Dirichlet approach is competitive, it is not clear to me how useful the derived analytical expressions are. As the authors report, the MC variant seems to be fast and accurate with a range of base predictors.

However, the empirical results are positive and the empirical evaluation is, I believe, novel. The clarity and quality are both good. Overall, I am leaning towards acceptance but would like to see authors’ responses to a few questions listed below (especially about the advantage of stochastic majority vote classifiers over non-stochastic counterparts).

What are SOTA algorithms for optimizing standard (deterministic) weighted majority vote classifiers? The comparisons here are all to PAC-Bayes bound optimization, but are these algorithms at all competitive? And how about the same question but with stochastic majority vote classifiers? I would like the authors to provide references and report their (test) performance in the same cases as tested in Figure 5. How do they compare in error? If these other algorithms do better, what is the advantage of adding stochasticity? How do PAC-Bayes bounds on error of stochastic majority vote compare to held-out set bounds for non-stochastic majority vote achieved by these alternative algorithms?

To what extent does the empirical evaluation replicate what has already been reported in previous papers (e.g., on first and second order bounds)? That is: is the empirical evaluation performed here to be considered a novel contribution?

When trained on the datasets used in Fig 5 (so not just the moon dataset), did you also observe that Dirichlet had high entropy/higher than for classifiers trained with alternative algorithms?

The authors also present a hypothesis why their algorithm’s performance (or tightness of the bound?) decreases (relative to other algorithms tested) under input noise (using 0-1 vs loss with margin information). While a theoretical analysis might be challenging, it would be nice to see some empirical evidence evaluating their hypothesis.

Also, what is the (approximate, perhaps) Bayes error for the noise levels used in Figure 12? What should we compare the performance against? 
limitations_and_societal_impact: The authors discuss the following limitations of the proposed algorithm: the algorithm seems to underperform under input noise; the obtained guarantees get looser with an increasing number of base predictors. These seem to be fair limitations.

The authors do not foresee any negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper gives a tighter bound on the generalization of majority voting classifier by using a form of stochastic majority vote classifier. Using minimization of this bound, they are able to get better accuracy for the classifier as well as tighter generalization guarantees.

main_review: The paper uses PAC Bayesian bounds on stochastic majority voting scheme to get tighter generalization bounds on its performance. The paper is interesting and they are able to achieve good results experimentally. But, my main concern is that the main contribution of the paper is to get tighter generalization bounds by using stochastic majority votes. However, it is not clear to me why the bound is tighter when going from the error of one classifier to the expected majority vote classifier. On line 240, this conversion still introduces a factor of 2. So, it is not clear why this bound is tighter. The statement made in the paragraph is vague and hard to understand.

Can the authors clarify the statement made in line 141 that second order and C-bounds fail to leverage the diversity in the whole set of classifiers?

The paper seems interesting to me. However, I feel that the paper is not well written and many claims are vague without proper explanation and thus, hard to understand. The writing of the paper can be improved.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a novel majority-vote learning algorithm for finite hypothesis classes based on minimizing a PAC-Bayes bound. The paper also reports experimental results that the theoretical generalization bound is close to the observed held-out error i.e., the generalization bound is tight, when the base hypothesis class is a collection of decision trees.
main_review: Originality. Existing PAC-Bayes learning algorithms are designed to a) find a probability distribution Q over base hypotheses H and b) define the final majority-vote classifier as the one outputting the average prediction under Q. For finite hypothesis classes H, the paper’s learning algorithm modifies a) by implicitly redefining the base hypothesis class to be H’, where each element h’ is a convex combination of all the elements of H (Equation 4). With this H’, the paper returns to the standard methodology, by searching for Q’ by minimizing a generalization bound (either Theorem 1 or Theorem 2), and derandomizing to return the final majority-vote classifier. Section 3.1 and Section 3.2 explain that the generalization bound as a function of the parameters defining the distribution Q’ is differentiable. Therefore, first-order methods such as gradient descent can be used to reach (at least) local minima. More importantly, since the bounds hold for arbitrary Q’, it is always possible to evaluate performance even if training is not perfect (reaching global optima).

Quality. The claims in the paper are well-supported by evidence. I have some questions if time permits/for future work. First, can we inspect how different the final majority vote classifier in Figure 5 for exact is from the baselines? I am puzzled by how the different methods have similar test errors, but the generalization bounds are so different. Since the majority votes are defined by the convex combination with respect to the base hypotheses, this should be simple visualization. Second, is there a concrete, synthetic situation that gives intuition why the paper’s approach of first implicitly defining H’ and then computing Q’ gives better bounds then the standard PAC-Bayes approach? As an analog, section 2.2 lists some ideas of why a second order bound is better than a first-order one (because of correlation among the base hypotheses). Is there something like that for StocMC? Third, what do the different components of the generalization bounds before the de-randomization stage look like? This is related to my first question. All the PAC-Bayes bounds balance a trade off between empirical fit (the Rhat term) with complexity (the KL term). Since the different methods in Figure 5 have similar test error, I am tempted to think that the difference in generalization bounds come from the complexity term. In any case it would be good to check!
 
Clarity. The paper is clear and well-written. One suggestion is putting the datasets where both the test error and the generalization bounds are too small (like sensorless, mushrooms) to the appendix. 

Significance. The consistent ability of the generalization bound to approximate the test error from above (Figure 5) is very encouraging evidence that this kind of majority-vote algorithm can explain how ensemble methods generalize on unseen data.
limitations_and_societal_impact: There is at least one other work also involving PAC-Bayes majority vote and decision trees that might be relevant to your work https://papers.nips.cc/paper/2018/hash/1819020b02e926785cf3be594d957696-Abstract.html. This paper aims to derive classifiers whose excess risk (risk of classifier minus Bayes risk) goes to zero if the hypothesis class is allowed to grow with the dataset size (like decision trees of increasing depth). The tightness here is a different sense than the tightness in your paper, however. 

On another note, are extensions to continuous hypotheses spaces possible? For instance, neural networks. These are the hypothesis classes where most of the interesting work in statistical learning is being done currently. 

The societal impact has been addressed well.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the generalization properties of the stochastic weighted majority vote (MV) classifiers, where the weight of the MV follows another distribution over MVs. The proposal allows a direct analysis of the risk of the stochastic MV instead of analyzing through other empirical quantities, which leads to tighter bounds. By taking the distribution over MVs to be Dirichlet distributions, the authors also provide an exact and an approximation method to optimize the parameters of the distribution.
main_review: Most of the previous results for weighted majority vote (MV) considered the performance of a deterministic MV. To the best of my knowledge, this is the first investigation of stochastic MVs. The idea might open a new path to investigate the performance of the ensembled classifiers. However, some refinement in the paper might be required.

Major points:

1) Equation (7) in the proof is incorrect, although the conclusion holds. The probability follows the distribution, but the equality doesn't hold. Also, Lemma 2 is important for the idea to work, but the reference or the proof of Lemma 2 is missing.

2) The reported generalization bounds for the new methods are perhaps not very comparable to the others in the sense that it is the generalization bound for the stochastic MV, which is different from the deterministic MVs. If we consider the deterministic MV induced by the stochastic MV, for example, the expected MV, the bound would be 2 times larger.


Minor points:

1) The notation of the vectors is not consistent throughout the paper. It would be better to use (), instead of [] or {} to denote a vector. "unit vector" in line 161 should be "all-ones vector." In the statement of Lemma 2, [1, M] should be [M]. The definition of R(\rho) in line 175 is missing. \hat{R}_{\leq m} (\hat{R}_{> m}), and their definitions in Line 233 are missing. \mathcal{D} in line 224 should be D. Also, some references in the appendix are not properly handled, for instance, the captions of Figure 9 and Table 1.
limitations_and_societal_impact: Yes. The authors have discussed the potentially large KL increasing with M. The runtime of the exact method could be large, while the runtime of the approximation method is small for smaller M but increases with M. On the other hand, I don't see any negative societal impact in this work so far.
review_title: null

Meta-review: The reviewers like the approach proposed in the paper and recommend acceptance. There were several clarity issues raised during the discussion and I hope they will be addressed in the final revision. In particular, the fixes to benchmark experiments that were discussed and revision of the two-moon experiment.
Decision: Accept (Poster)