Distributional Generalization: Structure Beyond Test Error
Authors: Preetum Nakkiran
Yamini Bansal
Venue: ICLR 2022 Submitted (2022)
Keywords: generalization
empirical phenomena
overparameterization

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.

Under review as a conference paper at ICLR 2022
DISTRIBUTIONAL GENERALIZATION: STRUCTURE BEYOND TEST ERROR
Anonymous authors Paper under double-blind review
ABSTRACT
Classifiers machine learning are often reduced to single dimensional quantities, such test error loss. Here, initiate 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, well quantitative conjec- tures 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 cats in the train set of CIFAR-10, then a ResNet trained to interpolation will in fact mislabel roughly 30% of dogs cats on the test ser 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 new kind of generalization, which goes beyond measuring single-dimensional quantities to measuring entire distributions.
INTRODUCTION
In learning theory, when we study how well a classifier "generalizes", we usually consider single metric- - its test eιror (Shalev-Shwartz & 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 (z. (xr) for samples from the distribution x ~ D for a classifier f(z). 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).
2014). However, there could be many different
Experiment 1. Consider binary classification version of CIFAR-1O, where CIFAR-IO images 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 Ob ject 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 not explicitly told what a cat 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 closest to option (3) as shown in Figure 1. The left panel shows the joint density of train inputs 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 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 stronger sense than just average error. Specifically, when
pnggroup-structure in the distribution. Second, the amount of error on

---

Under review as a conference paper at ICLR 2022
Train Set
Test Set
Orlect
6.10
0.00
0.20
2.00
5.00
0.00
0.23
0.32
6.00
0.00
0.93
6:00
Ided
Anfim
M:22
8:M
9.00
0.20
2.30
M133
0:10
0:30
0.00
Train classifier
f(x) Classieer
OIAR 10 Labedel
Figure I: The setup and result of Experiment 1. The CIFAR-IO train set is labeled as either Animals or Objects, with label noise affecting only cats. A WideResNet-28. 10 is then trained to 0 train error on this train set, and evaluated on the test set. Full experimental details in Appendix C.2
conditioned subgroup (cat), the distribution of the true labels is close to that of the classifier outputs. Third, this 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 thus behaving poorly from the perspective of Bayes-optimality, but behaving well a certain distributional sense (which will formalize soon).
Now, consider a seemingly unrelated experimental observation. Take an AlexNet trained on ImageNet, 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 may mistake the exact breed. In this work, 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 the true labels even when conditioned on many subsets of the domain. For example, in Figure I, the distribution of p(f(x)la the true label distribution p(y) cat). We propose a formal conjecture (Feature Calibration), that predicts which subgroups of the domain can be conditioned on for the above distributional closeness hold.
cat) is close
These experimental behaviors could not have been captured solely by looking at average test error, as is done the classical theory of generalization. In fact, they are special cases of new kind of generalization, which we call "Distributional Generalization".
1.1 DISTRIBUTIONAL GENERALIZATION
Informally, Distributional Generalization states that the outputs of classifiers on their train sets and test sets are close as distributions (as opposed to close in just error). That is, the following joint distributions' close: (x, f(=))s-Teesee (x))
(1)
The remainder this paper is devoted to making the above statement precise, and empirically checking its validity real- real-world tasks. Specifically, approximation (R), 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.
want formally define the notion of
1.2 OUR CONTRIBUTIONS AND ORGANIZATION
We discover new empirical behaviors of interpolating classifiers, and we propose quantitative conjec- tures 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, experimentally stress test Feature Calibration conjecture across various settings in machine learning, including neural networks, kernel machines, and decision trees. This highlights the universality of results across machine learning.
'These distributions also include the randomness in sampling the train and test sets, and in training the classifier, we define more precisely in Section 3.
2

---

Under review as a conference paper at ICLR 2022
In Section 5, relate results to classical generalization. by defining 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 new type of generalization exhibited across many methods machine learning.
1.3 RELATED WORK AND SIGNIFICANCE
Our work has connections to, and implications for many existing research programs in deep learning.
Implicit Bias and Overparamettrizztion.. There has been 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. 22018a;b 2019); Liang & Rakhlin (2018); Nakkiran et al. (2020); Schapire et al. (1998); Breiman (1995); Soudry et al. (2018); Gunasekar al. (2018)). The "implicit bias" program here aims to answer: Among all models with 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 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 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 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)). 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 overpurameterized scaling limit, where data-size < model-size always. The underparameterizee scaling limit is well-understood: when data is essentially infinite, neural networks will converge to the Bayes-optime 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 fxx is sample from p(y/ (z), as opposed to the Bayes-optimal f (z) = argmax,, p(y]z)). 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 would be consistent with that of a I-Nearest-Neighhor classifier in 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 & 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 -ineeinnnioonl structure
dinennnnsii manifold (Narayanan & Mitter, 2010; Sharma
3

---

Under review as a conference paper at ICLR 2022
in ligh-dimensional settings (Gerace 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 arXiv, it has been directly built on by other authors. The work Jiang et al. (2021) investigates our conjectures further, and extends them develop method for -ittr--dditributionn uncertainty estimation. This highlights the fundamental nature and importance of our results, since they have already been used in practical application. A full discussion of related works is in Appendix A.
2 PRELIMINARIES
Notation. We consider joint distributions D on I X' and discrete y y [k]]. Let S {(z,, yi) J=) ~ "D" 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 training a classifier f on train-set S using procedure A. We consider classifiers which output hard decisions f + V. Let (N) = z, denote the nearest-neighbor to æ 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 ( (z) denote the nearest-neighbor estimator itself, that NN (a) := y/ where F; = (2).
A denote
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 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 Prob- ability Metries (Müller, 1997), which we review here. For two distributions P, Q over X x V, let "test" (or "distinguisher") be function T X x - [o, 1] which accepts sample from either distribution, and is intended to classify the sample as either from distribution P or Q. For any set C C {T: X x y [0, 1]} of tests, say distributions P and Q are "s-indistinguishable up C-tests" they are close with respect to all tests in class That is,
P P
Q
[(x, TEe (a.N)~
sup
[Tx w) Se
(z.0)~
Total- Total-Variation Variation distance is equivalent to closeness in all tests, iee C (T X' 10, 1]}, but consider closeness for restricted families of tests C. P Re Q denotes e-closeness in TV-distance.
FEATURE CALIBRATION CONJECTURE
3.1 DISTRIBUTIONS OF INTEREST
We first define three key distributions that we will use in stating our formal conjecture. For a given data distribution D over X' x )' and training procedure Train consider the following three distributions over X' ):
1. Source D: (Ir where x, y D.
2. Train Du.: (Ziz, (aw)) where S ~ D". (S)) (Zi., Ver) ~ S
3. Test Dro: (xr, (x:) where S ~ D", f Train
D
The source distribution D is simply the original distribution. To sample once from the Train Dis- tribution D.. we first sample train set S ~ D" train classifier f on it, then output (æi, ((x)) for a random train point Fsg E S. That is, Drr is the distribution of input and outputs of a trained classifier f on its train set. To sample once from the Test Distribution Die. we do this same proce- dure, but output (x, f fx)) for a random test point x. That is, the D,c is the distribution of input and outputs of a trained classifier test time. The only difference between the Train Distribution and
4

---

Under review as a conference paper at ICLR 2022
Test Distribution is that the point is sampled from the train set the test set, respectively. For interpolating classifiers, f (I = Ytr on the train set, and so the Source and Train distributions are equivalent: D Dr.- (Note that these definitions, crucially, involve randomness from sampling the train set, training the classifier, and sampling a test point).
3.2 FEATURE CALIBRATION
We now formally describe the Feature Calibration Conjecture. At a high level, we argue that the distributions De 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(z), Re (L(x),))
We think of L as defining subgroups over the domain for example, L(x) E {dog, cat, horse... Then, the above statistical closeness is essentially equivalent to requiring that for all subgroups E [M], the conditional distribution of classifier output on the p(()) E) - is close to the true conditional distribution: Lx)) = f).
The crux of our conjecture lies in defining exactly which subgroups 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 fully-comme connected network (MLP) instead of ResNet. An MLP cannot properly distinguish cats even when it is actually provided the real CIFAR-10 10 labels, and so (informally) it has no hope of behaving differently on cats in the setting of Experiment 1, where the cats 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 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 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 distinguishable feature: a partition of the domain X' that is learnable for given training procedure. Thus, in Experiment I, 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 & Rs 0).
Definition A, n)- Distiiguusia Feature). For a distrúbution DD over x Y, number of samples training procedure A, and small 2 O, an (E, D, n) -ditiinguishable feature is partition L X + [M] ] of the domain 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,D, distinguishable feature if:
Pr S=((e,
[f(x) = L(x) 2xx)]21-111 21-5
S EADD fr-Train xnD
This definition depends only on the marginal distribution of on x. and not on the label distribution PD PD(vlz) (v(æ). To recap. this definition is meant capture labeling of the domain X' that is learnable for a given training procedure A. must depend on the architecture used by AA 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 (E, A, n) including features not implied by the class label such the presence of grass in CIFAR-10 image. Our main conjecture follows.
Conjecture (Feature Calibration). For all natural distributions DD number of samples n, interpo- lating training procedures A, and ε 2 O, the following distributions are statistically close for all (E, A, D, - features L:
(I(x), f()) ft Train (D"); a.y=DD
(L(x),)) 2.y<D
TTechnically, these definitions require training fresh classifier for each sample, using independent train sets. For practical reasons of our experiments train single classifier and evaluate the entire train/test
5

---

Under review as a conference paper at ICLR 2022
or equivalently:
(I(2)), 3) D..r--Dn
Ric
(L(x). a.yrD
(4)
This claims that the TV distance between the LHS and RHS of Equation (4) is at most E, where e is the error of the distinguishable feature (in Definition 1). We claim that this holds for all distinguishable features L "automatically" we simply train classifier, without specifying any particular partition. The formal statements of Definition and Conjecture 1 may seem somewhat arbitrary, involving many quantifiers over (e, A, DD n1). However, we believe these statements are natural: In addition to extensive experimental evidence in Section 4, we also prove that Conjecture is formally true as stated for -.Nearest-Neightee classifiers in Theorem 1.
3.3 FEATURE CALIBRATION FOR 1-NEAREST- NEIHHEESS
Here we prove that the I-Nearest-Neighher 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 below, it is unclear if our statement of Conjecture 1 can ever be satisfied by any classifier, if it is simply too strong to be true. This theorem applies generically class of distributions; the only assumption is weak regularity condition. The proof of Theorem is straightforward, and provided in Appendix D but this strong property of nearest- neighstsn was not know before, to our knowledge.
wide
Theorem 1. Let D be distribution over X x V, and let n E N be the number of train samples. Assume the following regularity condition holds: Sampling the nearest-neighhor train point random test point yields (close to) uniformly random test point. That is, suppose that for some =6 {z)znD- Then, Conjecture holds. That is,
small 6 2 0, the distributions: (NNs(z) Is-D"
for all (e, LN,NN, n.
( -distinguishable partitions L, the following distributions are statistically close:
{(y, (x)))))))aa
Reto
{(N(5)) (x), (x), SNDD
2.3=D
3.4 LIMITATIONS: NATURAL DISTRIBUTIONS
Technically, Conjecture 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 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 al., 2019: Li al., 2019; Allen-Zhu et al., 2018). 8). 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.
4 EXPERIMENTS FEATURE CALIBRATION
We now give empirical evidence for our conjecture in a variety of settings in machine learning. In each experiment, we consider 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:
For this feature, Conjecture reduces to the statement that the marginal distribution of class labels for Consider the
constant feature: L(x) = everywhere.
any interpolating classifier close to the true marginals p(y). To test this, we construct a variant of CIFAR- 10 with class-imbalange 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, for classifier that only achieves 37% test error.

---

Under review as a conference paper at ICLR 2022
Train Set
Tost Set
Thue 126
Reshet1S, Test Enor 0.09Ms
MLF. Test Error 37%
0.0
942
C 1255
Figure 2: Feature Calibration. (A) Random confusion matrix CIFAR-10, with Wede 10 trained to interpolation. Left: Joint density of labels y and original class I. on the train set. Right: Joint density of classifier predictions f(x) and original class I. the test set. These two joint densities are close, as predicted by Conjecture 1. (B) Constant partition: The CIFAR-I0 train set is class-rebalanced according the left panel distribution. The center and right panels show that both ResNets and MLPs have the correct marginal distribution of outputs, even though the MLP has high test eтrоr.
Wearing Lipstick
Heavy Makeup
0913 rodingg class 3-3 with prosibilty 50
Male
0
0.5
1030
0
0:1
0:42
0:30
2020
5050
TV Sescan
10300
0.15
0.38
0.20
0.31
0.40
0.12
11 20300
50000
0:34
0.11
0.29
Detriuztona
Gemeralizaiion
0.14
0.41
021
0.34
0.44
0.11
A
poostilty
B
Figure 3: Feature Calibration. (A) CIFAR-10 with p fraction of class 0 + mislabeled on the train set. Plotting observed noise classifier outputs vs. applied noise on the train set. (B) Multiple feature calibration on CelebA. (C) TV-distance between (L(z), (z)) and (L(x), y) for a variant of
Experiment 1 with error the distinguishable partitions (e). The error changed by changing the number of samples n.
Coarse Partition: Consider AlexNet trained on ILSVRC-2012 ImageNet (Russakovsky et al., 2015), 1000-class image classification problem with 1 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)) E {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 ImageNet are Terriers, and indeed the network classifies 20.9% of all dogs Terriers (though has 9% error which specific dogs it classifies as Terriers). See Appendix Table 2 for details, and related experiments on ResNets and kernels in Appendix C.
We now consider settings where the class labels are themselves distinguishable features (eg: CIFAR-I0 classes distinguishable by ResNets). Here conjecture predicts the behavior of interpolating classifiers under structured label noise. As an example, we generate a random spare confusion matrix and apply this the labels of CIFAR-10 shown in Figure 2A. We find that a WideResNer trained to interpolation outputs the same confusion matrix on the test set as well (Figure 2B). Now, test that this phenomenon 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 + 1 in the test set (Figure 3A shows p versus p). The Bayes optimal classifier for this distribution behaves red), and a classifier that obeys Conjecture exactly would follow the diagonal (in green). The actual experiment (in blue) is close to the behavior predicted by Conjecture 1. This experiment shows 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 different sense: they match the distribution of their train set. We discuss this further in Section See Appendix C.4 for more experiments, including other classifiers such Decisions Trees.
Class Partition:
step function (in
7

---

Under review as a conference paper at ICLR 2022
Multiple features: Conjecture 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 (aceuracy 80%) and confirm that the Feature Calibration holds for all the other attributes (Figure 3) that themselves distinguishable.
We now test the quantitative predictions made by Conjecture 1. This conjecture states that the TV-distance between the joint distributions f(x)) and (L(x), y) is most e, where & is the error of the training procedure in learning L (see Definition 1). To test this, we consider binary task similar to Experiment where (Ship, Plane) are labeled class 0 and (Cat, Dog) are labeled as class 1, with p = 0.3 fraction of cats mislabeled to class O. Then, we train a network 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, p,, F Flane, Cat, Dog). . Then, we use the same setup to train networks on the binary task and measure the TV-distance between (L(x), (x)) and (L(x), (z):; y) in this task. The results are shown in Figure 3C. As predicted, the TV distance on the binary task upper bounded by error the way classification task.
Quantitative predictions:
DISTRIBUTIONAL GENERALIZATION
In order relate our results the classical theory of generalization, we now propose a formal defimition 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 J be a trained classifier. Then J generalizes if:
E TrainSer (xx
10 [())) R
E
[1 + v(z))}
Teater (-f(2)
Above, y(xx) the true class of x and ÿ is the predicted class. The LHS of Equation 6 the train eтror of f. and the RHS is the test error. Using our definitions of Dur. Dre from Section 3.1, and defining Tem (x. ②) : 10 + y(r)}, we can write Equation 6 equivalently:
E [Ten 7)
[Tee (2, 7)]
That is, classical generalization states that certain function (Tan) has similar expectations on both the Train Distribution Dr, and Test Distribution Die. We can now introduce Distributional Generalization, which is a property of trained classifiers. is parameterized by a set of bounded functions ("tests")): T (T: X x y [0, 1]}.
Distributional Generalization: Let f be a trained classifier. Then f satisfies Distributional Gener- alization with respect to tests T if:
VT
[T(,
~
E x.yrDie
[T(x, 7)1
D.
This states that the train and test distribution have similar expectations for all functions in the family T, which we can write as: Dir RT Die- For the singleton set T {Ton). 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 object- not stating when or how it satisfied. Feature Calibration turns this into a concrete conjecture.
5.1 FEATURE CALIBRATION AS DISTRIBUTIONAL GENERALIZATION
We can write our Feature Calibration Conjecture as a special case of Distributional Generalization, for certain family of tests T. Informally, for 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( [(x), y) where I. is a distinguishable feature, and g is arbitrary. Formally,
8

---

Under review as a conference paper at ICLR 2022
Step 2000
Step 20000
Step 40000
Step 76000
Train Set
800
Test SSC
Figure 4: Distributional Generalization for WideResNet on CIFAR-10. The confusion matrices on the train set (top row) and test set (bottom row) remain close throughout training.
for a given problem setting, suppose & is the set of A, D, distiniinuuii features. Then Conjecture states that vL e L: (I(x), fxx) = (Ixx),) v)- This is equivalent to the statement
Dio - D
where iis is the set of functions : (T: T(x, g((()) LEC, g: xxxxx 1]}. For interpolating classifiers, we have D = Dtr. and so Equation (9) is equivalent to Die =²7 Dur. which is a statement Distributional Generalization. Since any classifier family will contain large number of distinguishable features, the set L may be very large. Hence, the distributions D,r and Dro. can be thought of as being close as distributions.
5.2 BEYOND INTERPOLATING METHODS
The previous sections focused 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 not as precise as previous sections, and is only meant 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, Dro R²T D.r for some family of tests T. For example, the following is possible generalization of Feature Calibration. Conjecture (Generalized Feature Calibration, informal). For trained classifiers f, the the following distributions statistically close for many partitions L of the domain:
(I(x). a.ji~Die
(I(x)).) 2.jj~Dar
(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 random sparse confusion the CIFAR-10 train set. We then train a single WideResNNe28-10 10, and measure its predictions on the train and test over increasing SGD steps. The top shows the confusion matrix of predictions f (xx true labels
[xx) on the train set, and the bottom row shows the corresponding confusion matrix on the test set.
As the network is trained for longer, fits more of the noise on the train set, and this noise mirrored almost identically on the test set. Full experimental details in Appendix B.
CONCLUSION
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 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 results inspire further work on distributional generalization in machine learning.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error in neural networks. arXiv preprint 1rxiv:1110.0.::0 2017.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv:1811.049/ 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang, Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in neural information processing systems, pp. 6158-6169, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332, 2019.
Susan Athey, Julie Tibshirani, Stefan Wager, et al. Generalized random forests. The Annals of Statistics, 47(2):1148-1177) 2019.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681) 2017.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. In Advances in neural information processing systems, pp. 2300-2311, 2018a.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. arXiv preprint arXiv: 802.01396, 2018b.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnie practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, 116632):1584--15554 2019.
Lco Breiman. Reflections after refereeing papers for nips. The Mathematics of Generalization, pp. 11-15, 1995.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Leo Breiman, Jerome Friedman, Charles Stone, and Richard A Olshen. Classification and regression frees. CRC press, 1984.
Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. arXiv preprint 1rXh::2004.12019, 2020.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04486, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httttt//////ctive ics. www..edu.u.. mmdu
Gintare Karolina Dziugaite and Daniel Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: /703. 1008, 2017.
Manuel Germandez-Delgado. Delgado, Eva Cernadas, Senén Barro, and Dinani Amorim. Do need hundreds of classifiers to solve real world classification problems? The journal of machine learning research, 15(1):3133-318, 2014.
Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A new perspective generalization in neural networks. arXiv preprint arXiv: (00i:::991.094440 2019.
10

---

Under review as a conference paper at ICLR 2022
Mario Geiger, Stefano Spigler, Stéphane d' A'sooli Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition as paradigm to understand the loss landscape of deep neural networks. Physical Review E, 100(1):01211,, 2019.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Gener- alisation error in learning with random features and the hidden manifold model. arXiv preprint arXiv:2002.09333, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint arXiv: 12191, 2019.
Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-378, 2007.
Sebastian Goldt, Madhu S Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborova. Generalisation dynamics of online learning in wver-parameterised neural networks. arXiv preprint arXiv:1901.00085, 2019.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832-1841. PMLR, 2018.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. arXiv preprint arXiv:1706.04599 2017.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 0tt.::/933.08555 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Úrsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cali- bration for the compuuationally--denfffall masses. In International Conference on Machine Learning, pp. 1939-1948. 2018.
Tin Kam Ho. Random decision forests. In Proceedings of 3rd international conference on document analysis and recognition, volume 1, pp. 278-282. IEEE, 1995.
Rashidedin Jahandideh, Alireza Tavakoli Targhi, and Maryam Tahmasbi. Physical attribute prediction using deep residual neural networks. arXiv preprint arXiv:1812.07885 2018.
Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, and J Zico Kolter. Assessing generalization of sgd via disagreement. arXiv preprint arXiv:2106. 13799, 2021.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6611)):227-23222 1998.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. arXiv preprint arXiv:1907.04599. 2019.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can generalize. arXiv preprint arXiv: 1808. 00387, 2018
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Song Mei and Andrea Montanari. The generalization error random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv:/908.053.0 2019.

---

Under review as a conference paper at ICLR 2022
Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7(Ju)): 983-999, 2006.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443, 1997.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless inter-
polation of noisy data in regression. IEEE Journal on Selected Areas Information Theory, 2020.
Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may unable to explain generaliza- tion in deep learning. 2019.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. International Conference on Learning Representations, 2020.
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In Advances in neural information processing systems, pp. 1786-1794, 2010.
Nagarajan Natarajan, Inderjit Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems, pp. 1196-1204 2013.
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioannis Mitliagkas. A modern take on the bias-variance tradcoff in neural networks. arXiv preprint arXiv: 1rXhv:1810.0859/1 2018.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over per-paaametrizationn in generalization of neural networks. arXiv preprint 18Xx::/005./2770 2018.
Alexandru Niculescu-Mizzi and Rich Caruana. Predicting good probabilities with supervised learning. In Proceedings of the 22nd international conference on Machine learning, pp. 625-632, 2005.
Matthew A Olson and Abraham Wyner. Making sense of random forest probabilities: kernel perspective. arXiv preprint arXiv: 2018.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vito,, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel. M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau,, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-leamn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
Taylor Pospisil and Ann B Lee. Rfede: Random forests for conditional density estimation. arXiv preprint arxiv:1880 384.05553, 2018.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning robust to massive label noise. arXiv preprint arXiv: 1704. 2017.
Jonas Rothfuss, Fabio Ferreira, Simon Walther, and Maxim Ulrich. Conditional density estimation with neural networks: Best practices and benchmarks. arXiv preprint wwXiv:1903.0095. 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg. and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 2015. doi: 10.1007/sl 1263-015-0816--
12

---

Under review as a conference paper at ICLR 2022
Robert E Schapire. Theoretical views of boosting. In European conference computational learning theory, pp. 1-10. Springer, 1999.
Robert E Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee, et al. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 2665):1651-1686 1998.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Vaishaal Shankar, Alex Fang. Wenshuo Guo, Sara Fridovich- Keil, Ludwig Schmidt, Jonathan Ragan- Kelley, and Benjamin Recht. Neural kernels without tangents. arXiv preprint arXiv:2003.02237, 2020.
Utkarsh Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004. 10802, 2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018
Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd- Yusof. Combating label noise in deep learning using abstention. arXiv preprint arXiv: 19X444, 2019.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake Vand erPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, F. A. Quintero, Charles R Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-22 272, 2020. doi: https://doi.org/1.. 10000000000/1111-1999-66666
Larry Wasserman. All of statistics: a concise course in statistical inference. Springer Science & Business Media, 2013.
Geoffrey Watson. Smooth regression analysis. Sankhyā: The Indian Journal of Statisties, Series A. pp. 359-372, 1964.
Abraham J Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of adaboost and random forests as interpolating classifiers. The Journal of Machine Learning Research, 18(1):1558-1555 1590, 2017.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747 2017. 2017.
Mohammad Yaghini, Bogdan Kulynych, and Carmela Troncoso. Disparate vulnerability: On the unfaimess of privacy attacks against machine learning. arXiv preprint arXiv: (0..199600093 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:1605.07146 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: /6/ 1.03530, 2016.
Liu Ziyin, Blair Chen, Ru Wang, Paul Pu Liang, Ruslan Salakhutdinov, Louis Louis-Philippe Morency, and Masahito Ueda. Learning not learn in the presence of noisy labels. arXiv preprint arXiv:2002.06541, 2020.
13

---

Under review as a conference paper at ICLR 2022
A FULL RELATED WORK
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;ba 2019); Liang& & Rakhlin (2018); Nakkiran et al. (2020); Mei & Montanari (2019); Schapire et al. (1998); Breiman (1995); Chorbani et al. (2019); Hastie 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 et al. (2019); Neyshabur 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 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 tabular data Germández-Delgadde 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., 201 8a: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 (c.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 equivalent to Madaraya-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-neighhors since they are explicitly method (Hastie et al., 2009). Thus, it may not be surprising that decision trees behave similarly to 1- Searest--Niighbors. Wyner et al. (2017); Olson & Wyner (2018) took steps towards characterizing and understanding this behavior- - in particular, Olson & Wynne (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 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 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 et al. (201 8b)), and there are many works on making networks more robust to label noise via modifications the training procedure or objective (Rolnick 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 be fixed, but rather a consequence of a stronger property: distributional generalization.
sensitive label noise (e.g. Figure 1 in Zhang et al. (2016), and Belkin
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 distribution approximating the conditional density of p(y(z) in a certain sense. Conditional density estimation has been well-studied in classical nonparametric statistics (e.g. the Nadaraya- 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 al. (2019)). Random forests have also been known to exhibit properties similar to conditional density estimators. This has been formalized various ways, often only with asymptotic guarantees (Meinshausen, 2006; Pospisil & Lee, 2018; Athey al., 2019).
14

---

Under review as a conference paper at ICLR 2022
No prior work that 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 multicalibra- tion (Guo et al., 2017; Niculescu-Mizie Mizil & Caruana, 2005; Hébert-Johnson et al., 2018). In our framework, calibration is implied by Feature Calibration for specific of partitions (determined by level sets of the classifier's s confidence). However, we are not concerned with 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-classe classclassiiiiationn deci- sions and not confidences, and we study only standard learning algorithms which are not given any in advance. Our notion of distributional generalization is
distinguished set of cubgroups/partitiinn also related to the notion of "distributional subgroup overfitting" introduced recently by Yaghini et al. (2019) to study algorithmic fairness. This can be seen studying distributional generalization for 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 works 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 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 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 {(x;, 8t}} } will yield a good density estimate of p(y(zr) 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 I even in settings without proper scoring rules (kernel SVM and decision trees).
B EXPERIMENTAL DETAILS
Here we describe general background, and experimental details common to all sections. Then we provide cettion-specffe details below.
B. DATASETS
We consider the image datasets CIFAR- and CIFAR-100 (Krizhevsky et al., 2009), MNIST (LeCun et al., 1998), -ashion-MNIST (Xiao et al., 2017), CelebA (Liu et al., 2015), and ImageNet (Rus- sakovsky et al., 2015). We normalize images to z E [0, 1jx 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 Frrnández-Delgadd et al. (2014). Some of these tasks have very few examples, so we restrict to the 92 classification tasks from Fernández-Delgado et al. (2014) which have least 200 total examples.
B.2 MODELS
We consider neural-networks, kernel methods, and decision trees.
B.2.1 DECISION TREES
We train interpolating decision trees using a growth rule from Random Forests (Breiman, 2001; Ho, 1995): selecting split based on a random vd subset of d features, splitting based on Gini impurity, and growing trees until all leafs have single sample. This is imple- mented by Scikit-leam Pedregosa et al. (2011) defaults with CandomPorestClasee (n_est imators=1, bootstrap=Falls lse).
15

---

Under review as a conference paper at ICLR 2022
B.2.2 KERNELS
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 (2018b); Shankar et al. (2020). We solve the following convex problem training:
a'
argmin ||Ka - yll2 + Xa Ka DERNXM
where K, = ,( is the kernel matrix of the training points for kernel function k; y E RNX the one-hot encoding of the train labels, and À 2 0 the regularization parameter. The solution can be written
a' = (K + +
which we solve numerically using SciPy 1 iinalg.soly
(Virtanen et al., 2020). We use the explicit form of all kernels involved. That is, we not use random-feature approximations (Rahimi & Recht, 2008), though expect they would behave similarly.
The kernel predictions on test points are then given by
Ia (x)x) = Σ ask(o,, x)
(11)
SE[N]
(z) == argmax (x))
(12)
JE[M]
where g(æ) E R.M are the kernel regressor outputs, and g(x) E [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 (A 0), except in Section 5.2.
For kernel SVM, we use the implementation provided by Scikit-learn (Pedregosa al., 2011) sklearn. svm SVC with precomputed kernel, for inverse-regularizztoon parameter C 2 0 (larger C' corresponds smaller regularization).
Types of Kernels. We use the following kernel functions k Rd x Rd + R
Gaussian Kernel (RBF): k(z1, 22) exp(- || -0.--:18
27
Laplace Kernel: (z) exp( |||, -
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 = ē/Vd. We use the following bandwidths, found by cross-validation to maximize the unregularized test accuracy:
MNIST: 0.15 for RBF kerne..
Fashion-MNIST: 0.1 for RBF kernel. a 1.0 for Laplace kernel.
CIFAR-10: Myrtle10 Kernel from Shankar al. (2020), and o 0.1 for RBF kernel.
B.2.3 NEURAL NETWORKS
We use 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 BatchNoomalization layer and ReLU activation function.
WideResNet:
We the standard WideResNet-225 10 described in Zagoruyko & Komodakis (2016).
Our code is based on this repository.
ResNet50: We standard ResNet-50 from the PyTorch library (Paszke et al., 2017).
16

---

Under review as a conference paper at ICLR 2022
MLP
R8
WideResNet
NesNe
Batchsize Epochs
128
128
128
32
820
200
200
50
Adam
SGD +
SGD +
Optimizer
SGD
(3 = 0.9, |2 = 0.999)
Momentum (0.9)
Momentum (0.9)
Initial LR = 0.001,
Inital LR= 0.05
Inital LR= 0.1
Learning rate (LR) schedule
scale by 0.1 if training loss stagmant for 2000 gradient steps
Constant LR 0.001
scale by 0.1 at
scale by 0.2
epochs (80, 120)
epochs (80, 120, 160)
Data Augmentation
Random flips + RandomCropp322, padding-4)
CIFAR-10 Error
37%
8%
4%
N/A
Table 1: Hyperparameters used to train the neural networks and their errors the unmodified
CIFAR-10 dataset
ResNet18: We use modification of ResNet18 He al. (2016) adapted CIFAR-10 image sizes. Our code is based on this repository.
For Experiment and Section 4, the hyperparameters used train the above networks are given in Table 1.
17

---

Under review as a conference paper at ICLR 2022
C FEATURE CALIBRATION. APPENDIX
C.I A GUIDE TO READING THE PLOTS
All the experiments support of Conjecture involve various quantities which we enumaerate here
1. Inputs z: Each experiment involves inputs from 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 We consider various features like the original classes itself, 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 constructed binary task as Experiment
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. [(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(z)), [(x)) for all training inputs x. We also refer (f(x), L(x)) as the test density, measure this only the test set.
C.2 EXPERIMENT
Experimental details: We now provide further details for Experiment 1. We first construct a dataset from CIFAR-10 10 that obeys the joint density (y: [ax)) shown in Figure left panel. We then train -ideResNeet28-- 10 (WRN-28- 10) this modified dataset zero training error. The network is trained with the hyperparameters described Table We then observe the joint density (f(x), Lxx) on the test images and find that the 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. uniformly random CITAR-I0 image, and sample the label as p(y|æ)
Sample I Bernoulli( Cww.IIAACaass.... (x) 10)). That is, if the CIFAR-10 class of x is label is 1 with probability (k/10) and O otherwise. Figure 5 shows this joint distribution of (I, y) As before, train a WideResNet to 0 training error on this distribution.
9}. then the
In this experiment too, we observe that the train and test joint densities are close as shown Figure
Now, we repeat the same experiment, but with an MLP instead of WRN-28-108 10. The training procedure described in Table 1. This MLP has an error on 37% on the original CIFAR-10 dataset.
Since this MLP has poor accuracy the original CIFAR-10 classification task, it does not form distinguishable partition for As a result, the train and test joint densities (Figure 6) do not match as well as they did for WRN-28- 20.
C.3 CONSTANT PARTITION
Conjecture states that the marginal distribution of class labels for any interpolating classifier (() close to the true marginals p(y). To show this, we construct a dataset based on CIFAR-10 that has class-imi cass-imbalance. For class & {0...), sample (k + 1) x 500 images from that class. This will give us a dataset where classes will have marginal distribution p(y = E) x + for classes E [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 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
18

---

Under review as a conference paper at ICLR 2022
0
0.10
0.09
0.08
0.07
0.06
0.05
0.04
0.03
0.02
0.01
1
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0
0.10
0.09
0.08
0.07
0.07
0.06
0.04
0.03
0.02
0.01
f
1
0.00
0.01
0.02
0.03
0.03
0.04
0.06
0.07
0.08
0.09
plane
auto-
bird
cat
deer
dog
frog
horse
ship
truck
mobile
Joint densities of the distributions involved Experiment 2. The top panel shows the joint density of labels on the train set: (CIFAR.C)) class y The bottom panels shows the joint density of classifier predictions the test set: (CIFAR_C) ass (x) f(r)). Distributional Generalization claims that these two joint densities are close.
Figure 5: Distributional Generalization in Experiment 2.
0
0.10
0.09
0.08
0.07
0.06
0.05
0.04
0.03
0.02
0.01
1
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0
0.08
0.07
0.07
0.06
0.06
0.06
0.05
0.04
0.03
0.03
f(x)
1
0.02
0.03
0.03
0.04
0.04
0.04
0.05
0.06
0.07
0.07
plane
auto- mobile
bird
cat
deer
dog
frog
horse
ship
truck
Figure 6: Joint density of (y. (1)ss())), top, and (f(x), Class(x)), bottom, for test samples (x. y) from Experiment 2 for MLP.
C.4 CLASS PARTITION
C.4.1 NEURAL NETWORKS AND CIFAR-10
We now describe details for the experiments in Figures 2A and 3A. A WRN-28-10 10 achieves an enror of 4% on CIFAR- 10. Hence, the original labels CIFAR-10 form distinguishable partition for this dataset. To demonstrate that Conjecture holds, consider different structured label noise the CIFAR-I0 dataset. To do so, we apply variety of confusion matrices to the data. That is, for confusion matrix C 10 x 10 matrix, the element Cij gives the joint density that randomly sampled image had original label j. but flipped to class For no noise, this would be an identity matrix.
We begin by simple confusion matrix where flip only class 0 1 with varying probability Figure 7A shows one such confusion matrix for = 0.4. We then train a WideResNet-22 10 zero train error this dataset. We the hyperparameters described in B.2 We find that the
19

---

Under review as a conference paper at ICLR 2022
classifier outputs on the test set closely track the confusion matrix that applied to the distribution.
Figure 7C shows that this is independent of the value of p and continues to hold for p = [0, 1].
A
B
Imistabeling class 0-11 with probabiltty p)
Wideetesseet-22 10 CITAR-10
BCC
3.93
13000
3.00
000
0.05
0.00
666
0.00
6.c0
0.00
6:00
0.00
0.00
0.00
6:00
00
0,00
0:00
0.00
6.00
0:90
0.00
0:50
0.00
0.
0:00
0:65
9:00
0:00
6:C0
0:00
0.00
6:00
9.99
8:00
0.90
0.00
0:00
8:00
f(x)
4.60
1:1
way
6:12
616
0:00
9:93
10:30
6:16
C:09
10:0
8:44
0000
E43
389
0.00
6:0
646
3.00
0.10
000
6.00
002
3:90 0.39
0.0
644
0:00
0.10
600
Bayes Optimal Distributional Gereera lcation Wi NedeReNet
DIC
191 0.99
6/0
eEe
0.00
010
9:9
0:00
0.00
CX0
E40
0.00
0.00
0.0
6.30
04 05 07 probabiity
Figure 7: Feature Calibration with original classes on CIFAR-10: We train a WRN-28- 10 on the CIFAR-10 10 dataset where we mislabel class - 1 with probability p. (A): Joint density of the distinguishable features L (the original CIFAR-10 10 class) and the classification task labels y on the train set for noise probability p = 0.4. (B): Joint density of the original CIFAR-10 10 classes L and the network outputs fzz on the test set. (C): Observed noise probability in the network outputs on the test set (the (1, 0) entry of the matrix in B) for varying noise probabilities
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 sparse confusion matrix 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 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.
C.4.2 DECISION TREES
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 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 wi wine task is a 3- w-w classification problem: to identify the cultivar of given wine (out of cultivars), given 13 physical attributes describing the wine. Figure 9 shows an analogous experiment with label noise taking class to class 2.
The mushroom task is 2-way classification problem: to classify the type of edibility of 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.
C.5 MULTIPLE FEATURES
Conjecture 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 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 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
20

---

Under review as a conference paper at ICLR 2022
p
0.0
0.1
0.2
0.3
0.4
Train Set
0.00
0.30
0.24
0:24
0.00
0.24
0:00
0.00
3.24
0.00
0.00
2.24
0.05
0.0C
0.24
0.10
0.00
0.24
0.18
0.00
0.24
0.20
6.00
0.24
0.25
3.00
6.00
0.00
0.00
0.00
0.30
0.00
0.52
0:00
0,0
=
0.1
0.2
0.3
0.4
0.5
Test Set
3.32
0:02
0.17
((4)
0.02
1-10
0.00
0.02
0.0
0.03
10
10
0.04
0.20
0.22
0:08
1.
0:22
Figure 8: Feature Calibration for Decision trees on UCI (molecular biology). We add label noise that takes class 2 to class 1 with probability E [0, 0.5]. The top row shows the confusion matrix of the true class (xx) vs. the label y on the train set, for varying levels of noise p. The bottom row shows the corresponding confusion matrices of the classifier predictions fæx on the test set, which closely matches the train set, as predicted by Conjecture 1.
p 0.0
0.1
0.2
0.3
0.4
p
0.5
Train Set
0.00
0.00
0.34
0:00
26.1
0.00
2.40
0.00
24
0.00
0.28
0.00
0.0C
0.32
0.00
24
0.00
0.31
0.00
>
0.00
0.23
0.00
0.00
0:21
0.00
3.00
0:04
0:00
0.07
0.06
0.00
0.27
0:00
0:27
0,0
=
0.1
0.2
0.3
0.4
0.5
Test Set
3.32
0105
0.30
0.00
[X4)
3:39
0:00
0.00
0:30
02
0:00
0.00
0.20
8:00
0:02
8:23
5.00
0:c0
11
0.00
Figure 9: Decision trees on UCI (wine). We add label noise that takes class to class with probability p E [0, 0.5]. Each column shows the test and train confusion matrices for given p. Note that this decision trees achieve high accuracy on this task with no label noise (leftmost column). We plot the empirical joint density of the train set, and not the population joint density of the train distribution, and thus the top row exhibits some statistical error due to small-sample effects.
generalizes well. We initialize the network with a pretrained ResNet-50 from the Py PyTorch library Paszke et al. (2017) and use the hyperparameters described in Section B.2 to train 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' 'Attractive'. even if the network makes mistakes on which particular inputs
will be classified 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 Figure 11, the classifier outputs are correctly calibrated for each attribute. Loosely, this can be viewed as the network performing INN classification in a metric space that is well separated for each of these distinguishable features.
C.6 COARSE PARTITION
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 coarser division of the classes.
21

---

Under review as a conference paper at ICLR 2022
p 0.0
p = 0.1
p 0.2
0.3
0.4
p
Train Set
0:48
0.39
1B
016
0:48
0.1
0:46
0.26
p 0.0
= 0.1
= 0.2
p 0.3
p 0.4
p 0.5
0:35
0.30
0.00
0.00
((3)
Test
0.22
Figure 10: Decision trees UCI (mushroom). We add label noise that takes class 0 to class 1 with probability p E [0, 0.5]. Each column shows the test and train confusion matrices for given p. Note that this decision trees achieve high accuracy on this task with no label noise (leftmost column).
Wearing Lipstick
Heavy Makeup
Blond
Eye- Glasses
Male
Hair
0.42
0.43
0.06
0.15
0.36
0.20
0.31
0.46
0.05
0.40
0.12
0.51
0.01
0.34
0.11
0.39
0.07
0.44
0.01
0.18
0.28
0.39
0.06
f(x)
0.14
0.41
0.21
0.34
0.49
0.06
0.44
0.11
0.54
0.01
0
Figure 11: Feature Calibration for multiple features on CelebA: We train ResNet-50 to perform binary classification task the CelebA dataset. The top row shows the joint distribution of this task label with various other attributes in the dataset. The bottom row shows the same joint distribution for the ResNet-50 outputs on the test set. Note that the network was not given any explicit inputs about these attributes during training.
To verify this, we consider a division of the CIFAR-10 10 classes into Objects fairplane, 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 distinguishable partition with MLPs. Figure 12a, we show the results of training an MLP on the original CIFAR- 10 classes. We see that the network mostly classifies objects objects and animals as animals, even when it might mislabel a dog for a cat.
We perform similar experiment for the RBF kernel Fashion-MNIST. with partition (clothing, shoe, bag}, in Figure 12b.
ImageNet experiment. In Table 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 the ImageNet test set.
C.7 DISCUSSION: PROPER SCORING RULES
Here distinguish the censity-estimation of Conjecture from another setting where density estimation occurs. If Ei y) is a strietly-proper scoring rule' on predicted distribution p E A())
See Gneiting& Raftery (2007) for survey of proper scoring rules.
22

---

Under review as a conference paper at ICLR 2022
Model
AlexNet
ResNet18
ResNet50
BagNet8
BagNet32
ImageNet Accuracy Accuracy on dogs
0.565
0.698
0.761
0,464
0.667
0.588
0.729
0.793
0.462
0.701
Accuracy on terriers
0.572
0.704
0.775
0,421
0.659
Accuracy for binary (dog/not-dog)
0.984
0.993
0.996
0.972
0.992
Accuracy on (terrier/no--teriier) among dogs
0.913
0.955
0.969
0.876
0.944
Fraction of real-terriers among dogs Fraction of predicted-terriers among dogs
0.224
0.224
0.224
0.224
0.224
0.209
0.222
0.229
0.192
0,215
Table 2: ImageNet classifiers calibrated with respect dogs: All classifiers predict terrier for roughly ~ 22% of all dogs (last row), though they may mistake which specific dogs are terriers.
Actual
sted 2n Tael
Hebr Slrd
3.39
3.
877
811
Cea
5.59
811
mic
3.29
6.3
Fiac
0001
1:2
Eoc
(a) CIFARIO + MLP
(b) Fashion-MNIST MNIST RBF
Figure 12: Coarse partitions as distinguishable features: consider a setting where the original classes are not distinguishable, but superset of the classes are distinguishable.
23

---

Under review as a conference paper at ICLR 2022
and sample y E V/ then the population minimizer of ((F(()) v) is exactly the conditional density F(x) 2)). That is,
p()x) argmin F(X-)(()) (m.w)~>
E
[((F())))))
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 (æ,, y) will yield good density estimate of p(y]2)) 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. the softmax layer itself was close to p(y|zz) then the classifier itself will be close to argmax, p(y|æ) that is, close to the optimal classifier. However, this is not the case (since the classifiers make significant errors). Second, observe Conjecture even in settings where train with non-proper scoring rules (e.g. kernel regression, where the classifier does not output a probability).
D NEAREST-NEIGHBOR PROOFS
D.1 FEATURE CALIBRATION PROPERTY
Proof of Theorem I. Recall that L being an NN, D, diddiniinee partition means that nearest-neighbors works to classify L(x) from æ:
[NN = [t))
Pr f-" S (=((;; a,8rD
(13)
Now, we have
(NNN5) (x), [(x)))
S-DD
= ((7, M(x))
(14)
2WWDD
R ((0) I(E)))
5~D"
(15)
N
I.
R8 (0T) ((G:)) [( Z:D:DD
(16)
Line (15) is by distinguishability, since Pr[l(x) + L(E)) S c. And Line (16) is by the regularity condition.
E NON-INTERPOLATING CLASSIFIERS: APPENDIX
Here we give an additional example of distributional generalization: in kernel SVM (as opposed to kernel regression, in the main text).
24

---

Under review as a conference paper at ICLR 2022
Thaiy
2:3
Train
Test. 20
MC 012
6O
I+ 3M
Figure 13: Distributional Generalization. Train (left) and test (right) confusion matrices for kernel SVM on MNIST with random sparse label noise. Each row corrosponds to one value of inverse- regularization parameter C. All rows are trained on the same (noisy) train set.
25

---

Under review as a conference paper at ICLR 2022
Step 2000
Step 20000
Step 40000
Step 76000
Train Set
1X0
Test Set
1600
Figure 14: Distributional Generalization for WideResNet on CIFAR-10.
We apply label noise from random sparse confusion the CIFAR-10 train set. We then train single WideResNet28-101 10, and measure its predictions on the train and test sets over increasing train time (SGD steps). The top row shows the confusion matrix of predictions f(x)) true labels L(xr) 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 the train set, and this behavior is mirrored almost identically on the test set.
26


Reviews:
[{"review_id": "ZaRRGKciyMR", "reviewer": "Reviewer_bHpa", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThough 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.\n\nTo 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.\n\nThere 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_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.", "summary_of_the_review": "As mentioned below, the overall framework is not convincing to me and hence I recommend rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Xc2erX96zMr", "reviewer": "Reviewer_SzaL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \nBut 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. \n", "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. \nThe authors present some examples where \"distinguishable features\" depends on classifier. They prove the conjecture for nearest neighbors classifier under some regularity conditions. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GlUGXU2AXzF", "reviewer": "Reviewer_4xds", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths of the paper:\n1.\tIt is well-written and the main ideas are clearly presented. The paper is also quite self-contained.\n2.\tThe proposed empirical observation is novel to the best of my knowledge and a significant observation.\n3.\tThe paper proposes a neatly formalized explanation behind the phenomenon and performs a good set of experiments to back their claim.\n\nWeaknesses:\n1.\tBased 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.\n\nComments and questions:\n1.\tWhat 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.\n2.\tIt 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.\nHowever, 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).\n3.\tIt 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.\n\nMinor comments:\n1.\tAlexNet top-1 accuracy on ImageNet reported as 56.5%. Isn’t this 63.3%?\n2.\tAnother 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.\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

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