Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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. 
main_review: Strengths:
- The connection between calibration and generalization is novel. The theoretical results are sound.
- 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.
- Experiments are through and sound.
- Paper is well written and easy to follow.

Weaknesses:
The 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.

Comments:
- 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?
- Page 7: typo in “even though an ensembe of one or…”

--- Update ---

I have read all the reviews and I am satisfied with the authors' responses. 

summary_of_the_review: This paper has novel contributions with both theoretical and practical implications. I recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review:  **Strength** 

The 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.

**Weakness**

As 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. 

The 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. 

The 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.

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

**Overall Recommendation**

Overall I recommend the acceptance of this paper without any reservation. 

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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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).

The authors prove that test error will equal disagreement rate _in expectation_ for any stochastic learning algorithm whenever the algorithm's predictions have a certain calibration property.
main_review: ## Strengths
The 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.

The 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.

## Weaknesses

The 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.

The 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.

## Other thoughts

As 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_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.)
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: Strengths:

I 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. 

I 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. 

Weaknesses:

It 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?

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

---
Update: 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_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.
review_title: null

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)