Year: 2021

Abstract:
We empirically show that the test error of deep networks can be estimated by training the same architecture on the same training set but with two different runs of Stochastic Gradient Descent (SGD), and then measuring the disagreement rate between the two networks on unlabeled test data. This builds on — and is a stronger version of — the observation in Nakkiran & Bansal (2020), which requires the runs to be on separate training sets. We further theoretically show that this peculiar phenomenon arises from the well-calibrated nature of ensembles of SGD-trained models. This finding not only provides a simple empirical measure to directly predict the test error using unlabeled test data, but also establishes a new conceptual connection between generalization and calibration.

heading: 1 INTRODUCTION
text: Consider the following intriguing observation made in Nakkiran & Bansal (2020). Train two networks of the same architecture to zero training error on two independently drawn datasets S1 and S2 of the same size. Both networks would achieve a test error (or equivalently, a generalization gap) of about the same value, denoted by . Now, take a fresh unlabeled dataset U and measure the rate of disagreement of the predicted label between these two networks on U . Based on the triangle inequality, one can quickly surmise that this disagreement rate could lie anywhere between 0 and 2 . However, across various training set sizes and for various models like neural networks, kernel SVMs and decision trees, Nakkiran & Bansal (2020) (or N&B’20 in short) report that the disagreement rate not only linearly correlates with the test error , but nearly equals (see first two plots in Fig 1). What brings about this unusual equality? Resolving this open question from N&B’20 could help us identify fundamental patterns in how neural networks make errors. That might further shed insight into generalization and other poorly understood empirical phenomena in deep learning.
In this work, we first identify a stronger observation. Consider two neural networks trained with the same hyperparameters and the same dataset, but with different random seeds (this could take the form e.g., of the data being presented in different random orders and/or by using a different random initialization of the network weights). We would expect the disagreement rate in this setting to be much smaller than in N&B’20, since both models see the same data. Yet, this is not the case: we
observe on the SVHN (Netzer et al., 2011), CIFAR-10/100 (Krizhevsky et al., 2009) datasets, and for variants of Residual Networks (He et al., 2016) and Convolutional Networks (Lin et al., 2013), that the disagreement rate is still approximately equal to the test error (see last two plots in Fig 1), only slightly deviating from the behavior in N&B’20. In fact, while N&B’20 show that the disagreement rate captures significant changes in test error with varying training set sizes, we highlight a much stronger behavior: the disagreement rate is able to capture even minute variations in the test error under varying hyperparameters like width, depth and batch size. Furthermore, we show that under certain training conditions, these properties even hold on many kinds of out-of-distribution data in the PACS dataset (Li et al., 2017), albeit not on all kinds.
The above observations not only raise deeper conceptual questions about the behavior of deep networks but also crucially yield a practical benefit. In particular, our disagreement rate does not require fresh labeled data (unlike the rate in N&B’20) and rather only requires fresh unlabeled data. Hence, ours is a more meaningful and practical estimator of test accuracy (albeit, a slightly less accurate estimate at that). Indeed, unsupervised accuracy estimation is valuable for real-time evaluation of models when test labels are costly or unavailable to due to privacy considerations (Donmez et al., 2010; Jaffe et al., 2015). While there are also many other measures that correlate with generalization without access to even unlabeled test data (Jiang et al., 2018; Yak et al., 2019; Jiang et al., 2020b;a; Natekar & Sharma, 2020; Unterthiner et al., 2020), these require (a) computing intricate proportionality constants and (b) knowledge of the neural network weights/representations. Disagreement, however, provides a direct estimate, and works even with a black-box model, which makes it practically viable when the inner details of the model are unavailable due to privacy concerns.
In the second part of our work, we theoretically investigate these observations. Informally stated, we prove that if the ensemble learned from different stochastic runs of the training algorithm (e.g., across different random seeds) is well-calibrated (i.e., the predicted probabilities are neither overconfident nor under-confident), then the disagreement rate equals the test error (in expectation over the training stochasticity). Indeed, such kinds of SGD-trained deep network ensembles are known to be naturally calibrated in practice (Lakshminarayanan et al., 2017). While we do not prove why calibration holds in practice, the fact the condition in our theorem is empirically satisfied implies that our theory offers a valuable insight into the practical generalization properties of deep networks.
Overall, our work establishes a new connection between generalization and calibration via the idea of disagreement. This has both theoretical and practical implications in understanding generalization and the effect of stochasticity in SGD. To summarize, our contributions are as follows:
1. We prove that for any stochastic learning algorithm, if the algorithm leads to a well-calibrated ensemble, then the ensemble satisfies the Generalization Disagreement Equality1 (GDE) in expectation over the stochasticity. Notably, our theory is general and makes no restrictions on the hypothesis class, the algorithm, the source of stochasticity, or the test distributions (which may be different from the training distribution).
2. We empirically show that for Residual Networks (He et al., 2016), convolutional neural networks (Lin et al., 2013) and fully connected networks, and on CIFAR-10/100 (Krizhevsky et al., 2009) and SVHN (Netzer et al., 2011), GDE is nearly satisfied, even on pairs of networks trained on the same data with different random seeds. This yields a simple method that in practice accurately estimates the test error using unlabeled data in these settings. We also empirically show that the corresponding ensembles are well-calibrated (according to our particular definition of calibration) in practice. We do not, however, theoretically prove why this calibration holds.
3. We present preliminary observations showing that GDE is approximately satisfied even for certain distribution shifts within the PACS (Li et al., 2017) dataset. This implies that the disagreement rate can be a promising estimator even for out-of-distribution accuracy.
4. We empirically find that different sources of stochasticity in SGD are almost equally effective in terms of their effect on GDE and calibration of deep models trained with SGD. We also explore the effect of pre-training on these phenomena.
1Nakkiran & Bansal (2020) refer to this as the Agreement Property, but we use the term Generalization Disagreement Equality to be more explicit and to avoid confusion regarding certain technical differences.

heading: 2 RELATED WORKS
text: Understanding and predicting generalization. Conventionally, generalization in deep learning has been studied through the lens of PAC-learning (Vapnik, 1971; Valiant, 1984). Under this framework, generalization is roughly equivalent to bounding the size of the search space of a learning algorithm. Representative works in this large area of research include Neyshabur et al. (2014; 2017; 2018); Dziugaite & Roy (2017); Bartlett et al. (2017); Nagarajan & Kolter (2019b;c); Krishnan et al. (2019). Several works have questioned whether these approaches are truly making progress toward understanding generalization in overparameterized settings (Belkin et al., 2018; Nagarajan & Kolter, 2019a; Jiang et al., 2020b; Dziugaite et al., 2020). Subsequently, recent works have proposed unconventional ways to derive generalization bounds (Negrea et al., 2020; Zhou et al., 2020; Garg et al., 2021). Indeed, even our disagreement-based estimate marks a significant departure from complexity-based approaches to generalization bounds. Of particular relevance here is Garg et al. (2021) who also leverage unlabeled data. Their bound requires modifying the original training set and then performing a careful early stopping, and is thus inapplicable to (and becomes vacuous for) interpolating models. While our estimate applies to the original training process, our guarantee applies only if we know a priori that the training procedure results in well-calibrated ensembles.
There have been a few other works in unsupervised accuracy estimation such as Donmez et al. (2010); Platanios et al. (2017); Jaffe et al. (2015); Steinhardt & Liang (2016); ElSahar & Gallé (2019); Schelter et al. (2020); Chuang et al. (2020). Since these works focus on out-of-distribution and/or specialized learning settings, they often require extra information about the tasks or specialized training algorithms. In a concurrent work, Chen et al. (2021) make similar discoveries regarding estimating accuracy via agreement by developing a sophisticated ensemble-learning algorithm and make connections to calibration. Overall, their focus is more algorithmic, while our focus is primarily on understanding the nature of this phenomenon. Furthermore, in comparison to all these works which focus on out-of-distribution settings, since we focus on the in-distribution setting, we are able to identify a much simpler approach that works with vanilla-trained blackbox models.
Calibration. Calibration of a statistical model is the property that the probability obtained by the model reflects the true likelihood of the ground truth (Murphy & Epstein, 1967; Dawid, 1982). A well-calibrated model provides an accurate confidence on its prediction which is paramount for high-stake decision making and interpretability. In the context of deep learning, several works (Guo et al., 2017; Lakshminarayanan et al., 2017; Fort et al., 2019; Wu & Gales, 2021; Bai et al., 2021; Mukhoti et al., 2021) have found that while individual neural networks are usually over-confident about their predictions, ensembles of several independently and stochastically trained models tend to be naturally well-calibrated. In particular, there are two types of ensembles that have typically been studied: (a) ensembles where each member is trained by independently sampling training data (with replacement), also called bagging (Breiman, 1996) and (b) ensembles where each member is trained on the same data, but with different random seeds (e.g., different random initialization and data ordering), also called deep ensembles (Lakshminarayanan et al., 2017). The latter typically achieves better accuracy and calibration (Nixon et al., 2020).
On the theoretical side, Allen-Zhu & Li (2020) have studied why deep ensembles outperform individual models in terms of accuracy. Other works studied post-processing methods of calibration (Kumar et al., 2019), established relationships to confidence intervals (Gupta et al., 2020), and derived upper bounds on calibration error either in terms of sample complexity or in terms of the accuracy (Bai et al., 2021; Ji et al., 2021; Liu et al., 2019; Jung et al., 2020; Shabat et al., 2020).
The discussion in our paper complements the above works in multiple ways. First, most works within the machine learning literature focus on top-class calibration, which is concerned only with the confidence level of the top predicted class for each point. The theory in our work, however, requires looking at the confidence level of the model aggregated over all the classes. We then empirically show that SGD ensembles are well-calibrated even in this class-aggregated sense. Furthermore, we carefully investigate what sources of stochasticity result in well-calibrated ensembles. Finally, we provide an exact formal relationship between generalization and calibration via the notion of disagreement, which is fundamentally different from existing theoretical calibration bounds.
Empirical phenomena in deep learning. Broadly, our work falls in the area of research on identifying & understanding empirical phenomena in deep learning (Sedghi et al., 2019), especially in
the context of overparameterized models that interpolate. Some example phenomena include the generalization puzzle (Zhang et al., 2017; Neyshabur et al., 2014), double descent (Belkin et al., 2019; Nakkiran et al., 2020), and simplicity bias (Kalimeris et al., 2019; Arpit et al., 2017).
As stated earlier, we build on N&B’20’s empirical observation of the Generalization Disagreement Equality (GDE) in pairs of models trained on independently drawn datasets. Here we provide a detailed discussion of how our results are distinct from and/or complement their other relevant findings. First, N&B’20 provide a proof of GDE specific to 1-Nearest Neighbor models trained on two independent datasets. Our result does not restrict the hypothesis class, the algorithm or its stochasticity. Second, N&B’20 identify a notion they term as “feature calibration” which can be thought of as a generalized version of calibration. However, the instantiations of feature calibration that they empirically study are significantly different from the standard notion we study. Furthermore, they treat GDE and feature calibration as independent phenomena. Conversely, we show that calibration in the standard sense implies GDE. Finally, in their Appendix D.7.1, N&B’20 do report studies of ensembles where the members are trained on the same data. But this is in an altogether independent context — the GDE-related experiments in N&B’20 are all reported only on ensembles of members trained on different data. Hence, overall, their empirical results do not imply our GDE results.

heading: 3 DISAGREEMENT TRACKS GENERALIZATION ERROR
text: We demonstrate on various datasets and architectures that the test error can be estimated directly by training two runs of SGD and measuring their disagreement on an unlabeled dataset. Importantly, we show that the disagreement rate can track even minute variations in the test error induced by varying hyperparameters. Remarkably, this estimate does not require an independent labeled dataset.
Notations. Let h : X → [K] denote a hypothesis from a hypothesis space H, where [K] denotes the set of K labels {0, 1, . . . ,K − 1}. Let D be a distribution over X × [K]. We will use (X,Y ) to denote the random variable with the distribution D , and (x, y) to denote specific values it can take. Let A be a stochastic training algorithm that induces a distribution HA over hypotheses in H. Let h, h′ ∼ HA denote random hypotheses output by two independent runs of the training procedure. We note that the stochasticity inA could arise from any arbitrary source. This may arise from either the fact that each h is trained on a random dataset drawn from D or even a completely different distribution D ′. The stochasticity could also arise from merely a different random initialization or data ordering. Next, we denote the test error and disagreement rate for hypotheses h, h′ ∼HA by:
TestErrD(h) , ED [1[h(X) 6= Y ]] and DisD(h, h′) , ED [1[h(X) 6= h′(X)]] . (1)
Let h̃ denote the “ensemble” corresponding to h ∼HA. In particular, define
h̃k(x) , EHA [1[h(x) = k]] (2)
to be the probability value (between [0, 1]) given by the ensemble h̃ for the kth class. Note that the output of h̃ is not a one-hot value based on plurality vote.
Main Experimental Setup. We report our main observations on variants of Residual Networks, convolutional neural networks and fully connected networks trained with Momentum SGD on CIFAR-10/100, and SVHN. Each variation of the ResNet has a unique hyperparameter configuration (See Appendix B.1 for details) and all models are (near) interpolating. For each hyperparameter setting, we train two copies of models which experience two independent draws from one or more sources of stochasticity, namely 1. random initialization (denoted by Init) and/or 2. ordering of a fixed training dataset (Order) and/or 3. different (disjoint) training data (Data). We will use the term Diff to denote whether a source of stochasticity is “on”. For example, DiffInit means that the two models have different initializations but see the same data in the same order. In DiffOrder, models share the same initialization and see the same data, but in different orders. In DiffData, the models share the initialization, but see different data. In AllDiff, the two models differ in both data and in initialization (If the two models differ in data, the training data is split into two disjoint halves to ensure no overlap.). The disagreement rate between a pair of models is computed as the proportion of the test data on which the (one-hot) predictions of the two models do not match.
Observations. We provide scatter plots of test error of the first run (y) vs disagreement error between the two runs (x) for CIFAR-10, SVHN and CIFAR-100 in Figures 1, 2 and 3 respectively (and for CNNs on CIFAR-10 in Fig 10). Naively, we would expect these scatter plots to be arbitrarily distributed anywhere between y = 0.5x (if the errors of the two models are disjoint) and x = 0 (if the errors are identical). However, in all these scatter plots, we observe that test error and disagreement error lie very close to the diagonal line y = x across different sources of stochasticity, while only slightly deviating in DiffInit/Order. In particular, in AllDiff and DiffData, the points typically lie between y = x and y = 0.9x while in DiffInit and DiffOrder, the disagreement rate drops slightly (since the models are trained on the same data) and so the points typically lie between y = x and y = 1.3x. We quantify correlation via the R2 coefficient and Kendall’s Ranking coefficient (tau) reported on top of each scatter plot. Indeed, we observe that these quantities are high in all the settings, generally above 0.85. If we focus only on the data-augmented or the non-data-augmented models, R2 tends to range a bit lower, around 0.7 and τ around 0.6 (see Appendix C.8).
The positive observations about DiffInit and DiffOrder are surprising for two reasons. First, when the second network is trained on the same dataset, we would expect its predictions to be largely aligned with the original network — naturally, the disagreement rate would be negligible, and the equality observed in N&B’20 would no longer hold. Furthermore, since we calculate the disagreement rate without using a fresh labeled dataset, we would expect disagreement to be much less predictive of test error when compared to N&B’20. Our observations defy both these expectations.
There are a few more noteworthy aspects. In the low data regime where the test error is high, we would expect the models to be much less well-behaved. However, consider the CIFAR-100 plots (Fig 3), and additionally, the plots in Fig 4 where we train on CIFAR-10 with just 2000 training points. In both settings the network suffers an error as high as 0.5 to 0.6. Yet, we observe a behavior similar to the other settings (albeit with some deviations) — the scatter plot lies in y = (1 ± 0.1)x (for AllDiff and DiffData) and in y = (1 ± 0.3)x (for DiffInit/Order), and the correlation metrics are high. Similar results were established in N&B’20 for AllDiff and DiffData.
Finally, it is important to highlight that each scatter plot here corresponds to varying certain hyperparameters that cause only mild variations in the test error. Yet, the disagreement rate is able to capture those variations in the test error. This is a stronger version of the finding in N&B’20 that disagreement captures larger variations under varying dataset size.
Effect of distribution shift and pre-training We study these observations in the context of the PACS dataset, a popular domain generalization benchmark with four distributions, Photo (P in short), Art (A), Cartoon (C) and Sketch (S), all sharing the same 7 classes. On any given domain, we train pairs of ResNet50 models. Both models are either randomly initialized or ImageNet (Deng et al., 2009) pre-trained. We then evaluate their test error and disagreement on all the domains. As we see in Fig 5, the surprising phenomenon here is that there are many pairs of source-target domains where GDE is approximately satisfied despite the distribution shift. Notably, for pre-trained models, with the exception of three pairs of source-target domains (namely, (P, C), (P, S), (S, P)), GDE is satisfied approximately. The other notable observation is that under distribution shift, pre-trained models can satisfy GDE, and often better than randomly initialized models. This is counter-intuitive, since we would expect pre-trained models to be strongly predisposed towards specific kinds of features, resulting in models that disagree rarely. See Appendix B.1 for hyperparameter details.

heading: 4 CALIBRATION IMPLIES THE GDE
text: We now formalize our main observation, like it was formalized in N&B’20 (although with minor differences to be more general). In particular, we define “the Generalization Disagreement Equality” as the phenomenon that the test error equals the disagreement rate in expectation over h ∼HA. Definition 4.1. The stochastic learning algorithm A satisfies the Generalization Disagreement Equality (GDE) on the distribution D if,
Eh,h′∼HA [DisD(h, h′)] = Eh∼HA [TestErrD(h)]. (3)
Note that the definition does not imply that the equality holds for each pair of h, h′ (which we observed empirically). However, for simplicity, we will stick to the above “equality in expectation” as it captures the essence of the underlying phenomenon while being easier to analyze. To motivate why proving this equality is non-trivial, let us look at the most natural hypothesis that N&B’20 identify. Imagine that all datapoints (x, y) are one of two types: (a) the datapoint is so “easy” that w.p. 1 over h ∼HA, h(x) = y (b) the datapoint is so “hard” that h(x) corresponds to picking a label uniformly at random. In such a case, with a simple calculation, one can see that the above equality would hold not just in expectation over D , but even point-wise: for each x, the disagreement on x in expectation over HA would equal the error on x in expectation over HA (namely (K − 1)/K if
x is hard, and 0 if easy). Unfortunately, N&B’20 show that in practice, a significant fraction of the points have disagreement larger than error and another fraction have error larger than disagreement (see Appendix C.4). Surprisingly though, there is a delicate balance between these two types of points such that overall these disparities cancel each other out giving rise to the GDE.
What could create this delicate balance? We identify that this can arise from the fact that the ensemble h̃ is well-calibrated. Informally, a well-calibrated model is one whose output probability for a particular class (i.e., the model’s “confidence”) is indicative of the probability that the ground truth class is indeed that class (i.e., the model’s “accuracy”). There are many ways in which calibration can be formalized. Below, we provide a particular formalism called class-wise calibration.
Definition 4.2. The ensemble model h̃ satisfies class-wise calibration on D if for any confidence value q ∈ [0, 1] and for any class k ∈ [K],
p(Y = k | h̃k(X) = q) = q. (4)
Next, we show that if the ensemble is class-wise calibrated on the distribution D , then GDE does hold on D . Note however that shortly we show a more general result where even a weaker notion of calibration is sufficient to prove GDE. But since this stronger notion of calibration is easier to understand, and the proof sketch for this captures the key intuition of the general case, we will focus on this first in detail. It is worth emphasizing that besides requiring well-calibration on the (test) distribution, all our theoretical results are general. We do not restrict the hypothesis class (it need not necessarily be neural networks), or the test/training distribution (they can be different), or where the stochasticity comes from (it need not necessarily come from the random seed or the data).
Theorem 4.1. Given a stochastic learning algorithm A, if its corresponding ensemble h̃ satisfies class-wise calibration on D , then A satisfies the Generalization Disagreement Equality on D .
Proof. (Sketch for binary classification. Details for full multi-class classification are deferred to App. A.2.) Let Xq correspond to a “confidence level set” in that Xq = {X ∈ X | h̃0(X) = q}. Our key idea is to show that for a class-wise calibrated ensemble, GDE holds within each confidence level set i.e., for each q ∈ [0, 1], the (expected) disagreement rate equals test error for the distribution D restricted to the support Xq . Since X is a combination of these level sets, it automatically follows that GDE holds over D . It is worth contrasting this proof idea with the easy-hard explanation which requires showing that GDE holds point-wise, rather than confidence-level-set-wise.
Now, let us calculate the disagreement on Xq . For any fixed x in Xq , the disagreement rate in expectation over h, h′ ∼HA corresponds to q(1−q)+(1−q)q = 2q(1−q). This is simply the sum of the probability of the events that h predicts 0 and h′ predicts 1, and vice versa. Next, we calculate the test error on Xq . At any x, the expected error equals h̃1−y(x). From calibration, we have that exactly q fraction of Xq has the true label 0. On these points, the error rate is h̃1(x) = 1− q. On the remaining 1− q fraction, the true label is 1, and hence the error rate on those is h̃0(x) = q. The total error rate across both the class 0 and class 1 points is therefore q(1− q)+(1− q)q = 2q(1− q).
Intuition. Even though the proof is fairly simple, it may be worth demystifying it a bit further. In short, a calibrated classifier “knows” how much error it commits in different parts of the distribution i.e., over points where it has a confidence of q, it commits an expected error of 1 − q. With this in mind, it is easy to see why it is even possible to predict the test error without knowing the test labels: we can simply average the confidence values of the ensemble to estimate test accuracy. The expected disagreement error provides an alternative but less obvious route towards estimating test performance. The intuition is that within any confidence level set of a calibrated ensemble, the marginal distribution over the ground truth labels becomes identical to the marginal distribution over the one-hot predictions sampled from the ensemble. Due to this, measuring the expected disagreement of the ensemble against itself becomes equivalent to measuring the expected disagreement of the ensemble against the ground truth. The latter is nothing but the ensemble’s test error.
What is still surprising though is that in practice, we are able to get away with predicting test error by computing disagreement for a single pair of ensemble members — and this works even though an ensemble of two models is not well-calibrated, as we will see later in Table 1. This suggests that the variance of the disagreement and test error (over the stochasticity of HA) must be unusually small; indeed, we will empirically verify this in Table 1. In Corollary A.1.1, we present some preliminary discussion on why the variance could be small, leaving further exploration for future work.

heading: 4.1 A MORE GENERAL RESULT: CLASS-WISE TO CLASS-AGGREGATED CALIBRATION
text: We will now show that GDE holds under a more relaxed notion of calibration, which holds “on average” over the classes rather than individually for each class. Indeed, we demonstrate in a later section (see Appendix C.7) that this averaged notion of calibration holds more gracefully than class-wise calibration in practice. Recall that in class-wise calibration we look at the conditional probability p(Y = k | h̃k(X) = q) for each k. Here, we will take an average of these conditional probabilities by weighting the kth probability by p(h̃k(X) = q). The result is the following definition:
Definition 4.3. The ensemble h̃ satisfies class-aggregated calibration on D if for each q ∈ [0, 1],∑K−1 k=0 p(Y =k,h̃k(X)=q)∑K−1
k=0 p(h̃k(X)=q) = q. (5)
Intuition. The denominator here corresponds to the points where some class gets confidence value q; the numerator corresponds to the points where some class gets confidence value q and that class also happens to be the ground truth. Note however both the proportions involve counting a point x multiple times if h̃k(x) = q for multiple classes k. In Appendix A.5, we discuss the relation between this new notion of calibration to existing definitions. In Appendix A.1 Theorem A.1, we show that the above weaker notion of calibration is sufficient to show GDE. The proof of this theorem is a nontrivial generalization of the argument in the proof sketch of Theorem 4.1, and Theorem 4.1 follows as a straightforward corollary since class-wise calibration implies class-aggregated calibration.
Deviation from calibration. For generality, we would like to consider ensembles that do not satisfy class-aggregated calibration precisely. How much can a deviation from calibration hurt GDE? To answer this question, we quantify calibration error as follows:
Definition 4.4. The Class Aggregated Calibration Error (CACE) of an ensemble h̃ on D is CACED(h̃) , ∫ q∈[0,1] ∣∣∣∑k p(Y =k,h̃k(X)=q)∑ k p(h̃k(X)=q) − q ∣∣∣ ·∑k p(h̃k(X) = q)dq. (6)
In other words, for each confidence value q, we look at the absolute difference between the left and right hand sides of Definition 4.3, and then weight the difference by the proportion of instances where a confidence value of q is achieved. It is worth keeping in mind that, while the absolute difference term lies in [0, 1], the weight terms alone would integrate to a value of K. Therefore, CACED(h̃) can lie anywhere in the range [0,K]. Note that CACE is different from the “expected calibration error (ECE)” (Naeini et al., 2015; Guo et al., 2017) commonly used in the machine learning literature, which applies only to top-class calibration.
We show below that GDE holds approximately when the calibration error is low (and naturally, as a special case, holds perfectly when calibration error is zero). The proof is deferred to Appendix A.3.
Theorem 4.2. For any algorithm A, |EHA [DisD(h, h′)]− EHA [TestErrD(h)]| ≤ CACED(h̃).
Remark. All our results hold more generally for any probabilistic classifier h̃. For example, if h̃was an individual calibrated neural network whose predictions are given by softmax probabilities, then GDE holds for the neural network itself: the disagreement rate between two independently sampled one-hot predictions from that network would equal the test error of the softmax predictions.

heading: 5 EMPIRICAL ANALYSIS OF CLASS-AGGREGATED CALIBRATION
text: Empirical evidence for theory. As stated in the introduction, it is a well-established observation that ensembles of SGD trained models provide good confidence estimates (Lakshminarayanan et al., 2017). However, typically the output of these ensembles correspond to the average softmax probabilities of the individual models, rather than an average of the top-class predictions. Our theory is however based upon the latter type of ensembles. Furthermore, there exists many different evaluation metrics for calibration in literature, while we are particularly interested in the precise definition we have in Definition 4.3. We report our observations keeping these considerations in mind.
In Figure 6, 7 and 8, we show that SGD ensembles do nearly satisfy class-aggregated calibration for all the sources of stochasticity we have considered. In each plot, we report the conditional
probability in the L.H.S of Definition 4.3 along the y axis and the confidence value q along the x axis. We observe that the plot closely follows the x = y line. In fact, we observe that calibration holds across different sources of stochasticity. We discuss this aspect in more detail in Appendix A.6.
For a more precise quantification of how well calibration captures GDE, we also look at our notion of calibration error, namely CACE, which also acts as an upper bound on the difference between the test error and the disagreement rate. We report CACE averaged over 100 models in Table 1 (for CIFAR-10) and Table 3 (for CIFAR-100). Most importantly, we observe that the CACE across different stochasticity settings correlates with the actual gap between the test error and the disagreement rate. In particular, CACE for AllDiff/DiffData are about 2 to 3 times smaller than that for DiffInit/Order, paralleling the behavior of |TestErr− Dis| in these settings.
Caveats. While we believe our work provides a simple theoretical insight into how calibration leads to GDE, there are a few gaps that we do not address. First, we do not provide a theoretical characterization of when we can expect good calibration (and hence, when we can expect GDE to hold). Next, our theory and the supporting experiments shed insight into why GDE holds in expectation over training stochasticity. However, it is surprising that in practice the disagreement rate (and the test error) for a single pair of models lies close to this expectation. This occurs even though two-model-ensembles are poorly calibrated (see Tables 1 and 3). Finally, while CACE is an upper bound on the deviation from GDE, in practice CACE is only a loose bound, which could either imply a mere lack of data/models or perhaps that our theory can be further refined.

heading: 6 CONCLUSION
text: Building on Nakkiran & Bansal (2020), we observe that remarkably, two networks trained on the same dataset, tend to disagree with each other on unlabeled data nearly as much as they disagree with the ground truth. We’ve also theoretically shown that this property arises from the fact that SGD ensembles are well-calibrated. Broadly, these findings contribute to the larger pursuit of identifying and understanding empirical phenomena in deep learning. Future work could shed light on why different sources of stochasticity surprisingly have a similar effect on calibration. It is also important for future work in uncertainty estimation and calibration to develop a precise and exhaustive characterization of when calibration and GDE would hold. On a different note, we hope our work inspires other novel ways to leverage unlabeled data to estimate generalization and also further cross-pollination of ideas between research in generalization and calibration.

heading: A APPENDIX: ADDITIONAL THEORETICAL DISCUSSION

heading: A.1 PROOF OF THEOREM A.1
text: We will now prove Theorem A.1 which states that if the ensemble h̃ satisfies class-aggregated calibration, then the expected test error equals the expected disagreement rate.
The basic intuition behind why class-aggregated calibration implies GDE is similar to the argument for class-wise calibration — we can similarly argue that within a confidence level set, the distribution over the predicted classes matches the distribution over the ground truth labels; therefore, measuring disagreement of the ensemble against the ensemble itself boils down to measuring disagreement against the ground truth. However, the confidence level sets here can involve counting the same data point multiple times, and this nuance needs to be handled carefully as can be seen from the proof in the appendix.
Theorem A.1. Given a stochastic learning algorithm A, if its corresponding ensemble h̃ satisfies class-aggregated calibration (Definition 4.3) on D , then A satisfies GDE on D (Definition 4.1).
Proof. Before we delve into the details of the proof, we will outline the high-level proof idea which is similar to that proof sketch presented in Section 4. First, we express the expected test error in terms of an integral over the confidence values (Eq 23) and then plug in the definition for classaggregated calibration to get Eq 25. For expected disagreement rate, we can analogously express it as an integral over the confidence values, because the models are independent and the expectation naturally produces the confidence values. Note that the calibration assumption is not used for deriving the expected disagreement rate and the final result (Eq 44) is equal to the expected test error (Eq 25), which completes our proof.
We’ll first simplify the expected test error and then proceed to simplifying the expected disagreement rate to the same quantity.
Test Error Recall that the expected test error (which we will denote as ETE for short) corresponds to EHA [p(h(X) 6= Y | h)].
ETE , Eh∼HA [p(h(X) 6= Y | h)] (7) = Eh∼HA [ E(X,Y )∼D [1[h(X) 6= Y ]] ] (8)
= E(X,Y )∼D [EHA [1[h(X) 6= Y ]]] (exchanging expectations by Fubini’s theorem) (9) = E(X,Y )∼D [ 1− h̃Y (X) ] . (10)
For our further simplifications, we’ll explicitly deal with integrals rather than expectations, so we get,
ETE = K−1∑ k=0 ∫ x (1− h̃k(x))p(X = x, Y = k)dx. (11)
We’ll also introduce h̃(X) as a r.v. as,
ETE = ∫ q∈∆K K−1∑ k=0 ∫ x (1− h̃k(x))p(X = x, Y = k, h̃(X) = q)dxdq. (12)
Over the next few steps, we’ll get rid of the integral over x. First, splitting the joint distribution over the three r.v.s by conditioning on the latter two,
ETE = ∫ q∈∆K K−1∑ k=0 p(Y = k, h̃(X) = q) ∫ x (1− h̃k(x)︸ ︷︷ ︸ =qk )p(X = x | Y = k, h̃(X) = q)dxdq (13)
= ∫ q∈∆K K−1∑ k=0 p(Y = k, h̃(X) = q) ∫ x (1− qk)︸ ︷︷ ︸ constant w.r.t ∫ x p(X = x | h̃(X) = q, Y = k)dxdq
(14)
= ∫ q∈∆K K−1∑ k=0 p(Y = k, h̃(X) = q)(1− qk) ∫ x
p(X = x | h̃(X) = q, Y = k)dx︸ ︷︷ ︸ =1 dq (15)
= ∫ q∈∆K K−1∑ k=0︸ ︷︷ ︸
swap
p(Y = k, h̃(X) = q)(1− qk)dq. (16)
= K−1∑ k=0 ∫ q∈∆K p(Y = k, h̃(X) = q)(1− qk)dq. (17)
(18)
In the next few steps, we’ll simplify the integral over q by marginalizing over all but the kth dimension. First, we rewrite the joint distribution of h̃(X) in terms of its K components. For any k, let h̃−k(X) and q−k denote theK−1 dimensions of both vectors excluding their kth dimension. Then, ETE = K−1∑ k=0 ∫ qk ∫ q−k p(h̃−k(X) = q−k | Y = k, h̃k(X) = qk) p(Y = k, h̃k(X) = qk)(1− qk)︸ ︷︷ ︸ constant w.r.t ∫ q−k dq−kdqk
(19)
= K−1∑ k=0 ∫ qk p(Y = k, h̃k(X) = qk)(1− qk) ∫ q−k
p(h̃−k(X) = q−k | Y = k, h̃k(X) = qk)dq−k︸ ︷︷ ︸ =1 dqk
(20)
= K−1∑ k=0 ∫ qk p(Y = k, h̃k(X) = qk)(1− qk)dqk. (21)
Rewriting qk as just q, ETE = K−1∑ k=0 ∫ q∈[0,1]︸ ︷︷ ︸
swap
p(Y = k, h̃k(X) = q)(1− q)dq (22)
= ∫ q∈[0,1] K−1∑ k=0 p(Y = k, h̃k(X) = q)(1− q)dq. (23)
Finally, we have from the calibration in aggregate assumption that ∑K−1
k=0 p(Y = k, h̃k(X) = q) = q ∑K−1
k=0 p(h̃k(X) = q) (Definition 4.3). So, applying this, we get
= ∫ q∈[0,1] q K−1∑ k=0 p(h̃k(X) = q)(1− q)dq. (24)
Rearranging,
ETE = ∫ q∈[0,1] q(1− q) K−1∑ k=0 p(h̃k(X) = q)dq. (25)
Disagreement Rate The expected disagreement rate (denoted by EDR in short) is given by the probability that two i.i.d samples from h̃ disagree with each other over draws of input from D , taken in expectation over draws from HA. That is,
EDR , Eh,h′∼HA [p(h(X) 6= h′(X) | h, h′)] (26) = Eh,h′∼HA [ E(X,Y )∼D [1[h(X) 6= h′(X)]] ] (27)
= E(X,Y )∼D [Eh,h′∼HA [1[h(X) 6= h′(X)]]] (exchanging expectations by Fubini’s Theorem) (28)
Over the next few steps, we’ll write this in terms of h̃ rather than h and h′.
EDR =E(X,Y )∼D [ Eh,h′∼HA [ K−1∑ k=0 1[h(X) = k] (1− 1[h′(X) = k]) ]] (29)
=E(X,Y )∼D [ K−1∑ k=0 Eh,h′∼HA [1[h(X) = k] (1− 1[h′(X) = k])] ] (swapping the expectation and the summation)
(30)
=E(X,Y )∼D [ K−1∑ k=0 p(h(X) = k | X) (1− p(h′(X) = k | X)) ] (since h and h′ are i.i.d samples from HA)
(31)
=E(X,Y )∼D [ K−1∑ k=0 h̃k(X)(1− h̃k(X)) ] . (32)
From here, we’ll deal with integrals instead of expectations.
EDR = ∫ x K−1∑ k=0 h̃k(x)(1− h̃k(x))p(X = x)dx. (33)
Let us introduce the random variable h̃(X) as,
EDR = ∫ q∈∆K ∫ x K−1∑ k=0 h̃k(x)(1− h̃k(x))p ( X = x, h̃(X) = q ) dxdq. (34)
In the next few steps, we’ll get rid of the integral over x. First, we split the joint distribution as,
EDR = ∫ q∈∆K p ( h̃(X) = q )∫ x K−1∑ k=0
h̃k(x)(1− h̃k(x))︸ ︷︷ ︸ apply h̃k(x)=qk
p ( X = x | h̃(X) = q ) dxdq. (35)
= ∫ q∈∆K p ( h̃(X) = q )∫ x
K−1∑ k=0︸︷︷︸
bring to the front
qk(1− qk)p ( X = x | h̃(X) = q ) dxdq. (36)
= K−1∑ k=0 ∫ q∈∆K p ( h̃(X) = q )∫ x qk(1− qk)︸ ︷︷ ︸ constant w.r.t ∫ x p ( X = x | h̃(X) = q ) dxdq. (37)
= K−1∑ k=0 ∫ q∈∆K p ( h̃(X) = q ) qk(1− qk) ∫ x p ( X = x | h̃(X) = q ) dx︸ ︷︷ ︸
1
dq. (38)
= K−1∑ k=0 ∫ q∈∆K p ( h̃(X) = q ) qk(1− qk)dq. (39)
Next, we’ll simplify the integral over q by marginalizing over all but the kth dimension.
EDR = K−1∑ k=0 ∫ qk ∫ q−k p(h̃−k(X) = q−k | h̃k(X) = qk) p(h̃k(X) = qk)qk(1− qk)︸ ︷︷ ︸ constant w.r.t. ∫ q−k dq−kdqk (40)
= K−1∑ k=0 ∫ qk p(h̃k(X) = qk)qk(1− qk) ∫ q−k
p(h̃−k(X) = q−k | h̃k(X) = qk)dq−k︸ ︷︷ ︸ =1 dqk (41)
= K−1∑ k=0 ∫ qk p ( h̃k(X) = qk ) qk(1− qk)dqk. (42)
Rewriting qk as just q,
EDR = K−1∑ k=0 ∫ q∈[0,1]︸ ︷︷ ︸
swap
p ( h̃k(X) = q ) q(1− q)dq (43)
= ∫ q∈[0,1] q(1− q) K−1∑ k=0 p ( h̃k(X) = q ) dq. (44)
This is indeed the same term as Eq 25, thus completing the proof.

heading: A.2 PROOF OF THEOREM 4.1 AND VARIANCE OF DISAGREEMENT
text: Since Theorem 4.1 is a special case of Theorem A.1, we can easily prove the former:
Proof. Observe that if h̃ satisfies the class-wise calibration condition as in Definition 4.2, it must also satisfy class-aggregated calibration.
p ( Y = k | h̃k(X) = q ) = q ∀k (45)
=⇒ ∑K−1
i=1 p(Y = k, h̃k(X) = q)∑K−1 i=1 p(h̃k(X) = q) =
∑K−1 i=1 p ( Y = k | h̃k(X) = q ) p(h̃k(X) = q)∑K−1
i=1 p(h̃k(X) = q) = q (46)
Then, we can invoke Theorem A.1 to claim that GDE holds.
The theorem above shows that in expectation, the disagreement of independent pairs of hypotheses is equal to the test error of a single hypothesis. Now, we will drive an upper bound on the variance of the distribution. This result corroborates the empirical observation where we can use as low as a single pair of independent models to accurate estimate the test error. Corollary A.1.1. If GDE holds and there exists κ ∈ [ 1 2 , 1 ]
such that, for all h, h′ in the support of HA, Dis(h, h′) ≤ κ (TestErr(h) + TestErr(h′)) , then
Varh,h′∼HA (Dis(h, h ′)) ≤ 2κ2Varh∼HA (TestErr(h)) +
( 4κ2 − 1 ) ETE2.
Proof. First we write the expression for the exact variance of the disagreement:
Varh,h′∼HA (Dis(h, h ′)) = Eh,h′∼HA
[ Dis(h, h′)2 ] − EDR2. (47)
By the assumption: Eh,h′∼HA [ Dis(h, h′)2 ] (48)
≤ κ2Eh,h′∼HA [ (TestErr(h) + TestErr(h′)) 2 ]
(49) ≤ κ2Eh,h′∼HA [ TestErr(h)2 + 2TestErr(h)TestErr(h′) + TestErr(h′)2 ] . (50)
Since h and h′ are independent and identically distributed, the expectation of the cross term is equal to the product of each expectation and the second moments are equal:
Eh,h′∼HA [ Dis(h, h′)2 ] ≤ κ2 ( 2Eh∼HA [ TestErr(h)2 ] + 2ETE2 ) (51)
= κ2 ( 2Eh∼HA [ TestErr(h)2 ] − 2ETE2 + 2ETE2 + 2ETE2 ) (52)
= κ2 ( 2Varh∼H (TestErr(h)) + 4ETE2 ) . (53)
Substituting the inequality back to (47):
Varh,h′∼HA (Dis(h, h ′)) ≤ κ2 ( 2Varh∼H (TestErr(h)) + 4ETE2 ) − EDR2. (54)
By the GDE, we know that ETE = EDR:
Varh,h′∼HA (Dis(h, h ′)) ≤ 2κ2Varh∼H (TestErr(h)) +
( 4κ2 − 1 ) ETE2. (55)
Remark. This corollary characterizes the worst-case behavior of the disagreement error’s variance and relates it to the expectation and variance of the test error distribution over HA. Recent works (Neal et al., 2018; Nakkiran et al., 2020) have shown that the classical bias-variance trade-off exhibits unusual behaviors in the overparameterized regime where the model contains much more parameters than the number of data points. In particular, Neal et al. (2018) shows that the variance actually decreases as the number of parameters increases, which implies that the first term of the RHS in (55) is negligible. Empirically, this is supported by the first columns of Table 1 and Table 3, where we show the variance of the test error is small.
κ represents the amount of structure present in HA. If κ = 1, the assumption Dis(h, h′) ≤ TestErr(h) + TestErr(h′) is always true, since it follows directly from the triangle inequality; however, this would imply that there exists a pair of hypotheses in the support of HA that achieve the largest possible disagreement rate. Empirical evidence (Nakkiran & Bansal, 2020) indicates that this may not the case. Instead, deep models make mistakes in highly structured manner, suggesting κ is much smaller than 1 in practice. On the other hand, if κ = 12 , the GDE holds pointwise for every hypotheses pair (up to the small stochasticity present in the distribution of TestErr). This is also unlikely since it would imply the disagreement rate variance is at most only a half of test error variance. In practice, Table 1 and 3 show that the variance of disagreement is approximately equal to the variance of the test error, suggesting that κ falls somewhere between 12 and 1. This supports the hypothesis that the models make errors in a structured manner which gives rise to the observed phenomena.

heading: A.3 DISAGREEMENT PROPERTY UNDER DEVIATION FROM CALIBRATION
text: Recall from the main paper that we quantified deviation from class-aggregated calibration in terms of CACE. Below, we provide the proof of Theorem 4.2, which shows that GDE holds approximately when CACE is low.
Proof. Recall from the proof of Theorem A.1 that the expected test error (ETE) satisfies:
ETE = ∫ q∈[0,1] K−1∑ k=0
p(Y = k, h̃k(X) = q)︸ ︷︷ ︸ subtract and add a q ∑K−1 k=0 p(h̃k(X) = q)
(1− q)dq
= ∫ q∈[0,1] ( K−1∑ k=0 p(Y = k, h̃k(X) = q)− q K−1∑ k=0 p(h̃k(X) = q) ) (1− q)dq
+ ∫ q∈[0,1] q K−1∑ k=0 p(h̃k(X) = q)(1− q)dq.
Recall that the second term on R.H.S is equal to the expected disagreement rate EDR. Therefore,
|ETE− EDR| = ∫ q∈[0,1] ( K−1∑ k=0 p(Y = k, h̃k(X) = q)− q K−1∑ k=0 p(h̃k(X) = q) ) (1− q)dq.
Multiplying and dividing the inner term by ∑K−1
k=0 p(h̃k(X) = q),
|ETE− EDR| = ∣∣∣∣∣ ∫ q∈[0,1] (∑K−1 k=0 p(Y = k, h̃k(X) = q)∑K−1 k=0 p(h̃k(X) = q) − q ) K−1∑ k=0 p(h̃k(X) = q)(1− q)dq ∣∣∣∣∣ ≤ ∫ q∈[0,1] ∣∣∣∣∣ ∑K−1 k=0 p(Y = k, h̃k(X) = q)∑K−1 k=0 p(h̃k(X) = q) − q ∣∣∣∣∣ K−1∑ k=0 p(h̃k(X) = q) (1− q)︸ ︷︷ ︸ ≤1 dq
≤ ∫ q∈[0,1] ∣∣∣∣∣ ∑K−1 k=0 p(Y = k, h̃k(X) = q)∑K−1 k=0 p(h̃k(X) = q) − q ∣∣∣∣∣ K−1∑ k=0 p(h̃k(X) = q)dq
= CACE(h̃).
Note that it is possible to consider a more refined definition of CACE that yields a tighter bound on the gap. In particular, in the last series of equations, we can leave the 1 − q as it is, without upper bounding by 1. In practice, this tightens CACE by upto a value of 2. We however avoid considering the refined definition as it is less intuitive as an error metric.

heading: A.4 CALIBRATION IS NOT A NECESSARY CONDITION FOR GDE
text: Theorem A.1 shows that calibration implies GDE. Below, we show that the converse is not true. That is, if the ensemble satisfies GDE, it is not necessarily the case that it satisfies class-aggregated calibration. This means that calibration and GDE are not equivalent phenomena, but rather only that calibration may lead to the latter.
Proposition A.1. For a stochastic algorithm A to satisfy GDE, it is not necessary that its corresponding ensemble h̃ satisfies class-aggregated calibration.
Proof. Consider an example where h̃ assigns a probability of either 0.1 or 0.2 to class 0. In particular, assume that with 0.5 probability over the draws of (x, y) ∼ D , h̃0(x) = 0.1 and with 0.5 probability, h̃0(x) = 0.2. The expected disagreement rate (EDR) of this classifier is given by ED [ 2h̃0(x)h̃1(x) ] = 2 ( 0.1·0.9+0.2·0.8
2
) = 0.25.
Now, it can be verified that the binary classification setting, class-aggregated and class-wise calibration are identical. Therefore, letting p(Y = 0 | h̃0(X) = 0.1) , 1 and p(Y = 0 | h̃0(X) = 0.2) , 2, our goal is to show that it is possible for 1 6= 0.1 or 2 6= 0.2 and still have the expected test error (ETE) equal the EDR of 0.25. Now, the ETE on D conditioned on h̃0(x) = 0.1 is given by (0.1(1− 1) + 0.9 1) and on h̃0(x) = 0.2 is given by (0.2(1− 2) + 0.8 1). Thus, the ETE on D is given by 0.15 + 0.5(0.8 1 + 0.6 2). We want 0.15 + 0.5(0.8 1 + 0.6 2) = 0.25 or in other words, 0.8 1 + 0.6 2 = 0.2.
Observe that while 1 = 0.1 and 2 = 0.2 is one possible solution where h̃ would satisfy classwise calibration/class-aggregated calibration, there are also infinitely many other solutions for this equality to hold (such as say 1 = 0.25 and 2 = 0) where calibration does not hold. Thus, classaggregated/class-wise calibration is just one out of infinitely many possible ways in which h̃ could be configured to satisfy GDE.

heading: A.5 COMPARING CACE TO EXISTING NOTIONS OF CALIBRATION.
text: Calibration in machine learning literature (Guo et al., 2017; Nixon et al., 2019) is often concerned only with the confidence level of the top predicted class for each point. While top-class calibration is weaker than class-wise calibration, it is neither stronger nor weaker than class-aggregated calibration. Class-wise calibration is a notion of calibration that has appeared originally under different names in Zadrozny & Elkan; Wu & Gales (2021). On the other hand, the only closest existing notion to class-aggregated calibration seems to be that of static calibration in Nixon et al. (2019), where it is only indirectly defined. Another existing notion of calibration for the multi-class setting is that of strong calibration (Vaicenavicius et al., 2019; Widmann et al., 2019) which evaluates the accuracy of the model conditioned on h̃(X) taking a particular value in the K-simplex. This is significantly stronger than class-wise calibration since this would require about exp(K) many equalities to hold rather than just the K equalities in Definition 4.2.

heading: A.6 THE EFFECT OF DIFFERENT STOCHASTICITY.
text: Compared to AllDiff/DiffData, DiffInit/Order is still well-calibrated, with only slight deviations. Why is varying the training data almost as effective in calibration as varying the random seed? One might propose the following natural hypothesis in the context of DiffOrder vs DiffData. In the first few steps of SGD, the data seen under two different reorderings are likely to not intersect at all, and hence the two trajectories would initially behave as though being trained on two independent datasets. Further, if the first few steps largely determine the kind of minimum that the training falls into, then it is reasonable to expect that the stochasticity in data and in ordering both have the same effect on calibration. However, this hypothesis falls apart when we try to understand why two runs with the same ordering and different initialization (DiffInit) exhibits the same effect as DiffData. Indeed, Fort et al. (2019) have empirically shown that two such SGD runs explore diverse regions in the function space. Hence, we believe that there is a more nuanced reason behind why different types of stochasticity have a similar effect on ensemble calibration. One promising hypothesis for this could be the multi-view hypothesis from Allen-Zhu & Li (2020), which show that different random initializations could encourage the network to latch on to different predictive features (even when exposed to the same training set), and thus result in ensembles with better test accuracy. Extending their study to understand similar effects on calibration would be a useful direction for future research.

heading: B APPENDIX: EXPERIMENTAL DETAILS

heading: B.1 PAIRWISE DISAGREEMENT
text: In this work, the main architectures we used are ResNet18 with the following hyperparameter configurations:
1. width multiplier: {1×, 2×} 2. initial learning rate: {0.1, 0.05} 3. weight decay: {0.0001, 0.0} 4. minibatch size: { 200, 100} 5. data augmentation: {No, Yes}
Width multiplier refers to how much wider the model is than the architecture presented in He et al. (2016) (i.e. every filter width is multiplied by the width multiplier). All models are trained with SGD with momentum of 0.9. The learning rate decays 10× every 50 epochs. The training stops when the training accuracy reaches 100%.
For Convolutional Neural Network experiments, we use architectures similar to Network-inNetwork (Lin et al., 2013). On a high level, the architecture contains blocks of 3 × 3 convolution followed by two 1 × 1 convolution (3 layers in total). Each block has the same width and the final layer is projected to output class number with another 1 × 1 convolution followed by a global average pooling layer to yield the final logits. Other differences from the original implementation are that we do not use dropout and add batch normalization layer is added after every layer. The hyperparameters are:
1. depth: {7, 10, 13} 2. width: {128, 256, 384} 3. weight decay: {0.001, 0.0} 4. minibatch size: {200, 100, 300}
All models are optimized with momentum of 0.9 and uses the same learning rate schedule as ResNet18.
For Fully Connected Networks, we use:
1. depth: {1,2,3,4} 2. width: {128, 256, 384, 512} 3. weight decay: {0.0, 0.001} 4. minibatch size: {100, 200, 300}
All models are optimized with momentum of 0.9 and uses the same learning rate schedule as ResNet18.
Distribution shift and pre-training experiments. On all our experiments on the PACS dataset, we use ResNet50 (with Batch Normalization layers frozen and the final fully-connected layer removed) as our featurizer and one linear layer as our classifier. All our models are trained until 3000 steps after reaching 0.995 training accuracy with the following hyperparameter configurations:
1. learning rate: 0.00005
2. weight decay: 0.0
3. learning rate decay: None
4. minibatch size: 100
5. data augmentation: Yes
On each of these domains, we train 5 pairs of ResNet50 with a linear layer on top, varying the random seeds (keeping hyperparameters constant). Both models in a pair are trained on the same 80% of the data, and only differ in their initialization, data ordering and the augmentation on the data. We then evaluate the test error and disagreement rate of all pairs on each of the four domains. We consider both randomly initialized models and ImageNet pre-trained models (Deng et al., 2009). For pre-trained models, only the linear layer is initialized differently between the two models in a pair.

heading: B.2 ENSEMBLE
text: For ensembles, unless specified otherwise, we use the combination of the first option for each hyperparameters in Section B.1.

heading: B.2.1 FINITE-SAMPLE APPROXIMATION OF CACE
text: For every ensemble experiment, we train a standard ResNet 18 model (width multiplier 1×, initial learning rate 0.1, weight decay 0.0001, minibatch size 200 and no data augmentation).
To estimate the calibration, we use the testset Dtest. We split [0, 1] into 10 equally sized bins. For a class k, we can group all (x, y) ∈ Dtest into different bins Bki according to h̃k(x) (all bins have boundaries that do not overlap with other bins). In total, there are 10×K bins.
Bki = { (x, y) | lower(Bki ) ≤ h̃k(x) < upper(Bki ) and (x, y) ∈ Dtest } (56)
Where upper and lower are the boundaries of the bin. To mitigate the effect of insufficient samples for some of the middling confidence value in the middle (e.g. p = 0.5), we further aggregate the calibration accuracy over the classes into a single bin Bi = ⋃K k=1 Bki in a weighted manner. Concretely, for each bin, we sum over all the classes when computing the accuracy:
acc(Bi) = 1∑K
k=1 |Bki | K∑ k=1 ∑ (x,y)∈Bki 1[y = k] = 1 |Bi| K∑ k=1 ∑ (x,y)∈Bki 1[y = k] (57)
To quantify the how “far” the ensemble is from the ideal calibration level, we use the Class Aggregated Calibration Error (CACE) which is an average of how much each bin deviates from y = x weighted by the number of samples in the bin:
ĈACE = NB∑ i=1 |Bi| |Dtest| |acc(Bi)− conf(Bi)| (58)
where NB is number of bins (usually 10 in this paper unless specified otherwise), conf(Bi) is the ideal confidence level of the bin, which we set to the average confidence of all data points in the bin. This is the sample-based approximation of definition 4.4.

heading: B.2.2 FINITE-SAMPLE APPROXIMATION OF ECE
text: ECE is a widely used metric for measuing calibration. For completeness, we will reproduce its approximation here. Let Ŷ be the class with highest probability under h̃ (we are omitting the dependency on X in the notation since it is clear):
Ŷ = argmax k∈[K] h̃k(X) (59)
We once again split [0, 1] into 10 equally sized bins but do not divide further into K classes. Each bin is constructed as:
Bi = { (x, y) | lower(Bi) ≤ h̃ŷ(x) < upper(Bi) and (x, y) ∈ Dtest } (60)
With the same notation used for CACE, the accuracy is computed as:
acc(Bi) = 1 |Bi| ∑
(x,y)∈Bi
1[y = ŷ] (61)
Finally, the approximation of ECE is computed as the following:
ÊCE = NB∑ i=1 |Bi| |Dtest| |acc(Bi)− conf(Bi)| (62)

heading: C ADDITIONAL EMPIRICAL RESULTS

heading: C.1 ADDITIONAL FIGURES

heading: C.2 CIFAR100 CALIBRATION TABLE
text: Here we present the calibration error for ResNet18 trained on CIFAR100 with 10k training examples.

heading: C.3 OTHER DATASETS AND ARCHITECTURES
text: In Fig 10, we provide scatter plots for fully-connected networks (FCN) on MNIST, and convolutional networks (CNN) on CIFAR10. We observe that when trained on the whole MNIST dataset, there is larger deviation from the x = y behavior (see left-most image). But when we reduce the dataset size to 2000, we recover the GDE observation on MNIST. We observe that the CNN settings satisfies GDE too.

heading: C.4 ERROR DISTRIBUTION OF ENSEMBLES
text: Here (Fig 11) we show the error distribution of the ensemble similar to N&B’20. The x-axis of these plots represent 1 − h̃y(X) in the context of our work. As N&B’20 note, these plots are not bimodally distributed on zero error and random-classification-level error (of K−1K where K is the number of classes). This disproves the easy-hard hypothesis as discussed in the main paper. As a side note, we observe that all these error distributions can be fit well by a Beta distribution.

heading: C.5 CALIBRATION CONFIDENCE HISTOGRAM
text: Here (Fig 12) we report the number of points that fall into each bin in calibration plots. In other words, for each value of p, we report the number of times the ensemble h̃ satisfies h̃k(x) ≈ p for some k and some x.

heading: C.6 COMBINING STOCHASTICITY
text: In Fig 13, for the sake of completeness, we consider a setting where both the random initialization and the data ordering varies between two runs. We call this setting the SameData setting. We observe that this setting behaves similar to DiffData and DiffInit.

heading: C.7 CLASS-WISE CALIBRATION VS CLASS-AGGREGATED CALIBRATION
text: In Fig 14, we report the calibration plots for a few random classes in the CIFAR10 and CIFAR100 setup and compare it with the class-aggregated calibration plots. We observe that the class-wise plots have a lot more variance, indicating that calibration within each class may not always be perfect. However, when aggregating across classes, calibration becomes much more well-behaved. This suggests that the calibration is smoothed over all the classes. It is worth noting that a similar effect also happens for ECE, although not reported here.

heading: C.8 CORRELATION VALUES IN FIG 1
text: In the main paper figures, we quantified correlated via R2 and τ for scatter plots that include both data-augmented models and non-data-augmented models. Here, we report these values specific to each group of models.

heading: C.9 MORE THAN ONE PAIR OF MODELS
text: Here, we show the ResNet18 CIFAR-10 DiffInit experiments (no data augmentation) with only one pair of models v.s. the average of 4 pairs of models. We see that while 4 pairs of models does improve the correlation, the improvement is only marginal. This suggests that only using a single pair of models may be sufficient for estimating the generalization error.
(a) The scatter plot for the disagreements of 1 pair of models.
(b) The scatter plot for the average disagreements of 4 pairs of models.
However, if we instead measure the distance from the y = x line. Specifically, each pair’s deviation is measured as
|TestError− Disagreement| 0.5(TestError+ Disagreement) . (63)
The denominator normalizes the deviation so hyperparameters with different performance contribute equally. Then, we observed that 1-pair achieves an average deviation of 0.112 while the 4-pair achieves 0.034. This shows that if one is interested in estimating the exact generalization error, using more pairs of models would help.

Review summaries:
This paper identifies and studies a new phenomena in the generalization of deep learning. First, it presents the observation of Generalization-Disagreement Equality (GDE) between same models trained with different stochasticity, strengthening the similar observation of Nakkiran and Bansal (2020). Second, it shows theoretically that calibration of ensembles (in both the per-class sense and a suitable aggregated sense) implies GDE, with accompanying experiments on their relationship.

This paper shows empirically that the test error of a network is approximately equal to the disagreement rate between two separate training runs of the network, measured on unlabeled test data. This is true even when the two training runs are on the same training set, and with varying sources of stochasticity (e.g. random seed, ordering of training data). The authors show theoretically that this phenomenon is due to ensembles trained with SGD being well-calibrated. 

This paper builds upon and extends from Nakkiran/Bansal (2020). First, it shows empirically that models learned from two independent runs of SGD on the same training set have their prediction disagreement highly correlated (and nearly equal) to the test error of the models.  It then attempts a theoretical explanation for this phenomenon. Under two notions of "calibration", the paper proves that when the learning algorithm is well-calibrated, a "generalization disagreement equality" holds (i.e., disagreement in prediction is equal to the test error in expectation).  The paper performs further experiments and provides empirical evidence suggesting that SGD is well calibrated.  The paper also proves that the gap between the test error and the prediction disagreement is upper bounded by a calibration error.

The authors build on a striking empirical observation of Nakkiran & Bansal—namely, that if two neural networks with the same architecture are trained on independently drawn training sets, achieving generalization error $\epsilon$, then their rate of disagreement on a test set is typically nearly equal to the test error of the two networks. In this paper, it is shown that this observation also holds even if the two networks are trained on the same data, but with different random seeds (data ordering and/or initialization).  The authors prove that test error will equal disagreement rate _in expectation_ for any stochastic learning algorithm whenever the algorithm's predictions have a certain calibration property.