When are ensembles really effective?
Authors: Ryan Theisen
Hyunsuk Kim
Yaoqing Yang
Liam Hodgkinson
Michael W. Mahoney
Venue: NeurIPS 2023 poster (2023)
Keywords: Ensembling
theory
deep learning

Abstract: Ensembling has a long history in statistical data analysis, with many impactful applications. 
However, in many modern machine learning settings, the benefits of ensembling are less ubiquitous and less obvious. 
We study, both theoretically and empirically, the fundamental question of when ensembling yields significant performance improvements in classification tasks. 
Theoretically, we prove new results relating the \emph{ensemble improvement rate} (a measure of how much ensembling decreases the error rate versus a single model, on a relative scale) to the \emph{disagreement-error ratio}. 
We show that ensembling improves performance significantly whenever the disagreement rate is large relative to the average error rate; and that, conversely, one classifier is often enough whenever the disagreement rate is low relative to the average error rate. 
On the way to proving these results, we derive, under a mild condition called \emph{competence}, improved upper and lower bounds on the average test error rate of the majority vote classifier.
To complement this theory, we study ensembling empirically in a variety of settings, verifying the predictions made by our theory, and identifying practical scenarios where ensembling does and does not result in large performance improvements. 
Perhaps most notably, we demonstrate a distinct difference in behavior between interpolating models (popular in current practice) and non-interpolating models (such as tree-based methods, where ensembling is popular), demonstrating that ensembling helps considerably more in the latter case than in the former.

When are ensembles really effective?
Ryan Theisen Department of Statistics University of California, Berkeley theisen@berkeley, edu
Hyunsuk Kim Department Statistics
University of California, Berkeley hyskin7@berkeeey edu
Yaoqing Yang
Liam Hodgkinson
Department of Computer Science Dartmouth College
School of Mathematics and Statistics
University of Melbourne, Australia
Yaoqing Yang@dartmuuth. edu
Lhodgkinson@umimell edu.
Michael W. Mahoney
International Computer Science Institute Lawrence Berkeley National Laboratory and Department of Statistics University of California, Berkeley mmahoney@stat. berkeley edu
Abstract
Ensembling has a long history statistical data analysis, with many impactful applications. However, in many modern machine learning settings, the benefits ensembling are less ubiquitous and less obvious. We study, both theoretically and empirically, the fundamental question of when ensembling yields significant performance improvements classification tasks. Theoretically, we prove new results relating the ensemble improvement rate (a measure of how much ensem- bling decreases the error rate versus a single model, on a relative scale) to the disagreement-error ratio. We show that ensembling improves performance signifi- cantly whenever the disagreement rate is large relative to the average error rate; and that, conversely, one classifier is often enough whenever the disagreement rate is low relative to the average еттог rate. On the way to proving these results, we derive, under a mild condition called competence, improved upper and lower bounds on the average test еттоr rate of the majority vote classifier. To complement this theory, we study ensembling empirically in variety of settings, verifying the predictions made by our theory, and identifying practical scenarios where ensembling does and does not result in large performance improvements. Perhaps most notably, we demonstrate distinct difference in behavior between interpolating models (popu- lar current practice) and non-interpolating models (such as tree-based methods, where ensembling is popular), demonstrating that ensembling helps considerably more the latter case than in the former.
Introduction
The fundamental ideas underlying ensemble methods can be traced back at least two centuries, with Condorcet's Jury Theorem among its earliest developments [Con85]. This result asserts that if each juror on a jury makes a correct decision independently and with the same probability p > 1/2, then the majority decision of the jury is more likely to be correct with each additional juror. The general principle of aggregating knowledge across imperfectly correlated sources intuitive, and it has motivated many ensemble methods used in modern statistics and machine learning practice. Among
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

these, rree-based methods like random forests [Bre01] and XGBoost [CG16] are some of the most effective and widely-used.
With the growing popularity of deep learning, a number of approaches have been proposed for ensembling neural networks. Perhaps the simplest of them are so-called deep ensembles, which ensembles of neural networks trained from independent initializations [ABP* 22, ABPC22, FHL19]. In some cases, it has been claimed that such deep ensembles provide significant improvement in performance [FHL19, OFR 19, ALMV20J. Such ensembles have also been used to obtain uncertainty estimates for prediction [LPB17] and to provide more robust predictions under distributional shift. However, the benefits of deep ensembling are not universally accepted. Indeed, other works have found that ensembling is less necessary for larger models. and that some cases a single larger model can perform as well as ensemble of smaller models [HVD* 15, BCNM06, GJS 20, ABP*22]. Similarly mixed results, where empirical performance does not conform with intuitions and popular theoretical expectations. have been reported in the Bayesian approach to deep learning [INLW21]. Furthermore, an often-cited practical issue with ensembling, especially of large neural networks, is the constraint of storing and performing inference with many distinct models.
In light of the increase in computational cost, it is of great value understand exactly when we might expect ensembling to improve performance non-trivine non-trivially. In particular, consider the following practical scenario: a practitioner has trained single (perhaps large and expensive) model, and would like to know whether they can expect significant gains in performance from training additional models and ensembling them. This question lacks a sufficient answer, both from the theoretical and empirical perspectives, and hence motivates the main question of the present work:
When are ensembles really effective?
The present work addresses this question, both theoretically and empirically, under very general conditions. We focus our study on the most popular ensemble classifier-the majority vote classifier (Definition 1), which we denote by haav-although our framework also covers variants such weighted majority vote methods.
Thcoretical results. Our main theoretical contributions, contained in Section 3, are as follows. First, we formally define the ensemble improvement rate (EIR, Definition 3), which measures the decrease in error rate from ensembling, on a relative scale. We then introduce new condition called competence (Assumption 1) that rules out pathological cases, allowing us to prove stronger bounds on the ensemble improvement rate, Specifically, 1) we prove (in Theorem 1) that competent ensembles can never hurt performance, and 2) we prove (in Theorem 2) that the EIR can be upper and lower bounded by linear functions of the disagreement-ervon ratio (DER, Definition 4). Our theoretical results predict that ensemble improvement will be high whenever disagreement is large relative to the average error rate (i.e., DER> > 1). Moreover, we show (in Appendix A.3) that as Corollaries of our theoretical results, we obtain new bounds on the error rate of the majority vote classifier that significantly improve on previous results, provided the competence assumption is satisfied.
Empirical results. In light of our new theoretical understanding of ensembling, we perform a detailed empirical analysis of ensembling in practice. In Section 4, we evaluate the assumptions and predictions made by the theory presented in Section 3. In particular, we verify on variety of tasks that the competence condition holds, we verify empirically the linear relationship between the EIR and the DER, as predicted by bounds. In Section 5, we provide significant evidence for distinct behavior arising for ensembles in and out of the "interpolating regime," i.c., when each of the constituent classifiers in an ensemble has sufficient capacity to achieve zero training error. We show 1) that interpolating ensembles exhibit consistently lower ensemble improvement rates, and 2) that this corresponds to ensembles transitioning (sometimes sharply) from the regime DER 1 to DER < 1. Finally, we also show that tree- based ensembles represent a unique exception to this phenomenon, making them particularly well-suited ensembling.
In addition to the results presented in the main text, we provide supplemental theoretical results (including all proofs) in Appendix A, as well as supplemental empirical results in Appendix B.

---

2
Background and preliminaries
In this section, we present some background as well as preliminary results of independent interest that set the context for our main theoretical and empirical results.
2.1 Setup
In this work, we focus on the K-class classification setting, wherein the data (X,Y) x consist of features a e X' and labels y y = (1...., K}. Classifiers are then functions h: X' - y that belong some set H. To measure the performance of single classifier h on the data distribution D, we use the usual error rate:
= -x())=Exxx-(((((((() + Y)
For notational convenience, we will drop the explicit dependence on 'D whenever it is apparent from context.
central object in our study is a distribution p over classifiers. Depending on the context, this distribution could represent variety of different things. For example, p could be:
i) A discrete distribution finite of classifiers (l1...., har) with weights fl,...,PM e.g.. representing normalized weights a weighted ensembling scheme;
ii) A distribution parameters 0 of parametric family of models, he, determined, e.g., by stochastic optimization algorithm with random initialization;
ii) A Bayesian posterior distribution.
The distribution p induces two error rates of interest. The first the average error rate of any single classifier under defined to be [A))] The second is the error rate of the majority vote classifier, NMV, which defined for a distribution p as follows.
Definition 1 (Majority vote classifier), Given p. the majority vote classifier is the classifier which, for an input æ, predicts the most probable class for this input among classifiers drawn from p.
hMv(#) arg max En-p[1(h(2)) =]]]
j
In the Bayesian context, p= p(h Xuain Yrain) a posterior distribution over classifiers. In this case, the majority vote classifier is often called the Bayes classifier, and the error rate L(hav) is called the Bayes error rate. such contexts, the average error rate often referred to as the Gibbs error rate associated with p and DD
Finally, we will present results terms of the disagreement rate between classifiers drawn from distribution p. defined as follows.
Definition (Disagreement), The disagreement rate between two classifiers h h/ given by Do (h, h = E x (h(X) # h'(X))). The expected disagreement rate is Eh.N-p(DDi (h, h()], where h, h P are drawn independently.
Remark 1. We focus on the case of classification with the 0/1 loss for few reasons. First, this scenario represents a significant portion of the practical uses of ensembling. Moreover, it also presents the greatest challenge from technical perspective, when compared to convex loss functions such as cross entropy, in which case Jensen's inequality immediately implies improvement from ensembling, or regression with squared error, in which case precise analytical results are more easily obtained (see Remark 3 for an example).
2.2 Prior work
Ensembling theory. Perhaps the simplest general relation between the majority vote error rate and the average error rate guarantees only that the majority vote classifier is worse than twice the average error rate [LMRRI] 17, MLIS20J. To see this, let W, = W,(X, denote the proportion of erroneous classifiers in the ensemble for a randomly sampled input-output pair (X,Y)= D. and note that [[[, E[]( Then, by a "first-order" application of Markov's inequality, have that
[I=p[[((((]) Y)]
0 L(hxv) s SP(W, 1/2) 2 2 Em [Lh]]]
(1)
3

---

This bound is almost always uninformative in practice. Indeed, it may seem surprising that an ensemble classifier could perform worse than the average of its constituent classifiers, much less a factor of two worse. Nonetheless, the first-order upper bound is, in fact, tight: there exist distributions p (over classifiers) and D (over data) such that the majority vote classifier is twice as erroneous as any one classifier, on average. As one might expect, however, this tends to happen only in pathological cases; we give examples of such ensembles in Appendix C.
To circumvent the shortcomings of the simple first-order bound, more recent approaches have developed bounds incorporating "second-order" information from the distribution P [MLIS20].
One successful example of this is given by class of results known as C-bounds [GLL*15 15, LMRRI7J. The most general form of these bounds states, provided E[M,(X, Y)] > 0, that L(hNv) $ - (X,, (EEM)))
where Mp (X(X,Y) = [ = Y)] m Ei- [ (1(h(x)=)))))))))))))) -)] is called the margin. In the binary classification case, the condition 1/2. Hence, it can be viewed as requirement that individual classifiers are "weak learners." " The same condition is used to derive a very similar bound for random forests in [BreO1]. which is then further upper bounded to obtain more intuitive (though weaker) bound in terms of the "c/s2" ratio. Relatedly, [MLIS20] obtains a bound on the error rate of the majority-vote classifier, in the special case of binary classification, directly in terms of the disagreement rate, taking the form 4E[ [E(]] 2E[ k')]. We note that our theory improves this bound by factor of (see Appendix A.3). Other results obtain similar expressions, but in terms of different loss functions, e.g., cross-entropy loss [ABP*22, OCnM22).
E[M, (X, Y)] is equivalent to the assumption Et--[[(())
Other related studies. In addition to theoretical results, there have been a number of recent empirical studies investigating the use of ensembling. Perhaps the most closely related is [ABPC22], which shows, perhaps surprisingly, that ensembles do not benefit significantly from encouraging diversity during training. In contrast the present work, [ABPC22] focuses on the cross entropy loss for classification (which facilitates somewhat simpler theoretical analysis), whereas we focus on the more intuitive and commonly used classification error rate. Moreover, while [ABPC22] study the ensemble improvement gap (i.e., the difference between the average loss of a single classifier and the ensemble loss), we focus on the gap in error rates on a relative scale. As we show, this provides much finer insights into ensembles improvement. To complement this, [FHL.19] study ensembling from a loss landscape perspective, evaluating how different approaches to ensembling, such as deep ensembles, Bayesian ensembles, and local methods like Gaussian subspace sampling compare in function and weight space diversity. Other recent work has studied the use of ensembling to provide uncertainty estimates for prediction [LPB 17], and to improve robustness to out-of-distribution data [OFR* 19], although the ubiquity of these findings has recently been questioned in [ABP*22].
3 Ensemble improvement, competence, and disagreement-error ratio
In this section, our goal is to characterize theoretically the rate which ensembling improves performance. To do this, we first need to formalize a metric to quantify the benefit from ensembling. One natural way of measuring this improvement would be to compute the gap E [ - L(huv) ). A similar gap was the focus of [ABPC22], although in terms of the cross-entropy loss, rather than the classification error rate. However, the unnormalized gap can be misleading- will tend to be small whenever the average error rate itself is small, thus making it impractical to compare, e-g., across tasks of varying difficulty. Instead, we work with a normalized version of the average-minus-ensembe error rate gap, where the effect of the normalization is to measure this error in relative scale. We call this the ensemble improvement rate.
partieular,
Definition 3 (Ensemble improvement rate). Given distributions P over classifiers and D over data, provided that En-p[L(h)) # O, the ensemble improvement rate (EIR) is defined as
Em-pl [Lh]]][(h]] -(hD)))
EIR
Ex-p[L(h))
In contrast to the unnormalized gap, the ensemble improvement rate can be large even for very easy tasks with small average error rate. Recall the simple first-order bound on the majority-vote classifier: L(hmv) I 2E([(h) Rearranging, we deduce that EIR -1. Unfortunately, in the absence of additional information, this first-order bound is in fact tight: one can construct ensembles for this T.(hMv)= = 21 2f[]. (see Appendix C). However, this bound is inconsistent with how ensembles generally behave and practice, and indeed it tells us nothing about when ensembling can

---

improve performance. In the subsequent sections, we derive improved bounds on the EIR that can provide such insight.
3.1 Competent ensembles never hurt
Surprisingly, to our knowledge, there is no known characterization of the majority-vote eroor rate that guarantees it be worse than the rate of any individual classifier, on average. Indeed, turns out this is the result of strange behavior that can arise for particularly pathological ensembles rarely encountered practice (see Appendix C for more detailed discussion of this). To eliminate these cases, we introduce mild condition that we call competence.
Assumption 1 (Competence), Let W, = WYX,,Y) (n-)([(((XX) Y)]. The ensemble p competent if for every 0 s t 1/2,
P(W, [t, P(W,, e [1/2,1-t]).
The competence assumption guarantees that the ensemble is pathologically had, and in particular eliminates the scenarios under which the naive first-order bound (1) tight. As we will show in Section 4, the competence condition is quite mild, and it holds broadly in practice. Our first result uses competence to improve non-trivially the naive first-order bound.
Theorem 1. Competent ensembles never hurt performance, i.e., EIR 0.
Translated into bound on the majority vote classifier, Theorem guarantees that T.(havv s {F(] improving on the naive first-order bound (1) by a factor of two. To the best of our knowledge, the competence condition is the first of its kind, in that it guarantees what is widely observed in practice, ie., that ensembling cannot hurt performance. However, how much ensembling can improve performance. To address this question, we turn to a "second-order" analysis involving the disagreement rate.
insufficient to answer the question of
3.2 Quantifying ensemble improvement with the disagreemeenterroo ratio
Our central result in this section will be to relate the EIR to the ratio of the disagreement to average error rate, which we define formally below.
Definition 4 (Disagreement-errro ratio). Given the distributions over classifiers and D over data, provided that En [.(h)] the disagreement-erro ratio (DER) defined as
EnM-pl ((h,
DER
Ex [[h)]
Our next result relates the EIR a linear function of the DER.
Theorem 2. For any competent ensemble of K-class classifiers, provided [n-p[[(h)] + 0, the ensemble improvement rate satisfies
-(K- K
3K
DER 2 EIR 2
DER
K
Note that neither Theorem 1 Theorem 2 is uniformly stronger. In particular, if DER (3K - 4)/(2K - 2) then the lower bound provided in Theorem will be superior to the one in Theorem 2.
Theorem predicts that the EIR fundamentally governed by a linear relationship with the DER result that will verify empirically in Section 4. Importantly, note that there regimes in which the bounds Theorem provide non-trivial guarantees.
distinet
DER small (< 1). this case, by the trivial bound (1), EIR 1, and thus the upper bound in Theorem 2 guarantees ensemble improvement cannot be too large whenever DER < 1, that is, whenever disagreement small relative to the average error rate.
DER large (> 1). In this case, the lower bound in Theorem 2 guarantees ensemble improvement whenever disagreement sufficiently large relative average error rate, in particular when DER > (3K- 4)/(2K - 2 1.
5

---

In our empirical evaluations, we will see that these two regimes (DER > 1 and DER 1) strongly distinguish between situations in which ensemble improvement is high, and when the benefits of ensembling are significantly less pronounced.
Moreover, Theorem captures an important subtlety in the relationship between ensemble improve- ment and predictive diversity. In particular, while general intuition-and significant body of prior literature, as discussed in Section 2- suggests that higher disagreement leads to high ensemble improvement, this may not be the case if the disagreement is nominally large, but small relative to the average error rate.
Remark 2 (Corollaries of Theorems 1 and 2). Using some basic algebra, the upper and lower bounds presented in Theorems 1 and 2 can easily be translated into upper and lower bounds on the error rate of the majority vote classifier itself. For the sake of space, defer discussion of these Corollaries Appendix A.3, although we note that the resulting bounds constitute significant improvements on existing bounds, which we verify both analytically (when possible) and empirically.
Remark 3 (Relation to the regression case). We remark that the bounds in Theorem 2 share direct (and simpler) analogue the regression case with the squared error loss. In this case, a bias-variance decomposition (taken over randomness arising from the sampling of a regressor f p) yields the identity:
Ey-oL4())] = L(F) + (xxx[VVs-LL(X
where here the ensemble regressor is f(xx) = 5=-=)(((a))) and V[J is the variance. Normalizing, obtain the identity
EIR -f-o[4())) Ex-DIVy-p(((X))) [L-)[((f)]
[x-p[[(f)]
where the latter variance-average error ratio is a natural analogue to the DER. Note also since the variance is non-negative, this expression immediately implies that EIR 0 in the regression case. See Appendix A.4 for a derivation.
4 Evaluating the theory
In this section, we investigate the assumptions and predictions of the theory proposed in Section 3. In particular we will show 1) that the competence assumption holds broadly in practice, across range of architectures, ensembling methods and datasets, and 2) that the EIR exhibits a close linear relationship with the DER, as predicted by Theorem 2.
Before presenting our findings, we first briefly describe the experimental settings analyzed in the remainder of the paper. Our goal is to select sufficiently broad range of tasks and methods so as to demonstrate the generality of our conclusions.
4.1 Sctup for empirical evaluations
In Table I we provide a brief description of our experimental setup; more extensive experimental details can be found in Appendix B.I.
Table 1:
Datasets and ensembles used in empirical evaluations, where denotes the number of classes, and M
denotes the number of classifiers.
Datasets
Ensembles
Dataset
Reference
Base classifier
Ensembling
Reference
MNIST (5K subset)
10
[Den
ResNNer20-Swish
Bayesian Ens.
100
[VHW22]]
CIFAR-10
10
[KH 09]
ResNet18
Deep Ens.
5
[KH*09]
IMDB
2
[MDP* 11]
CNN-LSTM
Bayesian Ens.
100
[IVIW21]]
QSAR
[BGCT19]
BERT (fine-tune)
Deep Ens.
IDCIT19,
Thyroid
[QCHL87]
Random Features
Bagging
N/A
GLUB (7 tasks)
[WSM" 19]
Decision Trees
Random Forests
100
[PVG' 11, Bre01]
4.2
Verifying competence in practice.
Our theoretical results in Section 3 relied on the competence condition. One might wonder whether competent ensembles exist, and if so how ubiquitous they are. Here, we test that assumption. (That is, we test not just the predictions of our theory, but also the assumptions of our theory.)

---

Farestss
Random Thyroid
Bandom Fealures
Random Pestures
CNN-LSTM/MDD (bayes)
DINNW20NCIPAR111 (aayes)
MNNIS
AW, 122)
68
E11, 1-12,,1100 1-0
64
044
54
02
24
Figure 1: Verifying the competence assumption in practice. W,(X,Y) in Assumption is estimated using hold-out data. Across all tasks,
supporting Assumption 1.
We have observed that the competence assumption is empirically very mild, and that in practice applies very broadly. In Figure 1, we estimate both P(W, E [t, 1/2)) and P(W, E [1/2, tJ) on test data, validating that competence holds for various types of ensembles across subset of tasks. To do this, given test set of examples { 1;) and classifiers h hy drawn from p. construct the estimator
N W P
1
Σ n=1
1(hn (2,) + yz),
N
and we calculate P(W, e [t,1/2)) and P(W, [1/2, 1 1)) from the empirical CDF of (W y- In Appendix B, provide additional examples of competence plots across more experimental settings (and we observe substantially the same results).
4.3 The linear relationship between DER and FIR.
Pandd UNIST L-bendaa no0t
Theorem 2 predicts a linear relationship between the EIR and the DER; here we verify that this relationship holds empirically. In Figure 2, we plot the ETR against the DER across several experimental settings, varying capacity nyper-parameters (width for the ResNet18 models, number of random features for the random feature classifiers, and number of leaf nodes for the random forests), reporting the equation of the line of best fit, as well as the Pearson correlation between the two metries. Across of the 8 experimental settings evaluated, we find a very strong linear relationship with the Pearson R 2 0.96. The two exceptions are found for the Thyroid classification dataset (though there is still a strong trend between the two quantities, with R x 0.8).
2012
Duskato: GE333
(Lovoza 1.00--10 Done,
655
Backi Desure copnal
So-77e 26 wodel
DER
Figure 2: EIR is linearly correlated with the DER. We plot the EIR against the DER across variety of experimental settings, and observe a close linear relationship between EIR and DER, as predicted by our thcoretical results. In the legend, we also report the equation for the line of best fit within each setting, as well as the Pearson correlation.
Interestingly, we can compare the lines of best fit to the theoretical linear relationship predicted by Theorem 2. In the case of the binary classification datasets (QSAR and Thyroid), the bound predicts that EIR æ DER- FER-1; while for the 10-class problems (MNIST and CIFAR-
10), the equation is EIR & 1.8 DER - 2.6. While for some examples (e.g., random forests on MNIST), the equations are close to those theoretically predicted, there is a clear gap between theory and the experimentally measured relationships for other tasks. In particular, we notice significant difference in the governing equations for the same datasets between random forests and the random feature ensembles, suggesting that the relationship is to some degree modulated by the model architecture something our theory cannot capture. We therefore see refining our theory to incorporate such information as important direction for future work.
Ensemble improvement is low in the interpolating regime
In this section, we will show that the DER behaves qualitatively differently for interpolating versus non-interpolating ensembles, in particular exhibiting behavior associated with phase transitions. Such phase transitions are well-known the statistical mechanics approach to learning [EdB01, MM17, TKM21, YHT*21], but they have been viewed as surprising from the more traditional approach to statistical learning theory [BHMM19]. We will use this to understand when ensembling and not effective for deep ensembles, and to explain why tree-based methods seem to benefit much
7

---

MNIST
Thyrold
OSAR
MNNSST
Thynold
OSAR
1.0
1.0
3000
0.5
2.5
Poosse
8030 G03ehooadeeee
0.
10:
18"
10
10
12
10"
102
100
10
Fandon: Reaturee
Random Teaturns
Randem Pesturre
Max Leaf Nodos
Leat Nocos
Max Nodes
Any.
Figure 3: Bagged random feature classifiers. Blacked dashed line represents the interpolation threshold. Across all tasks, DER and EIR are maxi- mized at this point, and then decrease thereafter.
Figure 4: Random forest classifiers. Blacked dashed line represents the interpolation threshold, Across all tasks, DER and EIR are maximized at this point, and then remain constant thereafter.
DER
EIR
DER
EIR
0.35
1.1
Batch Size
1.1
0.30
Batch
1.0
0.3
1.0
0.25
0.8
0.8
Width
Width
Width
Width
(a) Without LR decay.
(b) With LR decay.
Figure 5: Large scale studies of deep ensembles on ResNet18/CIEAR- We plot the DER and EIR across range of hyper-parameteen for two training settings: one with learning rate decay, and one without, The black dashed line indicates the interpolation threshold, i.e., the curve below which individual models achieve exactly zero training error. Observe that interpolating ensembles attain distinctly lower EIR than non-intennn non-interpolating ensembles, and correspondingly have low DER (< 1), compared non-interpolating ensembles with high DER (> 1).
from ensembling across all settings. We say that model is interpolating if it achieves exactly zero training error, and we say that is non-interpolating otherwise; we call an ensemble interpolating each of its constituent classifiers is interpolating. Note that for methods that involve resampling of the training data (c.g., bagging methods), we define the training error as the "in-bag" training, i.c., the error evaluated only the points classifier was trained on.
Interpolating random feature classifiers. We first look at the bagged random feature ensembles plot the EIR, DER and training error
on the MNIST, Thyroid, and QSAR datasets. In Figure for each of these ensembles. We observe the same phenomenon across these three tasks: as a function of model capacity, the EIR and DER are both maximized the interpolation threshold, before decreasing thereafter. This indicates that much higher-capaciy, models, those with the ability to easily interpolate the training data, benefit significantly less from ensembling. In particular, observe that for sufficiently high-capacit ensembles, the DER become less than 1, entering the regime in which our theory guarantees low ensemble improvement.
Interpolating deep ensembles. We next consider the DER and EIR for large-scale empirical models in batch size/width space, both with and without learning
evaluations on Res rate decay. See Figure 5 for the results. Note that the use of learning rate decay facilitates easier interpolation of the training data during training, hence broadening the range of hyper-parameters for which interpolation occurs. The figures are colored so that ensembles in the regime DER < are in red, while ensembles with DER. 1 are in grey. The black dashed line indicates the interpolation threshold, i.c., the curve in (meaning every classifier in the ensemble has zero training error). Observe in particular that, across all settings, all models in the regime DER < are interpolating models; and, more generally, that interpolating models tend exhibit much smaller DER than non- interpolating models. Observe moreover that there can be sharp transition between these two regimes, wherein the DER is large just the interpolation threshold, and then it quickly decreases beyond that threshold. Correspondingly; ensemble improvement is much less pronounced for interpolating ensembles versus more traditional non-interpolating ensembles. This consistent with results previously observed in the literature, e.g.. [GJS+20]. We remark also that the behavior observed in Figure 5 exhibits the same phases identified
space below which ensembles achieve zero training error

---

12
EIR
1.0
DEI
0.6
0.6
04
02
0.2
CNN LETXIMDE DeSN to
Figure 6: Bayesian ensembles IMDB and CIFAR-10. These provide examples ensem- bles which do not interpolate the training data, and which have high DER (> 1) and corre- spondingly high FIR.
RTE
CoLA
XNL
MRPC
Q0P
QNLI
5512
Figure 7: Ensembles of fine-tuned BERT on GLUE tasks. Here the models are large relative the dataset size, and consequently they exhibit low DER (< 1) and EIR across all tasks.
in [1] (an example of phase transitions in learning more generally [EdBO1, MM17J), although the DER itself was not considered in that previous study,
Bayesian neural networks. Next, we show that Bayesian neural networks benefit significantly from ensembling. In Figure 6, we plot the DER and EIR for Bayesian ensembles on the CIFAR-10 10 and IMDB tasks, using the ResNet20 and CNN-LSTM architectures, respectively. The samples we present here are provided by [INLW2I], who use Hamiltonian Monte Carlo to sample accurately from the posterior distribution over models. For both tasks, we observe that both ensembles exhibit DER > and high EIR. In light of our findings regarding ensemble improvement and interpolation, we note that the Bayesian ensembles by design do not interpolate the training data (when drawn at non-zero temperature), as the samples are drawn from distribution not concentrated only on the modes of the training loss. While we do not perform additional experiments with Bayesian neural networks in the present work, evaluating the DER/EIR these models is an interesting direction for future work. We hypothesize that the qualitative effective of decreasing the sampling temperature will be similar to that of increasing the batch size in the plots in Figure 5.
function of posterior temperature for
Fine-tuned BERT ensembles. Here, we present results for ensembles of BERT models fine-tuned on the GLUE classification tasks. These provide examples of very large model trained small datasets, on which interpolation casily possible. For these experiments, we use 25 BERT models pre-trained from independent initializations provided in 22). Each of these 25 models is then fine-tuned on the classification tasks in the GLUE [WSM* 19] benchmark set and evaluated on relatively small test sets, ranging in size from 250 (RTE) 40,000 (QQP) samples. In Figure 7, plot the EIR and DER across these benchmark tasks and observe that, as predicted, the ensemble improvement rate is low and DER. is uniformly low (< 1).
The unique of random forests. Random forests methods in practice. Here, we show that the effectiveness of ensembling is much greater for random forest models than for highly-parameterii ensembles. Note that for random forests, interpolation of the training data is possible, in particular whenever the number of terminal leaf nodes is sufficiently large (where here we again compute the average training error using on the in-bag training examples for each tree), but it is not possible go "into" the interpolating regime. In Figure 4, plot the DER, EIR, and training error function of the max number of leaf nodes (a measure of model complexity). Before the interpolation threshold, both the EIR and DER increase as function of model capacity, in line with what is observed for the random feature and deep ensembles. However, we observe distinct behavior at the interpolation threshold: both EIR and DER become constant past this threshold. This is fundamental to tree-based methods, due to the method by which they are fit, e.g., using standard procedure like CART [BFSO84]. As soon split the nodes further is saturated at zero, and therefore the models cannot continue to grow. This indicates that trees are particularly well-suited to ensembling across all hyper-parameter values, in contrast to other parameterized types of classifiers.
of the most widely-used ensembling
models like the random feature classifiers and the deep
tree achieves zero training error, any impurity method used to
Discussion and conclusion
To help answer the question when ensembling is effective, we introduce the ensemble improvement rate (EIR), which we then study both theoretically and empirically. Theoretically, we provide

---

comprehensive characterization of the EIR in terms of the disagreement-ergg ratio DER. The results are based on a new, mild condition called competencee which we introduce rule out pathological cases that have hampered previous theoretical results. Using simple first-order analysis, we show that the competence condition is sufficient to guarantee that ensembling cannot hurt performance- something widely observed in practice, but surprisingly unexplained by existing theory. Using second-order analysis, we are able to theoretically characterize the EIR, by upper and lower bounding it in terms of a linear function of the DER. On the empirical side, we first verify the assumptions of our theory (namely that the competence assumption holds broadly in practice), and we show that our bounds are indeed descriptive of ensemble improvement in practice. We then demonstrate that improvement decreases precipitously for interpolating ensembles, relative to non-interponn interpppppog ones, providing very practical guideline for when to use ensembling.
Our work leaves many directions to explore, of which we name few promising ones. First, while our theory represents significant improvement on previous results, there are still directions to extend our analysis. For example, Figure suggests that the relationship between EIR and DER can be even more finely characterized. Is it possible to refine our analysis further to incorporate information about the data and/or model architecture? Second, can we formalize the connection between ensemble effectiveness and the interpolation point, and relate it to similar ideas in the literature?
References
[ABP*22] 22] Taiga Abe, E. Kelly Buchanan, Geoff Pleiss, Richard Zemel, and John Patrick Cunning- ham. Deep ensembles work, but are they necessary? In Advances in Neural Information Processing Systems, 2022.
[ABPC22] Taiga Abe, E Kelly Buchanan, Geoff Pleiss, and John Patrick Cunningham. The best deep ensembles sacrifice predictive diversity. In I Can't I Believe It's Not Better Workshop: Understanding Deep Learning Through Empirical Falsification, 2022.
[ALMV20] Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov. Pitfalls of in-domain uncertainty estimation and ensembling in deep learning. International Conference on Learning Representations (ICLR), 2020.
[BCNM06] Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizil Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 535-541, 2006.
[BFSO84] Leo Breiman, Jerome Friedman, Charles J. Stone, and R.A. Olshen. Classification and Regression Trees. Chapman and Hal//CRC, 1984.
[BGCT19] Davide Ballabio, Francesca Grisoni, Viviana Consonni, and Roberto Todeschini. In- tegrated qsar models to predict acute oral systemic toxicity. Molecular Informaties. 2019.
[BHMM19] M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proc. Natl. Acad. Sci. USA, 116: 15:49- 15854, 2019.
[Bre01] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[CG16] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
[Con85] Marquis de Condorcet. Essay on the application of analysis to the probability of majority decisions. Paris: Imprimerie Royale, 1785.
[DCLT19] Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre- training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, pages 4171-4186, June 2019.
[Den12] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 19(6):141-142 2012.
10

---

[DG17] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[EdB01] A. Engel and C. L. Van den Broeck. Statistical mechanics of learning. Cambridge University Press, 2001.
[FHL19] Stanislav Fort, Huiyi Hu, and Balaji Lakshminaarayanan. Deep ensembles: A loss landscape perspective. arXiv preprint arXiv::112..02757,220 2019.
[GJS 20] Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters deep learning. Journal of Statistical Mechunics: Theory and Experiment, 2020()):23401, 2020.
[GLL*15) 15] Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario March, and Jean- Francis Roy. Risk bounds for the majority vote: From PPC--Baystie analysis to learning algorithm. Journal of Machine Learning Research, 16(26):787-88) 2015.
[HD19] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. Proceedings of the International Conference on Learning Representations, 2019.
[HVD" 15] Geoffrey Hinton, Oriol Vinyals, Jeff Dean, et al. Distilling the knowledge in a neural network. arXiv preprint (rXXiv:50330055:3 2(7), 2015.
[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.
[INLW21] Pavel Izmailov, Patrick Nicholson, Sanae Lotfi, and Andrew G Wilson. Dangers of Bayesian model averaging under covariate shift. Advances in Neural Information Processing Systems, 01:3309-33222 2021.
[IVHW21] Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson. What are Bayesian neural network posteriors really like? In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages
PMLR, 18-24 Jul 2021.
[KH 09] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[LMRR17] François Laviolette, Emilie Morvant, Liva Ralaivola, and Sran-Francis Roy. Risk upper bounds for general ensemble methods with an application to multiclass classification. Neurocomputing. 2 19::15-25, 2017.
[LPB17] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
[MDP" 11] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 142-150, June 2011.
[MLIS20] Andres Masegosa, Stephan Lorenzen, Christian Igel, and Yevgeny Seldin. Second order PAC-Bayesian bounds for the weighted majority vote. In Advances in Neural Information Processing Systems, volume 33, pages 5263-5273, 2020.
[MM17] C. H. Martin and M. W. Mahoney. Rethinking generalization requires revisiting old idcas: statistical mechanics approaches and complex learning behavior. Technical Report Preprint: arXiv:1710.09553. 2017.
[OCnM22] Luis A. Ortega, Rafael Cabañas, and Andres Masegosa. Diversity and generalization in neural network ensembles. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 11720-11743, 28-30 Mar 2022.

---

[OFR' 19] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
[PVG 11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blon- del, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas. A. Passos, D. Coumapeaa, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28355 2011.
[QCHL87] R. Quinlan, P. J. Compton, K. A. Horn, and L. Lazarus. Inductive knowledge acquisition: A case study. In Proceedings of the Second Australian Conference on Applications of Expert Systems, page 137-156, USA, 1987. Addison-Wesleg Longman Publishing Co., Inc.
[RRSS19] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do Ima- geNet classifiers generalize to ImageNet? Kamalika Chaudhuri and Ruslan Salakhut- dinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages $389-5400 PMLR, 09-15 Jun 2019.
[SYT*22] Thibault Sellam, Steve Yadlowsky, Ian Tenney, Jason Wei, Naomi Saphra, Alexander D' Amour, Tal Linzen, Jasmijn Bastings, Iulia Raluca Turc. Jacob Eisenstein, Dipanjan Das, and Ellie Pavlick. The multiBERTs: BERT reproductions for robustness analysis. In International Conference on Learning Representations, 2022.
[TKM21] Ryan Theisen, Jason Klusowski, and Michael Mahoney. Good classifiers are abundant in the interpolating regime. In Arindam Banerjee and Kenji Fukumizu, editors, Pro- ceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3376-3384. PMLR. 13-15 Apr 2021.
[WSM 19] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: multi-task benchmark and analysis platform for natural language understanding. In International Conference on Learning Representations, 2019.
[YHT*21] Yaoqing Yang, Liam Hodgkinson, Ryan Theisen, Joe Zou, Joseph E Gonzalez, Kannan Ramchandran, and Michael W Mahoney. Taxonomizing local versus global structure in neural network loss landscapes. In Advances in Neural Information Processing Systems, volume 34, pages 18722-18733 2021.
12


Reviews:
[{"review_id": "EtEAdNr8CE", "reviewer": "Reviewer_G3j5", "summary": "This study explores when ensembling leads to significant performance enhancements in classification tasks. Theoretical findings reveal that ensembling improves performance considerably when the disagreement rate among classifiers is large compared to the average error rate. The study also establishes improved upper and lower bounds on the average test error rate of the majority vote classifier under a condition called competence. In addition to the theoretical analysis, the researchers conduct empirical experiments in various scenarios to validate their theory. The study highlights a distinction in the behaviour of interpolating models  and non-interpolating models, showing that ensembling provides more significant benefits in the latter case.\n", "questions": "Could you derive Thm 2 under the assumption that EIR>1? Because, in this case, your assumption should be EIR>1. \n", "limitations": "Authors do not fully discussed the limitations of their work. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The work addresses a relevant and, still, open problem: when are ensembles really effective? The presented theoretical framework is specially designed to answer this question. Although it builds on previous theoretical analysis, it introduces a new concept, “competent ensembles”, which give rises to more insightful conclusions. \n\n- The empirical evaluation of this work is quite strong. Besides validating the proposed theoretical framework, authors also provide insightful analysis about the effectiveness of ensembles. The analysis of what happens at the interpolation regime is of high importance for current practices of machine learning. \n", "weaknesses": "- Assumption 1 is central in the theoretical analysis of this work. Although authors make an effort in describing assumption 1 as a condition guaranteeing that ensembles are better than individual classifiers, this assumption is very technical and it is not well described. \n\n- Although this is not the main aim of this paper, the provided theoretical framework provides little to no guidance in how to build better ensembles. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review of our work, and useful feedback. While the aim of this work is not necessarily to provide guidance on how to build better ensembles, we hypothesize that some of our insights might lead to the development of better methods in future work. In particular, our findings regarding EIR/DER in and out of the interpolating regime suggest that overparameterized deep ensembles require more diversity than current methods allow to be effective.\n\nRegarding Assumption 1, there are a few comments that can be made to perhaps better elucidate its nature. For example, taking $t = 0$ in the statement of the assumption reveals the condition that, on average over the data, more classifiers in the ensemble are correct than not. What we actually require is stronger than this -- that, over the data, it is more likely that *slightly* more classifiers in the ensemble are correct than *slightly* less. This is along the lines of a stochastic dominance condition. However, we do observe that the competence condition holds widely in practice. We will add these comments in the revised version of the paper.\n\nWith regard to the reviewer's question about $\\text{EIR} > 1$, some clarification would be helpful. By definition, $\\text{EIR} \\leq 1$, so perhaps the reviewer had in mind a different scenario?"}, {"review_id": "yc5KUZANCJ", "reviewer": "Reviewer_GNtk", "summary": "Analysis the ensemble improvement rate vs. the disagreement-error ratio", "questions": "What is the usefulness of this study? \nHow to apply them in practice?\n", "limitations": "Not applicable", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "A solid analytical analysi.", "weaknesses": "It is not clear for me what is the usefulness of obtained results.\nThe scope of the experiments is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for providing a review of our paper. As the title and results suggest, the usefulness of this study is in describing when we can expect ensembling methods to be effective. In particular, our empirical result suggests that ensemble improvement is much less pronounced for interpolating versus more traditional noninterpolating ensembles. If possible, it would be helpful if you could provide some additional feedback and/or detail regarding your concerns about our work."}, {"review_id": "AUnYbuGkps", "reviewer": "Reviewer_sRJm", "summary": "The paper asks the following question: when is ensembling beneficial? The benefit is measured by the ensemble improvement rate (EIR), defined as the difference of average and majority voting risk, divided by the average risk. It is shown that 'competent ensembles never hurt', in the sense that under mild assumptions, EIR \\geq 0 (Th. 1). A more precise result (Th. 2) provides quantitative bounds relating EIR and another quantity called the disagreement-error ratio (DER). DER is simply the expected disagreement between our ensembles, divided by the expected loss. A consequence of this result is that improvement is moderate when disagreement is small, whenever it can be large whenever disagreement is large. The paper concludes with some empirical evaluation.", "questions": "Do you suspect that Th. 2 is tight? Could examples similar to those developed for Th. 1 achieve tightness in the string of inequalities?", "limitations": "see weaknesses", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The key question of the paper is of utmost importance to the machine learning community. The answers provided by the present work, although simple, are quite interesting. What is really promising is that competence can be evaluated in practice (Section 4.2), giving an actionable way to check whether it is profitable to do ensembling in a specific concrete case. ", "weaknesses": "The main weakness in my opinion is the restriction to the classification setting, and, further, to the use of the 0-1 loss. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and helpful feedback. The classification/0-1 loss setting represents the most significant challenge from the theoretical perspective, hence the focus on this case. For example, in regression with MSE loss, one has (via a simple bias-variance decomposition) the following identity:\n\n$$\nE_f[L(f)] = L(\\bar{f}) + E_X[\\text{Var}_{f}[f(X)]]\n$$\n\nFrom this, an analogous characterization of the EIR can be derived: $EIR = \\frac{E_f[L(f)] - L(\\bar{f})}{E_f[L(f)]} = \\frac{E_X[\\text{Var}_{f}[f(X)]]}{E_f[L(f)]} \\geq 0$. Similarly, for other loss functions (like the cross entropy loss), the analysis is significantly easier, as one can typically exploit Jensen's inequality to relate the average error to the error of the ensemble model. Other works have addressed this case in detail, e.g. Abe et al. 2022 and Ortega et al. 2022. We will provide some additional clarification on this point in an updated draft of the paper.\n\nWithout further restrictions, we believe Theorem 2 should be tight, although we do not have a formal argument for this. This belief comes from numerical simulations involving perturbations of examples along similar lines to those given in Appendix D. Consider for each example $x$, exactly $(1-\\epsilon)$ fraction of classifiers predict the correct label and the remaining $\\epsilon$ fraction of classifiers predict a wrong label. In this case, $EIR=1$, and the lower bound of the Theorem 2 is $1-\\epsilon\\frac{4(K-1)}{K}$ which can be arbitrarily close to $1$. More precise conditions on the nature of the constants in the lower bound of Theorem 2 arise from considering classifiers with slightly differing individual probabilities.    "}, {"review_id": "XnZyQ6d9oZ", "reviewer": "Reviewer_un8p", "summary": "The paper \"When are ensembles really effective?\" discusses the question asked in the title: When are ensembles really effective? To do so, the authors introduce novel theoretical measures called the ensemble improvement rate and the disagreement-error ratio. The ensemble improvement rate measures the relative rate an ensemble improves over a single learner, whereas the disagreement-error ratio measures the expected disagreement between members of the ensemble scaled by the expected performance of each model. The authors relate both terms to each other through a series of inequalities, i.e. provide an upper and lower bound for the ensemble improvement rate wrt. to the disagreement-error ratio. Moreover, the authors introduce the concept of competent ensembles which more closely resemble ensembles we are seeing in practice: While we might construct ensembles with arbitrarily bad members, we usually see ensembles that, on average, have well-performing members. Last, the authors conclude the paper with an empirical investigation that shows that a) ensembles are indeed competent in practice and b) that the disagreement-error ratio is valuable in predicting if an ensemble might improve performance compared to a single model. ", "questions": "- In the introduction, you present the following scenario: \"In particular, consider the following practical scenario: a practitioner has trained a single (perhaps large and expensive) model, and would like to know whether they can expect significant gains in performance from training additional models and ensembling them\" -- How can you answer this question with EIR and DER? As far as I can see, EIR and DER require already trained ensembles and explain their performance and not predict the performance of a yet untrained ensemble? In this sense, it is similar to the bias-variance decomposition that explains the performance of a model/ensemble post-hoc (i.e. after training) and, therefore might be used as a theoretical guidance tool but not necessarily as a prediction of what model/ensemble performs better or worse in a given scenario. Did I miss something here? \n- Did you explore the relationship between the disagreement-error ratio and the bias-variance decomposition, and if so, what is it? I assume that given a suitable disagreement rate D, one could come up with a term that is close to the variance (i.e., diversity), but the normalization via the expected error rate this novel here.  \n", "limitations": "The authors empirically validate their assumption of competent ensembles that might limit the applicability of the presented theory. Moreover, they point out the unique case of Random Forests that arguably justifies a study in its own right. I agree with the authors that there do not seem to be any negative societal impacts from the theory presented in this paper. ", "rating": 9, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper is well-written and easy to follow. The authors introduce remarks where necessary and re-visit existing results from the literature if it adds valuable information to the paper. \n- The authors introduce new theoretical concepts, argue in favor of them, and show their practical value in experiments. In addition, the authors also validate any assumptions they are making in their empirical investigation. Hence, the authors offer a very complete overview of their ideas, studying them from a theoretical and a practical point of view. This should be the gold standard for all papers introducing novel concepts. \n- The introduced ensemble improvement rate and disagreement-error ratio seem to work well in practice and hence are valuable. Second, I think the idea of competent ensembles can be potentially impactful for future studies about ensembles, as it brings the theory about ensembles closer to what we see in practice", "weaknesses": "- In some form, the paper presents many things we already know in a new form. For example, the disagreement-error ratio can be seen as some form of diversity that has been studied for a long time in the literature. Similarly, the concept of weak learnability and competent ensembles seem to be closely related to each other (see my question below). While the authors did a decent job relating their work to existing work, a deeper discussion here would be interstring\n- There is a minor typo in the paper: Section 3 uses \"K\" as the number of classes, whereas in Section 4 \"C\" is used for the number of classes\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your strong review of our work, and very helpful feedback. \n\nThank you for noticing the K/C typo -- we will correct this. We also agree that a better discussion of the relation of our work to weak learnability would be helpful; we will do our best to incorporate this in an updated draft of the paper.\n\nFor the first question, what you say is indeed true with respect to our theory: to compute any of the terms in our bounds (e.g. the DER), one needs to already have multiple trained models. However, one concrete piece of guidance we can give would be based on our empirical results regarding the behavior of the DER in and out of the interpolating regime. In particular, a simple rule-of-thumb would be that if a *single* trained model is _not_ able to easily interpolate the training data, then ensembling is likely to help signifcantly (though what \"significantly\" means will of course depend on the particular application). In the future, it would be interesting to see if the $DER </> 1$ condition could be used to obtain different heuristics in other settings.\n\nAs for the second question, our results are indeed very closely related to a bias-variance decomposition. In the regression case, when one computes a bias-variance decomposition over randomness in the sampling of models, a completely analogous result holds as an identity: \n$E_f[L(f)] = L(\\bar{f}) + E_X[\\text{Var}_{f}[f(X)]]$, implying that \n\n$$\nEIR = \\frac{E_f[L(f)] - L(\\bar{f})}{E_f[L(f)]} = \\frac{E_X[\\text{Var}_{f}[f(X)]]}{E_f[L(f)]}\n$$\n\nThus, without the normalization, the bound in Theorem 2 admits a similar interpretation. Similar expressions can also be derived for other loss functions, e.g. as in Ortega et al. 2022. We agree that this is an important comment, and will use additional space in an updated draft to include a discussion on this point. "}, {"review_id": "HOIEhWOegY", "reviewer": "Reviewer_E93x", "summary": "The authors offer a novel theoretical analysis of the majority vote classifier. In the process they define the \"ensemble improvement rate\" and give lower and upper bounds on it in terms of another entity they call the \"disagreement-error ratio\", under a novel assumption (competence) that they show empirically is mild. They also show how other works can be phrased in terms of lower/upper bounds on the ensemble improvement rate.", "questions": "This is a bit nit-picky, but I find the $W_{\\rho}$ notation confusing: $E_{h\\sim\\rho}(1_{(h(X)\\neq Y)})$ should really be $E_{h\\sim \\rho}(1_{(h(X)\\neq Y)}|X, Y)$. On the other hand, others may find the notation \"$E_{h\\sim\\rho}(1_{(h(X)\\neq Y)}|X, Y)$\" confusing, despite being exactly correct. (Conditional expectation on random variables yields a random variable.)\n\nPerhaps the solution is to keep $W_{\\rho}$ as $W_{\\rho}(X,Y)$ (meaning not to neglect $X$ and $Y$ in the notation)? Or maybe explain a little more that $P(W_{\\rho} \\in [t, 1/2))$ is over the distribution of $(X,Y)$?\n\nI am also a little confused about the relationship between competence and a similar notion where you change the order of expectation: replace $P_{(X,Y)\\sim D}(E_{h\\sim \\rho}(1_{(h(X)\\neq Y)}|X, Y) \\text{is in some interval})$ with $P_{h\\sim \\rho}(E_{(X,Y)\\sim D}(1_{(h(X)\\neq Y)}|h) \\text{is in some interval})$. Is this more or less intuitive? Can anything be said about ensembles with this alternate definition of competency?\n\nHow does this work compare with the seminal \"Super Learner\" paper (Van der Laan, M. J., Polley, E. C., and Hubbard, A. E.) that is commonly cited in theoretical ensemble research? They compare ensemble performance to the best performing base learner, but they don't give guarantees for when it is better. Would they be able to benefit from a regression-equivalent of \"competence\"?", "limitations": "None that I can see.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "As they say in the paper, without any assumptions all that can be said is that EIR (the ensemble improvement rate) is >=-1. In MLIS20 they make additional assumptions and yield better results, but the current work improves upon the work in MLIS20 by a factor of 2.\n\nThe main novelty and strength of the paper is in the definition of \"competence\", a seemingly mild assumption that allows to get much better theoretical results. (Theorem 1: competent ensembles never heart, i.e. EIR>=0; and Theorem 2 giving explicit bounds of EIR under the assumption of competence.)\n\nAnother strength of the paper is that they are not satisfied that \"competence\" feels like a mild assumption, they show empirical proof that this is often the case.\n\nThe mathematical definitions are elegant, and the paper is easy to read.", "weaknesses": "It is not clear how much the analysis can translate to regression tasks, perhaps some words to address this would be helpful. It may also be nice to say some words about whether the bounds become trivial as K goes to infinity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and very insightful questions. We completely agree on the notational points, and will improve this in an updated draft of the paper. \n\nAs we mention in our response to Reviewer 3, the analysis is actually very simple in the regression case. In this case, via a bias-variance decomposition, we obtain an _identity_ $EIR = \\frac{E_f[L(f)] - L(\\bar{f})}{E_f[L(f)]} = \\frac{E_X[\\text{Var}_{f}[f(X)]]}{E_f[L(f)]} \\geq 0$. Much of the novelty of this work is in addressing the much more challenging case of classification with the 0-1 loss. We will provide some additional clarification on this point in an updated draft of the paper.\n\nThe case $K\\to \\infty$ is actually very interesting and highlights a significant strength of our bound versus prior work. Note that in the limit of large $K$, Theorem 2 reduces to $\\text{EIR} \\geq 2* \\text{DER} - 3$. Far from trivial, this is in fact the same bound one would obtain in the _binary_ case according to the result of Masegosa et al. 2020. Prior to our work, this bound was the tightest known for any $K$. So even under the pessimistic scenario $K \\to \\infty$, our results (and the competence assumption) constitute a significant improvement over existing second-order bounds.\n\nWith respect to the alternative form of the competence assumption the reviewer proposes, we could see a case for this new notion being slightly more intuitive. In particular, depending on one's perspective, it may be more intuitive to reason about a probability over models $h\\sim \\rho$ versus a probability over data. However, it's unclear whether a similar analysis could be conducted under this assumption -- certainly the techniques we employ would have to be suitably adjusted.\n\nThe \"Super Learner\" paper you mention proposes and studies a specific method for ensembling, whereas our paper derived results that apply to (almost) any arbitrary ensembling technique. Moreover, they focus on the regression setting, whereas our focus is on classification."}]

Author rebuttal:

Meta-review: This paper theoretically explores when ensembling leads to significant performance enhancements in classification tasks. Reviewers were unanimously convinced by the contribution and their positive assessment was reinforced by the authors' response (with the exception of one reviewer, who was not very confident in their recommendation and did not engage into the discussions). I recommend acceptance.
Decision: Accept (poster)