PaperlayerView exact revision on arXiv

Source-linked AI summary

Assessing Generalization of SGD via Disagreement

Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, J. Zico Kolter

arXiv:2106.13799v2cs.LGcs.AIstat.ML

TL;DR

The paper asks why disagreement between independently trained models can nearly equal their test error, then tests whether this also holds when models share training data but differ in SGD randomness. It reports that GDE is nearly satisfied in these settings and relates the equality in expectation to well-calibrated ensembles.

  • Problem

    Nakkiran & Bansal (2020) observed that models trained on independent datasets can disagree at nearly the test-error rate, raising the question of why this equality occurs.

    Source: §1 · p. 1

  • Method

    The paper measures disagreement between same-architecture networks trained on the same data with different random seeds and proves that calibrated ensembles from stochastic learners satisfy GDE in expectation.

    Source: §1 · pp. 1–2

  • Results

    GDE is nearly satisfied for several network types and datasets, including pairs trained on the same data, and the corresponding ensembles are empirically well-calibrated under the paper's definition.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Disagreement offers a direct estimate of test accuracy using unlabeled data and establishes a connection between generalization and calibration.

    Source: §1 · p. 2, §6 · p. 9

    The paper does not characterize when good calibration, and thus GDE, holds; without prior assurance, verifying calibration requires labeled test data.

    Source: §5 · p. 9

Abstract

from arXiv · show

We empirically show that the test error of deep networks can be estimated by simply training the same architecture on the same training set but with a different run of Stochastic Gradient Descent (SGD), and 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 second run to be on an altogether fresh training set. We further theoretically show that this peculiar phenomenon arises from the \emph{well-calibrated} nature of \emph{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.

1 INTRODUCTION

The paper extends disagreement-based test-error estimation to networks trained on the same data with different SGD randomness, including small error changes across hyperparameters. It connects this behavior to calibrated ensembles and motivates disagreement as a direct estimate from unlabeled data.

1 INTRODUCTION

  • Across SVHN, CIFAR-10/100, and several network architectures, same-data models with different random seeds disagree at roughly the test-error rate.The paper also reports that disagreement captures minute test-error variations under changes in width, depth, and batch size.Source: §1 · pp. 1–2
  • Under certain training conditions, GDE approximately holds on some PACS distribution shifts, but not all.The authors identify disagreement as a promising estimator for out-of-distribution accuracy in this setting.Source: §1 · p. 2
  • Disagreement estimates test accuracy using fresh unlabeled data, without requiring fresh labeled data or access to a model's internals.The authors describe it as a direct estimate that can work with a black-box model when labels or model details are costly or unavailable.Source: §1 · p. 2
  • The authors prove that a well-calibrated ensemble from a stochastic learning algorithm satisfies GDE in expectation over the algorithm's stochasticity.The result places no restrictions on the hypothesis class, algorithm, stochasticity source, or test distribution.Source: §1 · p. 2
  • The authors empirically find that SGD ensembles are well-calibrated under their definition, but do not theoretically explain why.Source: §1 · p. 2
  • Different sources of SGD stochasticity are almost equally effective for GDE and calibration; the paper also explores pre-training.Source: §1 · p. 2

2 RELATED WORKS

The paper situates disagreement-based estimation alongside complexity bounds, unsupervised accuracy estimation, calibration, and work on empirical deep-learning phenomena. It distinguishes its approach by using the original training process and linking GDE to class-aggregated calibration.

2 RELATED WORKS

  • Unlike complexity-based bounds, disagreement provides a direct estimate, while its guarantee requires knowing that the training procedure yields well-calibrated ensembles.Garg et al. (2021) require modifying the training set and careful early stopping, making their bound inapplicable to interpolating models; older bounds such as Madani et al. (2004) require independent training sets.Source: §2 · p. 3
  • Prior unsupervised accuracy-estimation work focused on out-of-distribution or specialized settings and often required specialized algorithms or extra task information.Concurrent work by Chen et al. (2021) also studies agreement-based accuracy estimation, with a more algorithmic focus.Source: §2 · p. 3
  • Unlike churn-reduction work, which targets reproducible predictions, this paper uses disagreement to estimate test error.Prior work also examined how different stochasticity sources can produce non-trivial disagreement rates.Source: §2 · pp. 3–4
  • Individual neural networks are often over-confident, whereas independently and stochastically trained ensembles tend to be naturally well-calibrated.Deep ensembles train members on the same data with different random seeds; this paper's theory requires class-aggregated rather than only top-class calibration.Source: §2 · p. 3
  • The paper connects GDE to empirical deep-learning phenomena and differs from Nakkiran & Bansal (2020), whose proof concerns 1-nearest-neighbor classifiers under specific distributional assumptions.Source: §2 · p. 4

3 DISAGREEMENT TRACKS GENERALIZATION ERROR

Across the reported datasets, disagreement between independently trained runs tracks test error closely, including when both runs use the same data. The section examines this relationship across stochasticity settings, low-data training, hyperparameter variations, and distribution shift.

3 DISAGREEMENT TRACKS GENERALIZATION ERROR

  • Two model copies vary in initialization, data ordering, and/or training data; disagreement is the proportion of test examples where their one-hot predictions differ.Test error is the expected misclassification rate, while disagreement is the expected rate at which the two predictions differ.Source: §3 · p. 4
  • Across CIFAR-10, SVHN, and CIFAR-100, disagreement tracks test error near y=x across stochasticity sources, with only slight deviations for DiffInit and DiffOrder.The plots compare pair-wise disagreement with the first run’s test error.Source: §3 · pp. 4–5, Figure 2 · p. 5, Figure 3 · p. 5
  • y=x to y=0.9x for AllDiff/DiffData and y=x to y=1.3x for DiffInit/DiffOrder bracket the typical points.R² and Kendall’s τ are generally above 0.85 across settings.Source: §3 · p. 5
  • Even at test errors of 0.5–0.6, the CIFAR-100 and 2,000-example CIFAR-10 plots show similar behavior, with some deviations.The points lie in y=(1 ± 0.1)x for AllDiff/DiffData and y=(1 ± 0.3)x for DiffInit/Order.Source: §3 · p. 5, Figure 3 · p. 5, Figure 4 · p. 5
  • Disagreement captures mild test-error variations induced by hyperparameter changes, extending Nakkiran and Bansal’s finding on larger variations from dataset-size changes.The supplied passage describes this as a stronger version of that finding.Source: §3 · p. 6
  • On PACS, GDE is approximately satisfied for many source-target domain pairs despite distribution shift; for pretrained models, three specified pairs are exceptions.Pretrained models often satisfy GDE better than randomly initialized models under distribution shift.Source: §3 · p. 6, Figure 5 · p. 6

4 CALIBRATION IMPLIES THE GDE

The paper links calibration of a stochastic learner’s ensemble to equality, in expectation, between test error and disagreement. It extends this result to a weaker class-aggregated calibration condition and shows that low calibration error yields approximate equality.

4 CALIBRATION IMPLIES THE GDE

  • Class-wise calibration of the ensemble on D is sufficient for the stochastic algorithm to satisfy GDE on D.The equality is over the algorithm’s stochasticity, not necessarily true for each pair of models.Source: §4 · pp. 6–7
  • Calibration makes expected disagreement and test error equal within each confidence-level set, even though their differences need not cancel point by point.The proof divides the distribution into confidence-level sets; the paper contrasts this with an easy-hard explanation that would require pointwise equality.Source: §4 · pp. 6–7
  • A single pair can estimate test error in practice despite two-member ensembles not being well-calibrated, suggesting unusually small variance across stochastic runs.The paper says it empirically verifies this variance behavior in Table 1.Source: §4 · p. 7

4.1 A MORE GENERAL RESULT: CLASS-WISE TO CLASS-AGGREGATED CALIBRATION

  • Class-aggregated calibration, which averages conditional probabilities across classes, is a weaker sufficient condition for GDE than class-wise calibration.Class-wise calibration implies class-aggregated calibration, whose definition weights each class’s conditional probability by the frequency of that confidence value.Source: §4.1 · pp. 7–8
  • GDE holds approximately when class-aggregated calibration error is low and holds perfectly when that error is zero.CACE weights the absolute calibration difference at each confidence value by the proportion of instances attaining it; it differs from top-class ECE.Source: §4.1 · p. 8
  • The calibration-to-GDE result applies to probabilistic classifiers generally, including an individual calibrated neural network using softmax probabilities.For such a network, disagreement between independently sampled one-hot predictions equals the test error of its softmax predictions.Source: §4.1 · p. 8

5 EMPIRICAL ANALYSIS OF CLASS-AGGREGATED CALIBRATION

The tested SGD ensembles nearly satisfy class-aggregated calibration across the considered stochasticity settings. CACE tracks the gap between test error and disagreement, although the empirical calibration evidence uses a particular ensemble definition and does not resolve when calibration should be expected.

5 EMPIRICAL ANALYSIS OF CLASS-AGGREGATED CALIBRATION

  • The calibration evidence concerns ensembles averaged over top-class predictions and the paper’s specific Definition 4.3, not the usual average-softmax ensemble output.The paper notes that common SGD ensembles average softmax probabilities, whereas its theory uses an average of top-class predictions.Source: §5 · p. 8
  • Across considered stochasticity settings, the calibration plots closely follow the x = y line, indicating near class-aggregated calibration.The plots show conditional probability on the y-axis and confidence q on the x-axis.Source: §5 · p. 8
  • CACE for AllDiff/DiffData is about 2 to 3 times smaller than CACE for DiffInit/Order, paralleling the behavior of |TestErr − Dis|.The paper reports CACE as an upper bound on the test-error/disagreement gap.Source: §5 · p. 9
  • The authors give no theoretical characterization of when good calibration holds, so confirming small CACE may require labeled test data.That verification would defeat the purpose of using unlabeled-data disagreement to estimate test error.Source: §5 · p. 9

6 CONCLUSION

The conclusion presents same-dataset, different-run disagreement as a near estimate of test error and connects this phenomenon theoretically to calibration. The related-work discussion distinguishes this result from prior work by its scope, in-distribution setting, and explanatory focus.

6 CONCLUSION

  • Two networks trained on the same dataset tend to disagree on unlabeled data nearly as much as they disagree with the ground truth.The paper links this empirical observation to the well-calibrated nature of SGD ensembles.Source: §6 · p. 9
  • The authors leave open why different sources of SGD stochasticity have similar effects on calibration and when calibration and GDE hold.They also identify unlabeled-data generalization estimation and links between generalization and calibration as directions for further work.Source: §6 · p. 9

A RELATED WORK

  • The theory makes standard calibration imply GDE, whereas Nakkiran & Bansal (2020) treated GDE and feature calibration as independent phenomena.Their GDE proof was specific to 1-Nearest Neighbor models trained on two independent datasets; this paper places no such restrictions on hypothesis class, algorithm, or stochasticity.Source: A RELATED WORK · p. 14
  • Unlike the out-of-distribution focus of related work, this paper studies in-distribution estimation with vanilla-trained blackbox models.It uses ensembles as a theoretical vehicle rather than developing an ensemble-learning algorithm.Source: A RELATED WORK · p. 14

B.1 PROOF OF THEOREM B.1

The proof establishes that class-aggregated calibration of a stochastic algorithm’s ensemble implies GDE. It equates expected test error and expected disagreement by expressing both through ensemble confidence values.

B.1 PROOF OF THEOREM B.1

  • The intuition is that within a confidence level set, predicted classes and ground-truth labels have matching distributions, making ensemble disagreement equal ground-truth error.The proof handles carefully the possibility that confidence level sets count the same data point multiple times.Source: §B.1 · p. 14
  • If a stochastic learning algorithm’s ensemble satisfies class-aggregated calibration on D, the algorithm satisfies GDE on D.The theorem is stated for a general stochastic learning algorithm and its corresponding ensemble.Source: §B.1 · p. 14
  • The proof expresses expected test error as an integral over confidence values and substitutes the class-aggregated calibration condition.It separately expresses expected disagreement through confidence values; that derivation does not use the calibration assumption.Source: §B.1 · p. 14

B.2 PROOF OF THEOREM 4.1 AND VARIANCE OF DISAGREEMENT

The appendix derives GDE from calibration and examines disagreement variance and deviation from calibration. It also bounds the expected test-error/disagreement gap by CACE, with a simpler but looser calibration-error definition.

B.2 PROOF OF THEOREM 4.1 AND VARIANCE OF DISAGREEMENT

  • The proof observes that a predictor satisfying class-wise calibration also satisfies class-aggregated calibration, and then invokes Theorem B.1 to claim that GDE holds.Source: §B.2 · pp. 17–18
  • The variance result supports estimating test error from a single independent model pair when GDE holds and the stated bound involving κ applies.The corollary introduces κ through a bound on pairwise disagreement relative to the two models’ test errors.Source: §B.2 · p. 18
  • Empirically, disagreement variance is approximately equal to test-error variance, suggesting κ lies between 1/2 and 1 and that model errors are structured.The paper contrasts this with the κ = 1/2 and κ = 1 extremes.Source: §B.2 · p. 18

B.3 DISAGREEMENT PROPERTY UNDER DEVIATION FROM CALIBRATION

  • When class-aggregated calibration deviates, low CACE implies that GDE holds approximately.CACE bounds the difference between expected test error and expected disagreement rate.Source: §B.3 · p. 19
  • A refined CACE definition can tighten the gap bound by up to 2, but the authors retain the less intuitive error metric.The refinement leaves the 1 − q factor in the derivation instead of upper-bounding it by 1.Source: §B.3 · p. 19

B.4 CALIBRATION IS NOT A NECESSARY CONDITION FOR GDE

The appendix separates calibration from necessity: calibration can imply GDE without being required for it, while several stochastic training choices are compared in the experiments. It also specifies the pairwise training setups and the ensemble configuration used.

B.4 CALIBRATION IS NOT A NECESSARY CONDITION FOR GDE

  • GDE can hold without class-aggregated calibration: the binary example has infinitely many solutions matching expected test error to expected disagreement, including uncalibrated ones.Calibration is one of many possible configurations satisfying GDE, not a necessary condition.Source: §B.4 · pp. 19–20

B.5 COMPARING CACE TO EXISTING NOTIONS OF CALIBRATION.

  • Top-class, class-wise, class-aggregated, and strong calibration are distinct notions, with strong calibration requiring about exp(K) equalities rather than K.The closest existing notion to class-aggregated calibration identified here is static calibration.Source: §B.5 · p. 20

B.6 THE EFFECT OF DIFFERENT STOCHASTICITY.

  • DiffInit/Order remains well-calibrated with slight deviations from AllDiff/DiffData, but the reason different stochasticity sources behave similarly remains unresolved.The proposed data-ordering explanation does not account for DiffInit; diverse function-space regions and multi-view learning are discussed as possible directions.Source: §B.6 · p. 20

C.1 PAIRWISE DISAGREEMENT

  • The pairwise experiments vary initialization, ordering, augmentation, architecture, and training settings; PACS pairs share 80% of a domain's data and are evaluated across four domains.PACS experiments include randomly initialized and ImageNet-pretrained models; for pretrained pairs, only the linear layer initialization differs.Source: §C.1 · pp. 21–22

C.2 ENSEMBLE

  • Unless stated otherwise, ensemble experiments use the first listed option for each hyperparameter in Section C.1.The default ensemble configuration is specified by the selected first options, rather than a separate setting.Source: §C.2 · p. 22

C.2.1 FINITE-SAMPLE APPROXIMATION OF CACE

The finite-sample CACE estimate aggregates calibration accuracy across classes within confidence bins and weights deviations by bin size; ECE uses top-class confidence bins. The appendix also supplies calibration plots and a CIFAR100 calibration table.

C.2.1 FINITE-SAMPLE APPROXIMATION OF CACE

  • The CACE estimate divides confidence into 10 bins per class, then aggregates class-specific bins to mitigate sparse samples at middling confidence levels.For each aggregated bin, accuracy is computed by summing over classes.Source: §C.2.1 · p. 22
  • CACE estimates calibration error by averaging each bin's deviation from ideal calibration, weighted by the number of samples in that bin.The ideal confidence is the bin's average confidence; the approximation usually uses 10 bins.Source: §C.2.1 · p. 22

C.2.2 FINITE-SAMPLE APPROXIMATION OF ECE

  • ECE uses 10 confidence bins based on the highest-probability class, rather than splitting bins by class.The passages describe bin construction, accuracy calculation, and the resulting ECE approximation.Source: §C.2.2 · pp. 22–23

D.1 ADDITIONAL FIGURES

  • Calibration plots show ensembles of 100 ResNet18 models trained on 2,000 CIFAR10 points and on 10,000 CIFAR100 points.A separate figure plots CACE against the test-error/disagreement gap under distribution shift, by evaluation domain and source-domain marker shape.Source: Figure 7 · p. 24, Figure 8 · p. 24, Figure 9 · p. 24

D.2 CIFAR100 CALIBRATION TABLE

  • The cited passage reports a calibration error result for ResNet18 trained on CIFAR100 with 10k training examples, identifying the model, dataset, and training-set size for that reported setting.Source: §D.2 · p. 24

D.3 OTHER DATASETS AND ARCHITECTURES

Additional dataset and architecture experiments find GDE behavior for convolutional networks on CIFAR10 and for MNIST FCNs when training data are reduced to 2,000 points; whole-dataset MNIST FCNs deviate more. The appendix also identifies PACS and CIFAR100 calibration tables.

D.3 OTHER DATASETS AND ARCHITECTURES

  • MNIST fully connected networks show greater deviation from GDE on the whole dataset, while reducing training data to 2,000 points recovers the observed GDE behavior.The comparison is shown in the scatter plots for the MNIST FCN setting.Source: §D.3 · p. 24
  • The CNN experiments on CIFAR10 also satisfy GDE, according to the reported scatter plots.The cited passage reports the result without giving a quantitative deviation.Source: §D.3 · p. 24
  • The PACS table is scoped to ResNet18 results over 10 models, reporting test error, disagreement, their gap, and CACE under distribution shift.Source: Table 2 · p. 25
  • The CIFAR100 table covers ResNet18 trained on 10,000 examples, reporting test error, disagreement, their gap, ECE, and CACE over 100 models.Source: Table 3 · p. 25

D.4 ERROR DISTRIBUTION OF ENSEMBLES

The appendix examines ensemble error distributions, calibration-bin occupancy, stochasticity combinations, class aggregation, correlation, and the number of model pairs. It reports non-bimodal error distributions and finds that additional pairs reduce average deviation from GDE.

D.4 ERROR DISTRIBUTION OF ENSEMBLES

  • The ensemble error distributions are not bimodal at zero and random-classification-level error, contrary to the easy-hard hypothesis; they fit Beta distributions well.Figure 11 presents the error distributions for the experiments.Source: §D.4 · p. 25, Figure 11 · p. 26

D.5 CALIBRATION CONFIDENCE HISTOGRAM

D.6 COMBINING STOCHASTICITY

  • Varying both initialization and data ordering together produces behavior similar to DiffData and DiffInit.The setting is called SameData in this passage.Source: §D.6 · p. 26, Figure 13 · p. 27

D.7 CLASS-WISE CALIBRATION VS CLASS-AGGREGATED CALIBRATION

  • Class-wise calibration plots vary more than class-aggregated plots; aggregating across classes makes calibration better-behaved.The passage notes a similar effect for ECE, although those plots are not reported.Source: §D.7 · p. 27, Figure 14 · p. 27

D.8 CORRELATION VALUES IN FIG 1

  • The appendix reports R2 and τ correlation values separately for groups of data-augmented and non-data-augmented models.Tables 4 and 5 contain the respective R2 and τ values.Source: §D.8 · p. 27, Table 4 · p. 27, Table 5 · p. 27

D.9 MORE THAN ONE PAIR OF MODELS

  • 0.112 average deviation for one model pair versus 0.034 for four pairs; additional pairs help estimate exact generalization error.The one-pair and four-pair comparison shows only marginal correlation improvement, while the normalized average deviation falls with four pairs.Source: §D.9 · p. 28
Loading 2106.13799v2…