Distributional Generalization: Characterizing Classifiers Beyond Test Error
Year: 2021

Abstract:
We present a new set of empirical properties of interpolating classifiers, includ1 ing neural networks, kernel machines and decision trees. Informally, the output 2 distribution of an interpolating classifier matches the distribution of true labels, 3 when conditioned on certain subgroups of the input space. For example, if we 4 mislabel 30% of dogs as cats in the train set of CIFAR-10, then a ResNet trained 5 to interpolation will in fact mislabel roughly 30% of dogs as cats on the test set 6 as well, while leaving other classes unaffected. These behaviors are not captured 7 by classical generalization, which would only consider the average error over 8 the inputs, and not where these errors occur. We introduce and experimentally 9 validate a formal conjecture that specifies the subgroups for which we expect this 10 distributional closeness. Further, we show that these properties can be seen as a 11 new form of generalization, which advances our understanding of the implicit bias 12 of interpolating methods. 13

We present a new set of empirical properties of interpolating classifiers, includ-1 ing neural networks, kernel machines and decision trees. Informally, the output2 distribution of an interpolating classifier matches the distribution of true labels,3 when conditioned on certain subgroups of the input space. For example, if we4 mislabel 30% of dogs as cats in the train set of CIFAR-10, then a ResNet trained5 to interpolation will in fact mislabel roughly 30% of dogs as cats on the test set6 as well, while leaving other classes unaffected. These behaviors are not captured7 by classical generalization, which would only consider the average error over8 the inputs, and not where these errors occur. We introduce and experimentally9 validate a formal conjecture that specifies the subgroups for which we expect this10 distributional closeness. Further, we show that these properties can be seen as a11 new form of generalization, which advances our understanding of the implicit bias12 of interpolating methods.13
1 Introduction14
In learning theory, when we study how well a classifier “generalizes”, we usually consider a single15 metric – its test error [59]. However, there could be many different classifiers with the same test error16 that differ substantially in, say, the subgroups of inputs on which they make errors or in the features17 they use to attain this performance. Reducing classifiers to a single number misses these rich aspects18 of their behavior. In this work, we propose formally studying the entire joint distribution of classifier19 inputs and outputs. That is, the distribution (x, f(x)) for samples from the distribution x ⇠ D for a20 classifier f(x). This distribution reveals many structural properties of the classifier beyond test error21 (such as where the errors occur). In fact, we discover new behaviors of modern classifiers that can22 only be understood in this framework. As an example, consider the following experiment (Figure 1).23 Experiment 1. Consider a binary classification version of CIFAR-10, where CIFAR-10 images x24 have binary labels Animal/Object. Take 50K samples from this distribution as a train set, but25 apply the following label noise: flip the label of cats to Object with probability 30%. Now train26 a WideResNet f to 0 train error on this train set. How does the trained classifier behave on test27 samples? Options below:28
(1) The test error is low across all classes, since there is only 3% overall label noise in the train set.29
(2) Test error is “spread” across the animal class. After all, the classifier is not explicitly told what a30 cat or a dog is, just that they are all animals.31
(3) The classifier misclassifies roughly 30% of test cats as “objects”, but all other animals are largely32 unaffected.33
The reality is closest to option (3) as shown in Figure 1. The left panel shows the joint density of34 train inputs x with train labels Object/Animal. Since the classifier is interpolating, the classifier35
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
outputs on the train set are identical to the left panel. The right panel shows the classifier predictions36 f(x) on test inputs x.37
• In Section 3, we introduce a formal “Feature Calibration” conjecture, which unifies our74 experimental observations. Roughly, Feature Calibration says that the outputs of classifiers75 match the statistics of their training distribution when conditioned on certain subgroups.76
• In Section 4, we experimentally stress test our Feature Calibration conjecture across various77 settings in machine learning, including neural networks, kernel machines, and decision trees.78 This highlights the universality of our results across machine learning.79
• In Section 5, we relate our results to classical generalization, by defining a new notion of80 Distributional Generalization which subsumes both classical generalization and our new81 conjectures.82
• Finally, in Section 5.2 we informally discuss how Distributional Generalization can be83 applied even for non-interpolating methods.84
Our results, thus, extend our understanding of the implicit bias of interpolating methods, and introduce85 a new type of generalization exhibited across many methods in machine learning.86
1.3 Related Work and Significance87
Our work has connections to, and implications for many existing research programs in deep learning.88
Implicit Bias and Overparameterization. There has been a long line of recent work towards89 understanding overparameterized and interpolating methods, since these pose challenges for classical90 theories of generalization (e.g. Belkin et al. [8, 9, 10], Breiman [11], Gunasekar et al. [25], Liang91 and Rakhlin [36], Nakkiran et al. [43], Schapire et al. [58], Soudry et al. [62], Zhang et al. [71]). The92 “implicit bias” program here aims to answer: Among all models with 0 train error, which model is93 actually produced by SGD? Most existing work seeks to characterize the exact implicit bias of models94 under certain (sometimes strong) assumptions on the model, training method or the data distribution.95 In contrast, our conjecture applies across many different interpolating models (from neural nets to96 decision trees) as they would be used in practice, and thus form a sort of “universal implicit bias” of97 these methods. Moreover, our results place constraints on potential future theories of implicit bias,98 and guide us towards theories that better capture practice.99
Benign Overfitting. Most prior works on interpolating classifiers attempt to explain why training100 to interpolation “does not harm” the the model. This has been dubbed “benign overfitting” [7] and101 “harmless interpolation” [40], reflecting the widely-held belief that interpolation does not harm the102 decision boundary of classifiers. In contrast, we find that interpolation actually does “harm” classifiers,103 in predictable ways: fitting the label noise on the train set causes similar noise to be reproduced at104 test time. Our results thus indicate that interpolation can significantly affect the decision boundary of105 classifiers, and should not be considered a purely “benign” effect.106
Classical Generalization and Scaling Limits. Our framework of Distributional Generalization is107 insightful even to study classical generalization, since it reveals much more about models than just108 their test error. For example, statistical learning theory attempts to understand if and when models109 will asymptotically converge to Bayes optimal classifiers, in the limit of large data (“asymptotic110 consistency” [59, 65]). In deep learning, there are at least two distinct ways to scale model and data111 to infinity together: the underparameterized scaling limit, where data-size model-size always, and112 the overparameterized scaling limit, where data-size⌧ model-size always. The underparameterized113 scaling limit is well-understood: when data is essentially infinite, neural networks will converge to114 the Bayes-optimal classifier (provided the model-size is large enough, and the optimization is run115 for long enough, with enough noise to escape local minima). On the other hand, our work suggests116 that in the overparameterized scaling limit, models will not converge to the Bayes-optimal classifier.117 Specifically, our Feature Calibration Conjecture implies that in the limit of large data, interpolating118 models will approach a sampler from the distribution. That is, the limiting model f will be such that119 the output f(x) is a sample from p(y|x), as opposed to the Bayes-optimal f⇤(x) = argmax
y p(y|x).120 This claim— that overparameterized models do not converge to Bayes-optimal classifiers— is unique121 to our work as far as we know, and highlights the broad implications of our results.122
Locality and Manifold Learning. Our intuition for the behaviors in this work is that they arise due to123 some form of “locality” of the trained classifiers, in an appropriate embedding space. For example, the124 behavior observed in Experiment 1 would be consistent with that of a 1-Nearest-Neighbor classifier125 in a embedding that separates the CIFAR-10 classes well. This intuition that classifiers learn good126
embeddings is present in various forms in the literature, for example: the so-called called “manifold127 hypothesis,” that natural data lie on a low-dimensional manifold [44, 61], as well as works on local128 stiffness of the loss landscape [19], and works showing that overparameterized neural networks can129 learn hidden low-dimensional structure in high-dimensional settings [6, 15, 21]. It is open to more130 formally understand connections between our work and the above.131
Other Related Works. Our conjectures also describe neural networks under label noise, which has132 been empirically and theoretically studied in the past [9, 14, 45, 54, 63, 71, 72], though not formally133 characterized. A full discussion of related works is in Appendix A.134
2 Preliminaries135
Notation. We consider joint distributions D on x 2 X and discrete y 2 Y = [k]. Let S =136 {(xi, yi)}ni=1 ⇠ Dn denote a train set of n iid samples from D. Let A denote the training procedure137 (including architecture and training algorithm for neural networks), and let f TrainA(S) denote138 training a classifier f on train-set S using procedure A. We consider classifiers which output hard139 decisions f : X ! Y . Let NNS(x) = xi denote the nearest-neighbor to x in train-set S, with140 respect to a distance metric d. Our theorems will apply to any distance metric, and so we leave141 this unspecified. Let NN(y)
S (x) denote the nearest-neighbor estimator itself, that is, NN(y) S (x) := yi142 where xi = NNS(x).143
Experimental Setup. Briefly, we train all classifiers to interpolation (to 0 train error). Neural144 networks (MLPs and ResNets [29]) are trained with SGD. Interpolating decision trees are trained145 using the growth rule from Random Forests [12]. For kernel classification, we consider kernel146 regression on one-hot labels and kernel SVM, with small or 0 of regularization (which is often147 optimal [60]). Full experimental details are provided in Appendix B.148
Distributional Closeness. We consider the following notion of closeness for two probability dis-149 tributions: For two distributions P,Q over X ⇥ Y , let a “test” (or “distinguisher”) be a function150 T : X ⇥ Y ! [0, 1] which accepts a sample from either distribution, and is intended to classify the151 sample as either from distribution P or Q. For any set C ✓ {T : X ⇥ Y ! [0, 1]} of tests, we say152 distributions P and Q are “"-indistinguishable up to C-tests” if they are close with respect to all tests153 in class C. That is,154
P ⇡C " Q () sup
T2C E (x,y)⇠P [T (x, y)] E (x,y)⇠Q [T (x, y)]  " (2)
Total-Variation distance is equivalent to closeness in all tests, i.e. C = {T : X ⇥ Y ! [0, 1]}, but we155 consider closeness for restricted families of tests C. P ⇡" Q denotes "-closeness in TV-distance.156
3 Feature Calibration Conjecture157
3.1 Distributions of Interest158
We first define three key distributions that we will use in stating our formal conjecture. For a given159 data distribution D over X ⇥ Y and training procedure TrainA, we consider the following three160 distributions over X ⇥ Y:161
1. Source D: (x, y) where x, y ⇠ D.162 2. Train Dtr: (xtr, f(xtr)) where S ⇠ Dn, f TrainA(S), (xtr, ytr) ⇠ S163
3. Test Dte: (x, f(x)) where S ⇠ Dn, f TrainA(S), x, y ⇠ D164
The source distribution D is simply the original distribution. To sample once from the Train Dis-165 tribution Dtr, we first sample a train set S ⇠ Dn, train a classifier f on it, then output (xtr, f(xtr))166 for a random train point xtr 2 S. That is, Dtr is the distribution of input and outputs of a trained167 classifier f on its train set. To sample once from the Test Distribution Dte, we do this same proce-168 dure, but output (x, f(x)) for a random test point x. That is, the Dte is the distribution of input and169 outputs of a trained classifier f at test time. The only difference between the Train Distribution and170
Test Distribution is that the point x is sampled from the train set or the test set, respectively.2 For171 interpolating classifiers, f(xtr) = ytr on the train set, and so the Source and Train distributions are172 equivalent: D ⌘ Dtr. (Note that these definitions, crucially, involve randomness from sampling the173 train set, training the classifier, and sampling a test point).174
3.2 Feature Calibration175
We now formally describe the Feature Calibration Conjecture. At a high level, we argue that the distributions Dte and D are statistically close for interpolating classifiers if we first “coarsen” the domain of x by some partition L : X ! [M ] in to M parts. That is, for certain partitions L, the following distributions are statistically close:
(L(x), f(x))x⇠D ⇡" (L(x), y)x⇠D We think of L as defining subgroups over the domain— for example, L(x) 2 {dog, cat, horse. . .}.176 Then, the above statistical closeness is essentially equivalent to requiring that for all subgroups177 ` 2 [M ], the conditional distribution of classifier output on the subgroup—p(f(x)|L(x) = `) — is178 close to the true conditional distribution: p(y|L(x) = `).179 The crux of our conjecture lies in defining exactly which subgroups L satisfy this distributional180 closeness, and quantifying the " approximation. This is subtle, since it must depend on almost all181 parameters of the problem. For example, consider a modification to Experiment 1, where we use182 a fully-connected network (MLP) instead of a ResNet. An MLP cannot properly distinguish cats183 even when it is actually provided the real CIFAR-10 labels, and so (informally) it has no hope of184 behaving differently on cats in the setting of Experiment 1, where the cats are not labeled explicitly185 (See Figure C.2 for results with MLPs). Similarly, if we train the ResNet with very few samples from186 the distribution, the network will be unable to recognize cats. Thus, the allowable partitions must187 depend on the classifier family and the training method, including the number of samples.188
We conjecture that allowable partitions are those which can themselves be learnt to good test189 performance with an identical training procedure, but trained with the labels of the partition L instead190 of y. To formalize this, we define a distinguishable feature: a partition of the domain X that is191 learnable for a given training procedure. Thus, in Experiment 1, the partition into CIFAR-10 classes192 would be a distinguishable feature for ResNets (trained with SGD with 50K or more samples), but193 not for MLPs. The definition below depends on the training procedure A, the data distribution D,194 number of train samples n, and an approximation parameter " (which we think of as " ⇡ 0).195 Definition 1 ((",A,D, n)-Distinguishable Feature). For a distribution D over X ⇥ Y , number of samples n, training procedure A, and small " 0, an (",A,D, n)-distinguishable feature is a partition L : X ! [M ] of the domain X into M parts, such that training a model using A on n samples labeled by L works to classify L with high test accuracy. Precisely, L is a (",A,D, n)distinguishable feature if:
Pr S={(xi,L(xi)}x1,...,xn⇠D
f TrainA(S); x⇠D
[f(x) = L(x)] 1 "
This definition depends only on the marginal distribution of D on x, and not on the label distribution196 pD(y|x). To recap, this definition is meant to capture a labeling of the domain X that is learnable for197 a given training procedure A. It must depend on the architecture used by A and number of samples198 n, since more powerful classifiers can distinguish more features. Note that there could be many199 distinguishable features for a given setting (",A,D, n) — including features not implied by the class200 label such as the presence of grass in a CIFAR-10 image. Our main conjecture follows.201 Conjecture 1 (Feature Calibration). For all natural distributions D, number of samples n, interpo-202 lating training procedures A, and " 0, the following distributions are statistically close for all203 (",A,D, n)-distinguishable features L:204
(L(x), f(x)) f TrainA(Dn); x,y⇠D ⇡" (L(x), y) x,y⇠D
(3)
or equivalently:205 (L(x), by) x,by⇠Dte ⇡" (L(x), y) x,y⇠D
(4)
2Technically, these definitions require training a fresh classifier for each sample, using independent train sets. For practical reasons most of our experiments train a single classifier f and evaluate it on the entire train/test set.
This claims that the TV distance between the LHS and RHS of Equation (4) is at most ", where " is the206 error of the distinguishable feature (in Definition 1). We claim that this holds for all distinguishable207 features L “automatically” – we simply train a classifier, without specifying any particular partition.208 The formal statements of Definition 1 and Conjecture 1 may seem somewhat arbitrary, involving209 many quantifiers over (",A,D, n). However, we believe these statements are natural: In addition210 to extensive experimental evidence in Section 4, we also prove that Conjecture 1 is formally true as211 stated for 1-Nearest-Neighbor classifiers in Theorem 1.212
3.3 Feature Calibration for 1-Nearest-Neighbors213
Here we prove that the 1-Nearest-Neighbor classifier formally satisfies Conjecture 1, under mild214 assumptions. We view this theorem as support for our (somewhat involved) formalism of Conjecture 1.215 Indeed, without Theorem 1 below, it is unclear if our statement of Conjecture 1 can ever be satisfied by216 any classifier, or if it is simply too strong to be true. This theorem applies generically to a wide class217 of distributions; the only assumption is a weak regularity condition: sampling the nearest-neighbor218 train point to a random test point should yield (close to) a uniformly random test point.219 Theorem 1. Let D be a distribution over X ⇥ Y , and let n 2 N be the number of train samples.220 Assume the following regularity condition holds: Sampling the nearest-neighbor train point to a221 random test point yields (close to) a uniformly random test point. That is, suppose that for some222 small 0, the distributions: {NNS(x)}S⇠Dn
x⇠D ⇡ {x}x⇠D. Then, Conjecture 1 holds. That is,223 for all (",NN,D, n)-distinguishable partitions L, the following distributions are statistically close:224
{(y, L(x))}x,y⇠D ⇡"+ {(NN(y)S (x), L(x)}S⇠Dn x,y⇠D
(5)
The proof of Theorem 1 is straightforward, and provided in Appendix D – but this strong property of225 nearest-neighbors was not know before, to our knowledge.226
3.4 Limitations: Natural Distributions227
Technically, Conjecture 1 is not fully specified, since it does not specify exactly which classifiers or228 distributions obey the conjecture. We do not claim that all classifiers and distributions satisfy our229 conjectures. Nevertheless, we claim our conjectures hold in all “natural” settings, which informally230 means settings with real data and classifiers that are actually used in practice. The problem of231 understanding what separates “natural distributions” from artificial ones is not unique to our work,232 and lies at the heart of deep learning theory. Many theoretical works handle this by considering233 simplified distributional assumptions (e.g. smoothness, well-separatedness, gaussianity), which are234 mathematically tractable, but untested in practice [2, 4, 35]. In contrast, we do not make untestable235 mathematical assumptions. This benefit of realism comes at the cost of mathematical formalism.236 We hope that as the theory of deep learning evolves, we will better understand how to formalize the237 notion of “natural” in our conjectures.238
4 Experiments: Feature Calibration239
We now give empirical evidence for our conjecture in a variety of settings in machine learning,240 including neural networks, kernel machines, and decision trees. In each experiment, we consider241 a feature that is (verifiably) distinguishable, and then test our Feature Calibration conjecture for242 this feature. Each of the experimental settings below highlights a different aspect of interpolating243 classifiers, which may be of independent interest. Selected experiments are summarized here, with244 full details and further experiments in Appendix C.245
Constant Partition: Consider the trivially-distinguishable constant feature: L(x) = 0 everywhere.246 For this feature, Conjecture 1 reduces to the statement that the marginal distribution of class labels for247 any interpolating classifier is close to the true marginals p(y). To test this, we construct a variant of248 CIFAR-10 with class-imbalance and train classifiers with varying levels of test errors to interpolation249 on it. As shown in Figure 2B, the marginals of the classifier outputs are close to the true marginals,250 even for a classifier that only achieves 37% test error.251
Coarse Partition: Consider AlexNet trained on ILSVRC-2012 ImageNet [56], a 1000-class image252 classification problem with 116 varieties of dogs. The network achieves only 56.5% accuracy253
on the test set. But it will at least classify most dogs as dogs (with 98.4% accuracy), making254 L(x) 2 {dog, not-dog} a distinguishable feature. Moreover, as predicted by Conjecture 1, the255 network is calibrated with respect to dogs: 22.4% of all dogs in ImageNet are Terriers, and indeed256 the network classifies 20.9% of all dogs as Terriers (though it has 9% error on which specific dogs257 it classifies as Terriers). See Appendix Table 2 for details, and related experiments on ResNets and258 kernels in Appendix C.259
Class Partition: We now consider settings where the class labels are themselves distinguishable260 features (eg: CIFAR-10 classes are distinguishable by ResNets). Here our conjecture predicts the261 behavior of interpolating classifiers under structured label noise. As an example, we generate a262 random spare confusion matrix and apply this to the labels of CIFAR-10 as shown in Figure 2A.263 We find that a WideResNet trained to interpolation outputs the same confusion matrix on the test264 set as well (Figure 2B). Now, to test that this phenomenon is indeed robust to the level of noise, we265 mislabel class 0! 1 with probability p in the CIFAR-10 train set for varying levels of p. We then266 observe bp, the fraction of samples mislabeled by this network from 0! 1 in the test set (Figure 3A267 shows p versus bp). The Bayes optimal classifier for this distribution behaves as a step function (in268 red), and a classifier that obeys Conjecture 1 exactly would follow the diagonal (in green). The actual269 experiment (in blue) is close to the behavior predicted by Conjecture 1. This experiment shows a270 contrast with classical learning theory. While most existing theory focuses on whether classifiers271 converge to the Bayes optimal solution, we show that interpolating classifiers behave “optimally” in a272 different sense: they match the distribution of their train set. We discuss this further in Section 5. See273 Appendix C.4 for more experiments, including other classifiers such as Decisions Trees.274
Multiple features: Conjecture 1 states that the network should be automatically calibrated for275 all distinguishable features, without any explicit labels for them. To do this, we use the CelebA276 dataset [37], containing images with many binary attributes per image. (“male”, “blond hair”, etc).277
We train a ResNet-50 to classify one of the hard attributes (accuracy 80%) and confirm that the278 Feature Calibration holds for all the other attributes (Figure 3) that are themselves distinguishable.279
Quantitative predictions: We now test the quantitative predictions made by Conjecture 1. This280 conjecture states that the TV-distance between the joint distributions (L(x), f(x)) and (L(x), y)281 is at most ", where " is the error of the training procedure in learning L (see Definition 1). To282 test this, we consider binary task similar to Experiment 1 where (Ship, Plane) are labeled as283 class 0 and (Cat, Dog) are labeled as class 1, with p = 0.3 fraction of cats mislabeled to class 0.284 Then, we train a convolutional network to interpolation on this task. To vary the error " on these285 distinguishable features systematically, we train networks with varying number of train samples.286 Networks with fewer samples have larger " since they are worse at classifying the distinguishable287 features of (Ship,Plane,Cat,Dog). Then, we use the same setup to train networks on the binary288 task and measure the TV-distance between (L(x), f(x)) and (L(x), y) in this task. The results are289 shown in Figure 3C. As predicted, the TV distance on the binary task is upper bounded by " error on290 the 4-way classification task.291
5 Distributional Generalization292
In order to relate our results to the classical theory of generalization, we now propose a formal293 notion of “Distributional Generalization”, which subsumes both Feature Calibration and classical294 generalization. In fact, we will also give preliminary evidence that this new notion can apply even for295 non-interpolating methods, unlike Feature Calibration.296
A trained model f obeys classical generalization (with respect to test error) if its error on the train set297 is close to its error on the test distribution. We first rewrite this using our definitions below.298
Classical Generalization (informal): Let f be a trained classifier. Then f generalizes if:299 E
x⇠TrainSet by f(x) [ {by 6= y(x)}] ⇡ E x⇠TestSet by f(x) [ {by 6= y(x)}] (6)
Above, y(x) is the true class of x and by is the predicted class. The LHS of Equation 6 is the train300 error of f , and the RHS is the test error. Using our definitions of Dtr,Dte from Section 3.1, and301 defining Terr(x, by) := {by 6= y(x)}, we can write Equation 6 equivalently:302
E x,by⇠Dtr [Terr(x, by)] ⇡ E x,by⇠Dte [Terr(x, by)] (7)
That is, classical generalization states that a certain function (Terr) has similar expectations on both the303 Train Distribution Dtr and Test Distribution Dte. We can now introduce Distributional Generalization,304 which is a property of trained classifiers. It is parameterized by a set of bounded functions (“tests”):305 T ✓ {T : X ⇥ Y ! [0, 1]}.306 Distributional Generalization: Let f be a trained classifier. Then f satisfies Distributional Gener-307 alization with respect to tests T if:308
8T 2 T : E x,by⇠Dtr [T (x, by)] ⇡ E x,by⇠Dte [T (x, by)] (8) 309
This states that the train and test distribution have similar expectations for all functions in the family310 T , which we can write as: Dtr ⇡T Dte. For the singleton set T = {Terr}, this is equivalent to311 classical generalization, but it may hold for much larger sets T . This definition of Distributional312 Generalization, like the definition of classical generalization, is just defining an object— not stating313 when or how it is satisfied. Feature Calibration turns this into a concrete conjecture.314
5.1 Feature Calibration as Distributional Generalization315
We can write our Feature Calibration Conjecture as a special case of Distributional Generalization,316 for a certain family of tests T . Informally, for a given setting, the family T is all tests which take317 input (x, y), but only depend on x via a distinguishable feature (Definition 1). For example, a test318 of the form T (x, y) = g(L(x), y) where L is a distinguishable feature, and g is arbitrary. Formally,319 for a given problem setting, suppose L is the set of (",A,D, n)-distinguishable features. Then320 Conjecture 1 states that 8L 2 L : (L(x), f(x)) ⇡" (L(x), y). This is equivalent to the statement321
Dte ⇡T" D (9)
where T is the set of functions T := {T : T (x, y) = g(L(x), y), L 2 L, g : X ⇥ Y ! [0, 1]}.322 For interpolating classifiers, we have D ⌘ Dtr, and so Equation (9) is equivalent to Dte ⇡T" Dtr,323 which is a statement of Distributional Generalization. Since any classifier family will contain a large324 number of distinguishable features, the set L may be very large. Hence, the distributions Dtr and Dte325 can be thought of as being close as distributions.326
5.2 Beyond Interpolating Methods327
The previous sections have focused on interpolating classifiers, which fit their train sets exactly. Here328 we informally discuss how to extend our results beyond interpolating methods. The discussion in this329 section is not as precise as in previous sections, and is only meant to suggest that our abstraction of330 Distributional Generalization can be useful in other settings.331
For non-interpolating classifiers, we may still expect that they behave similarly on their test and332 train sets – that is, Dte ⇡T Dtr for some family of tests T . For example, the following is a possible333 generalization of Feature Calibration to non-interpolating methods.334 Conjecture 2 (Generalized Feature Calibration, informal). For trained classifiers f , the following335 distributions are statistically close for many partitions L of the domain:336
(L(x), by) x,by⇠Dte ⇡ (L(x), by) x,by⇠Dtr
(10)
We leave unspecified the exact set of partitions L for which this holds, since we do not yet understand337 the appropriate notion of “distinguishable feature” in this setting. However, we give experimental338 evidence suggesting some refinement of Conjecture 2 is true. In Figure 4, we apply label noise from339 a random sparse confusion to the CIFAR-10 train set. We then train a single WideResNet28-10, and340 measure its predictions on the train and test sets over increasing train time (SGD steps). The top row341 shows the confusion matrix of predictions f(x) vs true labels L(x) on the train set, and the bottom342 row shows the corresponding confusion matrix on the test set. As the network is trained for longer, it343 fits more of the noise on the train set, and this noise is mirrored almost identically on the test set. Full344 experimental details, and an analogous experiment for kernels, are given in Appendix B.345
6 Conclusion346
This work initiates the study of a new kind of generalization— Distributional Generalization— which347 considers the entire input-output behavior of classifiers, instead of just their test error. We presented348 both new empirical behaviors, and new formal conjectures which characterize these behaviors.349 Roughly, our conjecture states that the outputs of classifiers on the test set are “close in distribution”350 to their outputs on the train set. These results build a deeper understanding of models used in practice,351 and we hope our results inspire further work on distributional generalization in machine learning.352
References353
[1] Madhu S Advani and Andrew M Saxe. High-dimensional dynamics of generalization error in354 neural networks. arXiv preprint arXiv:1710.03667, 2017.355
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overpa-356 rameterized neural networks, going beyond two layers. arXiv preprint arXiv:1811.04918,357 2018.358
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame-359 terized neural networks, going beyond two layers. In Advances in neural information processing360 systems, pages 6158–6169, 2019.361
[4] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op-362 timization and generalization for overparameterized two-layer neural networks. In International363 Conference on Machine Learning, pages 322–332, 2019.364
[5] Susan Athey, Julie Tibshirani, Stefan Wager, et al. Generalized random forests. The Annals of365 Statistics, 47(2):1148–1178, 2019.366
[6] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal367 of Machine Learning Research, 18(1):629–681, 2017.368
[7] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in369 linear regression. Proceedings of the National Academy of Sciences, 2020.370
[8] Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for371 classification and regression rules that interpolate. In Advances in neural information processing372 systems, pages 2300–2311, 2018.373
[9] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to374 understand kernel learning. arXiv preprint arXiv:1802.01396, 2018.375
[10] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-376 learning practice and the classical bias–variance trade-off. Proceedings of the National Academy377 of Sciences, 116(32):15849–15854, 2019.378
[11] Leo Breiman. Reflections after refereeing papers for nips. The Mathematics of Generalization,379 pages 11–15, 1995.380
[12] Leo Breiman. Random forests. Machine learning, 45(1):5–32, 2001.381
[13] Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. Classification and382 regression trees. CRC press, 1984.383
[14] Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers384 in the overparameterized regime. arXiv preprint arXiv:2004.12019, 2020.385
[15] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural386 networks trained with the logistic loss. arXiv preprint arXiv:2002.04486, 2020.387
[16] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.388 ics.uci.edu/ml.389
[17] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds390 for deep (stochastic) neural networks with many more parameters than training data. arXiv391 preprint arXiv:1703.11008, 2017.392
[18] Manuel Fernández-Delgado, Eva Cernadas, Senén Barro, and Dinani Amorim. Do we need393 hundreds of classifiers to solve real world classification problems? The journal of machine394 learning research, 15(1):3133–3181, 2014.395
[19] Stanislav Fort, Paweł Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness:396 A new perspective on generalization in neural networks. arXiv preprint arXiv:1901.09491,397 2019.398
[20] Mario Geiger, Stefano Spigler, Stéphane d’Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio399 Biroli, and Matthieu Wyart. Jamming transition as a paradigm to understand the loss landscape400 of deep neural networks. Physical Review E, 100(1):012115, 2019.401
[21] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová.402 Generalisation error in learning with random features and the hidden manifold model. arXiv403 preprint arXiv:2002.09339, 2020.404
[22] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized405 two-layers neural networks in high dimension. arXiv preprint arXiv:1904.12191, 2019.406
[23] Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation.407 Journal of the American statistical Association, 102(477):359–378, 2007.408
[24] Sebastian Goldt, Madhu S Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborova.409 Generalisation dynamics of online learning in over-parameterised neural networks. arXiv410 preprint arXiv:1901.09085, 2019.411
[25] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias412 in terms of optimization geometry. In International Conference on Machine Learning, pages413 1832–1841. PMLR, 2018.414
[26] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural415 networks. arXiv preprint arXiv:1706.04599, 2017.416
[27] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning:417 data mining, inference, and prediction. Springer Science & Business Media, 2009.418
[28] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-419 dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560, 2019.420
[29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image421 recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition,422 pages 770–778, 2016.423
[30] Úrsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration:424 Calibration for the (computationally-identifiable) masses. In International Conference on425 Machine Learning, pages 1939–1948, 2018.426
[31] Tin Kam Ho. Random decision forests. In Proceedings of 3rd international conference on427 document analysis and recognition, volume 1, pages 278–282. IEEE, 1995.428
[32] Rashidedin Jahandideh, Alireza Tavakoli Targhi, and Maryam Tahmasbi. Physical attribute429 prediction using deep residual neural networks. arXiv preprint arXiv:1812.07857, 2018.430
[33] Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.431
[34] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning432 applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.433
[35] Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial434 large learning rate in training neural networks. arXiv preprint arXiv:1907.04595, 2019.435
[36] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can436 generalize. arXiv preprint arXiv:1808.00387, 2018.437
[37] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the438 wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.439
[38] Song Mei and Andrea Montanari. The generalization error of random features regression:440 Precise asymptotics and double descent curve. arXiv preprint arXiv:1908.05355, 2019.441
[39] Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7442 (Jun):983–999, 2006.443
[40] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless444 interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory,445 2020.446
[41] Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1):447 141–142, 1964.448
[42] Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain449 generalization in deep learning, 2019.450
[43] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.451 Deep double descent: Where bigger models and more data hurt. In International Conference on452 Learning Representations, 2020.453
[44] Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis.454 In Advances in neural information processing systems, pages 1786–1794, 2010.455
[45] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning456 with noisy labels. In Advances in neural information processing systems, pages 1196–1204,457 2013.458
[46] Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste-459 Julien, and Ioannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks.460 arXiv preprint arXiv:1810.08591, 2018.461
[47] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro.462 Towards understanding the role of over-parametrization in generalization of neural networks.463 arXiv preprint arXiv:1805.12076, 2018.464
[48] Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised465 learning. In Proceedings of the 22nd international conference on Machine learning, pages466 625–632, 2005.467
[49] Matthew A Olson and Abraham J Wyner. Making sense of random forest probabilities: a kernel468 perspective. arXiv preprint arXiv:1812.05792, 2018.469
[50] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito,470 Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in471 pytorch. 2017.472
[51] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,473 P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher,474 M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine475 Learning Research, 12:2825–2830, 2011.476
[52] Taylor Pospisil and Ann B Lee. Rfcde: Random forests for conditional density estimation.477 arXiv preprint arXiv:1804.05753, 2018.478
[53] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances479 in neural information processing systems, pages 1177–1184, 2008.480
[54] David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive481 label noise. arXiv preprint arXiv:1705.10694, 2017.482
[55] Jonas Rothfuss, Fabio Ferreira, Simon Walther, and Maxim Ulrich. Conditional density estima-483 tion with neural networks: Best practices and benchmarks. arXiv preprint arXiv:1903.00954,484 2019.485
[56] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng486 Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.487 ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision488 (IJCV), 115(3):211–252, 2015. doi: 10.1007/s11263-015-0816-y.489
[57] Robert E Schapire. Theoretical views of boosting. In European conference on computational490 learning theory, pages 1–10. Springer, 1999.491
[58] Robert E Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee, et al. Boosting the margin: A new492 explanation for the effectiveness of voting methods. The annals of statistics, 26(5):1651–1686,493 1998.494
[59] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to495 algorithms. Cambridge university press, 2014.496
[60] Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Keil, Ludwig Schmidt, Jonathan497 Ragan-Kelley, and Benjamin Recht. Neural kernels without tangents. arXiv preprint498 arXiv:2003.02237, 2020.499
[61] Utkarsh Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold.500 arXiv preprint arXiv:2004.10802, 2020.501
[62] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The502 implicit bias of gradient descent on separable data. The Journal of Machine Learning Research,503 19(1):2822–2878, 2018.504
[63] Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal505 Mohd-Yusof. Combating label noise in deep learning using abstention. arXiv preprint506 arXiv:1905.10964, 2019.507
[64] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David508 Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J.509 van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew510 R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, İlhan Polat, Yu Feng, Eric W.511 Moore, Jake Vand erPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen,512 E. A. Quintero, Charles R Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa,513 Paul van Mulbregt, and SciPy 1. 0 Contributors. SciPy 1.0: Fundamental Algorithms for514 Scientific Computing in Python. Nature Methods, 17:261–272, 2020. doi: https://doi.org/10.515 1038/s41592-019-0686-2.516
[65] Larry Wasserman. All of statistics: a concise course in statistical inference. Springer Science &517 Business Media, 2013.518
[66] Geoffrey S Watson. Smooth regression analysis. Sankhyā: The Indian Journal of Statistics,519 Series A, pages 359–372, 1964.520
[67] Abraham J Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success521 of adaboost and random forests as interpolating classifiers. The Journal of Machine Learning522 Research, 18(1):1558–1590, 2017.523
[68] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for524 benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.525
[69] Mohammad Yaghini, Bogdan Kulynych, and Carmela Troncoso. Disparate vulnerability: On526 the unfairness of privacy attacks against machine learning. arXiv preprint arXiv:1906.00389,527 2019.528
[70] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint529 arXiv:1605.07146, 2016.530
[71] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding531 deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.532
[72] Liu Ziyin, Blair Chen, Ru Wang, Paul Pu Liang, Ruslan Salakhutdinov, Louis-Philippe Morency,533 and Masahito Ueda. Learning not to learn in the presence of noisy labels. arXiv preprint534 arXiv:2002.06541, 2020.535
Checklist536
1. For all authors...537 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s538 contributions and scope? [Yes]539 (b) Did you describe the limitations of your work? [Yes]540 (c) Did you discuss any potential negative societal impacts of your work? [No] This paper541 does not introduce any new methods or applications, and we thus cannot predict any542 near-term societal impact (positive or negative).543
(d) Have you read the ethics review guidelines and ensured that your paper conforms to544 them? [Yes]545
2. If you are including theoretical results...546 (a) Did you state the full set of assumptions of all theoretical results? [Yes]547 (b) Did you include complete proofs of all theoretical results? [Yes]548
3. If you ran experiments...549 (a) Did you include the code, data, and instructions needed to reproduce the main ex-550 perimental results (either in the supplemental material or as a URL)? [No] No new551 methods were introduced, so the code is standard. We fully specify all experimental552 hyperparameters for the sake of reproduction.553
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they554 were chosen)? [Yes]555
(c) Did you report error bars (e.g., with respect to the random seed after running experi-556 ments multiple times)? [No] The experiments we consider all exhibit concentration557 around their expected values, and this is well-known in the community. Notably, we558 only consider supervised learning.559
(d) Did you include the total amount of compute and the type of resources used (e.g., type560 of GPUs, internal cluster, or cloud provider)? [No]561
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...562 (a) If your work uses existing assets, did you cite the creators? [Yes]563 (b) Did you mention the license of the assets? [No]564 (c) Did you include any new assets either in the supplemental material or as a URL? [No]565 (d) Did you discuss whether and how consent was obtained from people whose data you’re566 using/curating? [No]567 (e) Did you discuss whether the data you are using/curating contains personally identifiable568 information or offensive content? [No]569 5. If you used crowdsourcing or conducted research with human subjects...570
(a) Did you include the full text of instructions given to participants and screenshots, if571 applicable? [N/A]572
(b) Did you describe any potential participant risks, with links to Institutional Review573 Board (IRB) approvals, if applicable? [N/A]574
(c) Did you include the estimated hourly wage paid to participants and the total amount575 spent on participant compensation? [N/A]576

Review summaries:
The paper empirically characterizes a fine-grained generalization property of interpolating learning algorithms, and give a conjecture that formalizes the observed phenomenon. Roughly, the paper observes that the generalization properties of an interpolating classifier can be quite distinct for different sample subpopulations with the same label, whenever the label noise imposed on these subpopulations during the training phase is distinct. Authors conjecture that the generalization properties may be uniform only for samples belonging to a smaller "distinguishable" clusters of the input data space.

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

This submission proposes a new type of generalization satisfied by interpolating classifiers (the primary focus), that is different from agreement between test error and train error as in classical learning theory. This type of generalization is largely motivated by empirical evidence across different models (neural networks, kernel regression & svm, decision trees) and theoretically for 1-Nearest Neighbors classification (Theorem 1). More specifically, the submission claims that for certain types of mappings x -> L(x) (termed "distinguishable features" -- i.e. they must be learnable to good test accuracy in the setting under consideration), the joint distribution of (L(x), y) where (x,y) pairs are drawn from the true distribution will be "close" to the joint distribution of (L(x), f(x)) on the test set, where f(x) is the trained model prediction.  List of contributions: --Proposes that interpolating classifiers satisfy "distributional generalization." This is first more specifically formulated as the "Feature Calibration Conjecture" (FCC) in Section 3. A crucial component of this is to identify the types of features L(x) for which the calibration holds (Definition 1); roughly, if the feature is learnable from inputs x to good test accuracy in the setting under consideration (fixed algorithm, data distribution, number of samples, allowable error), then under that same setting calibration will be achieved. The authors prove FCC is true for 1-Nearest neighbors. The Feature Calibration Conjecture is not fully specified, in that there is an assumption of "natural distribution" D (which is such that the conjecture holds in the empirical settings considered).  --Empirical test of the FCC. The types of distinguishable features L considered include (i) the constant partition (calibration then implies the marginal distribution p(y) of the predicted labels matches that of the true label distribution); (ii) a "coarse partition" (L(x) is an "easy" classification task) and calibration holds for fine-grained label subgroups, for instance in Imagenet; (iii) "class partition" (classes that can be learned well from standard datasets, and the true label distribution is a noisy corruption of this); (iv) multiple features. Models investigated include neural networks (WideResnets and MLPs), kernels (standard and high-performing ones), and decision trees.   --A definition for "distributional generalization" which subsumes the definition of feature calibration & classical generalization, and very preliminary evidence that this holds for non-interpolating models (a Wide Resnet model on CIFAR-10 during training).