Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This submission proposes a new type of generalization satisfied by interpolating classifiers (the primary focus), that is different from agreement between test error and train error as in classical learning theory. This type of generalization is largely motivated by empirical evidence across different models (neural networks, kernel regression & svm, decision trees) and theoretically for 1-Nearest Neighbors classification (Theorem 1). More specifically, the submission claims that for certain types of mappings x -> L(x) (termed "distinguishable features" -- i.e. they must be learnable to good test accuracy in the setting under consideration), the joint distribution of (L(x), y) where (x,y) pairs are drawn from the true distribution will be "close" to the joint distribution of (L(x), f(x)) on the test set, where f(x) is the trained model prediction.

List of contributions:
--Proposes that interpolating classifiers satisfy "distributional generalization." This is first more specifically formulated as the "Feature Calibration Conjecture" (FCC) in Section 3. A crucial component of this is to identify the types of features L(x) for which the calibration holds (Definition 1); roughly, if the feature is learnable from inputs x to good test accuracy in the setting under consideration (fixed algorithm, data distribution, number of samples, allowable error), then under that same setting calibration will be achieved. The authors prove FCC is true for 1-Nearest neighbors. The Feature Calibration Conjecture is not fully specified, in that there is an assumption of "natural distribution" D (which is such that the conjecture holds in the empirical settings considered).

--Empirical test of the FCC. The types of distinguishable features L considered include (i) the constant partition (calibration then implies the marginal distribution p(y) of the predicted labels matches that of the true label distribution); (ii) a "coarse partition" (L(x) is an "easy" classification task) and calibration holds for fine-grained label subgroups, for instance in Imagenet; (iii) "class partition" (classes that can be learned well from standard datasets, and the true label distribution is a noisy corruption of this); (iv) multiple features. Models investigated include neural networks (WideResnets and MLPs), kernels (standard and high-performing ones), and decision trees. 

--A definition for "distributional generalization" which subsumes the definition of feature calibration & classical generalization, and very preliminary evidence that this holds for non-interpolating models (a Wide Resnet model on CIFAR-10 during training). 

main_review: Originality: This work identifies & investigates an original empirical property that appears to be satisfied by interpolating classifiers. The proposed concepts (Feature Calibration) are general & seem distinct from any prior work to the best of my knowledge. (For example, the authors note that "standard" calibration is a particular case of Feature Calibration with specific choice of L(x).) I think this work is bold in what it seeks to accomplish (asking a fundamentally new question at the basis of learning theory, building evidence from diverse empirical examples) and makes a reasonable first step towards doing so. 

Quality: The quality of the work seems high. The authors give a number of different empirical examples with sufficient coverage across model diversity and provide a theoretically satisfied case (1-Nearest Neighbors). The authors note the limitations of the work (e.g. the FCC is specified in terms of "natural distributions" which has an unclear meaning) and are fairly thorough in addressing potential concerns & connections to other works. I was not able to identify significant shortcomings with respect to the conceptual formulation or message of the paper. I make some comments about diversity of empirical examples (with respect to datasets / partitions) below.

Clarity: The paper is clearly written and was straightforward to read.

Significance: I think this paper takes a risk in its premise, provides a reasonable amount of evidence in support of its main claims, and would spur further work in this area; as I was also not able to identify any major issues with the paper, this is the reason behind my suggested score. In Section 1.3 the authors discuss a number of consequences for learning theory which seem notable. This work tells us more about the implicit bias of models (though not just neural networks); most interesting I think is that in certain limits (e.g. when models are interpolating, and model size >> dataset size), models are not approaching the Bayes optimal classifier but sample from the distribution p(y|x). 

Other comments & questions:

--I find some mentions of "Bayes optimal classifier" to be confusing at times -- for instance, its usage in L268 seems to be with respect to argmax p(y | L(x)) (rather than argmax p(y|x)), if I understand correctly. Perhaps it is worth pointing this out and the connection between the two (e.g. in the setting where p(y|x) is discussed, section starting at L107). 

--In the empirical examples with label noise, why do the authors consider only sparse confusion matrices?

--I think this work has good empirical diversity across very distinct classes of interpolating models, but one place where the paper could be noticeably strengthened is diversity of examples with respect to the datasets / partitions L(x) that are considered. Apart from the constant partition L(x) = 0, all the partitions seem to be largely based off of semantic distinctions that are already available in datasets. (Because of this, I also wondered whether the behavior is largely inherited from the dataset and from the existing semantic structure within it.) Are there more complex L(x), that are not semantically constructed, that can be considered? Separate but related to this, is it valid to consider L(x) that have some knowledge of the distribution D, or even a particular training set? For instance, L(x) that is constructed from trained intermediate layer embeddings in a neural network -- or would L(x) that has knowledge of the distribution D potentially break FCC?

(For instance, this type of L(x) / y constructed from true labels / label noise on existing label structure, e.g. CIFAR-10, is also used in the non-interpolating setting in Section 5.2, which makes the reader wonder what is actually happening in the interpolating setting. More generally, I found Section 5.2 to be in tension with the main message prior to that section, and perhaps too preliminary to be presentable.)

--I think one other experiment that would significantly strengthen the paper is one that tests the implications mentioned for scaling limits in L107 (e.g. measure feature calibration as models are scaled from the underparametered scaling regime to overparameterized.) This would give some more diverse evidence of places where feature calibration breaks down.

Nit points:
--Typo L263: spare -> "sparse"
--Typo L265: Figure label should be "2A"
--L749 in appendix is cut off
limitations_and_societal_impact: The paper does not address potential negative societal impact, but I believe it is not necessary given the nature of the work.

The authors do provide adequate discussion of limitations and are clear about the conjectural portions of their work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors consider interpolating classifiers, i.e. classifiers that interpolate the training data by selecting the correct class for training samples, often performing poorly in terms of generalization error. The authors propose a new notion of generalization, i.e. the Distributional Generalization. Such a notion does not focus on the average error over the inputs, and subsumes both classical generalization and the conjecture that the outputs of classifiers match the statistics of their training distribution when conditioned on certain subgroups. The authors formally introduce and experimentally validate a conjecture to specify such subgroups. While the conjecture is proven for 1-nearest-neighbor classifiers, empirical evidence is provided for other classifiers; such as kernel machines and neural networks.
main_review: == Main comments ==

- The paper is overall well written and the topics are clearly exposed. Illustrative examples are effectively presented to further clarify the problem at hand.
- The presented work tackles a timely and relevant problem in machine learning, drawing ideas from many related areas of research, such as output distribution calibration, overparametrization, and benign overfitting. The presented results are worthy but not completely surprising. 
- The paper addresses a very much similar problem than : 
Vapnik, V. & Izmailov, R.. (2020). Complete statistical theory of learning: learning using statistical invariants. Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications, in PMLR 128:4-40
However, this problem is known to below to the class of  ill-posed problems. How does the current work related to the above mentioned reference? How does it overcome the ill-posed problem. 
- In eq. (1) the notation is a bit confusing. Are TrainSet and TestSet the distributions from which the samples of these sets are drawn (but then D_tr, D_te are used to mean the same), or rather the sets themselves (and then ~ should be replaced with ∈)?
- One of the two main contributions is thoroughly expressed in section 3.2. This is indeed a very interesting observation. However it looks closely related to the problem defined in section 2 of [26].
Could the authors further underline the value and originality of their contribution by discussing the connection between the two concepts?
- Although the feature calibration conjecture is fully proved to 1-nearest-neighbors classifiers, it is also true that it represents a very limited model. It seems that for more complex (and more commonly used) models, only empirical evidence can be provided so far, with no much theoretical formalization. Although this is not necessarily a negative aspect for works in progress and contributions which bring new ideas, the expectation set up by the writers in the introductory section are diminished by lack of formalization.
- The training procedure is sometimes indicated as Train_A, and sometimes as A. We suggest to choose one symbol and consistently use it throughout the whole paper.
- Have the authors thought of any potential issue related to identifying potentially sensitive subgroups L such as, ethnicity, high/low income, etc. instead of dogs, cats, etc. when using different
datasets?
- We would like to draw attention on the fact that, in line 101, the reference to the work in [7] does not seem to properly fit it. Indeed, in [7] the authors already explain that ‘benign overfitting’ is only characterized in specific cases and does not generally apply, making the claim in lines 103-104 appear a bit excessive. Reference [26] should be reported as the version officially published at ICML 2017.
limitations_and_societal_impact: The authors take into the scientific limitations of their work in section 3.4. Further improvements can be implemented by answering the questions and doubts raised in the Main Review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper empirically characterizes a fine-grained generalization property of interpolating learning algorithms, and give a conjecture that formalizes the observed phenomenon. Roughly, the paper observes that the generalization properties of an interpolating classifier can be quite distinct for different sample subpopulations with the same label, whenever the label noise imposed on these subpopulations during the training phase is distinct. Authors conjecture that the generalization properties may be uniform only for samples belonging to a smaller "distinguishable" clusters of the input data space.
main_review: Post-rebuttal: I thank authors for their detailed response. Most of the authors' response made a perfect sense. One thing that prevented me from raising the score further is that I am still not sure about is whether the conjecture itself is meaningful or useful. In fact, after reading the response to my first point (Converse...), I am slightly more pessimistic about the possibility that "distinguishability" and "feature calibration" are tightly connected concepts (say, in a causal sense). I am curious if there are alternate (and perhaps more useful) conjectures that can help explain the phenomenon. In other words, I think the paper should benefit from having an extensive discussion that justifies why the proposed conjecture based on distinguishability is nontrivial, useful, and better than other possible alternatives.


---

__What I like.__ The reported empirical observation is intriguing to some degree, and (in my opinion) is worthy of documenting and formalizing. Authors validate the observation under a variety of scenarios in Section 1 & 4 (and also appendices), which helped convincing me of the existence of such phenomenon. As the authors noted, establishing a theoretical framework that can explain the depicted phenomenon may be an interesting open problem (perhaps we can phrase problems in a minimax style with multiple tasks?). The clarity of the writing is well above average, while there are several points that can be clarified further. I also liked the theoretical contributions, which could help readers grasp the idea of how such conjectures can be proved.

__Checking/refining the conjecture.__ On the one hand, I find that the provided empirical observations support the conjecture well. On the other hand, I think that one can even further strengthen the argument by trying to provide an evidence supporting that the conditions described in the conjecture is indeed essential for the distributional similarity. I am actually very curious whether the "distinguishable features" are really essential. Is there a case where the distributional similarity does not hold for indistinguishable features, which is perhaps more informative than the perfectly random case? Although this is not really necessary if one is interested only in the validity of the conjecture, having such evidence will help us understand how non-vacuous/"tight" the conjecture is.

__Clarifying the terminology: Interpolating.__ I think the term "interpolating classifier" can be clarified further in the text. Although the terminology is now (sort of) popularly used in the literature, I think still they need to be properly defined at least once in the main text, as the modern use of this terminology are often wider than what is used to mean in the classic kernel-based literature.

__Clarifying the terminology: Distributional Closeness.__ I am curious in what sense the notion of "distributional closeness" introduced in Section 2 is different from the widely used notion of integral probability metrics (IPMs). If they are identical, sticking to the existing notation would help reduce the confusion.

__Practical implication.__ While I mostly liked the theoretical implications illustrated in Section 1.3, I wonder if authors could give an idea why capturing such fine-grained generalization properties may be important. For instance, could there be any implications to the fairness or shortcut learning?
limitations_and_societal_impact: The limitation is clearly described, in my opinion. This work mainly discusses what is implicitly taking place in the standard learning practices, instead of giving a new one. I do not think there is any "potential negative impact" that should be discussed.
review_title: null

Meta-review: This paper studies interpolating classifiers and introduces a conjecture about their distributional generalization. Reviewer EwQL is mainly positive about this work. However, reviewers fCRG and fE8g, while appreciating interesting observations in the paper, find it not ready for publication.Specifically, within an internal discussion among the reviewers, fCRG stated how the conjecture introduced in the paper is meaningful or useful is not clear, saying "after reading the authors' response to my own review, I am now slightly more pessimistic about the possibility that distinguishability and feature calibration are tightly connected concepts". This reviewer expects the conjecture to be very persuasive and impactful for the paper to be accepted. Reviewer fE8g has concerns about the conjecture relying on poorly defined statistical setting and also recommends a more thorough discussion on the relationship between this work and that of Vapnik & Izmailov's. Authors are encouraged to address these concerns and resubmit.


Decision: Reject