How many classifiers do we need?
Authors: Hyunsuk Kim
Liam Hodgkinson
Ryan Theisen
Michael W. Mahoney
Venue: NeurIPS 2024 poster (2024)
Keywords: ensemble
model aggregation
machine learning
computer vision
Primary area: learning_theory
TL;DR: We develop bounds on the majority vote error that are tight enough to predict ensemble performance.

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 rate 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 error rate, 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 theoretical findings are supported by empirical results on several image classification tasks with various types of neural networks.

How many classifiers do we need?
Hyunsuk Kim Department of Statistics University of California, Berkeley hyskin77berkeeley. edu
Liam Hodgkinson
School of Mathematics and Statisties University of Melbourne, Australia Ihodgkinsoonunnieelb edu. au
Ryan Theisen Harmonic Discovery
Michael W. Mahoney
ICSI, LBNL, and Dept. of Statisties University of California, Berkeley nmahoney@stat. berkeeeettetbbbbeeeeeeee.e edu
xyaathharmoonicclsccvvveryooom com
Abstract
As performance gains through scaling data and/or model size experience diminish- ing returns, it becoming increasingly popular to turn ensembling, where the predictions of multiple models are combined to improve accuracy. In this paper, we provide detailed analysis of how the disagreement and the polarization 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 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 hyperparamcters classifiers. (2) The error rate the majority vote classifier is considered under restricted entropy conditions, and present tight upper bound that indicates that the disagreement is linearly correlated with the error rate, 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 predicting the performance for larger number of classifiers from that of a smaller number. Our theoretical findings are supported by empirical results on several image classification tasks with various types of neural networks.
architectures of
1 Introduction
As performance gains through scaling data and/or model size experience diminishing returns, is becoming increasingly popular to turn to ensembling, where the predictions of multiple models 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 17] 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 often unclear whether the additional performance gains are worth the cost. Assuming that constructing two 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 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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, 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 desired level of performance in modern practical applications, in particular for neural network models. In more detail, our contributions are follows.
(i) We introduce and define the concept of polarization, a notion that measures the higher- order dispersity of the error rates at each data point, and which indicates how polarized the ensemble is relative to the ground truth. We state and prove 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 and 2).
(ii) Using the notion of polarization, develop a refined set of bounds 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 new, tighter 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 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 accurate across various pairs of model architecture and dataset (Figure 4).
In Section bounds for the eтror rate of the majority vote from previous work. The next three sections are the main part of the paper. In Section we introduce the notion of polarization, 77. 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 eгror rate of the majority vote for ensembles that satisfy certain conditions; and in Section we prove how disagreement behaves in terms of the number of classifiers. All of these ingredients are put together to estimate the eтrоr rate of the majority vote for a large number of classifiers using information from only three sampled classifiers. In Section 6, we provide brief discussion and conclusion. Additional material is presented in the appendices.
define the notations that will be used throughout the paper, and introduce upper
2
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.
2.1 Notations
We focus on K-class classification problems, with features X E X', labels Y E [K] = 2,.,...., K} and feature-label pairs (X, Y) D. A classifier h X - [K] is function that maps feature to a label. We define the error rate of a single classifier f, and the disagreement and the tandem loss [MLIS20] between two classifiers, h and hi, the following:
Error rate : T(hh) Ep [1 (N(X) # Y)]
Disagreement: D(h, h/) Ep[1(((X) # R'(X))
Tandem loss L(h, h-) ( ())( #Y)].
where the expectation EE is used to denote ExX,Y\~. Next, we consider a distribution of classifiers,
which may be viewed as ensemble of classifiers. This distribution can represent variety of
different cases. Examples include: (1) a discrete distribution over finite number of h;, e.g., weighted sum of h,; and (2) distribution over parametric family he, e.g., distribution of classifiers resulting

---

from one or multiple trained neural networks. Given the ensemble p, the (weighted) majority vote ha p [K] is defined as
MV (x) = arg max Ep(1(1((x)= - -y]]-
vE[K]
Again, Ep denotes En-p, and we use Ep, Epg Pp for En-p, ("hh,,"">pp,,PPp..>> Ph-pp respectively, through- out the paper. In this sense, Bp (h)] represents the average error rate under distribution of classifiers p and (e (D(,, k/) represents the average disagreement between classifiers under p. Hereafter, we refer to [p)], EE, (D hh), and L(h, as the average error rate, the disagree- ment, and the majority vote error rate, respectively, with
L(hgr) = (h MV (X) xY].
Lastly, we define the point-wise error rate, W (xX,YY) Y), which will serve very important role in this paper (for clarity, will denote W,(X, , Y) by W unless otherwise necessary):
W p X, Y) = R (1 (h(X) *Y)-
2.2 Bounds on the majority vote error rate
The simplest relationship between the majority vote error Lh MV) and the average error rate Ep (h)] was introduced in [McA98]. It states that the error in the majority vote classifier cannot exceed twice the average error rate:
L( S (L)(L(())
A simple proof for this relationship can be found in [MLIS20] using Markov's inequality. Although (2) does not provide useful information in practice, is worth noting that this bound is, in fact, tight. There exist pathological examples where A. exhibits twice the average error rate (see Appendix C in [TKY+24]]. This suggests that the "fdrst-order" term, (h)].
hardly obtain useful tighter bound by relying only
Accordingly, more recent work constructed bounds in terms of "second-order" quantities, E [T,h,, h() and (D,,, W)). particular, [LMRR17] and [MLIS20] designed so-called C-bound using the Chebyshev-Camus Cantelll inequality, establishing that, if [E)) < 1/2, then
L( < E, [(h, M2) [L)] +
As an alternative approach, [MLIS20] incorporated the disagreement IE (D(, into the bound as well, albeit restricted to the binary classification problem, to obtain:
L(hbV) < 4E,[L(h)] 2E, (Dhh,
While (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 "good ensemble," and introducing the competence condition (see Definition 3 in our Appendix A). Informally, competent ensembles are those where it is more likely- average across the data-that more classifiers are correct than not, Based on this notion, [TKY+24] prove that competent ensembles are guaranteed have weighted majority vote error smaller than the weighted average error of individual classifiers:
LV < [L())-
(5)
That is, the majority vote classifier is always beneficial. Moreover, [TKY+24] proves that any competent ensemble p of K-class classifiers satisfy the following inequality.
L(NMV) S 4(K- 11)
[E,(L())
1 E,e [D(h, (D(h,
K
We 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.
3

---

3 The Polarization of an Ensemble
In this section, we introduce a new quantity, Tpp which we refer to as the polarization an ensemble p. First, we provide examples as what this quantity represents and draw connection previous studies. Then, we present theoretical and empirical results that show this quantity plays a fundamental role in relating the majority vote rate average emro rate and disagreement. In Theorem 1, prove an upper bound for the polarization Tpp, which highlights a fundamental relationship between the polarization and the constant 3. Inspired from the theorem, we propose Conjecture which we call neural polarization law. Figures and present empirical results image recognition task that corroborates the conjecture.
We start by defining the polarization of ensemble. In essence, the polarization is improved (smaller) coefficient on the Markov's inequality on (DW,, > 0.5), where W, is the point-wise error rate defined equation (1). It measures how much the ensemble is "polarized" from the truth, with consideration of the distribution of wp.
Definition (POLARIZATION). An ensemble is 7-polarized if
|E 2 PD > 1/2).
(7)
The polarization of an ensemble is
PD(W, > 1/2)
Mp
(8)
Ep|W?]
which is the smallest value of 1) satisfies inequality (7).
Note that the polarization always takes value in [0, 4]. due to the positivity constraint and Markov's inequality. Also note that ensemble p with polarization `i is 11-polarized for any 1j 2 ']p-
To understand better what this quantity represents, consider the following examples. The first example demonstrates that polarization increases 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 ensemble p where 75% of classifiers output Label with probability one, and the other 25% classifiers output Label 2 with probability one.
Case 1. The true label is Label I for the whole data.
this case, the majority vote in p results in zero error rate. The point-wise error rate W, is 0.25 on the entire dataset, and thus I' (W, 0.5) = O. The polarization Tpp is O.
Case 2. The true label is Label I 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 77p 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 p wrong on every data point. The point-wise error rate W is 0.75 on the entire dataset and thus PD(W) > 0.5) = 1. The polarization d) is 1 1/0.3125 3.2.
Example 2. the other 49% classifiers always output Label 2.
Now consider an ensemble p of which 51% % of classifiers always output Label 1, and
Case 1. The polarization ?, is now 0, the same as in Example 1.
Case 2. The polarization 7)p is 0.5/0.2500 2, which is larger than 1.6 in Example 1.
Case 3. The polarization 7) is now 1 /00.2501 R 4, which is larger than 3.2 in Example 1.
In addition, the following proposition draws 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 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 7p- The proof of Theorem deferred to Appendix I.

---

(a)
ResNet18 CIFAR-10
(b)
ResNet18 CIFAR-10.1
1.38
1.38
1.34
1.34
Polarization fl
OOD Polanizttio
1.32
1.30
1.30
1.26
126
1:44
0.075
0.100
0.125
0.150 0175 000 0225
0.175 200 0.255 0.5 o 0.275 0.300 o 0.225 o 0.350
Majority vote error rate
OOD Majority vote error rate
Non-interpolators
Interpolators
4/3
Figure 1: Polarizations obtained from ResNet18 trained on CIFAR-I0 with various sets of hyper-parameters tested (a) an out-of-sample CIFAR-10 and (b) out-of-distribution dataset, CIFAR-10.1, Red dashed line indicates y = 4/3, a suggested value of polarization appears in Theorem and Conjecture 1.
Theorem 1. Let {(x,, =. be independent and identically distributed samples from 'D that are independent of an ensemble p. Then the polarization the ensemble, 7p satisfies
4
8m
log 1
+
Sm
3
log 4SP
Up S max
(9)
3
25
with probability at least 1 where S 1 Em (X,,,, and P 1 Em 1(W Y;) 1/2).f
a appears to be a good choice for wide variety of cases. See Figure and Figure 2, which show the polarization 17p obtained from VGG11 [SZ14], DenseNet40 [HLVDMWT) 17], 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-of- distribution dataset, CIFAR-10.1 [RRSS18, TFF08). For more details on these empirical results, see Appendix C.
Surprisingly. in practice, "pp 4
Remark. We emphasize that values for Ωp that are larger than 3 does not contradict Theorem 1.
This happens when the non-constant second term in (9) is larger than 4 which is often the case for classifiers which are not interpolating (or, indeed, that underfit or perform poorly).
Definition 2 (INIERPOLATING, [BHMM19]. classifier is interpolating if achieves accuracy of 100% on the training data.
Putting Theorem and the consistent empirical trend shown in Figure 2(b) together, we propose the following conjecture.
Conjecture (NEURAL POLARIZATION LAw). The polarization of ensembles comprised of inde-
pendently trained interpolating neural networks is smaller than
Entropy-Restrictte Ensembles
In this section, we first present an upper bound on the majority vote error rate, L(h in Theorem using our notion of polarization To which we introduced and defined in the previous section. Then, we present Theorems and which are the main elements in obtaining tighter upper bounds on MV,. Figure 3 shows our proposed bound offers significant improvement over state-of-the-art results. The new upper bounds are inspired from the fact that classifier prediction probabilities tend to concentrate small number of labels, rather than be uniformly spread over all the possible labels.
5

---

(a)
Various architectures on CIFAR-10
(b)
Interpolating models on various datasets
1.33
1.34
(OOD) Polarization nla
1.30
Polarization Rl
1.28
y=4/3
1.30
VGG11
1.25
y=
DenseNet40
1:23
FMNIST
ResNet18
KMNIST
ResNet50
1.20
CIFAR-10
1.26
ResNet101
CIFAR-10.1
0.08
0.10
0.12
0.14
0.16
0.18
0.20
0.1
0.2 0.3
0.4
Majority vote error rate
(OOD) Majority vote error rate
Figure 2: Polarization 7)p obtained (a) from various architectures trained on CIFAR-10 and (b) only from interpolating classifiers trained various datasets. Red dashed line indicates y 4/3. In subplot (b), we observe that the polarization all interpolating models expect one are smaller than 4/3, which aligns with Conjecture 1.
This is analogous to the phenomenon of neural collapse [Kot22]. As example, in the context of a computer vision model, when presented with photo of a dog, one might expect that a large portion of reasonable models might classify the photo an animal other than dog, but not as a or an airplane.
We start by stating upper bound the majority vote error, L(h function of polarization "lo- 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,
[Kp(K 1)
[B][((h)] 1 (Dx,,
)(hMV)
K
where 11 is the polarization of the ensemble p.
Based on the upper bound stated Theorem 2, we add a restriction on the entropy of constituent classifiers obtain Theorem 3. The theorem provides 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 Appendix B.3.
Theorem 3. Let be any n-polarized ensemble of K-class classifiers that satisfies Pp Pp((x) & A(x)) s where y E A(x) C [] and |A(x) I for all data points (x, y) E D. Then, we have
L(NNV) < 2n(M 1))
[1+ M A) [x [E
M
While Theorem 3 might provide tighter bound than prior work, coming up with pairs (M, A) that satisfy the constraint is not easy task. This is not issue for discrete ensemble, however. If a discrete distribution of N classifiers, then we observe that the assumption of Theorem must always hold with (M, A) (N (,)), We state this as the following corollary.
Corollary (FINITE ENSEMBLE). For an ensemble that is weighted sum of N classifiers, we have
2n N+1
1 [D(h,(h,
L(M S
Ep(L(h) (D(,,
(10)
where Up is the polarization of the ensemble p.

---

(a)
CIFAR-10
(b)
CIFAR-10.1
Upper bounds L(h
Upper bounds L(hMg)
1.0
0.8-
0.6
0.6
0.4
0.4
0.2
0.2
0.10
0.15
0.20
0.25
0.30
0.175 0.000 0.225 250 0.775 0.300 0.325 0.350 OOD Majority vote error rate, L(h
Majority vote error rate, L(h
C-bound
[TKY+23] bound
Corollary bound
Maj.error (y=x)
Figure Comparing our new bound from Corollary (colored black), which the right hand side of inequality (10), with bounds from previous studies. Green corresponds to the C-bound in inequality (3), and blue corresponds to the right hand side inequality (6). ResNet18, ResNet50, ResNet101 models with various sets of hyperparameters are trained CIFAR-10 then tested (a) out-of-sample CIFAR-10, (b) an out-of-distribution dataset, CIFAR-10.1.
See Figure 3, which provides empirical results that compare the bound in Corollary with the C-bound in inequality (3), and with inequality (6) proposed [TKY* 24]. We can observe that the new bound in Corollary is strictly tighter than the others. For more details on these empirical results, see Appendix C.
Although the bound in Corollary is tighter than the bounds from previous studies, it's still not tight enough
estimator for L(h In the following theorem, we 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 n-polarized ensemble p that satisfies
ED [ (h(X) # Y, (X) * (X)(X) + (((x)) Se (b(x) Y)),
(1I)
we have
L(h s n E,(+)),([(h)) - | - (D
The condition (11) can be rephrased as follows: compared to the error P (h(h()) + y), the entropy of the distribution of wrong predictions is small, and it is concentrated on small number of labels. A potential problem that one must know or estimate smallest possible value of e advance. At K-2 least, we can prove that 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 Ty-polarized ensemble p of K-class classifiers, we have
L(M S
[(1+
2(K 11) E
K-2
- 10,
Naturally, this is not good enough for our goal. We discuss more on how to estimate the smallest possible value of the following section.
5 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 can obtain from an ensemble with small number, e.g., three,
7

---

of classifiers. Among the elements in the bound in Theorem 4,
7 E1) 1 1
(D N1]
we plug in r) 3 result of Theorem 1; and since [T.A]] is invariant the number of classifiers,
it remains predict the behavior of [D, h(]] and the smallest possible value of E, Ep
Eo (x))))=)
Since the denominator Ep [Po (h(X) * Ep(L(h)
28 (((())))))
is invariant to the number of classifiers, and the numerator resembles the disagreement between classifiers, Ep expected to follow similar pattern as E (h, h')]. Note that the numerator of Ep 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-sttatistic, as shown equation (12). In the next theorem, we show that the disagreement for finite number of classifiers can be expressed as the sum of a hyperbolic curve and an unbiased random walk. Here, [xx] denotes the greatest integer less than or equal to x and D(0, 1] is the Skorokhod space [0, 1] (sce Appendix B.5).
Theorem 5. Let PN denote an empirical distribution of N independent classifiers {h₃ [ sampled from a distribution p and of Var (B/nsPPPppp/a_ * h(()))). Then, there exists D such that
B >~pp' (D(h, 1') = (1 - 1/
Doo + 2
27N)
7N
VN
where EZN- = O, VarZx + of and ا 4NO converges weakly to a standard Wiener process in D(O, 1] as N 00.
Proof. Let D(s, h2) PP(()(() + (x)). We observe that
N2 E BUNNNOR (D),
PD (h: (x( hz()))
N(N
N(N
1,==1
N Σ md=1
2
(hi h2)
D(h; =: UN, (12)
N(N-
4: symmetric k(),,)))=0
N(N-) -1)
ISicjEN
which is a U-statistic with the kernel function +. Let On = (E, pr ((h, (h, h!).
The invariance principle of U-statistics (Theorem Appendix B.5) states that the process En (f), E [0, 1J). defined by (x( & N
k 2 NV (Ux - Po) and (t( = EN (1 converges weakly to standard Wiener process in D(0, 1] as N 00, since of = Varb~ (h, N/). Therefore, UN converges in probability as N - 0o to Doo == Do.
Letting ZI=OIÊN(1)=
V N -Ux-Dxo), we can express UN as UN - D 2 Zn. with EZN 0
VN
and Var oo. Since L [
=
Ni [ En
No
Et(t), it follows by Slutsky's Thcorem [
that { vi ZNoo)reeoo11 converges weakly standard Wiener process D(0, 1] as N -00.
Theorem suggests that the disagreement within N classifiers, Ezg, [D h(), can be approximated as N-1 Doo. From the disagreement within N) classifiers, D.o can be approximated as M
M E [D(h, h(),, and therefore we get
N M
Egg [D(h,)
M F,g, (D(,,)))-
(13)
N
Assume that we have three classifiers sampled from p. We denote the average enror rate, the disagreement, and the &, from these three classifiers by [T)],, E2 (Dh,, hi)], and 6a, respectively. Then, from Theorem 4 and approximation (13) (which applics to both disagreement and Ep),
8

---

(a1)
ResNet18 CIFARIO
(a2)
ResNet18 CIFARI0
ResNet18 CIFAR10.1
0.440
0.40
0.7
0.35
0.26
Error rates
0.150
0.30
Error rates
0.25
0.125
Erro
0.25
C-bound (leq. (2))
0.24
TKY+23 bound (leq. (5))
0.20
0.2
0.115
0110
0.15
0.2
0.105
0.10
021
of models
of models
of models
(c)
ResNet18 FMNIST
ResNet18 KMNIST
MobileNet MNIST
0.0033
0.058
0.024
0.0029
0.022
0.056
0.0028
Error rates
Error rates
0.020
Error rates
0.054
0.0027
0.018
0.052
0.0026
0.016
0.0025
0.044
0.0024
0.048
0.012
10
models
of models
of models
Avg. error
Est. Maj. error 4/3
Est. Maj. error w/ ==
Maj. error
Figure 4: Comparing the estimated (extrapolated) majority vote error rates in equation (14) (blue- dashed lines) and (15) (orange-dashed lines) with the true majority vote error (green solid line) for each number of classifiers. The solid sky-blue line corresponds to the average error rate of constituent classifiers. Subplots (al), (b), (c), (d), (e) show the results from different pairs of (classification model, dataset). Subplot (a2) overlays the right hand side of inequality (3) (C-bound, colored red) and inequality (6) ([TKY Y 24] bound, colored purple) on the subplot (al). These two quantities from previous studies much larger compared to the average error rate. We see the same pattern for other (architecture, dataset) pairs, which we therefore omit from the plot. For more details on these empirical results, Appendix C.
estimate the majority vote error rate of N classifiers from P as the following:
4
N -
3
N -
3 B. (D(,
L(hMV)
3
1
N
2
E3
E3 [g(L(h))
N
2 222
4
3(N
1)
1 [3BBa[(()]] E Est((
[s[L(h)]
(14)
3
2N
Alternatively, we can use the polarization measured from three classifiers, 77. instead of r = to obtain:
LONNV 1/3 [g[L(h)++ 3(N 3(N-1)
1) Eg (3B3s[LM) | D
(15)
2N
Figure 4 presents empirical results that compare the estimated (extrapolated) majority vote error rates in equations (14) and (15) with the true majority vote eтror for each number of classifiers. ResNet18 models are tested four different dataset: CIFAR-10. CIFAR-IO.1. Fashion-MNIST [XRV17] and Kuzushiji- -NIST [CBIK+ 18] where the models are trained on the corresponding train data. MobileNet [How 17] 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 the average error rate. This is also the case for (architecture, dataset) pairs of other subplots.

---

6 Discussion and Conclusion
This work addresses the question: how does the majority vote error rate change according to the number of classifier?? While this is an age-old question, it 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 Tpp, of an ensemble of classifiers. This notion plays an important role throughout this paper and appears in every upper bound presented. Although Theorem I gives some insight into polarization, our conjectured neural polarization law (Conjecture 1) is yet to exciting avenue for future work. (2) We proposed two
be proved or disproved, and it provides 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 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 metries 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 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, is worth considering whether the majority vote error rate is still as valuable. The natural alternative in this regard is the probability FWW, > 1/2), that is, the probability that at least half of the classifiers agree on the correct answer. This quantity is especially well- bell-behaved, and it frequently appears in our proofs. (Indeed, every bound presented in this work serves as an upper bound for IF,, (W, > 1/2).) We conjecture that this quantity is useful much more generally.
Acknowledgements. support of this work.
We would like thank the DOE, IARPA, NSF, and ONR for providing partial
References
[BHMM19] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnigg practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 156432):5544--1588 2019.
[Bil1]] Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, 2nd edition, 2013.
[BJRK22] Christina Baek, Yiding Jiang, Aditi Raghunathan, and Zico Kolter. Agreement-on the-line: Predicting the performance of neural networks under distribution shift. Advances in Neural Information Processing Systems, 35:19274-19288 2022.
[CBIK* 18] Tarin Clanuwat, Mikel Bober-Irizar Asanobu Kitamoto, Alex Lamb, Kazuaki Ya- mamoto, and David Ha. Deep learning for classical japanese literature. arXiv preprint 18/1v:/8/2.011 2018.
[Den12] Li Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-144 2012.
HLLDMW17] Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4700-4708, 2017.
[How17] Andrew G Howard. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv:1704.04861, 2017.
10

---

[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[JNBK22] Yiding Jiang, Vaishnavh Nagarajan, Christina Back, and J Zico Kolter. Assessing generalization of SGD via disagreement. In International Conference on Learning Representations. 2022.
[Kal21] Olav Kallenberg. Foundations of modern probability. Springer, 3rd edition, 2021.
[KB13] Vladimir S. Korolyuk and Yu V. Borovskich. Theory of U-statistics. Springer Science & Business Media, 2013.
[Kot22] Vignesh Kothapalli. Neural collapse: A review on modelling principles and general- ization, arXiv preprint arXiv:2206. 04041, 2022.
[Kri09] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[LMRR17] François Laviolette, Emilie Morvant, Liva Ralaivola, and Jean-France Roy. Risk upper bounds for general ensemble methods with an application to multiclass classi- fication. Neurocomputing, 219:15-25, 2017.
[LPB17] Balaji Lakshminarayanann, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems, 30, 2017.
[McA98] David A. McAllester. Some PAC-Bayesian theorems. Proceedings of the eleventh annual conference on Computational Learning T'heory, pages 230-234, 1998.
[MLIS20] Andrés Masegosa, Stephan Lorenzen, Christian Igel. and Yevgeny Seldin. Second order PAC-Baycsian bounds for the weighted majority vote. Advances in Neural Information Processing Systems, 33:5263-5273, 2020.
[RRSS18] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do CIFAR-10 classifiers generalize to CIFAR-10? arXiv preprint arXiv: /aoo:/000500 2018.
[SZ14] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1558: 2014.
TFF088
Antonio Torralba, Rob Fergus, and William T Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE transactions on Puttern Analysis and Machine Intelligence, 30(1 I): 1958-190,, 2008
[TK++24] Ryan Theisen, Hyunsuk Kim, Yaoqing Yang, Liam Hodgkinson, and Michael W. Mahoney. When are ensembles really effective? Advances in Neural Information Processing Systems, 36, 2024.
[XRV17] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST; novel im- age dataset for benchmarking machine learning algorithms. arXiv preprint wxXiv:1708.0774F 2017.

---

A More discussion on competence
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 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, (4)), The ensemble p competent for every 0 S//
PD(W, [/2) 2 PD [1/2, t)).
(16)
A.1 Cases when competence fails
One tricky part in the definition of competence is that it requires inequality (16) to hold for every 0 S t < 1/2. In case t 1/2, the incquality becomes
0 PD 1
This not a significant issue in the case that p continuous distribution over classifiers, e.g., a Bayes posterior or distribution over parametric family hag as (W, 1/2} would be a measure-zero set. In the case that p is discrete distribution over finite number of classifiers, however, P' (W, - 1/2) is likely to be positive quantity, in which case it can violate the competence condition.
That being said, {(x;, y) Wp y) = 1/2) represent tricky data points that deserves separate attention. This event be divided into two cases: 1) all the classifiers that incorrectly made 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(p, D):
TIE(P, D): ((x,)) (PP()) = (P((((()) = v)) = 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 p- weightt of classifiers. An easy way resolve this issue is to slightly tweak the weights. For instance, if p is an equally weighted sum of two classifiers, we can change each of their weights to be (1/2+ 42+e, e. 1/2 e), instead of (1/2, 1/2). This change may manipulative, but it corresponds tie-breaking rule which prioritizes one classifier over the other, which is a commonly used tie- breaking rule.
deterministic
Definition 4 (Tie-free ensemble). An ensemble is tie-free ifPD(TIE(p, D)) 0.
Proposition 2. An ensemble with a deterministic tie-breaking rule is tie-free.
With such tweak make the set TIE(p, D) to be empty set or measure-zero set, we present slightly milder condition that is enough for the bounds (5) and (6) to still hold.
Definition (Semi-compeeennce. The ensemble p is semi-competent for every 0 1//1/2
P(W, E 1/21 2 P(W, E (1/2,1-1))
(17)
Note that inequality (17) is a strictly weaker condition than inequality (16), and hence competence implies semi--coeeeee comiiccompetence. The converse is not true. An ensemble is semi-competent even if the point- wise error W, W, 1/2 every data points, but such ensemble is not competent.
Theorem 6. For tie-free ensemble and semi-competent ensemble p. L(hMV) I [,]](h)] and
4(K - 1) K
[EIL((M)- (D(h 1 |E,,D((hhh'))
L(
holds K-class classification setting.
We provide the proof as separate subsection below.
12

---

A.2 Proof of Theorem and Proposition
We start with the following lemma, which a semi-competence version of Lemma from [TKY+24] 24].
Lemma 1. For a semi-competent ensemble p and any increasing function g satisfying g(0) 0.
Enl((W,) 2 (Bll((,))) (, w,x1/2/
where W = 1 W
Proof. For every x E [0, 1]. it holds that
Pp(W,I,,si 21/2 2 x) = P E 1/2]] 1z11/2
PD 1 W <1/2 2 x) (W [x, 1/2)) L2g1/2 = PDW,, E (1/2,1
xi]) 1//21
From the definition of semi-competence, this implies that Po(W,Iw,5I)
x) N
Po 2 x) for every E [0, 1]. Using the fact that g( llase) g(r) for any increasing function g with g(0) 0, we obtain
(P w. w.s 2 x) PD(h(W,) w,<1/2 2 x))
Putting these together with well-known equality EX So PP 2 z)dr for non-negative random variable proves the lemma.
Now we use Lemma and Theorem 2 to prove Theorem 6.
Proof of Theorem 6. Applying Lemma with g(z) 2x² gives,
Mo 2 Ep|2W, / E2 4W, + +22
(18)
Putting this together with the following decomposition of IE [2W3)) shows that the ensemble is 2-polarized:
Ep [2 2 Ep[2W 1,2 22/2 5,,51/2]
> Ep|2w 120 + Epi(2 4W, 1w,)/
(18)
(19)
2 ED[(1 2W, ,) w,,1/2| (W, 1/2)
2 (W > 1/2).
Therefore, applying Theorem 2 with constant 7) concludes the proof.
also state the following proof of Proposition for completeness.
Proof of Proposition 1. Inequality (19) with Lemma proves the proposition.
A.3 Example that the bound (6) is tight
Here, we provide a combination of (p. D) of which L( is arbitrarily close to the bound.
Consider, for each feature æ, that exactly (1 e) fraction of classifiers predict the correct label, and that the remaining e fraction of classifiers predict wrong label. In this case, L(AMV) = 0,
E, [h)] = c, and E,2 [D(h, h-]] = 2c(1 <). Hence, the upper bound (6) is 4(K-1) which can be arbitrarily close to 0.
K
13

---

B Proofs of our main results
In this section, we provide proofs for our main results.
B.1 Proof of Theorem
We start with the following lemma which shows the concentration of linear combination of W I 1/2)-
p and
Lemma 2. For sampled data points {(x,, Y.) ~ D, define Z2 =
W E Y;) and
Zo = Ei i= (X,,(( > 1/2). The ensemble is n-polarized with probubility al least 5
max
34 1 log
(nZ2 Zo)
I
(20)
2m
Proof. Let Z2: - (X;, Yi) and Zo: - ( (X,, Yi) > 1/2). Observe that 1) Z2: - Zoi always
takes a value between [ - max { a 1--1111 since W (X,, Y,) E [o, 1]. This implies that 7) Zoi8
are i.idd. sub-Gaussian random variable with parameter
max 13/2.
By letting A2 = E/nW3 1(W, 2 1/22] and using the Hoeffding's 's inequality, we obtain
37 1} max
1 (nZ Zo) S m
4 log
2m
with probability at least 1 - 8. Therefore, is p7polarizedd with probability at least 1
5 if
max
3n
1
(n Zo) >
4
log 8"
2m
Now we use Lemma to prove Theorem 1.
Proof of Theorem 1. Observe that S = 1 Zz, P 1 Zo. and thus (1 - 2n) = n1S P. For
" _.4 the lower bound in Lemma 2 is simply
31, log }. and the inequality (20) can be viewed as Bm
a quadratic inequality in terms of vT. From quadratic formula, we know that
3n log
3n 8m
log 1/4 4SP
31 1
if
V
then n P
log
0.
25
8m
Putting this together with Lemma proves the theorem:
2
3. log 1 +
3. log 3 + 4SP
17 2
(21)
3
25
37 8mn
S
P
log
p is vy-polarized w.p. 1 - 5,
Lemma2
and thus the polarization Tp, the smallest such that is y-polarized, upper bounded by the right hand side of inequality (21).
B.2 Proof of Theorem
We start by proving the following lemma which relates the error rate of the majority vote, M(, with the pise error rate, W,, using Markov's inequality, In general, L(NMV) s P (w, 1/2) is true for any ensemble p. We prove tighter version of this. The difference between the two can be nen-negligible when dealing with an ensemble with finite number of classifiers. Refer to Appendix A.I and Definition& 4 for more details regarding this difference and tie-free ensembles.
14

---

Lemma 3. For a tie-free ensemble we have the inequality L(h S PD(W, 1/2).
Proof. For given feature x, W S 1/2 implies that more than or exactly p-weighted half of the classifiers outputs the true label. Since the ensemble p is tie-free, 1M outputs the true label
W - 1/2. Therefore, {<z, v) W, v) - 1/2] C ((,,)) hav (x) = = Applying PDD 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, Wr and the tandem loss, Epp (L(h, h")].
Lemma 4. The equality Ep 2 Exp (L h²) holds.
The next lemma appears as Lemma 4 in [TKY 24]. This lemma provides an upper bound on the tandem loss, E,,|L (L,,, h')] in terms of the average error rate, (,],(h)], and the average disagreement, E,p (D I²']
Lemma 5.
For the K K-class problem,
-(K-1) B,t[L(h,
Eg[L(()]] B,- (D,,
K
Now use these results to prove Theorem 2.
Proof of Theorem 2. Putting Lemmas 3, and and the definition of the polarization together proves the theorem:
PD > 1/2)
Tp ED W??
Lemma 3
polarization
2np 1)
1 En, 1o (D(h,,)))))))))
Tp Bpa [L(, 1t)]
Lemma
Lemma 5
K
B.3 Proof of Theorem 3
We start with lemma which is corollary of Newton's inequality.
Lemma 6. For any collection of probabilities Pl,....3 Pr, the following inequality holds.
2
n
P&P I
Σ
Pi
2n
Isijjnn
Proof. Newton's inequality states that
22
E1
where e1 =
and
e2
Σ 1gi<jšn
PiPj-
1=1
Rearranging the terms gives the lemma.
Now use this and the previous lemmas to prove Theorem 3.
Proof of Theorem 3. From Lemma 3, Lemma 4, and the definition of p-lolarizedd ensemble, we have the following relationship between L(MMV) and E, (L,h,hh))
L(
<
IP 1/2)
ED [W Lermaa
(22)
Lem.
7-polarized
From this, suffices to prove that h. E,2 (h, W/)] smaller than the upper bound the theorem. First, observe the following decomposition of E, [h,, h²)]:
E,2 (L,, R²)] Ep (Px( * r) Ep (x(X) * (h(X) # (X) =Y).
(23)
15

---

For any predictor mapping into K classes, let denote the true label for an imput Now we derive a lower bound of (h # Y, (X)) Y) using the following decomposition of oa (h(x) + ))))))::
1
2 (h)(h()) # (x)))
= (p)((((z) # sy, (2)) y) +
Σ
PiPjs
E
PiP
+
Σ
PiPj.
A()
AJEA(m))M)
jEA()\{b}
i<j
where p2 = pt)) = Pp(((x)) i). let A. Pp(h(x) & A(x)) and apply Lemma 6 to the last two terms:
P ( hl()))
2
= (p)(((x) # y, h(x)) =1) +) +)
Σ
PiPj + Σ PiPj
(JEA())))) K2
(.tA(()) .<
2(M - (1 (1-Py- - )²) + K-M-1 A2.
M 2
S (p((()) (x) v) + Ar Py A +
Lemma
2(K M)
Rearranging the terms and plugging 1-py = Pp(h(x) # y) gives
PP (h(x)) * Fv, = 9)
1
A.
M-2
2 (P()()) # (x)) M- Pp(M(x) + v)
Pp(M(()) + u)²
2(M 1)
K-1 A2
M)
AS
M-2
P (h(x)) # (((x)) 2
P Po(((T)) +v)
Pp(((()) + 4)
M
2(M -1)
A
M-2
I 2 (p(x)) # ((()))
(x(x)) *
TP, ()(xx)) + +1)²
M
2(M 1)
where the last inequality comes from the condition A. = P((h(x) & A(x)) < A. Putting this together with the equality (23) gives
ED (h(x))
S 1
ED (h(() # Y)] 2 Ep [ (b(X) ED [P)(h(X) #Y)
M-1
M 2
+
2(M - 1)
which implies
Exe (L(),)))) = ED [P, (b(X) + 2
$
1
1+
A
ED (p()(() # Y)]
ED (h(X) # [(X))]
M
M-1
1
A
1 Bap (p2 [E)((h)) -
M
M-1
Combining this with inequality (22) concludes the proof.
B.4 Proof of Theorem 4 and Corollary 2
First, we prove Theorem 4 by decomposing the point-wiss wise disagreement between constituent classi- fiers.
Proof Theorem 4. The following decomposition of PA, (h(x) + N'(x)) holds:
Ppp (h(x)) + h((x)) = (h(x) # v.)'(z) = = + 2222201 Pa (h(x) # y. hxx) y,h(()) + h())))
2
16

---

Applying Ep to both sides and using the given condition (11), we obtain,
2 Eo(Ppp(M()) + ((x)) & ED (Y,
Y)] + tEED)P + Y)).
The left hand side equals EE (h, h')], and the second term on the right hand side simply e P2 [T])]. Hence, the inequality above can be rephrased as follows:
R (D(1, [T( < DD PPpP) (X,
= v)]
(24)
Putting this together with the inequality (22) and the equality (23), gives
[(h Σ 17 E [L 1))
= 77 ED TP (1(()((()))))) + Y) - pA (h(x) * =Y,N(x)=
=
22
23
" [b]](()]] Ep (M() + -X,(()==
< 7 E1+))E, 1 [D(,
21
Next, we use Lemma to prove Corollary 2.
Proof of Corollary 2. Let == P,(h(x) i) for i E [K], and let y = K be the true label, without loss of generality. Then, we observe
K-1
K
Ppp XYMM
Σ
Paj
and (a(1(X) =
Σ pi
Lemma 6 gives us the following:
Eistejsk-1Pig PiPs
Ensusjsk-PPPp PiPs
Eistessk-PPiP PiPj (E
K-2
2 2
Lemma 2(K 1)²
where the first inequality used the fact that EKT Pi I 1. Thus, K-2 (II), and the result follows from Theorem
satisfies the condition
2(K-1)
B,5 Invariance principle of U-statistics
In this subsection, we state the invariance principle of Usstatistics, which plays a main role in the proof of Theorem 5. We note that this is special case of an approximation of random walks (Theorem 23. 14 [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 in [Bil13].
Theorem 7 (Theorem 5.2.1 in [KB13]). Define a U-statistic Us = -G)) "Eiskss (hi,, the expectation of the kernel + as to = ( (h,, and the first-coordinate variance of = Varn=o(gi(h)). where g1 (h) = B hi). Let En (tn, E [o, II), where
k
k(U 2o)
En
for 0-0, 1,
2
and (t) = ([nt)/nn) with [x]] denoting the greatest integer less than or equal to a. Then, &n converges weakly in D(0, 1) to a standard Wiener process as n - 50.
C Details on our empirical results
In this section, we provide additional details empirical results.
17

---

C.1 Trained classifiers
On CIFAR-I0 [Kri09] train set with size 50, 000, the following models were trained with 100 epochs, learning rate starting with 0.05. For models trained with learning rate decay. used learning rate 0.005 after epoch 50, and used 0.0005 after epoch 75. For following models, 5 classifiers are trained for each hyperparameter combination. Five classifiers differ in weight initialization and vary due to the randomized batches used during training.
ResNet18, every combination (width, batch size) of
Width:4, 8, 16, 32, 64, 128
Batch size: 16, 128, 256, 1024, with learning rate decay
Additional batch size of 64, 180, 364 for without learning rate decay
ResNet50, ResNet101, every combination (width, batch size) of
Width:8, 16
Batch size: 64, 256, without learning rate decay
VGG11, every combination (width, batch size) of
Width:16,
Batch size: 64, 256, without learning rate decay
DenseNet40, every combination (width, batch size) of
Width:5, 12,
Batch size: 64, 256, without learning rate decay
For models in Figure 4, more than 5 classifiers were trained. The classifiers differ in weight initialization and vary due to the randomized batches used during training.
ResNer18 on CIFAR-10, width 16 and batch size 64 without learning rate decay (20 classi- fiers)
The models below are trained with learning rate 0.05, momentum 0.9 and weight decay 5e-4 with cosine annealing.
MobileNet on MNIST, batch size 128 (10 classifiers)
ResNet18 on FMNIST, width 48 and batch size 128 (10 classifiers)
ResNet18 KMNIST, every combination of widths and batch sizes below (8 classifiers each)
Width: 48,66 64
Batch size: 32, 64, 128
C.2 Majority vote and tie-free For an ensemble with N classifiers, generated N uniformly-distribun random numbers e1.,,,yy E [0, 0.0001]. Then used + e + + ex) after normalization as weights for each classifier. This guarantees the ensemble be tie-free.
18

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Main claims made in the abstract and introduction accurately reflect the paper's contribution and scope.
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 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 include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
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 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 separate "Limitations" section 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 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
19

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
We provided the proof as clearly as possible.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Details are provided Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce
20

---

the model (e.g., with an spen-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Most of the experiments are straightforward to reproduce.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc)
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: https///ooeeobbieiooooeeeeeeeeee
/ //nips.cc///// cc htt.cccccpllcgguuue www.ic/ggiie///ee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Details provided in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
21

---

Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 accompanied by error bars, confi- dence 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.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 text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The experiment requires 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 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: ://p:://///erree http///nurrrp.ppeee http///uurrscccpuull/// cc/public//eieeccccccccccccceeee htw.hi//eehhcehieeelllelee
Answer: [Yes]
22

---

Justification:
The research conducted in this paper conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. 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 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 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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.
23

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets used in the paper are properly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode www.coo//aaaooooo com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]

---

Justification:
Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. 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 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 crowdsoureing nor research with human subjects.
Depending 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 expect authors adhere 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.
25


Reviews:
[{"review_id": "QvKC0Blt0p", "reviewer": "Reviewer_UfPx", "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.", "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$?).\n\nFor the experimental results shown in Figure 3, is it possible to plot some of the other bounds described in Section 2.2 for reference?\n\nThe ``#’’ sign shows up in an equation on line 131, which was not defined. Is this an error?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The work is well motivated and clearly presented. The authors show that the theorems they derive can be used to estimate the performance of large ensembles (although further validation of this would strengthen the paper, see weaknesses).", "weaknesses": "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.\n\nSome 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review of our paper; we greatly appreciate your comments and questions. \n\n[Weakness 1] Please see the general response: we hope that the newly presented form of Theorem 1 addresses your concerns. In the original wording, we state that an $\\eta$ greater than the stated lower bound is guaranteed. This is true, but one should pick the best possible $\\eta$ for the task, which is what the newly worded theorem now states. $4/3$ in the theorem mainly arises from Lemma 1, equation (9). The notable point is that the value $4/3$ aligns well with the empirical result as shown in Figure 1.\n\n[Weakness 2] Thank you for your comments. Please refer to Figure C on the figure document attached to the rebuttal for all reviewers above. On KMNIST, which is an easier task than CIFAR-10, ResNet18 with various width (48, 64) were trained with batch size (32,64,128) to interpolate the train data. On Fashion-MNIST, ResNet18 with width 48 was trained with batch size 128 to interpolate the train data.\n\n[Question 1] Lemma 2 states that the majority vote error rate is smaller than $P(W_\\rho > 1/2)$, the numerator term in the definition of polarity. If the error W_\\rho(X) is smaller than 0.5 for all datapoints in the test set, the equality holds and the majority vote error rate $= P(W_\\rho > 1/2) = 0$. This ensemble is $0$-polarized and thus $4/3$-polarized. We may have misunderstood your question. Could you explain a bit more about what you meant by 'small or large error regime (e.g. $\\epsilon$ or $0.5-\\epsilon$)'?\n\n[Question 2] We avoided overlaying those bounds (described in Section 2.2) as they are so far above the current set of axes that one cannot deduce the accuracy of our novel bounds. Please refer to Figure B in the figure document attached to the rebuttal for all reviewers above\n\n[Question 3] We used # as an indicator function 'f(A)=1 if A is true, otherwise 0'. For clarity, we will change this in the final version to a more common notation $1_A$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lFIgghGxbu", "reviewer": "Reviewer_ueod", "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.", "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. \n2. 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?\n3. 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": "Some limitations discussed in the conclusion section.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Overall, the paper is well-written, concise, and would be valuable to the wide audience working on predictive optimization and ensemble models.\n2. The use of the notion of polarity is novel and seems to capture two relevant properties simultaneously: (a) whether a large fraction of classifiers are making an incorrect prediction, and (b) whether the predictions of large groups of classifiers differ from each other. This characterization specially seems to assist in handling the presence of multiple classes as well. The conjectured upper bound on polarity is also independently interesting.  \n3. I liked the focus on entropy-restricted ensembles. The focus on ensembles with quantifiable “disagreement properties“ (as in Thms 3, 4) allows for stronger bounds on majority vote error rate, although it does seem difficult to then derive bounds for these “disagreement properties” (like the parameter $\\delta$). Nevertheless, the approach of bounding majority vote error rate using disagreement notions is intuitively appealing and, as the paper shows, it does provide reasonable theoretical bounds.", "weaknesses": "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.  \n\n2. 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.  \n3. 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive appraisal of our work!\n\n[Weakness 1] Please see the general response. Interpolators are models that are trained to perfectly fit the train data, and appear prominently in the double descent literature, as well as prior explorations into the benefits of ensembling. \n\n[Weakness 2, Question 1] Thank you for pointing this out. It is true that the empirical approximation converges to $\\eta$ itself. Here the bound becomes trivial with large $m$, as $\\eta$ is clearly bounded by the maximum of $4/3$ and itself. \n\nWe rephrased the theorem and conjecture and posted as a rebuttal for all reviewers above. We hope this clarifies the statement. Our conjecture follows from the observation that $P/S$ is less than $4/3$ (and hence $\\max\\{4/3, P/S\\}$) for interpolators. To prove this in the theory is a fascinating open problem for us.\n\n[Weakness 3, Question 2] We will add more implementation details to Appendix C in the final version. The constituent classifiers differ in weight initialization and vary due to the randomized batches used during training. We see that the number of classifiers we used (mostly 5) is specified in Appendix C.1, but please kindly let us know if you feel we missed something.\n\n[Question 3] Thank you for pointing this out. We will correct this in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f0tSE0n556", "reviewer": "Reviewer_CG1s", "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.", "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.\n\n2. 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.\n\n3. 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.\n\n4. In the definition of $\\mathcal{L}(h)$ in line 215, it appears that the symbol $h$ is overloaded.", "limitations": "Limitations are addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "As far as I am aware, the notion of an ensemble's polarity around which the paper is developed is a novel concept. The derived bounds based on polarity are stronger than previously known bounds and even subsume some of them, for example those based on the notion of competent ensembles.", "weaknesses": "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.\n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this paper; we really appreciate your comments and questions. \n\n[Weakness 1] We agree that further empirical evidence would strengthen our claim. It is difficult to obtain an ensemble of well-trained interpolating models in practice, so we are limited in our selection of models and datasets. For now, we provide further evidence of the universality of $\\eta<4/3$ on two additional datasets in the figure document: KMNIST and Fashion-MNIST. Please refer to Figure A on the figure document attached to the rebuttal for all reviewers above.\n\nOn KMNIST, which is an easier task than CIFAR-10, ResNet18 with various width (48, 64) were trained with various batch size (32,64,128) to interpolate the train data.\nOn Fashion-MNIST, ResNet18 with width 48 was trained with batch size 128 to interpolate the train data. \n\n[Weakness 2, Question 3] The main role of Theorem 5 is to justify our approximation of the entire disagreement curve by neglecting $N^{-1/2}Z_N$. If we used a ordinary central limit theorem, we could only justify approximations of $D_n$ for large $n$. Appealing to Donsker's invariance principle, we can justify our procedure of extrapolating the disagreement as $D_n = D_3 * (1-1/n)/(1-1/3)$.\n\nIn this case, $\\sigma^2$ is equal to $Var_{h\\sim\\rho}(L(h))$. We will update this in the final version along with the typo on the $U_N$ Hoeffding decomposition in Line 214 where $E_{\\rho_N^2}$ should be $E_{\\rho^2}$ instead.\n\n[Question 1] We rephrased the theorem and conjecture and posted as a rebuttal for all reviewers above. We hope this clarifies the statement. \n\n[Question 2] Perhaps it is only at an intuitive level, but we see neural collapse and reduced entropy on the probabilities as symptoms of the same general phenomenon. If the representations within each class are reduced to a single point, then a classifier ensemble is going to become increasingly confident within each class, as there is less variability in the outputs.\n\n[Question 3] Answered with Weakness 2 above.\n\n[Question 4] Thank you for pointing this out. We will update this to $\\mathcal{L}(h)=\\mathbb{E}\\_{h'\\sim\\rho}\\mathbb{P}\\_{\\mathcal{D}}(h(X)\\neq h'(X))-\\mathbb{E}\\_{(h',h'')\\sim\\rho^2}\\mathbb{P}\\_{\\mathcal{D}}(h'(X)\\neq h''(X))$ in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5ZrEsxTbpq", "reviewer": "Reviewer_2Qk3", "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.", "questions": "QUESTIONS\n\n* How do the authors define *interpolating* neural networks in this work?\n* Can the authors please expand on the point raised in W5?\n\nSUMMARY OF THE REVIEW\n\nThis 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": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Section 2 is, by in large, excellent, and does a very good job of summarizing the existing work in this area.\n2. The concept of polarity is clearly defined and well supported via the helpful example in Fig. 1.\n3. The tighter bounds in Sec. 4 are well-described and scoped.", "weaknesses": "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.\n2. 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\n3. Equation (6) appears to have a formatting error, there's a long underscore under one half of the equation\n4. 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.\n5. \"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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this paper and we really appreciate your comments and questions. \n\n[Weakness 1] Agreed. That was the reason why we narrowed down the scope to interpolating models in Conjecture 1 although Theorem 1 holds for any ensemble. We think it would be an interesting direction to see how $\\eta$ differs in non-interpolating models in different fields (e.g. language models). \n\n[Weakness 2] Thank you for catching this. We will fix this in the final version. \n\n[Weakness 3] The long underscore is due to the footnote below the formula.\n\n[Weakness 4, Question 1] Please see the general response: \"interpolator\" is a model that is trained to perfectly fit the train data. In Conjecture 1, we wanted to draw a statement analogous to so-called 'neural scaling laws', which states that the out-of-sample performance of an interpolating neural network scales with the width of the neural net. We will add a paragraph about this on the final version.\n\n[Weakness 5, Question 2] In Theorem 5, we prove that the disagreement for $N$ classifiers has a representation as $(1-1/N)(D_\\infty + N^{-1/2}Z_N)$, and through Donsker's invariance principle, it can be approximated through the disagreement of a smaller number of classifiers (say $M$) as $(1-1/N) / (1-1/M) * (\\text{Disg. of }M\\text{ classifiers})$. The justification for this argument is that the disagreement is a $V$-statistic, and so its bias can be accounted for. The same is true for the numerator of $\\delta$ (the denominator is unbiased): it is also a $V$-statistic, and should behave similarly to the disagreement, as its form is the same with only one less label. We will add this clarification in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
As there are overlapping comments regarding Theorem 1 and Conjecture 1, we provide clarification and a rephrased version of the theorem and conjecture here. Firstly, for Theorem 1, we recognize that the current wording may be misleading, so we reword the theorem in the following way for clarity:

Theorem 1: Letting $$\eta = \max\left\\{ \frac{4}{3},\left(\frac{\sqrt{\frac{3}{8m}\log\frac{1}{\delta}}+\sqrt{\frac{3}{8m}\log\frac{1}{\delta}+4SP}}{2S}\right)^{2}\right\\}$$, the ensemble $\rho$ is $\eta$-polarized with probability at least $1-\delta$.

No modifications to the proof are necessary, as this is simply a restatement of the finding obtained at the end of the proof. 

Definition of Interpolator, Interpolating: We define a neural net (or any other type of model) as an interpolator and say it is interpolating if it is trained to exactly fit the training data, i.e. $L_{train} = 0$. This term was recently popularized in Belkin et al.'s paper, "Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-Off", which we now cite.

Conjecture 1: An ensemble $\rho$ comprised of independently trained high-performing interpolating neural networks is $\eta$-polarized for $\eta \leq 4/3$. 

As some reviewers have pointed out, the previous wording suggested that interpolating neural network ensembles were $\eta$-polarized for $\eta$ precisely equal to $4/3$ and no lower. To clarify, we are asserting that $4/3$ suffices, as evidenced by Figure 1, which highlights that estimates for polarity (that is, $P/S$) are consistently below $4/3$ for interpolating models. We also wish to add that the "high-performing" moniker should be necessary here to ensure that $P$ is not too large in general.

Meta-review: 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.
Decision: Accept (poster)