Ensembles of Classifiers: a Bias-Variance Perspective
Authors: Neha Gupta
Jamie Smith
Ben Adlam
Zelda E Mariet
Venue: Accepted by TMLR ()

Abstract: Ensembles are a straightforward, remarkably effective method for improving the accuracy, calibration, and robustness of neural networks on classification tasks. Yet, the reasons underlying their success remain an active area of research. Building upon (Pfau, 2013), we turn to the bias-variance decomposition of Bregman divergences in order to gain insight into the behavior of ensembles under classification losses. Introducing a dual reparameterization of the bias-variance decomposition, we first derive generalized laws of total expectation and variance, then discuss how bias and variance terms can be estimated empirically. Next, we show that the dual reparameterization naturally introduces a way of constructing ensembles which reduces the variance and leaves the bias unchanged. Conversely, we show that ensembles that directly average model outputs can arbitrarily increase or decrease the bias. Empirically, we see that such ensembles of neural networks may reduce the bias. We conclude with an empirical analysis of ensembles over neural network architecture hyperparameters, revealing that these techniques allow for more efficient bias reduction than standard ensembles.

Published in Transactions on Machine Learning Research (09/2022)
Ensembles of Classifiers: a Bias-Variance Perspective
Neha Gupta' Stanford University
nchagguplaaccssssaajorrr.c
Jamie Smith Google
jamieas cattleos@@oogle.cco
Ben Adlam Google
adlam com
Zelda Mariet
zmariet@google..om com
Google
Reviewed on OpenReview: https: openreview. net/ forum? id= LIQQFV>cY9
Abstract
Ensembles are straightforward, remarkably effective method for improving the accuracy, calibration, and robustness of neural networks on classification tasks. Yet, the reasons underlying their success remain an active area research. Building upon Pfau (2013), we turn to the bias-variance decomposition of Bregman divergences order to gain insight into the bchavior of ensembles under classification losses. Introducing a dual reparametorization of the bias-variance decomposition, first derive generalized laws of total expeclation and variance, then discuss how bias and variance terms can be estimated empirically. Next, show that the dual reparameterization naturally introduces way of constructing ensembles which reduces the variance and leaves the bias unchanged. Conversely, we show that ensembles that directly average model outputs can arbitrarily increase or decrease the bias. Empirically, we see that such ensembles neural networks may reduce the bias. We conclude with an empirical analysis of ensembles over neural network architecture hyperparameters, revealing that these techniques allow for more efficient bias reduction than standard ensembles.
1 Introduction
The success deep learning has nocessitated many extensions of classical learning theory to modern models and algorithms. In particular, the double-descent phenomenon (Belkin et al., 2019) has inspired a wide breadth of research, in which the classical bias-variance decomposition (BVD) has been key (Neal al., 2019; Adlam & Pennington, 2020). Such analyses have been instrumental to understanding the performance of various strategies that improve deep learning methods, including ensembles of deep networks (Hansen & Salamon, 1990; Takshminarayanan et al., 2017) simple method with state-of-the-art robustness and uncertainty results (Ovadia et al., 2019; Gustafsson et al., 2020).
Most bias-variance analyses are specific to the mean-squared error (MSE). Although one can analyze classifiers from an MSE perspective (Yang et al., 2020), such a restriction inevitably reduces the power of the analysis. However, generalizing bias-variance dccompositions to non-MSE losses is challenging. Although the MSE allows decomposition based on the performance of the mean predictor, this is peculiarity of the MSE rather than the rule. In the general case, bias-variance decompositions require manipulating "central prediction" that is much less amenable to analysis. Although bias-variance decompositions exist for Bregman divergences (including the KL divergence from which standard classification losses are derived) (Pfan, 2013), such decompositions are difficult to interpret and appear to break away from standard intuitions.
Work done Google.

---

Published in Transactions on Machine Learning Research (09/2022)
We begin by bridging the gap between the classical bias-variance decomposition and its generalization to Bregman divergences by means of dual reparameterivation. Analyzing the properties of the bias and variance for non-symmetric losses, we characterize their departure from standard intuition. In particular, we will see that ensembles that average model outputs can either increase or decrease the bias under non-symmetric losses, whereas the bias is unchanged under the MSE. We then further leverage the dual reparameterization to show that alternate ensembling techniques can recover the expected behavior of ensembles under the MSE.
We then investigate the empirical behavior of ensembles of neural networks. We first contrast the behaviors of the two natural ensembling choices that arise from the generalized BVD. We find that, in practice, ensembles that average model outputs decrease the bias, and discuss the conditions under which one ensemble construction is preferable to the other. Hypothesizing that bias reduction is key to the performance of recent ensembling techniques, we finally evaluate ensembles of networks of different architectures, showing that the resulting bias reduction is indeed more efficient than that of ensembles of networks of identical architectures.
Contributions. Using a dual roparamctorization of the central prediction in the bias-variance dccomposition of Pfau (2013), we tease apart which behaviors of the bias and variance are specific to the mean squared error, 1 and which behaviors are common to all Bregman divergences. Our key contributions are the following.
The key quantity (the "central prediction") in the BVD of a Bregman divergence is the primal projection of the expected dual prediction; primal and dual spaces are specific to the choice of Bregman divergence.
This central prediction follows a generalized law of total expectation. Similarly, the resulting variance in the BVD of a Bregman divergence satisfies a generalized law of total variance.
Conditional estimates of the bias and variance are biased by an irreducible quantity which overestimates the bias and underestimates the variance; iterative bootstrapping can improve these estimates.
We (re)define primal and dual ensembling methods based on the BVD. For the cross-entropy loss, primal ensembling averages model probabilities, whereas dual ensembling averages model logits.
Dual ensembling recovers the standard properties of ensembles under the MSE loss (unchanged bias and reduced variance). However, ensembling in primal space can either increase or decrease the bias.
Empirically, we see on Cifar10 and Cifar100 that primal ensembling neural networks under the cross-entropy loss tends to decrease the bias, achieving a lower loss than dual ensembling. This can be explained by the larger influence of extreme predictions under dual ensembling.
Bias reduction contributes to the improved performance of ensembles of neural networks of different. architectures; such ensembles reduce the bias more efficiently as a function of ensemble size.
2 Related work
Bias-variance dccompositions. The bias-variance decomposition has been an important tool in under- standing the behavior of machine learning models (Geman et al., 1992; Kong & Dietterich, 1995; Breiman, 1996; Adlam & Pennington, 2020; Yang et al., 2020; d'coli et al., 2020; Neal et al., 2019; Lin & Dobriban, 2021). Key to the decomposition are the notions of a "central label" and of a "central prediction." Most analyses focus on the bias-variance decomposition for the Euclidean square loss. In this case, the central label and prediction correspond respectively to the mean label and prediction. James (2003) proposed a more general decomposition for symmetric losses, Domingos (2000) focussed on the 0-1 loss, and Pfau (2013) proposed a generalization to the space of all Bregman divergences. Hansen & Heskes (2000) identify which loss functions admit bias-variana decompositions with specific properties (but do not analyze the decompositions themselves). Jiang et al. (2017); Buschjäger et al. (2020) decompose twice diffcrentiable losses via socond order Taylor expansion. In the general case including for the KL divergence the resulting decompositions are approximate. Additionally, the resulting variance term may depend on target labels (Buschjäger et al., 2020, via the loss (()) in Eqs. 1, 2), in significant departure from other standard definitions of a variance.
OOr, more accurately, symmetric losses.
2

---

Published in Transactions on Machine Learning Research (09/2022)
Bregman divergences and KL divergence. Bregman divergences are a generalization of the notion of distance, similar to but less restrictive than metries. Bregman divergences and operations in their associated dual space are instrumental to optimization techniques such as mirror descent and dual averaging (Nemirovski & Yudin, 1983; Nesterov, 2009; Juditsky et al., 2021). Closcr to our work, the Bregman representative defined in Banerjee et al. (2005) is related to the central label defined in (Pfau, 2013). The KI. divergence and mean squared error are the most commonly used Bregman divergences in machine learning. The Itakura-Saito distance appears in matrix factorization tasks for audio processing (Févotte et al., 2009; Lefevre al., 2011). Recent work has also looked at parametric (Amid et al., 2019) or learned Bregman divergences (Cilingir et al., 2020; Siahkamari et al., 2020; Lu et al., 2022).
Due to its importance in machine learning, the KL divergence is one of the few non-MSE Bregman divergences for which the bias-variance tradeoff has been specifically analyzed (Heskes, 1998; Yang et al., 2020). For the KL divergence, the "central predictor" corresponds to an average in log-probability space, which has been studied in many works, including (Brofos & Shu, 2019; Webb al., 2020). The fact that the bias remains unchanged when averaging log- Dog-probability space has been brielly mentioned in (Dietterich, 2005).
Ensembles of deep networks. Ensembles combine the predictions of multiple models to improve upon the performance of single model; see, e.g., (Zhou, 2019; Dietterich, 2000). Recently, ensembles of neural networks that only differ in their random seed ("deep ensembles") have been shown to be particularly strong bascline for a varicty of benchmarks (Lakshminarayanan et al., 2017). This result prompted further research into alternative ensemble methods, including ensembles over architectures (Zaidi et al., 2021), and joint ensemble training (Webb et al., 2020). In parallel, several hypotheses have been proposed to explain the performance of deep ensembles. Fort et al. (2019) showed empirically that deep ensembles explore diverse modes in the loss landscape. Allen-Zhh Zhu & Li (2020) argued that the effectiveness of deep ensembles hinges on the assumption that inputs to the model have multiple correct features that are learned by the different ensemble members. Wilson & Izmailov (2020); Hoffmann & Elster (2021) analyzed deep ensembles a Bayesian averaging procedure. Masegosa (2020); Ortega et al. (2021) focus on understanding the relationship between generalization and diversity for deep ensembles, both from theoretical and empirical perspectives. Lobacheva et al. (2020); Kobayashi et al. (2021) considered the interplay between model and ensemble size.
(Wenzel et al., 2020),
3 Bias-Varianne decomposition
We begin with some background on Bregman divergences, which also serves to set our nolation. We refer to & Lugosi (2006) for further background on Bregman divergences.
Although our empirical analysis focuses on the specific case of the KL divergence, all thcoretical results are stated for arbitrary Bregman divergences; proofs not provided in the main text can be found in Appendix A.
3.1 Preliminaries
Let X be closed, convex subset of Rd, and let F: X be strictly convex, differentiable function over X. The Bregman divergence associated with F is the function Dr X x X + RR,,, such that
Dr[vlla]== Fly) - F(x) VF (y xx).
(1)
It follows directly from the convexity of F that Dr is convex in its first argument, although not necessarily in its second argument (Bauschke & Borwein, 2001).
Ezample 3.1. The Bregman divergence of the negative entropy F(x) = = x log x, is the generalized KL
divergence DF [M|[=] KLyy|lz] E,(, - z.). For and y in the probability simplex, Drlv|l=] KL[y [x]]
The Bregman divergence of the convex conjugate F of F is also of particular importance to our analysis. We recall that the convex conjugate of a convex function F is defined as
F*(=) sup (2, - F(x).
3

---

Published in Transactions on Machine Learning Research (09/2022)
Example 3.2. The convex conjugate of the negative entropy function on the probability simplex is the log-sun-exp function (Boyd & Vandenberghe, 2004, Example 3.25).
As we assume that is differentiable, we denote by (x))) the dual of x E X. We will require the following identity between primal and dual x²:
( (VF(()))
(2)
Example 3.3. Let F be the negative entropy over the probability simplex, whose convex conjugate F is the log-sum-exp function. Then, V is the softmax function, and Equation (2) yields the identity softmax(logr - 1) softmax log x, where we let log operate element-wise on the vector æ.
A Bregman divergence Dp and its conjugate equivalent DF- are related by the following equality: Proposition 3.1 (Cesa-Bianchh & Lugosi (2006)). Vz, y E X, DF(# Il vl = I=-lv" || x*).
Ezample 3.4. Let F be the negative entropy over the probability simplex, and write log-sum-exp as LSE.
Dr.1y"11="1 LSE(y") LSE(x*) - softmax(x") Ty" x*).
3.2 General statement
Let X be random variable over X S Ied representing predictions made by machine learning model, and y be the random variable associated with the corresponding label. Randomness in X may come from the choice of training data, the seed used to initialize the training algorithm, or any other source of randommess in the process that used to obtain the model generating predictions. In contrast, randomness Y is typically due alcatoric uncertainty, such as sensor noise.
A bias-variance analysis decomposes the average divergence []] between label and prediction variables into bias and two separate variance terms. The bias measures the divergence between the average label and the average prediction. The variances mcasure the amount of fluctuation in the labels (Bayes error) and predictions (model variance). These fluctuations are measured around an "average" or "central" point.
Under the mean squared error, these central points are respectively the expected label and expected prediction. More generally, for an arbitrary Bregman divergence, these central labels and predictions are defined minimizers of the expected Bregman divergence with respect to the corresponding random variable.
Definition 3.5 (Central label). Let be random variable over X' (intuitively, the label). We call the unique minimizer arg mingex E [|>] the central label.
Definition 3.6 (Central prediction). Lot X be a random variable over X (intuitively, the prodiction). We call the unique minimizer arg min,ex [D[=[[X] the central prediction.
Proposition 3.2 (Banerjee al. (2005)). The central label sotisfies arg min.e.x ED[Y EY.
By analogy Proposition 3.2, and for reasons that will be clear momentarily, we refer the minimizer arg min, [ the dual mean, and write ΣX.
We now write out the bias- decomposition for any Bregman divergence D (Pfau, 2013):
EDYY |D[
(Bayes error) (bias) (model variance)
+ ||
(3)
+ [X]
Because Bregman divergences are necessarily symmetric, Equation (3) takes on a more complicated form than the mcan squared error's docomposition. In particular, the central prediction is no longer the expected prediction (whereas the central label remains unchanged); additionally, the ordering of terms within the bias and variances is now meaningful.
4

---

Published in Transactions on Machine Learning Research (09/2022)
A main obstacle in bias-variance decompositions of Bregman divergences lies in the unwieldy form of the central prediction, EX- = arg ming [ || x]. Our first contribution resolves this difficulty via simple observation: much like the central label, the central prediction is also the expectation of a random variable; only, this expectation is taken in the dual space defined by the convex function F.
Proposition 3.3 (Dual mean). The duul mean EX is the primal projection of the mean of X in dual space:
EX = (V
Proof. By simple application of Propositions 3.1 and 3.2.
arg argmin min EDr(2 X] =EX
arg argmin EDr- || arr min BDp. (D || [1=") -BXx))
=EX
=*xx*
This reformulation is crucial to our analysis, and, to the extent of our knowledge, novel.
Remark 3.7. When Dr is symmetric, follows from Proposition 3.2 that Σ EX. Ezample 3.8. When F is the negative entropy over the probability simplex, Dy is the KL divergence, and
EX softmax(EElg) X).
3.3 Laws of total expectations and variance
Despite its more general form, the model variance [ of Equation (3) satisfies fundamental properties associated with the usual variance VX B(X EXX). particular, denoting the operation X + BEDEE by V, one can casily verify that VX 2 O, and that VX and only if X is almost surcly constant.
We next show that VX also follows a generalization of the law of total variance. This law disentangles the effect of different sources of randomness, and is thus fundamental tool in model analysis. Given two variables X and Z, the law of total variance decomposes the standard (Euclidcan) variance as VX = E[V(X V Z)]: the variance of X is the sum of the variances respectively unerplained and explained by Z.
We begin by showing that the dual mean satisfies its own form of the law of total expectation; proving this is straightforward with the reparametcrization of Proposition 3.3.
Lemma 3.1. Let X, Z be random voriables on X. Then EX = Ex(E[X|Z],, where E[X 2 = (E(X*)
Proof. The proof follows directly from the (standard) law of total expectation and Equation (2).
8 =(((XX))2)]) (1 (B[B(x12))) = (EX*)) = EX.
-
With Lemma 3.1 in hand, we can easily show a generalized form of the law of total variance, which simply accounts for the definition of dual mean and generalized variance.
Lemma 3.2. Let X, Z be random variables over X, and define the conditional variance V[X [2] == E[D(E(XIZ) I| x] The variance VX == [D[EX]|X] satisfies generalized law of total variance:
v[x] = [[x V[8[x
As above, we define the conditional variance by replacing E[.] with B., We cannot overstate the importance of Lemma 3.2, which is key to disentangling sources of randomness in ML algorithms (Neal et. al., 2019; Adlam & Pennington, 2020; Lin & Dobriban, 2021).
2Pfau (2013) showed that arg min, ED X] satisfies (= [(F(()), which also entails Prop. This definition is simply the definition of using the conditional expectation B[-|Z] in place of El-..
5

---

Published in Transactions on Machine Learning Research (09/2022)
4 Conditional and bootstrapped estimates
Before turning our attention to ensembles, we briefly discuss empirical estimates of the bias and variance.
The bias-variance decomposition of Equation (3) applies to any source of randomness. This includes the random seed chosen to train the model, as well as the randomness in the training data T. However, although one can easily draw new random seed and retrain a model, sampling a new training set is often more difficult. Even when acquiring more data is possible, this data is often used to augment existing training set rather than to evaluate the model's robustness to data randomness.
In settings where there is randomness that cannot be controlled for, the empirical estimates of the bias and variance of Equation (3) will necessarily be only approxinale. For example, if we only get one draw of the training set, our estimates will be conditioned on the available training data. The following proposition quantifies to which extent these conditional quantitics depart from their unconditional equivalents.
Proposition 4.1. Let x Z be two random variables over X; to simplify notation, we assume that the label Y is deterministic (Y = y E X). Applying Equation (3) to X|Z then taking the expectations over Z yields
allernale BVD:
BDb (2D(x]E(XII + +EZE|DE((XINII)]]
Conditional hins: Biasz
Conditional variance: Varz
The conditional bias (resp. variance) overestimates (resp. underestimales) their respective tolal values by the fiaed quantity Ez D
Biasz = total bias + (2D|EX((E(XXI2)
Varz = total variance E=D(Ex(]((((2))
Remark 4.1. The quantity ExD[EX[(((XI2) is non-negative, and equal to 0 if X and Z are independent.
Alternatively, one can estimate the true bias and variance by partitioning the training set into disjoint subscts; models are trained on these subsets, which act as different draws of the training distribution. This approach yields an unbiased estimator that is consistent as the nunber of partitions goes to infinily. However, partitioning raises the difficult question of how (and if) the model should also be modified: for a neural network, should the width or number of layers be reduced to accommodate the smaller training set? Furthermore, this approach by construction incapable of estimating the bias and variance of models trained on the full training set.
A second option lies in bootstrapping (Efron & Tibshirani, 1994; Hall, 1992): we create new datasets by sampling with replacement from the original dataset, and use these samples to estimate the bias and variance. Repeating this procedure by resampling from the bootstrap samples in turn estimates the quantity required to correct (Hall, 1992) the bootstrapped estimate (Algorithm and Figure 2). This approach does not require reducing the size of the training set, but bootstrapped samples will contain duplicate points.
To compare the conditional and bootstrapped estimates, we trained Wide ResNets (WRNs) (Zagoruyko & Komodakis, 2016) with the cross-entropy loss on different disjoint partitionings of the CIFAR-10 dataset. Figure Ia uses 50 partitions of 1 training points, and Figure 1b uses 20 partitions of 2.5k training points. These partitions allow to also compute the true bias and variance of the algorithm." To estimate the conditional bias and variance, all models are trained on only one of the 50 (or 20) partitions of the training data but with different random seeds. To estimate the true bias and variance values, each model is trained on a different partition and a different random seed. To calculate the bootstrap estimates of the bias and variance values, one partition out of the total 50 (or 20) partitions is randomly chosen from the training data, then bootstrap estimates are calculated using Algorithm 1.
In both cases, both estimation methods systematically underestimate the variance and overestimate the bias. Additionally, the boostrap bias is more accurate than the bootstrap variance; for this reason, practitioners may prefer to estimate the variance as the total error minus the bootstrapped bias.
that the bootstrapped estimates are more accurate than the conditional samples, but
4Soc Figure 7 in App. for an empirical analysis of how many partitions are necessary for estimates converge. We insist here that these are the bias and variance of the algorithm trained on respectively 1k and 2.5k points, rather than the bias and variance of the algorithm trained the entire dataset.
6

---

Published in Transactions on Machine Learning Research (09/2022)
bootstrap bias
actual bias
conditional bias conditional variance
bootstrap variance
actual variance
2
0.15
1.0
0.10
0.5
0.05
0
0.0
5
10
15
20
5
10
15
20
5
10
15
20
trained models
trained models
trained models
(a) CIFAR-10, partitions
(b) CIFAR-10, 20 partitions
(c) CIFAR-10, no partitions
Figure/ 1: Conditional and bootstrapped estimates of the bias and variance on variations the CIFAR-10 dataset. The approximations of the CIFAR-10 dataset in figures (a) and (b) allow us to compute the true bias and variance; in both cases, the bootstrap estimates more accurate than the conditional estimates. Figure (c) shows the bootstrap
and conditional estimates the true CIFAR-10 dataset, for which the true estimate cannot be computed.
Algorithm Bootstrap estimate of bias (or variance)
T
Input: Training set T, number of bootstrap samples
for i E (l...., B} do
T; < uniform sample(T) uniform_ssmmpe(T)) for E (1.... B) do
Of size [T]
Ti
T2
T'
Ti f muiifor_sample(T]
Of size [T]
(2)) < bias((TT)))
Bootstrap estimate for Tç
( bias((T))))
Bootstrap estimate for T
T11
T1
T21
T31
(
8 3 6
I ( /D(2)
Corrective term
Figure 2: Generating bootstrap samples from dataset The child every node is sampled with replacement from its parent that all datasets have the same size.
( 10))
return Bias estimate (D))
Figure Ic reports bootstrap and conditional bias and variance on the full dataset. Since the gap between actual bias and variance widens as we decrease the number of partitions, it likely that the true bias dominates the variance the non-partitineed regime (sce also Appendix C).
The rest of results focus the conditional bias and variance, for two reasons. First, bootstrap estimates are expensive to compute, requiring training O(B²) models. Second, attempt to match the standard practice of benchmarking on datasct. Even in cases where model's loss (rather than bias variance) is studied, considering performance across i. draws of the training set is not common practice despite this being the technically correct approach from a frequentist perspective.
5 Ensembles and the BV decomposition
We conclude our theoretical analysis by considering ensembles within the context of the bias-variance decomposition for non-symmetric losses. We will distinguish two types of ensembling. Primal ensembles average individual model outputs, acting as an empirical approximation of the mean operator. In contrast, dual ensembles will approximate the dual mean, by averaging the dual projection of individual model outputs, then casting this average back into primal space.

---

Published in Transactions on Machine Learning Research (09/2022)
5.1 Primal ensembles
Most often in deep learning, ensembles simply average the outputs of n models that dilfer in their initializa- tion (Lakshminarayanan et al., 2017). These ensembles are commonly motivated by the desire to reduce the variance of the predictive model. Indeod, for the MSE, we know that ensembles averaging the outputs of models drawn in i. fashion will (a) reduce the variance, and (b) conserve the bias.
We begin by recovering (a) under some additional weak convexity assumptions on the Bregman divergence, but (b) will prove impossible in the general case.
Proposition 5.1. Let D be Bregman divergence that is jointly convex in both variables. Let X Xn be i..dd random variables drown from some unknown distribulion, and define X E, Xi. Then,
vx ED[EX1IS] S [D|EX]|X]= = VX.
Both KT, divergence and mean squared error are jointly convex, and are special cases of Proposition 5.1. However, conserving the bias when ensembling requires that the Bregman divergence symmetric ensuring that E and & are equivalent operators. In the general case, ensembles can either decrease or increase the bias.
Proposition 5.2. Let D be the KL divergence. There exists distribution over predictions X E IR2 and label {0, 1} such that the bias Dly][[[:]] satisfies
D < D
D[1 - - > D[1 y|EX],
where as above we define the random variable for ensemble predictions X x= = E, X1, and by abuse of notation conflate y E 10 with its one-hot representation.
Remark 5.1. Despite Proposition 5.2, ensembles reduce the overall cross-entropy loss due to Jensen's 's inequality.
That standard ensembles do not preserve the bias (and can, fact, increase it) is a strong departure from what one might naively expect. Thus, it is natural seek an ensemble method that would maintain the following two behaviors: the variance decreases, and the bias is conserved.
5.2 Dual ensembles
To keep the bias D[EY]|EX] unchanged under ensembling, it is clearly sufficient to ensemble in such way that the ensemble predictor X satisfies the equality EX = =XX This is also sufficient to reduce the variance. Proposition 5.3. Let D be any Bregman divergence. Let X,, be i. random variables drown from some unknown distribution, and define the dual ensemble
x x= (=
This operation ensures that ΣX = EX. Furthermore, dual ensembling reduces the variance and conserves the bias: for any independent label variable YoverX, we have
D[EY {X = D BY || [X]
EDEX X < ED[EX X].
Comparod Proposition 5.1 for primal ensembles, dual ensembles do not roquire that be jointly convex guarantee variance reduction; the natural convexity of D in its first argument sufficient. Remark 5.2. Under the KL divergence, dual ensembles amount to averaging model logits instcad of model probabilities (sometimes referred to as geometric averaging).
X = softmax Σ log(X.))
8

---

Published in Transactions on Machine Learning Research (09/2022)
Additional properties of dual ensembling under the KL divergence have been discussed in (Brofos & Shu, 2019); that it preserves bias has been mentioned briefly in (Dietterich, 2005).
Remark 5.3. Reordering Equation (3) for the KL divergence, we can write the loss of an ensemble of models averaged in logit space as the difference between the average individual model loss and the variance, thus recovering the ensemble diversity regularizer from (Webb et al., 2020). Consider noiseless label Y = y for the cross-entropy loss, and let the random variable X be uniformly distributed over n different models 21, , Tn. Writing i == softmax( Σ, log mz) the (dual) ensemble prediction, Equation (3) then yields
1 Σ n
CE = CF(V, $)
cE[$|
Reordering, we can write the ensemble loss CEly, a] as the difference between the average individual model loss and the regularizor in (Webb et al., 2020, Eq. (5)) with regularization strength = 1:
- n E, CElv|læ;] _ n E. CE[
CEly,
6 Empirical analysis of ensembles under the eross-yntropy loss
Choosing the Bregman divergence to be the KL divergence, we know that both primal and dual ensembles reduce the total loss and variance. Furthermore, dual ensembles do not affect the bias, but primal ensembles can either increase or decrease the bias. We now analyze how primal and dual ensembles compare in practice when ensembling neural networks.
6.1 Comparing primal and dual ensembles
We begin by empirical validation of the expected behaviors of primal and dual ensembles. Figures 3a and 3b show the evolution of the total loss, bias, and variance of ensembles of independent WRNs 28-10 under the cross-entropy loss on the associated Cifar test sets; Figure 3c stratifies the decomposition by corruption intensity on the corrupted Cifar-100 (Hendrycks & Dietterich, 2019) test set.
For both primal and dual ensembles, the bias dominates the variance. As these are conditional estimates subject the estimation error described in Proposition 4.1, we cannot affirm that the true bias dominates the true variance, although this is plausible based the conclusions of Figure 1.
As expected, the dual bias is independent of ensemble size. The variance is reduced both by primal and dual ensembling, and is slightly lower for dual ensembles. Finally, bias and variance gaps between primal and dual ensembles widen as the corruption severity increases (Figure 3c). Surprisingly, the primal bias decreases when ensembling; Proposition 5.2 states that primal ensembling can affect the bias, but not necessarily by reducing it.6 However, since primal ensembling reduces bias on these datasets, and because the gap between primal and dual variances is small, the primal NLL is lower; this behavior has been noted previously in (Brofos & Shu, 2019). To understand this, we turn to pointwisc analysis.
Consider models that assign probabilities Pı,-..,PP to the true class. In the two-class setting, we can (pI...... )
exactly write out the primal NLL as - -log trn and the dual NLL as log (pr"""))''>" (00))/**+(((0))((())) (1=p))))>)
Fixing P1. Pi...., Pn-1 > 0, and considering f(pn) primal_loss(pi)) ..... Pn) dual (pss((p......................... Pa), we have
00 S f(pm) < - log Pi + ... Pn-1
(4)
The lower bound of Equation (4) is achioved for P.. + 0: a single model in the ensemble can make the dual loss arbitrarily worse than the primal loss. In contrast, the same single model can at best provide a bounded
Note that the terms shown in Figure are averaged over the entire set. individual points, we will below that the bias be increased decreased by ensembling.
9

---

Published in Transactions on Machine Learning Research (09/2022)
Primal bias
Primal variance
Primal NLL
Dual bias
Dual variance
Dual NLL
0.15
0.10
0.4
0.05
0.2
0.00
15
Ensemble size
Ensemble size
(a) BVD on CIFAR-10
(b) BVD on CIFAR-100
Ensembling:
Primal
Dual
NLL
Bias
0.075
0.050
0.000
severity
severity
severity
(c) BVD on Cifar100 corrupted datasets, stratified by corruption severity, for ensemble size of 5.
Figure 3: Conditional bias, variance, and NLL of ensembles of WRNs 28 10 (estimated using 20 draws of each ensemble size). The dual bias remains constant as function of the ensemble size, while the primal bias reduced. The variance is reduced slightly more for dual ensembles, but at an overall magnitude much smaller than the bias.
improvement for dual ensembles over primal ensembles. Thus, even single point in dataset with large dual loss is theorctically sufficient to make primal ensembling outperform dual ensembling average.
After some simple arithmetic manipulations, we obtain the following equivalent condition under which primal ensembling achieves a lower NLL than dual ensembling in the two-class setting:
Σp: 2 II p/)
II
(5)
E(1
Inequality (5) of arithmetic and geometric mean ratios can be further simplified for ensembles of two models.
Proposition 6.1. Let pı and pa be the probabilities assigned by two models to the true class y. Primal ensembling these models will achieve lower cross-entioe entropy loss than dual ensembling if and only if P2 S 1 Pı.
In other words, primal ensembles are favorable when there is significant. disagreement between ensemble members. This is not surprising: for primal ensembles, all predictions contribute similarly to the ensemble prediction, whereas dual ensembles are more sensitive to extreme predictions (p - 0 or p + 1), and in particular to extreme incorrect predictions (p - 0) see also Figure 16 (Appendix H).
We confirm this in Figure 4, visualizing the pointwise BVD for ensembles of size n on CIFAR-100. As expected, we see that dual ensembles more likely to provide extreme probability estimates than primal ensembles (Figure 4b). When primal ensembles achieve lower NLL than dual ensembles (Figure 4c), both primal and dual ensembles assign probabilitics close to zero to the true class; however, dual probabilities are more concentrated around zero. Conversely, when dual ensembles achieve the lower loss, primal and dual probabilities are more spread out, and dual probabilities tend closer to one (Figure 4d). Finally, for the ensembles analyzed in Figure 4, the dual NLL lower than the primal NLL on almost 85% of datapoints; on such points, we have [NLLprimal NLL 0.05, whereas on the 15% of datapoints where dual NLL is higher than the primal NLL, have [NT.Torimal NL Rs 0.42. This is in line with earlier analysis,
10

---

Published in Transactions on Machine Learning Research (09/2022)
10
Prinal vurtnzee
Pniall NLL
Primul his
0.2
0.1
10.0
0.4
10.0
Dual
Pointwise bias-variance decomposition on Cifar100.
10
Primal
Primal
Primal
Dual
Dual
10F
Dual
Count
Conat
10
101
10
10
0.0
0.2
0.4
0.5
0.5
1.0
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Probubility assigned the
Probubility assigned class
Probubility assigned
(b) Overall distribution
(c) Primal < dual
(d) Dual primal
Figure 4: Pointwise analysis of the bias-variance decomposition the CIFAR-100 test set, using 20 draws of size-5 ensembles. (a) Decomposition over the full test set. Primal quantities (NLL, bias and variance) tend to be lower than their dual counterparts, except for when the loss very close zero, in which dual quantities are smaller. (b) Empirical distribution of primal and dual probabilities assigned to the correct class over all CIFAR-100 test points; extreme predictions (close
1) more common for dual ensembles. (b) Empirical distribution of probabilities assigned to the correct class for the 50 points where the signed difference between primal and dual loss is smallest; (c) for the 50 points where the signed difference between primal and dual loss largest.
which showed that the asymmetry between primal and dual NLL allows for only a few points with much worse dual NLL influence the overall average performance.
We conclude this section by noting that Equation (5) still requires knowledge of the true labels. We leave to future work the question of whether one predict whether primal or dual ensembling will achieve a lower loss without access to the true labels.
6.2 Primal ensembles of different model classes
We conclude our analysis by investigating the behavior of (primal) ensembles that average over network width or network depth as well as random seeds; this has been shown to improve upon ensembling only over the random seed (Zaidi et al., 2021). Based on our analysis, we seek to evaluate whether this improvement over standard ensembles due to faster bias reduction. (Yang et al., 2020) already showed that ensembles of larger models have smaller bias; here, we are interested in whether the bias reduction as function of ensemble size is more efficient when ensembling over different architectures.
We begin with ensembles over different depths, training 100 WRNs of depths of 28, 40, and 52 cach, following the prescribed pallern depth- = 6d + 4; the width multiplier is set to 10. Figure 5 shows indeed that, for the ensemble size compared to ensembles of fixed depth and equivalent model size. Ensembles different depths unsurprisingly have higher variance; however, this increase in variance less than the decrease bias, as shown by the overall NLL. The bias, variance, and NLL values of size-1 ensembles is provided in Appendices E. and F.
ensembles of different depths, the bias decreases faster as a function
11

---

Published in Transactions on Machine Learning Research (09/2022)
Depth = 6d
d=
d Unif((4, 6, 8))
0.700
0.045
Variance
NLL
0.675
Bias
0.632
0.030
0.650
0.624
0.015
0.625
10
20
40
10
20
30
40
20
30
40
Ensemble size
Ensemble size
Ensemble size
(a) NLL
(b) Bias
(c) Variance
Figure 5: Bias, variance, and NLL on CIFAR-100 (estimated using ensemble draws). Networks are trained with different random seeds and different depths and then averaged in probability space (primal ensembles). Averaging over depths dramatically reduces the bias, but turn increases variance. However, the increase variance is much smaller than the decrease in bius, and ensembles over multiple depths outperform ensembles of fixed depth.
width
Unif( (10, 20, 30))
0.045
0.630
Variance
0.030
NLL
Bias
0.645
0.625
0.015
0.620
10
20
40
30
40
Ensemble
Ensemble
Ensemble size
(a) NLL
(h) Bias
(c) Variance
Figure 6: Bias, variance and NLL on CIFAR-100 (estimated using 20 ensemble draws). Networks are trained with different initial random seeds and different widths and then averaged in probability space (primal ensembles). Averaging over the width improves the bias at the cost of the variance.
A similar conclusion holds for ensembles of different widths (Figure 5), where this time we fix the depth 6d + 4 28 and let the width multiplier take values in {10, 20, 20,30). Appendices E and F include results for CIFAR-10 and corrupted datasets, with similar conclusions only the CIFAR-100 corrupted data is faster decrease in bias unclear.
7 Conclusion
Ensembles of deep classifiers achieve state-of-the-art performance across variety of benchmark tasks. Where ensembles have previously been analyzed for regression models through the lens of the bias-variance decomposition, applying this decomposition proves more complicated for non-symmetric losses such as the KL divergence-bast based losses used in the vast majority of classification tasks. Pfau (2013) generalized the BVD to Bregman divergences (including the KL divergence). However, whereas the "central" prediction for the MSE decomposition simply the expected prediction EX, the corresponding quantity for arbitrary Bregman divergences is defined as the minimizer of an expected divergence, a term much less amenable analysis.
We begin by resolving this difficulty by viewing the Bregman decomposition through the lens of convex conjugates, showing that Bregman divergences implicitly defines primal and dual spaces, distinct when the divergence is asymmetric. This perspective allows us to redefine the central prediction simply as the primal projection of the expectation over dual predictions.
Using this reparameterization, we easily show that the model variance resulting from the bias-variance dccomposition satisfics a generalized law of total variance. We also exactly quantify the error estimating the bias and variance terms when such estimates are implicitly conditioned on uncontrolled source of randomness (oftentimes, the randomness in the training data).
12

---

Published in Transactions on Machine Learning Research (09/2022)
The existence of primal and dual spaces for the vlas-variance decomposition also has key implications when building ensembles. Ensembling in primal space corresponds to simply averaging model predictions; this is the usual setting for ensembles of neural network classifiers. We show that primal ensembles deviates from standard assumptions: although they will reduce the variance under gentle assumptions, primal ensembling may either increase or decrease the bias. Conversely, ensembling in dual space recovers expected behaviors, always reducing the variance and leaving the bias unchanged.
Comparing different estimates of the bias and variance, show that conditional estimates incur an irreducible error, and that empirically the conditional bias dominates the variance for WRNs Cifar. Bootstrapped and partitioned estimates suggest that this holds true for the true bias and variance on the full test set.
Finally, we use the bias-variance decomposition to investigate the empirical behavior of neural work ensembles under the cross-entropy loss. Experimentally, we observe that primal ensembling (a) reduces the average bias, and (b) achieves variance reduction of similar magnitude to dual ensembles, thus achieving a lower overall NLL. To understand this behavior, we compare primal and dual ensembles on individual inputs, showing that dual ensembles more sensitive to extreme predictions, and incorrect predictions particularly. Finally, we turn to (primal) ensembles of neural networks over different architectures, hypothesizing that their improved performance may be in part explained by the behavior of the bias. Empirically, we confirm that ensembling over architectures provides a faster bias reduction than ensembling only over random seeds.
Our analysis opens several avenues for future work. Of particular interest is identifying whether the average bias reduction (and corresponding lower loss) of primal ensembles under the cross-entropy loss is common other datasets and tasks, well as applying 2020; Siahkamari et al., 2020; Lu et al., 2022). Analyzing other common ensembling methods used in deep learning and understanding their affect the bias and variance is also of independent interest. Finally, we found that primal ensembling achieves much greater variance reduction than bias reduction, despite bias being the dominating term term-raistt mrai-iiiing the question of whether the insights developed in this work can help derive ensembling methods with greater bias reduction.
analysis to learned Bregman divergences (Cilingir al.,
13

---

Published in Transactions on Machine Learning Research (09/2022)
References
Ben Adlam and Jeffrey Pennington. Understanding double descent requires fine-grained bias-variance docomposition. In Advances in Neural Information Processing Systems, 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. wrXic:201.0996 2020.
Ehsan Amid, Manfred KK Warmuth, Rohan Anil, and Tomer Koren. Robust bi-tempered logistic loss basod on bregman divergences. Advances in Neural Information Processing Systems, 32, 2019.
Arindam Banerjce, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with Bregman divergences. Journal of Machine Learning Research, 2005. ISSN 1532-4435.
Heinz H. Bauschke and Jonathan M. Borwein. Joint and separate convexity of the Bregman distance. In Inherently Parallel Algorithms in Feasibility and Optimization and their Applications. 2001.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias variacee trade-off. Proceedings of the National Academy of Sciences, 2019. ISSN 0027-8424.
Stephen Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, 2004.
Leo Breiman. Bias, variance, and arcing classifiers. Technical report, 1996.
James A. Brofos and Rui Shu. A bias-variance decomposition for Bayesian deep learning. In NewrIPS 2019 Workshop on Bayesian Deep Learning, 2019.
Sebastian Buschjäger, Lukas Pfahler, and Katharina Morik. Generalized negative correlation learning for deep ensembling. CoRR, abs/2011.02952 2020.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
Kubra Cilingir, Rachel Manzelli, and Brian Kulis. Deep divergence learning. In Proceedings of the 37th International Conference on Machine Learning, ICML (C,,'20, 2020.
Stéphane d' Ascolli Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent Bias and variance(s) in the lazy regime. In International Conference on Machine Learning, 2020.
Thomas G. Dietterich. Ensemble methods in machine learning. In International Workshop on Multiple Classifier Systems, 2000. ISBN 3540677046.
Thomas G. Dietterich. Bias-variance theory, 2005.
Pedro Domingos. A unified varianer decomposition and applications. In International Conference on Machine Learning, 2000.
Bradley Efron and Robert J Tibshirani. An introduction to the bootstrup. Chapman & Hall/CRC, 1994.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape perspective. arXiv:1912.02757, 2019.
Cédric Févotte, Nancy Bertin, and Jean-Louis Durrieu. Nonnegative Matrix Factorization with the Itakura- Saito Divergence: With Application to Music Analysis. Neurol Computation, 21(3):793 830, 03 2009. ISSN 0899-7667. doi: 10.1162 nel11///ncco...
www...000...... 200..0008.440 2008004008----00 04-0000--77.... URL https://doi.orge 1162/n/co.. 20-..000000000 04 04-08-771.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural computation, 1992.
Fredrik Gustafsson, Martin Danelljan, and Thomas B Schön. Evaluating scalable bayesian deep learning methods for robust computer vision. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 2020.
14

---

Published in Transactions on Machine Learning Research (09/2022)
Peter Hall. The bootstrap and Edgeworth expansion / Peter Hall. Springer-Verlans New York, 1992. ISBN
3540977201 0387977201.
Jakob Vogdrup Hansen and Tom Heskes. General
decomposition with target independent variance of error functions derived from the exponential family of distributions. In Proceedings 15th International Conference on Pattern Recognition. ICPR-2000, volume 2, pp. 207-210. IEEE, 2000.
L.K. Hansen and P. Salamon. Neural network ensembles. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990. doi: 10.1109/34.5887..
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Represenlations, 2019.
Tom Heskes. Bias/variance decompositions for likelihood-based estimators. Newrul Compulation, 1998.
Lara Holfmann and Clemens Elster. Deep ensembles from Bayesian perspective. arXiv:2105.1328 13283, 2021.
Gareth M James. Variance and bias for general loss functions. Machine learning, 2003.
Zhengshen Jiang, Hongzhi Liu, Bin Fu, and Zhonghai Wu. Generalized ambiguity decompositions for classification with applications in active learning and unsupervised ensemble pruning, In Proceedings of the AAAT Conference on Artificial Intelligence, volume 31, 2017.
Anatoli Juditsky, Joon Kwon, and Eric Moulines. Unifying mirror descent. and dual averaging. arXiv:1910.1311 13742, 2021.
Seijin Kobayashi, Johannes von Oswald, and Benjamin Grewe. On the reversed biri-variance tradeoff in deep ensembles. In ICML 2021 Workshop on Uncertainty and Robustness in Deep Learning, 2021.
Eun Bae Kong and Thomas G. Dietterich. Error-correcting output coding corrects bias and variance. In International Conference on Machine Learning, 1995.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, 2017.
Augustin Lefevre, Francis Bach, and Cédric Févolle. Online algorithms for nonnegative matrix factorization with the itakura-saito divergence. In 2011 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA), pp. 313 316. IEEE, 2011.
Licong Lin and Edgar Dobriban. What causes the test error? going beyond bias- via anova. J. Mach. Learn. Res., 22:155-1, 2021.
Ekaterina Lobacheva, Nadezhda Chirkova, Maxim Kodryan, and Dmitry Vetrov. On power laws in deep ensembles. arXiv:2007.08483, 2020.
Fred Lu, Edward RafI, and Francis Ferraro. Neural bregman divergences for distance learning, 2022. URL
attpp://aane http:///axvvvv.. http///rrii..ooraa////////a orggabs//2/ae 22tp///222600.6.... 04763.
Andres Masegosa. Learning under model misspecification: Applications to variational and ensemble methods. In Advances in Neural Information Processing Systems, 2020.
Zachary Nado, Neil Band, Mark Collier, Josip Djolonga, Michael Dusenberry, Sebastian Farquhar, Angelos Filos, Marton Havasi, Rodolphe Jenatton, Ghassen Jerfel, Jeremiah Liu, Zelda Marict, Jeremy Nixon, Shreyas Padhy, Jie Ren, Tim Rudner, Yeming Wen, Florian Wenzel, Kevin Murphy, D. Sculley, Balaji Lakshminarayanan, Jasper Snoek, Yarin Gal, and Dustin Tran. Uncertainty Baselines: Benchmarks for uncertainty & robustness in deep learning. (xfr:2106.04011 2021.
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste-Julien, and Ioannis Mitliagkas. A modern take on the bias-variane tradeoff in neural networks. arXiv:1810.08s. 085911
2019.
15

---

Published in Transactions on Machine Learning Research (09/2022)
A.S. Nemirovski and D.B. Yudin. Problem Complerity and Method Efficiency in Optimization. Wiley, 1983.
Yurii E. Nesterov. Primal-dual subgradient methods for couvex problems. Math. Program., 2009.
Luis A Ortega, Rafael Cabañas, and Andrés R Masegosa. Diversity and generalization in neural network ensembles. arXiv:2110.13755 2021.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? Evaluating predictive uncertainty under dataset shift. In Aduances in Newral Information Processing Systems, 2019.
David Pfau. A Generalized Bias- Variance Decomposition for Bregman Divergences. http://daviddfau..om
pdf, 2013.
Ali Siahkamari, Xide Xia, Venkatesh Saligrama, David Castañón, and Brian Kulis. Learning to approximate a bregman divergence. In Proceedings of the 34th International Conference on Newral Information Processing Systems, NIPS'20, 2020.
Andrew Webb, Charles Reynolds, Wenlin Chen, Henry Reeve, Dan Iliescu, Mikel Lujan, and Gavin Brown. To ensemble or not ensemble: When does end-to-end training fail? In ECML. PKDD, 2020.
Florian Wenzel, Jasper Snock, Dustin Tran, and Rodolphe Jenatton. Hyperparameter ensembles for robustness and uncertainty quantification. In Advances in Newral Information Processing Systems, 2020.
Andrew Gordon Wilson and Pavel Ixmailov. Bayesian deep learning and probabilistic perspective of generalization. Advances in Neural Information Processing Systems, 2020. ISSN 1049-5258.
Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade-off for gencralization of noural networks. In International Conference on Machine Learning. PMLR, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference (BMVC), September 2016.
Sheheryar Zaidi, Arber Zela, Thomas Elsken, Chris Holmes, Frank Hutter, and Yoe Whye Tch. Neural ensemble search for performant and calibrated predictions. In Avances in Neural Information Processing Systems, 2021.
Zhi-Hua Zhou. Ensemble methods: foundations and algorithms.. Chapman and Hal//CCC 2019.
16

---

Published in Transactions on Machine Learning Research (09/2022)
A Proofs
Proposition A.1 (Generalized briangle inequality for Bregman divergences). For any x. y in the domain of F, we have (1r, 2) (ax,y) D),, (VF(y) =t
Lemma 3.2. Let X, Z be random variables over X, and define the conditional variance V(X =
E [[D(E(X(z) z] The variance VX == [ satisfies a generalized law of total variance:
v[x] B V[E[
Proof. The proof follows from the generalized triangle inequality for Bregman divergences ( (Proposition A.1).
VX = E
Ez
[[EXIII]
DEX1EENN221-DPEEXXX22111111AAC2P - E(X1Z)) z
E
- ((XI2)) 2
E
(((())))) - (((X))))))))))))))(((((())))))") DEXXII(X112)+
- X-,EX - - [
Ez E
Di
EX [[(X| Ez ED 2
+ +2 2 - 1
12, -
E(E(XIZ)
V(XI2)
-[{((]/Z) Z))
Proposition 4.1. Let X, Z be two random variables over X; to simplify nolation, we assume that the label
Y is deterministic (Y = y E X). Applying Equation (3) to X|Z then taking the expectations over yields an alternate BVD:
ED4 E2 (()((((XX
E2E [
Conditional bias: Biasz
Conditional variance: Varz
The conditional bias (resp. variance) overestimates (resp. underestimates) their respective total values by the fized quantity (x
Biasz total bias + EzD[EX([E(X(Z)
Varz -tttll variance EE>|EX|](((|Z))
Proof. Applying Equation (3) to the conditional bias Ez Dly|E((( 2)), we have
EzD || 8(X 2) D [(ε(1|2) + Ez [(x((|Z)] E
E(X12))
Diy Ex] + E2 {(X[Z))
where the last equality stems from the law of iterated expectations for E. The result for the variance terms follows immediately, conditional bias and variance have the same sum the full bias and variance. L
Proposition 5.1. Let D be Bregman divergence that is jointly convez in both variables. Let X1 XI...., Xn be i..dd random variables drawn from some. unknown distribution, and define & = 1 Σ, X,. Then,
v -D-EEEIIIILL
- VX.
-D|EX|IX]=
17

---

Published in Transactions on Machine Learning Research (09/2022)
Proof. Let D 2 x X RR+ be Bregman divergence jointly convex in both variables. Let X = E,E, X where the X; are iid. By convexity, for any E X,
D[ X1 v Σ D[z || X:]
ED|= X] - 1
Σ [D || X,] ED(z || X]
min [D > X] v min [D[= X].
As EX arg min, ED[2 X], min, EDIz X] ED[xX X], concluding the proof.
Proposition 5.2. Let D be the KL divergence. There exists distribulion over predictions X E RR² and label [0 such that the bias Dly] satisfies
D'ylEE < [
- -
- y|Ex],
where as above we define the rundom variable for ensemble predictions 8= E; Xi, and by abuse of nolation we conflate E {0, with its one-hot representation.
Proof. For any one-hot label y {0, 13 and probability vector æ, have KL[y||=] log Ty, and KL[1 y||=| log(1 ny)- As log 1 is decreasing, suffices prove that there exists distribution D such that KL |L]y||EX] + KL] In fact, it suffices to prove the existence of a distribution D such that EX + &&.
For the cross-entropy loss, we know? that ΣX loltmax(EElog.X.. X). Let be the distribution that assigns (0.6, 0.4), and is clsewhere. The equivalent ensemble distribution assigns 1/4 probability to (0.8, 0.2) and (0.6, 0.4), and 1/2 probability to (0.7,0.3) A simple numerical computation then shows that EX * EX, concluding our proof.
equal probability to (0.8, 0.2) and
Proposition 5.3. Let be any Bregman divergence. Let .I....,A Xn be n i.i.d. random variables drawn from some unknown distribution, and define the dual ensemble
x= n -=,xxx))'
This operation ensures that = Furthermore, dual ensembling reduces the variance and conserues the bios: for any independent label variable Y Yover have
D[EY {X = D EY || EX]
EDEE X < ED[EX X].
Proof. To preserve bias, it suffices have Ex EXX By definition of X, we have
= = (EX*)) (x=+)X))
(RX***
E [R| Exxx)
(EX*)* = EX.
(6)
See, e.g., (Yang al., 2020).
18

---

Published in Transactions on Machine Learning Research (09/2022)
We now focus on the variance. Successively,
EDr[EX||X]
ED, [X
(by EX = EX)
= F [X [[(E)))
(by Proposition 3.1)
ED Σ, x; ((()(
(0)
ED xxI](Ex)]]
(by convexity of De- in its first argument)
Σ EDF EX|XX
n
D
Proposition 6.1. Let and be the probabilities assigned by two models to the true class Primal ensembling these models will achieve lower cross-enlropy loss than dual ensembling if and only if p2 S - Pt.
Proof. When n = 2, inequality (5) holds if and only if
- 11)p1)(1 (p) + p2)² - P1Pp2( - (p1 + P2)) 2 0 (p1 P2)) 2 0. (p1 (01-2))(( P2)
Thus, the primal loss is smaller than the dual loss if and only if p1 P2 P2 P1-
B Experimental Details
The models used in this work wide residual networks (WRN-28-10) (Zagoruyko & Komodakis, 2016) with the cross-entropy loss unless specified otherwise. We train models with SGD + momentum to optimize the cross-entropy loss. We use the learning rate schedule, batch size, and data augmentations specified in the deterministic baseline provided by Nado et al. (2021).
19

---

Published in Transactions on Machine Learning Research (09/2022)
C
Partitioned estimates of the bias and variance
14-
32
12-
varfancc
multple fixed
26
foed
06-
24
0.4
22
02-
75
17.5
75
15.0
Number
(a) Bias
(b) Variance
Figure 7: Bias and variance of a smaller WRN-16-55 over the CIFAR-100 dataset. We create 20 partitions of the CIFAR-100 dataset, and estimate the bias cither by conditioning a partition (partition Exed/conditional estimate), by including the partition into the expectations that define the bias and variance (partition multiple; converges to the true estimate). We see that it takes 2 10 partitions for the estimates of bias and variance to begin converging, and that the converged values appear to still show the bias dominating the variance.
Bias-variance decomposition on SVHN and corrupted Cifar
Primal bias
Primal variance
Primal NLL
Dual bias
Dual variance
Dual NLL
1.0
0.8
20
0.10
6.6
618
62
0.5
(a) SVHN (clean test set)
(b) CIFAR-10 corrupted
(c) CIFAR-100 corrupted
Figure 8: Conditional bias, variance, and NLL of primal and dual WRN-28-11 ensembles on the SVHN test set (left) and the corrupted Cifar10 and Cifar100 Lest sets (averaged over all corruptions). The comparison between primal and dual ensembling methods remains similar, although are values are increased due to the dataset shift.
20

---

Published in Transactions on Machine Learning Research (09/2022)
E Additional depth experiments
Depth = 6d
d - Unif((4 6, 8))
0.120
0.1100
0.0100
Variance
0.0075
NLE
0.115
Bias
0.0050
0.1050
0.0025
0.105
0.1025
10
20
30
40
20
10
20
30
40
Ensemble size
Ensemble size
Ensemble size
(a) NLL
(h) Bias
(c) Variance
Figure 9: (Primal) ensembling over depths: bias-variance decomposition on the Cifar10 clean test set.
Depth 6d++4
d=
d Unif((4, 6))
0.84
0.045
0.78
0.81
Variance
Bias
0.030
0.76
0.78
0.015
0.75
0.74
10
20
40
20
30
10
30
40
Ensemble size
Ensemble size
Ensemble size
(a) NLL
(b) Bias
(c) Variance
Figure 10: (Primal) ensembling over depths: bias-variance decomposition on the Cifar10 corrupted test
Depth = 6d++4
d Unif((4. 61)
2.16
0.12
Varianoe
0.09
Bias
2.12
2.66
0.06
2.08
20R
0.03
10
30
20
40
Ensemble size
Ensemble size
Ensemble size
(a) NLL
Bias
(c) Variance
Figure 11: (Primal) ensembling over depths: bias-variance decomposition on the Cifar100 corrupted test set.
Depth
NLL
Bias
Variance
Depth
NLL
Bias
Variance
0,181
0.127
0.053
6
1.170
0.923
0.247
Uniform
0.177
0.125
0.051
Uniform
1.120
0.885
0.235
(a) Clean test set
(b) Corrupted test set
Table 1: Bias, variance, and NLL values for size-1 ensembles for varying WRN depths Cifar10
21

---

Published in Transactions on Machine Learning Research (09/2022)
Depth
NLL
Bias
Variance
Depth
NLL
Bias
Variance
0.971
0.717
0.254
2.887
2.355
0.532
Uniform
0.980
0.718
0.262
Uniform
2.917
2.372
0.547
(a) Clean test set
(b) Corrupted test set
Table 2: Bias, variance, and NLL values for size-1 ensembles for varying WRN depths on Cifar100
F Additional width experiments
width = 20
Unif(( (10, 30))
0.108
0,008
Variance
Blas
0.106
0.110
0.004
0.105
0.002
10
20
40
10
20
30
40
30
40
Ensemble size
Ansemble size
Ensemble size
(a) NLL
(b) Bias
(c) Variance
Figure 12: (Primal) ensembling over widths: bias-variance decomposition on the Cifar10 clean test set.
width 20
Unif(( 20, 30))
0.04
0.800
0.750
Variance
0.03
NLL
0.775
Bias
0.02
0.750
0.735
0.725
10
20
40
30
40
Ensemble size
Ensemble size
Ensemble size
(a) NLL
(b) Bias
(c) Variance
Figure 13: (Primal) ensembling over widths: bias-variance decomposition on the Cifar10 corrupted test set.
width 20
Unif(( (10, 20, 30))
212
2.040
0.075
NLL
Bias
2.025
Variance
0.050
2.100
2.04
2000
10
20
30
40
10
20
30
40
10
20
30
40
Ensemble size
Ensemble size
Ensemble size
(a) NLL
(b) Bias
(c) Variance
Figure 14: (Primal) ensembling widths: bias-variance decomposition the Cifar 100 corrupted test set.
22

---

Published in Transactions on Machine Learning Research (09/2022)
Width
NLL
Bias
Variance
Width
NLL
Bias
Variance
20
0.164
0.123
0.041
20
1.044
0.848
0.196
Uniform
0.164
0.121
0.043
Uniform
1.040
0.841
0.199
(a) Clean test set
(b) Corrupted test set
Table 3: Bias, variance, and NLL values for size-1 ensembles for varying WRN widths on Cifar10
Width
NLL
Bias
Variance
Width
NLL
Bias
Variance
20
0.864
0.683
0.180
20
2.529
2.166
0.364
Uniform
0.877
0.684
0.193
Uniform
2.574
2.176
0.399
Clean Lest set
(b) Corrupted test set
Table 4: Bias, variance, and NLL values for size-1 ensembles for varying WRN widths on Cifar100
G Expected calibration error
Primal
Dual
0.025
0.07
0.06
BCB
0.05
0.015
0.04
0.010
0.0
0.005
0.02
Ensemble size
Ensemble size
(a) CIFAR-10
(b) CIFAR-100
Figure 15: Primal and dual expected calibration error (ECE) on the Cifar10 and Cifar100 datasets.
H Primal and dual ensembling for = 2
Primal
Dual
2.5
2.0
2.0
1.5
1.5
1.0
1.0
0.5
0.5
0.0
0.0
1.0
0.4
0.8
0.2
P2
Pt
P2
pi = 0.2
(b) p1 =.5
(c) pi =.8
Figure 16: Ensembling two models with the cross-entropy loss. When the second model's predicted probability for the true class Pa is extreme (either towards towards 1), it dominates This allows dual ensembling to achieve lower loss when the second model is correct (p2 - 1), but also achieves much higher losses when the second model is incorrect (pa + 0). Note that primal and dual losses are equal at pı pa and Pi P2, predicted by Proposition 6.1.
prediction made by other model p
23


Reviews:
[{"review_id": "RyqUZEytnP", "reviewer": "Reviewer_iTBd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Novel analysis applying the bias variance tradeoff for Bregman divergence to model ensembles\n2. Introduction of a new class of (dual) ensembles whose behaviour (same bias, lower variance) is clearly justified by the theory introduced in the paper\n3. Extensive experiments comparing primal and dual ensembles, and comparing primal ensembles of different model architectures which is demonstrated to be superior to using the same architecture for all models in the ensemble.\n\nWeaknesses:\n\n1. Explanation could be clearer (see requested changes below)\n2. Experimental results (superior performance/lower bias of primal ensembles compared to dual ensembles) are not fully explained by the theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a justification for the success of ensemble models in various prediction tasks. The main novelty is the analysis through the generalization of the bias-variance tradeoff to Bregman divergences, thereby extending it beyond Mean Squared Error (MSE) to asymmetric losses like the KL divergence. The authors demonstrate that in this case the mean prediction from the bias-variance analysis with MSE can be replaced by the primal projection of a dual mean. Using this, the authors show that (conventional) model ensembling in the primal space reduces variance and may increase or decrease bias, while ensembling in the dual space decreases variance and leaves bias unchanged. Experimental results validate these claims though bias with primal ensembles is almost always lower than that of dual ensembles, and appears to decrease with increasing ensemble size.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I like the novelty of the idea and the extent of the analysis and experiments. I think the paper will be ready for publication if the following changes are made to the explanation:\n\n1. I would recommend adding a running example in Section 3 since all readers interested in ensemble models may not be familiar with Bregman divergences. A good candidate for this would be the KL divergence. Currently Remark 3.4 mentions that if $F$ is the cross entropy loss then $D_{F]$ is the KL divergence. I would recommend using this example throughout Section 3 to illustrate the convex conjugate, the identity in (2), and the results of Proposition 3.1, 3.2, 3.3 for the cross entropy/KL divergence case.\n\n2. Please mention the exact meaning of $X$, $Y$, and the sources of randomness over which the expectation may need to be taken, at the beginning of Section 3.2 before introducing $\\mathbb{E} D[Y||X]$. \n\n3. Since the conditional bias and variance are approimations, the expression in Propsition 4.1 should not be an equality right (LHS is the same as the LHS of (3) but the RHS is an approximation)?\n\n4. The description of the experiments comparing conditional and bootstrapped estimates is a bit vague. Particularly the word partition seems to be used in different contexts. In the context of conditional bias, the authors say \"one can estimate bias and variance by partitioning the training set into disjoint subsets\", while later the authors say \"these partitions allow us to compute the true bias and variance of the algorithm\". It seems like partitioning the entire dataset allows computing of the true bias and variance while each partition is further partitioned into sub-partitions to compute the conditional and bootstrapped estimates. Please clarify if this is the case and please specify the number of sub-partitions (is it equal to \\# trained models?) for the conditional and bootstrapped estimates in each case.\n\n5. Related to the above point, the meaning of \"partition multiple\" in the plots in Appendix C was not clear to me. Please clarify.\n\n6. Please include the relevant expressions to show how the loss of ensembles averaged in the logit space is equivalent to the ensemble diversity regularizer (Remark 5.3). This will also be easier to convey if the KL divergence running example is included in Section 3 as mentioned in point 1 above.\n\n6. Please completely specify experimental conditions for Section 6. Currently the partition sizes, and number of partitions for each experiment are not mentioned. Can you also specify the values of bias, variance, NLL etc for the case when a single model is used? The usefulness of the dual ensemble will be quite limited if it does not outperform a single model.\n\n7. X-axis labels are missing in Fig 4(b), 4(c), 4(d). \n\n8. Please summarize the experimental results more concretely in the last paragraph of Section 7. The current paragraph describes the experiments conducted but does not include all results/conclusions from the experiments.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oEtiPsyqlc", "reviewer": "Reviewer_YLUi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- Natural, elegant extension of previous work on model ensembles and Bregman divergences\n- Intermediate results such as the law of total variance may be of independent interest\n- Well-organized with clear explanations and proofs\n\n### Weaknesses\n- This paper would be strengthened if the contributions included a setting that distinguished itself from what has been covered by previous work, e.g. analyzing another asymmetric Bregman divergence besides KL divergence, or an application in which the dual ensemble outperforms the corresponding primal ensemble\n- A better conclusion would offer directions for future work, in addition to reiterating what was outlined in the introduction.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper derives a dual formulation of the bias-variance decomposition for Bregman divergences [1], and analyzes several properties of model ensembles for cases where typical assumptions (symmetry, joint convexity) do not hold. Namely, for asymmetric Bregman divergences (e.g. KL divergence), primal ensembles are distinct from dual ensembles. For classifiers trained with cross entropy loss, the latter corresponds to averaging logits rather than output probabilities. While dual ensembles keep bias fixed and reduce variance, primal ensembles may either increase or decrease bias while reducing variance. The authors verify their theory with experiments on ensembles of neural network classifiers, and offer insight as to which would perform better in practice.\n\n[1] D. Phau. A Generalized Bias-Variance Decomposition for Bregman Divergences. 2013. http://davidpfau.com/assets/generalized_bvd_proof.pdf", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "### Critical\n- In addition to the related work section, cite relevant work in Section 5 where the results generalize earlier analysis on primal/dual ensembles. \n- Provide additional motivating examples of asymmetric Bregman divergences in ML\n\n### Non-critical\n- Comment on calibration error of primal vs dual ensembles\n- Show an empirical example of a neural network primal ensemble in which bias increases with ensemble size \n- Additional experiments involving other asymmetric Bregman divergences\n- Typo\n    - \"whereas the bias unchanged\" should be \"whereas the bias is unchanged\"\n", "broader_impact_concerns": "The authors could comment on how the bias-variance decomposition for deep network ensembles relates to notions of bias, fairness, and calibration in ML systems, i.e. whether ensembles with lower statistical bias are inherently more fair.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BFhTSFPRUu", "reviewer": "Reviewer_KKeP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First of all, I must admit that I don't have a strong background in the related literature, so my assessment of the novelty may be incorrect.\n\nStrengths\n- The paper provides a novel parameterization that leads to an interesting bias-variance analysis of ensembles.\n- The empirical validations, although restricted to CIFAR10 and CIFAR100, are thorough and well match the theory.\n- The paper is generally well written and provides a nice summary of the related works.\n\nWeakness\n- The experiments only consider the image classification tasks trained with the cross-entropy loss, while the theory in principle covers arbitrary Bregman divergences.\n- At least from the theory, it is not known under what circumstances the primal ensembling reduces the bias in the image classification tasks. Also, most of the experiments are done only for CIFAR10 and CIFAR100, so it is not clear whether this bias reduction is specific to those two datasets or more common in generic image classification tasks.\n- The empirical confirmation is based on conditional biases and variances, not the original biases and variances.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a theoretical tool to analyze the bias-variance tradeoff under general Bregman divergence and studies deep ensembles using it. Specifically, the paper first reveals the dual-reparameterization of the \"central prediction\" term in the generalized Bias-Variance Decomposition (BVD) and extends the law of total variance to the generic notion of variance defined under the dual parameterization. Proceeding further, the paper shows the effect of ensembling on the bias and variances terms, and show that the primal ensembling (the typical ensembling done in the function output space) may increase or decrease the bias unlike the traditional ensembles under MSE loss. Instead, the paper shows that the ensembles done in the dual space actually preserves the bias while reducing the variance as expected in the typical MSE loss. The presented theories are empirically backed up using image classification benchmark datasets.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- Are there more examples of the loss functions being used for deep networks that actually correspond to a special case of the presented framework? If so, it would be nice to see whether the ensembling reduces the bias as in the presented experiments with cross-entropy loss.\n- As noted above, it would be good to see similar experiments on datasets other than CIFAR10 or CIFAR100; e.g., SVHN, Tiny ImageNet, or even ImageNet if affordable.\n- Typically, the deep neural networks are trained with regularization terms such as weight decays. I wonder how this relates with the presented theory; does the cross entropy augmented with weight decay naturally fall into the presented framework?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your submission to TMLR.  The reviewers all felt that the paper was strong enough to be accepted, and that the authors have responded adequately to the concerns of the reviewers with their revisions.
Decision: Accept (poster)