Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a new notion of ``distributional generalization". It formalizes this through a conjecture (feature calibration conjecture) which says that the output distribution of an interpolating classifier matches the distributions of the labels on a certain class of sub-groups of the data. The paper evaluates this conjecture empirically, and also proves it for certain nearest neighbor models.
main_review: The feature-calibration conjecture seems interesting at first sight, but I'm not sure it is really saying that much, which is my main concern for the paper.

Though generalization in learning theory is often summarized as just train performance $\approx$ test performance, what it really talks about is concentration of measure. With this in mind, if we define any subgroup of the data (such as in Experiment 1, where the subgroups are the different animals), then if the model is generalizing it's training and test performance on the subgroups will be approximately equal---I'm not sure why the authors are regarding this experimental finding as surprising or novel. This just follows from the fact that the generalization bounds hold for all subsets in any partition of the space as well, at most suffering some union bound to get uniform bounds for all subgroups in the partition. The authors don't repeat Experiment 1 for the MLP model which is not expressive enough to identify the different sub-groups, but they repeat a similar experiment in Fig. 6. For the MLP model, the training and test numbers differ by at most 1-2%, as one would expect based on generalization bounds. If one argues that the numbers differ slightly less across the groups in Fig. 5, that seems just a consequence of the fact that the model in Fig. 5 has an overall generalization gap which is very small (smaller than a percent it seems), and therefore even if one does a union bound across the 10 subgroups we will still get very small error on all groups. One gets a tiny bit more in Fig. 6 but I'm not sure if that is so important. And if the authors believe somehow that this difference is in fact important, then I think the entire argument needs to be rewritten to take this into account.

To summarize, an interpolating model will match the training distribution, and if it is generalizing, it will match the test distribution on any not too large partition of the space (to avoid too large factors in the union bound). Therefore, Fig. 1 is not surprising, given the fact that models which interpolate can still generalize. Of course, there is the mystery of why interpolating models generalize at all, but that's another story.

There are strengths to the paper too, the definition and subgroup property is interesting, and the experiments are well carried out (though it seems that the authors don't include any code). There could be merit in exploring the idea further, but at present it falls short of the mark in my opinion.
summary_of_the_review: As mentioned below, the overall framework is not convincing to me and hence I recommend rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper argues about considering entire distribution of classifier behavior rather than a traditional single metric view (test error). The distribution can highlight the areas where the errors actually occur. The paper analyzes datasets with perturbed labels and shows how the classifiers will perform on these perturbed training data. It presents a conjecture that when conditioned on "distinguishable features" the distribution on output is similar to that of distribution of true labels. 
The authors present some examples where "distinguishable features" depends on classifier. They prove the conjecture for nearest neighbors classifier under some regularity conditions. 
main_review: It is true that analyzing output distribution of classifier reveals more information than focusing on single metric. The paper provides decent examples to demonstrate the phenomenon where test (output) distribution mirrors that of true labels (supporting conjecture). The paper argues that this result is surprising in contrast to Bayes optimal classifier. 
But these results are rather intuitive and not that surprising for "overparametrized" networks. The theoretical analysis of conjecture stops at nearest neighbors and leaves the characterization of classifiers and distributions which obey conjecture to future work. The paper can benefit with more analysis and at least a rough proof sketch for distributional generalization for more general distributions and classifiers. The conjecture is mainly supported by few experiments and not much theory. 

summary_of_the_review: The paper introduces good albeit "unsurprising" conjecture. The paper doesn't support the conjecture with enough theoretical analysis and even the conditions are not fully defined and just relegated to "natural" settings. The paper stands as a good initial study but needs more analysis.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper reports an interesting phenomenon in deep over-parameterized networks which train to zero train error (known as interpolating networks). Not only does the accuracy on test mimic the accuracy on train, but the accuracy measured on certain subsets of the train set also matches that on the corresponding subsets in test set. The paper coins the term distributional generalization for this phenomenon. The paper then proceeds to perform a number of experiments across a bunch of image datasets to exhibit the generality of this phenomenon.
main_review: Strengths of the paper:
1.	It is well-written and the main ideas are clearly presented. The paper is also quite self-contained.
2.	The proposed empirical observation is novel to the best of my knowledge and a significant observation.
3.	The paper proposes a neatly formalized explanation behind the phenomenon and performs a good set of experiments to back their claim.

Weaknesses:
1.	Based on some efforts to reproduce the results on my end, it is not clear how strongly the proposed observation holds which might limit the significance of the contributions of the paper.

Comments and questions:
1.	What would constitute distributional generalization in the setting of regression? If I consider the setting of regression for a moment, the phenomenon appears to be less surprising: a reasonably smooth regression model which interpolates the train data would necessarily exhibit distributional generalization in that setting.
2.	It would help to see some error bars on the plots in Figure 2B. I tried replicating the toy example (classify CIFAR-10 classes as objects vs animals with label noise on cats) and observed that when label noise is 30% on the train data only 2-5% of cats in test set were being labeled as objects. The network used was a ResNet50 trained to train accuracy 96.2% using SGD with learning rate = 0.1, momentum = 0.9 and weight decay of 5e-4 and trained for ~160 epochs.
However, I did observe that when the label noise is increased to 70%, the distributional generalization effect was seen more strongly (test cats labeled objects 60-80% of the time).
3.	It would make for a stronger case if the paper reports the numbers observed when the label noise experiment is performed on image-net with 1000 classes as well (at least on the non-tail classes). This would further stress test the conjecture. Even if the phenomenon significantly weakens in this setting, the numbers are worth seeing.

Minor comments:
1.	AlexNet top-1 accuracy on ImageNet reported as 56.5%. Isn’t this 63.3%?
2.	Another minor comment is on the name used to describe the phenomenon: distributional generalization sounds a bit strong to capture the empirical phenomenon presented. It represents the ideal of the total variation between the test and train distributions of the network’s outputs vanishing to zero which might not be the case. It is hard to draw this conclusion from a few test functions on which the outputs match.

summary_of_the_review: The empirical phenomenon reported by the paper is novel to the best of my knowledge. It is also an important observation to be made in the behavior of deep neural nets. The paper presents a possible reason behind this behavior and this is formalized in a clean manner. Overall, the paper is very well-written and performs a comprehensive set of experiments to back their claims. I am not entirely convinced the observation holds in the strong form it is stated in but nevertheless I feel the paper’s contributions are sufficient for it to clear the bar for acceptance. Some changes in the empirical experiments which would help make the paper’s case stronger are (i) error bars on plots of label noise experiments (ii) label noise experiments on ImageNet data, (iii) including code in the supplementary material.
review_title: null

Meta-review: The paper proposes a new perspective on the generalization performance of interpolating classifiers based on the entire joint distribution of their inputs and outputs. It conjectures that, when conditioned on certain subgroups, the output distribution matches the distribution of true labels. The conjecture is investigated empirically on a number of datasets and models, and proved to hold for a simple nearest neighbor model.

This paper generated varying responses from the reviewers and a detailed discussion. One main concern focused on whether the feature calibration conjecture is actually surprising, given standard expectations about generalization from learning theory. Indeed, from the discussion and the paper itself, it seems the authors conceived of classical generalization as a statement about whether train performance $\approx$ test performance, whereas one reviewer remarked that "what it really talks about is concentration of measure." I agree with the importance of this distinction in general, though it is perhaps less relevant in the current setting of modern interpolating classifiers, for which so little about generalization is understood in the first place. In particular, the empirical observations of varied forms of good generalization behavior for overparameterized models are likely to be interesting to the community, regardless of whether this behavior might be expected in the large sample limit.

As such, this is a very borderline paper, with many good arguments both for and against acceptance. After a detailed discussion among the chairs, it was decided that the current version is just shy of the acceptance threshold, but I would strongly encourage the authors to address the main reviewer concerns and resubmit a revised manuscript to a future venue.
Decision: Reject