Assessing Generalization of SGD via Disagreement
Authors: Yiding Jiang
Vaishnavh Nagarajan
Christina Baek
J Zico Kolter
Venue: ICLR 2022 Spotlight (2022)
Keywords: Generalization
Deep Learning
Empirical Phenomenon
Accuracy Estimation
Stochastic Gradient Descent

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 20, 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.

Published as a conference paper at ICLR 2022
ASSESSING GENERALIZATION VIA DISAGREEMENT
Yiding Jiang
Vaishnavh Nagarajan xt Google Research vaishnavhégoogle.cm com
Christina Baek, J. Zico Kolter Carnegie Mellon University {kbaek, zkoa ter J@cs. cmu, edu
Carnegie Mellon University ydjiang@cmu. edu
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 re- quires 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.
INTRODUCTION
Consider the following intriguing observation made in Nakkiran & Bansal (2020). Train two net- works of the same architecture to zero training error on two independently drawn datasets S1 and S2 of the same size. Both networks would achieve test eπror (or equivalently, generalization gap) of about the same value, denoted by e. 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 2c. 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 c, but nearly equals c (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.
0.30
ABDI 2 5.9 bey: 3 604
2= 0.31x
5.275
Gal: 5.040
0.20
Plo
0.30
DITIl/ e2, 0.00 tsu 0.800
(1. 0.11s
0.16
1997
0290
0.14
0.14
2.79
0.12
0.19
3.50
0.10
0.08
0190
0.125
0.52
2.00
0.10
0.14
dsagssmment
The scatter plots of pair-wise model disagreement (x-axis) vs the test emror (y-axis) of the different ResNet18 trained on CIFAR1O. The dashed line is the diagonal line where disagreement equals the test error. Orange dots represent models that use data augmentation. The first two plots correspond to pairs of networks trained on independent datasets, and in the last two plots, on the same dataset. The details are described in See 3.
Figure 1: GDE on CIFAR-10:
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
"qqual contribution
Work performed when Vaishnavh Nagarajan was student Careegie Mellon University.

---

Published as a conference paper at ICLR 2022
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 much stronger behavior: the disagreement rate is able to capture even minute variations in the test error under varying hyperparamettess 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 net- works 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 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 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 propor- tionality constants and (b) knowledge of the neural network weightsfrepresentations. Disagreement, however, provides direct estimate, and works even with a black-box model, which makes it prac- tically 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) well-calibrated (i.e., the predicted probabilities are neither over- confident 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 (Lakshminarayamn calibration holds in practice, the fact the condition in our theorem is empirically satisfied implies that our theory offers valuable insight into the practical generalization properties of deep networks.
et al., 2017). While we do not prove why
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:
We prove that for any stochastic learning algorithm, if the algorithm leads to well-calibrated ensemble on particular data distribution, then the ensemble satisfies the Generalization Dis- agreement Equality' (GDE) on that distribution, in expectation over the stochasticity of the al- gorithm. Notably, our theory is general and makes 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-calibratd (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 cer- tain distribution shifts within the PACS (Li et al., 2017) dataset. This implies that the disagree- ment rate can be a promising estimator even for distr--iistii 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.
NNakiiran & Bansal (2020) refer to this the Agreement Property, but we use the term Generalization Disagreement Equality to he more explicit and avoid confusion regarding certain technical differences.
2

---

Published as a conference paper at ICLR 2022
2
RELATED WORKS
Understanding and predicting generalization. Conventionally, generalization in deep learning has been studied through the lens of PAC-Iearning (Vapnik, 1971; Valiant, 1984). Under this frame- work, 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 ct al., 2020b; Dziugaite et al., 2020). Subsequently, recent works have pro- posed unconventional ways to derive generalization bounds (Negrea al., 2020; Zhou et al., 2020; Garg et al., 2021). Indeed, even our disagreement- 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 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. Finally, it is worth noting that much older work (Madani et al., 2004) has provided bounds on the test error as a function of (rather than based on "direct estimate" of) disagreement. However, these require the two runs to be on independent training sets.
estimate marks a significant departure from
While there has been research in unsupervised accuracy estimation (Donmez et al., 2010; Platanios et al., 2017; Jaffe et al., 2015; Steinhardt & Liang, 2016; ElSahar & Gallé, 2019; Schelter et al., 2020; Chuang et al., 2020), the focus has been on out-of-distribution and/or specialized learning settings. Hence, they require specialized training algorithms or extra information about the tasks. Concurrent work Chen et al. (2021) here has made similar discoveries regarding estimating accuracy via agreement, although their focus is more algorithmic than ours. We discuss this in Appendix A.
Reducing churn. A line of work has looked at reducing disagreement (termed there as "churn"") to make predictions more reproducible and easy-to-debug. (Milani Fard et al., 2016; Jiang et al., 2021: Bhojanapalli et al., 1). Bhojanapalli et al. (2021) further analyze how different sources of stochasticity can lead to non-trivial disagreement rates.
Calibration. Calibration of a statistical model the property that the probability obtained by the model reflects the true likelihood of the ground truth (Murphy & Epstein, 1967; Dawid, 1982). 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, two types of ensembles have typically been studied, depending on whether the members are trained on independently sampled data also called bagging (Breiman, 1996) or the same data but with different random seeds (e.g., different random initial- ization and data ordering) also called deep ensembles (Lakshminarayanaa 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 in- dividual 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 de- rived 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, re- quires looking at the confidence level of the model aggregated over all the classes. We then empiri- cally show that SGD ensembles are well-calibrated even in this class aaass-gggee sense. Furthermore, 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.
3

---

Published as a conference paper at ICLR 2022
Empirical phenomena in deep learning. Broadly, our work falls in the area of research on identi- fying & understanding empirical phenomena in deep learning (Sedghi et al., 2019), especially in the context of overparameterized models that interpolate. Some example phenomena include the gen- eralization puzzle (Zhang et al., 2017; Neyshabur et al., 2014), double descent (Belkin et al., 2019; Nakkiran al., 2020), and simplicity bias (Kalimeris et al., 2019; Arpit et al., 2017). As stated ear- lier, we particularly build on N&B 20's empirical observation of the Generalization Disagreement Equality (GDE) in pairs of models trained on independently drawn datasets. They provide a proof of GDE for 1-nearest- -nearest-neighhor classifiers under specific distributional assumptions, while our result different, and much more generic. Due to space constraints, we defer detailed discussions of the re relationship between our works in Appendix A.
3 DISAGREEMENT TRACKS GENERALIZATION ERROR
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 eπror induced by varying hyperparameters. Remarkably, this estimate does not require an independent labeled dataset.
Notations. Let h X' > [K] denote hypothesis from hypothesis space H. where [K] denotes the set of labels {0, I,.., K - 1]. Let 2 be distribution over X' [K]. We will use (X, Y) to denote the random variable with the distribution 2, and (I. y) to denote specific values it can take. Let AA be a stochastic training algorithm that induces a distribution AA over hypotheses in H. Let h. h ~ A.A denote random hypotheses output by two independent runs of the training procedure. We note that the stochasticity in A could arise from any arbitrary source. This may arise from either the fact that each h is trained on random dataset drawn from 9 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:
TestErr (h) A Eg [1() # YJ
and Disg (h, M) A Eg [1(M(X) * M(X)] (1)
Let h denote the "ensemble" corresponding to HA. In particular, define
(x(x)) A Exe, [1())) k]]
to be the probability value (between [0. 1) given by the ensemble ì for the 1ith 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 unique hyperparameter configura- tion (See Appendix C.1 for details) and all models are (near) interpolating. For each hyperparameter setting, we train two copies 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 source of stochasticity is "on". For example, Di DiffInit means that the two models have different initializations but see the same data in the same order. In Di DiffOrder, models share the same initialization and the same data, but in different orders. In Di ffData, the models share the initialization, but see different data. In AlIDiff, 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 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 (1) vs disagreement error between the two runs (x) for CIFAR-IO, SVHN and CIFAR- in Figures 1, 2 and 3 respectively (and for CNNs on CIFAR- in Fig 10). Naively, we would expect these scatter plots to be arbitrarily distributed anywhere between y = 0.5z (if the errors of the two models are disjoint) and x = 0 (if the errors are identical). However, in all these scatter plots, error lie very close to the diagonal line y = x across different sources of stochasticity, while only slightly deviating in DiffInit t/Oderr. In particular, in AllDiff ff and Di ffData, the points typically
observe that test error and disagreement
4

---

Published as a conference paper at ICLR 2022
ABDII 0.080
DiDtrorr 2 145 tau 2756
Offied e 995 Day 6 791
8:00
0.000
0.34
P-LL 1L.
0.00
0.20
0.00
B0T
0.000
0.50
000
925
0000
322
0.55
8:11
112
011
0304
1104
0151
0100
1154
Figure 2: GDE on SVHN: The scatter plots of pair-wise model disagreement (x-axis) vs the test error (y-axis) of the different ResNet18 trained on SVHN.
AIDeT 1. 5.525 lac CBM
Distlate 1 C.74 Lau: 7.7
Dim 2 0984 bur o R0P
D3 1O F. 6 966 fay: 0.925
0.90
(= 2 0.33
0.56
C 0.31
0:45
(La 233
(La 33
0.50
D40
044
035
0.0
0.40
033
0.35
vi 41g
vib sug
0.35
035
00.0
64
0.5
83
04
dsogrommort comort
dbog rommrtt
Ubugraamee1)
dbugromment
Figure 3: GDE on CIFAR-100: The scatter plots of pair-wise model disagreement (x-axis) vs the test error (y-axis) of the different ResNet18 trained CIFAR100.
ABDI e ces taui 831
CaTtatt 0:373 6au: 0.852
Dufte 0.900 1a22 0781
DICCddrr e 0.02 Lat: 2.877
p- a 3.30
0.33
(- 333
01600
0.00
y=11 0:51
0:55
0053
0.59
044
0145
0:45
0.46
049
055
WV
0.55
0.5
0.25
0.30
044
0.22
diagnommet
Figure 4: GDE on 2k subset of CIFAR-10: The scatter plots of pair-wise model disagreement (X-axis) vs the test error (y-axis) of the different ResNet18 trained on only 2000 points of CIFARIO. 10.
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 and y = 1.3x. We quantify correlation via the R² 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-augmente or the non-data-auge augmented models, R² tends to range a bit lower, around 0.7 and 7 around 0.6 (see Appendix D.8).
The positive observations about DiffInit t 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 dis- agreement rate without using 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 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- 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 the other settings (albeit with some deviations)
the scatter plot lies in y = (1 + 0.1)xz (for AllDiff and Dif DiffData) and in y = (1 = 0.3)xz (for DiffInit t/Order), and the correlation metrics are high. Similar results were established in N&B'20 for AllDiff and Di ffata.
5

---

Published as a conference paper at ICLR 2022
Finally, it is important to highlight that each scatter plot here corresponds to varying certain hyper- parameters 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 stronger version of the finding in N&B' 20 that disagreement captures larger variations under varying dataset size.
Effeet 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 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 mod- els, 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 that under distribution shift, pre-trained models can satisfy GDE, and often better than randomly initialized models. This is counter- counter-intuitive, since we would expect pre- are-trained models to be strongly predisposed towards specific kinds of fea- tures, resulting in models that disagree rarely. See Appendix C. for hyperparameter details.
10
100
sbarihh
Source
08
0.8
APT
6-4
6.4
carizon prona
tast
6.31i
02
02
522
0.2
08
0.0
diskgreement
disagreement
disggremmnt
disagreement
Figure 5: GDE under distribution shift: The scatter plots of pair-wise model disagreement (x- axis) vs the test error (y-axis) of the different ResNet50 trained on PACS. Each plot corresponds to models evaluated on the domain specified in the title. The marker shapes indicate the source domain.
4 CALIBRATION IMPLIES THE GDE
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 ~ HA-
Definition 4.1. The stochastic learning algorithm A satisfies the Generalization Disagreement Equality (GDE) on the distribution D if,
En, (Dis y (h, h')] En (TestErr
Note that the definition does not imply that the equality holds for each pair of h h (which we observed empirically). However, for simplicity, 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 look at the most natural hypothesis that N&B'20 identify. Imagine that all datapoints (z, y) are one of two types: (a) the datapoint is so "casy" that w.p. over h A, h(x) y (b) the datapoint so "hard" that h(x) corresponds to picking a label uniformly at random. In such case, with simple calculation, one can see that the above equality would hold not just in expectation over 2, but even point-wise: for each æ, the disagreement on x in expectation over HA would equal the error on in expectation over HA (namely (K 1)/ K if r 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 D.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 ensem- ble is cell-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

---

Published as a conference paper at ICLR 2022
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 H if for any confidence value q E [o, 1] and for any class & E [K],
p(Y (X) 9) = q.
Next, we show that if the ensemble is class-wise calibrated on the distribution Z, then GDE does hold on 9. Note however that shortly we show a more general result where even 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 general. We do not restrict the hypothesis class (it need not necessarily be neural networks), or the test/training distribution (they can be different, as long as calibration holds in the test distribution), 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. B.2.) Let Xg correspond to a "confidence level set" in that X = {X E X ho(X)) = g)- Our key idea is to show that for class-wise calibrated ensemble, GDE holds within each confidence level sel i.e., for each q E [0. 1]. the (expected) disagreement rate equals test error for the distribution 9 restricted to the support Xg. Since X' is combination of these level sets, it automatically follows that GDE holds over 2. It is worth contrasting this proof idea with the easy-hard explanation which requires showing that GDE holds point-wise, rather than confidence-level-sse--ww
Now, let us calculate the disagreement on Xz. For any fixed in Xg. the disagreement rate in expectation over h. h ~ HeA corresponds to q(1 +1) (1-111110) q)q = 2g (111-) 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 Xg- At any x, the expected error equals (x)) From calibration, we have that exactly q fraction of Xg has the true label O. On these points, the error rate is h1()) = 1 q. On the remaining 1 q fraction, the true label is 1, and hence the error rate on those is ho(r) g. The total error rate across both the class and class points therefore q(1 - q) + (1 - 4)q 2q(1 g)- L
Intuition. Even though the proof is fairly simple, it may be worth demystifying it a bit further. In short, calibrated classifier "knows" how much error commits in different parts of the distribu- tion i.e., over points where it has confidence of 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 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 this, measuring the expected disagree- ment 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 .A) must be unusually small; indeed, we will empirically verify this in Table 1. In Corollary 1.1.1, we present some preliminary discussion on why the variance could be small, leaving further exploration for future work.
4.1 MORE GENERAL RESULT: CLASS-WISE TO CLASS- -AASSAAGGREGATED CALIBRATION
We will now show that GDE holds under more relaxed notion of calibration, which holds "on aver- age" over the classes rather than individually for each class. Indeed, we demonstrate in later section (see Appendix D.7) that this averaged notion of calibration holds more gracefully than class-wise
7

---

Published as a conference paper at ICLR 2022
calibration in practice. Recall that in class-wise calibration we look at the conditional probability p(Y = k hg (X) q) for each k. Here, will take average of these conditional probabilities by weighting the ktt probability by p(ha (X) - q). The result the following definition:
Definition 4.3. The ensemble h satisfies class-aggregated calibration on 2 if for each E [0, 1}.
PV q. En=o (()x(
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 point multiple times if (x) q for multiple classes k. In Appendix B.5, we discuss the relation between this new notion of calibration to existing definitions. In Appendix B. Theorem B.I, we show that the above weaker notion of calibration is sufficient to show GDE. The proof of this theorem is a non- trivial generalization of the argument in the proof sketch of Theorem 4.1, and Theorem 4. follows straightforward corollary since class wise calibration implies class aggrregted calibration.
Deviation from calibration. For generality, we would like to consider ensembles that do not satisfy class-aggregated calibration precisely. How much can 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 Ø is
CA)
/ 7E
En (x))=) E. (()=
E. pha((x()) g)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.
worth keeping in mind that, while the absolute difference term lies in [0, 1], the weight terms alone would integrate to value of K. Therefore, CACE (h) can lie anywhere in the range [0, K]. Note that CACE 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 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 Appendix B.3.
Theorem 4.2. For any algoritium A,
Ese g (h h')] - EE Ee [TestErr (h)] S CACE (h).
Remark. All our results hold more generally for any probabilistic classifier h. For example, if 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.
EMPIRICAL ANALYSIS OF CLASS-AGGREGATH CALIBRATION
Empirical evidence for theory. As stated in the introduction, it 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 proba- bilities of the individual models, rather than an average of the top-class predictions. Our theory is however based upon the latter type of ensembles. tion metrics for calibration in literature, while Furthermore, there exists many different evalua- 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 axis and the confidence value q along the 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 B.6.
8

---

Published as a conference paper at ICLR 2022
AELMT
LNTLaGa
DIICTOO
LVTINE
62 0o/0don00
confidonce
contioonco
conf0oonc
Figure 6: Calibration on CIFARIO: Calibration plot of different ensembles of 100 8
trained on CIFARIO. The error bar represents one bootstrapping standard deviation (most are ex- tremely small). The estimated CACE for each scenario is shown Table
Test Error
Disagreement
Gap
C)C
CACE
CACE
ECE
AlIDiff
0.336 0.015
0.348 1 0.015
0.012
0.0437
0,2064
0.4244
0.0197
DiffData
0.341 = 0.020
0.354 0.020
0.013
0.0491
0.2242
0.4411
0.0267
DiffInit
0.337 00017
0.307 0.022
0.030
0.0979
0.2776
0,4495
0.0360
DiffOrder
0.335 = 0.017
0.302 0.020
0.033
0.1014
0.2782
0.4594
0.0410
Table 1: Calibration error vs. deviation from GDE for CIFAR10: Estimated CACE for en- sembles with different number of models (denoted in the superscript) for ResNet18 on CIFARIO with 10000 training examples. Test Error, Disagreement statistics and ECE are averaged over 100 models. Here ECE is the standard measure of top-class calibration error, provided for completeness.
For more precise quantification of how well calibration captures GDE, also look at 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 (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 disagree- ment rate. In particular, CACE for AllDiff/Dis /DiffData are about 2 to times smaller than that for DiffInit/Order, paralleling the behavior of [TsstEr Dis in these settings.
100 models in Table
Caveats. While we believe our work provides 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). Therefore, if we do not know a priori that calibration holds in a particular setting, we would need labeled test data to verify if CACE is small. This would defeat the purpose of using unlabeled- data-based disagreement to measure the test error. (Thankfully, in in-distribution settings, it seems like may be able to assume calibration for granted.) Next, our theory sheds 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 single pair of models lies close this expectation This occurs even though two-model-ensemblee are poorly calibrated (see Tables I and 3). Finally, while CACE an upper bound on the deviation from GDE, in practice CACE is only a loose bound. which could either indicate mere lack of data/models or perhaps that our theory can be further refined.
6 CONCLUSION
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 iden- tifying and understanding empirical phenomena in deep learning. Future work could shed light on why different sources of stochasticity surprisingly have similar effect calibration. It is also important for future work in uncertainty estimation and calibration to develop a precise and ex- haustive characterization of when calibration and GDE would hold. On different note, we hope our work inspires other novel ways to leverage unlabeled data to estimate generalization and also further cross- moss-pollinatton of ideas between research in generalization and calibration.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors would like to thank Andrej Risteski, Preetum Nakkiran and Yamini Bansal for valuable discussions during the course of this work. Yiding Jiang and Vaishnavh Nagarajan were supported by funding from the Bosch Center for Artificial Intelligence.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. 2020. URL http://awww..og.bb/////////a 09816.
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron C. Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization deep networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, 2017.
Yu Bai. Song Mei, Huan Wang, and Caiming Xiong. Don't just blame seer-araamttizatioon for over-confidence: Theoretical analysis of calibration binary classification. arXiv preprint arXiv:2102.07856, 2021.
Peter L. Bartlett, Dylan J. Foster, and Matus J. Telgarsky. Spectrally- margin bounds for neural networks. In Advances in Neural Information Processing Systems 30; Annual Conference Neural Information Processing Systems 2017, 2017.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018. PMLR, 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15854,, 2019. doi: 19.73///aa..90000011
Srinadh Bhojanapalli, Kimberly Wilber, Andreas Veit, Ankit Singh Rawat, Seungyeon Kim, Aditya Menon, and Sanjiv Kumar. On the reproducibility of neural network predictions. arXiv preprint arXiv:2102.033: 033449 2021.
Leo Breiman. Bagging predictors. Mach. Learn., 24(2): 1996.
Jiefeng Chen, Frederick Liu, Besim Avei, Xi Wu, Yingyu Liang, and Somesh Jha. Detecting er- rors and estimating accuracy on unlabeled data with self-training ensembles. arXiv preprint 1rXi::2106.15728. 2021.
Ching-Yas Yao Chuang, Antonio Torralba, and Stefanie Jegelka. Estimating generalization under distri- bution shifts via domain-invariin representations. Proceedings of the 37th International Con- ference on Machine Learning, ICML 2020, Proceedings of Machine Learning Research. PMLR, 2020.
A Philip Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77 (379):605-610, 1982.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255 Icee, 2009.
Pinar Donmez, Guy Lebanon, and Krishnakumar Balasubramanian. Unsupervised supervised learn- ing estimating classification and regression errors without labels. J. Mach. Learn. Res., 2010.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: /008. 2017.
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, loannis Mitliagkas, and Daniel M Roy. In search of robust measures of generaliza- tion. arXiv preprint arXiv:2010. /924, 2020.
10

---

Published as a conference paper at ICLR 2022
Hady ElSahar and Matthias Gallé. To annotate not? predicting performance drop under do- main shift. In Proceedings of the 2019 Conference on Empirical Methods Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP- IJCNLP 2019. Association for Computational I Linguistics, 2019.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape per- spective. arXiv preprint arXtv:1912.02757, 2019.
Saurabh Garg, Sivaraman Balakrishnan, J. Zico Kolter, and Zachary C. Lipton. RATT: leveraging unlabeled data to guarantee generalization. 2021.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pp. 1321-1330. PMLR, 2017.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas, Distribution-Fiee binary classification: prediction sets, confidence intervals and calibration. In Advances in Neural Information Process- ing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Ariel Jaffe, Boaz Nadler, and Yuval Kluger. Estimating the accuracies of multiple classifiers without labeled data. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, AISTATS 20155, JMLR Workshop and Conference Proceedings, 2015.
Ziwei Ji, Justin D. Li, and Matus Telgarsky. Early-stopped neural networks are consistent. 2021. hwwp:////ggab//6655// URL httph: http://axvvvvve org/ 2210 05932.
Heinrich Jiang, Harikrishna Narasimhan, Dara Bahri, Andrew Cotter, and Afshin Rostamizadeh.
Churn reduction via distillation. arXiv preprint arXiv:2/06.02654 2021.
Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distributions. arXiv preprint arXiv:1810.00111 2018.
Yiding Jiang, Pierre Foret, Scott Yak, Daniel M Roy, Hossein Mobahi, Gintare Karolina Dziugaite, Samy Bengio, Suriya Gunasekar, Isabelle Guyon, and Behnam Neyshabur. Neurips 2020 compe- tition: Predicting generalization in deep learning. arXiv preprint arXiv:2012.07976 2020a.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference on Learning Representations, 2020b. URL https://openreviee
net/forum?id=SSgIPPP
Christopher Jung, Changhwa Lee, Mallesh M. Pai, Aaron Roth, and Rakesh Vohra. Moment multi- calibration for uncertainty estimation. 2020. URL https:tt/attii......// http://awwvv.....aaa////a// oogg/bbs//000 200.0/0007000
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin L. Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. SGD on neural networks learns functions of increasing complex- ity. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 2019.
Dilip Krishnan, Hossein Mobahi, Behnam Neyshabur, Peter Bartlett, Dawn Song, and Nati Srebro. Understanding and improving generalization in deep learning. ICML 2019 Workshop, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ananya Kumar, Percy Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neu- ral Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, 2019.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, 2017.

---

Published as a conference paper at ICLR 2022
Da Li, Yongxin Yang. Yi-Zhe Song, and Timothy M. Hospedales. Deeper, broader and artier domain generalization. In JEEE Interationnal Conference on Computer Vision, ICCV 2017, 2017.
Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. arXiv preprint arXiv:1312.4400, 2013.
Lydia T. Liu, Max Simchowitz, and Moritz Hardt. The implicit fairnsss criterion of unconstrained learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Proceedings Machine Learning Research, 2019.
Omid Madani, David M. Pennock, and Gary William Flake. Co-validation: Using model disagree- ment unlabeled data to validate classification algorithms. In Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, NIPS 2004, 2004.
Mahdi Milani Fard, Quentin Cormier, Kevin Canini, and Maya Gupta. Launch and iterate: Reducing prediction churn. Advances in Neural Information Processing Systems, 29:3179 29:3179-3187, 2016.
Jishnu Mukhoti, Andreas Kirsch, Joost van Amersfoort, Philip H. S. Torr, and Yarin Gal. Determin- istic neural networks with appropriate inductive biases capture epistemic and alcatoric uncertainty. CoRR, abs/2102.1 1582, 2021. URL https://arxiii org/
11582.
Allan H Murphy and Edward S Epstein. Verification of probabilistic predictions: A brief review. Journal of Applied Meteorology and Climatology, 6(5):748-755, 1967.
Mahdi Pakdaman Naeini, Gregory F, Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the Twenty-Ninth AAAI Conference Artificial Intelligence. AAAI Press, 2015.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Advances in Neural Information Processing Systems 32, 2019at
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience arXiv preprint arXiv:/905. 13344, 2019b.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint arXiv:1901.01671 2019c.
Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generalization. abs/2009.08092, 2020. URL http:://axxxv.rrrgeoee
08092.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In 8th International Conference on Learning Representations, ICLR 2020, 2020.
Parth Natekar and Manik Sharma. Representation based complexity measures for predicting gener- alization in deep learning. 2020. URL https://arxiv.. /ttp//////21122.....
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. arXiv preprint
2018.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors. In Proceed- ings of the 37th International Conference on Machine Learning, ICML 2020. PMLR, 2020.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning, 2011.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1412.6614, 2014.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring gener- alization in deep learning. In Advances Neural Information Processing Systems 30, NeurlPS 2017, 2017.
12

---

Published as a conference paper at ICLR 2022
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A pac-bayesian approach to spectrally-normalizee normalized margin bounds for neural networks. International Conference on Learning Representations (ICLR), 2018.
Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measur- ing calibration in deep learning. In CVPR Workshops, volume 2, 2019.
Jeremy Nixon, Balaji Lakshminarayanann and Dustin Tran. Why are bootstrapped deep ensembles not better? 2020. URL httpttts/////pnreeee
nett/forummiddddTirreoc
Emmanouil A. Platanios, Hoifung Poon, Tom M. Mitchell, and Eric Horvitz. Estimating accuracy from unlabeled data: A probabilistiic logic approach. In Advances Neural Information Process- ing Systems 30: Annual Conference on Neural Information P Processing Systems 2017, 2017.
Sebastian Schelter, Tammo Rukat, and Felix Bießmann. Learning to validate the predictions of black box classifiers on unseen data. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, 2020.
Hanie Sedghi, Samy Bengio, Kenji Hata, Aleksander Madry, Ari Morcos, Behnam Neyshabur, Maithra Raghu, Ali Rahimi, Ludwig Schmidt, and Ying Xiao. Identifying and understanding deep learning phenomena. JCML 2019 Workshop, 2019.
Eliran Shabat, Lee Cohen, and Yishay Mansour. Sample complexity of uniform convergence for multicalibration. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
Jacob Steinhardt and Percy Liang. Unsupervised risk estimation using only conditional indepen- dence structure. In Advances in Neural Information Processing Systems 29; Annual Conference on Newral Information Processing Systems 2016, 2016.
Thomas Unterthiner, Daniel Keysers, Sylvain Gelly, Olivier Bousquet, and Ilya O. Tolstikhin. Pre- dicting neural network accuracy from weights. 2020. URL 11448.
Juozas Vaicenavicius, David Widmann, Carl R. Andersson, Fredrik Lindsten, Jacob Roll, and Thomas B. Schön. Evaluating model calibration in classification. In The 22nd International Con- ference on Artificial Intelligence and Statistics, AISTATS 2019, Proceedings of Machine Learning Research, 2019.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-1142, 1984.
Vladimir Naumovich Vapnik. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. 1971.
David Widmann, Fredrik Lindsten, and Dave Zachariah. Calibration tests in multi-class classifica- tion: A unifying framework. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pp. 12236-12246, 2019.
Xixin Wu and Mark Gales. arXiv:2101.05339, 2021.
Should ensemble members be calibrated?
arXiv preprint
Scott Yak, Javier Gonzalvo, and Hanna Mazzawi. Towards task and architecture innpeeeedde-ndeeedeeeeneeee gen- cralization gap predictors. 2019, URL http://arxiv.org hatgg//bs11990 1996. 01550.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In Proceedings of the Eighteenth International Conference on Machine Learning 2001).
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. 2017.
Lijia Zhou, Danica J. Sutherland, and Nati Srebro. On uniform convergence and low-norm inter- polation learning. Advances in Neural Information Processing Systems 33, NeurIPS 2020, 2020.
13

---

Published as a conference paper at ICLR 2022
A RELATED WORK
Here we provide a more detailed discussion of some related work. First we discuss how our results distinct from and/or complement their other relevant findings. First, N&B'20 20 provide proof of GDE specific to I-Nearest Neighbor models trained on two independent datasets. Our result does not restrict the hypothesis class, the algorithm or its stochasticity. Second, N&B' 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 dif- ferent 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' 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 exper- iments in N&B 20 are all reported only ensembles of members trained on different data. Hence, overall, their empirical results do not imply our GDE results.
In a concurrent work, Chen 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 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 e.g., we examine the effects of different kinds of stochasticity, we introduce ensembles only as a vehicle to understand the phenomenon theoretically (rather than an algorithmic object), and we prove how GDE holds under certain novel notions of calibration weaker than the existing ones.
understanding
B APPENDIX: ADDITIONAL THEORETICAL DISCUSSION
B. PROOF OF THEOREM B.1
We will now prove Theorem B.1 which states that if the ensemble h satisfies class- llass-aggregtted cali- bration, then the expected test error equals the expected disagreement rate.
The basic intuition behind why class-aggregatt 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 seen from the proof in the appendix.
Theorem B.1. Given stochastic learning algorithm A, if its corresponding ensemble h satisfies class laass-gggeeatte calibration (Definition 4.3) on 9, then A satisfies GDE on 9 (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 class- aggregated calibration to get Eq 25. For expected disagreement rate, 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 deriv- ing the expected disagreement rate and the final result (Eq 44) is equal to the expected test error (Eq 25), which completes our proof.
analogously express it
We'll '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 E, (p(h(X) # Y h)].
ETE A En [p(h(X) +Y| h)]
14

---

Published as a conference paper at ICLR 2022
BANae E (x,Y)~ [1( + YIll [E ~xx
(8)
[[) + YIll
(exchanging expectations by Fubini's theorem)
(9)
-((xY)~~ 1 - ixx)
(10)
For our further simplifications, we'll explicitly deal with integrals rather than expectations, so we get,
K-1
ETE Σ K=
h1- = 2, Y k)dr.
(11)
We'll also introduce i(X) as arv. as,
K-1
ETE
k,, q)dxdq.
(12)
9EAK
k=0
Over the next few steps, we'll get rid of the integral over First, splitting the joint distribution over the three r.v.s by conditioning on the latter two.
ETE
E P(==
<p(Y=k,((x) q) /(L (,(1))p(X x Y k,,(() q)dxdq (13)
GEAN
K=U
K-1
Jf
p(Y - = = f. (-ox)) gx) p(x= x h(X) q. Y k)dxrqq
Σ
JEEAN k=0
constant w.E. J.
(14)
= =I JOEAK k=0
K-1 p(Y= = k,h((x = q)(1 (n) / p(xx==
Σ
= ll(X)(()))))))))){()) = q.Y Y = k)dx dq
(15)
K-1
Σ
p(Y = k,,(x) = 4)(1 - 9x.
(16)
qEAK k=0
swap
K-1
Σ
-Y==; = k,,(X)= = () gn )dg.
(17)
K= QEAR
(18)
In the few steps, we'll simplify the integral over q by marginalizing over all but the kth dimen- sion. First, rewrite the joint distribution of h(X) ) in terms of its K components. For any k, let h k (X) and q- denote the K dimensions of both vectors excluding their kth dimension. Then,
$11 /
ETE Σ
(x) q-k Y = (X) gx) p(Y k. (X) = 4x)(1 qu) pdp
k=0 9k q-k
coustant w.t. Jq-N
(19)
K-1 Σ
p(Y = -k, = = )x)
p(h= = --k Y k. (x)) qb )d dga
k=0
4-6
(20)
K-1
/
Σ
k = qx - qx dqk.
(21)
k=0
15

---

Published as a conference paper at ICLR 2022
Rewriting qk just 9,
K- ETE
p(Y = (x) = -) - -dd4
(22)
k=0
gE
swap
9) qddq.-
(23)
9 k=
Finally, we have from the calibration in aggregate assumption that Σ p(Y (X)x(X) = q)
E k-
(Xhx(X) (Definition 4.3). So, applying this, we get
K-1
Σ
p(ha(x) = () d)4
(24)
gE(u,1]
k=0
Rearranging,
K-1 x()((X)= =dd4. k=U
ETE
0(1 4) vE(o.1)
(25)
Disagreement Rate The expected disagreement rate (denoted by EDR short) given by the
probability that two i.i.d samples from h disagree with each other over draws of input from 2, taken in expectation over draws from AA. That is,
EDR A ht
(x(( # H' (X) h M)]
(26)
Ep
E - [1 (X) # [X)]]]]
(27)
(X
BA, [XX) * xlIIIll|
(exchanging expectations by Fubini's Theorem)
(28)
Over the next few steps, we'll write this in terms of l rather than /t and h'.
K-1
EDR =B E(XYN
BA
Σ
T[(x)= = x]] (1 - [x((x) = k))
(29)
k=0
=B(xyyigg
BAANWeA [1[x() = A1 - - 1[x(X) = x)]]
(swapping the expectation and the summation)
(30)
K-1
=B(x
Σ
p(h(X)= = ke (1 x(N(x= 1x1)
(since and h are i.i.d samples from H.)
(31)
K
=b(x,nw
Σ
The (x))(1
(32)
From here, we'll deal with integrals instead of expectations.
K
EDR
Σ (x) - (x(x))x(XX
- = x)dx.
(33)
Let us introduce the random variable h(X) as.
EDR =
/
K
Σ
h1(2)) hx(x))p (x= xx==xhh x,Ι( = 9) dndq.
(34)
GEAR
1mm
16

---

Published as a conference paper at ICLR 2022
In the next few steps, we'll ll get rid of the integral over First, split the joint distribution as,
EDR- / P (1(x)=9)
K-1
(1) (x)) (x= h(x) q) dxdq. (35)
JEAR
apply ho (xr)=
-/6 P (h(X)= - /
(x= (x qx (.)1-9))p(
9:)p
i(x) 9) dxdq. (36)
QEAR
bring to the front
R-1 Σ
P (M(X) -q) /. 2a - (w) px x h(()) 4) drdq.
(37)
R=U qEAM
constant WiF. I-
R-1 Σ
P (h(x) - - qa(1 - 91) 1 p 1h(x) = 4) dx dq.
(38)
qEAK
Σ
P (h(x) - gr( gx)dq.
(39)
qEAK
Next, we'll simplify the integral over q by marginalizing over all but the kth dimension.
K-1
I p(h) - a-u [x(()) - qx) p(h((x)) - Qu (a - qu d (40)
EDR-
km 2k q-
w.st. Sam
ΣΣ p(ha(X) 91)4(11 (1 - qu) / p(h 9- (X) qu .d dgp (41)
96
= Σ / p (fx(X))=
K-1
-x an) ga(11 an dnd...
(42)
km 94
Rewriting as just 9,
K-1 EDR = Σ /
P (hx(x)) = -0)g99/9) a(1 - -dd4
(43)
0= 9E(0.))
swap
Σ (ha(X) = dy.
q(1 ②)
(44)
4E
This is indeed the same term Eq 25, thus completing the proof.
B.2 PROOF OF THEOREM 4.1 AND VARIANCE OF DISAGREEMENT
Since Theorem 4.1 is special case of Theorem B.I, we can easily prove the former:
Proof. Observe that if h satisfies the class-wise calibration condition in Definition 4.2, it must also satisfy class aggregagge calibration.
(Y = k (x)( = 4) vk:
(45)
17

---

Published as a conference paper at ICLR 2022
ER- - L p( ΣK- p()x
Σ p (o hx(x)) = =q) p(hu(X)) = (46)
EK-1 ((hx(()) -
Then, we can invoke Theorem B.1 to claim that GDE holds.
The theorem above shows that in expectation, the disagreement of independent pairs of hypotheses equal to the test error of 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 single pair of independent models to accurate estimate the test error.
Corollary B.1.1. If GDE holds and there exists K. E HA
[ 1]
such that, for all h, h in the support of
Dis(h, h²) S (TestErr(h) + TestErr(h')),
then
Vara, (Dis(h, h²)) < 2x Var (TestErr(h)) + (4x²² 1) ETE".
Proof. First we write the expression for the exact variance of the disagreement:
Varn, (Dis(h,)))) = En (h, N0)3] EDR?.
(47)
By the assumption:
Ha [is(
(48)
S n. " EA
(TestErr(h) + TestErr(h')))
(49)
S n x>"E,,'~EEE (Te) + ( + TestErr(N')]]
(50)
Since and 1/ are independent and identically distributed, the expectation of the cross term equal to the product of each expectation and the second moments are equal:
ER [his(h, N0 < x? (2Eh TestErr + 2ETE?)
(51)
R² (2 [estErr(h))] 2ETE² + 2ETE + 2ETE")
(52)
xx (2Var
(TestErr(h)) + 4ETE²)
(53)
Substituting the inequality back to (47):
Vara, (Dis(h, h²)) S x² (2Var (TestErr(h)) + 4ETE*) EDR2.
(54)
By the GDE, we know that ETE EDR:
Var (Dis(h, H)) S 2k 2x² Var (TestErr(h)) + (4x² - 1) ETE?.
(55)
Remark. This corollary characterizes the worst-case behavior of the disagreement error's variance and relates 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 ex- hibits 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 supported by the first columns of Table I 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 h') < TestErr(h) + TestErr(A') is always true, since it follows directly from the triangle inequality: however, this would imply that there exists a pair of hypotheses 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 highly structured manner, suggesting is much smaller than 1 in practice. On the other hand, if = 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 half of test error variance. In practice, Table and 3 show that the variance of disagreement is approximately equal to the variance of the test error, suggesting that falls somewhere between 1 and 1. This supports the hypothesis that the models make errors in a structured manner which gives rise to the observed phenomena.
18

---

Published as a conference paper at ICLR 2022
B.3 DISAGREEMENT PROPERTY UNDER DEVIATION FROM CALIBRATION
Recall from the main paper that we quantified deviation from class-aggregated calibration in terms of CACE. Below, provide the proof of Theorem 4.2, which shows that GDE holds approximately when CACE is low.
Proof. Recall from the proof of Theorem B.1 that the expected test error (ETE) satisfies:
K
/
ETE =
Σ = (x)
=x)= (1 - 1)dg
ge 0.1]
subiract and addd q ΣK-n p(hx(()) =9)
Σ = kx,) 9) -9 pp)( =0) (()
p(h)(()=
(1 (1-9)dg 9)g
k=
K
Σ p(h((x) = 19(1-9)dd g)dgg.
4E(0.1]
k=0
Recall that the second term on R.H.S is equal to the expected disagreement rate EDR. Therefore,
ETE - EDR| =
JOE(D.))
/
K
Σ
= = h,) = 9) - Σ
K
2 p(ho(x)= a)) (1 (1-g)dg. g)dq.
k=0
Multiplying and dividing the inner term by ΣK-1 p(hnx = 4).
V
ΣK-I p(Y = h hX) = 9)
K
ETE EDR|
=
Σ ((h = 9) gddq
Σkzo p(1 = =))
k=
/
MA k ply = k, (X) 2)
9
Σ ((h((X) =9) (1-)) dg
②)
4Ej0.1]
mk p( p(11111 (X) =9)
S1
/
Ek=o p(Y = k, hu
K-1
K-1
Σ ((hx(X)= dg
E p(ha(()) =
qE(0.1]
CACE(A).
Note that it is possible consider more refined definition of CACE that yields tighter bound on the gap. In particular, in the last series of equations, we can leave the 1 as it is, without upper bounding by In practice, this tightens CACE by upto a value of 2. We however avoid considering the refined definition as it is less intuitive an error metric.
B.4 CALIBRATION IS NOT A NECESSARY CONDITION FOR GDE
Theorem B.1 shows that calibration implics 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 B.1. For stochastic algorithm A to satisfy GDE, it is not necessary that its corre- sponding ensemble h satisfies class-aggregated calibration.
Proof. Consider example where h assigns probability of either 0.1 or 0.2 to class O. In par- ticular, assume that with 0.5 probability over the draws of (x, y) D. ho(w)) 0.1 and with
19

---

Published as a conference paper at ICLR 2022
0.5 probability, hx(x)) 0.2. The expected disagreement rate (EDR) of this classifier is given by E (2)(2)/z (1) 2 (.1-0.9-0200)) 0.25.
Now, it can be verified that the binary classification setting, class- aggregated and class-wise cali- bration are identical. Therefore, letting p(Y
(X) = 0.1) _ 61 and p(Y = 0 hx( = 0.2) _ E2, our goal is to show that it is possible for e1 # 0.1 or e2 + 0.2 and still have the expected test error (ETE) equal the EDR of 0.25. Now, the ETE on 2 conditioned on ho(z) = 0.1 is given by (0.1 c1) + 0.9e;) and on ha) = 0.2 is given by (0.2(1 E2) + -..8e1). Thus, the ETE on 9 is given by 0.15 + (..(0. + 0.Geg). We want 0.15 + 0.5(0.8e) + 0.6e2) 0.25 or in other words, 0.8c1 + 0.6c2 = 0.2.
Observe that while 6 0.1 and 62 = 0.2 is one possible solution where á would satisfy class- calibration, there are also infinitely many other solutions for this equality to hold (such as say 61 = 0.25 and 62 = 0) where calibration does not hold. Thus, class- aggregated/class- wise calibration is just one out of infinitely many possible ways which h could be configured to satisfy GDE.
wise calibration/llas--ggrree
B.5 COMPARING CACE TO EXISTING NOTIONS OF CALIBRATION.
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 cali- bration. Class-wise calibration is notion of calibration that has appeared originally under different names in Zadrozny& & Elkan; Wu & Gales (2021). l). On the other hand, the only closest existing notion to class-aggee calibration seems be that of static calibration in Nixon et al. (2019), where is only indirectly defined. Another existing notion of calibration for the multi-class setting is that of strong calibration (Vaicenavicius al., 2019; Widmann et al., 2019) which evaluates the accuracy of the model conditioned on I(() taking a particular value the K-simplex. This 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.
B.6 THE EFFECT OF DIFFERENT STOCHASTICITY.
Compared to AlIDiff /Di ffData, DiffInit t/Order is still well-calibrated, with only slight devia- tions. 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 Di 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 (Dif fffffiit t exhibits the same effect as Di ffData. 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 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 latch on to different predictive features (even when exposed to the same training set), and thus result in ensembles with better test accuracy. Ex- tending their study to understand similar effects on calibration would be a useful direction for future research.
20

---

Published as a conference paper at ICLR 2022
C APPENDIX: EXPERIMENTAL DETAILS
C.I PAIRWISE DISAGREEMENT
In this work, the main architectures we used are ResNet18 with the following hyperparameter con- figurations:
1. width multiplier: {1x, 2x}
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 multiplied by the width multiplier). All models are trained with SGD with momentum of 0.9. The learning rate decays 10x every 50 epochs. The training stops when the training accuracy reaches 100%.
For Convolutional Neural Network experiments, we use architectures similar to Network-in- Network (Lin et al., 2013). On a high level, the architecture contains blocks of convolution followed by two 1 convolution (3 layers in total). Each block has the same width and the fi- nal layer is projected to output class number with another x convolution followed by 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, 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
21

---

Published as a conference paper at ICLR 2022
On each of these domains, train 5 pairs of ResNet50 with linear layer 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 data. We then evaluate the test error and disagreement rate of all pairs on each the four domains. We consider both randomly initialized models and ImageNet pre-trained models (Deng al., 2009). For pre-trained models, only the linear layer is initialized differently between the two models in pair.
the
C.2 ENSEMBLE
For ensembles, unless specified otherwise, we use the combination of the first option for each hy- perparameters in Section C.I.
C.2.1 FINITE-SAMPLE APPROXIMATION OF CACE
For every ensemble experiment, we train a standard ResNet 18 model (width multiplier 1x, initial learning rate 0.1, weight decay 0.0001, minibatch size 200 and no data augmentation).
To estimate the calibration, we use the testset Drest- We split [0, 1] into 10 equally sized bins. For class k, group all (x, y) E Diest into different bins B according to (x) (all bins have boundaries that do not overlap with other bins). In total, there are 10 K bins.
{ (x. v) lower(BB)) < (x) < upper(BB.) (B.)) and (x, v) E Dreet B =
(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 single bin B, Uk=1 B in weighted manner. Concretely, for each bin, sum over all the classes when computing the accuracy:
K
(C.( Σ k= B
Σ
1yy= k]
Σ (x.y))
1ly - k]
(57)
B
(2.
To quantify the how "far" the ensemble from the ideal calibration level, we use the Class Aggre- gated Calibration Error (CACE) which is an average of how much each bin deviates from weighted by the number of samples in the bin:
Ns B.J
CACÉ
[acc(B.) conf(B:)]
(58)
Drest
where Ng is number of bins (usually 10 in this paper unless specified otherwise). conf(B;) is the ideal confidence level the bin, which we set the average confidence of all data points in the bin. This is the sample-based approximation of definition 4.4.
C.2.2 FINITE-SAMPLE APPROXIMATION OF ECE
ECE is widely used metric for measuing calibration. For completeness, will reproduce its approximation here. Let y be the class with highest probability under (we omitting the depen- dency on X in the notation since it is clear):
ÿ arg max hu (X)
(59)
ke[K]
We once again split [0, 1] into 10 equally sized bins but do not divide further into K classes. Each bin constructed as:
B, (x.y) y) lower(B.) hg(x) upper((B)) and (x, v) E Diest
(60)
22

---

Published as a conference paper at ICLR 2022
With the same notation used for CACE, the accuracy is computed
(Cc(
Σ
1 - 5l
(61)
B
(r.y)E
Finally, the approximation of ECE is computed the following:
N8
[B
ECE
|ace(B;))
conf(B3))
(62)
D
Drest
23

---

Published as a conference paper at ICLR 2022
D ADDITIONAL EMPIRICAL RESULTS
D.1 ADDITIONAL FIGURES
confoencce
corridence
confieecce
comfidence
Figure 7: Calibration on 2k subset of CIFAR1O: Calibration plot of different ensembles of 100 ResNet18 trained CIFAR10 with 2000 training points.
10
22
22
30
30
Conteence
confience
corfsence
confeence
Figure 8: Calibration on CIFAR100: Calibration plot of different ensembles of 100 ResNet18 trained on CIFARI00 with 10000 data points.
4.34
ANl Ever
pretaan
choto
SUFEET
Bant amr
CACE
CACE
CACE
CACE
Figure 9: Calibration error vs. deviation from GDE under distribution shift: The scatter plots of CACE (x-axis) the gap between the test error and disagreement rate (y-axis) averaged over an ensemble of 10 ResNet50 models trained on PACS. Each plot corresponds to models evaluated on the domain specified in the title. The source/training domain indicated by different marker shapes.
D.2 CIFAR 1 10 CALIBRATION TABLE
Here we present the calibration error for ResNet18 trained on CIFARI00 with 10k training exam- ples.
D.3 OTHER DATASETS AND ARCHITECTURES
In Fig 10, we provide scatter plots for fully-comnected networks (FCN) on MNIST, and convolutional networks (CNN) on CIFARIO. We observe that when trained on the whole MNIST dataset, there is larger deviation from the y behavior (see left-most image). But when reduce the dataset size to 2000, we recover the GDE observation on MNIST. We observe that the CNN settings satisfies GDE too.
24

---

Published as a conference paper at ICLR 2022
Test Error
Disagreement
Gap
CACE
Art + Art
0,0518 40.0107
0.0685 4-0.0133
0.0166
0.0505
Art Cartoon
0.3229 50.0365
0.2524 40.0446
0.0705
0.2577
Art + Photo
0.0509 2097
0.0592 20.0156
0.0082
0.0335
Art + Sketch
0.3871 #0.0613
0.3639 #0.079
0.0231
0.2374
Cartoon + Art
0.2555 0203
0.2534
1:00226
0.0020
0.1121
Cartoon Cartoon
0.0303 =0.0 18
0.0380 10.0150
0.0077
0.0308
Cartoon + Photo
0.1361 1: 20.0222
0.1327 4:0 10.0201
0.0034
0.0580
Pretrained Cort + Sketch
0.2672 #0.0200
0.2398 +0.0326
0.0273
0.1322
Photo Art
0.3315
0.2649 1:0 .624
0.0666
0.2943
Photo + Car
0.6721 10 0645
0.2100 1:0 0.000001
0,4621
1.0725
Photo + Photo
0.0245 10.01100
0.0322
10.0125
0.0076
0.0460
Photo + Sketch
0.7180 #0.0774
0.2497
+0.1350
0.4683
0.8507
Sketch + Art
0,5187 10.0598
0.4144
1:007669
0,1042
0.4274
Sketch Cartoon
0.3064 0.0000
0.2557
1:00349
0,0506
0,2069
Sketch + Photo
0.5203 #0.0 30.0495
0.2908
20.0618
0.2295
0.5245
Sketch + Sketch
0.0443 20.0067
0.0460 #0.0074
0.0016
0.0389
Test Error
Disagreement
Gap
CACE (10
Art + Art
0.3821 10.0137
0.3545 10.0361
0.0276
0.2021
Art + Cartoon
0.6337 10.0320
0.4764 10.0481
0.1573
0.6267
Art > Photo
0.4443 #0.0277
0.3161 +0.0300
0.12821
0.4778
Art > Sketch
0.6517 #0.0337
0.5513 #0.0097
0.1004
0.5169
Cartoon + Art
0.6911 10.0158
0,4186 1: 0528
0.2725
0.8669
Cartoon toon
0.1910 10.0163
0.1817
0.0092
0.0981
Cartoon Photo
0.6 +0.0439
0.4070 #0.0022
0.1929
0.6207
Pretrained
Car toon + Sketch
0.6084 #0.0720
0.5072 #0.0767
0.1012
0.4767
Photo Art
0,6899
0,4301 10.00 0.0085
0,8119
0,2598
Photo Cartoon
0.7293 10.0222
0.4431 10.0566
0.8905
0.2862
Photo + Photo
0.2281 18.0166
0.1868 #0.0258
0.1791
0.0413
Photo + Sketch
0. D.7822 =0.021
0.2388 10.1 1180
0.7954
0.5435
Sketch + Art
0.8110 10.0164
0.6044 20.0620
0.2068
0.9540
Sketch Cartoon
0.6215 10.0114
0.4882 10.0522
0.1332
0.5785
Sketch + Photo
0.8204 10.0202
0.4868
20.0875
0.3335
0.9615
Sketch + Sketch
0.1066 +000094
0.0989 40.0122
0.0076
0.0601
Table 2: Calibration error vs. deviation from GDE under distribution shift: Test error, dis- agreement rate, the gap between the two, and CACE for ResNet18 on PACS over 10 models cach.
Test Error
Disagreement
Gap
CACE
ECE
AlIDiff DiffData
0.679 0.0098
0.6947 = 0.0076
0.0157
0.1300
0,0469
0.682 0.0110
0.6976 0.0074
0.0150
0.1354
0.0503
DiffInit
0.681
0.5945
0.0865
0.3816
0.1400
DiffOrder
0.679 0.0097
0.5880 + 0.010s
0.0910
0.3926
0.1449
Table 3: Calibration error vs. deviation from GDE for CIFAR100: Test error, disagreement
rate, the gap between the two, and ECE and CACE for ResNet18 on CIFAR100 with 10k training examples computed over 100 models.
D.4 ERROR DISTRIBUTION OF ENSEMBLES
Here (Fig 11) show the error distribution of the ensemble similar to N&B'20. The x-axis of these plots represent 1 - h, (X) in the context of our work. As N&B '20 note, these plots not bimodally distributed on enror and random- caaddom-cassffcaationeewee error (of K-1 where K is the number of classes). This disproves the easy-hard hypothesis as discussed the main paper. As a side note, observe that all these emror distributions can be fit well by Beta distribution.
25

---

Published as a conference paper at ICLR 2022
MNA Datiids plos hard
0104
03.
3.00
340
5000
011
325
C315
0002
MNIST FCN
(b) MNIST FCN, 2k dat-
(c) CIFARIO CNN
apoints.
Figure 10: Scatter plots for fully conneced and convolutional networks on MNIST and CIFAR-10 respectively.
FON MNSS
CNN CIFAR
Reshiatt CIRARTO
100
600
200
1-P0100 51
1-P0000 31
(a) Error distribution for the MNIST FCN experi- ment
(b) Error distribution for the CIFARIO CNN periment
Error distribu-
tion for the CIFARIO
ResNet18 experiment with SameInit
Figure 11: Error distributions for different experiments
CINN, AILHI
cless NNNSS ABLiv
clace, Al LA!!
1000
0930
5000
MA0C
nuubber 0000
conTideriod
confidonnos
confidencc
(a) CIFARIO + CNN
ResNet18 (b) MNIST + 2 layer FCN (c) Full Resarl0
Figure 12: Histogram of calibration confidence for different settings.
D.5 CALIBRATION CONFIDENCE HISTOGRAM
Here (Fig 12) 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 hz(x) p for some & and some x.
D.6 COMBINING STOCHASTICITY
In Fig 13, for the sake of completeness, consider 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 Di ffData and Di ffInit.
26

---

Published as a conference paper at ICLR 2022
SamiDora
010
A35
0.0
900
(a) Calibration plot
Figure 13: The scatter plot and calibration plot for model pairs that use the different initialization and different data ordering.
condernce
confideric
confideric
confidercce
(a) CIFARIO
(b) CIFARIO's calibra- tion plot
(c) CIFARIO0
(d) CIFAR100's calibra-
tion plot
Figure 14: The calibration plot for 5 randomly selected individual classes vs the aggregated calibra- tion plot for ResNetl 8 trained CIFARIO and CIFAR100.
D.7 CLASS-WISE CALIBRATION VS CLASS-AGGREGATED CALIBRATION
In Fig 14, we report the calibration plots for a few random classes the CIFARIO and CIFAR100 setup and compare it with the aggs-eggee 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 similar effect also happens for ECE, although not reported here.
D.8 CORRELATION VALUES IN FIG
In the main paper figures, we quantified correlated via Rº and for scatter plots that include both data-augmented models and non-data-augmentt models. Here, we report these values specific to each group of models.
AllDiff
DiffData
DiffOrder DiffInit
w/o aug w aug both
0.888
0.977
0.728
0.923
0.984
0.963
0.737
0.881
0.986
0.998
0.941
0.983
Table R² values
AllDiff
DiffData
DiffOrder 0.582
DiffInit
w/o aug
0.752
0.891
0.771
w aug
0.829
0.891
0.626
0.650
both
0.899
0.948
0.807
0.858
Table 5: values
27

---

Published as a conference paper at ICLR 2022
D.9 MORE THAN ONE PAIR MODELS
Here, we show the ResNet18 CIFAR-10 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.
Difst el 6-003 bour 1T
1=12 C.ls
022
011
0100
011
316
014
diagrsement
(a) The seatter plot the disagrcements of the average disagree- ments of 4 pairs of models.
(b) The scatter plot for
pair of models.
However, we instead measure the distance from the y = x line. Specifically, each pair's deviation measured as
TestError Disagreement]
(63)
0.T + Disagreement)
The denominator normalizes the deviation hyperparameters with different performance contribute equally. Then, we observed that 1 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.
28


Reviews:
[{"review_id": "ZxIENUB3G5", "reviewer": "Reviewer_DeNB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "## Strengths\nThe main empirical observation, that the disagreement rate is nearly equal to test error across variations in architecture and hyperparameters, is surprising to me. (I would probably have expected disagreement to be more than 1.3x lower than test error for variations in random seed.) This experimental finding is a valuable contribution to the literature in and of itself. It is, as the authors note, a tantalizing connection between generalization and calibration. And the authors' explanation of this observation by reduction to a calibration property is clever and convincing (though as they note it only explains it in expectation). The paper is well-written.\n\nThe notion of \"class-aggregated calibration\" introduced in this paper is natural. The proofs that I checked appear to be correct. I was glad to see an attempt at an analysis of the variance of disagreement in the form of Corollary A.1.1, weak though it is.\n\n## Weaknesses\n\nThe correlation between disagreement rate and test error is strong for random initialization and order but not as strong as it is for freshly drawn training sets. It also appears that much of the correlation might be coming from the affect of data augmentation being turned on or off. I would have liked to see plots where the disagreement rate is averaged across more than one pair of runs—how much stronger does the correlation with test error get? This is crucial to judging how effective disagreement would be in practice as a tool for predicting test error with unlabeled data. (The fact that there is correlation isn't surprising—it is intuitive that more error-prone classifiers will disagree more). More generally I would say that the main weakness of the paper is that it doesn't really attempt to present a strong case for the usefulness of the main observation in practice. That being said, the novelty of their empirical result and conceptual explanation are enough to make the paper worthy of acceptance in my opinion.\n\nThe proofs in the paper are quite straightforward (though somewhat long-winded because each small step is written explicitly); the theoretical innovation is in the statements, not the proofs.\n\n## Other thoughts\n\nAs the authors mention, the study of calibration of neural network ensembles has primarily focused on their softmax probability outputs. Does softmax calibration imply anything about metrics of disagreement of softmax outputs (via, say, KL divergence)? I don't have much familiarity with the literature on calibration of neural network ensembles, so I don't know how novel this paper's discussion of that topic is.", "summary_of_the_paper": "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).\n\nThe 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.", "summary_of_the_review": "I am recommending acceptance because this paper presents a surprising, simple experimental result and provides a satisfying partial explanation which connects test error disagreement to calibration. Ideally there would be more thorough experiments and more exploration of whether the experimental result is useful, but the paper is substantial enough that it is okay if such additions are left to future work. (Because of these qualms I would give the paper a score of 7 instead of 8 if it were possible to do so.)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YDzzbgTEPgi", "reviewer": "Reviewer_sYb8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "Strengths:\n- The connection between calibration and generalization is novel. The theoretical results are sound.\n- This paper shows stronger results than prior work (Nakkiran & Bansal 2020) with more practical implications-- being able to approximate the test error without a separately labeled dataset, given calibration.\n- Experiments are through and sound.\n- Paper is well written and easy to follow.\n\nWeaknesses:\nThe data for DiffOrder and DiffInit deviates from the y=x curve more than the other two cases where a fresh dataset is used, so in practice, it’s still more accurate to use a fresh-labeled dataset.\n\nComments:\n- On the last line on page 6 “namely ½ if x is hard, and 0 if easy”, is ½ supposed to be 1/k where k is the number of classes?\n- Page 7: typo in “even though an ensembe of one or…”\n\n--- Update ---\n\nI have read all the reviews and I am satisfied with the authors' responses. \n", "summary_of_the_paper": "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. ", "summary_of_the_review": "This paper has novel contributions with both theoretical and practical implications. I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GWajQVZ2kg", "reviewer": "Reviewer_5dWv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": " **Strength** \n\nThe paper marks a significant advance in the understanding of the generalization of deep neural networks trained with SGD. Specifically, a theoretical connection between generalization and calibration is provided. This opens up new opportunities and inspiring directions for the study of generalization in deep learning.  The theoretical analysis is sound and the experimental results are convincing. The paper is also beautifully written and a pleasure to read.\n\n**Weakness**\n\nAs the authors also acknowledge, why and when SGD (or any given learning algorithm) is well-calibrated remains unclear and requires further characterization. It is also curious that the prediction disagreement of a pair of learned models from SGD appears to have low variance. Finally to what extent the development of this paper will truly impact further understanding of deep learning is yet to be seen. But rather than considering these as weaknesses, I tend to think of them more positively, as being inspiring and pointing to new directions. The contributions of this paper in my opinion well justify an acceptance decision. \n\nThe writing of the paper is occasionally sloppy, for example, in the proof of Theorem 4.1, the authors speak of ${\\scr D_q}$ as if it is a set (rather than a distribution), in, for example,  \"calculate the error on ${\\scr D_q}$\", \"a $q$ fraction of ${\\scr D_q}$\" etc. \n\nThe authors are also encouraged to provide more intuition in the main body of the paper regarding the key insights in the proofs. Although the proofs are not difficult to follow, the reader is likely to be buried in their technical details without truly appreciating the fundamental reasons for which the theorems are true.\n\nFinally, the developed theory is not limited to the context of SGD. It might be a good idea to reflect the generality of the theoretical results in the paper title. -- a suggestion, not a weakness.\n\n**Overall Recommendation**\n\nOverall I recommend the acceptance of this paper without any reservation. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper contains novel and inspiring empirical observations, which are justified by establishing a relationship between generalization and prediction disagreement of two models learned independently using SGD.  The paper is also well written.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BNiHfYDSH_y", "reviewer": "Reviewer_APKH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "Strengths:\n\nI think the GDE phenomenon presented in this paper is quite novel, and in my opinion, this message could be quite interesting to the DL theory / phenomena community. The core theoretical observation that calibration implies GDE does have a simple proof, admittedly, but I think the contribution is more in identifying the correct design choices to allow this theorem (e.g. consider ensemble of one-hot predictions rather than ensemble of probabilities), which I think is somewhat non-trivial. Also, although it is still a bit opaque why calibration happens, the connection itself (between calibration and GDE) is kind of convincing and may motivate further research from both perspectives. \n\nI also think the experiments in this paper are thorough and quite well-executed. The common variants (architectures, datasets, various notions of stochasticity, out-of-distribution performance) are sufficiently tested. Some of the more advanced questions arising from the theory (e.g. does ${\\rm Dis}(h, h’)$ concentrate around its expectation, which I did wonder) are also tested via experiments. \n\nWeaknesses:\n\nIt is a slight concern that the core observation in this paper is quite similar to Nakkiran and Bansal (2020)---Even though the authors already have a somewhat detailed comparison in the related work section, I am still left with some questions. Specifically, I get an idea of what is the difference in the empirical results (DiffData vs. the newly proposed DiffInit and DiffOrder), but am still unclear in the theoretical / formulational aspects: Did they propose GDE as-is (in expectation over h, h’), just restricted to the “DiffData” version? Also in the “they proved GDE specific to 1-NN models trained on different data”, did they not assume calibration but rather rely on something else to get that theorem?\n\nAlso, the main theoretical result is not end-to-end---calibration implies GDE, but no clues on when calibration happens in the first place. The authors discussed this on Page 9 and I suggest they also make sure various earlier claims reflect this limitation, when appropriate. \n\n---\nUpdate: I thank the authors for their response and updates to the paper. I am satisfied with the responses and would be glad to keep my current evaluation.", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper presents GDE, an empirical phenomena about the generalization of deep learning, with novel theoretical justifications via the connection to calibration, and thorough experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article introduces an interesting variant of the work of Nakkiran & Bansal (2020). It shows empirically that the test error of deep models can be approximated from the disagreement on the unlabelled test data between two different trainings on the same data. The authors then show theoretically that a calibration property can explain such behaviour, and they report experiments showing that the relationship does exist in practical situations.  All reviewers agree on the practical and theoretical value of the article, which is very well organised and written. The ideas developed here are likely to lead to further work in the future, and they clearly deserve to be published at ICLR.

I agree with one of the reviewers that the title is somewhat misleading, as the reader expects an analysis based on SGD. The title could be shortened to "Assessing Generalization via Disagreement", and the experimental restriction to SGD could be mentioned in the abstract.
Decision: Accept (Spotlight)