Distributional Generalization: A New Kind of Generalization
Authors: Preetum Nakkiran
Yamini Bansal
Venue:  (2021)
Keywords: understanding deep learning
generalization
interpolating methods
empirical investigation

Abstract: We introduce a new notion of generalization--- Distributional Generalization--- which roughly states that outputs of a classifier at train and test time are close as distributions, as opposed to close in just their average error. 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 behavior is not captured by classical generalization, which would only consider the average error and not the distribution of errors over the input domain. Our formal conjectures, which are much more general than this example, characterize the form of distributional generalization that can be expected in terms of problem parameters: model architecture, training procedure, number of samples, and data distribution. We give empirical evidence for these conjectures across a variety of domains in machine learning, including neural networks, kernel machines, and decision trees. Our results thus advance our understanding of interpolating classifiers.

Under review as a conference paper at ICLR 2021
DISTRIBUTIONAL GENERALIZATION: A NEW KIND OF GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce new notion of generalization- Distributional Generalization which roughly states that outputs of classifier at train and test time are close as distributions, as opposed to close in just their average error. For example, if we mislabel 30% dogs as cats the train set CIFAR-10, then ResNet trained interpolation will in fact mislabel roughly 30% of dogs cats on the test set as well, while leaving other classes unaffected. This behavior is not captured by classical generalization, which would only consider the average error and not the distribution errors over the input domain. Our formal conjectures, which are much more general than this example, characterize the form of distributional generalization that can be expected in terms of problem parameters: model architecture, training procedure, number of samples, and data distribution. We give empirical evidence for these conjectures across a variety of domains in machine learning, including neural networks, kernel machines, and decision trees. Our results thus advance our understanding of interpolating classifiers.
INTRODUCTION
We begin with an experiment motivating the need for a notion of generalization beyond test error. Experiment 1. Consider binary classification version of CIFAR-IO, where CIFAR- 10 images have binary labels Animal 1aaaa///bjeee /ectect. Take 50K samples from this distribution as a train set, but apply the following label noise: flip the label of cats to Objec Object with probability 30%. Now train WideResNet f to O train error this train set. How does the trained classifier behave test samples? Options below:
1. The test error is low across all classes, since there is only 3% label noise in the train set
2. Test error "spread" across the animal class, After all, the classifier is not explicitly told what cat dog is, just that they are all animals.
3. The classifier misclassifies roughly 30% of test cats "objects", but all other types of animals are largely unaffected.
In fact, reality is closest to option (3). Figure [ shows the results of this experiment with a NedeResNet. The left panel shows the joint density of train inputs with train labels Ob jbject/ Animal, Since the classifier is interpolating, the classifier outputs on the train set are identical to the left panel. The right panel shows the classifier predictions (x) on test inputs
Train Set
Test Set
Drler 0.12
5.10
0.00
0.22
2,00
0.00
0:22
5.00
0.00
0.20
Obex:
Idbel Anlma
810
0.35
0.30
0.11
6:10
0.00
0.08
Train a classifier
f(x) Claraifer
0.22
8.00
0.06
0.22
8.10
CIFA Labedol
CBAU Lubelol
Figure 1: The setup and result of Experiment] I The CIFAR-10 train set is labeled either Animals or Objects, with label noise affecting only cats. A WideResNeet28- 10 is then trained to 0 train error on this train set, and evaluated on the test set. Full experimental details are in C.2

---

Under review as a conference paper at ICLR 2021
There are several notable things about this experiment. First, the error is localized to cats in test set as it was in the train set, even though no explicit cat labels were provided. Second, the amount of error on the cat class is close to the noise applied on the train set. Thus, the behavior of the classifier on the train set generalizes to the test set in a certain sense. This type of similarity in behavior would not be captured solely by average test error it requires reasoning about the entire distribution of classifier outputs. In our work, we show that this experiment is just one instance of a different type of generalization, which we call "Distributional Generalization". We now describe the mathematical form of this generalization. Then, through extensive experiments, we will show that this type of generalization occurs widely existing machine learning methods: neural networks, kemnll machines and decision trees.
1.1 DISTRIBUTIONAL GENERALIZATION
Supervised learning aims to learn a model that correctly classifies inputs I E X' from a given distribution D into classes y E y. We want a model with small test error on this distribution. In practice, we find such a classifier by minimizing the train error of a model on the train set. This procedure justified when we expect a small generalization gap: the gap between the error on the train and test set. That is, the trained model should have: ErrorTainser (f) ~ Errorressee (f). We now re-write this classical notion of generalization Classical Generalization: Let f be trained classifier. Then f generalizes if:
form better suited for our extension.
E [1 + v()x)}
R
E Teater (-((2)
[1 + v(z)
(1)
eoTrainSer (ar
Above, y(xx) the true class of x and ÿ is the predicted class. The LHS of Equation I the train error of f. and the RHS is the test error. Crucially, both sides of Equation I are expectations of the same function (Ter(2,)) 77 == [ + y(z))) under different distributions. The LHS of Equation is the expectation of Fer under the "Train Distribution" Dr., which is the distribution over (z, V) given by sampling train point x along with its classifier-label fax). Similarly, the RHS is under the "Test Distribution" Die. which is this same construction over the test set. These two distributions are the central objects in our study, and are defined formally in Section 2.T 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 trained classifier. Then f satisfies Distributional Gener- alization with respect to tests T if:
ET
E De TruinSer g+ f(x)
E
[Txx 7)
Teseeeer f(z((z
We write this property as Dr. R7 Dic- This states that the train and test distribution have similar expectations for all functions in the family T. For the singleton set T= {Ten), ) this is equivalent to classical generalization, but may hold for much larger sets T. For example in Experiment [ the
train and test distributions match with respect to the test function "Fraction of true cats labeled as object." In fact, it best think of Distributional Generalization stating that the distributions Dur and Dee are close as distributions.
This property becomes especially interesting for interpolating classifiers, which fit their train sets exactly. Here, the Train Distribution (I;, fx;)) ) is exactly equal"]n to the original distribution (r. y) ~ D. since (x;) = yi on the train set. In this case, distributional generalization claims that the output distribution (x, (=)) of the model on test samples is close to the true distribution (ær, y). The following conjecture specializes Distributional Generalization to interpolating classifiers, and will be the main focus of our work.
Interpolating Indistinguishabiiity Meta-Conjecture (informal): For interpolating classifiers f. and a large family T of test functions, the distributions:
(a, f())) T (x., f())(( (z)) = (x,, 2.
'The formal definition of Train Distribution, in Section 2.1 includes the randomness of sampling the train set well. We consider fixed train set in the Introduction for sake of exposition.
2

---

Under review as a conference paper at ICLR 2021
This is a "meea--onjecture"", which becomes a concrete conjecture once the family of tests T is specified. One of the main contributions of our work is formally stating two concrete instances of this conjecture- conjecure-sppccfyingg specifying exactly the family of tests T and their dependence on problem parameters (the distribution, model family, training procedure, etc). It captures behaviors far more general than Experiment I, and applies to neural networks, kernels, and decision trees. We give empirical evidence for conjectures across a variety of natural settings in machine learning.
1.2 SUMMARY OF CONTRIBUTIONS
We extend the classical framework of generalization by introducing Distributional Generalization, in which the train and test behavior of models are close distributions. Informally, for trained classifiers f. its outputs on the train set (z, (x)) TeTinnse are close in distribution to its outputs on the test set (ar, f where the form of this closeness depends on specifics of the model, training procedure, and distribution. This notion is more lin-grained than classical generalization, since considers the entire distribution of model outputs instead of just the test error.
We initiate the study of Distributional Generalization across various domains in machine learning. For interpolating classifiers, we state two formal conjectures which predict the form of distributional closeness that can be expected for given model and task:
1. Feature Calibration Conjecture (Section 3): Interpolating classifiers, when trained on sam- ples from a distribution, will match this distribution up to all "distinguishable features" (Definition D.
2. Agreement Conjecture (Section 4 For two interpolating classifiers of the same type, trained independently the same distribution, their agreement probability with each other test samples roughly matches their test accuracy.
We perform number of experiments surrounding these conjectures, which reveal new behaviors of standard interpolating classifiers (e.g. ResNets, MI.Ps, kernels, decision trees). We prove our conjectures for N-NeabesttNeighbors (Theorem D. which suggests some form of "locality" as the underlying mechanism. Finally, we discuss extending these results to non-interpolating methods in Section 5 Our experiments and conjectures shed new light on the structure of interpolating classifiers, which are extensively studied in recent years yet still poorly understood.
Related Work. Our work is inspired by the broader study of interpolating and overparameterized methods in machine learning (c.g. [Zhang et al. (2016); [elkin et al. (201 by 2019); Liang and Rakhlin 2018); Nakkiran al. (2020); Schapiire al. (1998); Breiman (1995)) In similar vein to our work, Wynner et al. (2017): Olson and Wyner (008) investigate decision trees, and show that random forests are equivalent to Nadaraya-Watte Watson smoother (Nadaraya 1964 Watson
1964) with
a certain smoothing kernel. Our conjectures also describe neural networks under label noise, which has been empirically and theoretically studied in the past (Zhang el al. 2016 Belkin al. 2018b
Rolnick et al. 2017] Natarajan et al., 2013) Thulasidasa et al.) [019]] Ziyin et al.) [2020] Chatterji and Long 2020). though not formally characterized. The behaviors we consider are also similar to conditional density estimation (e.g. [sybakov (2008); Dutordoir et al. (2018), though we consider samplers, not density estimators. We include a full discussion of related works in Appendix
PRELIMINARIES
Notation. We consider joint distributions D on E X and discrete E y = [kc] Let D" denote n iid samples from D and ((r,, 3t) denote train set. Let denote the classifier family (including architecture and training algorithm for neural networks), and let ʃ +- Trainz(S)) denote training a classifier f E F on train-set S. We consider classifiers which output hard decisions f X - y.
Let NNs(z) x; denote the nearest-neighhor to x in train-set S, with respect to a distance metric d. Our theorems will apply to any distance metric, and so we leave this unspecified. Let NN(") (x)
denote the nearest-neighhor estimator itself, that is, NN (x) V: where r; (Ns(x))
Experimental Setup. Full experimental details are provided in Appendix B Briefly, we train all classifiers to interpolation (to 0 train error). Neural networks (MIPs and ResNets (He et al. 2016)
3

---

Under review as a conference paper at ICLR 2021
trained with SGD. Interpolating decision trees are trained using the growth rule from Random Forests (Breiman 2.01). For kernel classification, we consider kernel regression on one-ho hot labels and kernel SVM, with small or 0 of regularization (which is often optimal [Shankar et al. (2020)).
Distributional Closeness. We consider the following notion of closeness for two probability dis- tributions: For two distributions P, Q over X y, let a "test" (or "distinguisher") be function T: x y - [o, 1] which accepts a sample from either distribution, and is intended to classify the sample as either from distribution P or Q. For any set C C {T': X x y + [0, I]] of tests, we say distributions P and Q are "e-indistinguuisable up to C-tests" if they are close with respect to all tests in class C. That is,
P
sup TEC
(Tx v)] (Z.9)~P
E
E (a.7)
[Tx, w\] S
VarialVaiittion distance is equivalent to closeness in all tests, i.e. C = : x x - 10, 1]}, but we consider closeness for restricted families of tests C. P = Q denotes e-closeness in TV-distance.
2.1 FRAMEWORK FOR INDISTINGUISHABILITYY
We consider throughout the following three distributions over X' x V:
Source D: (x. v) where z. y ~ D
Train Dir: (Der, f(w S~ D" .f f- Trainz(S), Per, Utr ~ S
Test Dio (I. fxx) S ~ D" f Tr))
Iyy~D D
The Source Distribution D simply the original distribution. To sample from the Train Distribu- tion Der, we first sample a train set S ~ DD" train a classifier f on it, then output (Far, (irrs((zaa (xxr)) for random train point Tur- That is, Der is the distribution of input and outputs of a trained elassifier on its train set. To sample from the Test Distribution Dre. do we this same procedure, but output (z, f(x)) for a random test point x. That is, the Pre is the distribution of input and outputs of a trained classifier f at test time. The only difference between the Train Distribution and Test Distribution is that the point x is sampled from the train set or the test set, respectively 2 For interpolating classifiers, (*+.) = 3hr on the train set, and so the Source and Train distributions are equivalent: = Dir. Our general thesis is that the Train and Test Distributions are indistinguishable under a variety of test families T. Formally, we argue that for certain families of tests T and interpolating classifiers F, the distributions: D Dr, ~ Dee. Sections 3 and give specific families of tests T for which these distributions are indistinguishable.
3 FEATURE CALIBRATION
The distributional closeness of Experiments 1 is subtle, and depends on the classifier architecture, distribution, and training method. For example, Experiment 1 does not hold if use a fully- connected network (MLP) instead of a ResNet, or if we early-stop the ResNet instead of training to interpolation (see Appendix C.2 Both these scenarios fail in different ways: An MLP cannot properly distinguish cats even when trained on real CIFAR- 10 labels, and so (informally) it has On the other hand, an
no hope of behaving differently on cats in the setting of Experiment early-stopped ResNet for Experiment does not label 30% of cats objects on the train set, since it does not interpolate, and thus has no hope of reproducing this behavior on the test set. We now characterize these behaviors, and their dependency on problem parameters, via formal conjecture.
This conjecture characterizes a family of tests T for which the output distribution of a classifier (z, f()) Die is "close" to the souree distribution (z, y) ~ D. At high level, argue that the distributions Die and D are statistically close if we first "coarsen" the domain of x by some labelling L X + [M]. That is, for certain partitions L, the following distributions are statistically close: (I(x), (x)) Re (I(x). Intuitively, allowable partitions are those which can be learnt from samples. To formalize the set of allowable partitions L for training algorithm, we define
Technically, these definitions require training fresh classifier for each sample, using independent train sets. We use this definition because we believe it is natural, although for practical reasons most of our experiments train single classifier f and evaluate the entire train/test set.
4

---

Under review as a conference paper at ICLR 2021
distinguishable feature:
partition of the domain X' that is learnable for given family of models. For example, in Experiment the partition into CIFAR-10 classes would be a distinguishable feature for ResNets, but not for MLPs.
Definition ((eFF, n Distinguishable Feature). For a distribution DD over X V, number of samples n., family of models F, and small & 2 0, an Fe DD ni-dditiiguuisaall feature is a partition : X [M] of the domain X into M parts, such that training a model from F samples labeled by L works to classify L with high test accuracy. Precisely, L is Fs D, n)) distiinguishhble feature if:
Pr S=((s,,LEdd)a F (--Train==SS) 2nD
[f(z)
L(x) 2 1
This definition depends only on the marginal distribution of D on x, and not on the label distribution PD (ylær). To recap, this definition is meant capture labeling of the domain X' that is learnable for a given training procedure. It must depend on the classifier family F 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, F, D, n) including features not implied by the class CIFAR-10 10 image. Our main conjecture in this section that the test distribution (z, f())) ~ Die is statistically close to the source distribution (z, v) ~ 'D when the domain is "coarsened" by a distinguishable feature. Formally:
label such the presence of grass
Conjecture (Feature Calibration). For all natural distributions D. number of samples n. family of interpolating models F, and & 2 O, the following distributions are statistically close for all (c, F.F.DDD D., n.) distinguusshhble features L;
(L(z), f(x)) f+-Train (DD") a.y-DD
RE
(L(z). 2,ywD
(4)
We claim that this holds for all distinguishable features "automatically" - we simply train a classifier, without specifying any particular partition. As trivial instance of the conjecture, suppose have distribution with deterministic labels, and consider the e-distinguishable feature L(x) =- y(x), i.e. the label itself. The here is then simply the test error of f, and Conjecture is true by definition. The formal statements of Definition T and Conjecture [ may seem somewhat arbitrary, involving many quantifiers over (e, F, n.n). However, we believe these statements are natural. To support this, in Theorem [ we prove that Conjecture[[is formally true as stated for I-Nearest --Nearost-Neighbor classifiers.
Connection to indistinguishability. Conjecture iss an instantiation of our general Indistinguishably Conjecture. In particular, Conjecture [ is equivalent to the statement Die mf D where L is the family of all tests which depend on x only via a distinguishable feature L. In other words, Die is indistinguishable from 'D to any function that only sees the input via a distinguishable feature L(x).
3.1 EXPERIMENTS
We now give empirical evidence for our conjectures in variety of settings in machine learning, including neural networks, kernel machines, and decision trees. Selected experiments are summarized here, with full details and further experiments in Appendix C
Constant Partition: Consider the triviallyddistinuuihbbbl constant feature L(x) O. Then, Con- jecture I states that the marginal distribution of class labels for any interpolating classifier (xx is close to the true marginals p(y). We construct a variant of CIFAR- 10 with llass-imallance and train classifiers with varying levels of test errors (9-41%) to interpolation on it. The marginals of the classifier outputs are close to that of the train set, irrespective of the test error. (See Appendix
Class Partition: We now consider settings where the original class labels form a distinguishable feature (eg: CIFAR-10 10 classes are distinguishable by ResNets). The conjecture holds for arbitrary distributions p(y) (z). This includes the setting of Experiments from the Introduction. We mislabel class 0 + 1 with probability p in the CIFAR-10 train set and train WideResNet-28-1U1 (WRN-28-10) on this distribution. Now, we observe the fraction of samples mislabeled by this network 5 from 0 + 1 in the test set. Figure 2 shows versus P. The Bayes optimal classifier for this distribution behaves as a step function (in red), and a classifier that obeys Conjecture I exactly would follow the diagonal (in green). The actual experiment (in blue) is close the behavior predicted by Conjecture 1.
5

---

Under review as a conference paper at ICLR 2021
Appendix C.4 includes experiments for more distributions (including random joint density matrices) and other classifiers such as Decisions Trees.
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. 2013), containing images with many binary attributes per image. We train ResNet- 50 to classity one of the hard attributes (accuracy 80%) and confirm that the output distribution is calibrated with respect all attributes (Figure 2 that are themselves distinguishable by a ResNet-50.
Multiple features:
Consider AlexNet trained on ILSVRC-2012 ImageNet (Russakovsky et al., 2015), 1000-class image classification problem with 1 166 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 (xx) E {dog, not-dog) distinguishable feature. Per Conjecture 1, the network is calibrated with respect to dogs: 22.4% of all dogs in ImageNet are Terriers, and the network classifies 20.9% of all dogs as Terriers (though has 9% error on which specific dogs it classifies as Terriers). See Appendix Table for details, and related experiments on ResNets and kernels in Appendix C
Coarse Partition:
A
Wideebentinn2--11- a CIPAD-10
B
Wearing Lipstick
Heavy Makeup
(misiabcling class -n with probabiiity e)
Male
0.7
0-
0.38
0.11
0.42
0.07
0.18
0.30
Figure 2: Feature Cali- bration. (A) CIFAR-10 with fraction of class 0 0 1 mislabeled. Actual p vs. observed noise in the classifier outputs. (B) Mul-
0.36
0.31
0.12
Optimal
0
0.11
0.39
0.07
0.28
Generallzation
Wicuhss/ut
tiple feature calibration on CelebA.
0.14
0.41
0.21
0.34
0.44
0.11
Nclse probubilty
3.2 DISCUSSION
Conjecture 1 claims that Die is close to D up to all tests which are themselves learnable. That is, an interpolating method is capable of learning a certain partition of the domain, then it will also produce outputs that are calibrated with respect this partition, when trained on any problem. This conjecture thus gives a way of quantifying the resolution with which classifiers approximate the source distribution D, via properties of the classification algorithm itself. This is in contrast many classical ways of quantifying the approximation of density estimators, which rely on analytic (rather than operational) distributional assumptions (Tsybakov 2008 Wasserman 2006).
Proper Scoring Rules. If the loss function used in training is a strictly-proper scoring rule such as cross-entropy (Gneiting and Raftery] 2007), then we may expect that in the limit of large- capacity network and infinite data, training on samples {(T;, v:)} 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 T even in settings without proper scoring rules (e.g. kernel SVM and decision trees).
1-N -Nearest-Neighbors Connection. Here we show that the L-Nearest-Neighhee classifier provably satisfies Conjecture [ under mild assumptions. This theorem applies generically to a wide class of distributions, with no assumptions on the ambient dimension of inputs or the underlying metric. The only assumption is a weak regularity condition: sampling the nearest-neighbor train point to a random test point should yield (close to) a uniformly random test point.
Let 'D be distribution over X x Y, and let n N be the number of train samples. Assume the following regularity condition holds: Sampling the nearest-neighhor truin point to random test point yields (close to) uniformly random test point. That is, suppose that for some 26 {æ) Then, Conjecture 7 holds. That is.
Theorem 1.
small 8 2 0, the distributions: {NN s ((NNs())ss)) (x))s=pp anD
for all (e, NN, D, D.n)D..nddinnnn distingguuiee partitions L, the following distributions are statistically close:
{1v, (xx)))xz.gr)
Reto
(NNNS) (x), [(x)) S-D" 2.y~D
(5)

---

Under review as a conference paper at ICLR 2021
The proof of Theorem is straightforward, and provided in Appendix We view this theorem both as support for our formalism of Conjecture [ and as evidence that the classifiers we consider in this work have local properties similar to -eearest-Neighbos.
AGREEMENT PROPERTY
We now present an "agreement property" of interpolating classifiers. This property is independent of the previous section, though both are special cases of our general indistinguishabiity conjecture. We claim that, informally, the test accuracy of classifier is close the probability that it agrees with identically-traiin trrinned classifier on a disjoint train set.
Conjecture (Agreement Property). For certain classifier families F and distributions D, the test accuracy of a classifier is close its agreement probability with independently-natn trainne classifier. That is, let S1.5y S2 be disjoint train sets sampled from D and let fi, f2 be classifiers trained on S1, 82 respectively, then
Pr (1
Pr (i(x)= = [2(x))
(6)
(2.0)~D
(2.9)-D
Moreover, this holds with high probability over training f1, f2: P((aw))D(f((z) P((eeii=D/((s)- = [2(=]]
y)
The agreement property may be surprising for several reasons. For example, suppose we have two classifiers f1, f2 which were trained on independent train sets, and both achieve test accuracy say 50% on a 10-class problem. Depending other much less than they agree with the true label, since each individual classifier is an independently noisy version of the truth. OR (2) They agree with each other much more than 50%, since elassifiers tend to have "correlated" predictions. However, in practice there is a surprising coincidence, and they agree with each other very close to 50%. Conjecture also provably holds for -.Nearest-Neighbor in some settings, under stronger assumptions (Theorem 2 in Appendix EE. Finally, in Section D.3 we consider, and refute, several potential mechanisms which could explain the experimental results of Conjecture 2
intuition, may expect (1) They agree with each
Connection Indistinguishahiiity Conjecture is fact a special case of our general Indistin-
guishability Conjecture. Formally, consider the specific test Tugree (x. 77) + 1 (x) 7 where fi (D*). The expectation of this test under the Source Distribution D is exactly the LHS of Equation 6 while the expectation under the Test Distribution Dio is exactly the RHS. Thus,
Conjecture can be equivalently stated as R Tigm
Dre.
4.1 EXPERIMENTS
In our experiments, we train pair of classifiers fi, f2 on random disjoint subsets of the train set for a given distribution. Both classifiers are oth- erwise trained identically, using same architecture, number of train- samples n, and optimizer. We then plot the test eπror of fi against the agreement probability fa(x)). Figure 3 shows experiments with ResNet18 on CIFAR-10 and CIFAR-100, with varying train sam- ples n. The Agreement Property ap- proximately holds for all pairs of iden- tical classifiers, and continues to hold even for "weak" classifiers (c.g. when f1, fo have high test error). Full experimental details are in Appendix [] including further experiments with RBF and Laplace kernels, the Myrtlel0 kernel (Shankar et al. 2020), and decision trees on UCI tasks.
Agreement: ResNlet18
Agreement: ResNet18. CIFAR 100
1.0
0.8
1=1000
Iw3333
0.9
igreement Probwbiing ity
0.8
1=15000
Incco
Dorcement Probabiity
0.6
IW23330
3233333
0.5
0.0
[f (x) =
0.2
8.1
0.3
0.0
Test
Test Accuracy
Figure 3: Agreement Property on CIFAR-10/100.

---

Under review as a conference paper at ICLR 2021
5 DISTRIBUTIONAL GENERALIZATION! BEYOND INTERPOLATING METHODS
The previous sections have focused on interpolating classifiers, which fit their train sets exactly. For con-interpolating classifiers, their outputs on the train set (a, f (a))a=-Transee will nor match the original distribution (x, 2/ ~ 'D. Thus, there little hope that their outputs the test set will match the original distribution, and we do not expect the Indistinguishabiity Conjecture to hold. How- ever, Distributional Generalization does not require interpolation, and we could still expect that the the train and test distributions are close (Dtr RM Drc) for some family of tests T. For example, the following is a possible generalization of Feature Calibration.
Lambdo -
Lambda 0.1
Conjecture 3 (Generalized Feature Calibration, informal), For trained classifiers f. the following distributions statistically close for many partitions L of the domain:
Lambda 1.0
( 21 2ir/TrainSet
(I(z), f(x))
(7)
Lambda 10.0
We leave unspecified the exact set of partitions L for which this holds, since we do not yet understand the appropriate notion of "dis- tinguishable feature" in this setting. However, we give experimental evidence suggesting some refinement of Conjecture 3 is true. In Figure 4 we train Gaussian kernel regression on MNIST. with label noise determined by random sparse confusion matrix. We vary the f2 regularization, and plot the confusion matrix of predictions on the train and test sets. With higher regularization, the kernel no longer interpolates the train set, but the test and train confusion matrices remain close. That is, regularization prevents the kernel from fitting the noise on both the train and test sets a similar way. Full experimental details are given in Appendix B including an analogous experiment for neural networks CIFAR-10 10, with carly-stopping in place of regularization (Fig- ure (22). These experiments suggests that Distributional Generalization a meaningful notion even for non-interpolating classifiers.
Figure 4: Distributional Gen- eralization
CONCLUSION AND DISCUSSION
In this work, we presented a new set of empirical behaviors of standard interpolating classifiers. We unified these under the framework of Distributional Generalization, which states that outputs of trained classifiers on the test set are "close" distribution to their outputs on the train set. For interpolating classifiers, we stated several formal conjectures (Conjectures andd] 2 to characterize the form of distributional closeness that can be expected.
Beyond Test Error. Our work proposes studying the entire distribution of classifier outputs test samples, beyond just its test error. We show that this distribution is often highly structured, and we take steps towards characterizing to satisfy certain forms of distributional generalization "automatically." despite being trained to simply minimize train error. This even holds in cases when satisfying distributional generalization is in conflict with satisfying classical generalization- that is, when a distributionally geneeallliggg classifier must necessarily have high test error (e.g. Experiments I and 2). We thus hope that studying distributional generalization will be useful to better understand modern classifiers, and to understand generalization more broadly.
Surprisingly, modern interpolating classifiers appear
Classical Generalization. Our framework of Distributional Generalization can be insightful even to study classical generalization. That is, even if we ultimately want to understand test error, it may be easier to do so through distributional generalization. This is especially relevant for understanding the success of interpolating methods, which pose challenges to classical theories of generalization. Our work shows new empirical behaviors of interpolating classifiers, well as conjectures characterizing these behaviors. This sheds new light on these poorly understood methods, and could pave the way to better understanding their generalization.
8

---

Under review as a conference paper at ICLR 2021
Interpolating vs. Non-interpolating Methods. Our work also suggests that interpolating classifiers should be viewed as conceptually different objects from non con-interpolating ones, even if both have the same test error. In particular, interpolating classifier will match certain aspects of the original distribution, which a non-interpolating classifier will not. This also suggests, informally, that interpolating methods should not be seen methods which simply "memorize" their training data in a naive way (as in a look up table) rather this "memorization" strongly influences the classifier's decision boundary (as in -.eearett-Neighbrrs)
Limitations. The conjectures presented in this work are not fully specified, since they do not exactly specify which classifiers or distributions for which they hold. We experimentally demonstrate instances of these conjectures in various "natural" settings in machine learning, but we do not yet understand which assumptions on the distribution or classifier are required. Some experiments also deviate slightly from the predicted behavior. Nevertheless, we believe our conjectures capture the essential aspects of the observed behaviors, at least to first order. is an important open question to refine these conjectures and better understand their applications and limitations- both theoretically and experimentally.
6.1 OPEN QUESTIONS
Our work raises number of open questions and connections other areas. We briefly collect some of them here.
1. As described in the limitations, we do not precisely understand the set of distributions and interpolating classifiers for which our conjectures hold. We empirically tested number of "realistic" settings, but is open to state formal assumptions defining these settings.
2. It is open to theoretically prove versions of Distributional Generalization for models beyond 1 --Nearest-Neighbors This is most interesting in cases where Distributional Generalization is at odds with classical generalization (e.g. Figure
3. It is open to understand the mechanisms behind the Agreement Property (Section theo- retically or empirically.
4. There are a number of works suggesting "local" behavior of neural networks, and these are somewhat consistent with our locality intuitions in this work. However, it open to formally understand whether these intuitions are justified in our setting.
5. We give two families of tests T for which our Interpolating Indistinguishabiiity Meta- conjecture empirically holds. This may not be exhaustive there may be other ways in which the source distribution D and test distribution Dre are close. It is open to explore more ways in which Distributional Generalization holds, beyond the tests presented here.
REFERENCES
Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error neural networks. arXiv preprini arXiv: 2017.
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, pages 6158-6169, 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, pages 322-332, 2019.
Susan Athey, Julie Tibshirani, Stefan Wager, al. Generalized random forests. The Annals of Statistics, (7(2):1148-117) 2019.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):6296611, 2017.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.

---

Under review as a conference paper at ICLR 2021
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting perfect fitting? risk bounds for classification and regression rules that interpolate. In Advances in neural information processing systems, pages 2300-2311, 2018a.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. understand deep learning we need to understand kernel learning. arXiv preprini arXiv: /eX.vv:800..00 280.001966 2018b.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32)118849-1555 2019.
Leo Breiman. Reflections after refereeing papers for nips. The Mathematics of Generalization, pages 11-15, 1995.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. Classification and regression trees. CRC press, 1984.
Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. arXiv preprint arXiv: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 http: ics. uci. edu/ml
Vincent Dutordoir, Hugh Salimbeni, James Hensman, and Marc Deisenroth. Gaussian process conditional density estimation. In Advances in neural information processing systems, pages 2385-2395, 2018.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprins arXiv:1703.11008, 2017.
Manuel Fernández- Delgado, Eva Cernadas, Senén Barro, and Dinani Amorim. Do we need hundreds of classifiers to solve real world classification problems? The journal of machine learning research, 15(1):3133-3181, 2014.
Stanislav Fort, Pawet Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A new perspective on generalization in neural networks. arXiv preprint (xXiv:1911009499 2019.
Mario Geiger, Stefano Spigler, Stéphane Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition paradigm understand the loss landscape of deep neural networks. Physical Review E, 100(1) (00(1):01211) 15, 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 20X30:2002.093339 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint 1rXiv:1904.121911 2019.
Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):3593375 2007.
Sebastian Goldt, Madhu S Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborova. Generalisation dynamics of online learning in parmmerraeteri neural networks. arXiv preprint arXiv:1901.09083 2019.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. arXiv preprint arXiv: 076770004999 2017.
10

---

Under review as a conference paper at ICLR 2021
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 S00i:::99030085000 2019.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
Ürsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cali- bration for the (computationalll-iddnn) Learning, pages 1939-1948, 2018.
masses. International Conference on Machine
Tin Kam Ho. Random decision forests. In Proceedings of 3rd international conference on document analysis and recognition, volume 1, pages 278 282. IEEE, 1995.
Rashidedin Jahandideh, Alireza Tavakoli Targhi, and Maryam Tahmasbi. Physical attribute prediction using deep residual neural networks. arXiv preprint 1rXiv:1812.07755/ 2018.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances neural information processing systems, pages 6402-6413 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):278-22224, 1998.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can generalize. arXiv preprint arXiv: 00387, 2018.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint 1008.09990005300 2019.
Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7(Ju)): 983-999, 2006.
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 be 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. In International Conference Learning Representations, 2020.
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In Advances in neural information processing systems, pages 1786-1794 2010.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems, pages 1 1204, 2013.
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioannis Mitliagkas. A modern take on the bias- bias-variance tradeoff in neural networks. arXiv preprint arXiv: / 810.0889) 2018.
11

---

Under review as a conference paper at ICLR 2021
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over paramerrattiinnionnn in generalization of neural networks. arXiv preprint arXiv:1805.12076. 2018.
Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learning. In Proceedings of the 22nd international conference on Machine learning, pages 625-632, 2005.
Matthew A Olson and Abraham Wyner. Making sense of random forest probabilities: kernel perspective. arXiv preprint arXiv: 1.12v::811.05792 2018.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vito,o Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
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-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 12:2825-2830, 2011.
Taylor Pospisil and Ann B Lee. Rfede: Random forests for conditional density estimation. arXiv preprint arXiv: 1r04. 05753, 2018.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pages 1 1177-1184, 2008
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv preprint arXiv: 10694, 2017.
Jonas Rothfuss, Fabio Ferreira, Simon Walther, and Maxim Ulrich. Conditional density estimation with neural networks: Best practices and benchmarks. arXiv preprint arXiv: /9Kiv:9903.00 19033009344 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 (3):211-252, 2015. doi: 10. 1263-015-081
Robert E Schapire. Theoretical views of boosting. In European conference on computational learning theory, pages 1-10. Springer, 1999.
Robert E Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee, al. Boosting the margin: A new explanation for the effectiveness voting methods. The annals of statistics, 26(5):1651 1998.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Ked Keil, Ludwig Schmidt, Jonathan Ragan- Kelley, and Benjamin Recht. Neural kernels without tangents. arXiv preprint vrXiv:2003.02237. 2020.
Utkarsh Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004. 2202000440000... 2020.
Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd- Yusof. Combating label noise in deep learning using abstention. arXiv preprint arXiv:1905. 2019.
Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media, 2008
Pauli Virtanen, Ralf Gommers, Travis 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, A. Quintero, Charles R Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1. O Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: https://doi..or/1000 1038//111111111111 001-8394199---1-666-----9
12

---

Under review as a conference paper at ICLR 2021
Larry Wasserman. All of nonparametric statistics. Springer Science & Business Media, 2006.
Geoffrey S Watson. Smooth regression analysis. Sankhya: The Indian Journal of Statistics, Series A, pages 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-159) 2017.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747 2017.
Mohammad Yaghini, Bogdan Kulynych, and Carmela Troncoso. Disparate vulnerability: On the unfairness of privacy attacks against machine learning. arXiv preprint arXiv: (XKiv:900.00000 00389, 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 4rX.v:660..07146 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 1611.0300 2016.
Liu Ziyin, Blair Chen, Ru Wang. Paul Pu Liang, Ruslan Salakhutdinov, Louis-Philippe Morency, and Masahito Ueda. Learning not learn in the presence of noisy labels. arXiv preprini arXiv:2002.06541, 2020.
13

---

Under review as a conference paper at ICLR 2021
A FULL RELATED WORK
Our work is inspired by the broader study of interpolating and overparaameterized methods in machine
learning; a partial list of works in this theme includes Zhang et al. (20T6); [Blliin et al. (2018a) 80 bb.
2019| Liang and Rakhlin (2018); Nakkiran et al. (2020); Mei and M (2019); |Schapire et al.
(1998) ; Breiman [995g; Ghorbani et al. (2019); Hastie et al. (2019); Bartlett et al. (2020); Advani
and Saxe (2017); Geiger et al. (2019); Gerace al. (2020); Chizat and Bach (2020); Goldt et al.
(2019) x Arora et al. (2019): Allen Zhu et al. (2019); Neyshabur et al. 20188; Dziugaite and Roy
(2017) Muthukumar al. (2020): Neal et al. (0188)
Interpolating Methods. Many of the best-performing techniques on -igh-dimensional tasks are interpolating methods, which fit their train samples to 0 train error. This includes neural-networks and kernels on images (He et al., 2016] (Shankar et al., 2020), and random forests on tabular data 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
(Fernández-Delgaddo
Schapire, 1999; [Breiman| 1995; Zhang et al. 2016, Belkin al. 2018a by 2019] Liang and Rakhlin 2018: and Montanari [2019] Hastie et al., 2019 Nakkiran et al., 20200) 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 /Zhngg jet al., 2016 [Belkin et al. 20188 by Nagarajan and Kolter 2 The few techniques which do apply to interpolating methods (c.g. margin theory (Schapire al. 1998)) remain vacuous modern neural-networks and kernels.
Decision Trees. In similar vein to our work. Wyner et al. 2017) Olson and Wyner (2018)
investigate decision trees, and show that random forests are equivalent to a Nadaraya Watson smoother Naddaaay (1964); Watson (1944) with certain smoothing kernel. Decision trees (Breiman jet al. 1984) are often intuitively thought of as "adaptive nearest-neighbott
since they are explicitly ppattal-partitioning method (Hastie et al. [2009). Thus, it may not be surprising that decision trees behave similarly to 1 Seaarest-Neighoors Wyner et al. (2017); Olson and Wyner (2018) took steps towards characterizing and understanding this behavior in particular, OOson and Wyner (2018) defines an equivalent smoothing kernel corresponding to a random forest, and empirically investigates the quality of the conditional density estimate. Our work presents a formal characterization of the quality of this conditional density estimate (Conjecture I which is a novel characterization even for decision trees, as far as we know.
Kernel Smoothing. smoothers, such as the AadaraaaaWaatson 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.
The term kernel regression is sometimes used in the literature to refer to kernel
Label Noise. Our conjectures also describe the behavior of neural networks under label noise, which has been empirically and theoretically studied in the past, though not formally characterized before (Zhang et al. 2016: Belkin et al. 2018b Rolnick al. 2017]] Natarajan et al.) 2013 Thulasidasan ct al. 2019 Ziyin et al. 20200 Chatterji and Long 2020). Prior works have noticed that vanilla sensitive label noise (e.g. Figure 1 in /Zhang et al. (2016), and Belkin et al. (2018b)), and there are many works on making networks more robust to label noise via modifications 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.
interpolating networks
Conditional Density Estimation. Our density calibration property is similar to the guarantees of a conditional density estimator. More specifically, Conjecture I 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 nigh-dimentional problems via augmenting estimators with neural networks (e.g. Rothfuss et al. (2019). Random forests have also been known to exhibit properties similar to conditional density estimators. This has been formalized in various ways, often only with asymptotic guarantees (Meinshausen 2006; Pospisil and Lee. 2018 Athey et al. 2019).
14

---

Under review as a conference paper at ICLR 2021
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 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.
Uncertainty and Calibration. The Agreement Property (Conjecture bears some resemblance to uncertainty estimation (e.g. Lakshminarayanan et al. (2017), since it estimates the the test error of a classifier using an ensemble of models trained on disjoint train sets. However, there are important caveats: (1) Our Agreement Property only holds on on-distribution, and degrades on off-distribution inputs. Thus, it not helpful estimate out-of-distributee errors. (2) It only gives an estimate of the average test eттоr, and does not imply pointwise calibration estimates for each sample.
Feature Calibration (Conjecture 1T is also related to the concepts of calibration and multicalibra- tion (Guo et al. 2017, Niculescu-Mize and Caruana 2005; Hébert-Johnson et al., 2018). In our framework, calibration is implied by Feature Calibration for specific set of partitions (determined by level sets of the classifier'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-classification deci- sions and not confidences, and we study only standard learning algorithms which are not given any distinguished set of subgroups/partttoons in advance. Our notion of distributional generalization is also related to the notion of "distributional subgroup overfitting" introduced recently by Yaghini et al. (2019) to study algorithmic fairness. This can be specific family of tests (determined by distinguished subgroups in the population).
studying distributional generalization for
Locality and Manifold Learning. Our intuition for the behaviors in this work that they arise due to some form of "locality" of the trained classifiers, in an appropriate space. This intuition is present in various forms the literature, for example: the so-called called 'manifold hypothesis." that natural data lie on a cow-dimensional manifold (e.g. Narayanan and Mitter (2010); [Sharma and Kaplan (2020), as well works on local stiffness of the loss landscape (Fort et al., (201)). and works showing that overparameterized neural networks can learn hidden low-dimensional structure in high- nigh-dimensional settings (Gerace et al., 2020; Bach 2017] Chizat and Bach 2020). It is open to more formally understand connections between work and the above.
B EXPERIMENTAL DETAILS
Here we describe general background, and experimental details common to all sections. Then we provide section-speciio details below.
B. DATASETS
We consider the image datasets CIFAR- and CIFAR-100 (Krizhevsky et al. 2009), MNIST (LeCun ct al. 1998), Fashion-MNIST (Xiao et al. 2017). CelebA (Liu al. 2015). and ImageNet (Rus- sakovsky et al. 2015). We normalize images to E [0, 1 1xx
We also consider tabular datasets from the UCI repository Dua and Graff (2017). For UCI data, we consider the 121 classification tasks as standardized in Fernández- Fernández-Delgadoo et al. (2014). Some of these tasks have very few examples, so we restrict to the 92 classification tasks from Fernnnezz-Delaal 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 Ho 1995): selecting a split based on a random vd subset of d features, split- ting based Gini impurity, and growing trees until all leafs have single plc. This as implemented by Scikit-leam Pedregosa et al.] (20IT) defaults with RandommFrrettllasss fier fier (n (n_esti in_estimatoosss bootstrap=Falsee
2001
15

---

Under review as a conference paper at ICLR 2021
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 and Recht (2008);
Belkin et al. (2018b); Shankar et al. (2020). We solve the following convex problem for training:
argmin ||K - vl12 + Xa Ka
DERNXM
where Ki = (( 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 sinalg.solly
VVrtanen et al. 2020). We use the
explicit form of all kernels involved. That is, we not use random-feature approximations (Rahimi and Recht 2008 though we expect they would behave similarly.
The kernel predictions on test points are then given by
Ia (x) = Σ ask(o,, x))
(8)
SE[N]
fa (z) == argmax (x))
(9)
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
For kernel SVM, we use the implementation provided by Scikit-learn (Pedregosa et al. 2011 sklearn. svm SVC with precomputed kernel, for inverse-regularizztoon parameter C 2 (larger C' corresponds smaller regularization).
Types of Kernels. We use the following kernel functions k Rd x Rd + Rzo-
Gaussian Kernel (RBF): k(z1, 2,) exp(- || -0.1-:118
27
Laplace Kernel: 2z) 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..
Pashion-MNIST 0.1 for RBF kernel. o 1.0 for Laplace kernel.
CIFAR-10: Myrtle10 Kernel from Shankar 2020), and 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 BatchNormalization layer and ReLU activation function.
Nede We the standard WedeRessNet-28- described in Zagoruyko and Komodakis (001)). Our code is based on this repository
ResNet50:
We standard ResNet-50 from the PyTorc library Paszke et al. 2017
16

---

Under review as a conference paper at ICLR 2021
MLP
18
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 the hyperparameters used train the above networks are given in T
17

---

Under review as a conference paper at ICLR 2021
C FEATURE CALIBRATION: APPENDIX
C.I A GUIDE TO READING THE PLOTS
All the experiments in support [expeccire[[expeeemmmett Section Jani the Introduction) involve various quantities which we enumaerate here
1. Inputs æ: Each experiment involves inputs from standard dataset like CIFAR-IO 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) 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, constructed binary task as in 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. L(x)), which depends on our dataset and task and common across train and test, and (f(x), L(x)) which depends on the interpolating classifiers outputs on the fest set. Since y, L(x) and fz) 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(z)) (f)),, [xx) for all training inputs We also refer to (f(x), ((r)) the test density,
as we measure this only on the test set.
C.2 EXPERIMENT I
Experimental details: We now provide further details for Experiment T We first construct a dataset from CIFAR- 10 that obeys the joint density (y. L(x)) shown in Figure I left panel. We then train a WideResNNet225 10 (WRN-28- 10) on this modified dataset to zero training error. The network is trained with the hyperparameters deseribed in Table We then observe the joint density (f(x), L(x)) on the test images and find that the two joint densities are close as shown Figure
We now consider a modification of this experiment as follows:
Experiment 2. Consider the following distribution over images and binary labels Sample I as a uniformly random CIFAR-10 10 image, and sample the label as p(y|z) Bernoulli CIFAR Class (x) /10). That is, the CIFAR-10 class of x is k 10, then the label is with probability (k/10) and O otherwise. Figure 5 shows this joint distribution of (I, v). As before, train a WideResNet to O training error on this distribution.
In this experiment too, observe that the train and test joint densities are close shown in Figure 5
Now, we repeat the same experiment, but with an MLP instead of WRN-28-10 10. The training procedure is described in Table [ This MLP has error on 37% on the original CIFAR-10 dataset.
Since this MIP has poor accuracy on the original CIFAR-10 classification task, it does not form a distinguishable partition for it. As result, the train and test joint densities (Figure () do not match as well as they did for WRN-28-10.
C.3 CONSTANT PARTITION
Consider the ditilly-distinnnushaalle constant feature T.(x) 0. Then, Conjecture 1 states that the marginal distribution of class labels for any interpolating classifier f f(x) is close to the true marginals p(y). That is, irrespective of the classifier's 's test accuracy, it outputs the "right" proportion of class labels the test set, even when there is strong class imbalance.
To show this, we construct a dataset based on CIFAR-10 that has glass-imbalance. For class k E (0...9), sample (k + 1) 500 images from that class. This will give dataset where classes will have marginal distribution p(y = f) x l + 1 for classes & E [10], as shown in Figure We do this both for the training and the test set, to keep the distribution D fixed.
18

---

Under review as a conference paper at ICLR 2021
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 _ The top panel shows the joint density of labels on the train set: (CIFAR.C)) class ( The bottom panels shows the joint density of classifier predictions the test set: (CIFAR_C) ass (x), f(x)). Distributional Generalization claims that these two joint densities are close.
Figure 5: Distributional Generalization in Experiment 2
involved Experiment
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-
bird
cat
deer
dog
frog
horse
ship
truck
mobile
Figure 6: Joint density of (y, Class(x)), top, and (f(x), Class(xr)), bottom, for test samples (v; y)
from Experiment 2 for an MLP.
We then train variety of classifiers (MLPs, Kernels, 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 is then close to the class balance on the train set, irrespective of the classifier error. Full experimental details and results are described in Appendix Note that l-nearest-neighhors classifier would have this property.
C.4 CLASS PARTITION
C.4.1 NEURAL NETWORKS AND CIFAR-10
We now provide experiments in support of Conjecture I when the class itself is distinguishable partition. WRN-28-1 10 achieves an error 4% on CIFAR-10. Hence, the original labels in CIFAR-10 10 form distinguishable partition for this dataset. To demonstrate that Conjecture [ holds, we consider different structured label noise on the CIFAR- dataset. To do so, we apply a variety of confusion matrices the data. That is, for confusion matrix C 10 10 matrix, the element Gj
19

---

Under review as a conference paper at ICLR 2021
A
True (D)
B ResNet18. Test Error 0.09%
C
MLP. Test Emrrr 37%
D
RBF kemel 41%
9.20
0:15
0.25
0.35
0:15
60.10
0.010
60.10
0.100
0.05
0.45
0.06
9.0b
0.00
0.00
5.00
Class Label
Class Label
Class Label
Cless Label
The CIFAR-10 train and test sets are class-rebalanced according (A). Interpolating classifiers are trained on the train set, and we plot the class-bal blas-balaacce of their outputs on the test set. This roughly matches the class-balenc, of the train set, even for poorly-genene generaliznn classifiers.
Figure 7: Feature Calibration for Constant Partition L:
gives the joint density that a randomly sampled image had original label j. but is flipped to class i. For no noise, this would be an identity matrix.
We begin by simple confusion matrix where we flip only one class 0 + 1 with varying probability Figure ?? shows one such confusion matrix for p 0.4. We then train WideResNNet-28-10 to zero train error on this dataset. We use the hyperparameters described in B.2 We find that the classifier outputs on the test set closely track the confusion matrix that was applied to the distribution. Figure shows that this is independent of the value of p and continues to hold for [0, 1].
A
B
CIFAR-10 Imistabeling class O-w with probability p)
WidehesNNet228 10
0:00
0:00
3:93
0.00
1:00
8.20
KIDE
D:ED
0:3
0.10
BAS
3.93
6:5
0.00
10:0
8:00
0.8
0:00
3:3
0.10
660
0.00
6.C4
9.00
0.00
0.00
0.00
8:00
399
0.00
0:00
0.00
0.4
0:00
0:00 0:0
8:00
0.00
8:0
9.99
0:00
<.0e c:c0
0:00
0:00
8:00
Bayes Optimal
Distributional
646
444
393
0:90
660
645
3:30
0.00
6.16
6:0
501
0:39
000
5:2
091
0:00
6.10
0.0
Gereralzation
Wi MideReeNeet
Nolse probabilty
Figure 8: Feature Calibration with original classes on CIFAR-10: We train a WRN-28- 10 on the CIFAR-10 dataset where we mislabel class 0 + 1 with probability p. (A): Joint density of the distinguishable features (the original CIFAR- 10 class) and the classification task labels on the train set for noise probability p- 0.4. (B): Joint density of the original CIFAR- 10 classes L and the network outputs fx) 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 10 on it and report the test confusion matrix. The resulting train and test densities are shown in Figure [ same sparsity pattern.
As expected, the train and test confusion matrices are close, and share the
C.4.2 DECISION TREES
Figure 10 shows 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.
20

---

Under review as a conference paper at ICLR 2021
Train Set
Test Set
BMC
K.L.
CAS
DAE
6/22
6ICE
SIC
BICE
CC4
CAR
RUDS
CAE
6ICE
CCCE
DEC
RICE
RICK
f(x)
666
CUSS
CAE
KICS
FICE
DEC
RICE
CUS
DCE
CIE
OCC
6:00
CCE
DOC
C.0
0CC
DEB
DEC
E.E
E.0
Figure 9: Feature Calibration with random confusion matrix on CIFAR-10: Left: Joint density of labels y and original class L on the train set. Right: Joint density of classifier predictions f(x) and original class L on the test set, for a WideResNee28- 10 trained to interpolation. These two joint densities close, predicted by Conjecture 1
Similar results hold for decision trees; here we show experiments on two UCI tasks: wine and mushroom.
The wine task is 3-way classification problem: to identify the cultivar of a given wine (out of 3 cultivars), given 13 physical attributes describing the wine. Figure II shows an analogous experiment with label noise taking class 1 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 12 shows an analogous experiment with label noise flipping class to class 1.
0,0
0.1
0.2
0.3
0.4
0.5
Train Set
0.00
0:00
B:24
0:34
10:00
3.00
0.24
0.00
3:24
0.00
1024
125
0.01
10.4
0.20
0.24
0.75
3:20
0.52
0.20
01000
0.00
0.00
1.335
11000
0.20
0.00)
0.00
0.22
0.0
0.1
0.3
0.4
0.5
Test Set
0:18
3:00
0.04
0:18
0.02
04
0:18
0.32
0.00
0.17
0.02
0.06
0.19
0.02
0.00
0.17
0.02
0.04
0.03
3.05
0.42
0.03
0.04
0.30
0.04
0.34
0.54
0.04
0.02
0.30
0.02
0.03
0.27
0.02
0.08
0.25
Figure 10: Feature Calibration for Decision trees on UCI (molecular biology). We add label noise that takes class 2 to class 1 with probability p E [0, 0.5]. The top row shows the confusion matrix of the true class L(x) vs. the label on the train set, for varying levels of noise p. The bottom row shows the corresponding confusion matrices of the classifier predictions, f(xx the test set, which closely matches the train set, as predicted by Conjecture
C.5 MULTIPLE FEATURES
Conjecture 1 states that the network should be automatically calibrated for all distinguishable features, without any explicit labels for them. To verify this, we use the CelebA dataset (Liu et al. 2015). containing images with various labelled binary attributes per-image ("male", "blond hair", etc). Some of these attributes form a distinguishable feature for ResNet50 as they are learnable to high accuracy (Jahandideh et al. 2018). We pick one of hard attributes the target classification task. We train ResNet-50 to predict the attribute { (Attractive, Not Attractive). We choose this attribute because a ResNet-50 performs poorly this task (test error 20%) and has good class balance. We choose
21

---

Under review as a conference paper at ICLR 2021
p
0.0
0.1
0.2
0.3
0.4
Train Set
0.00
0.00
0:04
0.00
26.1
0.00
3.40
0.00
0.00
0.28
0.00
0.00
0.32
0.00
0.00
0.31
0.00
0.00
0.22
0.00
6.00
0:21
9.00
3.30
0:04
27
0.00
0.06
0.00
0.27
0:00
0.27
0,0
=
0.1
0.2
0.3
0.4
0.5
Test Set
0.32
0:05
0:00
0.00
0.39
0.00
0.00
0:30
07
0/02
2.30
0.00
0.02
0.20
0.00
0:02
0.20
5.00
0:00
0.11
0:00
Figure 11: Decision trees UCI (wine). We add label noise that takes class 1 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.
p
0.0
= 0.1
0.2
= 0.3
0.4
0.5
Train Set
6:57
8:80
21/6
3:00
0:42
8:00
0:30
D.00
0:31
0.00
0:20
0.
0.16
0.21
0:48
0.26
p 0.0
== 0.1
p= 0.2
p.=
0.3
0.4
p
Set
0.62
0.00
0.48
2.30
0:41
0.00
0.35
0.00
0.30
0.00
0.26
0.00
0.00
0.48
0.00
2.48
0.11
0.46
0.17
0.48
0.22
0.48
0.25
0.48
Figure 12: Decision trees on UCI (mushroom). We add label noise that takes class 0 to class 1 with probability p E [0, 0.5). Each column shows the and train confusion matrices for given p. Note that this decision trees achieve high accuracy on this task with no label noise (leftmost column).
an attribute with poor generalization because the conjecture would hold trivially for if the network generalizes well. We initialize the network with pretrained ResNet-50 from the PyTorch library Paszke et al. (017)) and use the hyperparameters described Section B.2 to train on this attribute. We then check the train/test joint density with various other attributes like Male, Wearing Lipstick etc. Note that the network is not given any label information for these additional attributes, but is calibrated with respect to them. That is, the network says 30% of images that have 'heavy makeup' will be classified as 'Atrractive, even if the network makes mistakes on which particular inputs chooses do In this setting, the label distribution is deterministic, and not directly dependent the distinguishable features, unlike the experiments considered before. Yet, as we see in Figure [3] the classifier outputs are correctly calibrated for each attribute. Loosely, this be viewed as the network performing INN classification in metric space that is well separated for each of these distinguishable features.
C.6 COARSE PARTITION
We consider cases where the original classes do not form 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.
To verify this, we consider a division of the CIFAR- 10 classes into Objects fairplane, automobile, ship, truck) Animals (cat, deer, dog, frog). An ML.P trained this problem has low error (~ 8%),
22

---

Under review as a conference paper at ICLR 2021
Wearing Lipstick
Heavy Makeup
Blond Hair
Eye- Glasses
Male
0.38
0.11
0.42
0.07
0.48
0.01
0.18
0.30
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.39
0.07
0.44
0.01
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
1
0
1
0
0
1
0
1
Figure 13: Feature Calibration for multiple features on CelebA: We train ResNet-50 to perform binary classification task on 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.
Model
AlexNet
ResNet18
ResNet50
BagNet8
BagNet32
ImageNet Accuracy
0.565
0.698
0.761
0.464
0.667
Accuracy on dogs
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/not-terrier) 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 are calibrated with respect to dogs: All classifiers predict terrier for roughly 22% of all dogs (last row), though they may mistake which specific dogs are terriers.
but the same network performs poorly on the full dataset (~> 37% error). Hence, Object vs Animals forms distinguishable partition with MIPss. In Figure 14a we show the results of training an MILP on the original CIFAR- 10 classes. We see that the network mostly classifies objects objects and animals as animals, even when it might mislabel dog for cat.
We perform similar experiment for the RBF kernel on Fashion-MNIST with partition (clothing, shoe, bag), in Figure 14b
ImageNet experiment. In Table 2 we provide results of the terrier experiment in the body, for various ImageNet classifiers. We use publicly available pretrained ImageNet models from this repository and use their evaluations the ImageNet test set.
C.7 QUANTITATIVE PREDICTIONS: TV DISTANCE VS
We now test the quantitative predictions made by Conjecture T This conjecture states that the TV-distance between the joint distributions (L(x), f(z)) and (L(z),
y) is at most s, where the
стror of the training procedure in learning L (see Definition
f())
S
To test this, we consider binary task similar to Experiment where (Ship, Plane) are labeled as class 0 and (Cat, Dog) are labeled as class 1. We then add add noise 0.3 fraction of cats to mislabel them as class O. Then, we train a convolutional network to interpolation on this task. this experiment, (Cat, Dog, Plane, Ship) form distinguishable features. To vary the error on these
23

---

Under review as a conference paper at ICLR 2021
Predicted
9-/10
612
0.1
6.c
21
0.22
6.0
0.11
0.11
dee
0.14
dkg
69g
627
0.
(a) CIFARIO MLP
(b) Bushion-MNIST. RBF
Figure 14: Coarse partitions as distinguishable features: We consider a setting where the original classes are not distinguishable, but the superset the classes are.
n 100
250
500
0.5
TV distance
10000
20000
50000
0.3
0.2
0.1
0.2
0.3
0.4
0.5
0.6
Figure 15: TV distance between (L(x), f(x)) and (L(z), y) vs. for the distinguishable features
distinguishable features systematically, we train a networks to classify (Cat, Dog, Plane, Ship) with changing number samples. Networks with fewer samples have larger since they are worse at classifying the distinguishable features. Then, we use the same setup and number of samples respectively to train networks on the binary task and measure the TV-distance between (L(x), f(x)) and (L(x), u) in this task. The results are shown in Figure 15 As predicted, the TV distance is upper bounded by E.
C.8 DISCUSSION: PROPER SCORING RULES
Here we distinguish the estimation occurs. If E(p, y) is a strictly-pron propper scoring ruld on predicted distribution P E A())) and sample y E y; then the population minimizer of E ([F(), y) is exactly the conditional density F(x) pz)]z). That is,
estimation of Conjecture from another setting where density
p(12)
argmin F:X-
E [((F(x).v))
(#.8)~p
See Gneiting and Raftery (007)) for survey of proper scoring rules.
24

---

Under review as a conference paper at ICLR 2021
This suggests that in the limit of sarre--appcity network and very large data (to approximate population quantities), training neural nets with cross-entropy loss on samples (z, y) will yield a good density estimate of p(y|z) at the softmax layer. However, this is not what is happening in experiments. First, our experiments consider the hard-thresholded classifier, i.e. the argmax of the softmax layer. If the softmax layer itself was close to p(y]ær), then the classifier itself will be close argmax, p(y(x)) that is, close to the optimal classifier. However, this is not the case (since the classifiers make significant errors). Second, observe Conjecture [ evenn in settings where we train with non-proper scoring rules (e.g. kernel regression, where the classifier does not output a probability).
D AGREEMENT PROPERTY: APPENDIX
D.1 EXPERIMENTAL DETAILS
For ResNets CIFAR-I0 and CIFAR-100, use the following training procedure. For S 25000, we sample two disjoint train sets S1, S2 of size n from the 50K total train samples. Then we train two ResNet18s f1, fo S2 respectively. We optimize using SGD the cross-entropy loss, with batch size 128, using learning rate schedule 0.1 for 40 50000 epochs, then 0.01 for 20 50000 epochs. That is, scale up the number of epoches for smaller train sizes, to keep the number of gradient steps constant. We also early-stop optimization when the train loss reaches < 0.0001, to save computational time. For experiments with autaentgmennainnn, we use horizontal flips and RandomCrop (32, padding=4) 4) We estimate test accuracy and agreement probability on the CIFAR-10/100 test sets.
For the kernel experiments on -NISST, we repeat the same procedure: we sample two disjoint train sets from all the train samples, train kernel regressors, and evaluate their agreement on the test set. Each point on the figures correspond to one trial.
For UCI, some UCI tasks have very few examples, and so here we consider only the classification tasks from "vernández-Delgatdd et al. (2014) which have at least 200 total examples. For each task, we randomly partition all the examples into a 40%-44%%-20% split for disjoint train sets, and I test set (20%). We then train two interpolating decision trees, and compare their performance on the test set. Decision trees are trained using a growth rule from Random Forests (Breiman 2001 Ho 1995): select- ing a split based on a random v subset of d features, splitting based on Gini impurity, and growing trees until all leafs have single sample. This is implemented by Scikit-learn Pedregosa al. (011) defaults with RandomFooo wwweeeoooreeetooo www.meowststttasseiceciacasaaaee fier en_est dessimmatorss]. bootstrap=False))
D.2 ADDITIONAL PLOTS
Figure 16 shows the Agreement Property for the Myrtle Kernel on CIFAR-10, and Figure 17 shows the RBF and Laplace kernels on Fashion-MNIST.
Figure 18a shows interpolating decision trees on 90 classification UCI tasks. We plot the means of agreement probability and test accuracy when averaged over 100 random partitions for each task, and also include the corresponding plot for single trial. Error bars UCI tasks show 95% Clopper-Pearre Pearson confidence intervals in estimating population quantities.
D.3 POTENTIAL MECHANISMS
We now consider, and refute, several potential mechanisms which could explain the experimental results of Conjecture ( ("Agreement Property"). In this section, we would like to understand the distribution of f + Train(D"), in order to evaluate several proposed mechanisms. Technically, sampling from this distribution requires training a classifier on a fresh train set. Since we do not have infinite samples for CIFAR- 10, we construct empirical estimates by training an ensemble of classifiers on random subsets of CIFAR-10 10. Then, to approximate a sample f +- Train(D"), we simply sample from our ensemble f {f().
25

---

Under review as a conference paper at ICLR 2021
Agreement: Myrtie10 Kernel, CIFAR-10
y=x
F=50
Agreement Probabiltty
0.8
2-250
F- 500
0.6
C- 2000
10000
T-25000
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Test Accuracy
Figure 16: Agreement Property for Myrtle Kernel on CIFAR-10.
Agreement: RBT Kernel 0.11)
Agreement:: RDT Kernel (or=))
Agreement: Laplace Kernel to= 1)
1.0
Y-4
1.0
-..
V--4
1.0
V-x
[1400
ne30
Dw30
0.9
0.9
0.9
n-100
Probobiilty
Agreemeent Probrbality
0.8
1=1000
m=2000
m=2000
2-2000
n-2000
B-2000
1=2000
0.7
n=3000
n-2000
Agreament
0.6
Agreementt
0.6
0.6
10002
0.5
0.5
0.5
0.4
03 0.4 0.5 0.5 0.7 088 099
1.0
0.3 0.4
0.5 0.6 0.7 08 0.9 1.0
0.3 0.4
0.5 0.5 0.7 088 0.9 1.0 lest Accuracy
lest Accuracy
lest Accuracy
(a) RBF 0.1
(b) RBF a
(c) Laplace Kernel
Figure 17: Agreement Property for Kernels on Fashion-MNIST. For two classifiers trained disjoint train sets, the probability they agree with each other (on the test set) is close to their test accuracy.
D.3.1 BIMODAL SAMPLES
A simple model which would exhibit the Agreement Property is the following: Suppose test samples come in two types: "easy" or "hard." All classifiers get "easy" samples correct, but they output uniformly random class on "hard" samples. That is, for fixed x, consider the probability that freshly-trained classifier gets x correct. "Easy" samples are such that
For E EASY:
/+-rain(D"")) [f(x) = y(x)] =
Pr
while "hard" samples have uniform distribution on output classes [K]:
For HARD:
Pr Te-Train(D") [f(x)= =
Vi Vi [K]
Notice that for HARD samples x, a classifier /1 agrees with the true label with exactly the same probability that agrees with an independent classifier fz (because both fi. fz are uniformly random on 2). Thus, the agreement property (Conjecture (2 holds exactly under this model. However, this strict decomposition of samples into "easy" and "hard" does not appear to be the case in the experiments, as shown below.
Figure shows a histogram of
h(x) == (t-TrainDD.)
Pr [f(x) = vl (()))
26

---

Under review as a conference paper at ICLR 2021
Agreement: Decision
Agreement: Decision Trees
ymx
1.0
Agreement Probability
0.8
Agreement Probability
0.8
0.6
0.6
0.4
0.2
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.8
1.0
Test Accuracy
Test Accuracy
Mean of 100 trials.
(b) Single trial.
Figure 18: Agreement Property on UCL. For two decision trees trained on disjoint train sets, the probability they agree with each other (on the test set) is close to their test accuracy. Each point corresponds one UCI task, and error bars show 95% Clopper-Pearson confidence intervals in estimating population quantities.
for test samples x in CIFAR-10, 10, where f a ResNet18 trained on 5000 samples This quantity can be interpreted the "casiness" of given test sample (I, y) to certain classifier family.
the EASY/HARD bimodal model were true, we would expect the distribution of h(x) to be concentrated on h(z) = 1 (easy samples) and h(x) 0.1 (hard samples). But this is not the case in Figure 19 and thus the bimodal model does not explain the Agreement Property.
Histogram Correctness
CIFAR-10[SK]
Histogram
3500
1200
3000
Number of Text Samples
2500
Nam Text Samples
2009
600
1500
3000
500
200
00
0.2
04
-0.6
-0.2
Pr][is]
Mix
Figure 19: Histogram of sample-hardnesser
Figure 20: Pointwise agreement histogram.
D.3.2 POINTWISE AGREEMENT
We could more generally posit that Conjecture is true because the Agreement Property holds pointwise for most test samples x:
w.h.p. for (x. v) D:
Pr fi fieinain(D")) [f(()) = y)
Pr
(f(()) = f2(x)) (10)
fi Trainn f2t Trs-Tri
However, we find (perhaps surprisingly) that this is not the case. To see why this is surprising, observe that Conjecture implies that the agreement probability is close to test accuracy, in expectation
We estimate this probability over the empirical ensemble f +- (fi).. where each fi is classifier trained random 5k-subset of CIFAR-10. We train 100 classifiers this ensemble.
27

---

Under review as a conference paper at ICLR 2021
the test sample and the classifiers f1. +- Train(D"):
Pr
[f((.) = vl
Pr 12(z))=((1)
(Conjecture
fiJo
(
(a.))D
[((()) y
[1(((z)) J2(x)
(11)
hith a.yD
Swapping the order of expectation, this implies
[1f((x)
())((t)----111 -)))) f2()))] 0
(12)
f1.f2
(1.a)
Now, may expect that this means (x, y) 0 pointwise, for most test samples (zz, y). But this is not the case. turns out that (x, y) takes on significantly positive and negative values, and these effects "cancel out" in expectation
the distribution, yield Conjecture
For example, we compute M (x. y) for the Myrtle10 kernel on CIFAR-10 with 1000 train samples.
The agreement probability is within 0.8% of the test error (as in Figure 16 and so
E [M (z, y)] x 0.008
2. However, (x, y) is not pointwise close to 0. E.g,
E 2
MMx v)1l ~ 0.133
Figure 20 plots the distribution of (x, 3). We see that some samples (ær, 3) have high agreement probability, and some low, and these happen balance in expectation to yield the accuracy.
Interestingly, 1-nearest neighbors can satisfy the agreement property of Claim 2 without satisfying
the "pointwise agreement" of Equation 10 It remains an open problem understand the mechanisms behind the Agreement Property.
E NEAREST-NEIGHBOR PROOFS
E. FEATURE CALIBRATION PROPERTY
Recall that L being an (s, NN, D, distinguishabe partition means that nearest-neit -eighhss works to classify L(x) from x:
Proof of Theorem /
Pr (a. (=((x) 2.0D
(x)= 21-
(13)
Now, we have
S-D" (NNN)) (x), (x), (())) SWDD ((n,
(14)
2,y0D
N. K.yD
RC (10) L(f)))
SNDD
(15)
NN 2y~D
R3 ((0) L(
(16)
Line (15) is by distinguishability, since Pr[L(x) + L( < s. And Line (6) is by the regularity condition.
'ee estimate the expectation in M(z, v) by training ensemble of 5000 pairs of classifiers (f1, f2), each
pair on disjoint train samples.
28

---

Under review as a conference paper at ICLR 2021
E.2 AGREEMENT PROPERTY
Theorem 2 (Agreement Property). For given distribution D on (z, v). and given number of train samples N. suppose NN satisfies the following regularity condition: If we sample two independent train sets S1, S2. then the following two "couplings" are statistically close:
NNs SD"D" S2mDD
R8 {(NNs, (x))) STND
( S2~DD
(17)
m;ERS1
2~D
The LHS is simply random test point Vy along with its nearest-neighbor in the train set. The RHS produces an (zt, x2) by sampling two independent train sets, sampling test point x D, and producing the nearest-neighbor of x in S₁ and Sn respectively.
Then:
Pr NN (z) y) m5 SND (2.4)~D
Pr (NN(() (I) NN (x)]
(18)
SiND"
SamDD
(.,,5)/D
Proof. Let the LHS of Equation 17 be denoted distribution P over X' X. And let Q be the RHS of Equation (17). Let D, denote the marginal distribution on æ of D, and let p(yla) (r) denote the conditional distribution with respect to D.
The proof follows by considering the sampling of train set S in the following order: first, sample all the z-marginals: sample test point D. and train points Sz D Then compute the nearest- neighbors 2 +- NNs, (z:. And finally, sample the values y of all the points involved. according to the densities p(y)
29

---

Under review as a conference paper at ICLR 2021
Pr SwDn (r.y)~D
(x)
E Snpn (a.y)~D
[ (x) (x)= = =
(19)
E S
E y-plyla (>
[1 vHl
(20)
"
Me NN (xr)
T(r,5)
[T(x, 3)]
(21)
SpnDa " B>D= 5t NN,N (x)
(a (211,
E
(P: LHS Equation
R88
E
T(11
(Q: RHS of Equation
(2)
E
[2(
(22)
SInDa
SpnD
a>D
8 NN (x)
00 NN (x)
E
E
[1 = SaHl
(23)
S
S2
8 1.--NN NN5 (Ø)
8 NNs, (x)
1 N (z) NN 9. (x)
(24)
S
S2 (#.0)>D
Pr SINDa SynD" (m.y)~D
NN S, (z) = [ (z)
(25)
as desired.
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).
30

---

Under review as a conference paper at ICLR 2021
Train,
Test, 0.01
9/00
0/33
0:30
6:00
540
0/00
6100
8:00
0:0
300
0.00
0-31
0.00
0:33
0.03
D100
0.93
0.00
00:3
0.91
0.00
0.00
0:37
3.90
6:22
D:00
0:00
6:00
DC
0.00
2:0
DC
GOLL
0.00
0.23
0.9
0.0%
200
6:77
0.01
0.99
6:03
0:00
0:00
600
6:00
1:22
2.00
8:2
0.03
300
9:0
6.29
0.22
1200
300
0.7L
6:00
0.00
0.02
0:
300
000
0000
0.00
0:31
9.0
8:00
010
00
0.00
3:00
922
0:3
0.99
3.00
A30
0:33
0.95
1190
3/00
0:33
6/00
0100
6/00
0:00
85
3:08
DC
D91
399
0000
0.91
Test.
0.1
3/00
0:33
0:93
010
0100
1100
3:00
0.93
300
0.00
0.0
0.00
0:93
0.9
8:00
D40
0.00
8:00
800
0.00
3:0
0.00
0.00
0:33
0.90
0.00
0.00
0:00
0:39
0.03
6:00
0:00
D400
0.00
6:00
0.00
000
3:0
20
0:00
3.00
0/00
0:33
0.00
0.00
3.00
0.30
0.99
0000
5.00
GOL
0.00
0.32
0.99
G-0000
2-000
300
0.33
0:0
0:00
000
0000
5.00
2:0
858
U33
OAD
GUO
7- A193 3101
0100
0:10
0.00
0.52
3:0
919
319
0.10
8:09
n993
390
1193
0:0
5.55
Train
10
Test
10
0.00
022
0:30
0:00
8:00
0:00
0:02
6:00
00
+30
200
8:C
0.03
0.00
0.32
0.93
000
200
0VD
R:00
C:00
D:00
R:00
4:22
2.00
204
320
3000
0.20
GUP
0:00
0.00
0:00
DED
5:00
0:30
0.00
3.00
0:00
0.33
0:00
6:00
0.00
6:00
6:02
DC
5:00
2:0
DC
300
0.20
0.92
1190
0:33
3:00
RSB
1192
0.93
DIO
2003
5:
2:0
3193
0100
0.33
Train,
1.00
Test,
1:00
5:00
0:00
0:30
0.90
8:00
0.60
0.00
6:00
8:00
5:0
5:88
8:00
0.90
3.00
0.00
0:33
0.99
0.00
D00
0:20
0:30
0:00
6:00
0:00
0.00
0:22
6:00
2:7
3:0
8:C
0.00
3000
0.00
0.31
0.00
0:03
3:00
0:00
0:00
D
0.20
0.93
0.00
0.00
0:99
6.8
6:02
DO
6:00
9:50
0.00
0.99
3100
RUD
DC
3
REJ
DC
GUR
JUY
BITR
0:
0:5
S
S1S
HINE
200
0000
0,30
U00
D000
422
219
300
000
01,32
Figure 21: Distributional Generalization. Train (left) and test (right) confusion matrices for kernel SVM on MNIST with random sparse label noise. Each row corrosponds to value of inverse- regularization parameter C. All rows are trained on the same (noisy) train set.
31

---

Under review as a conference paper at ICLR 2021
Step 2000
Step 20000
Step 40000
Step 76000
Train Set
1X0
Test Set
1600
Figure 22: 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.
32


Reviews:
[{"review_id": "vN3RJYOK_G", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "> Summarize what the paper claims to contribute\n\nThis paper generalizes the classical notion of generalization to the notion that the output of the classifier should be close when applied to the training data and the testing data. Two conjectures were made to predict the behavior of the distributional generalization for a few models and data. The first conjecture, Feature Calibration Conjecture, asserts that the distribution of the outputs are similar up to “distinguishable features”. The second conjecture, Agreement Conjecture, asserts that test accuracy matches the classification stability for interpolated classifiers. A number of experiments surrounding these conjectures were conducted to illustrate the Distributional Generalization\n\n> List strong and weak points of the paper. Be as comprehensive as possible.\n+ Great idea to look into distribution of the output beyond the error. I think this is long overdue and this paper has a lot of potential.\n+ Comprehensive numerical studies which show some interesting findings.\n- Many vague and ambiguous notations which make the paper hard to read.\n- Barely any theoretical justification. \n- \"Too many\" ideas. I would suggest the authors to divide the paper into 3 papers and dig deeper in each topic. \n\n> Provide supporting arguments for your recommendation.\n\n1. Notation. While the display on the bottom of page 2 is supposed to be an informal conjecture, it may be too informal. Does x∈TestSet indicate a distribution or a set? What does ≡ mean here? It was mentioned that the joint distribution of X and Y is D, and D^n denote n iid samples from D. But is D^n a sample of training data points, or a distribution? Later on it was mentioned that \"S ∼ D^n\" which does not make sense if D^n is a sample. \n2. There are only two theoretical results in the paper with rigorous proofs. But they are established for nearest neighbor classifier only and some assumptions are imposed which warrants the results straightforwardly. However, most of the conjectures are made for many classifiers beyond nearest neighbor. \n3. Indistinguishability and interpolated classifier: in the Indistinguishability meta-conjecture on page 2, the second equality is clearly due to interpolated classifier. I wonder if the closeness indicated in the first approximation (between trainset and testset) is a merit of the interpolated classifier, or the general good generalization performance of a classifier. It is not clear to me why interpolated classifiers will induce this closeness.\n4. The role of L. From what I can see, this intermediate feature L is introduced because \\mathcal{X} can be a large high-dimensional space which can make visualization or quantification of the closeness difficult. This function L is introduced so that it is easier to see how (L(x), f(x)) is distributed. For constant partition (L(x) = 0), the distributional generalization reduces to the marginal distribution of \"f(x)\". In my opinion, if a classifier is true generalizable, the distribution of (x, f(x)) itself, without L, should be the same between the test and training domains. From the statement of Theorem 1, it seems to me that  Conjecture 1 holds for nearest neighbor BECAUSE some distinguishable features exist, which may already be a strong assumption. So strong that the very existence of the distinguishable features warrants the generalizability. Unfortunately because there are only conjectures and no rigorous proofs, this part is still not clear to me.\n\n> Ask questions you would like answered by the authors to help you clarify your understanding of the paper and provide the additional evidence you need to be confident in your assessment. \n\nWhile the numerical studies have convinced me that distributional generalization is really a thing here, I am not sure that I am that impressed. After all, the precision was only two decimal points. Can the total-variation distance be calculated? Is there a counterexample in which one classifier does have classical generalizability but not distributional generalizability? Focus on a narrower set of topics but dig deeper may go a long way here.  \n\n> Minor comments\n\nPage 3: “do we this same procedure” is a typo\nPage 4: how is “learnable” defined?\nPage 5: f←Train F (D^n) is not defined, esp. given that it is unclear if D^n is a distribution or a set. Should D^n be replaced by S?\nPage 5: Indistinguishably is a typo\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "oVm6p6iuAA3", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new notion of generalization called distributional generalization which states that the outputs of the classifier for train and test are close as distributions not just their corresponding accuracy numbers. They propose conjectures about their the distributional closeness that they expect and how it depends on the model, number of data points and the algorithm. This paper gives experiments to support their conjectures for different model classes including neural networks, kernel methods and decision trees.\n\nI find the notion of distributional generalization interesting. The first experiment of this paper is that the label noise introduced in the training set in one subgroup of a particular class is also localized in the same subgroup in the test set although the classifier does not have any explicit information about the subgroups which is interesting. The paper formally states that the distribution of train and test outcomes are similar in distribution with respect to tests which themselves can learned by that model class with the current number of samples.\n\nI recommend accepting this paper because the notion of distributional generalization that this paper introduces is both interesting and surprising. Moreover, this paper has shown that it holds widely across different interpolating classifiers like decision trees, neural networks and kernel methods.\n\nThe paper includes an extensive set of experiments that are easy to follow.\n\nOne concern is as itself mentioned in the paper that this work does not talk about what conditions on the distribution, algorithm and the model class are necessary for this conjecture to hold either empirically or theoretically and the conjecture is not precisely defined. Any insights on this part would be good to include. \n\nAnother concern is that although this is an interesting observation, the paper does not talk about why and how studying this form of generalization would be useful for understanding interpolating classifiers and generalization in general. \n\nQuestions:\n1) The authors suspect locality to be the underlying reason behind distributional generalization and find this observation to be true for kernel methods also. Do the authors know if there is some work on the locality aspects of kernel methods arguing that some particular kernels are more local than others and how this relates to the observations in this paper?\n2) Regarding the agreement property in section 4, I find it a little surprising that the conjecture says that the correlation and the accuracy are the same. Does this relate to the number of classes present?", "extra_scores": {}, "extra_text": {}}, {"review_id": "_623CXN_77", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an extended notion of generalization. The new proposed notion asks that for a family of tests $T: X \\times Y → [0,1]$, $T(x, f(x))$  will be similar for train/test examples. The paper proposes three interesting conjectures that are related to distributional generalization. The paper proves Conjecture 1 for nearest-neighbor classifiers. The paper also gives empirical evidence supporting their conjectures.\n\nI think this is a nice contribution. It raises some new questions on generalization, and points to some interesting properties that interpolating classifiers satisfy (at least empirically) that deserve to be studied in more detail. In particular, Conjecture 1 seems to suggest that there is a form of hierarchical learning that interpolating classifiers are doing without being told to explicitly do so. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9YWrlrqZGX9", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a new notion of \"distributional generalization\" as a tool to quantify the difference between the outputs from training and testing data sets using a certain machine learning algorithm. The authors formulate two conjectures for the so-called \"Interpolating classifiers\": the Feature Calibration Conjecture and Agreement Conjecture. The conjectures are supported numerically by some real data experiments and are proven for the 1-nearest-neighbor classifier under some technical conditions. \n\nStrengths: \n1. Two conjectures are interesting and have the potential to explain some unexplained phenomena for some existing machine learning algorithms.\n2. Numerical experiments are quite thorough, using different data sets and different machine learning algorithms.\n\nWeaknesses:\n1. The justifications of the conjectures are almost purely empirical (except in the 1-nearest-neighbor (1-N-N) classifier case). However, the 1-NN classifier is just a toy example that has limited use in machine learning literature. In fact, one even does not need to train the 1-NN classifier given a training data set. This is probably why it is easy to analyze 1-NN under the considered setting.\n2. While observations from data experiments are interesting and I enjoyed reading them, the paper fails to directly demonstrate how these observations can be used to improve performances or our understandings of existing algorithms. For example, how Conjecture 2 is useful? can we use it to evaluate the uncertainty (or confidence interval) of the test accuracy?\nHow can we find distinguishable features in Conjecture 1 in practice? using trees?\n\nConclusion:\nAlthough I find the proposed conjectures interesting and may have potential values, the current formulation, and justification for these conjectures are a bit too superficial and loose. It is difficult for me to envision a scenario where these conjectures can make a meaningful impact.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a notion of distributional generalization, which aims at characterizing aspects of underlying distribution that are learned by a trained predictor. Authors make several interesting conjectures and support them with empirical evidence. Reviewers agreed on the novelty of the ideas; however, the work seems to be preliminary in its current form. Unfortunately, I cannot recommend acceptance at this time. 
Decision: Reject