DISTRIBUTIONAL GENERALIZATION: STRUCTURE BEYOND TEST ERROR
Year: 2021

Abstract:
Classifiers in machine learning are often reduced to single dimensional quantities, such as test error or loss. Here, we initiate a much richer study of classifiers by considering the entire joint distribution of their inputs and outputs. We present both new empirical behaviors of standard classifiers, as well as quantitative conjectures which capture these behaviors. Informally, our conjecture states: the output distribution of an interpolating classifier matches the distribution of true labels, when conditioned on certain subgroups of the input space. For example, if we mislabel 30% of dogs as cats in the train set of CIFAR-10, then a ResNet trained to interpolation will in fact mislabel roughly 30% of dogs as cats on the test set as well, while leaving other classes unaffected. This conjecture has implications for the theory of overparameterization, scaling limits, implicit bias, and statistical consistency. Further, it can be seen as a new kind of generalization, which goes beyond measuring single-dimensional quantities to measuring entire distributions.

heading: 1 INTRODUCTION
text: In learning theory, when we study how well a classifier “generalizes”, we usually consider a single metric – its test error (Shalev-Shwartz & Ben-David, 2014). However, there could be many different classifiers with the same test error that differ substantially in, say, the subgroups of inputs on which they make errors. Reducing classifiers to a single number misses these rich aspects of their behavior. In this work, we propose formally studying the entire joint distribution of classifier inputs and outputs. That is, the distribution (x, f(x)) for samples from the distribution x ∼ D for a classifier f(x). This distribution reveals many structural properties of the classifier beyond test error (such as where the errors occur). In fact, we discover new behaviors of modern classifiers that can only be understood in this framework. As an example, consider the following experiment (Figure 1). Experiment 1. Consider a binary classification version of CIFAR-10, where CIFAR-10 images x have binary labels Animal/Object. Take 50K samples from this distribution as a train set, but apply the following label noise: flip the label of cats to Object with probability 30%. Now train a WideResNet f to 0 train error on this train set. How does the trained classifier behave on test samples? Options below:
(1) The test error is low across all classes, since there is only 3% overall label noise in the train set.
(2) Test error is “spread” across the animal class. After all, the classifier is not explicitly told what a cat or a dog is, just that they are all animals.
(3) The classifier misclassifies roughly 30% of test cats as “objects”, but all other animals are largely unaffected.
The reality is closest to option (3) as shown in Figure 1. The left panel shows the joint density of train inputs x with train labels Object/Animal. The right panel shows the classifier predictions f(x) on test inputs x.
There are several notable things about this experiment. First, the error is localized to cats in the test set as it was in the train set, even though no explicit cat labels were provided. The interpolating model is thus sensitive to subgroup-structures in the distribution. Second, the amount of error on the cat class is close to the noise applied on the train set. Thus, the behavior of the classifier on the train set generalizes to the test set in a stronger sense than just average error. Specifically, when
conditioned on a subgroup (cat), the distribution of the true labels is close to that of the classifier outputs. Third, this is not the behavior of the Bayes-optimal classifier, which would always output the maximum-likelihood label instead of reproducing the noise in the distribution. The network is thus behaving poorly from the perspective of Bayes-optimality, but behaving well in a certain distributional sense (which we will formalize soon).
Now, consider a seemingly unrelated experimental observation. Take an AlexNet trained on ImageNet, a 1000-way classification problem with 116 varieties of dogs. AlexNet only achieves 56.5% test accuracy on ImageNet. However, it at least classifies most dogs as some variety of dog (with 98.4% accuracy), though it may mistake the exact breed. In this work, we show that both of these experiments are examples of the same underlying phenomenon. We empirically show that for an interpolating classifier, its classification outputs are close in distribution to the true labels — even when conditioned on many subsets of the domain. For example, in Figure 1, the distribution of p(f(x)|x = cat) is close to the true label distribution of p(y|x = cat). We propose a formal conjecture (Feature Calibration), that predicts which subgroups of the domain can be conditioned on for the above distributional closeness to hold.
These experimental behaviors could not have been captured solely by looking at average test error, as is done in the classical theory of generalization. In fact, they are special cases of a new kind of generalization, which we call “Distributional Generalization”.

heading: 1.1 DISTRIBUTIONAL GENERALIZATION
text: Informally, Distributional Generalization states that the outputs of classifiers f on their train sets and test sets are close as distributions (as opposed to close in just error). That is, the following joint distributions1 are close:
(x, f(x))x∼TestSet ≈ (x, f(x))x∼TrainSet (1) The remainder of this paper is devoted to making the above statement precise, and empirically checking its validity on real-world tasks. Specifically, we want to formally define the notion of approximation (≈), and understand how it depends on the problem parameters (the type of classifier, number of train samples, etc). We focus primarily on interpolating methods, where we formalize Equation (1) through our Feature Calibration Conjecture.

heading: 1.2 OUR CONTRIBUTIONS AND ORGANIZATION
text: We discover new empirical behaviors of interpolating classifiers, and we propose quantitative conjectures to characterize these behaviors.
• In Section 3, we introduce a “Feature Calibration” conjecture, which unifies our experimental observations. Roughly, Feature Calibration says that the outputs of classifiers match the statistics of their training distribution when conditioned on certain subgroups.
• In Section 4, we experimentally stress test our Feature Calibration conjecture across various settings in machine learning, including neural networks, kernel machines, and decision trees. This highlights the universality of our results across machine learning.
1These distributions also include the randomness in sampling the train and test sets, and in training the classifier, as we define more precisely in Section 3.
• In Section 5, we relate our results to classical generalization, by defining a new notion of Distributional Generalization which extends and subsumes the classical notion.
• Finally, in Section 5.2 we informally discuss how Distributional Generalization can be applied even for non-interpolating methods.
Our results extend our scientific understanding of of interpolating methods, and introduce a new type of generalization exhibited across many methods in machine learning.

heading: 1.3 RELATED WORK AND SIGNIFICANCE
text: Our work has connections to, and implications for many existing research programs in deep learning.
Implicit Bias and Overparameterization. There has been a long line of recent work towards understanding overparameterized and interpolating methods, since these pose challenges for classical theories of generalization (e.g. Zhang et al. (2016); Belkin et al. (2018a;b; 2019); Liang & Rakhlin (2018); Nakkiran et al. (2020); Schapire et al. (1998); Breiman (1995); Soudry et al. (2018); Gunasekar et al. (2018)). The “implicit bias” program here aims to answer: Among all models with 0 train error, which model is actually produced by SGD? Most existing work seeks to characterize the exact implicit bias of models under certain (sometimes strong) assumptions on the model, training method or the data distribution. In contrast, our conjecture applies across many different interpolating models (from neural nets to decision trees) as they would be used in practice, and thus form a sort of “universal implicit bias” of these methods. Moreover, our results place constraints on potential future theories of implicit bias, and guide us towards theories that better capture practice.
Benign Overfitting. Most prior works on interpolating classifiers attempt to explain why training to interpolation “does not harm” the the model. This has been dubbed “benign overfitting” (Bartlett et al., 2020) and “harmless interpolation” (Muthukumar et al., 2020), reflecting the widely-held belief that interpolation does not harm the decision boundary of classifiers. In contrast, we find that interpolation actually does “harm” classifiers, in predictable ways: fitting the label noise on the train set causes similar noise to be reproduced at test time. Our results thus indicate that interpolation can significantly affect the decision boundary of classifiers, and should not be considered a purely “benign” effect.
Classical Generalization and Scaling Limits. Our framework of Distributional Generalization is insightful even to study classical generalization, since it reveals much more about models than just their test error. For example, statistical learning theory attempts to understand if and when models will asymptotically converge to Bayes optimal classifiers, in the limit of large data (“asymptotic consistency” Shalev-Shwartz & Ben-David (2014); Wasserman (2013)). In deep learning, there are at least two distinct ways to scale model and data to infinity together: the underparameterized scaling limit, where data-size model-size always, and the overparameterized scaling limit, where data-size model-size always. The underparameterized scaling limit is well-understood: when data is essentially infinite, neural networks will converge to the Bayes-optimal classifier (provided the model-size is large enough, and the optimization is run for long enough, with enough noise to escape local minima). On the other hand, our work suggests that in the overparameterized scaling limit, models will not converge to the Bayes-optimal classifier. Specifically, our Feature Calibration Conjecture implies that in the limit of large data, interpolating models will approach a sampler from the distribution. That is, the limiting model f will be such that the output f(x) is a sample from p(y|x), as opposed to the Bayes-optimal f∗(x) = argmaxy p(y|x). This claim— that overparameterized models do not converge to Bayes-optimal classifiers— is unique to our work as far as we know, and highlights the broad implications of our results.
Locality and Manifold Learning. Our intuition for the behaviors in this work is that they arise due to some form of “locality” of the trained classifiers, in an appropriate embedding space. For example, the behavior observed in Experiment 1 would be consistent with that of a 1-Nearest-Neighbor classifier in a embedding that separates the CIFAR-10 classes well. This intuition that classifiers learn good embeddings is present in various forms in the literature, for example: the so-called called “manifold hypothesis,” that natural data lie on a low-dimensional manifold (Narayanan & Mitter, 2010; Sharma & Kaplan, 2020), as well as works on local stiffness of the loss landscape (Fort et al., 2019), and works showing that overparameterized neural networks can learn hidden low-dimensional structure
in high-dimensional settings (Gerace et al., 2020; Bach, 2017; Chizat & Bach, 2020). It is open to more formally understand connections between our work and the above.
Uncertainty Estimation. Since the appearance of the current work on arXiv, it has been directly built on by other authors. The work of Jiang et al. (2021) investigates our conjectures further, and extends them to develop a method for out-of-distribution uncertainty estimation. This highlights the fundamental nature and importance of our results, since they have already been used in a practical application. A full discussion of related works is in Appendix A.

heading: 2 PRELIMINARIES
text: Notation. We consider joint distributions D on x ∈ X and discrete y ∈ Y = [k]. Let S = {(xi, yi)}ni=1 ∼ Dn denote a train set of n iid samples from D. Let A denote the training procedure (including architecture and training algorithm for neural networks), and let f ← TrainA(S) denote training a classifier f on train-set S using procedure A. We consider classifiers which output hard decisions f : X → Y . Let NNS(x) = xi denote the nearest-neighbor to x in train-set S, with respect to a distance metric d. Our theorems will apply to any distance metric, and so we leave this unspecified. Let NN(y)S (x) denote the nearest-neighbor estimator itself, that is, NN (y) S (x) := yi where xi = NNS(x).
Experimental Setup. Briefly, we train all classifiers to interpolation (to 0 train error). Neural networks (MLPs and ResNets (He et al., 2016)) are trained with SGD. Interpolating decision trees are trained using the growth rule from Random Forests (Breiman, 2001). For kernel classification, we consider kernel regression on one-hot labels and kernel SVM, with small or 0 of regularization (which is often optimal (Shankar et al., 2020)). Full experimental details are provided in Appendix B.
Distributional Closeness. We formalize distributional closeness using the notion of Integral Probability Metrics (Müller, 1997), which we review here. For two distributions P,Q over X × Y , let a “test” (or “distinguisher”) be a function T : X × Y → [0, 1] which accepts a sample from either distribution, and is intended to classify the sample as either from distribution P or Q. For any set C ⊆ {T : X × Y → [0, 1]} of tests, we say distributions P and Q are “ε-indistinguishable up to C-tests” if they are close with respect to all tests in class C. That is,
P ≈Cε Q ⇐⇒ sup T∈C ∣∣∣∣ E (x,y)∼P [T (x, y)]− E (x,y)∼Q [T (x, y)] ∣∣∣∣ ≤ ε (2) Total-Variation distance is equivalent to closeness in all tests, i.e. C = {T : X × Y → [0, 1]}, but we consider closeness for restricted families of tests C. P ≈ε Q denotes ε-closeness in TV-distance.

heading: 3 FEATURE CALIBRATION CONJECTURE

heading: 3.1 DISTRIBUTIONS OF INTEREST
text: We first define three key distributions that we will use in stating our formal conjecture. For a given data distribution D over X × Y and training procedure TrainA, we consider the following three distributions over X × Y:
1. Source D: (x, y) where x, y ∼ D. 2. Train Dtr: (xtr, f(xtr)) where S ∼ Dn, f ← TrainA(S), (xtr, ytr) ∼ S 3. Test Dte: (x, f(x)) where S ∼ Dn, f ← TrainA(S), x, y ∼ D
The source distribution D is simply the original distribution. To sample once from the Train Distribution Dtr, we first sample a train set S ∼ Dn, train a classifier f on it, then output (xtr, f(xtr)) for a random train point xtr ∈ S. That is, Dtr is the distribution of input and outputs of a trained classifier f on its train set. To sample once from the Test Distribution Dte, we do this same procedure, but output (x, f(x)) for a random test point x. That is, the Dte is the distribution of input and outputs of a trained classifier f at test time. The only difference between the Train Distribution and
Test Distribution is that the point x is sampled from the train set or the test set, respectively.2 For interpolating classifiers, f(xtr) = ytr on the train set, and so the Source and Train distributions are equivalent: D ≡ Dtr. (Note that these definitions, crucially, involve randomness from sampling the train set, training the classifier, and sampling a test point).

heading: 3.2 FEATURE CALIBRATION
text: We now formally describe the Feature Calibration Conjecture. At a high level, we argue that the distributions Dte and D are statistically close for interpolating classifiers if we first “coarsen” the domain of x by some partition L : X → [M ] in to M parts. That is, for certain partitions L, the following distributions are statistically close:
(L(x), f(x))x∼D ≈ε (L(x), y)x∼D
We think of L as defining subgroups over the domain— for example, L(x) ∈ {dog, cat, horse. . .}. Then, the above statistical closeness is essentially equivalent to requiring that for all subgroups ` ∈ [M ], the conditional distribution of classifier output on the subgroup—p(f(x)|L(x) = `) — is close to the true conditional distribution: p(y|L(x) = `). The crux of our conjecture lies in defining exactly which subgroups L satisfy this distributional closeness, and quantifying the ε approximation. This is subtle, since it must depend on almost all parameters of the problem. For example, consider a modification to Experiment 1, where we use a fully-connected network (MLP) instead of a ResNet. An MLP cannot properly distinguish cats even when it is actually provided the real CIFAR-10 labels, and so (informally) it has no hope of behaving differently on cats in the setting of Experiment 1, where the cats are not labeled explicitly (See Figure C.2 for results with MLPs). Similarly, if we train the ResNet with very few samples from the distribution, the network will be unable to recognize cats. Thus, the allowable partitions must depend on the classifier family and the training method, including the number of samples.
We conjecture that allowable partitions are those which can themselves be learnt to good test performance with an identical training procedure, but trained with the labels of the partition L instead of y. To formalize this, we define a distinguishable feature: a partition of the domain X that is learnable for a given training procedure. Thus, in Experiment 1, the partition into CIFAR-10 classes would be a distinguishable feature for ResNets (trained with SGD with 50K or more samples), but not for MLPs. The definition below depends on the training procedure A, the data distribution D, number of train samples n, and an approximation parameter ε (which we think of as ε ≈ 0). Definition 1 ((ε,A,D, n)-Distinguishable Feature). For a distribution D over X × Y , number of samples n, training procedure A, and small ε ≥ 0, an (ε,A,D, n)-distinguishable feature is a partition L : X → [M ] of the domain X into M parts, such that training a model using A on n samples labeled by L works to classify L with high test accuracy. Precisely, L is a (ε,A,D, n)distinguishable feature if:
Pr S={(xi,L(xi)}x1,...,xn∼D f←TrainA(S); x∼D
[f(x) = L(x)] ≥ 1− ε
This definition depends only on the marginal distribution of D on x, and not on the label distribution pD(y|x). To recap, this definition is meant to capture a labeling of the domain X that is learnable for a given training procedure A. It must depend on the architecture used by A and number of samples n, since more powerful classifiers can distinguish more features. Note that there could be many distinguishable features for a given setting (ε,A,D, n) — including features not implied by the class label such as the presence of grass in a CIFAR-10 image. Our main conjecture follows.
Conjecture 1 (Feature Calibration). For all natural distributions D, number of samples n, interpolating training procedures A, and ε ≥ 0, the following distributions are statistically close for all (ε,A,D, n)-distinguishable features L:
(L(x), f(x)) f←TrainA(Dn); x,y∼D ≈ε (L(x), y) x,y∼D
(3)
2Technically, these definitions require training a fresh classifier for each sample, using independent train sets. For practical reasons most of our experiments train a single classifier f and evaluate it on the entire train/test set.
or equivalently:
(L(x), ŷ) x,ŷ∼Dte ≈ε (L(x), y) x,y∼D
(4)
This claims that the TV distance between the LHS and RHS of Equation (4) is at most ε, where ε is the error of the distinguishable feature (in Definition 1). We claim that this holds for all distinguishable features L “automatically” – we simply train a classifier, without specifying any particular partition. The formal statements of Definition 1 and Conjecture 1 may seem somewhat arbitrary, involving many quantifiers over (ε,A,D, n). However, we believe these statements are natural: In addition to extensive experimental evidence in Section 4, we also prove that Conjecture 1 is formally true as stated for 1-Nearest-Neighbor classifiers in Theorem 1.

heading: 3.3 FEATURE CALIBRATION FOR 1-NEAREST-NEIGHBORS
text: Here we prove that the 1-Nearest-Neighbor classifier formally satisfies Conjecture 1, under mild assumptions. We view this theorem as support for our (somewhat involved) formalism of Conjecture 1. Indeed, without Theorem 1 below, it is unclear if our statement of Conjecture 1 can ever be satisfied by any classifier, or if it is simply too strong to be true. This theorem applies generically to a wide class of distributions; the only assumption is a weak regularity condition. The proof of Theorem 1 is straightforward, and provided in Appendix D – but this strong property of nearest-neighbors was not know before, to our knowledge. Theorem 1. Let D be a distribution over X × Y , and let n ∈ N be the number of train samples. Assume the following regularity condition holds: Sampling the nearest-neighbor train point to a random test point yields (close to) a uniformly random test point. That is, suppose that for some small δ ≥ 0, the distributions: {NNS(x)}S∼Dn
x∼D ≈δ {x}x∼D. Then, Conjecture 1 holds. That is,
for all (ε,NN,D, n)-distinguishable partitions L, the following distributions are statistically close:
{(y, L(x))}x,y∼D ≈ε+δ {(NN(y)S (x), L(x)}S∼Dn x,y∼D
(5)

heading: 3.4 LIMITATIONS: NATURAL DISTRIBUTIONS
text: Technically, Conjecture 1 is not fully specified, since it does not specify exactly which classifiers or distributions obey the conjecture. We do not claim that all classifiers and distributions satisfy our conjectures. Nevertheless, we claim our conjectures hold in all “natural” settings, which informally means settings with real data and classifiers that are actually used in practice. The problem of understanding what separates “natural distributions” from artificial ones is not unique to our work, and lies at the heart of deep learning theory. Many theoretical works handle this by considering simplified distributional assumptions (e.g. smoothness, well-separatedness, gaussianity), which are mathematically tractable, but unrealistic in practice (Arora et al., 2019; Li et al., 2019; Allen-Zhu et al., 2018). In contrast, we do not make unrealistic mathematical assumptions. This benefit of realism comes at the cost of mathematical formalism. We hope that as the theory of deep learning evolves, we will better understand how to formalize the notion of “natural” in our conjectures.

heading: 4 EXPERIMENTS: FEATURE CALIBRATION
text: We now give empirical evidence for our conjecture in a variety of settings in machine learning. In each experiment, we consider a feature that is (verifiably) distinguishable, and then test our Feature Calibration conjecture for this feature. Each of the experimental settings below highlights a different aspect of interpolating classifiers, which may be of independent interest. Selected experiments are summarized here, with full details and further experiments in Appendix C.
Constant Partition: Consider the trivially-distinguishable constant feature: L(x) = 0 everywhere. For this feature, Conjecture 1 reduces to the statement that the marginal distribution of class labels for any interpolating classifier is close to the true marginals p(y). To test this, we construct a variant of CIFAR-10 with class-imbalance and train classifiers with varying levels of test errors to interpolation on it. As shown in Figure 2B, the marginals of the classifier outputs are close to the true marginals, even for a classifier that only achieves 37% test error.
Coarse Partition: Consider AlexNet trained on ILSVRC-2012 ImageNet (Russakovsky et al., 2015), a 1000-class image classification problem with 116 varieties of dogs. The network achieves only 56.5% accuracy on the test set. But it will at least classify most dogs as dogs (with 98.4% accuracy), making L(x) ∈ {dog, not-dog} a distinguishable feature. Moreover, as predicted by Conjecture 1, the network is calibrated with respect to dogs: 22.4% of all dogs in ImageNet are Terriers, and indeed the network classifies 20.9% of all dogs as Terriers (though it has 9% error on which specific dogs it classifies as Terriers). See Appendix Table 2 for details, and related experiments on ResNets and kernels in Appendix C.
Class Partition: We now consider settings where the class labels are themselves distinguishable features (eg: CIFAR-10 classes are distinguishable by ResNets). Here our conjecture predicts the behavior of interpolating classifiers under structured label noise. As an example, we generate a random spare confusion matrix and apply this to the labels of CIFAR-10 as shown in Figure 2A. We find that a WideResNet trained to interpolation outputs the same confusion matrix on the test set as well (Figure 2B). Now, to test that this phenomenon is indeed robust to the level of noise, we mislabel class 0→ 1 with probability p in the CIFAR-10 train set for varying levels of p. We then observe p̂, the fraction of samples mislabeled by this network from 0→ 1 in the test set (Figure 3A shows p versus p̂). The Bayes optimal classifier for this distribution behaves as a step function (in red), and a classifier that obeys Conjecture 1 exactly would follow the diagonal (in green). The actual experiment (in blue) is close to the behavior predicted by Conjecture 1. This experiment shows a contrast with classical learning theory. While most existing theory focuses on whether classifiers converge to the Bayes optimal solution, we show that interpolating classifiers behave “optimally” in a different sense: they match the distribution of their train set. We discuss this further in Section 5. See Appendix C.4 for more experiments, including other classifiers such as Decisions Trees.
Multiple features: Conjecture 1 states that the network should be automatically calibrated for all distinguishable features, without any explicit labels for them. To do this, we use the CelebA dataset (Liu et al., 2015), containing images with many binary attributes per image. (“male”, “blond hair”, etc). We train a ResNet-50 to classify one of the hard attributes (accuracy 80%) and confirm that the Feature Calibration holds for all the other attributes (Figure 3) that are themselves distinguishable.
Quantitative predictions: We now test the quantitative predictions made by Conjecture 1. This conjecture states that the TV-distance between the joint distributions (L(x), f(x)) and (L(x), y) is at most ε, where ε is the error of the training procedure in learning L (see Definition 1). To test this, we consider binary task similar to Experiment 1 where (Ship, Plane) are labeled as class 0 and (Cat, Dog) are labeled as class 1, with p = 0.3 fraction of cats mislabeled to class 0. Then, we train a network to interpolation on this task. To vary the error ε systematically, we train networks with varying number of train samples. Networks with fewer samples have larger ε since they are worse at classifying the distinguishable features of (Ship,Plane,Cat,Dog). Then, we use the same setup to train networks on the binary task and measure the TV-distance between (L(x), f(x)) and (L(x), y) in this task. The results are shown in Figure 3C. As predicted, the TV distance on the binary task is upper bounded by ε error on the 4-way classification task.

heading: 5 DISTRIBUTIONAL GENERALIZATION
text: In order to relate our results to the classical theory of generalization, we now propose a formal definition of “Distributional Generalization”, which subsumes both Feature Calibration and classical generalization. A trained model f obeys classical generalization (with respect to test error) if its error on the train set is close to its error on the test distribution. We first rewrite this using our definitions below.
Classical Generalization (informal): Let f be a trained classifier. Then f generalizes if:
E x∼TrainSet ŷ←f(x) [1{ŷ 6= y(x)}] ≈ E x∼TestSet ŷ←f(x) [1{ŷ 6= y(x)}] (6)
Above, y(x) is the true class of x and ŷ is the predicted class. The LHS of Equation 6 is the train error of f , and the RHS is the test error. Using our definitions of Dtr,Dte from Section 3.1, and defining Terr(x, ŷ) := 1{ŷ 6= y(x)}, we can write Equation 6 equivalently:
E x,ŷ∼Dtr [Terr(x, ŷ)] ≈ E x,ŷ∼Dte [Terr(x, ŷ)] (7)
That is, classical generalization states that a certain function (Terr) has similar expectations on both the Train DistributionDtr and Test DistributionDte. We can now introduce Distributional Generalization, which is a property of trained classifiers. It is parameterized by a set of bounded functions (“tests”): T ⊆ {T : X × Y → [0, 1]}. Distributional Generalization: Let f be a trained classifier. Then f satisfies Distributional Generalization with respect to tests T if:
∀T ∈ T : E x,ŷ∼Dtr [T (x, ŷ)] ≈ E x,ŷ∼Dte [T (x, ŷ)] (8)
This states that the train and test distribution have similar expectations for all functions in the family T , which we can write as: Dtr ≈T Dte. For the singleton set T = {Terr}, this is equivalent to classical generalization, but it may hold for much larger sets T . This definition of Distributional Generalization, like the definition of classical generalization, is just defining an object— not stating when or how it is satisfied. Feature Calibration turns this into a concrete conjecture.

heading: 5.1 FEATURE CALIBRATION AS DISTRIBUTIONAL GENERALIZATION
text: We can write our Feature Calibration Conjecture as a special case of Distributional Generalization, for a certain family of tests T . Informally, for a given setting, the family T is all tests which take input (x, y), but only depend on x via a distinguishable feature (Definition 1). For example, a test of the form T (x, y) = g(L(x), y) where L is a distinguishable feature, and g is arbitrary. Formally,
for a given problem setting, suppose L is the set of (ε,A,D, n)-distinguishable features. Then Conjecture 1 states that ∀L ∈ L : (L(x), f(x)) ≈ε (L(x), y). This is equivalent to the statement
Dte ≈Tε D (9) where T is the set of functions T := {T : T (x, y) = g(L(x), y), L ∈ L, g : X × Y → [0, 1]}. For interpolating classifiers, we have D ≡ Dtr, and so Equation (9) is equivalent to Dte ≈Tε Dtr, which is a statement of Distributional Generalization. Since any classifier family will contain a large number of distinguishable features, the set L may be very large. Hence, the distributions Dtr and Dte can be thought of as being close as distributions.

heading: 5.2 BEYOND INTERPOLATING METHODS
text: The previous sections focused on interpolating classifiers, which fit their train sets exactly. Here we informally discuss how to extend our results beyond interpolating methods. The discussion in this section is not as precise as in previous sections, and is only meant to suggest that our abstraction of Distributional Generalization can be useful in other settings. For non-interpolating classifiers, we may still expect that they behave similarly on their test and train sets – that is, Dte ≈T Dtr for some family of tests T . For example, the following is a possible generalization of Feature Calibration. Conjecture 2 (Generalized Feature Calibration, informal). For trained classifiers f , the following distributions are statistically close for many partitions L of the domain:
(L(x), ŷ) x,ŷ∼Dte ≈ (L(x), ŷ) x,ŷ∼Dtr
(10)
We do not yet understand how to state this conjecture formally, but we give experimental evidence in its support. In Figure 4, we apply label noise from a random sparse confusion to the CIFAR-10 train set. We then train a single WideResNet28-10, and measure its predictions on the train and test over increasing SGD steps. The top row shows the confusion matrix of predictions f(x) vs true labels L(x) on the train set, and the bottom row shows the corresponding confusion matrix on the test set. As the network is trained for longer, it fits more of the noise on the train set, and this noise is mirrored almost identically on the test set. Full experimental details in Appendix B.

heading: 6 CONCLUSION
text: This work initiates the study of a new kind of generalization— Distributional Generalization— which considers the entire input-output behavior of classifiers, instead of just their test error. We presented both new empirical behaviors, and new formal conjectures which characterize these behaviors. Roughly, our conjecture states that the outputs of classifiers on the test set are “close in distribution” to their outputs on the train set. These results build a deeper understanding of models used in practice, and we hope our results inspire further work on distributional generalization in machine learning.

heading: A FULL RELATED WORK
text: Our work is inspired by the broader study of interpolating and overparameterized methods in machine learning; a partial list of works in this theme includes Zhang et al. (2016); Belkin et al. (2018a;b; 2019); Liang & Rakhlin (2018); Nakkiran et al. (2020); Mei & Montanari (2019); Schapire et al. (1998); Breiman (1995); Ghorbani et al. (2019); Hastie et al. (2019); Bartlett et al. (2020); Advani & Saxe (2017); Geiger et al. (2019); Gerace et al. (2020); Chizat & Bach (2020); Goldt et al. (2019); Arora et al. (2019); Allen-Zhu et al. (2019); Neyshabur et al. (2018); Dziugaite & Roy (2017); Muthukumar et al. (2020); Neal et al. (2018).
Interpolating Methods. Many of the best-performing techniques on high-dimensional tasks are interpolating methods, which fit their train samples to 0 train error. This includes neural-networks and kernels on images (He et al., 2016; Shankar et al., 2020), and random forests on tabular data (Fernández-Delgado et al., 2014). Interpolating methods have been extensively studied both recently and in the past, since we do not theoretically understand their practical success (Schapire et al., 1998; Schapire, 1999; Breiman, 1995; Zhang et al., 2016; Belkin et al., 2018a;b; 2019; Liang & Rakhlin, 2018; Mei & Montanari, 2019; Hastie et al., 2019; Nakkiran et al., 2020). In particular, much of the classical work in statistical learning theory (uniform convergence, VC-dimension, Rademacher complexity, regularization, stability) fails to explain the success of interpolating methods (Zhang et al., 2016; Belkin et al., 2018a;b; Nagarajan & Kolter, 2019). The few techniques which do apply to interpolating methods (e.g. margin theory (Schapire et al., 1998)) remain vacuous on modern neural-networks and kernels.
Decision Trees. In a similar vein to our work, Wyner et al. (2017); Olson & Wyner (2018) investigate decision trees, and show that random forests are equivalent to a Nadaraya–Watson smoother Nadaraya (1964); Watson (1964) with a certain smoothing kernel. Decision trees (Breiman et al., 1984) are often intuitively thought of as “adaptive nearest-neighbors,” since they are explicitly a spatial-partitioning method (Hastie et al., 2009). Thus, it may not be surprising that decision trees behave similarly to 1- Nearest-Neighbors. Wyner et al. (2017); Olson & Wyner (2018) took steps towards characterizing and understanding this behavior – in particular, Olson & Wyner (2018) defines an equivalent smoothing kernel corresponding to a random forest, and empirically investigates the quality of the conditional density estimate. Our work presents a formal characterization of the quality of this conditional density estimate (Conjecture 1), which is a novel characterization even for decision trees, as far as we know.
Kernel Smoothing. The term kernel regression is sometimes used in the literature to refer to kernel smoothers, such as the Nadaraya–Watson kernel smoother (Nadaraya, 1964; Watson, 1964). But in this work we use the term “kernel regression” to refer only to regression in a Reproducing Kernel Hilbert Space, as described in the experimental details.
Label Noise. Our conjectures also describe the behavior of neural networks under label noise, which has been empirically and theoretically studied in the past, though not formally characterized before (Zhang et al., 2016; Belkin et al., 2018b; Rolnick et al., 2017; Natarajan et al., 2013; Thulasidasan et al., 2019; Ziyin et al., 2020; Chatterji & Long, 2020). Prior works have noticed that vanilla interpolating networks are sensitive to label noise (e.g. Figure 1 in Zhang et al. (2016), and Belkin et al. (2018b)), and there are many works on making networks more robust to label noise via modifications to the training procedure or objective (Rolnick et al., 2017; Natarajan et al., 2013; Thulasidasan et al., 2019; Ziyin et al., 2020). In contrast, we claim this sensitivity to label noise is not necessarily a problem to be fixed, but rather a consequence of a stronger property: distributional generalization.
Conditional Density Estimation. Our density calibration property is similar to the guarantees of a conditional density estimator. More specifically, Conjecture 1 states that an interpolating classifier samples from a distribution approximating the conditional density of p(y|x) in a certain sense. Conditional density estimation has been well-studied in classical nonparametric statistics (e.g. the Nadaraya–Watson kernel smoother (Nadaraya, 1964; Watson, 1964)). However, these classical methods behave poorly in high-dimensions, both in theory and in practice. There are some attempts to extend these classical methods to modern high-dimentional problems via augmenting estimators with neural networks (e.g. Rothfuss et al. (2019)). Random forests have also been known to exhibit properties similar to conditional density estimators. This has been formalized in various ways, often only with asymptotic guarantees (Meinshausen, 2006; Pospisil & Lee, 2018; Athey et al., 2019).
No prior work that we are aware of attempts to characterize the quality of the resulting density estimate via testable assumptions, as we do with our formulation of Conjecture 1. Finally, our motivation is not to design good conditional density estimators, but rather to study properties of interpolating classifiers — which we find happen to share properties of density estimators.
Feature Calibration (Conjecture 1) is also related to the concepts of calibration and multicalibration (Guo et al., 2017; Niculescu-Mizil & Caruana, 2005; Hébert-Johnson et al., 2018). In our framework, calibration is implied by Feature Calibration for a specific set of partitions L (determined by level sets of the classifier’s confidence). However, we are not concerned with a specific set of partitions (or “subgroups” in the algorithmic fairness literature) but we generally aim to characterize for which partitions Feature Calibration holds. Moreover, we consider only hard-classification decisions and not confidences, and we study only standard learning algorithms which are not given any distinguished set of subgroups/partitions in advance. Our notion of distributional generalization is also related to the notion of “distributional subgroup overfitting” introduced recently by Yaghini et al. (2019) to study algorithmic fairness. This can be seen as studying distributional generalization for a specific family of tests (determined by distinguished subgroups in the population).
Locality and Manifold Learning. Our intuition for the behaviors in this work is that they arise due to some form of “locality” of the trained classifiers, in an appropriate space. This intuition is present in various forms in the literature, for example: the so-called called “manifold hypothesis,” that natural data lie on a low-dimensional manifold (e.g. Narayanan & Mitter (2010); Sharma & Kaplan (2020)), as well as works on local stiffness of the loss landscape (Fort et al., 2019), and works showing that overparameterized neural networks can learn hidden low-dimensional structure in high-dimensional settings (Gerace et al., 2020; Bach, 2017; Chizat & Bach, 2020). It is open to more formally understand connections between our work and the above.
Note about Proper Scoring Rules: If the loss function used in training is a strictly-proper scoring rule such as cross-entropy, then we may expect that in the limit of a large-capacity network and infinite data, training on samples {(xi, yi)} will yield a good density estimate of p(y|x) at the softmax layer. However, this is not what is happening in our experiments: First, our experiments consider the hard-decisions, not the softmax outputs. Second, we observe Conjecture 1 even in settings without proper scoring rules (kernel SVM and decision trees).

heading: B EXPERIMENTAL DETAILS
text: Here we describe general background, and experimental details common to all sections. Then we provide section-specific details below.

heading: B.1 DATASETS
text: We consider the image datasets CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2009), MNIST (LeCun et al., 1998), Fashion-MNIST (Xiao et al., 2017), CelebA (Liu et al., 2015), and ImageNet (Russakovsky et al., 2015). We normalize images to x ∈ [0, 1]C×W×H . We also consider tabular datasets from the UCI repository Dua & Graff (2017). For UCI data, we consider the 121 classification tasks as standardized in Fernández-Delgado et al. (2014). Some of these tasks have very few examples, so we restrict to the 92 classification tasks from Fernández-Delgado et al. (2014) which have at least 200 total examples.

heading: B.2 MODELS
text: We consider neural-networks, kernel methods, and decision trees.

heading: B.2.1 DECISION TREES
text: We train interpolating decision trees using a growth rule from Random Forests (Breiman, 2001; Ho, 1995): selecting a split based on a random √ d subset of d features, splitting based on Gini impurity, and growing trees until all leafs have a single sample. This is as implemented by Scikit-learn Pedregosa et al. (2011) defaults with RandomForestClassifier (n_estimators=1, bootstrap=False).

heading: B.2.2 KERNELS
text: Throughout this work we consider classification via kernel regression and kernel SVM. For M -class classification via kernel regression, we follow the methodology in e.g. Rahimi & Recht (2008); Belkin et al. (2018b); Shankar et al. (2020). We solve the following convex problem for training:
α∗ := argmin α∈RN×M ||Kα− y||22 + λαTKα
where Kij = k(xi, xj) is the kernel matrix of the training points for a kernel function k, y ∈ RN×M is the one-hot encoding of the train labels, and λ ≥ 0 is the regularization parameter. The solution can be written
α∗ = (K + λI)−1y
which we solve numerically using SciPy linalg.solve (Virtanen et al., 2020). We use the explicit form of all kernels involved. That is, we do not use random-feature approximations (Rahimi & Recht, 2008), though we expect they would behave similarly.
The kernel predictions on test points are then given by gα(x) := ∑ i∈[N ] αik(xi, x) (11)
fα(x) := argmax j∈[M ] gα(x)j (12)
where g(x) ∈ RM are the kernel regressor outputs, and g(x) ∈ [M ] is the thresholded classification decision. This is equivalent to training M separate binary regressors (one for each label), and taking the argmax for classification. We usually consider unregularized regression (λ = 0), except in Section 5.2.
For kernel SVM, we use the implementation provided by Scikit-learn (Pedregosa et al., 2011) sklearn.svm.SVC with a precomputed kernel, for inverse-regularization parameter C ≥ 0 (larger C corresponds to smaller regularization).
Types of Kernels. We use the following kernel functions k : Rd × Rd → R≥0.
• Gaussian Kernel (RBF): k(xi, xj) = exp(− ||xi−xj || 2 2
2σ̃2 ).
• Laplace Kernel: k(xi, xj) = exp(− ||xi−xj ||2σ̃ ). • Myrtle10 Kernel: This is the compositional kernel introduced by Shankar et al. (2020). We
use their exact kernel for CIFAR-10.
For the Gaussian and Laplace kernels, we parameterize bandwidth by σ := σ̃/ √ d. We use the following bandwidths, found by cross-validation to maximize the unregularized test accuracy:
• MNIST: σ = 0.15 for RBF kernel.
• Fashion-MNIST: σ = 0.1 for RBF kernel. σ = 1.0 for Laplace kernel.
• CIFAR-10: Myrtle10 Kernel from Shankar et al. (2020), and σ = 0.1 for RBF kernel.

heading: B.2.3 NEURAL NETWORKS
text: We use 4 different neural networks in our experiments. We use a multi-layer perceptron, and three different Residual networks.
MLP: We use a Multi-layer perceptron or a fully connected network with 3 hidden layers with 512 neurons in each layer. A hidden layer is followed by a BatchNormalization layer and ReLU activation function.
WideResNet: We use the standard WideResNet-28-10 described in Zagoruyko & Komodakis (2016). Our code is based on this repository.
ResNet50: We use a standard ResNet-50 from the PyTorch library (Paszke et al., 2017).
ResNet18: We use a modification of ResNet18 He et al. (2016) adapted to CIFAR-10 image sizes. Our code is based on this repository.
For Experiment 1 and Section 4, the hyperparameters used to train the above networks are given in Table 1.

heading: C FEATURE CALIBRATION: APPENDIX

heading: C.1 A GUIDE TO READING THE PLOTS
text: All the experiments in support of Conjecture 1 involve various quantities which we enumaerate here
1. Inputs x: Each experiment involves inputs from a standard dataset like CIFAR-10 or MNIST. We use the standard train/test splits for every dataset.
2. Distinguishable feature L(x): This feature depends only on input x. We consider various features like the original classes itself, a superset of classes (as in coarse partition) or some secondary attributes (like the binary attributes provided with CelebA)
3. Output labels y: The output label may be some modification of the original labels. For instance, by adding some type of label noise, or a constructed binary task as in Experiment 1
4. Classifier family F : We consider various types of classifiers like neural networks trained with gradient based methods, kernel and decision trees.
In each experiment, we are interested in two joint densities (y, L(x)), which depends on our dataset and task and is common across train and test, and (f(x), L(x)) which depends on the interpolating classifiers outputs on the test set. Since y, L(x) and f(x) are discrete, we will look at their discrete joint distributions. We sometimes refer to (y, L(x)) as the train joint density, as at interpolation (y, L(x)) = (f(x), L(x)) for all training inputs x. We also refer to (f(x), L(x)) as the test density, as we measure this only on the test set.

heading: C.2 EXPERIMENT 1
text: Experimental details: We now provide further details for Experiment 1. We first construct a dataset from CIFAR-10 that obeys the joint density (y, L(x)) shown in Figure 1 left panel. We then train a WideResNet-28-10 (WRN-28-10) on this modified dataset to zero training error. The network is trained with the hyperparameters described in Table 1. We then observe the joint density (f(x), L(x)) on the test images and find that the two joint densities are close as shown in Figure 5.
We now consider a modification of this experiment as follows:
Experiment 2. Consider the following distribution over images x and binary labels y. Sample x as a uniformly random CIFAR-10 image, and sample the label as p(y|x) = Bernoulli(CIFAR Class(x)/10). That is, if the CIFAR-10 class of x is k ∈ {0, 1, . . . 9}, then the label is 1 with probability (k/10) and 0 otherwise. Figure 5 shows this joint distribution of (x, y). As before, train a WideResNet to 0 training error on this distribution.
In this experiment too, we observe that the train and test joint densities are close as shown in Figure 5.
Now, we repeat the same experiment, but with an MLP instead of WRN-28-10. The training procedure is described in Table 1. This MLP has an error on 37% on the original CIFAR-10 dataset.
Since this MLP has poor accuracy on the original CIFAR-10 classification task, it does not form a distinguishable partition for it. As a result, the train and test joint densities (Figure 6) do not match as well as they did for WRN-28-10.

heading: C.3 CONSTANT PARTITION
text: Conjecture 1 states that the marginal distribution of class labels for any interpolating classifier f(x) is close to the true marginals p(y). To show this, we construct a dataset based on CIFAR-10 that has class-imbalance. For class k ∈ {0...9}, sample (k + 1)× 500 images from that class. This will give us a dataset where classes will have marginal distribution p(y = `) ∝ `+ 1 for classes ` ∈ [10], as shown in Figure 2. We do this both for the training set and the test set, to keep the distribution D fixed.
We then train a variety of classifiers (MLPs, RBF Kernel, ResNets) to interpolation on this dataset, which have varying levels of test errors (9-41%). The class balance of classifier outputs on the (rebalanced) test set

heading: C.4 CLASS PARTITION

heading: C.4.1 NEURAL NETWORKS AND CIFAR-10
text: We now describe details for the experiments in Figures 2A and 3A. A WRN-28-10 achieves an error of 4% on CIFAR-10. Hence, the original labels in CIFAR-10 form a distinguishable partition for this dataset. To demonstrate that Conjecture 1 holds, we consider different structured label noise on the CIFAR-10 dataset. To do so, we apply a variety of confusion matrices to the data. That is, for a confusion matrix C : 10× 10 matrix, the element cij gives the joint density that a randomly sampled image had original label j, but is flipped to class i. For no noise, this would be an identity matrix.
We begin by a simple confusion matrix where we flip only one class 0→ 1 with varying probability p. Figure 7A shows one such confusion matrix for p = 0.4. We then train a WideResNet-28-10 to zero train error on this dataset. We use the hyperparameters described in B.2 We find that the
classifier outputs on the test set closely track the confusion matrix that was applied to the distribution. Figure 7C shows that this is independent of the value of p and continues to hold for p = [0, 1].
To show that this is not dependent on the particular class used, we also show that the same holds for a random confusion matrix. We generate a sparse confusion matrix as follows. We set the diagonal to 0.5. Then, for every class j, we pick any two random classes for and set them to 0.2 and 0.3. We train a WRN-28-10 on it and report the test confusion matrix. The resulting train and test densities are shown in Figure 2A. As expected, the train and test confusion matrices are close, and share the same sparsity pattern.

heading: C.4.2 DECISION TREES
text: Figure 8 shows a version of this experiment for decision trees on the molecular biology UCI task. The molecular biology task is a 3-way classification problem: to classify the type of a DNA splice junction (donor, acceptor, or neither), given the sequence of DNA (60 bases) surrounding the junction. We add varying amounts of label noise that flips class 2 to class 1 with a certain probability, and we observe that interpolating decision trees reproduce this same structured label noise on the test set.
Similar results hold for decision trees; here we show experiments on two UCI tasks: wine and mushroom.
The wine task is a 3-way classification problem: to identify the cultivar of a given wine (out of 3 cultivars), given 13 physical attributes describing the wine. Figure 9 shows an analogous experiment with label noise taking class 1 to class 2.
The mushroom task is a 2-way classification problem: to classify the type of edibility of a mushroom (edible vs poisonous) given 22 physical attributes (e.g. stalk color, odor, etc). Figure 10 shows an analogous experiment with label noise flipping class 0 to class 1.

heading: C.5 MULTIPLE FEATURES
text: Conjecture 1 states that the network should be automatically calibrated for all distinguishable features, without any explicit labels for them. To verify this, we use the CelebA dataset (Liu et al., 2015), containing images with various labelled binary attributes per-image (“male”, “blond hair”, etc). Some of these attributes form a distinguishable feature for ResNet50 as they are learnable to high accuracy (Jahandideh et al., 2018). We pick one of hard attributes as the target classification task. We train a ResNet-50 to predict the attribute {Attractive, Not Attractive}. We choose this attribute because a ResNet-50 performs poorly on this task (test error ∼ 20%) and has good class balance. We choose an attribute with poor generalization because the conjecture would hold trivially for if the network
generalizes well. We initialize the network with a pretrained ResNet-50 from the PyTorch library Paszke et al. (2017) and use the hyperparameters described in Section B.2 to train on this attribute. We then check the train/test joint density with various other attributes like Male, Wearing Lipstick etc. Note that the network is not given any label information for these additional attributes, but is calibrated with respect to them. That is, the network says ∼ 30% of images that have ’heavy makeup’ will be classified as ’Attractive’, even if the network makes mistakes on which particular inputs it chooses to do so. In this setting, the label distribution is deterministic, and not directly dependent on the distinguishable features, unlike the experiments considered before. Yet, as we see in Figure 11, the classifier outputs are correctly calibrated for each attribute. Loosely, this can be viewed as the network performing 1NN classification in a metric space that is well separated for each of these distinguishable features.

heading: C.6 COARSE PARTITION
text: We now consider cases where the original classes do not form a distinguishable partition for the classifier in consideration. That is, the classifier is not powerful enough to obtain low error on the original dataset, but can perform well on a coarser division of the classes.
To verify this, we consider a division of the CIFAR-10 classes into Objects {airplane, automobile, ship, truck} vs Animals {cat, deer, dog, frog}. An MLP trained on this problem has low error (∼ 8%), but the same network performs poorly on the full dataset (∼ 37% error). Hence, Object vs Animals forms a distinguishable partition with MLPs. In Figure 12a, we show the results of training an MLP on the original CIFAR-10 classes. We see that the network mostly classifies objects as objects and animals as animals, even when it might mislabel a dog for a cat.
We perform a similar experiment for the RBF kernel on Fashion-MNIST, with partition {clothing, shoe, bag}, in Figure 12b. ImageNet experiment. In Table 2 we provide results of the terrier experiment in the body, for various ImageNet classifiers. We use publicly available pretrained ImageNet models from this repository, and use their evaluations on the ImageNet test set.

heading: C.7 DISCUSSION: PROPER SCORING RULES
text: Here we distinguish the density-estimation of Conjecture 1 from another setting where density estimation occurs. If `(p̂, y) is a strictly-proper scoring rule3 on predicted distribution p̂ ∈ ∆(Y)
3See Gneiting & Raftery (2007) for a survey of proper scoring rules.
and sample y ∈ Y , then the population minimizer of `(F (x), y) is exactly the conditional density F (x) = p(y|x). That is,
p(y|x) = argmin F :X→∆(Y) E (x,y)∼p [`(F (x), y)]
This suggests that in the limit of large-capacity network and very large data (to approximate population quantities), training neural nets with cross-entropy loss on samples (x, y) will yield a good density estimate of p(y|x) at the softmax layer. However, this is not what is happening in our experiments. First, our experiments consider the hard-thresholded classifier, i.e. the argmax of the softmax layer. If the softmax layer itself was close to p(y|x), then the classifier itself will be close to argmaxy p(y|x) – that is, close to the optimal classifier. However, this is not the case (since the classifiers make significant errors). Second, we observe Conjecture 1 even in settings where we train with non-proper scoring rules (e.g. kernel regression, where the classifier does not output a probability).

heading: D NEAREST-NEIGHBOR PROOFS

heading: D.1 FEATURE CALIBRATION PROPERTY
text: Proof of Theorem 1. Recall that L being an (ε,NN,D, n)-distinguishable partition means that nearest-neighbors works to classify L(x) from x:
Pr {xi,yi}∼Dn S={(xi,L(xi)}
x,y∼D
[NN (y) S (x) = L(x)] ≥ 1− ε (13)
Now, we have
{(NN(y)S (x), L(x))}S∼Dn x,y∼D ≡ {(ŷi, L(x))} S∼Dn x̂i,ŷi←NNS(x)
x,y∼D
(14)
≈ε {(ŷi, L(x̂i))} S∼Dn x̂i,ŷi←NNS(x)
x,y∼D
(15)
≈δ {(ŷi, L(x̂i))}x̂i,ŷi∼D (16)
Line (15) is by distinguishability, since Pr[L(x) 6= L(x̂i)] ≤ ε. And Line (16) is by the regularity condition.

heading: E NON-INTERPOLATING CLASSIFIERS: APPENDIX
text: Here we give an additional example of distributional generalization: in kernel SVM (as opposed to kernel regression, in the main text).

Review summaries:
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.

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. 

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.