How many classifiers do we need?

Authors: hyunsuk  kim
liam  hodgkinson
ryan  theisen
michael w mahoney
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:55:05

Abstract: As performance gains through scaling data and/or model size experience diminishing returns, it is becoming increasingly popular to turn to ensembling, where the predictions of multiple models are combined to improve accuracy. 
In this paper, we provide a detailed analysis of how the disagreement and the polarization (a notion we introduce and define in this paper) among classifiers relate to the performance gain achieved by aggregating individual classifiers, for majority vote strategies in classification tasks.
We address these questions in the following ways. 
(1) An upper bound for polarization is derived, and we propose what we call a neural polarization law: most interpolating neural network models are 4/3-polarized. Our empirical results not only support this conjecture but also show that polarization is nearly constant for a dataset, regardless of hyperparameters or architectures of classifiers. 
(2) The error of the majority vote classifier is considered under restricted entropy conditions, and we present a tight upper bound that indicates that the disagreement is linearly correlated with the target, and that the slope is linear in the polarization.
(3) We prove results for the asymptotic behavior of the disagreement in terms of the number of classifiers, which we show can help in predicting the performance for a larger number of classifiers from that of a smaller number. 
Our theories and claims are supported by empirical results on several image classification tasks with various types of neural networks.

Main paper: 
 introduction: 
 As performance gains through scaling data and/or model size experience diminishing returns, it is becoming increasingly popular to turn to ensembling, where the predictions of multiple models are combined, both to improve accuracy and to form more robust conclusions than any individual model alone can provide. In some cases, ensembling can produce substantial benefits, particularly when increasing model size becomes prohibitive. In particular, for large neural network models, deep ensembles [LPB17] are especially popular. These ensembles consist of independently trained models on the same dataset, often using the same hyperparameters, but starting from different initializations.The cost of producing new classifiers can be steep, and it is often unclear whether the additional performance gains are worth the cost. Assuming that constructing two or three classifiers is relatively cheap, procedures capable of deciding whether to continue producing more classifiers are needed. To do so requires a precise understanding of how to predict ensemble performance. Of particular interest are majority vote strategies in classification tasks, noting that regression tasks can also be formulated in this way by clustering outputs. In this case, one of the most effective avenues for predicting performance is the disagreement [JNBK22, BJRK22]: measuring the degree to which classifiers provide different conclusions over a given dataset. Disagreement is concrete, easy to compute, and strongly linearly correlated with majority vote prediction accuracy, leading to its use in many applications. However, a priori, the precise linear relationship between disagreement and accuracy is unclear, preventing the use of disagreement for predicting ensemble performance.Our goal in this paper is to go beyond disagreement-based analysis to provide a more quantitative understanding of the number of classifiers one should use to achieve a desired level of performance in modern practical applications, in particular for neural network models. In more detail, our contributions are as follows.(i) We introduce and define the concept of polarization, a notion that measures the higherorder dispersity of the error rates at each data point, and which indicates how polarized the ensemble is from the ground truth. We state and prove an upper bound for polarization (Theorem 1). Inspired by the theorem, we propose what we call a neural polarization law (Conjecture 1): most interpolating (Definition 2) neural network models are 4/3-polarized. We provide empirical results supporting the conjecture (Figures 1 and 2 ).(ii) Using the notion of polarization, we develop a refined set of bounds on the majority vote test error rate. For one, we provide a sharpened bound for any ensembles with a finite number of classifiers (Corollary 1). For the other, we offer a tighter-than-ever bound under an additional condition on the entropy of the ensemble (Theorem 4). We provide empirical results that demonstrate our new bounds perform significantly better than the existing bounds on the majority vote test error (Figure 3 ).(iii) The asymptotic behavior of the majority vote error rate is determined as the number of classifiers increases (Theorem 5). Consequently, we show that we can predict the performance for a larger number of classifiers from that of a smaller number. We provide empirical results that show such predictions are considerably accurate across various pairs of model architecture and dataset (Figure 4 ).In Section 2, we define the notations that will be used throughout the paper, and we introduce upper bounds for the error rate of the majority vote from previous work. The next three sections are the main part of the paper. In Section 3, we introduce the notion of polarization, η ρ , which plays a fundamental role in relating the majority vote error rate to average error rate and disagreement. We explore the properties of the polarization and present empirical results that corroborate our claims. In Section 4, we present tight upper bounds for the error rate of the majority vote for ensembles that satisfy certain conditions; and in Section 5, we prove how disagreement behaves in terms of the number of classifiers. All of these ingredients are put together to estimate the error rate of the majority vote for a large number of classifiers using information from only three sampled classifiers. In Section 6, we provide a brief discussion and conclusion. Additional material is presented in the appendices. 
preliminaries: 
 In this section, we introduce notation that we use throughout the paper, and we summarise previous work on the performance of the majority vote error rate.We focus on K-class classification problems, with features X ∈ X , labels Y ∈ [K] = {1, 2, ..., K} and feature-label pairs (X, Y ) ∼ D. A classifier h : X → [K] is a function that maps a feature to a label. We define the error rate of a single classifier h, and the disagreement and the tandem loss [MLIS20] between two classifiers, h and h ′ , as the following:Error rate :L(h) = E D [1(h(X) ̸ = Y )] Disagreement : D(h, h ′ ) = E D [1(h(X) ̸ = h ′ (X))]Tandem loss :L(h, h ′ ) = E D [1(h(X) ̸ = Y )1(h ′ (X) ̸ = Y )],where the expectation E D is used to denote E (X,Y )∼D . Next, we consider a distribution of classifiers, ρ, which may be viewed as an ensemble of classifiers. This distribution can represent a variety of different cases. Examples include: (1) a discrete distribution over finite number of h i , e.g., a weighted sum of h i ; and (2) a distribution over a parametric family h θ , e.g., a distribution of classifiers resulting from one or multiple trained neural networks. Given the ensemble ρ, the (weighted) majority voteh MV ρ : X → [K] is defined as h MV ρ (x) = arg max y∈[K] E ρ [1(h(x) = y)].Again, E ρ denotes E h∼ρ , and we use E ρ , E ρ 2 , P ρ for E h∼ρ , E (h,h ′ )∼ρ 2 , P h∼ρ , respectively, throughout the paper. In this sense, E ρ [L(h)] represents the average error rate under a distribution of classifiers ρ and E ρ 2 [D(h, h ′ )] represents the average disagreement between classifiers under ρ.Hereafter, we refer toE ρ [L(h)], E ρ 2 [D(h, h ′ )],and L(h MV ρ ) as the average error rate, the disagreement, and the majority vote error rate, respectively, withL(h MV ρ ) = E D [1(h MV ρ (X) ̸ = Y )]. Lastly, we define the point-wise error rate, W ρ (X, Y ), which will serve a very important role in this paper (for clarity, we will denote W ρ (X, Y ) by W ρ unless otherwise necessary):W ρ (X, Y ) = E ρ [1(h(X) ̸ = Y )].(1)The simplest relationship between the majority vote error L(h MV ρ ) and the average error rate E ρ [L(h)] was introduced in [McA98] . It states that the error in the majority vote classifier cannot exceed twice the average error rate:EQUATIONA simple proof for this relationship can be found in [MLIS20] using Markov's inequality. Although (2) does not provide useful information in practice, it is worth noting that this bound is, in fact, tight. There exist pathological examples where h MV ρ exhibits twice the average error rate (see Appendix C in [TKY + 24]). This suggests that we can hardly obtain a useful or tighter bound by relying on only the "first-order" term,E ρ [L(h)].Accordingly, more recent work constructed bounds in terms of "second-order" quantities,E ρ 2 [L(h, h ′ )] and E ρ 2 [D(h, h ′ )].In particular, [LMRR17] and [MLIS20] designed a so-called C-bound using the Chebyshev-Cantelli inequality, establishing that, ifE ρ [L(h)] < 1/2, then L(h MV ρ ) ≤ E ρ 2 [L(h, h ′ )] -E ρ [L(h)] 2 E ρ 2 [L(h, h ′ )] -E ρ [L(h)] + 1 4 .(3)As an alternative approach, [MLIS20] incorporated the disagreement E ρ 2 [D(h, h ′ )] into the bound as well, albeit restricted to the binary classification problem, to obtain:EQUATIONWhile (3) and (4) may be tighter in some cases, once again, there do exist pathological examples where this bound is as uninformative as the first-order bound (2). Motivated by these weak results, [TKY + 24] take a new approach by restricting ρ to be a "good ensemble," and introducing the competence condition (see Definition 3 in our Appendix A). Informally, competent ensembles are those where it is more likely-in average across the data-that more classifiers are correct than not.Based on this notion, [TKY + 24] prove that competent ensembles are guaranteed to have weighted majority vote error smaller than the weighted average error of individual classifiers:EQUATIONThat is, the majority vote classifier is always beneficial. Moreover, [TKY + 24] proves that any competent ensemble ρ of K-class classifiers satisfy the following inequality.EQUATIONWe defer further discussion of competence to Appendix A, where we introduce simple cases for which competence does not hold. In these cases, we show how one can overcome this issue so that the bounds (5) and (6) still hold. In particular, in Appendix A.3, we provide an example to show the bound (6) is tight.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss the difficulties in estimating certain quantities we are working with.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] .Justification: We repeated the same procedure across various models and hyperparameter choices.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
the polarization of an ensemble: 
 In this section, we introduce a new quantity, η ρ , which we refer to as the polarization of an ensemble ρ. First, we provide examples as to what this quantity represents and draw a connection to previous studies. Then, we present theoretical and empirical results that show this quantity plays a fundamental role in relating the majority vote error rate to average error rate and disagreement. In Theorem 1, we prove an upper bound for the polarization η ρ , which highlights a fundamental relationship between the polarization and the constant 4 3 . Inspired from the theorem, we propose Conjecture 1 which we call a neural polarization law. Figures 1 and 2 present empirical results on an image recognition task that corroborates the conjecture.We start by defining the polarization of an ensemble. In essence, the polarization is an improved (smaller) coefficient on the Markov's inequality on P D (W ρ > 0.5), where W ρ is the point-wise error rate defined as equation (1). It measures how much the ensemble is "polarized" from the truth, with consideration of the distribution of W ρ .EQUATION)The polarization of an ensemble ρ isEQUATIONwhich is the smallest value of η satisfies inequality (7).Note that the polarization always takes a value in [0, 4], due to the positivity constraint and Markov's inequality. Also note that ensemble ρ with polarization η ρ is η-polarized for any η ≥ η ρ .To understand better what this quantity represents, consider the following examples. The first example demonstrates that polarization increases as the majority vote becomes more polarized from the truth, while the second example demonstrates how polarization increases when the constituent classifiers are more evenly split.Example 1. Consider an ensemble ρ where 75% of classifiers output Label 1 with probability one, and the other 25% classifiers output Label 2 with probability one.-Case 1. The true label is Label 1 for the whole data.In this case, the majority vote in ρ results in zero error rate. The point-wise error rate W ρ is 0.25 on the entire dataset, and thus P D (W ρ > 0.5) = 0. The polarization η ρ is 0.-Case 2. The true label is Label 1 for half of the data and is Label 2 for the other half.In this case, the majority vote is only correct for half of the data. The point-wise error rate W ρ is 0.25 for this half, and is 0.75 for the other half. The polarization η ρ is 0.5/0.3125 = 1.6.-Case 3. The true label is Label 2 for the whole data.In this case, the majority vote in ρ is wrong on every data point. The point-wise error rate W ρ is 0.75 on the entire dataset and thus P D (W ρ > 0.5) = 1. The polarization η ρ is 1/0.3125 = 3.2.Example 2. Now consider an ensemble ρ of which 51% of classifiers always output Label 1, and the other 49% classifiers always output Label 2.-Case 1. The polarization η ρ is now 0, the same as in Example 1.-Case 2. The polarization η ρ is 0.5/0.2501 ≈ 2, which is larger than 1.6 in Example 1.-Case 3. The polarization η ρ is now 1/0.2501 ≈ 4 , which is larger than 3.2 in Example 1.In addition, the following proposition draws a connection between polarization and the competence condition mentioned in Section 2.2. It states that the polarization of competent ensembles cannot be very large. The proof is deferred to Appendix A.2.Proposition 1. Competent ensembles are 2-polarized.Now we delve more into this new quantity. We introduce Theorem 1, which establishes (by means of concentration inequalities) an upper bound on the polarization η ρ . The proof of Theorem 1 is deferred to Appendix B.1. Theorem 1. Let {(X i , Y i )} m i=1 be independent and identically distributed samples from D that are independent of an ensemble ρ. Then the polarization of the ensemble, η ρ , satisfiesEQUATIONwith probability at least 1 -δ, where S = 1 m m i=1 W 2 ρ (X i , Y i ) and P = 1 m 1(W ρ (X i , Y i ) > 1/2). Surprisingly, in practice, η ρ = 4 3 appears to be a good choice for a wide variety of cases. See Figure 1 and Figure 2 , which show the polarization η ρ obtained from VGG11 [SZ14] , DenseNet40 [HLVDMW17] , ResNet18, ResNet50 and ResNet101 [HZRS16] trained on CIFAR-10 [Kri09] with various hyperparameters choices. The trend does not deviate even when evaluated on an out-ofdistribution dataset, CIFAR-10.1 [RRSS18, TFF08] . For more details on these empirical results, see Appendix C.Remark. We emphasize that values for η ρ that are larger than 4 3 does not contradict Theorem 1. This happens when the non-constant second term in (9) is larger than 4 3 , which is often the case for classifiers which are not interpolating (or, indeed, that underfit or perform poorly).Putting Theorem 1 and the consistent empirical trend shown in Figure 2 (b) together, we propose the following conjecture.Conjecture 1 (NEURAL POLARIZATION LAW). The polarization of ensembles comprised of independently trained interpolating neural networks is smaller than 4 3 . 
entropy-restricted ensembles: 
 In this section, we first present an upper bound on the majority vote error rate, L(h MV ρ ), in Theorem 2, using our notion of polarization η ρ which we introduced and defined in the previous section. Then, we present Theorems 3 and 4 which are the main elements in obtaining tighter upper bounds on L(h MV ρ ). Figure 3 shows our proposed bound offers a significant improvement over state-of-the-art results. The new upper bounds are inspired from the fact that classifier prediction probabilities tend to concentrate on a small number of labels, rather than be uniformly spread over all the possible labels. This is analogous to the phenomenon of neural collapse [Kot22] . As an example, in the context of a computer vision model, when presented with a photo of a dog, one might expect that a large portion of reasonable models might classify the photo as an animal other than a dog, but not as a car or an airplane.We start by stating an upper bound on the majority vote error, L(h MV ρ ) as a function of polarization η ρ . This upper bound is tighter (smaller) than the previous bound in inequality (6) when the polarization is lower than 2, which is the case for competent ensembles. The proof is deferred to Appendix B.2.Theorem 2. For an ensemble ρ of K-class classifiers,L(h MV ρ ) ≤ 2η ρ (K -1) K E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] ,where η ρ is the polarization of the ensemble ρ.Based on the upper bound stated in Theorem 2, we add a restriction on the entropy of constituent classifiers to obtain Theorem 3. The theorem provides a tighter scalable bound that does not have explicit dependency on the total number of labels, with a small cost in terms of the entropy of constituent classifiers. The proof of Theorem 3 is deferred to Appendix B.3.Theorem 3. Let ρ be any η-polarized ensemble of K-class classifiers that satisfies P ρ (h(x) / ∈ A(x)) ≤ ∆, where y ∈ A(x) ⊂ [K] and |A(x)| ≤ M , for all data points (x, y) ∈ D. Then, we haveL(h MV ρ ) ≤ 2η(M -1) M 1 + ∆ M -1 E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] .While Theorem 3 might provide a tighter bound than prior work, coming up with pairs (M, ∆) that satisfy the constraint is not an easy task. This is not an issue for a discrete ensemble, however. If ρ is a discrete distribution of N classifiers, then we observe that the assumption of Theorem 3 must always hold with (M, ∆) = (N +1, 0). We state this as the following corollary.Corollary 1 (FINITE ENSEMBLE). For an ensemble ρ that is a weighted sum of N classifiers, we haveEQUATIONwhere η ρ is the polarization of the ensemble ρ.See Figure 3 , which provides empirical results that compare the bound in Corollary 1 with the C-bound in inequality (3), and with inequality (6) proposed in [TKY + 24]. We can observe that the Although the bound in Corollary 1 is tighter than the bounds from previous studies, it's still not tight enough to use it as an estimator for L(h MV ρ ). In the following theorem, we use a stronger condition on the entropy of an ensemble to obtain a tighter bound. The proof is deferred to Appendix B.4. Theorem 4. For any η-polarized ensemble ρ that satisfiesEQUATIONwe haveL(h MV ρ ) ≤ η (1 + ε) E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] .The condition (11) can be rephrased as follows: compared to the error P ρ (h(x) ̸ = y), the entropy of the distribution of wrong predictions is small, and it is concentrated on a small number of labels. A potential problem is that one must know or estimate the smallest possible value of ε in advance. At least, we can prove that ε = K-2 2(K-1) always satisfies the condition (11) for an ensemble of K-class classifiers. The proof is deferred to Appendix B.4.Corollary 2. For any η-polarized ensemble ρ of K-class classifiers, we haveL(h MV ρ ) ≤ η 1 + K -2 2(K -1) E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] .Naturally, this ε is not good enough for our goal. We discuss more on how to estimate the smallest possible value of ε in the following section. 
a universal law for ensembling: 
 In this section, our goal is to predict the majority vote error rate of an ensemble with large number of classifiers by just using information we can obtain from an ensemble with a small number, e.g., three, of classifiers. Among the elements in the bound in Theorem 4,η (1 + ε) E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] ,we plug in η = 4 3 as a result of Theorem 1; and since E ρ [L(h)] is invariant to the number of classifiers, it remains to predict the behavior of E ρ 2 [D(h, h ′ )] and the smallest possible value of ε,ε ρ = E D [P ρ 2 (h(X)̸ =Y,h ′ (X)̸ =Y,h(X)̸ =h ′ (X))] 2E D [Pρ(h(X)̸ =Y )] . Since the denominator E D [P ρ (h(X) ̸ = Y )] = E ρ [L(h)]is invariant to the number of classifiers, and the numerator resembles the disagreement between classifiers, ε ρ is expected to follow a similar pattern as E ρ 2 [D(h, h ′ )]. Note that the numerator of ε ρ has the same form as the disagreement, differing by only one less label. Both are V -statistics that can be expressed as a multiple of a U -statistic, as shown in equation ( 12). In the next theorem, we show that the disagreement for a finite number of classifiers can be expressed as the sum of a hyperbolic curve and an unbiased random walk. Here, [x] denotes the greatest integer less than or equal to x and D[0, 1] is the Skorokhod space on [0, 1] (see Appendix B.5).Theorem 5. Let ρ N denote an empirical distribution of N independent classifiers {h i } N i=1 sampled from a distribution ρ andσ 2 1 = Var h∼ρ (E h ′ ∼ρ P D (h(X) ̸ = h ′ (X))). Then, there exists D ∞ > 0 such that E (h,h ′ )∼ρ 2 N [D(h, h ′ )] = 1 - 1 N D ∞ + 2 √ N Z N ,whereEZ N = 0, VarZ N → σ 2 1 and { √ t σ1 Z [N t] } t∈[0,1] converges weakly to a standard Wiener process in D[0, 1] as N → ∞. Proof. Let Φ(h i , h j ) = P D (h i (X) ̸ = h j (X)). We observe that N 2 N (N -1) E (h,h ′ )∼ρ 2 N [D(h, h ′ )] = 1 N (N -1) N i,j=1 P D (h i (X) ̸ = h j (X)) = 1 N (N -1) N i,j=1 Φ(h i , h j ) = Φ: symmetric Φ(hi,hi)=0 2 N (N -1) 1≤i<j≤N Φ(h i , h j ) =: U N , (12) which is a U -statistic with the kernel function Φ. Let Φ 0 = E (h,h ′ )∼ρ 2 Φ(h, h ′ ).The invariance principle of U -statistics (Theorem 7 in Appendix B.5) states that the processξ N = (ξ N (t), t ∈ [0, 1]), defined by ξ N ( k N ) = k 2 √ N σ 2 1 (U k -Φ 0 ) and ξ N (t) = ξ N ( [N t] N ), converges weakly to a standard Wiener process in D[0, 1] as N → ∞, since σ 2 1 = Var h∼ρ E h ′ ∼ρ Φ(h, h ′ ). Therefore, U N converges in probability as N → ∞ to D ∞ := Φ 0 . Letting Z N = σ 1 ξ N (1) = √ N 2 (U N -D ∞ ), we can express U N as U N = D ∞ + 2 √ N Z N , with EZ N = 0 and VarZ N → σ 2 1 . Since √ t σ1 Z [N t] = N t [N t] ξ N ( [N t] N ) = N t [N t] ξ N (t), it follows by Slutsky's Theorem that { √ t σ1 Z [N t] } t∈[0,1] converges weakly to a standard Wiener process in D[0, 1] as N → ∞.Theorem 5 suggests that the disagreement within N classifiers,E ρ 2 N [D(h, h ′ )], can be approximated as N -1 N D ∞ . From the disagreement within M (≪ N ) classifiers, D ∞ can be approximated as M M -1 E ρ 2 M [D(h, h ′ )], and therefore we getEQUATIONAssume that we have three classifiers sampled from ρ. We denote the average error rate, the disagreement, and the ε ρ from these three classifiers byE 3 [L(h)], E 3 [D(h, h ′ )],and ε 3 , respectively. Then, from Theorem 4 and approximation (13) (which applies to both disagreement and ε ρ ), we estimate the majority vote error rate of N classifiers from ρ as the following:EQUATIONAlternatively, we can use the polarization measured from three classifiers, η 3 , instead of η = 4 3 , to obtain:EQUATIONFigure 4 presents empirical results that compare the estimated (extrapolated) majority vote error rates in equations ( 14) and (15) with the true majority vote error for each number of classifiers. ResNet18 models are tested on four different dataset: CIFAR-10, CIFAR-10.1, Fashion-MNIST [XRV17] and Kuzushiji-MNIST [CBIK + 18] where the models are trained on the corresponding train data.MobileNet [How17] is trained and tested on the MNIST [Den12] dataset. Not only do the estimators show significant improvement compared to the bounds introduced in Section 2.2, we observe that the estimators are very close to the actual majority vote error rate; and thus the estimators have practical usages, unlike the bounds from previous studies. In Figure 4 (a2), existing bounds (3) and ( 6) are much larger compared to the average error rate. This is also the case for (architecture, dataset) pairs of other subplots. 
discussion and conclusion: 
 This work addresses the question: how does the majority vote error rate change according to the number of classifiers? While this is an age-old question, it is one that has received renewed interest in recent years. On the journey to answering the question, we introduce several new ideas of independent interest. (1) We introduced the polarization η ρ , of an ensemble of classifiers. This notion plays an important role throughout this paper and appears in every upper bound presented. Although Theorem 1 gives some insight into polarization, our conjectured neural polarization law (Conjecture 1) is yet to be proved or disproved, and it provides an exciting avenue for future work.(2) We proposed two classes of ensembles whose entropy is restricted in different ways. Without these constraints, there will always be examples that saturate even the least useful majority vote error bounds. We believe that accurately describing how models behave in terms of the entropy of their output is key to precisely characterizing the behavior of majority vote, and likely other ensembling methods.Throughout this paper, we have theoretically and empirically demonstrated that polarization is fairly invariant to the hyperparameters and architecture of classifiers. We also proved a tight bound for majority vote error, under an assumption with another quantity ε, and we presented how the components of this tight bound behave according to the number of classifiers. Altogether, we have sharpened bounds on the majority vote error to the extent that we are able to identify the trend of majority vote error rate in terms of number of classifiers.We close with one final remark regarding the metrics used to evaluate an ensemble. Majority vote error rate is the most common and popular metric used to measure the performance of an ensemble. However, it seems unlikely that a practitioner would consider an ensemble to have performed adequately if the majority vote conclusion was correct, but was only reached by a relatively small fraction of the classifiers. With the advent of large language models, it is worth considering whether the majority vote error rate is still as valuable. The natural alternative in this regard is the probability P ρ (W ρ > 1/2), that is, the probability that at least half of the classifiers agree on the correct answer. This quantity is especially well-behaved, and it frequently appears in our proofs. (Indeed, every bound presented in this work serves as an upper bound for P ρ (W ρ > 1/2).) We conjecture that this quantity is useful much more generally. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: The experiment requires no additional time beyond training each classifier.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Not applicable.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: Not applicable.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.Justification: Not applicable.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: Not applicable.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this section, we delve more into the competence condition that was introduced in [TKY + 24]. We explore in which cases the competence condition might not work and how to overcome these issues. We discuss a few milder versions of competence that are enough for bounds (5) and (6) to hold. Then we discuss how to check whether these weaker competence conditions hold in practice, with or without a separate validation set. We start by formally stating the original competence condition.Definition 3 (Competence, [TKY + 24]). The ensemble ρ is competent if for every 0 ≤ t ≤ 1/2,EQUATIONOne tricky part in the definition of competence is that it requires inequality (16) to hold for every 0 ≤ t ≤ 1/2. In case t = 1/2, the inequality becomes0 ≥ P D (W ρ = 1/2).This is not a significant issue in the case that ρ is a continuous distribution over classifiers, e.g., a Bayes posterior or a distribution over a parametric family h θ , as {W ρ = 1/2} would be a measure-zero set.In the case that ρ is a discrete distribution over finite number of classifiers, however, P D (W ρ = 1/2) is likely to be a positive quantity, in which case it can violate the competence condition.That being said, {(x, y) | W ρ (x, y) = 1/2} represent tricky data points that deserves separate attention. This event can be divided into two cases: 1) all the classifiers that incorrectly made a prediction output the same label; or 2) incorrect predictions consist of multiple labels so that the majority vote outputs the true label. Among these two possibilities, the first case is troublesome. We denote such data points by TIE(ρ, D):TIE(ρ, D) := {(x, y) | P ρ (1(h(x) = j)) = P ρ (1(h(x) = y)) = 1/2 for true label y and an incorrect label j}.In this case, the true label and an incorrect label are chosen by exactly the same ρ-weights of classifiers. An easy way to resolve this issue is to slightly tweak the weights. For instance, if ρ is an equally weighted sum of two classifiers, we can change each of their weights to be (1/2 + ϵ, 1/2 -ϵ), instead of (1/2, 1/2). This change may seem manipulative, but it corresponds to a deterministic tie-breaking rule which prioritizes one classifier over the other, which is a commonly used tiebreaking rule.Definition 4 (Tie-free ensemble). An ensemble is tie-free if P D (TIE(ρ, D)) = 0.Proposition 2. An ensemble with a deterministic tie-breaking rule is tie-free.With such tweak to make the set TIE(ρ, D) to be an empty set or a measure-zero set, we present a slightly milder condition that is enough for the bounds (5) and (6) to still hold.Definition 5 (Semi-competence). The ensemble ρ is semi-competent if for every 0 ≤ t < 1/2,EQUATIONNote that inequality (17) is a strictly weaker condition than inequality (16), and hence competence implies semi-competence. The converse is not true. An ensemble is semi-competent even if the pointwise error W ρ (X, Y ) = 1/2 on every data points, but such an ensemble is not competent.Theorem 6. For a tie-free ensemble and semi-competent ensemble ρ, L(h MV ρ ) ≤ E ρ [L(h)] andL(h MV ρ ) ≤ 4(K -1) K E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )]holds in K-class classification setting.We provide the proof as a separate subsection below.We start with the following lemma, which is a semi-competence version of Lemma 2 from [TKY + 24].Lemma 1. For a semi-competent ensemble ρ and any increasing function g satisfying g(0) = 0,E D [g(W ρ )1 Wρ≤1/2 ] ≥ E D [g( W ρ )1 Wρ<1/2 ],whereW ρ = 1 -W ρ .Proof. For every x ∈ [0, 1], it holds thatP D (W ρ 1 Wρ≤1/2 ≥ x) = P D (W ρ ∈ [x, 1/2]) 1 x≤1/2 , P D ( W ρ 1 Wρ<1/2 ≥ x) = P D ( W ρ ∈ [x, 1/2)) 1 x≤1/2 = P D (W ρ ∈ (1/2, 1 -x]) 1 x≤1/2 .From the definition of semi-competence, this implies thatP D (W ρ 1 Wρ≤1/2 ≥ x) ≥ P D ( W ρ 1 Wρ<1/2 ≥ x) for every x ∈ [0, 1].Using the fact that g(x 1 x≤c ) = g(x)1 x≤c for any increasing function g with g(0) = 0, we obtainP D (h(W ρ )1 Wρ≤1/2 ≥ x) ≥ P D (h( W ρ )1 Wρ<1/2 ≥ x).Putting these together with a well-known equality EX = ∞ 0 P(X ≥ x)dx for a non-negative random variable X proves the lemma. Now we use Lemma 1 and Theorem 2 to prove Theorem 6.Proof of Theorem 6. Applying Lemma 1 with g(x) = 2x 2 gives,EQUATIONPutting this together with the following decomposition of E D [2W 2 ρ ] shows that the ensemble ρ is 2-polarized:EQUATIONTherefore, applying Theorem 2 with constant η = 2 concludes the proof.We also state the following proof of Proposition 1 for completeness.Proof of Proposition 1. Inequality (19) with Lemma 3 proves the proposition.Here, we provide a combination of (ρ, D) of which L(h MV ρ ) is arbitrarily close to the bound. Consider, for each feature x, that exactly (1 -ϵ) fraction of classifiers predict the correct label, and that the remaining ϵ fraction of classifiers predict a wrong label. In this case,L(h MV ρ ) = 0, E ρ [L(h)] = ϵ, and E ρ 2 [D(h, h ′ )] = 2ϵ(1 -ϵ).Hence, the upper bound (6) is 4(K-1) K ϵ 2 , which can be arbitrarily close to 0.In this section, we provide proofs for our main results.We start with the following lemma which shows the concentration of a linear combination of W 2 ρ andEQUATION) Proof. Let Z 2i = W 2 ρ (X i , Y i ) and Z 0i = 1(W ρ (X i , Y i ) > 1/2). Observe that η Z 2i -Z 0i always takes a value between [ η 4 -1, max{ η 4 , η-1}] since W ρ (X i , Y i ) ∈ [0, 1].This implies that ηZ 2i -Z 0i s are i.i.d. sub-Gaussian random variable with parameter σ = max{ 3η 4 , 1}/2. By lettingA 2 = E[ηW 2ρ -1(W ρ ≥ 1/2)] and using the Hoeffding's inequality, we obtain1 m (ηZ 2 -Z 0 ) -A 2 ≤ max{ 3η 4 , 1} 2m log 1 δ with probability at least 1 -δ.Therefore, ρ is η-polarized with probability at least 1 -δ if1 m (ηZ 2 -Z 0 ) > max{ 3η 4 , 1} 2m log 1 δ .Now we use Lemma 2 to prove Theorem 1.Proof of Theorem 1. Observe that S = 1 m Z 2 , P = 1 m Z 0 , and thus 1 m (ηZ 2 -Z 0 ) = ηS -P . For η ≥ 4 3 , the lower bound in Lemma 2 is simply 3η 8m log 1 δ , and the inequality (20) can be viewed as a quadratic inequality in terms of √ η. From quadratic formula, we know thatif √ η > 3η 8m log 1 δ + 3η 8m log 1 δ + 4SP 2S , then ηS -P - 3η 8m log 1 δ > 0.Putting this together with Lemma 2 proves the theorem:η ≥ max      4 3 ,   3 8m log 1 δ + 3 8m log 1 δ + 4SP 2S   2      (21) ⇒ ηS -P > 3η 8m log 1 δ ⇒ Lemma2 ρ is η-polarized w.p. 1 -δ,and thus the polarization η ρ , the smallest η such that ρ is η-polarized, is upper bounded by the right hand side of inequality (21).We start by proving the following lemma which relates the error rate of the majority vote, L(h MV ρ ), with the point-wise error rate, W ρ , using Markov's inequality. In general, L(h MV ρ ) ≤ P D (W ρ ≥ 1/2) is true for any ensemble ρ. We prove a tighter version of this. The difference between the two can be non-negligible when dealing with an ensemble with finite number of classifiers. Refer to Appendix A.1 and Definition 4 for more details regarding this difference and tie-free ensembles.Lemma 3. For a tie-free ensemble ρ, we have the inequality L(h MV ρ ) ≤ P D (W ρ > 1/2).Proof. For given feature x, W ρ ≤ 1/2 implies that more than or exactly ρ-weighted half of the classifiers outputs the true label. Since the ensemble ρ is tie-free, h MV ρ outputs the true label ifW ρ ≤ 1/2. Therefore, {(x, y) | W ρ (x, y) ≤ 1/2} ⊂ {(x, y) | h MV ρ (x) = y}.Applying P D on the both sides proves the lemma.The following lemma appears as Lemma 2 in [MLIS20] . This lemma draws the connection between the point-wise error rate, W ρ and the tandem loss,E ρ 2 [L(h, h ′ )]. Lemma 4. The equality E D [W ρ 2 ] = E ρ 2 [L(h, h ′ )] holds.The next lemma appears as Lemma 4 in [TKY + 24]. This lemma provides an upper bound on the tandem loss, E ρ 2 [L(h, h ′ )], in terms of the average error rate, E ρ [L(h)], and the average disagreement,E ρ 2 [D(h, h ′ )].Lemma 5. For the K-class problem,E ρ 2 [L(h, h ′ )] ≤ 2(K -1) K E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] .Now we use these results to prove Theorem 2.Proof of Theorem 2. Putting Lemmas 3, 4, and 5 and the definition of the polarization together proves the theorem:L(h MV ρ ) ≤ Lemma 3 P D (W ρ > 1/2) ≤ polarization η ρ E D [W 2 ρ ] = Lemma 4 η ρ E ρ 2 [L(h, h ′ )] = Lemma 5 2η ρ (K -1) K E h [L(h)] - 1 2 E h,h ′ [D(h, h ′ )] .We start with a lemma which is a corollary of Newton's inequality.Lemma 6. For any collection of probabilities p 1 , . . . , p n , the following inequality holds.1≤i<j≤n p i p j ≤ n -1 2n n i=1 p i 2 .Proof. Newton's inequality states that Rearranging the terms gives the lemma. Now we use this and the previous lemmas to prove Theorem 3.Proof of Theorem 3. From Lemma 3, Lemma 4, and the definition of η-polarized ensemble, we have the following relationship between L(h MV ρ ) and E ρ 2 [L(h, h ′ )]:EQUATIONFrom this, it suffices to prove that h α E ρ 2 [L(h, h ′ )] is smaller than the upper bound in the theorem. First, observe the following decomposition of E ρ 2 [L(h, h ′ )]:EQUATIONFor any predictor mapping into K classes, let y denote the true label for an input x. Now we derive a lower bound of P ρ 2 (h(X) ̸ = Y, h ′ (X) = Y ) using the following decomposition of P ρ 2 (h(x) ̸ = h ′ (x)):1 2 P ρ 2 (h(x) ̸ = h ′ (x)) = P ρ 2 (h(x) ̸ = y, h ′ (x) = y) + i / ∈A(x) j∈A(x)\{y} p i p j , + i,j∈A(x)\{y} i<j p i p j + i,j / ∈A(x) i<j p i p j ,where p i := p i (x) = P ρ (h(x) = i). We let ∆ x := P ρ (h(x) / ∈ A(x)) and apply Lemma 6 to the last two terms:1 2 P ρ 2 (h(x) ̸ = h ′ (x)) = P ρ 2 (h(x) ̸ = y, h ′ (x) = y) + ∆ x (1-p Y -∆ x ) + i,j∈A(x)\{y} i<j p i p j + i,j / ∈A(x) i<j p i p j ≤ Lemma 6 P ρ 2 (h(x) ̸ = y, h ′ (x) = y) + ∆ x (1-p y -∆ x ) + M -2 2(M -1) (1-p y -∆ x ) 2 + K -M -1 2(K -M ) ∆ 2 x .Rearranging the terms and plugging 1-p Y = P ρ (h(x) ̸ = y) givesP ρ 2 (h(x) ̸ = y, h ′ (x) = y) ≥ 1 2 P ρ 2 (h(x) ̸ = h ′ (x)) - ∆ x M -1 P ρ (h(x) ̸ = y) - M -2 2(M -1) P ρ (h(x) ̸ = y) 2 + K -1 2(K -M )(M -1) ∆ 2 x ≥ 1 2 P ρ 2 (h(x) ̸ = h ′ (x)) - ∆ x M -1 P ρ (h(x) ̸ = y) - M -2 2(M -1) P ρ (h(x) ̸ = y) 2 ≥ 1 2 P ρ 2 (h(x) ̸ = h ′ (x)) - ∆ M -1 P ρ (h(x) ̸ = y) - M -2 2(M -1) P ρ (h(x) ̸ = y) 2 ,where the last inequality comes from the condition ∆ x := P ρ (h(x) / ∈ A(x)) ≤ ∆. Putting this together with the equality (23) givesE D P ρ (h(X) ̸ = Y ) 2 ≤ 1 + ∆ M -1 E D [P ρ (h(X) ̸ = Y )] - 1 2 E D P ρ 2 (h(X) ̸ = h ′ (X)) + M -2 2(M -1) E D P ρ (h(X) ̸ = Y ) 2 ,which impliesE ρ 2 [L(h, h ′ )] = E D P ρ (h(X) ̸ = Y ) 2 ≤ 2(M -1) M 1 + ∆ M -1 E D [P ρ (h(X) ̸ = Y )] - 1 2 E D P ρ 2 (h(X) ̸ = h ′ (X)) = 2(M -1) M 1 + ∆ M -1 E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] .Combining this with inequality (22) concludes the proof.First, we prove Theorem 4 by decomposing the point-wise disagreement between constituent classifiers.Proof of Theorem 4. The following decomposition of P ρ 2 (h(x) ̸ = h ′ (x)) holds:1 2 P ρ 2 (h(x) ̸ = h ′ (x)) = P ρ 2 (h(x) ̸ = y, h ′ (x) = y) + 1 2 P ρ 2 (h(x) ̸ = y, h ′ (x) = y, h(x) ̸ = h ′ (x)).Applying E D to both sides and using the given condition (11), we obtain,1 2 E D [P ρ 2 (h(X) ̸ = h ′ (X))] ≤ E D P ρ 2 (h(X) ̸ = Y, h ′ (X) = Y ) + ε E D [P ρ (h(X) ̸ = Y )].The left hand side equals 1 2 E ρ 2 [D(h, h ′ )], and the second term on the right hand side is simply ε E ρ [L(h)]. Hence, the inequality above can be rephrased as follows:EQUATIONPutting this together with the inequality (22) and the equality (23), givesL(h MV ρ ) ≤ Ineq.22 η E ρ 2 [L(h, h ′ )] = Eq.23 η E D P ρ (h(X) ̸ = Y ) -P ρ 2 (h(X) ̸ = Y, h ′ (X) = Y ) = η E ρ [L(h)] -E D P ρ 2 (h(X) ̸ = Y, h ′ (X) = Y ) ≤ Ineq.24 η (1 + ε)E ρ [L(h)] - 1 2 E ρ 2 [D(h, h ′ )] .Next, we use Lemma 6 to prove Corollary 2.Proof of Corollary 2. Let p i := P ρ (h(x) = i) for i ∈ [K], and let y = K be the true label, without loss of generality. Then, we observeP ρ 2 (h(X) ̸ = Y, h ′ (X) ̸ = Y, h(X) ̸ = h ′ (X)) = K-1 i,j=1 i̸ =j p i p j and P ρ (h(X) ̸ = Y ) = K-1 i=1 p i .Lemma 6 gives us the following:1≤i̸ =j≤K-1 p i p j 2 1≤i≤K-1 p i ≤ 1≤i̸ =j≤K-1 p i p j 2( 1≤i≤K-1 p i ) 2 ≤ 1≤i<j≤K-1 p i p j ( 1≤i≤K-1 p i ) 2 ≤ Lemma 6 K -2 2(K -1),where the first inequality used the fact that K-1 i=1 p i ≤ 1. Thus, ε = K-2 2(K-1) satisfies the condition (11), and the result follows from Theorem 4.In this subsection, we state the invariance principle of U -statistics, which plays a main role in the proof of Theorem 5. We note that this is a special case of an approximation of random walks (Theorem 23.14 in [Kal21] ) combined with functional central limit theorem (Donsker's theorem). Here, D[0, 1] is the Skorokhod space on [0, 1], which is the space of all real-valued right-continuous functions on [0, 1] equipped with the Skorokhod metric/topology (see Section 14 in [Bil13] ).Theorem 7 (Theorem 5.2.1 in [KB13] ). Define a U -statisticEQUATIONξ n k n = k(U k -Φ 0 ) 2 nσ 2 1 for k = 0, 1, ..., n -1,and ξ n (t) = ξ n ([nt]/n), with [x] denoting the greatest integer less than or equal to x. Then, ξ n converges weakly in D[0, 1] to a standard Wiener process as n → ∞.In this section, we provide additional details on our empirical results. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: The research conducted in this paper conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: The reviewers agreed that this paper addresses an important topic, is clearly written, and has strong results. Some reviewers had concerns about the variety of tasks, models, and datasets in the experimental validations, but thought the positives outweighed this concern. Given the unanimous recommendation for acceptance from the four reviewers, I recommend accepting this paper.

Reviews: review: paper_summary: paper_summary: The authors introduce polarity $\eta$ to characterize an ensemble of classifiers. Polarity is the probability that over half the models in an ensemble make an incorrect prediction divided by the expected square fraction of models that make an incorrect prediction. This quantity is bound by a concentration inequality, and the authors empirically demonstrate that this value tends to hover around 4/3. The authors then bound the ensemble error probability via a relation that involves polarity, and refine this bound based on further assumptions on the behavior of the ensemble. Finally, the authors show how to extrapolate small ensemble statistics to estimate error rates of larger ensembles.
strength_weakness: strength_weakness: It seems that Theorem 1 would hold if we replace 4/3 with any quantity that is larger than 4/3 as well, so theoretically it is unclear where this quantity really arises from and what prevents this quantity from being made smaller. Perhaps the authors can sketch out some intuition on this.

Some additional experimental validation could help strengthen paper, since some of the results are empirical. For example, the experiments shown in Figure 3 could be extended to the other models discussed in the paper, and ideally should be performed multiple times to obtain a good idea of how reliable the estimates will be. Furthermore, some statistics could be reported (e.g. mean and variances for the distributions in Figure 1). However this is primarily theoretical work, so this is not a major concern.
questions: questions: Figure 1 appears to show a positive correlation between error rate and polarity. I imagine this is driven by the numerator term in polarity. Could the authors comment on this, and whether they would expect the 4/3 rule to hold in a small or large error regime (e.g. $\epsilon$ or $0.5-\epsilon$?).

For the experimental results shown in Figure 3, is it possible to plot some of the other bounds described in Section 2.2 for reference?

The ``#’’ sign shows up in an equation on line 131, which was not defined. Is this an error?
limitations: limitations: Yes.
paper_summary: paper_summary: This paper focuses on quantifying the impact of number of classifiers on the error rate of majority vote decision strategy for ensemble classifiers. They define the notion of “polarity” of an ensemble and use this notion to characterize the relationship between majority vote error rate and disagreement between classifiers in any relevant ensemble. Empirical analysis over CIFAR and MNIST datasets shows that the paper’s method provides a tighter bound for majority error vote than other prior methods.
strength_weakness: strength_weakness: 1. Some of the terms used in the paper could use additional descriptions. For example, I don’t see the description of “interpolation” or “interpolating models” anywhere. Considering that it is important in interpreting Figure 1 and also determining when the conjectured polarity upper bound is likely to hold, I would suggest spending a paragraph on prior work around interpolation.  

2. Related to the above point, some more details around the Remark in Lines 139-145 would be helpful. It looks like for the non-constant term in the maximum of Thm 1, the numerator and denominator are empirical approximations of the numerator and denominator of $\eta$. Given that, could these converge to $\eta$ itself as $m \rightarrow \infty$? And if so, isn’t it possible for the Conjecture 1 to be violated as even values of $\eta > 4/3$ could satisfy the condition in Theorem 1? Let me know if I am misinterpreting something here.  
3. More details of empirical analysis would be good to include in the main body. For instance, details about number of classifiers in each ensemble and whether the classifiers only differed in starting points (or other parameters as well) would be good to know while reading the figures themselves
questions: questions: 1. On the point of polarity, it would be good to get more details around the discussion in the Remark on Lines 139-145. The specific questions I have on this are noted in the point above. 
2. Regarding my point on empirical analysis, did the trained classifier ensemble consist of classifiers with just different starting points or were other training details/parameters changed?
3. Minor point, but $\delta$ notation is used in both Theorem 1 (for probability) and Theorems 3, 4 (for disagreement). And it looks like this notation is used in different contexts in these different results. Might be good to use different notations at different places if they are not related.
limitations: limitations: Some limitations discussed in the conclusion section.
paper_summary: paper_summary: This paper analyzes the majority vote error of an ensemble of classifiers. A new quantity called polarity is introduced. The polarity of neural networks is analyzed empirically and theoretically, and stronger bounds on the majority vote error are derived based on the polarity. Finally, the previously derived bounds are used to predict the majority vote error rate of a large ensemble from that of a smaller ensemble.
strength_weakness: strength_weakness: The conjecture of the neural polarity is somewhat lacking in evidence given the generality of the statement. While Figure 1 provides some empirical evidence for a variety of models and hyperparameters, only the relatively simple CIFAR-10 dataset is considered. It would be interesting to see if the neural polarity law still holds for more challenging tasks, where the performance of each individual classifier would be lower.

I also feel that some parts of the paper could be improved for clarity. In particular, in Section 5 it is somewhat unclear how all the results fit together, which can detract from their potential significance. See some of the questions below.
questions: questions: 1. The description of Theorem 1 as a lower bound in line 127 is somewhat misleading. As mentioned later in the paper, models can be polarized for $\eta$ lower than the derived bound. I wonder if the wording here can be improved.

2. I do not quite see the connection to neural collapse in line 159. Neural collapse describes the phenomenon that representations of examples from the same class collapse to a single point and the class means form a simplex ETF. Still, it does not state how the probabilities of any given example are distributed among the labels.

3. In theorem 5, what is $\sigma^2$? And what is the significance of the scaled random walk converging to Brownian motion? As far as I can tell, the convergence to Brownian motion is a restatement of a standard result from stochastic calculus and is not used anywhere else in the paper.

4. In the definition of $\mathcal{L}(h)$ in line 215, it appears that the symbol $h$ is overloaded.
limitations: limitations: Limitations are addressed.
paper_summary: paper_summary: The authors address the setting of ensembling, where the predictions of multiple models are combined to improve accuracy and form more robust conclusions. The authors define a quantity η (polarity among agents within a dataset), and show both empirically and theoretically that this quantity is nearly constant regardless of hyperparameters or architectures of classifiers. The authors present a tight upper bound for the error of majority vote under restricted entropy conditions. This bound indicates that the disagreement is linearly correlated with the target, and the slope is linear in polarity, η. Finally, the authors prove asymptotic behavior of disagreement in terms of the number of agents, which can help predicting the performance for a larger number of agents from that of a smaller number.
strength_weakness: strength_weakness: 1. The claim that the authors have shown empirically that η is nearly constant regardless of hparams or architectures is overbroad for the provided evidence; the authors should consider scoping their empirical claims more modestly, in keeping with the small scale experiments in this paper.
2. The phrase "a distribution over a parametric family hθ , e.g., a distribution of classifiers that is trained from a neural network or a random forest", could be misinterpreted as a claim that random forests are parametric models
3. Equation (6) appears to have a formatting error, there's a long underscore under one half of the equation
4. Conjecture 1 uses the term *interpolating* neural networks; however, this term is not defined in Sec. 2 and is overloaded in the literature. Please provide a definition in Sec. 2 or a relevant citation.
5. "Since the denominator ... is invariant to the number of classifiers and the numerator resembles the disagreement between classifiers, δ is expected to follow a similar pattern": this point could use more clarification
questions: questions: QUESTIONS

* How do the authors define *interpolating* neural networks in this work?
* Can the authors please expand on the point raised in W5?

SUMMARY OF THE REVIEW

This paper presents significant new theoretical contributions in its area, which is important and of interest to the larger community, but has a few overclaims and oversights which currently limit it. As the paper stands, I will give a weak accept, but if the weaknesses I list are addressed, I will raise my score.
limitations: limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.

Comments: comment: Our current theory doesn’t suggest a _general_ positive correlation. This is reflected in our experiments: when comparing the CIFAR10 and CIFAR10-1 examples in Figure A ([figure_document](https://openreview.net/attachment?id=RvSCTfKipG&name=pdf)), the polarity of the interpolators hasn’t changed significantly, even though the majority vote error rate has increased by ~0.1 on average.

However, we do not reject the possibility that a correlation might exist on a case-by-case basis. Our listed examples, Example 1 and Example 2 on page 4, highlight two extreme cases where this correlation is present. We are interested in conducting further investigations in future work.

Regarding polarity, as both Figure 1 and Figure A ([figure_document](https://openreview.net/attachment?id=RvSCTfKipG&name=pdf)) suggest, and based on our efforts to make Lemma 1 reasonably sharp, we conjecture that 4/3 is not purely an artifact of the proof.
We are glad your concerns were addressed. Please let us know if you have any additional questions.
We are glad the additional results and clarification were helpful. Please let us know if you have any additional questions or need further clarification.
We are glad that we could address your concerns and questions regarding our work. We will move some key implementation details to the main body in the final version.
Thank you for your response. I remain unsure whether 4/3 is an intrinsic property of polarity of whether it is an artifact of the proof - I would need to spend more time with the paper, which unfortunately we are short on. I am satisfied with the new figures the authors have provided to address [Weakness 2] and I have updated my score to reflect this.

On question 1: If you look at Figure 1 it seems as though there is a positive correlation. I was asking what you would expect to happen if the x-axis is expanded to 0-0.5 and populated with additional points in those unseen regimes.
Thanks to the authors for the clarifications. I will keep my score as it is but I would suggest moving some of the implementation details from the appendix to the main body if possible.
I would like to thank the authors for their detailed response. To acknowledge that my concerns have been addressed, I will update my score.
Thank you for the additional results and clarifications. I would be glad to increase my score.