Distributional Generalization: Characterizing Classifiers Beyond Test Error
Authors: Preetum Nakkiran
Yamini Bansal
Venue: NeurIPS 2021 Submitted (2021)
Keywords: generalization
overparameterization
interpolation
calibration

Abstract: We present a new set of empirical properties of interpolating classifiers, including neural networks, kernel machines and decision trees.
Informally, the output distribution of an interpolating classifier matches
the distribution of true labels, when conditioned on certain subgroups of the input space. For example, if we mislabel 30% of images 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.
These behaviors are not captured by classical generalization, which would only consider the average error over the inputs,
and not *where* these errors occur.
We introduce and experimentally validate a formal conjecture that specifies the subgroups for which we expect this distributional closeness.
Further, we show that these properties can be seen as a new form of generalization, which advances our understanding of the implicit bias of interpolating methods.

15 In learning theory, when we study how well a classifier "generalizes", we usually consider a single 16 metric- - its test error [59] However, there could be many different classifiers with the same test error that differ substantially in, say, the subgroups of inputs which they make errors or in the features 18 they use to attain this performance. Reducing classifiers to single number misses these rich aspects of their behavior. In this work, we propose formally studying the entire joint distribution of classifier Distributional Generalization: Characterizing Classifiers Beyond Test Error
Anonymous Author(s)
Affiliation Address
email
Abstract
We present new set of empirical properties of interpolating classifiers, includ- ing neural networks, kernel machines and decision trees. Informally, the output distribution of an interpolating classifier matches the distribution of true labels, when conditioned on certain subgroups of the input space. For example, if we mislabel 30% of dogs as cats in the train set of CIFAR-10, 10, then a ResNet trained to interpolation will in fact mislabel roughly 30% of dogs cats on the test ser as well, while leaving other classes unaffected. These behaviors are not captured by classical generalization, which would only consider the average error over the inputs, and not where these errors occur. We introduce and experimentally validate formal conjecture that specifies the subgroups for which expect this distributional closeness. Further, we show that these properties can be seen as a new form of generalization, which advances understanding of the implicit bias of interpolating methods.
3
7
11
13
Introduction
14
20 inputs and outputs. That is, the distribution (z, fz)) for samples from the distribution r ~ D for a classifier f(x). This distribution reveals many structural properties of the classifier beyond test error 22 (such as where the errors occur). In fact, we discover new behaviors modern classifiers that can only be understood in this framework. As an example, consider the following experiment (Figure [
24 Experiment 1. Consider a binary classification version of CIFAR-IO, RO0, where CIFAR-I 10 images have binary labels Animal/O0e /Object. Take 50K samples from this distribution apply the following label noise: flip the label of cats to 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:
train set, but
26
28
29 (1) The test error is low across all classes, since there is only 3% overall label noise in the train set.
(2) Test error is "spread" across the animal class. After all, the classifier is not explicitly told what 31 cat or a dog is. just that they are all animals.
32
(3) The classifier misclassifies roughly 30% of test cats as "objects", but all other animals are largely unaffected.
33
34
The reality is closest to option (3) as shown in Figure I The left panel shows the joint density of train inputs æ: with train labels Object/Animal Animal. Since the classifier interpolating, the classifier
35
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

38 outputs on the train set are identical to the left panel. The right panel shows the classifier predictions
37
fz) ) on test inputs x.
Train Set
Test Set
610 0.0
0.3
2,00
5.00 0.00 0.23
Obaez
0:33
6:10
9.10
00.0
5.00
0.42
6093
6:00
0.00
0:23
Trair Sut
160) orgas.
Train classifier f
Adma
A4:
6:00
0.60
0:33
2.10
0.06
0.32
8.10
0.10
0.13
CIPA--10 Labelatt
Figure 1: The setup and result of Experiment] [ The CIFAR- train set is labeled as either Animals or Objects, with label noise affecting only cats. A WideResNet-28- 10 is then trained to 0 train error on this train set, and evaluated on the test set. Full experimental details in Appendix C.2
36 There are several notable things about this experiment. First, the error is localized to cats in the test 39 set as it was in the train set, even though no explicit cat labels were provided. The interpolating model thus sensitive to subgroup-struce the cat class is close to the noise applied on the train set. Thus, the behavior of the classifier on the train set generalizes to the test set in a stronger sense than just average error. Specifically, when conditioned
40
in the distribution. Second, the amount of error on
41
42
43
subgroup (cat), the distribution of the true labels is close that of the classifier outputs. Third, this is not the behavior the Bayes-optimal classifier, which would always output the mokimum--ikellhooe label instead of reproducing the noise in the distribution. The network is thus behaving poorly from the perspective of Bayes-oper cottee--ptimaltty.. but behaving well in a certain distributional sense (which will formalize soon).
44
46
48 Now, consider a seemingly unrelated experimental observation. Take an AlexNet trained on ImageNet, 1000-way classification problem with 116 varieties of dogs. AlexNet only achieves 56.5% test accuracy on ImageNet. However, it at least classifies most dogs as some variety of dog (with 98.4% accuracy), though it may mistake the exact breed. In this work, we show that both of these experiments 52 are examples of the same underlying phenomenon. We empirically show that for an interpolating classifier, its classification outputs are close in distribution the true labels - even when conditioned 54 on many subsets of the domain. For example, Figure I, the distribution of px((x)) = cat) is close to the true label distribution of p(yl x cat). We propose formal conjecture (Feature Calibration), 56 that predicts which subgroups of the domain can be conditioned on for the above distributional closeness to hold.
50
51
These experimental behaviors could not have been captured solely by looking at average test error, 59 as is done in the classical theory of generalization. In fact, they are special cases of new kind of generalization, which we call "Distributional Generalization".
58
60
61
1.1 Distributional Generalization
82 Informally, Distributional Generalization states that the outputs of classifiers on their train sets and test sets are close as distributions (as opposed to close in just error). That is, the following joint distribution are close: (x, fEx))s=Tensee x (r),
63
64
65
The remainder of this paper is devoted to making the above statement precise, and empirically checking its validity real-world tasks. Specifically, we want formally define the notion of approximation (R)) and understand how depends on the problem parameters (the type of classifier, number of train samples, etc). We focus primarily on interpolating methods, where we formalize Equation ( through our Feature Calibration Conjecture.
67
88
89
1.2
Our Contributions and Organization
71 In this work, we discover new empirical properties interpolating classifiers, which are not captured in the classical framework of generalization. We then propose formal conjectures characterize
73 these behaviors.
'These distributions also include the randomness in sampling the train and test sets, and in training the classifier, we define more precisely in Section

---

74
In Section
we introduce a formal "Feature Calibration" conjecture, which unifies our experimental observations. Roughly, Feature Calibration says that the outputs of classifiers match the statistics of their training distribution when conditioned on certain subgroups.
75
76
77
In Section g we experimentally stress test our Feature Calibration conjecture across various settings in machine learning, including neural networks, kernel machines, and decision trees. This highlights the universality of our results across machine learning.
78
79
80
In Section 5]
we relate results to classical generalization, by defining new notion of Distributional Generalization which subsumes both classical generalization and our new conjectures.
81
82
Finally, in Section 2 we informally discuss how Distributional Generalization can be applied even for non non-interpolann interpolaati methods.
84
85
Our results, thus, extend our understanding of the implicit bias of interpolating methods, and introduce a new type of generalization exhibited across many methods in machine learning.
86
87
1.3
Related Work and Significance
Our work has connections to, and implications for many existing research programs in deep learning. 88
89
Implicit Bias and Overparameteriiztton. There has been a long line of recent work towards understanding overparameterized and interpolating methods, since these pose challenges for classical theories of generalization (e.g. Belkin al. B 2 IC Breiman [. Gunasekar et al. [25]. Liang and Rakhlin (36.. Nakkiran et al. 4 Schapire et al. (58), Soudry et al. [2]. Zhang et al.
90
91
92
The
"implicit bias" program here aims to answer: Among all models with 0 train error, which model is actually produced by SGD? Most existing work seeks to characterize the exact implicit bias of models under certain (sometimes strong) assumptions on the model, training method or the data distribution. 96 In contrast, our conjecture applies across many different interpolating models (from neural nets to decision trees) as they would be used in practice, and thus form a sort of "universal implicit bias" of these methods. Moreover, our results place constraints on potential future theories of implicit bias, and guide us towards theories that better capture practice.
93
94
95
97
98
99
100
Benign Overfitting, Most prior works on interpolating classifiers attempt to explain why training to interpolation "does not harm" the the model. This has been dubbed "benign overfitting" 7 and hharmless interpolation" [4), reflecting the widely-held belief that interpolation does not harm the decision boundary of classifiers. In contrast, we find that interpolation actually does "harm" classifiers, in predictable ways: fitting the label noise on the train set causes similar noise to be reproduced at test time. Our results thus indicate that interpolation can significantly affect the decision boundary of classifiers, and should not be considered a purely "benign" effect.
101
102
103
104
105
106
107
Classical Generalization and Scaling Limits. Our framework of Distributional Generalization is insightful even to study classical generalization, since it reveals much more about models than just their test error. For example, statistical learning theory attempts understand if and when models will asymptotically converge to Bayes optimal classifiers, in the limit of large data ("asymptotic In deep learning, there are at least two distinct ways to scale model and data to infinity together: the underparameterized scaling limit, where data-size >> model-size always, and the overparameterized scaling limit, where data-siz < model-size always. The underparameterized scaling limit is well-understood: when data is essentially infinite, neural networks will converge to the Bayes-optimal classifier (provided the model-size large enough, and the optimization is run for long enough, with enough noise to escape local minima). On the other hand, our work suggests that in the overparameterized scaling limit, models will not converge to the Baycs-optimal classifier. Specifically, our Feature Calibration Conjecture implics that in the limit of large data, interpolating models will approach a sampler from the distribution. That is, the limiting model f will be such that the output f(x) is sample from p(y ()) opposed to the Bayes-optimal fz(x) = argmax, p(y(z)) This claim that overparameterized models do not converge to Bayesaoptimal classifiers is unique
108
109
110
111
consistency" " 59 651
112
113
114
115
116
117
119
121
122
to our work far we know, and highlights the broad implications of our results.
123
Locality and Manifold Learning. Our intuition for the behaviors in this work is that they arise due to
124
some form of "locality" of the trained classifiers, in an appropriate embedding space. For example, the behavior observed in Experiment|] woolld be consistent with that of a 1-Nearest-Neighhor classifier in embedding that separates the CIFAR-10 10 classes well. This intuition that classifiers learn good
125
3

---

127
embeddings is present in various forms in the literature, for example: the so-called called "manifold hypothesis," that natural data lie on now-dimensional manifold 4 [1]. as well as works on local stiffness of the loss landscape [19] and works showing that overparameterized neural networks can learn hidden low-dimensional structure high-dimensional settings 15 21].
128
130
open to more formally understand connections between our work and the above.
132
Other Related Works.
Our conjectures also describe neural networks under label noise, which has 54
133
been empirically and theoretically studied in the past p 14
45
63
though not formally
134
characterized. full discussion of related works is in Appendix
135
2
Preliminaries
Notation. We consider joint distributions DD on I E X' and discrete E y = [A:]- Let S = (e), DD denote a train set of n iid samples from D. Let A denote the training procedure (including architecture and training algorithm for neural networks), and let f < T denote training a classifier f on train-set S using procedure A. We consider classifiers which output hard decisions f + V. Let (T) = z; denote the nearest-neighhorr to æ in train-set S, with respect to a distance metric d. Our theorems will apply to any distance metric, and so we leave this unspecified. Let NN()) (a:) denote the nearest-neighbor estimator itself, that is, NN (x) == y: where x; (x).
136
137
138
139
140
141
142
143
144
Experimental Setup. Briefly, we train all classifiers to interpolation (to 0 train error). Neural networks (MLPs and ResNets [29] are trained with SGD. Interpolating decision trees are trained using the growth rule from Random Forests [2] For kernel classification, we consider kernel regression one-hot labels and kernel SVM, with small or 0 of regularization (which is often
146
148
optimal 600). Full experimental details are provided in Appendix
149
Distributional Closeness. We consider the following notion of closeness for two probability dis- tributions: For two distributions P, Q over X' x V, let a "test" (or "distinguisher") be a function T: X' x y + [0, 1] which accepts sample from either distribution, and is intended to classify the sample as either from distribution /' or Q. For any set C S {T': X x y - [0, 1]] of tests, we say distributions P and Q are "e-indistinguishable up C-tests" if they are close with respect to all tests in class C. That is,
150
152
154
P P Q
sup E TEC (a.8)~P
y))
E (z.9)~
(Txx,))
SE
(2)
155
Variatvaii distance equivalent to closeness in all tests, i.e. C (T x (0, 1]}. but we consider closeness for restricted families of tests C. P = Q denotes e-closeness in TV-distance.
Feature Calibration Conjecture
157
158
3.1
Distributions of Interest
We first define three key distributions that will use in stating our formal conjecture. For given data distribution D over X' x y and training procedure Train we consider the following three distributions over X' Y:
160
162
1. Source D: (x, y) where v. ~ D.
163
2. Train Du, (Ztzs (Fw)) where S ~ D". f t- (S), (Dtr, ~ S
3. Test Dra: (zr, fx)) where S ~ D", f A x. y D
185
The source distribution D is simply the original distribution. To sample once from the Train Dis- tribution Dur, we first sample a train set S ~ DD,, train a classifier f on it, then output (ætr. f (xxx) for a random train point Fer S. That is, Drr is the distribution of input and outputs of a trained classifier / on its train set. To sample once from the Test Distribution Du.. we do this same proce- dure, but output (a, [(x) for a random test point æ. That is, the Die the distribution of input and outputs of a trained classifier test time. The only difference between the Train Distribution and
186
167
189

---

171
Test Distribution is that the point is sampled from the train set or the test set, respectively For interpolating classifiers, f f = Yor on the train set, and so the Source and Train distributions are equivalent: D= = Dr. (Note that these definitions, crucially, involve randomness from sampling the train set, training the classifier, and sampling a test point).
172
178
174
175
3.2
Feature Calibration
We now formally describe the Feature Calibration Conjecture. At a high level, we argue that the distributions Dt and D are statistically close for interpolating classifiers if we first "coarsen" the domain of æ by some partition L X' + [M] in to M parts. That is, for certain partitions L, the following distributions statistically close:
(L(z), = (L(x),
176 We think of L as defining subgroups over the domain- for example, L(x) E {dog, cat, horse... J.
Then, the above statistical closeness is essentially equivalent to requiring that for all subgroups
E [M.], the conditional distribution of classifier output on the subgroup subgroup-pp(fr ((ff)) = é) is
178
close to the true conditional distribution: p(y) = ().
180
The crux of our conjecture lies in defining exactly which subgroups satisfy this distributional closeness, and quantifying the approximation. This is subtle, since it must depend on almost all parameters of the problem. For example, consider a modification to Experiment 1, where we use fully-connected network (MLP) instead of ResNet. An MLP cannot properly distinguish cats even when it is actually provided the real CIFAR- 10 labels, and so (informally) it has no hope of behaving differently on cats in the setting of Experiment I, where the cats not labeled explicitly (See Figure C.2 for results with MLPs). Similarly, if we train the ResNet with very few samples from the distribution, the network will be unable to recognize cats. Thus, the allowable partitions must depend on the classifier family and the training method, including the number of samples.
182
184
186
188
189
We conjecture that allowable partitions are those which can themselves be learnt to good test performance with an identical training procedure, but trained with the labels of the partition I. instead of y. To formalize this, we define a distinguishable feature: a partition of the domain X' that is learnable for a given training procedure. Thus, in Experiment [ the partition into CIFAR-I0 classes would be distinguishable feature for ResNets (trained with SGD with 50K more samples), but not for MLPs. The definition below depends on the training procedure A, the data distribution D, number of train samples n, and an approximation parameter (which we think of 2 0).
190
192
194
195
Definition ((e, n,)) Distinguussal Feature). For a distrúbution DD over x Y, number of samples training procedure A. and small > O, an (,,A, n) -distinguusha feature is partition L : X + [M] of the domain into M parts, such that training a model using A on n samples labeled by L works to classify L with high test accuracy. Precisely, L is A,D, distinguishable feature if:
Pr 8=1 Mad Ma - T- a~D
(f(x) (()))=(x)]>>> 2(x))21- 2-
196
This definition depends only on the marginal distribution of D on x, and not on the label distribution PD PD (vlz). To recap. this definition is meant capture labeling of the domain X' that is learnable for a given training procedure A. It must depend on the architecture used by A and number of samples n, since more powerful classifiers can distinguish more features. Note that there could be many
198
199
200
distinguishable features for a given setting (e, A, D, n) including features not implied by the class
201
label such the presence of grass in CIFAR-10 10 image. Our main conjecture follows.
202
Conjecture (Feature Calibration). For all natural distributions D, number of samples n, interpo-
203
lating training procedures A, and 2 0, the following distributions are statistically close for all A, D, D,), distinguishalb featurs L:
204
(L(z), fx:) f ft-Train a (D"); a.y.DD
R
(L(x).))
(3)
2.
205
or equivalently:
(L(x), T D.i
(L(x). a.yDD
(4)
Technically, these definitions require training fresh classifier for each sample, using independent train sets. For practical reasons most of our experiments train single classifier and evaluate on the entire train/test set.
5

---

206
This claims that the TV distance between the LHS and RHS of Equation eτror of the distinguishable feature (in Definition D. We claim that this holds for all distinguishable features I, "automatically" we simply train classifier, without specifying any particular partition. The formal statements of Definition [ and Conjecture I may seem somewhat arbitrary, involving
E is at most E, where is the
207
209
many quantifiers over (e, A. D.,), n). However, we believe these statements are natural: In addition
210
211
to extensive experimental evidence in Section E we also prove that Conjecture Tis iss formally true as
stated for I-Nearest-Neighee classifiers in Theorem L|
213
3.3 Feature Calibration for 1-Nearest-Neighhor
Here we prove that the 1-Nearest-Neighhor classifier formally satísfies Conjecture T under mild assumptions. We view this theorem as support for our (somewhat involved) formalism of Conjecture D Indeed, without Theorem bellow, it unclear if our statement of Conjecture
215
216
I can ever be satisfied by
217
any classifier, or if it is simply too strong to be true. This theorem applies generically to a wide class of distributions; the only assumption is weak regularity condition: sampling the nearest-neighhor train point to random test point should yield (close to) uniformly random test point.
218
219
220
Theorem 1. Let D be a distribution over x YY, and let n N be the number of train samples.
221
Assume the following regularity condition holds: Sampling the nearest-neighte train point to random test point yields (close to) uniformly random test point. That is, suppose that for some
222
223
small 6 2 O, the distributions: {NN ((Ns(())ss)) (z))s>""
=6 {o) Then, Conjecture 7 holds. That is,
znD
for all (e, NN, D, D,n) diiddittinuuisea partitions L, the following distributions are statistically close:
((y)(()))
Ret8
{(NN (x) (x),
S-D= 2,y~D
(5)
225
The proof of Theorem | iis straightforward, and provided Appendix D but this strong property of nearest-neighhors was not know before, to our knowledge.
226
227
3.4
Limitations: Natural Distributions
Technically, Conjecture D is not fully specified, since it does not specify exactly which classifiers distributions obey the conjecture. We do not claim that all classifiers and distributions satisfy our conjectures. Nevertheless, we claim our conjectures hold in all "natural" settings, which informally means settings with real data and classifiers that are actually used in practice. The problem of understanding what separates "natural distributions" from artificial ones is not unique to work, and lies at the heart of deep learning theory. Many theoretical works handle this by considering simplified distributional assumptions (e.g. smoothness, well-separatedness, gaussianity), which are
229
231
232
239
234
235
mathematically tractable, but untested in practice 2 | 65]] In contrast, we do not make untestable mathematical assumptions. This benefit of realism comes at the cost of mathematical formalism.
236
237
We hope that as the theory of deep learning evolves, we will better understand how to formalize the notion of "natural" in our conjectures.
238
4
Experiments: Feature Calibration
239
240
We now give empirical evidence for our conjecture in a variety of settings in machine learning. including neural networks, kernel machines, and decision trees. In each experiment, consider
242 a feature that is (verifiably) distinguishable, and then test our Feature Calibration conjecture for this feature. Each of the experimental settings below highlights different aspect of interpolating classifiers, which may be of independent interest. Selected experiments are summarized here, with full details and further experiments in Appendix
243
244
245
246
Constant Partition: Consider the haaally-isstinuushablle constant feature: L(x) = everywhere. For this feature, Conjecture reduces to the statement that the marginal distribution of class labels for any interpolating classifier is close to the true marginals p(y). To test this, we construct a variant of CIFAR- 10 with class-imbalance and train classifiers with varying levels of test errors to interpolation
248
250
on it. As shown in Figure 2B, the marginals of the classifier outputs are close to the true marginals, even for classifier that only achieves 37% test error.
251
252
Coarse Partition: Consider AlexNet trained on ILSVRC-2012 ImageNet [56], a 1000-class image classification problem with 116 varieties of dogs. The network achieves only 56.5% accuracy

---

Train Get
Test
True 120
S Teak Eoar R.00ss
ML.. Teak Error 31%
5000
Figure 2: Feature Calibration. (A) Random confusion matrix CIFAR-10, with a WideResNet28-- 10 trained to interpolation. Left: Joint density of labels y and original class L on the train set. Right: Joint density of classifier predictions fax:) and original class L on the test set. These two joint densities are close, as predicted by Conjecture IT (B) Constant partition: The CIFAR-10 10 train set is class-rebaland rensaaeeal according to the left panel distribution. The center and right panels show that both ResNets and MLPs have the correct marginal distribution of outputs, even though the MLP has high test error.
WolcBechet 28 - CIFAK 10
Wearing Lipstick
Heavy Makeup
Male
0 100
11 250
O 500
1000
0-
0.38
0:11
0.42
0.07
0.18
0.30
2010
TV O2z0nnC
0.36
20000
50000
Kayos Oytima
f()
0-
0.34
0.11
0.39
0.07
0.18
0.28
Goncrulicziion Wiseitacler
0:41
021
0111
A
hobee probutiity
B
Figure 3: Feature Calibration. (A) CIFAR-10 with p fraction of class 0 + 1 mislabeled on the train set. Plotting observed noise on classifier outputs vs. applied noise on the train set. (B) Multiple feature calibration on CelebA. (C) TV-distance between ( and (L(x), v) for variant of
Experiment [ with error on the distinguishable partitions (z). The error was changed by changing the number of samples n.
254
on the test set. But will at least classify most dogs as dogs (with 98.4% accuracy), making L(x) E {dog, not-dog} a distinguishable feature. Moreover, as predicted by Conjecture 1, the network is calibrated with respect to dogs: 22.4% of all dogs in ImageNet are Terriers, and indeed the network classifies 20.9% of all dogs Terriers (though it has 9% error on which specific dogs classifies as Terriers). See Appendix Table@foo details, and related experiments on ResNets and kernels in Appendix
255
256
258
260
We now consider settings where the class labels are themselves distinguishable features (eg: CIFAR-10 classes are distinguishable by ResNets). Here our conjecture predicts the behavior of interpolating classifiers under structured label noise. As an example, we generate random spare confusion matrix and apply this to the labels of CIFAR- 10 as shown in Figure E
Class Partition:
261
262
263
264
We find that a WideResNet trained interpolation outputs the same confusion matrix on the test set as well (Figure 2 B). Now, to test that this phenomenon is indeed robust to the level of noise, we mislabel class + with probability p in the CIFAR-I0 train set for varying levels of p. We then observe P. the fraction of samples mislabeled by this network from 0 + 1 in the test set (Figure 3 shows p versus P). The Bayes optimal classifier for this distribution behaves as a step function (in red), and a classifier that obeys Conjecture 1 exactly would follow the diagonal (in green). The actual experiment (in blue) is close to the behavior predicted by Conjecture 1. This experiment shows a contrast with classical learning theory. While most existing theory focuses whether classifiers converge to the Bayes optimal solution, we show that interpolating classifiers behave "optimally" in a different sense: they match the distribution of their train set. We discuss this further in Section 5 See Appendix C.4 for more experiments, including other classifiers such as Decisions Trees.
286
268
270
272
274
Multiple features: Conjecture states that the network should be automatically calibrated for all distinguishable features, without any explicit labels for them. To do this, we use the CelebA datasct 37, containing images with many binary attributes per image. ("male", "blond hair". etc).
276
7

---

278
We train ResNet-50 to classify one of the hard attributes (accuracy 80%) and confirm that the Feature Calibration holds for all the other attributes (Figure 3 that are themselves distinguishable.
279
280
Quantitative predictions: We now test the quantitative predictions made by Conjecture T This
conjecture states that the TV-distance between the joint distributions (I(xx), f()) and (Zxz), y)
282
is at most E, where E is the error of the training procedure in learning L (see Definition D. To
283
test this, we consider binary task similar to Experiment [ where (Ship, Plane) are labeled as
284
class O and (Cat, Dog) are labeled as class 1, with p = 0.3 fraction of cats mislabeled to class O.
285
Then, we train a convolutional network to interpolation on this task. To vary the error E on these
286
distinguishable features systematically, we train networks with varying number of train samples. Networks with fewer samples have larger since they are worse classifying the distinguishable
287
288
features of (Ship, Plane, Cat, Dog). . Then, we use the same setup to train networks on the binary
task and measure the T'V-distacee between (I(r), J f()) and (I(x), y) in this task. The results are shown in TigureBE. As predicted, the TV distance on the binary task is upper bounded by error on the 4- way classification task.
289
290
291
292
5
Distributional Generalization
293
In order to relate our results to the classical theory of generalization, we now propose a formal notion of "Distributional Generalization", which subsumes both Feature Calibration and classical generalization. In fact, we will also give preliminary evidence that this new notion can apply even for non-interpolating methods, unlike Feature Calibration.
294
295
298
297
trained model f obeys classical generalization (with respect to test error) if its error on the train set is close to its error on the test distribution. We first rewrite this using our definitions below.
299
Classical Generalization (informal): Let f be a trained classifier. Then f generalizes if:
E 3e TeannSe (x)(
[1 + u(x)}1 R
E
[1[0 + y(z)}}
(6)
TextSer (-f(=)
Above, y(x) is the true class of x and y is the predicted class. The LHS of Equation 6 is the train error of f. and the RHS is the test error. Using our definitions of Dir, Dio from Section 3.1 and
301
302
defining Ten (r. 0) = 1(0 & y(r)), we can write Equation B equivalently:
E
[Tar(2
R
E
(x,
2.5~Die
303
That is. classical generalization states that certain function (Ter) has similar expectations on both the Train Distribution Dt, and Test Distribution Die. We can now introduce Distributional Generalization, which is a property of trained classifiers. is parameterized by a set of bounded functions ("tests""):
304
305
306
T S (T: X' x y - 1)]
Distributional Generalization: Let f be trained classifier. Then f satisfies Distributional Gener- alization with respect to tests T if:
308
VT E T
[T(,T))
R E Die
[Txx)))
(8)
Dor
309
This states that the train and test distribution have similar expectations for all functions in the family T. which we can write as: Drr RT Dic- For the singleton set T = {Ter), this is equivalent to classical generalization, but it may hold for much larger sets T. This definition of Distributional Generalization, like the definition of classical generalization, is just defining an object- not stating when how it is satisfied. Feature Calibration turns this into concrete conjecture.
311
312
313
315
5.1
Feature Calibration as Distributional Generalization
316
We can write our Feature Calibration Conjecture as a special case of Distributional Generalization, for a certain family of tests T. Informally, for given setting, the family T is all tests which take input (I, y). but only depend on æ via distinguishable feature (Definition Dp. For example, a test of the form T( y) = g( [(x), v) where L is a distinguishable feature, and g is arbitrary. Formally, for a given problem setting, suppose L is the set of Ac D. disttigguuueee features. Then
317
318
319
320
Conjecture I states that AL E L: (L)x), fa)) Re (L(z), v). This is equivalent to the statement
Dio - D
8

---

Step 2000
Step 20000
Step 40006
Step 760CO
Train Set
Testt Set
Figure 4: Distributional Generalization for WideResNet on CIFAR-10. The confusion matrices on the train set (top row) and test set (bottom row) remain close throughout training.
where T is the set of functions T= For interpolating classifiers, we have D = 'trr, and so Equation ( is equivalent to Dre 2 Dir. which is statement of Distributional Generalization. Since any classifier family will contain large number of distinguishable features, the set L may be very large. Hence, the distributions Die and Die can be thought of as being close as distributions.
g()))) LEL, g:xxx:xxxx 10 1].
323
325
328
5.2
Beyond Interpolating Methods
328
The previous sections have focused on interpolating classifiers, which fit their train sets exactly. Here informally discuss how extend results beyond interpolating methods. The discussion in this section not as precise as in previous sections, and is only meant to suggest that our abstraction of Distributional Generalization can be useful in other settings.
329
330
332
For non-interpolating classifiers, we may still expect that they behave similarly on their test and train sets that is, Die ~" D.r for some family of tests T. For example, the following is possible generalization of Feature Calibration to non-interpolating methods.
334
335
Conjecture (Generalized Feature Calibration, informal). For trained classifiers f. the following distributions are statistically close for many partitions L of the domain:
336
(I(x). T D
(L(x).))
(10)
2.G-Dar
337
We leave unspecified the exact set of partitions L for which this holds, since we do not yet understand the appropriate notion of "distinguishable feature" in this setting. However, we give experimental evidence suggesting some refinement of Conjecture 2 is true. In Figure 4. we apply label noise from a random sparse confusion to the CIFAR-10 train set. We then train single WideResNet28-1 10, and measure its predictions on the train and test sets over increasing train time (SGD steps). The top row
338
340
342
shows the confusion matrix of predictions f(x) vs true labels ((x) on the train set, and the bottom row shows the corresponding confusion matrix on the test set. As the network is trained for longer, it
3M
fits more of the noise on the train set, and this noise is mirrored almost identically on the test set. Full
345
experimental details, and an analogous experiment for kernels, are given in Appendix B
346
6
Conclusion
347
This work initiates the study of a new kind of generalization- Distributional Generalization which considers the entire input-output behavior of classifiers, instead of just their test error. We presented both new empirical behaviors, and new formal conjectures which characterize these behaviors. Roughly, our conjecture states that the outputs of classifiers on the test set are "close in distribution"
348
349
350
351
to their outputs on the train set. These results build a deeper understanding of models used in practice,
352
and we hope our results inspire further work on distributional generalization machine learning.

---

References
353
354
[1] Madhu S Advani and Andrew M Saxe. High-dimensioni dynamics of generalization error in neural networks. arXiv preprint arXiv:1710.03667, 2017.
22 Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overpa- rameterized neural networks, going beyond two layers. arXiv preprint arXiv: 1.04918, 2018.
357
358
359
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. In Advances in neural information processing systems, pages 6158-6169, 2019.
380
382
[4] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332, 2019.
363
384
365
[5] Susan Athey, Julie Tibshirani, Stefan Wager, et al. Generalized random forests. The Annals of Statistics, 47(2): 14781 2019.
366
367
66]
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):6296611, 2017.
388
389
[7] 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.
[8] Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. In Advances in neural information processing systems, pages 2300-231 2018
372
[9] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. arXiv preprint arXiv:/802.011 2018.
375
378
[10] 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, 116632):15849-133
377
378
2019.
379
[1I] Leo Breiman. Reflections after refereeing papers for nips. The Mathematics of Generalization, pages 11-15, 1995.
380
381
[12] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
382
[13] Leo Breiman, Jerome Friedman, Charles Stone, and Richard A Olshen, Classification and regression trees. CRC press, 1984.
[14] Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterizeed regime. arXiv preprint MXXIv22004.120199 2020.
385
386
[15] 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.0444 022200000044...... 2020.
16
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://////a
389
i css www.uuii.uuuuuuum
390
[17] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, arXiv preprint 173. 11008 2017.
391
392
393
[18] Manuel Fernández-Delgadue 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, 131113311
394
395
[19] Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: new perspective on generalization in neural networks. arXiv preprint arXiv: 1901. 094991, 2019.
397
10

---

[20] Mario Geiger. Stefano Spigler, Stéphane d' d'Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition as a paradigm understand the loss landscape of deep neural networks. Physical Review E, 100(1):012115, 2019.
400
[21] Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model. arXiv preprint arXiv:2002.093339 2020.
403
405
[22] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint 19X. 2019,
408
[23]
Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-3777 2007.
408
409
[24] Sebastian Goldt, Madhu S Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborova. Generalisation dynamics of online learning in over-parameterised neural networks. arXiv preprint
410
2019.
[25]
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR, 2018.
413
415
[26]
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. arXiv preprint arXiv:1706.0455 2017.
418
[27]
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science Business Media, 2009.
418
419
[28] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-
420
dimensional ridgeless least squares interpolation. arXiv preprint 000.:::99030056600 2019.
421
[29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
423
[30] Úrsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the inapuuttiinnlll-ddnnfffiii masses. In International Conference on Machine Learning, pages 1939-1948, 2018.
425
427
[31] Tin Kam Ho. Random decision forests. In Proceedings of 3rd international conference on document analysis and recognition, volume 1, pages 278-283 IEEE, 1995.
428
[32] Rashidedin Jahandideh, Alireza Tavakoli Targhi, and Maryam Tahmasbi. Physical attribute prediction using deep residual neural networks. arXiv preprint arXiv:1812.0788: 2018
430
431
[33]
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
[34]
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227--23)) 1998.
433
434
[35] Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. arXiv preprint arXiv:1907.04550 2019.
436
[36] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel" ridgeless" regression can generalize. arXiv preprint arXiv: 00387, 2018
437
[37] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang, Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV) December 2015.
439
440
[38] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint 1rXiv: 05355, 2019.
442
[39] Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, (Jun)9983-999, 2006.
11

---

444
[40] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 2020.
445
446
447
[41] Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(): 141-142, 1964.
448
449
[42] Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable explain generalization in deep learning, 2019.
450
451
[43] 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 on Learning Representations, 2020.
452
453
454
[44]
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In Advances in neural information processing systems, pages 1786-1799 1794, 2010.
455
[45] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems, pages 1196-1204,
457
2013.
[46] Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and loannis Mitliagkas. A modern take on the bias-variance tradcoff in neural networks. arXiv preprint arXiv:1810.08591, 2018.
460
[47] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of verrpparametrizatoon in generalization of neural networks. 2018
465
arXiv preprint 1rXiv:1805.
465
[48] 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.
466
468
[49] Matthew A Olson and Abraham J Wyner. Making sense of random forest probabilities: a kernel perspective. arXiv preprint arXiv:18/2.05792, 2018
469
470
[50] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary De Vito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
471
472
473
[51] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-leam: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2836 2011.
474
475
478
477
[52] Taylor Pospisil and Ann B Lee. Rfcde: Random forests for conditional density estimation. arXiv preprint arXiv: 1804.0044000555 2018
478
[53] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pages 1 1177-1884, 2008
480
481
[54] David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv preprint arXiv: 10694, 2017.
482
[55] Jonas Rothfuss, Fabio Ferreira, Simon Walther, and Maxim Ulrich. Conditional density estima- tion with neural networks: Best practices and benchmarks. arXiv preprint
484
000554,
485
2019.
[56] 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-552 2015. doi: 10.7// 1263-015-08166y.
487
489
490
[57] Robert E Schapire. Theoretical views boosting. In European conference on computational learning theory, pages 1-10. Springer, 1999.
12

---

492
[58] Robert E Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee, et al. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 2665):6611-1666 1998.
493
[59] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
496
497
[60]
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Keil, Ludwig Schmidt, Jonathan Ragan-Kelley, and Benjamin Recht. Neural kernels without tangents. arXiv preprint arXiv:2003.0223: 2020.
489
500
[61] Utkarsh Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004. 10802, 2020.
501
502
662] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822- 28788 2018
503
504
505
[63] Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Yusof. Combating label noise in deep learning using abstention. arXiv preprint arXiv:1955. 2019.
507
508
[64]
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake Vand erPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1. 0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261 272, 2020. doi: https://doi.og///1 0088/441922011-0688
509
510
511
512
513
514
515
516
[65] Larry Wasserman. All of statistics; concise course in statistical inference. Springer Science & Business Media, 2013.
518
519
[66]
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 67
522
of adaboost and random forests as interpolating classifiers. The Journal of Machine Learning Research, 18(1):1558-150 2017.
523
524
688]
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 1708.07747 2017.
[69] Mohammad Yaghini, Bogdan Kulynych, and Carmela Troncoso. Disparate vulnerability: On the unfairness of privacy attacks against machine learning. arXiv preprint arXiv:1906.0038) 2019.
527
[70] Sergey Zagoruyko and Nikos Komodakis.
Wide residual networks.
arXiv preprint
530
arXiv: 1605..1055.001 07 146, 2016.
771 Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03580 2016.
532
535
[72] Liu Ziyin, Blair Chen, Ru Wang, Paul Pu Liang, Ruslan Salakhutdinov, Louis-Philippe Morency, and Masahito Ueda. Learning not to learn in the presence of noisy labels. arXiv preprint arXiv:2002. 06541, 2020.
535
13

---

Checklist
536
537
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
539
contributions and scope? [Yes]
540
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] This paper does not introduce any new methods or applications, and we thus cannot predict any near-term societal impact (positive or negative).
542
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
545
546
2. If you are including theoretical results...
547
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
548
(b) Did you include complete proofs of all theoretical results? [Yes]
549
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [No] No new methods were introduced,
551
the code is standard. We fully specify all experimental hyperparameters for the sake of reproduction.
553
554
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
555
556
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] The experiments we consider all exhibit concentration around their expected values, and this is well-known in the community. Notably, we only consider supervised learning.
558
560
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
561
562
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
563
(a) your work uses existing assets, did you cite the creators? [Yes]
564
(b) Did you mention the license of the assets? [No]
565
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
586
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
567
using/curating? [No]
568
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
570
5. If you used crowdsourcing or conducted research with human subjects...
571
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
572
573
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
574
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
576
14


Reviews:
[{"review_id": "hUV6SW1OR_8", "reviewer": "Reviewer_EwQL", "summary": "This submission proposes a new type of generalization satisfied by interpolating classifiers (the primary focus), that is different from agreement between test error and train error as in classical learning theory. This type of generalization is largely motivated by empirical evidence across different models (neural networks, kernel regression & svm, decision trees) and theoretically for 1-Nearest Neighbors classification (Theorem 1). More specifically, the submission claims that for certain types of mappings x -> L(x) (termed \"distinguishable features\" -- i.e. they must be learnable to good test accuracy in the setting under consideration), the joint distribution of (L(x), y) where (x,y) pairs are drawn from the true distribution will be \"close\" to the joint distribution of (L(x), f(x)) on the test set, where f(x) is the trained model prediction.\n\nList of contributions:\n--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).\n\n--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. \n\n--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). \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Originality: This work identifies & investigates an original empirical property that appears to be satisfied by interpolating classifiers. The proposed concepts (Feature Calibration) are general & seem distinct from any prior work to the best of my knowledge. (For example, the authors note that \"standard\" calibration is a particular case of Feature Calibration with specific choice of L(x).) I think this work is bold in what it seeks to accomplish (asking a fundamentally new question at the basis of learning theory, building evidence from diverse empirical examples) and makes a reasonable first step towards doing so. \n\nQuality: The quality of the work seems high. The authors give a number of different empirical examples with sufficient coverage across model diversity and provide a theoretically satisfied case (1-Nearest Neighbors). The authors note the limitations of the work (e.g. the FCC is specified in terms of \"natural distributions\" which has an unclear meaning) and are fairly thorough in addressing potential concerns & connections to other works. I was not able to identify significant shortcomings with respect to the conceptual formulation or message of the paper. I make some comments about diversity of empirical examples (with respect to datasets / partitions) below.\n\nClarity: The paper is clearly written and was straightforward to read.\n\nSignificance: I think this paper takes a risk in its premise, provides a reasonable amount of evidence in support of its main claims, and would spur further work in this area; as I was also not able to identify any major issues with the paper, this is the reason behind my suggested score. In Section 1.3 the authors discuss a number of consequences for learning theory which seem notable. This work tells us more about the implicit bias of models (though not just neural networks); most interesting I think is that in certain limits (e.g. when models are interpolating, and model size >> dataset size), models are not approaching the Bayes optimal classifier but sample from the distribution p(y|x). \n\nOther comments & questions:\n\n--I find some mentions of \"Bayes optimal classifier\" to be confusing at times -- for instance, its usage in L268 seems to be with respect to argmax p(y | L(x)) (rather than argmax p(y|x)), if I understand correctly. Perhaps it is worth pointing this out and the connection between the two (e.g. in the setting where p(y|x) is discussed, section starting at L107). \n\n--In the empirical examples with label noise, why do the authors consider only sparse confusion matrices?\n\n--I think this work has good empirical diversity across very distinct classes of interpolating models, but one place where the paper could be noticeably strengthened is diversity of examples with respect to the datasets / partitions L(x) that are considered. Apart from the constant partition L(x) = 0, all the partitions seem to be largely based off of semantic distinctions that are already available in datasets. (Because of this, I also wondered whether the behavior is largely inherited from the dataset and from the existing semantic structure within it.) Are there more complex L(x), that are not semantically constructed, that can be considered? Separate but related to this, is it valid to consider L(x) that have some knowledge of the distribution D, or even a particular training set? For instance, L(x) that is constructed from trained intermediate layer embeddings in a neural network -- or would L(x) that has knowledge of the distribution D potentially break FCC?\n\n(For instance, this type of L(x) / y constructed from true labels / label noise on existing label structure, e.g. CIFAR-10, is also used in the non-interpolating setting in Section 5.2, which makes the reader wonder what is actually happening in the interpolating setting. More generally, I found Section 5.2 to be in tension with the main message prior to that section, and perhaps too preliminary to be presentable.)\n\n--I think one other experiment that would significantly strengthen the paper is one that tests the implications mentioned for scaling limits in L107 (e.g. measure feature calibration as models are scaled from the underparametered scaling regime to overparameterized.) This would give some more diverse evidence of places where feature calibration breaks down.\n\nNit points:\n--Typo L263: spare -> \"sparse\"\n--Typo L265: Figure label should be \"2A\"\n--L749 in appendix is cut off", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not address potential negative societal impact, but I believe it is not necessary given the nature of the work.\n\nThe authors do provide adequate discussion of limitations and are clear about the conjectural portions of their work.  ", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with the paper as far as I can tell.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "a6i_cJyDkGA", "reviewer": "Reviewer_fE8g", "summary": "The authors consider interpolating classifiers, i.e. classifiers that interpolate the training data by selecting the correct class for training samples, often performing poorly in terms of generalization error. The authors propose a new notion of generalization, i.e. the Distributional Generalization. Such a notion does not focus on the average error over the inputs, and subsumes both classical generalization and the conjecture that the outputs of classifiers match the statistics of their training distribution when conditioned on certain subgroups. The authors formally introduce and experimentally validate a conjecture to specify such subgroups. While the conjecture is proven for 1-nearest-neighbor classifiers, empirical evidence is provided for other classifiers; such as kernel machines and neural networks.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "== Main comments ==\n\n- The paper is overall well written and the topics are clearly exposed. Illustrative examples are effectively presented to further clarify the problem at hand.\n- The presented work tackles a timely and relevant problem in machine learning, drawing ideas from many related areas of research, such as output distribution calibration, overparametrization, and benign overfitting. The presented results are worthy but not completely surprising. \n- The paper addresses a very much similar problem than : \nVapnik, V. & Izmailov, R.. (2020). Complete statistical theory of learning: learning using statistical invariants. Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications, in PMLR 128:4-40\nHowever, this problem is known to below to the class of  ill-posed problems. How does the current work related to the above mentioned reference? How does it overcome the ill-posed problem. \n- In eq. (1) the notation is a bit confusing. Are TrainSet and TestSet the distributions from which the samples of these sets are drawn (but then D_tr, D_te are used to mean the same), or rather the sets themselves (and then ~ should be replaced with ∈)?\n- One of the two main contributions is thoroughly expressed in section 3.2. This is indeed a very interesting observation. However it looks closely related to the problem defined in section 2 of [26].\nCould the authors further underline the value and originality of their contribution by discussing the connection between the two concepts?\n- Although the feature calibration conjecture is fully proved to 1-nearest-neighbors classifiers, it is also true that it represents a very limited model. It seems that for more complex (and more commonly used) models, only empirical evidence can be provided so far, with no much theoretical formalization. Although this is not necessarily a negative aspect for works in progress and contributions which bring new ideas, the expectation set up by the writers in the introductory section are diminished by lack of formalization.\n- The training procedure is sometimes indicated as Train_A, and sometimes as A. We suggest to choose one symbol and consistently use it throughout the whole paper.\n- Have the authors thought of any potential issue related to identifying potentially sensitive subgroups L such as, ethnicity, high/low income, etc. instead of dogs, cats, etc. when using different\ndatasets?\n- We would like to draw attention on the fact that, in line 101, the reference to the work in [7] does not seem to properly fit it. Indeed, in [7] the authors already explain that ‘benign overfitting’ is only characterized in specific cases and does not generally apply, making the claim in lines 103-104 appear a bit excessive. Reference [26] should be reported as the version officially published at ICML 2017.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors take into the scientific limitations of their work in section 3.4. Further improvements can be implemented by answering the questions and doubts raised in the Main Review.", "review_text": "", "extra_scores": {"ethical_concerns": "There is no ethical concerns ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours "}, "extra_text": {}}, {"review_id": "EFIeYHIWZsG", "reviewer": "Reviewer_fCRG", "summary": "The paper empirically characterizes a fine-grained generalization property of interpolating learning algorithms, and give a conjecture that formalizes the observed phenomenon. Roughly, the paper observes that the generalization properties of an interpolating classifier can be quite distinct for different sample subpopulations with the same label, whenever the label noise imposed on these subpopulations during the training phase is distinct. Authors conjecture that the generalization properties may be uniform only for samples belonging to a smaller \"distinguishable\" clusters of the input data space.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Post-rebuttal: I thank authors for their detailed response. Most of the authors' response made a perfect sense. One thing that prevented me from raising the score further is that I am still not sure about is whether the conjecture itself is meaningful or useful. In fact, after reading the response to my first point (Converse...), I am slightly more pessimistic about the possibility that \"distinguishability\" and \"feature calibration\" are tightly connected concepts (say, in a causal sense). I am curious if there are alternate (and perhaps more useful) conjectures that can help explain the phenomenon. In other words, I think the paper should benefit from having an extensive discussion that justifies why the proposed conjecture based on distinguishability is nontrivial, useful, and better than other possible alternatives.\n\n\n---\n\n__What I like.__ The reported empirical observation is intriguing to some degree, and (in my opinion) is worthy of documenting and formalizing. Authors validate the observation under a variety of scenarios in Section 1 & 4 (and also appendices), which helped convincing me of the existence of such phenomenon. As the authors noted, establishing a theoretical framework that can explain the depicted phenomenon may be an interesting open problem (perhaps we can phrase problems in a minimax style with multiple tasks?). The clarity of the writing is well above average, while there are several points that can be clarified further. I also liked the theoretical contributions, which could help readers grasp the idea of how such conjectures can be proved.\n\n__Checking/refining the conjecture.__ On the one hand, I find that the provided empirical observations support the conjecture well. On the other hand, I think that one can even further strengthen the argument by trying to provide an evidence supporting that the conditions described in the conjecture is indeed essential for the distributional similarity. I am actually very curious whether the \"distinguishable features\" are really essential. Is there a case where the distributional similarity does not hold for indistinguishable features, which is perhaps more informative than the perfectly random case? Although this is not really necessary if one is interested only in the validity of the conjecture, having such evidence will help us understand how non-vacuous/\"tight\" the conjecture is.\n\n__Clarifying the terminology: Interpolating.__ I think the term \"interpolating classifier\" can be clarified further in the text. Although the terminology is now (sort of) popularly used in the literature, I think still they need to be properly defined at least once in the main text, as the modern use of this terminology are often wider than what is used to mean in the classic kernel-based literature.\n\n__Clarifying the terminology: Distributional Closeness.__ I am curious in what sense the notion of \"distributional closeness\" introduced in Section 2 is different from the widely used notion of integral probability metrics (IPMs). If they are identical, sticking to the existing notation would help reduce the confusion.\n\n__Practical implication.__ While I mostly liked the theoretical implications illustrated in Section 1.3, I wonder if authors could give an idea why capturing such fine-grained generalization properties may be important. For instance, could there be any implications to the fairness or shortcut learning?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation is clearly described, in my opinion. This work mainly discusses what is implicitly taking place in the standard learning practices, instead of giving a new one. I do not think there is any \"potential negative impact\" that should be discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "I cannot think of any relevant ethical issue.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}]

Author rebuttal:

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


Decision: Reject