Probing Predictions on OOD Images via Nearest Categories
Authors: Yao-Yuan Yang
Cyrus Rashtchian
Ruslan Salakhutdinov
Kamalika Chaudhuri
Venue: Accepted by TMLR ()

Abstract: We study out-of-distribution (OOD) prediction behavior of neural networks when they classify images from unseen classes or corrupted images. To probe the OOD behavior, we introduce a new measure, nearest category generalization (NCG), where we compute the fraction of OOD inputs that are classified with the same label as their nearest neighbor in the training set. Our motivation stems from understanding the prediction patterns of adversarially robust networks, since previous work has identified unexpected consequences of training to be robust to norm-bounded perturbations. We find that robust networks have consistently higher NCG accuracy than natural training, even when the OOD data is much farther away than the robustness radius. This implies that the local regularization of robust training has a significant impact on the network’s decision regions. We replicate our findings using many datasets, comparing new and existing training methods. Overall, adversarially robust networks resemble a nearest neighbor classifier when it comes to OOD data.

Published in Transactions on Machine Learning Research (03/2023)
Probing Predictions on OOD Images via Nearest Categories
Yao Yao-Yuan Yang"
yay005 ucsd. edu
UC San Diego
Cyrus Rashtchian Google Research
cyroid@google.com
Ruslan Salakhutdinov
rsalakhu@cs.ccm crna eduu
Cornegie Mellon University
Kamalika Chaudhuri UC San Diego
Samalika@engg ucsd. edu
Reviewed on OpenReview: https: // ottp:///pprrvvee....m net/ forum? id= FTNorIuIIG
Abstract
We study out-of-distribution (OOD) prediction behavior of neural networks when they classify images from unseen classes or corrupted images. To probe the OOD behavior, we introduce & new measure, nearest category generalization (NCG), where we compute the fraction of OOD imputs that are classified with the same label as their nearest neighbor in the training set. Our motivation stems from understanding the prediction patterns of adversarially robust networks, since previous work has identified unexpected consequences of training to be robust to norn-bounded perturbations. We find that robust networks have consistently higher NCG score than natural training, even when the OOD data is much farther away than the robustness radius. This implics that the local regularization of robust training has a significant impact on the network's 's decision regions. We replicate our findings using many datasets, comparing new and existing training methods. Overall, adversarially robust networks resemble a nearest neighbor classifier when comes to OOD data
1 Introduction
Understanding how neural networks generalize is an ongoing endeavor for machine learning researchers. Many generalization propertics for in-distribution data have been discovered (Geirhos et al., 2020; Sagawa et al. 2020 Dasgupta et. al., 2022 Chan et. al., 2022). However, how deep neural networks generalize out-of-distribution (OOD) data is less studied. In this context, OOD could mean that the inputs come from previously unseen categorics (Salchi et al. 2021 Yang et al. 2021), or that the inputs have been adversarially perturbed (Madry el al.) 2017) or corrupted (Hendrycks & Dielterich, 2019). Sludying OOD generalization may improve the reliability of machine learning systems. Another goal comes from semi-supervised and self-supervised learning, where the model propagates labels to unlabeled data [Van Engelen Hoos 2020 Identifying clear patterns in OOD behavior can aid engineers choosing among many methods.
Unfortunately, predictions OOD data be mysterious. For example, adversarially robust training methods often involve regularizing the network that it predicts the same label on both training example and on all points in a small e-ball around the example (Madry et al.] 2017 Zhang et al. 2019). Such methods only specify a local constraint on prediction behavior. At first glance, it may be tempting to guess that training to be robust in small e-ball should not affect prodictions on other parts of the input space. However, it has become clear that robust training can cause substantial differences in global behavior. For
NNo DeepMind.
"ooee available at http:://wth...a..a......eeeeeeea

---

Published in Transactions on Machine Learning Research (03/2023)
example, it may lead to excessive invariances (Jacobsen et al. 2018 Tramèr et al. 2020 improve transfer
learning (Salman et al. 2020 or change confidence on OOD data Hein et al. 2019
1.1 Nearest Category Generalization
In this work, we introduce a new metric that we call Nearest Category Generalization (NCG). Concretely, we calculate how often the predicted label on OOD data matches the 1-mearest-nniighorr (1-NN) label and call this measure as the NCG score (see Figure ! for a visual example). We explore whether neural networks are more likely classify OOD data with the class label of the ncarest training input. We also study how adversarial robust. training and find that it encourages the network to predict the same label not just in an
e-ball but also much further away in the pixel space (Carlini et al. 2019
Training example
Input: OOD example
4
4
Nearest neighbor
Label:
NCG if predicted as
A visual example of nearest category generalization. Assume we have model trained on MNIST digits zero to eight, and we have images of nine OOD examples. In the figure, OOD example has the image of four in the training set as the nearest neighbor. Tf this OOD example also gets predicted as a four, we say the model is gencralizing this OOD example to its nearest category. The NCG score measures how often OOD examples are generalized this way on the given model.
Figure 1:
that the imput
Following prior work (Salehi et al. 2021 we consider canonical lypes of OOD data (i) Unseen Classes: during training, hold out all images from one of the classes, but during testing, predict labels for images from this unseen class, (ii) Corrupted Data: we train on all classes, but test on images that have been corrupted. Importantly for us, both sources of OOD data have the property that the distance (e.g., (2) is quite large between the OOD data and the standard train/test images. In particular, the distance is much larger than the robustness radius used during robust training, and therefore, the training procedure does not explicitly dictate the predictions on such OOD data. Hence, NCG score measures global resemblance to the 1-NN classifier for unseen or corrupted images.
Understanding NCG can shed new light many rescarch questions. First, if changes in the training method lead lo significant changes in NCG score, then this suggests the network's 's decision boundaries have shifted to extrapolate very differently on OOD data. Even for ReLU networks, understanding the decision regions far away from training data is an active and important area of rescarch (Arora et al. 2016 Hanin & Rolnick 2019 Williams et al. 2019). Second, NCG score provides a new way to understand a model's prediction on unlabeled data that cannot be labeled using other information. This is contrast to transfer learning and few-shot learning that require auxiliary data Raghu et al. (2019); Yosinski et al. (2014); |Wan et al. (2020). Overall, emphasize that the NCG framework is not rooted in standalone task, but instead, it highlights new prediction patterns of networks on OOD data.
1.2 Contributions
Our result shed light on how to examples with unseen classes. Our first finding is that NCG score is consistently higher than chance levels for many training methods and datasets. This means that the behavior on OOD data is far from random. On both natural and corrupted OOD images, the network favors the 1-NN label. Surprisingly, this correlation with 1-NN happens in pixel space with & distance. The network converges to a classifier that depends heavily on the geometry of the input space, as opposed to making predictions based on semantic higher-level structures.
2

---

Published in Transactions on Machine Learning Research (03/2023)
Next, show that robust networks indeed have much higher NCG scores than natural training methods. This holds for a variety of held-out classes, corruption types, and robust training methods. 0OD inputs that are classified with the NCG label (I-NN in training set) are considerably further than from their closest training examples. These training examples also have adversarial examples that are closer than the robustness radius (see Figure 2 This implies that the decision regions of adversarially robust methods extend certain directions, but not others, and that the local training constraints lead to globally different behavior. We can identify these types of prediction patterns precisely because we examine the network with OOD data.
4
9
4
OOD dist
Figure Robust networks tend to predict the same at large distance in some directions, e.g., toward natural OOD examples (green), but are susceptible to adversarial examples that are closer in the worst-case directions (red).
Besides unseen classes, we also look at corrupted data, such as CIFARIO-C, CIFAR100-C, and ImgNet100- C Hendrycks & Dietterich (219 The NCG scores for all networks (including natural and robust networks) are above the chance levels, and robust networks often have much higher NCG score than natural training. We also uncover an intercsting correlation between NCG score and prediction accuracy for corrupted data. Corrupled examples that are correct in lerms of NCG score have a higher chance of being classified correctly in terms of the semantic label as well. In other words, if the network matches the 1-NN prediction, then it is more likely to predict the correct label for a corrupted image. This indicates that having higher NCG score may be desirable property, it is positively correlated with better predictions on corrupted data.
Our work uncovers an intriguing OOD generalization property of neural networks, and we find that robust networks have higher NCG score than naturally trained counterparts. However, robust training does not inherently impose constraints on the OOD data that we consider (OOD data are far from perturbed examples). We posit that the NCG behavior is a consequence of the inductive bias produced by neural networks (especially for adversarially robust networks). Also, different forms of robustness (l2 and corruptions) may be interconnected with NCG at deeper level.
1.3
Related Work
Many prior works have tried to understand how neural networks generalize. For instance, Geirhos et al. 2020 show that certain lypes of features are learned more easily, [Sagawa el al. (2020) study how changing the architecture could change the features that neural networks learned, and Dasgupta et al.) (2022); Chan et al, (2022) study how neural networks generalize on in-distribution data and suggest that in some in-distribution regions, neural networks behave like nearest neighbor classifiers. Our work is valuable addition to this series of studies.
To investigate the global behavior of robust networks, we explore patterns in how such networks predict on OOD data. However, the dimensionality of the input space for deep neural networks is usually high, making it hard to explore the entire input space. Prior human study shows that when human tends to categorize stimuli that are relatively few and distinct based on other previously seen stimuli that are similar to the current ones (e.g. complla--based prediction) (Shepard & Chang 1963 Nosofsky 1986 Rouder & Ratcliff 2004). Dasgupta et al. (2022); ; Chan et al. (2022) follow this idea and study neural network generalization on in-distribution image and language data. They first train neural networks on data w/ or w/o different attributes (e.g. the existence of a specific word in a sentence). Then, they probe these models' prediction with inputs w/ or w/o these attributes to study the model's generalization property. However, the scope of these prior experiments is limited to in-distribution data or certain OOD data, such as random noise or adversarial perturbations (Hein et al., 2011). Also, in this work, instead of focusing on human interpretable attributes, focus the raw input space and the learned feature space.
3

---

Published in Transactions on Machine Learning Research (03/2023)
There has been much rescarch properties of robust networks beyond robustness. Santurkar et al. (2020) study the performance of adversarially trained models on subpopulation shift. [Salman et al. (2020) consider transfer learning for robust models. Kireev et al. (2021) look at accuracy on corrupted data for robust training methods.
Our results on NCG strengthen and complement existing efforts in understanding the excessive invariances
that are induced by adversarial training (Jacobsen et al. 2018 Ortiz-Jimenez et al. 2020 Tramerr al.)
2020h. Another related area is extrapolation (Balestriero et al. 2021 Xu et al. 2020 where we provide a
theoretical result (Theorem I that corroborates claims that higher diversity of the training distribution helps
extrapolation to linear target functions (Hein et al. 2019: Xu et al. 2020).
Data augmentation is an effective way to improve generalization and robustness (Cubuk el al. 2020: Shorlen & Khoshgoftaar 2019). The success of this approach is consistent with our findings. Local regularization can lead to unexpected behavior, and hence, training on far-away images helps control the decision regions (c.g., for ness and generalization, ef. Herrmann et. al. (2021)) )
Connecting NCG with OOD detection is nice direction for future work (Manevitz & Yousef 2001 Liang ct al. 2018 Ren et al. 2019). OOD detectors already work well for some tasks, such as detecting data from another dataset (Sehwag et al. 2021 Tack et al. 2020). Holding out a single class from the same dataset provides a harder instance of OOD detection. Predictions on unseen data are also studied in the area of open set recognition (Dhamija et al. 2020). Another approach to OOD generalization involves the confidence/ confidence/uucceraiing /uncertainty on OOD data (Kristiadi et al.) 2020 Meinke & Hein 2019 Van Amersfoort et al.j 2020). However, much of this work takes Bayesian perspective and calibrates OOD predictions. We focus on geometric framework, looking at distances and 1-NN labels in the input space. The perceptual organization of neural networks is another way to probe OOD behavior (Kim et al. 2021).
2 Preliminaries
OOD Data. We consider two standard types of OOD data. Unseen Classes: We hold out all examples from one class during training time (e.g., MNIST without 9s). During test time, we evaluate test accuracy on the remaining classes, and we evaluate NCG score the held-out class (e.g., we predict 0-8 for the 9s). For each dataset, we hold out different classes, and we use the shorthand dataset-wo to mean that this class # is unseen. For example, Wof is MNIST with unseen digit 9, CIFAR10-wO0 is CIFAR10 with unseen airplane and CIFAR100-w00 is CIFAR100 with unseen aqualic mammals. We shorten this as M-9, C10-0, C100-0, etc. We use coarse labels for CIFAR100, For ImageNet, we subsample to 100 classes to form ImgNet100. Corruptions: We train on all classes and evaluate standard corruptions, which includes CIFAR1O-C and CIFARI00-C (Hendrycks & Dietterich 2019). Again, we measure NCG score by classifying corrupted data and checking whether the label matches the 1-NN training label.
Adversarially Robust Training. Let B(x,r) be a ball of radius r > 0 around x in a metric space. A classifier f is said to be robust at x with radius if for all x' E B(x,r) r), we have f(x') f(x). Standard adversarially robust training methods such as TRADES (Zhang et al. 2019) work by minimizing a loss function that is the sum of the cross-entropy loss plus a regularization term; this regularization term encourages that the network is smooth in a ball of radius r around each training point x,, ensuring robustness in this ball. Concretely, the TRADES loss is:
{(fo(x:), + 3 max (KL()) xeP.
(1)
where 3 is tradeoff parameter, l is the entsspy loss, and P. B(x,, r) is the ball of radius around x,-
Distance Metrics for NCG. We use the Ez distance for two representations. Pixel Space: Robust methods aim to have invariant predictions within a small norm ball in pixel space. Hence, we evaluate the distance in pixel space (we believe the le results would be similar). Feature Space: For another representation, we first train a different neural network (fully connected MLP) on the in-distribution data (we omit the unseen class). Then we compute the last layer embedding for all images, including those in the unseen class, giving us a learned, latent embedding. This provides vectors for both in-distribution and OOD images, and we use these
4

---

Published in Transactions on Machine Learning Research (03/2023)
vectors as our "feature space" version of the datasets. Note that we do not claim that these representations capture human-level or semantic similarity for the OOD data. Nonetheless, they both can be used by future work to provide insight into the OOD prediction behavior of robust and normal networks.
NCG score. The NCG score is the fraction of OOD imputs that are labeled as their nearest neighbor in the training set (i.e., we measure agreement with the 1-NN classifier). For corrupted data, we use the whole training set. For unseen classes, we use the training set minus the held-out class. We measure the 1-NN prediction in & distance in either the pixel space the above-defined feature space.
3 NCG for Unseen Classes
Set-up. For natural/robust training, on MNIST, we evaluate a CNN; on CIFAR10/100, we use Wider ResNet (WRN-40-10); on ImageNet, we use ResNet50. We consider natural training and mixup (Zhang et al. 2017 as baselines. For robust training, we consider two standard methods, Adversarial Training (Madry et al. (AT7)(AT) and TRADES (Zhang et al., 2019). These methods are known to have high adversarial robustness to l2 perturbations, and hence, they serve as good baseline examples of robust networks. For TRADES, we use robustness radii r e (2, 4, 8) for the lz ball in Equation [ In the pixel space, we use r 2 for AT. In the feature space, we set r= for AT on CIFAR10/100 and r = .5 for AT on ImgNett (on CIFAR10/10N AT failed to converge with r= 2 and on ImgNet100 with re {1, (1). We denote TRADES with r = 2 and AT with 1 as (RADES(2) and AT(1), respectively. Prior work observes that AT and TRADES give similar results with parameter luning (Yang el al. 2020 Carmon el al. 2019), and hence we expect them to behave similarly. Appendix C has more details.
Datascts. We consider all 10 classes as the unseen class for MNIST and three unseon classos for each of CIFAR10, CIFAR100, and ImgNet100. CIFAR10, we consider removing the airplane, deer, and truck classes; for CIFAR100, we remove the aquatic mammals, fruit and vegetables, and large man-made outdoor things classes; for 1mg,et100, we remove the American robin, Gila monster, and eastern hog-nosed snake classes. These are denoted as CO0,R10- 4, 9}, CIFAR100-wo(O, 4, 9), ImgNet100-wwo(f 1. 2}.
Results. Table 1 shows the NCG score of natural and robust models averaged over unseen classes (in both pixel and feature space). We perform a chi-squared test against the null hypothesis that the distribution of the labels is uniform with the p-value threshold set to 0.01. We find that for all 80 models trained, there is a significantly higher than chance level NCG score. Then, we perform a f-test between each robust model vs. natural training, with the null hypothesis being that the robust model has lower NCG score. In Table 2 we show the number of cases that pass this (-test. Adversarially robust. models, TRADES and AT, almost. always have a higher NCG score than natural training with verified statistical significance. Meanwhile, mixup have a higher NCG score than natural training in only less than half of the cases.
Adversarial robustness increases NCG score. The unseen class is absent at training, and this property has been obtained simply by making the model adversarially robust. This is interesting because it suggests that robust models extrapolate to OOD data in a way that is more likely to match 1-NN predictions. Prior work on extrapolation (Xu et al. 2020) has shown that MLPs tend to extrapolate as linear functions on far OOD data. The 1-NN classifier is not a linear function in their sense. Specifically, the 1-NN label is determined by the Voronoi decomposition of the training data, and the decision boundaries separate far away points using hyperplanes. Hence, the higher NCG score of robust classifiers uncovers new phenomenon of OOD behavior. We next investigate whether we should expect higher NCG score for robust models by mcasuring the distance to OOD examples.
3.1 OOD Data are Farther than Adversarial Examples
Why do robust models have higher NCG score for unscen classes? One plausible explanation is that the robust methods enforce the neural network to be locally smooth in a ball of radius r; if the OOD inputs are closer than r from their nearest training example, then they would get classified accordingly. Next, we test if this is the case by mcasuring the l distance between each OOD input x and its closest training example
*. Then, we calculate the closest adversarial example x' to x using various attack algorithms. We measure (i) the distance between OOD example and its closest training example ([|x x12) and (ii) the empirical
5

---

Published in Transactions on Machine Learning Research (03/2023)
Table The average and standard deviation of the NCG scores across different held-out class each dataset. There are 10 unseen classes for MNIST and unseen classes for CIFAR10, CIFAR100, and ImgNet100. In general robust methods have higher average NCG than natural training. The chance level is 1/9 for MNIST and CIFAR1O, 1/19 for CIFAR100, and 1/99 for ImgNet100.
MINST CTFAR10 CIFAR100
ImgNet100
pixel
natural
.49 1 14
24 .09
.18 .03
.04 .01
mixup
447
.20 .66
.04 .01
TRADES(2)
59
.12
.29 +
.04 .01
TRADES(4)
.59 .10
371
.29
.05 001
TRADES(8)
.52 112
31
.29 - .13
.06 001
(2(
.60 10. 10
36 .22
.26 + .07
.04 .01
feature
natural
.0 .18
.82 .22
.66 + .03
.12 .01
mixup
166
.79
.02
.66 .03
.14
TRADES(2)
115
.22
.72
.16
TRADES(4)
.64 -10
88
+.1
.13+
TRADES(8)
.67 67 .11
.85
.01
.14 001
(3))
.54 54 .17
.85 .03
.73
.16 .01
Table 2: The number of robust models with higher NCG score than natural training, For MNIST we check 10 unseen classes, and for CIFAR1O, CIFAR100, and ImgNet100,, use 3 unseen classes. 10/10 means that. out of the 10 unseen classes, all 10 models have higher NCG score.
pixel
feature C10
M
C10
C100
M
C100
mixup
5/10
0/3
2/3
0/3
0/10
0/3
2/3
3/3
TRADES(2)
10/10
3/3
3/3
3/3
9/10
2/3
3/3
3/3
TRADES(4)
8/10
3/3
3/3
3/3
10/10
3/3
3/3
3/3
TRADES(S)
7/10
3/3
3/3
3/3
10/10
3/3
3/3
3/3
(L)))(())(5)
10/10
3/3
3/3
3/3
9/10
3/3
3/3
3/3
robustness radius (|x' (ox2)x|(2). We plot the histograms in Figure 3 We use the C&W attack Carlini & Wagner (2017) algorithm to find the closest adversarial example. Some of these attacks are slow, so we compute adversarial examples for 300 randomly sampled training examples that are correctly predicted. Then, we restrict to OOD examples that have one of these 300 training examples as their closest neighbor.
Figure reports typical distance histogram in the pixel space (for C10-0). We find that the histograms of OOD distances and the empirical robust radii have little to no overlap in the pixel space, while in the measure
feature space, there is some overlap but not much. To better understand what is happening, the percentage of OOD examples that are covered in the ball centered around the closest training example with a radius of the empirical robust radius. We find that in both the pixel and feature space, for 186 out of 190 models, this percentage is less than 2%, which is siguificantly smaller than the difference between the NCG score of robust and naturally trained models in most cases (190 comes from having two metric spaces, five models, and 19 datasots). This result shows that almost all OOD examples from unseen classes are significantly further away from their closest training example than the empirical robust radius of these training examples.

---

Published in Transactions on Machine Learning Research (03/2023)
100
140
eeciito robest FAGMS
dtitncc
50-
70-
empricall rolest radkos distnce
3[0-
00
69
20
20
log
nutural datencs
natural distance
6,
(a) C10-wo0, pixel space
(b) C10-wo0, feature space
(c) T-woO, pixel space
(d) T-woO, feature space
Figure 3: Histograms: log of the empirical robust radius and OOD distance for TRADES(2) on CIFARIO-WoO and ImgNet100- Adversarial examples are much closer than OOD examples.
3.2 The Role of the Training Procedure
We next ask whether changing the robustness regions P, when optimizing the loss in Equation can change NCG score. TRADES enforces smoothness in a region P; that is to be a fixed radius r norm ball around each training example. Enforcing smoothness on fixed radius norm balls may not ensure good NCG score. Figure [d shows an example here, the purple points are closer to the orange cluster on the left and further from the orange cluster on the right. If we only enforce smoothness on a uniform ball (TRADES), the decision boundary for the purple points does not extend right enough. We explore making the classifier smooth in regions P. that adapt to the geometry of the dataset.
ball
TRADES
(a) region diagram
natural
uniform ball
(d) nor-Voronoi region
Figure 4: (a) A diagram showing the difference between the sub- Voronoi region (V) and the ball B used to approximate it. In figure (b), (c), and (d), we plot the decision boundary of neural networks trained with natural training, TRADES, and enforcement on the smoothness in V. The yellow examples are the OOD examples, and they are closer to the purple examples. In (b) and (c), we see that the predictions on the yellow examples are not consistent the nearest neighbor; on the other hand, in (d), the yellow examples are predicted as purple.
Sub- Voronoi Region. Can the 1-NN classifier as guide to actively improve NCG score? While we do not see OOD inpuls at training, can encourage all points x that are closer to a training point (x,, Wi) than to any other training point with a different label to be assigned to label In other words, we could set P: to be the Voronoi region of x; in the union of (x;, yi) and all other training points whose labels are different from yt- We call this the sub- Voronoi region of 81) Figure 4a shows an example.
Figures to show how different training methods change the decision regions. Note that the yellow points are never seen during training lesting (they are just for illustration of hypothetical OOD inputs). We draw the decision boundary for three methods natural, TRADES, and training with P. set to the sub-Vorono, region in Equation [ All three perform well on in-distribution examples; however, unlike TRADES, optimizing over the sur-Voronoi region classifies all of the OOD examples with their nearest. categories by putting the purple boundary in the correct. location.
We note that in Figure g we do not claim that one decision boundary is better than the others. Our motivation to see how to increase NCG score through new training method. NCG score measures how well the decision boundary of neural network matches the decision boundary of 1-nearest neighbor classifier
7

---

Published in Transactions on Machine Learning Research (03/2023)
OOD examples. Thus, the sub- Voronoi regions formed by the training examples natural choice of the robust region (because if a classifier has decision boundary that matches the sub- suboVoronoi region, and the label of each region is the same as the training example in that region, then the classifier has 100% NCG score). The reason for examining this property is that if an OOD example is given with no assumption made on these given examples. Then the best thing we can do is to predict this given example with the same label as the closest training example.
3.3 Approximations to the sub-Voronoi region
The loss in Equation is minimized by an iterative procedure. At each iteration, we find the input Pa that maximizes the regularization term. Running this requires being able project onto P; efficiently. While this can be done relatively fast when P. is a constant radius ball, it is considerably more challenging for the sub-Von Voronoi region which is polytope with close to constraints (one for each training point with label * yı). Therefore, we consider three alternative approximations that are faster to project on and can be efficiently implemented during training.
Sub-sampled sub- Voronoi. Here, instead of the sub- Voronoi region, of x, in the full training data, we use the Voronoi cell of x; the union of (x, y:) and a subsample of the training data with labels not equal to y/- Since the sub-sampled sub-Voronoi region can be large, which can cause the network to underfit, we introduce a shrinkage parameter À E [0. 1] to scale down the size of the region.
Ellipsoid. An alternative method is to use an cllipsoidal approximation. Computing the maximum volume ellipsoid inside the region is again challenging. To improve efficiency, we use the following approximation. We pick & differently-labeleed training examples that are closest to X;, learn a PCA on these & examples, and pick the ellipsoid centered at x; and described by the top k/2 principal components. We use a shrinkage parameter À to help generalization.
Non-uniform ball. A final approximation is to use E ball of radius rt, where r, is set to half the distance between x; and its closest training point with different label; this is the largest ball centered at x; that is contained in the sub- Voronoi region. As with the previous methods, with finite training data, this may overestimate the region where we should predict y and hence lead to underfitting; to address this, we again introduce a shrinkage parameter X, sctting P; to B(x,, Xr;). More details about the minimization procodure and each of these alternatives are given in Appendix B
3.4 Experiments on how the robust region affects NCG
We now empirically measure how the role of changing P. affects NCG score on real data. For this purpose, we consider enforcing smoothness in the three lypes of regions discussed above - non-uniform ball, ellipsoid, and sub-sampled sub- Voronoi. We also look at TRADES with three different radii and natural training as basclines. A detailed discussion of the experimental sctup is in Appendix [ Note that we do not aim to achieve the best performance in any given measure, we mostly use standard parameter settings, and we do not use data augmentation.
Results and Discussion. Table 3 shows the train, test, NCG score for MNIST, CIFARIO, CIFAR100 with different unseen categories. All robust methods TRADES and three approximations to sub- vab-Voronoi - have higher NCG score than the natural training. This agrees with our previous observations. Surprisingly, there is a lot of variation in the results. This warrants investigation, but we do not have a clear conjecture as to why certain classes have higher NCG score. For instance, in M-4, the NCG score can be up to 83%, while in M-1, the best is 53%. Perhaps there is visual similarity between some classes of images (e.g., 4s and 9s look alike), or spurious corrclations (Viichh et al. 2021 , or only some datascts have sufficient diversity in examples to "cover" the OOD class (Hein el al.] 2019 Xu et al. 2020). In high dimensional space, it is hard to measure whether some of the unseen classes are more like the training data than others. We later explore the NCG score as function of the distance to the training set. At least pixel space and for color images, we find that closer images are more likely to receive the NCG label. We next consider corrupted images as another source of OOD data.
8

---

Published in Transactions on Machine Learning Research (03/2023)
Table 3: The training, testing and NCG score of networks trained by enforcing smoothness on different regions (pixel space). We use MNIST with digits O, 1, 4, and 9 the unseen classes, CIFAR10 with airplane and deer the unseen classes, and CIFAR100 with aquatic mammals and fruit and vegetables as the unseen classes.
trn acc.
NCG score MNIST-wo0 (M-0)
acc.
trn acc.
tst acc.
NCG score
MNIST-wol (M-1)
sub-voronoi
0.981
0.981
0.474
0.982
0.981
0.376
ellipsoid
0.981
0.981
0.476
0.982
0.980
0.425
ball
0.975
0.973
0.510
0.976
0.973
0.338
TRADES
0.954
0.956
0.485
0.975
0.974
0.528
nat
1.000
0.995
0.390
1.000
0.995
0.273
MNIST-wo4 (M-4)
MNIST-wo9 (M-9)
sub-voronoi
0.982
0.983
0.827
0.988
0.988
0.703
ellipsoid
0.982
0.982
0.820
0.988
0.988
0.725
ball
0.977
0.976
0.795
0.982
0.981
0.711
TRADES
0.988
0.987
0.810
0.962
0.964
0.703
nat
1.000
0.995
0.760
1.000
0.996
0.577
CIFAR10 0000 (C10-0)
CIFAR10-wor (C10-4)
sub-voronoi
0.735
0.658
0.452
0.486
0.482
0.417
ellipsoid
0.671
0.613
0.472
0.483
0.481
0.409
ball
0.794
0.618
0.530
0.871
0.664
0.317
TRADES
0.870
0.660
0.520
0.862
0.643
0.355
nat
1.000
0.900
0.362
1.000
0.886
0.222
CIFAR100-wod (C100-0)
CIFAR1000wwd (C100-4)
sub-voronoi
0.308
0.289
0.241
0.706
0.499
0.207
ellipsoid
0.633
0.478
0.255
0.466
0.385
0.198
ball
0.936
0.517
0.236
0.930
0.489
0.176
TRADES
0.891
0.534
0.264
0.995
0.534
0.193
nat
1.000
0.757
0.169
1.000
0.694
0.140
4 NCG for Corrupted Data
Do the trends that we have seen for NCG also hold for other OOD data besides unseen classes? We consider images with Gaussian noise, blur, JPEG artifacts, snow, speckle, etc (Hendrycks & Dietterichl 2019). We use s_C" to denoted the corrupted version of dataset, e.g., CIFAR10-C (C10-C), CIFAR100-C (C100-C), and ImgNet100+ (T-C), which consists of corrupted images from the CIFAR10 (C10), CIFAR100 (C100), and ImgNet100 (I) datasets. C10-C and C100-C have 18 kinds of corruption, each with 5 corruption levels. I-C has 15 kinds of corruption, each with levels. We consider models trained on regular datasets, C10, C100, and (instead of removing the unseen class). We use corrupted set to refer a corruption type and intensity level. For C10 and C100, there are 90 corrupted sets for cach datasot; for there are 75 corrupted sets. We consider NCG under & distance for both the pixel and learned feature spaces. We train C10, C100, and and measure NCG score C10-C, C100-C, and I-C, respectively; each training method is measured 255 corruption sets.
Results. In both pixel and feature space, we find that all the 255 corruption sets have an NCG score above chance level. For robust models, we find that in the pixel space, TRADES(2) has an NCG score higher than naturally trained models on all 255 corrupted sets. Quantitatively, on average (over the and 75 corrupted sets), TRADES has an NCG score that 1.35 .02, 1.36 .03, and 1.66 + .04 times higher than naturally trained models for CIFAR10, CIFAR100, and ImgNet 100 respectively. Hence, in pixel space, the TRADES

---

Published in Transactions on Machine Learning Research (03/2023)
training procedure leads to much higher NCG score for corrupted data. On the other hand, in the feature space, the results are much less conclusive. In particular, the robust models still have higher NCG score on average, but this does not happen consistently across corruption types or datasets (see Appendix D.7].
Discussion. Our findings in Section 3 extend to these corruptions as the OOD data. In particular, the NCG score of adversarially robust networks is higher on both unseen, natural images, and on corrupted versions of seen classes. On the other hand, in the feature space, the robust models do not have much difference in NCG score from the naturally trained models. The fact that see less variation in the feature space compared to the pixel space is consistent with our results on the unseen classes. The TRADES robust training does not affect the decision regions much when the smoothness is enforced in the feature space. This is likely because the learned embedding has less variation in elements of the same class, and hence, the TRADES training does not contribute as much.
4.1 NCG score vs. test accuracy
Next, we look at the interaction between the NCG and test accuracies, so we also measure the test accuracy on the NCG correct data and NCG incorrect data. We first observe that NCG correct examples are more likely to be correctly classified. To verify that this phenomenon is statistically significant across the board, we perform the one-sided Welch's t-test (which does not assume equal variance) with the mull hypothesis being that the accuracy of NCG correct example is not greater than the accuracy of NCG incorrect example. We set the p-value threshold to 0.05, and the test results are in Table 4 For more details, please refer to Appendix D.3
Table 4: Number of cases where the NCG correct examples have a significantly higher test accuracy than the NCG incorrect examples. 87/90 means that out of the 90 corrupted sets, 87 of them pass the t-lest.
pixel C100
feature C100
C10
C10
natural
87/90
87/90
57/75
88/90
90/90
73/75
(2ADES(2)
84/90
88/90
60/75
89/90
90/90
73/75
5 Discussion and Connections
5.1 Sample complexity of NCG vs. OOD detection
We first observe that NCG is easier problem in theory than OOD detection. Indeed, any time we can detect an OOD example, then be at least as high as the true positive rate for OOD detection.
use the 1-NN classifier to label it. Thus, the NCG score should always
We next theoretically show that the converse is false in general. We prove that there exist cases where maximizing NCG score can be significantly more sample efficient than solving detection problems. OOD detection is hard when certain regions of space have low mass under the input distribution. In this case, it takes many samples to see a representative covering of the support. Prior work has made similar high-level observations in the context of data diversity for robustness and extrapolation (Hein al.) 2019 Xu et al., 2020). In contrast, when the NCG label is the same for nearby regions, then it suffices to see samples from fewer regions and generalize accordingly. We formalize this claim in the following theorem, which identifies simple distributions where detection requires many more samples than NCG. While the proof is not complicated, our result suggests that achicving a high NCG score can be much casier than achieving a good detection rale in some case
Theorem For any e 1/2), d> 1, and C > 2, there exists distributions μ on training ezamples from C classes in d and v on 0OD test eramples from outside of supp(p) such that (i) detecting whether on ezample from p or v requires (CC/c) samples from μe while (ii) classifying eramples from v with their nearest neighhor label from the support of p. requires only log C) samples.
10

---

Published in Transactions on Machine Learning Research (03/2023)
Figure 5 shows intuition for Theorem 1 in the binary case. OOD examples come from outside of the colored cubes. Appendix A has the proof for C classes in Rd
6
1 1-
1- E
Figure 5: An example for Theorem ] The sample frequency is the size of the red/ shapes. With few samples from each large probability region, we determine the NCG label via a large margin solution, but OOD detection requires samples from the small probability regions.
We sketch how to generalize Figure 5 for more classes and higher dimensional data. The idea is that we translate and replicate the binary datasct and increase the regions to d-dimensional cubes. For the distribution H. we have 4C' cubes with side length 1/vd. There will be 2 cubes that have labels from each of the C' classes. The high probability cubes emit samples with probability & (1 - - and the lower probability with & e/C. Due to the side lengths being 1/vd, the 1-nearest neighbor (1-NN) in Eg of the low probability region is paired with an adjacent high probability box, and hence, it is easy to predict given samples from the high probability region. By a coupon collector argument, we see all high probability regions after O(C C)) samples. On the other hand, by the construction of the probability distributions, we need ((C/e) samples for OOD detection, where is the sample probability from a low probability region. For the OOD distribution v, strategically sample points from outside of all of these cubes (while guaranteeing that the nearest neighbor labels are still correct). Thus, OC'log C*) samples are sufficient for NCG, but (CC/c) are needed for OOD detection.
This result suggests that there are cases where OOD detection is extremely sample inefficient and cannot be done well. In these cases, the model will have to give a prediction on examples that it does not expect. Thus, it would be crucial to understand how the model predicts these examples.
As a concrete example, we train model on MNIST images of 0-8 and use the model for prediction on images of 9s. We also train an OOD detector ODIN (Liang et al. 2018) which has a .951 true positive rate and .855 false negative rate. In this example, many images of 9s cannot be easily picked out by OOD detectors and will be treated as in-distribution examples. Thus, is important to know what kind of prediction will be given these 9s. From our previous result, we find that many Is are predicted as 4s, and this can be explained by nearest category generalization.
5.2 When do we have higher NCG scores?
One hypothesis is that OOD examples that are further from the training set are less likely to be predicted with the NCG label. To check this hypothesis, we conduct the following experiment. We bin the OOD examples based on their distance to the closest training example into 5 equal size bins, and we evaluate the NCG score in each bin. A typical result shown in Figure 6 (additional results are in Appendix D.6.3). We find that the NCG score is generally higher when OOD examples true both for unseen class and for corrupted data (in aggregate). While this is not surprising, it does give more insight into the patterns of OOD data that are labeled with the 1-NN label. We also looked at MNIST, but there was no clear connection between distance and NCG score.
closer to the training examples. This is
It known that OOD detectors perform well when in- and out-of-distrribution data are far away from each other (Liang et al., 2018). This, along with our result, gives us an interesting dynamic, which is that neural networks behave more like the nearest neighbor classifier when detectors perform worse. This also suggests that many of the OOD examples that are misclassified as in-distribution examples could follow the NCG property. It would allow the user to know that even when the OOD detector fails, the model would still output something reasonable. Therefore, if one wants a robust and predictable prediction on OOD data, it can be desirable to have a high NCG score.
Limitation: Choice of the distance metric. We only evaluate l distance in the pixel and feature space. With & distance, we already discovered interesting OOD behavior. However, an important direction is explore other distance measures to understand the prediction patterns. Some options include Eo or cosine
11

---

Published in Transactions on Machine Learning Research (03/2023)
0.7
natural TRACES(2)
6.12
0.08
TRADES22
stro
0.06
AT12)
8.4
A (2)
0.4
61
pos-
0.2
0.00
6.12
7.73
8.01
10.00
12:03
109.2 314.31 151.09 02 206.16
5.55
7.69
9.03
10:30
12:21
600
62.44
124.11
167.37
587.00
150.05
Aug: ded in the dinsed trairing ezample
Aug. f, dst the closent traming nxample
Aug. did. to dloeed trairing example
Avg e 8Z the doseet trin role
(a) CIFARIO-WOO
(b) ImgNet100-woo0
(c) CIFARIO (corrupted)
(d) ImgNet100 (corrupted)
Figure 6: We group OOD examples into five bins based on l2 distance to the closest training example in pixel
space. (a) and (b) show the NCG score of each bin on the unseen class of CIFAR10 and ImgNet100-woo. (c) and (d) the NCG score of each bin on the aggregate corrupted data of CIFARIO and ImgNet100. The downward trend seen here is not as apparent in the feature space (see Appendix D.6.3
distance measuring distance in embedding space of an auto-encoder. Ideally, the distance measure would capture perceptual similarity of the images. This would imply that NCG score corresponds to how humans may predict an unseen class. However, it is not clear if such a perceptual metric exists for images.
6 Conclusion
We examine out-of-distribution (OOD) properties of neural networks and uncover intriguing generalization properties. Neural networks have a tendency of predicting OOD examples with the labels of their closest training examples. We measure this via new metric called NCG score. Robust networks consistently have higher NCG score than naturally trained models. We replicate this result for two sources of OOD data (unscen classes and corrupted images), and we experiment with a variety of new and existing robust training methods. This is surprising because the OOD data are much further away in & distance than both the robustness radius and the nearest adversarial examples. Therefore, the robust training procedure is changing the decision regions on parts of space that are not directly considered in the loss function. We posit that this behavior and the higher NCG score is a consequence of the inductive bias of robust networks. In the future, it would be interesting to evaluate NCG for other training methods, architectures, and sources of OOD data like distribution shift or spurious correlations. Overall, NCG can be valuable and scalable addition to the toolbox of evaluation metrics for OOD generalization.
Acknowledgments
We thank Angel Hsing-Ch Hwang, Hanie Sedghi, Mary Anne Smart, and Otilia. Streteu for providing thoughtful comments the paper. Kamalika Chaudhuri and Yao- Yuan Yang thank NSF under CIF 1719133, NSF under CNS 1804829, and ARO MURI W911N72110317 for support. This work was also supported in part by NSF I1S1763562 and ONR Grant, N000141812861.
References
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks 2016.
with rectified linear units. arXie preprint
Randall Balestriero, Jerome Pesenti, and Yann LeCun. Learning in high dimension always amounts to extrapolation. arXiv preprint arXi::2110.00 10.09485, 2021.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable atlacks against black-box machine learning models. arXiv preprint arXiv:1712.042// 2017.
Wieland Brendel, Jonas Rauber, Matthias Kümmerer, Ivan Ustyuzhaninov, and Matthias Bethge. Accurate, reliable and fast robustness evaluation. arXiu preprint arXio:1907.01009, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 icee symposium security and privacy (sp), pp. 37-57. TEFE, 2017.
12

---

Published in Transactions on Machine Learning Research (03/2023)
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. ar preprinl arXiv:1902.06705, 2019.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data improves adversarial robustness. arXiv preprint arXiv:1905.13744 2019.
Stephanie CY Chan, Ishita Dasgupta, Junkyung Kim, Dharshan Kumaran, Andrew K Lampinen, and Felix Hill. Transformers generalize differently from information stored in context vs in weights. orXiv preprint arXiu:2210.05671, 2022.
Minhao Cheng, Simranjit Singh, Patrick Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsich. Sign-opt: A query-efficient hard-label adversarial attack. arXiv preprint XrXiv:1909. 107719999.1777,, 2019.
Minhao Cheng, Qi Lci, Pin-Yu Chen, Inderjit Dhillon, and Cho-Jui Hsich. Cat: Customized adversarial
training for improved robustness. arXiv preprint arXiv:200200678) 2020.
Ekin Dogus Cubuk, Barret Zoph, Jon Shlens, and Quoe Le. Randaugment: Practical aulomated data augmentation with reduced search space. Advances in Newral Information Processing Systems, 33, 2020.
Ishita Dasgupta, Erin Grant, and Tom Griffiths. Distinguishing rule and exemplar-based generalization in lcarning systems. In International Conference on Machine Learning, pp. 4816-4830. PMLR, 2022.
Akshay Dhamija, Manuel Gunther, Jonathan Ventura, and Terrance Boult. The overlooked elephant object detection: Open set. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 1021-1030, 2020.
Logan Engstrom, Andrew Tlass Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019. URL
Robert
Geirhos, Jorn-Henrik Jacobsen, Claudio Michaclis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix Wichmann. Shorteut learning in deep neural networks. Nature Machine Intelligence, 2(11): 665-673, 2020.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference on Machine Learning, pp.
PMLR, 2019.
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 pattern recognition, pp. 770 778, 2016.
Matthias Hcin, Maksym Andriushchenko, and Julian Bitterwolf. Why ReLU networks yield high-confidence predictions far away from the training data and how to mitigate the problem. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 41-50, 2019.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. Proceedings of the International Conference on Learning Representations, 2019.
Charles Herrmann, Kylc Sargent, Lu Jiang, Ramin Zabih, Huiwen Chang, Ce Liu, Dilip Krishnan, and Deqing Sun. Pyramid adversarial training improves vit performance. orXiv preprinl 1rXim:2111.1512, 2021.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700 4708, 2017.
Jörn-Henrik Jacobsen, Jens Behrmann, Richard Zemel, and Matthias Bethge. Excessive invariance causes adversarial vulnerability. arXiv preprint arXiv:1811.00400 2018
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. arXiv preprint arvi Nll:1702.0874. 2017.
13

---

Published in Transactions on Machine Learning Research (03/2023)
Been Kim, Emily Reif, Martin Wattenberg, Samy Bengio, and Michael C Mozer. Neural networks trained on natural scenes exhibit gestalt closure. Compulational Brain & Behavior, pp. 1-13, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 2014.
Klim Kireev, Maksym Andriushchenko, and Nicolas Flammarion. On the effectiveness of adversarial training against common corruptions. arXiv preprint arXiv:2103. 02325, 2021.
Agustinus Kristiadi, Matthias Hein, and Philipp Hennig. Being bayesian, even just bit, fixes overconfidence in relu networks. In International Conference on Machine Learning, pp. 5436-5446. PMLR, 2020.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. Adversarial machine learning at scale, arXie preprint arXiv:6611001280 2016.
Hyun Kwon, Yongchul Kim, Ki-Woong Park, Hyunsoo Yoon, and Dacscon Choi. Multi-targeted adversarial example in evasion allack on deep neural network. IEEE Access, 4460084440096, 2018.
Shiyu Liang, Yixuan Li, and R Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks. In 6th International Conference on Learning Representations, 1CLR 2018, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint XrXit:1706.0000 2017.
Larry M Manevitz and Malik Yousef. One-class svms for document classification. Journal of machine Learning research, 2(Doc)) 2001.
Alexander Meinke and Matthias Hein. Towards neural networks that provably know when they don't know. arXiv preprint 1XXx::100..11100 2019.
Robert M Nosofsky. Attention, similarity, and the iduttfication-aatggrriiatonn relationship. Journal of experimental psychology: General, 115(1):39, 1986.
Guillermo Ortiz-Jimencz, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Hold me tight! influence of discriminative features on deep network boundaries. ar preprint orXiv:2002.063./ 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, High-performance deep learning library. In Advonces in Neural Information Processing Systems 32, pp. 8024 8035. 2019.
Maithra Raghu, Chiyuan Zhang, Jon Kleinberg, and Samy Bengio. Transfusion: Understanding transfer lcarning for modical imaging. In Advances in neural information processing systems, pp. 3347-3357, 2019.
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: A python toolbox to benchmark the robustncss of machine lcarning models. In Reliable Machine Learning in the Wild Workshop, 34th International Conference on Machine Learning, 2017. URL htt////rriiv.oog///////1/ 04131
Jie Ren, Peter J Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark Depristo, Joshua Dillon, and Balaji Lakshminarayanan. Likelihood ratios for out-of-distribution detection. In Advances in Neural Information Processing Systems, pp. 14707-14718, 2019.
Jeffrey N Rouder and Roger Ratcliff. Comparing categorization models. Journal of Experimental Psychology: General, 133(1):63, 2004.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparamotori- zation exacerbates spurious correlations. In International Conference on Machine Learning, pp. 8346-8356. PMLRR 2020.
14

---

Published in Transactions on Machine Learning Research (03/2023)
Mohammadreza Salchi, Hossein Mirzaei, Dan Hendrycks, Yixuan Li, Mohammad Hossein Rohban, and Mohammad Sabokrou. A unified survey on anomaly, novelty, open-set, and out-of-distribution detection: Solutions and future challenges. arXiv preprint arXiv:2110.1405: 2021.
Hadi Salman, Andrew llyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? arXiv preprint w.Xi:2007.08450 2020.
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopulation shift. arXiv preprinl ar Xrx::000 04859, 2020.
Vikash Sehwag, Mung Chiang, and Prateek Mittal. Ssd: A unified framework for self-supervised outlier detection. arXiv preprint orXiv:2103.1005 2021.
Roger Shepard and Jih-Jie Chang. Stimulus generalization in the learning of classifications. Journal of Experimental Psychology, 65(1):94, 1963.
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6(1):60, 2019.
Chawin Sitawarin, Supriyo Chakraborty, and David Wagner. Improving adversarial robustness through progressive hardening. ar preprint Xiv: 09347, 2020.
Jihoon Tack, Sangwoo Mo, Jongheon Jeong, and Jinwoo Shin. Csi: Novelty detection via contrastive learning on distributionally shifted instances. arXie preprinl arXiv:2007.08177 2020.
Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jörn-Henrik Jacobsen. Fundamental tradeoffs between invariance and sensitivity to adversarial perturbations. In International Conference on Machine Learning, pp. 9561-9571. PMLR, 2020.
Joost Van Amersfoort, Lewis Smith, Yee whye Tch, and Yarin Gal. Uncertainty estimation using single deep deterministic neural network. In International Conference on Machine Learning, pp. 9690 9700. PMLR, 2020.
Jesper E Van Engelen and Holger H Hoos. A survey on semi-supervised learning. Machine Learning, 109(2): 373-440, 2020.
Victor Veitch, Alexander D' D'Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual invariance to spurious correlations: Why and how to pass stress tests. arXie preprint S.l::21060005433 2021.
Yaqing Wang, Quanming Yao, James T Kwok, and Lionel M Ni. Generalizing from few examples: A survey on few-shot learning. ACM Computing Surveys (CSUR), 53(3):1-34, 34,, 2020.
Francis Williams, Matthew Trager, Claudio Silva, Daniele Panozzo, Denis Zorin, and Joan Bruna, Gradient dynamics of shallow univariate relu networks. arXio preprint arXiv:1906.0r 07842, 2019.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanic Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint arXiv:2009.11844 2020.
Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribbtiio detection: A survey. arXiv preprint dr1::21100,1133,, 2021.
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaudhuri. A closer look at accuracy vs. robustness. arXiv preprint arXiu:2003.02460, 2020.
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Advances in neural information processing systems, pp.
2014.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXi::1005.071.. 2016.
15

---

Published in Transactions on Machine Learning Research (03/2023)
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P Xing, Laurent El Ghaoui, and Michael I Jordan. Theoretically principled trade-off between robustness and accuracy. arXiv preprint Xi:::1101 100100801,,,, 2019.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Pazz Paz. mixup: Beyond empirical risk minimization. Xrv preprint 1rXiu:1710.094 12, 2017.
16

---

Published in Transactions on Machine Learning Research (03/2023)
A Proof of the Sample Complexity Separation Theorem
As a warm-up, we prove Theorem for IR and C = 2 classes. We will use this as a building block for the general result.
A.1 Warm-up: binary case
For this special case, the universe for the examples will be the real line IR, and we consider a binary classification task with a third category that only appears in the testing distribution. Let e (0, 1/2) be a parameter. For the training distribution μ,, we define four regions:
Positive, large probability. Let Po = [1. 2], labeled as "+"
Positive, small probability. Let Pi = [3. 4], labeled as *4"
3. Negative, large probability. Let No = [-2, -1]. labeled as "_"
4. Negative, small probability. Let M1 [-4, 4, -3], labeled as "-7
To sample from the training distribution μ, we first set E (-1, randomly with equal probability. Then, we choose i {0, 1}, where = with probability 1 and i with probability c. = 1, sample a point x uniformly from P., and otherwise, if ( 11 we sample uniformly from Ng. Note that with probability e, have that a Po U No. while the probability of sceing any point in Pi W. is only Finally, let A be the uniform distribution on [-6, -5] [], where for V, label it sign(x).
We first argue that nearest category generalization can be efficiently solved. During training time, if we see at least 32 samples from μ, then with probability at least 99% we will see samples from both Po and No, since 1 > 1/2, and we see samples from each class with equal probability. Therefore, once we have at least one sample from each class, we can construct the classifier decides #1 based on the midpoint of the training examples (which will be between -2 and +2 with good probability). Then, on the testing distribution v, we see that all points will be classified correctly with the label of their nearest neighbor in the support of n.
Turning to out-o--distr detection, we claim that 211/cc samples are necessary. Indeed, to distinguish whether a sample comes from or from Pi WN, we must see at least one sample from each of P1 and Mi, since the support v is unknown at training time. As the probability of sampling from Pi or Mi is only e, we will miss one these regions with probability 99% if we have fewer than t t= 1/(100e) samples from μ. Indeed, with probability (1 (1-cl c)* e- = 0.99, we have that all the samples come from Po U No.
A.2 General case
We now provide the proof of Theorem 1 for any number C of classes and for any d > 1 dimensional dataset in Ed with nearest neighbors measured in & distance.
For je (1,2..... C} we define the following centers
dg = 1 + 10j and
df = 3+ 10j
and dz 5 + 10j,
where we naturally embed them in d dimensions by using these as the value of the first coordinate and setting the rest of the coordinates to be zero. In other words, we define a² = a² es, where e is the standard basis vector, that af E .dd
Then, for E (0, 1, and jE (1, C}, we define the following regions, which are cubes centered at the points defined above and have side length 1/Vd. dd Formally, we consider the d-dimensional cubes
1 = faf + (2,, x.) 00 24 & 1/Va].
To sample from the training distribution 14, we first choose & (1.2..... C) uniformly random. Then, we choose i e {0, 13, where i 0 with probability 1 and with probability e. Given our choice of f, we
17

---

Published in Transactions on Machine Learning Research (03/2023)
sample point uniformly from Af. Note that with probability 1 1- c, we have that x Uf- Al. while the probability of seeing any point in U5-1 A2 is only Finally, let be the uniform distribution on Uن- Ag. For both distributions, we label x as j if it comes from A/ for any iE 1,.
Notice that this definition with j = corresponds to the positively labeled regions ([1,2), [3, 4], [5, 6) from the proof of the binary case in the previous subsection. The probabilities are also the same when C' 2.
We explain the key properties of these regions, and then we prove the sample complexity results claimed in the theorem statement. First, for any i E 2, and j E 21. C), if x,y E AL, then |X y < because each A! is a cube with side length 1/vd in Rd.
Next, consider x E A2. We claim that x is closcr to Aá than to any point z E Ab' u A for any j' # j. To see this, we can check that the triangle inequality implies that.
min xx - y yeAg
< 4
while, since the centers satisfy lag- - af' > lag
ag
> 6, we also have that for j' * j,
min
|x
2 b 6.
Zu uA
As a consequence, we have that the nearest neighbor in &g distance for any point E Ai has the same label j as x does. In particular, this implies that we can solve the nearest category generalization problem for points sampled from To do so, we first sample O log C) points from μ., so that by coupon collector argument, we see at least one point from Ai for each j E (1,2...., C). Then, recall that v is supported on the union of Alj over j' E (1.2...., C}. By the above calculations, we have that the nearest neighbor for a point x E Ai is some point from either Ad or A₁. Therefore, since we have sampled at least one point from Age we can correctly determine that x has label j by computing the nearest neighbor in our sampled points. To be more precise, we can compute the multi-class large-margin classifier, where we have sequential decision regions (corresponding roughly to the centers defined above), setting the decision boundaries to be equally spaced between samples from adjacent regions (i.e., the natural generalization of the ID large-margin solution). Importantly, this solution does not require any extra knowledge of the support of μ and because it can be computed directly from the samples (and we have argued that with e log C) samples, we will see all C' classes at least once).
(CClog
We turn our attention to our lower bound, which is that we need at least (CC/c) samples to solve the OOD detection problem. More precisely, we provide lower bound for the number of samples to guarantee that we see that least one point from each region Af for each j E {1, (1, C}. This is a prerequisite for solving the OOD detection problem, because otherwise, we cannot tell whether a point comes from μ or v without prior knowledge of the regions. For the lower bound, we use the same argument as in the binary case in the previous subsection. This implies that we need ((C/e) samples to see one from Af for each fixed j since the probability of sampling from this region is c/C by the definition of μ.
A.3 Alternative generalizations
We could also use "noisy onc-hot encoding" to prove the thcorem, replicating and rotating the 1D datasct log2 C times, to get a subset of Rlog, C for C classes. One dimension is non-zero for each point, and each dimension has points from two possible labels (C total labels). Use 6C regions to define the low probability, high probability, and OOD regions (6 in each dimension with 3 for each class). Again, by coupon collector argument, we will see some point from each of the high probability regions after O log C) samples. This enables nearest category generalization. On the other hand, for OOD detection, we need (CC/e) samples, where e is the sample probability from a low probability region.
Instead of boxes, we could use Gaussian distributions with covariance I² and means shifted by increments of vector, spacing out the means by distance Q(a /Tg(d//)) to get analogous guarantees. Similar ideas
18

---

Published in Transactions on Machine Learning Research (03/2023)
work for Hamming distance 1);; embed regions as intervals in the partial order along a path from 0f to 14, spacing them out to ensure 1-NN properties. In general, there are many metric spaces where we can provide a separation between nearest category generalization and OOD detection by correctly setting up the regions and sampling probabilities. Therefore, we believe it a general phenomena that nearest category generalization a more tractable goal, in terms of sample complexity, than OOD detection.
B More details for algorithm implementation
Minimizing Equation Directly minimizing this loss function is challenging because of the second term; therefore, make some approximations. We compute the inner maximization using the projected gradient descent algorithm (PGD) (Kurakin et al. 2016). PGD is initialized as: x { x,, where x; is the i-th training example. For iteration I, we take a gradient step on x/ with step size a towards maximizing the KL divergence term (formally: x x ((-1) + +oVx (KI.(fo(x())dd fo(x:)), and then project x onto the
(T) region P.. After T iterations, we use x; as the solution to the inner maximization and update the parameter by a stochastic gradient step on ((fo(x;). y.) + (RI.(fa(x fo
Projecting onto different regions. The projection needs to be computationally efficient as we need to project many points onto many regions for each update of the network. Projecting from point to ball is efficient as we can divide the norm of the point and multiply the radius of the ball. The projection onto an ellipsoid can be reduced to a second-order cone program, and the projection onto the sub-sampled sub-Vorone Voronoi region is a quadratic program. Sophisticated solvers for these two types of programs exist, but it can still be difficult when we have a large dataset or the data resides in a high-dimensional space. Fortunately, we only need an approximated solution for these projections. We adopt a binary search method to solve these programs approximately. We perform a binary search between the point that we want to project (x) and the i-th training example (x; that is in P.). We use the point among all the points between x and x; that is the closest to x but within the region P; as the projected point.
Step size of PGD. For both TRADES (uniform balls) and non-uniform balls, we set the step size of PGD to the robust radius r and e: divided by 5. Different from balls, where the distance from the starting point (xs) to the boundary of the region is exactly the same for all directions, deciding the step size for the ellipsoid and sub-sampled sub- Voronoi region can be difficult. We heuristically set the step size for the ellipsoid to be the longest axis of each ellipsoid is divided by 5 As for sub-sampled sub- Voronoi regions, we set the step size as the distance from x, to the furthest linear constraint divided by 5.
B.1 Implementation details for each region
Sub-sampled sub- Voronoi region. We set the number of samples to 100 for MNIST and 50 for CIFAR10 and CIFAR100. Let W,x & h be linear constraint between example x; and an example x, where y, yj. we add the shrinkage parameter À to the constraint as W,x & h, X * Vj-
Non-uniform radius ball. The radius of the ball demaa can be large when examples are far apart. Cheng et al. (0200; Sitawarin et al. (2020) report that enforcing smoothness in a large radius ball can be difficult and proposed methods that can diffuse some of these challenges. We adopt two methods from these works. First, for each example x,, we set its radius 6 = 0 and then gradually incrcase G with a step size n after each epoch. Second, if the prediction within the ball centered at x; with radius e, is not smooth enough, we decrease 4 by 17. We set threshold thresh to determine whether it is smooth enough. The pseudocode is in Algorithm [
Ellipsoid. In practice, we set the number of differently-labeled samples k = 100. Let 8,, V; be the top & singular values and principal components respectively, We search for the shrinkage parameter A between and 500 with binary search and find the largest X; such that the ellipsoid include at most 5% of the k sampled examples. Then, we divide X, by to make sure the ellipsoid from another point does not overlap with the current ellipsoid.
19

---

Published in Transactions on Machine Learning Research (03/2023)
A Algorithm (x,, X, thresh, T
euaar X min 3 dist(x;;,,,)
G 0. e [M] for # epoch do
for i 1..N do
; - f +1 & = max(E; c
0
for j 1..T do
8; signl A (Ro,( + So); project 8, onto ((0,e,) ei) end for
if (xx(fo(x; + 6,), fo(),)) > thresh then 6- "1
end if update 0 to minimize ((fo(x:) v1) + B DKL(fo(x; + (o),((()))
end for end for
C Detailed experiment setups
The experiments are performed on 6 NVIDIA GeForce RIX 2080 Ti and 2 RTX 3080 GPUs located on three servers. Two of the servers have Intel Core i9 9940X and 128GB of RAM and the other one has AMD Threadripper 3960X and 256GB of RAM. We compute nearest neighbors using F (Johnson al.] 2017 and all neural networks are implemented under the PyTorch framework Paszke al. 2019). The code for all
the experiments can be found at https://githh:i
Algorithm implementations. For C&W attack algorithm (Carlini & Wagner 2017 we use the implemen-
tation by foolbox?] I RRuber et al. 2017). For TRADES ZZhagg et al. 2019) we also use the implementation
From the original author
Datasets. All datasets used in our paper can be found in publicly available urls. MNIST can be found in http://yani: lecun. coom/exbbmnnis/// CIFAR10 and CIFAR100 can be found in htttp:://wwwt toronto edu/-kriz/cite .hml Img.et can be found in https::/wwwz imw.e- -attaageeeee..g...
Architechtures. We consider the convolutional neural network (CNN |
wider residual network (WRN-40-
10) Zagoruyko & Komodakis 2016). ResNet50 (He et al. 2016 for our experiments in the pixel space.
Optimizers. We consider stochastic gradient descent (SGD) and Adam (Kingma & Ba 2014 as the optimizers.
MNIST setup. We use the CNN used by Zhang et al. (2099) for training neural networks in the pixel space. The learning rate is decreased by a factor of 0.1 on the 40-th, 50-th, and 60-th epoch. We use the output of the last convolutional CNN output as the extracted feature.
CIFAR10, CIFAR100, ImgNet100 sctup. For CIFAR10 and CIFAR100, we use Wider ResNot (WRN- 40- 10-10) Zagoruyko & Komodakis 2016 for training neural networks the pixel space. For ImgNet100, we use ResNet50 (He et al.J (2016) for training neural networks in the pixel space. The learning rate is decreased by a factor of 0.1 on the 40-th, 50-th, and 60-th epoch. For ImgNet1000, we normalize the data by subtracting the mean (0.485, 0.456, 0.406) and standard deviation (0.229, 0.224, 0.225).
2code and license can be found in http://ttthu.oommmeeecoeeeeeer//
Scode and license can be found in https://githul: http://twwwb..cco//tyttrrr/////e
*code and license can be found hstps://github: http:hhu...cmmbbbbeeeeee www.bbathgeelabboollllooooo
Scode and liceuse can be found astps://github. yaw.ongyodyyy/////oomm IRADES
6CNN is retrieved from public repository TRADES (Zhang
2019
blob/naster/nodels/ httaa//smaaaannppppp1aa
20

---

Published in Transactions on Machine Learning Research (03/2023)
dataset.
MNIST
CIFARIO
CTFAR100
Teg
network structure
CNN
WRN-40-10
WRN-40-10
ResNet50
optimizer
SGD
Adam
Adam
Adam
batch size
128
64
64
128
momentumm
0.9
epochs initial learning rale
70
70
70
70
0.01
0.01
0.01
0.01
# train examples
60000
50000
50000
126689
# test examples
10000
10000
10000
5000
# classes
10
10
20
100
Table 5: Experimental setup for training in the pixel space. No weight decay is applied.
Adversarial attack algorithms. For the adversarial attack algorithms used find the closest adversarial examples, we use a mixture of projected gradient descent (PGD) (Madry et al. 2017), Brendel Bethge attack (Brendel et al. 2019) boundary attack (Brendel et al. 2017). multi-targeted attack (Kwon et al. 2018). Sign-Opt. (Cheng et al. 2019) and C&W algorithm (Carlini & Wagner 2017
C.0.1 Setups for experiments the feature space
Architechtures. We use small networks to compute the embedding into the feature space (Iraining without the unseen class for the unseen class experiments). We continue to use a CNN or WRN for training and prediction. For the feature space, for MNIST, CIFAR10, and CIFAR100, we train multi-layer- perceptron (MLP) with two hidden layers each with 256 neurons and ReLU as the activation function in the train an MLP with two hidden layers each with 1024 neurons and ReLU
feature space. For ImgNet100,, the activation function in the feature space. For all four datasets, use SGD the optimizer with an initial learning rate of 0.01 and momentum of 0.9.
D
Additional experiment results
D.1
Synthetic data
Here, we present several more results on synthetic data showcase how enforcing smoothness onto different regions change the geometry of the decision boundary. From Figure 7 that natural training, in general, has more irregular decision boundary while the other methods That enforce local smoothing have more vertically straight boundaries.
D.2
Extension of Table 3
Table 0 shows the result of four more dataset on top of Table 3 Similar conclusions can be made on these datasets.
D.3 Interaction between NCG score and accuracy on corrupted data
Table 7 ssows an example of the interaction between NCG score and accuracy on the Gaussian noise corrupted data. From the table, we see three things: (1) NCG scores are above chance level, (2) test accuracies on NCG correct examples are higher than the test accuracies on NCG incorrect examples, and (3) the difference between natural training and TRADES are small in the feature space in comparison with the pixel space. This is a typical result, and similar results can be found in other corruption types. These observations are similar to those mentioned in the main text.
21

---

Published in Transactions on Machine Learning Research (03/2023)
a
natural
(b) TRADES
(c) ellipsoid
(d) sub- Voronoi
(e) ball
688
(f) natural
(g) TRADES
(h) ellipsoid
(1) sub- Voronoi
(i) ball
Figure The geometry of the decision boundary with diffcrent algorithms.
Table The training, testing, and NCG score neural networks trained by enforcing smoothness on different regions. Here we consider MNIST with five and eight, CIFAR10 with truck, and CIFAR100 with large man-made outdoor things as the unseen categories.
trn acc.
acc. MNIST-wo5
NCG score trn acc.
acc.
NCG score
MNIST-
sub-voronoi
0.982
0.982
0.628
0.982
0.981
0.513
ellipsoid
0.984
0.983
0.629
0.983
0.981
0.515
ball
0.978
0.976
0.625
0.979
0.976
0.513
TRADES
0.988
0.987
0.618
0.987
0.987
0.497
nat
1.000
0.995
0.505
1.000
0.994
0.416
CIFAR10-Wo9
CIFAR100-wo9
sub-voronoi
0.414
0.409
0.296
0.582
0.455
0.517
ellipsoid
0.519
0.504
0.226
0.658
0.508
0.449
ball
0.813
0.639
0.244
0.896
0.472
0.473
TRADES
0.778
0.641
0.245
0.867
0.515
0.475
nat
1.000
0.885
0.145
1.000
0.703
0.235
D.3.1 Control for distance
From Figure G we observe that a closer distance to the closest training example leads to a higher NCG score. However, the distance to the closest training example could be a confounding factor that leads to the observation of "test accuracies on NCG correct examples are higher than the test accuracies on NCG incorrect examples". To test whether this is the case, we gathered all examples with the same corruption type but different corruption levels, and we binned these examples into five equal-width bins based on their distance to the closest training example. We then measure, in each bin, how many corruption sets have their test accuracies on NCG correct examples significantly higher than the test accuracies on NCG incorrect examples.
The results are shown in Figure S and we labeled each bin from one to five based on their average distance to the closest training examples from the closest to farthest. From the result, we see that except ImgNet100 in the pixel space, in all other cases, the results are similar between different bins. This means that, general, the distance the closest training examples does not affect whether "test accuracies on NCG correct. examples are higher than the test accuracies on NCG incorrect examples" not.
22

---

Published in Transactions on Machine Learning Research (03/2023)
Table 7: Here we show models trained on CIFAR10 and CIFARI00 and evaluate them on the gaussian noise corrupted data. The NCG score, test accuracy, the test accuracy on the NCG correct corrupted examples, the test accuracy on the NCG incorrect corrupted examples, and the distance to the closest training example.
model
natural
(RADES(2)
NCG incorrect tst acc.
NCG correct. tst acc.
NCG incorrect tst acc.
NCG correct tst acc.
corruption level
tst acc.
NCG score
NCG score
dataset
0.76
0.70
0.88
0.34
0.71
0.67
0.78
0.40
2
0.63
0.54
0.82
0.30
0.71
0.66
0.78
0.39
C10
3
0.48
0.39
0.75
0.26
0.70
0.65
0.77
0.39
4
0.41
0.32
0.70
0.24
0.69
0.63
0.77
0.38
5
0.36
0.27
0.66
0.22
0.68
0.63
0.77
0.38
1
0.63
0.56
0.84
0.25
0.52
0.43
0.72
0.30
2
0.55
0.47
0.79
0.24
0.51
0.43
0.71
0.30
pixel
C100
3
0.47
0.39
0.74
0.23
0.51
0.42
0.71
0.30
0.44
0.36
0.71
0.22
0.50
0.42
0.71
0.30
5
0.40
0.33
0.67
0.21
0.50
0.41
0.71
0.29
1
0.42
0.41
0.68
0.04
0.36
0.35
0.51
0.06
2 0.34
0.33
0.64
0.03
0.36
0.35
0.53
0.05
3 0.22
0.21
0.49
0.03
0.34
0.33
0.49
0.05
4 0.12
0.11
0.24
0.02
0.30
0.30
0.45
0.05
5
0.04
0.04
0.07
0.02
0.22
0.22
0.34
0.04
1
0.74
0.39
0.78
0.89
0.72
0.32
0.77
0.89
2
0.59
0.35
0.64
0.85
0.56
0.23
0.62
0.85
C10
3
0.45
0.33
0.48
0.82
0.40
0.19
0.45
0.83
0.39
0.33
0.40
0.81
0.35
0.20
0.38
0.83
5
0.34
0.28
0.35
0.82
0.31
0.18
0.33
0.83
0.60
0.25
0.72
0.74
0.62
0.29
0.71
0.78
2
0.51
0.24
0.63
0.68
0.53
0.29
0.62
0.74
feature C100
3
0.43
0.23
0.54
0.64
0.44
0.25
0.53
0.69
4
0.40
0.22
0.51
0.63
0.40
0.23
0.49
0.67
5
0.37
0.21
0.46
0.61
0.37
0.21
0.46
0.65
0.22
0.18
0.44
0.15
0.21
0.18
0.41
0.16
2 0.19
0.16
0.36
0.14
0.18
0.15
0.34
0.15
3
0.14
0.12
0.26
0.14
0.13
0.11
0.21
0.17
4
0.09
0.08
0.16
0.13
0.08
0.07
0.14
0.16
5
0.05
0.04
0.08
0.14
0.04
0.03
0.08
0.14
D.4
Ablation study
showcases that our discovery are not only observed in our training setup but also extends in other scenarios, repeat our experiment with different network architecture in Appendix D.4..] and models trained by other researchers in Appendix D.4.2
D.4.1 different architecture
We repeat the experiment with a different network architecture DenscNet161 (Huang et al. 2017). Table shows the training, testing, and NCG scores. We see that even with different architecture, robust models still have higher NCG score than naturally trained models.
23

---

Published in Transactions on Machine Learning Research (03/2023)
Table 8: Number of cases where the NCG correct examples have a significantly higher test accuracy than the NCG incorrect examples. 12/15 means that of the 15 corrupted sets, 12 of them pass the t-test with 95% confidence level.
Teature C100
pixel C100
corrupt lvl
C10
C10
18/18
18/18
12/15
18/18
18/18
9/15
2
18/18
18/18
14/15
18/18
18/18
11/15
TRADES(2)
18/18
18/18
14/15
17/18
18/18
10/15
18/18
18/18
14/15
14/18
18/18
10/15
18/18
18/18
15/15
14/18
18/18
3/15
18/18
18/18
13/15
18/18
18/18
12/15
18/18
18/18
13/15
18/18
18/18
12/15
natural
18/18
18/18
13/15
18/18
18/18
12/15
18/18
18/18
14/15
17/18
18/18
12/15
18/18
18/18
15/15
18/18
18/18
9/15
Table 9: Results with 16nseNet161 on CIFARIO and CIFAR100.
natural
AT(2)
TRADES(2)
train acc.
1.000
0.781
0.876
CIFARIO-woO
test acc.
0.839
0.637
0.640
NCG score
0.342
0.487
0.521
train acc.
1.000
0.886
0.557
CIFAR100-wO0
test acc.
0.608
0.500
0.441
NCG score
0.173
0.225
0.271
D.4.2 Pretrained models on corrupted data
To verify that our observations on corrupted data can also be observed by models trained by others, we download pretrained models from https://github.. http:///wwa.......oo..saaa//eaea by [Engstrom et al. (2019). We cannot repeat the experiment for unscen classes since these models are trained the original CIFARI0.
For models in the features space, we follow the same setup in the feature space of CIFAR10, which trains multi-layer perceptron the CNN feature space, but in the feature space of the pretrained model. Table 10 shows three things: (1) the number of cases (out of 90 corrupted sets) where robust models that have an NCG score higher than naturally trained models, (2) the average difference in NCG score between robust networks and naturally trained networks (over the 90 corrupted sots), and (3) the average ratio NCG score between robust networks and naturally trained networks. From the table, we see that robust models with a large enough robust radius in general have larger NCG score than naturally trained models.
D.5 NCG score on in-distribution data
In Section claim that the robust networks are more likely to classify OOD data with the class label of the ncarest training input. One question is, does this phenomena also happen in-distribution data? To answer this question, we measures the NCG score on in-distribution data (which is the test accuracy of a I-nearest. neighbor classifier).
The results are in Table [T From the table, we see that robust training usually produces model that has a slightly higher NCG score. However, seems that these increases on in-distribution NCG score is small. A natural question is, compare to OOD data, these increases in-distribution NCG score are larger smaller.
24

---

Published in Transactions on Machine Learning Research (03/2023)
Table 10: In both pixel and feature space, among the 90 corrupted sets for CIFARIO, the first columns shows the number of robust models that have an NCG score higher than naturally trained network. The second and third column shows the average difference and ratio of the NCG score of the robust models and naturally trained networks (average over the NCG scores on the 90 corrupted sets).
robust natural counts
difference
ratio
pixel
AT().255
51/90
0.00 = 0.05
1.14 + 0.04
CIFARIO
AT(0.5)
86/90
0.14 + 0.10
3.27 + 0.55
AT(1.0)
88/90
0.18 + 0.06
3.09 + 0.22
Teature
AT(1.0)
70/90
0.00 + 0.00
1.01 + 0.00
TRADES(2)
55/90
0.00 = 0.00
1.00 + 0.00
CIFARIO
TRADES (4)
52/90
0.00 + 0.00
1.00 + 0.00
TRADES(S
55/90
0.00 = 0.00
1.00 + 0.00
Table 11: The in-distribution NCG score on different dataset and training methods.
natural
TRADES(2)
TRADES(4)
TRADES(S)
AT(
M-0
0.969
0.971
0.947
0.969
0.970
M-1
0.969
0.970
0.967
0.971
0.971
M-2
0.971
0.972
0.954
0.972
0.973
M-3
0.975
0.976
0.960
0.976
0.976
M-4
0.973
0.976
0.963
0.974
0.975
M-5
0.973
0.975
0.963
0.975
0.974
M-6
0.968
0.971
0.951
0.969
0.970
M-7
0.973
0.974
0.955
0.974
0.974
M-8
0.974
0.974
0.962
0.975
0.975
in-dist NOG
M-9
0.975
0.977
0.960
0.976
0.977
C10-0
0.357
0.410
0.418
0.381
0.403
C10-4
0.379
0.412
0.408
0.352
0.423
C10-9
0.371
0.405
0.407
0.378
0.418
C100-0
0.271
0.316
0.302
0.292
0.311
C100-4
0.261
0.300
0.295
0.279
0.295
C100-9
0.267
0.313
0.302
0.291
0.307
I-0
0.038
0.059
0.058
0.055
0.059
I-1
0.043
0.058
0.060
0.075
0.057
1-2
0.048
0.057
0.058
0.066
0.057
In Table 12
we make such comparison. We count the number of cases (same datasct with different held-out classes) where the increase in NCG score for in-distribution data large than the increase on OOD data by switching from natural training to robust training. We then categorize these results by the dataset and robust training method. From the result, we see that for most of the time, the increase in NCG score OOD data is larger than on in-distribution data. This suggest that the phenomenon of NCG is more prominent on OOD than on in-distribution data.
D.6 Additional results
For completeness, show additional results to the tables figures in the main paper.
25

---

Published in Transactions on Machine Learning Research (03/2023)
Table 12: For both in- and out-of-distrbbution data, the NCG score increase as we switch the natural training robust training. However, the magnitude of the increase larger for OOD data. This table shows the The number of cases where the robust models with higher in-distribution NCG score than natural training. For MNIST check 10 unscen classes, and for CIFARIO, CIFAR100, and ImgNet100, we use 3 unseen classos. 10/10 means that out of the 10 unseen classes, all 10 models have higher NCG score.
M
C10
C100
TRADES(2)
0/10
0/3
0/3
3/3
TRADES (4)
2/10
0/3
0/3
1/3
TRADES(8)
2/10
0/3
0/3
1/3
A2
0/10
0/3
0/3
3/3
D.6.1
Distance to the closest training examples of corrupted data
0.8
0.7
NCG score
NCG score
0.6
0.5
0.4
0.3
0.2
4.5
5.0
5.5
6.0
6.5
7.0
40
45
50
55
65
Avg. distance to the closest training
Avg. 12 distance to the closest training
(a) pixel space
(b) feature space
Figure NCG score of a naturally trained model as a function of the & distance to the closest training example for MNIST with different unseen classes.
Tables
13
to
15
show the average distance to the closest training examples for each corruption type and level.
D.6.2 NCG scores
for each unseen class MNIST with naturally trained models, we show the NCG score and the average distance of the examples in the unseen class the closest training example. Tables 17 to extends Table with the full table of different dataset unseen class pairs in MNIST, CIFAR10, CIFAR100, and ImgNet100.
Figure g
D.6.3 NCG score the distance to the closest training example
Figures and 10 shows the NOG score and the distance to the closest training example for MNIST, CIFARIO, and CIFAR100 in both pixel and feature space. We can see that, in general, the NCG score is higher when in- and out-of-distribution examples are closer each other.
D.7 Additional results for corrupted data
Robust models corrupted data. In the pixel space, average (over the 90 and 75 corrupted sets), robust models have NCG score that is 1.35 + .22 1.36 + .03, and 1.66 + .04 times higher than naturally trained models for CIFAR10, CIFAR100, and ImgNet 100 respectively. In the feature space, we still find that all the 255 corruption sets have an NCG score above chance level, but the NCG scores of the robust models are closer to the naturally trained models. For CIFAR100, we still observe that all robust models have an NCG score higher than the naturally trained models. But for CIFAR10, we find that on only 42 (out of 90) corrupted sets, TRADES(2) models have higher NCG score than naturally trained models. The
26

---

Published in Transactions on Machine Learning Research (03/2023)
Table 13: CIFARIO The average & distance the pixel space to the closest training example. A corruption level O means no corruption is applied, which represents the original test data.
corruption level
3
gaussian
9.21
9.46
9.75
10.13
10.35
10.58
impulse
9.21
9.67
10.10
10.50
11.27
11.97
shot
9.21
9.35
9.49
9.89
10.10
10.49
defocus
9.21
9.01
8.73
8.51
8.38
8.08
motion
9.21
8.73
8.48
8.27
8.27
8.08
zoom
9.21
8.61
8.54
8.45
8.38
8.27
glass snow
9.21
9.29
9.21
8.85
9.28
8.87
9.21
9.48
9.76
10.02
10.15
10.03
fog
9.21
8.02
7.06
6.63
6.50
6.50
contrast.
9.21
7.45
5.68
4.96
4.28
3.44
pixclate
9.21
9.14
9.07
9.04
8.94
8.81
brightness
9.21
9.34
9.49
9.62
9.70
9.69
elastic clastic_transtoon transform
9.21
8.93
8.84
8.65
8.60
8.59
gaussian blur
9.21
9.02
8.51
8.33
8.17
7.88
jpeg compression
9.21
9.20
9.17
9.16
9.14
9.13
saturate
9.21
9.03
9.11
9.68
10.18
10.59
spatter
9.21
9.36
9.59
9.92
9.73
10.02
ppckle__noise
9.21
9.35
9.59
9.75
10.12
10.56
Table 14: CIFAR100 & distance in the pixel space. A corruption level 0 means no corruption is applied, which represents the original test dat
gaussian 9.18
9.42
9.71
10.07
10.29
10.51
impulse
9.18
9.66
10.11
10.53
11.32
12.04
shot defocus
9.18
9.32
9.46
9.84
10.04
10.42
9.18
8.99
8.72
8.52
8.40
8.12
motion
9.18
8.72
8.49
8.30
8.29
8.12
zoom
9.18
8.62
8.53
8.44
8.37
8.24
glass
9.18
9.28
9.21
8.86
9.30
8.90
snow
9.18
9.40
9.62
9.86
9.93
9.72
fog
9.18
8.03
7.07
6.62
6.47
6.43
contrast
9.18
7.47
5.75
5.02
4.32
3.41
pixelate
9.18
9.12
9.06
9.03
8.93
8.81
brightness
9.18
9.30
9.42
9.51
9.56
9.47
elastic transform
9.18
8.99
8.89
8.70
8.64
8.61
gaussian blur
9.18
9.00
8.52
8.34
8.19
7.92
jpeg compression
9.18
9.17
9.13
9.12
9.10
9.08
saturate
9.18
8.88
8.95
9.69
10.13
10.47
spatler
9.18
9.33
9.55
9.86
9.78
10.09
speckle_noiie
9.18
9.32
9.56
9.71
10.08
10.52
average improvement over the naturally trained models in NCG score goes down to 1.00 .00, 1.07 .00, and 1.09 + .01 times for CIFAR10, CIFAR100, and ImgNet respectively.
27

---

Published in Transactions on Machine Learning Research (03/2023)
Table 15: 1m0 & distance the pixel space. A corruption level 0 means no corruption is applied, which represents the original test dat
corruption level
5
contrast
58.92
81.52
68.49
56.77
47.79
45.10
glass
58.92
157.96
154.18
149.79
145.57
138.42
shot.
58.92
164.22
164.39
163.95
162.02
160.25
jpeg
58.92
163.96
163.95
163.85
163.82
163.98
impulsc
58.92
162.38
160.93
159.38
154.99
149.85
elastic
58.92
162.32
162.45
162.30
162.10
161.49
58.92
153.57
150.31
146.04
143.64
139.73
frost
58.92
153.25
131.21
120.42
117.39
112.21
defocus
58.92
154.88
151.06
144.13
139.73
133.87
brightness
58.92
167.31
167.13
163.70
157.28
149.42
snow
58.92
169.97
163.99
169.25
166.42
145.04
pixelate
58.92
162.17
161.71
159.82
157.66
156.16
motion
58.92
157.85
152.94
146.59
140.29
135.60
gaussian 58.92
163.65
163.30
161.90
158.52
152.48
fog 58.92
95.21
91.82
95.09
100.12
103.61
Table 16:
The test accuracy of a 1-nearest neighbor classifier in the feature space 12 different datasets.
M-0
M-4
M-9
C10-0
C10-4
C10-9
C100-0
C100-4
C100-9
I-0
I-1
I-2
0.99
0.99
0.99
0.89
0.88
0.88
0.73
0.73
0.71
0.14
0.14
0.14
D.7.1
Additional results on the slope of corrupted test accuracy
NCG score. Repeating the same experiment with NCG score, we find similar results as well. In the pixel space, for CIFAR10 and CIFAR100, the slope of naturally trained models are significantly smaller than TRADES(2) 15 and 14 (out of 18) corruption types. For ImgNet100, 6 out of 15 corruption types pass the test. The other 9 corruption lypes not significant (they did not accept reject the hypothesis). In the feature space, we also test whether the slopes of robust and naturally trained models are different. For CIFAR1O and CIFAR100, 17 and 15 (out of 18) corruption types, respectively, are not significantly different. For ImgNet100, 13 out of 15 corruption types are not significant.
For reference, we show four selected corruption types on each dataset in Figure 11
28

---

Published in Transactions on Machine Learning Research (03/2023)
Table 17: The train, test, and NCG scores of 10 MNIST datasets and 5 training methods in the pixel space.
natural
AT(2)
TRADES(2)
TRADES(4)
TRADES(S)
Irain acc.
1.000
0.993
0.987
0.954
0.997
MNTST-wo0
test acc.
0.995
0.990
0.985
0.956
0.995
NCG score 0.390
0.457
0.457
0,485
0.402
train acc. 1.000
0.994
0.987
0.975
0.997
MNIST-wol test acc.
0.995
0.991
0.987
0.974
0.994
NCG score
0.273
0.451
0.355
0.528
0.259
Irain acc. 1.000
0.993
0.988
0.958
0.997
MNIST-wo2 test acc.
0.994
0.990
0.987
0.962
0.994
NCG score
0.402
0.532
0.529
0.520
0.452
train acc.
1.000
0.994
0.989
0.962
0.997
MNIST-wo3 test acc.
0.995
0.992
0.988
0.964
0.994
NCG score
0.564
0.659
0.667
0.592
0.538
train acc.
1.000
0.994
0.988
0.963
0.997
MNIST-wod
Lest acc.
0.995
0.991
0.987
0.966
0.995
NCG score
0.760
0.766
0.810
0.758
0.749
train acc. 1.000
0.993
0.988
0.965
0.997
MNIST-wo5
test acc.
0.995
0.990
0.987
0.965
0.995
NCG score 0.505
0.611
0.618
0.616
0.537
train acc. 1,000
0.993
0.987
0.959
0.997
MNIST-w06 test acc.
0.995
0.991
0.987
0.962
0.995
NCG score
0.515
0.551
0.556
0.505
0.538
train acc. 1.000
0.994
0.989
0.962
0.997
MNIST-wo?
test acc.
0.995
0.992
0.990
0.967
0.994
NCG score
0.507
0.672
0.703
0.713
0.594
train acc.
1.000
0.993
0.987
0.966
0.997
MNIST-w08 test acc.
0.994
0.990
0.987
0.966
0.995
NCG score
0.416
0.493
0.497
0.491
0.446
train acc.
1.000
0.996
0.992
0.962
0.997
MNIST-wo!
test acc.
0.996
0.994
0.992
0.964
0.995
NCG score
0.577
0.714
0.691
0.703
0.660
natural
0.7
natural
TRADES(2)
0.25
TRADESI21
NCG soge
0.06
0.3
011
0.1
005
5.11 6.62
7.08
7,54
8.17
6.12 7,73 8.1
10.00
12.03
601
7.65
8.76
0.91
11.00
27 134.31 151 89 271.2 206. 0.00
Avg.1, dst. to the closest training examrot
Avc. f, 0861 the dosest troiningg crample
Avg. clst 10 the descst braining exomple
Avc. 1, de3. to the clocest troinine exarrple
(a) M-O
(b) C10-0
(c) C100-0
(d) 1-0
Figure 9: The NCG score of examples from unseen classes and the distance to the closest training example for MNIST, CIFAR1O, CIFAR100, and ImageNet-100 100 the pixel space.
29

---

Published in Transactions on Machine Learning Research (03/2023)
Table 18: The train, test, and NCG scores of nine different. variations of CIFARIO, CIFARIO0, and ImgNet100 datasets and five training methods in the pixel space.
natural
AT(2)
TRADES(4) TRADES(2)
TRADES(S)
train acc.
1.000
0.999
0.992
0.870
0.878
CIFAR10-wo0
test acc.
0.898
0.729
0.716
0.660
0.761
NCG score
0.355
0.494
0.492
0.520
0.483
train acc.
1.000
1.000
0.990
0.874
0.508
CIF
test acc.
0.886
0.754
0.742
0.700
0.485
NCG score
0.222
0.361
0.333
0.331
0.289
train acc.
1.000
1.000
0.992
0.948
0.778
CIFAR10-Wo9
test acc.
0.885
0.725
0.712
0.732
0.641
NCG score
0.145
0.212
0.192
0.247
0.245
train acc.
1.000
0.998
0.995
0.943
0.902
CIFAR100-wo0
test acc.
0.741
0.554
0.547
0.576
0.607
NCG score
0.175
0.240
0.252
0.252
0.206
train acc.
1.000
0.998
0.995
0.857
0.859
CIFAR100 wood
test acc.
0.743
0.544
0.543
0.492
0.553
NCG score
0.137
0.192
0.191
0.187
0.185
train acc.
1.000
0.996
0.995
0.950
0.527
CIFAR100-wo9
test acc.
0.727
0.547
0.537
0.585
0.431
NCG score
0.222
0.353
0.412
0.427
0.465
train acc.
1.000
0.999
0.994
0.983
0.704
TmgNet100--ee
test
0.529
0.417
0.393
0.354
0.320
NCG score
0.033
0.044
0.041
0.054
0.067
train acc.
1.000
0.999
0.995
0.972
0.783
ImgNet100-wol
test acc.
0.534
0.414
0.385
0.356
0.316
NCG score
0.047
0.049
0.051
0.061
0.072
train acc.
1.000
0.999
0.994
0.971
0.695
1mgNet100-wo2
test acc.
0.537
0.394
0.388
0.353
0.320
NCG score
0.027
0.028
0.033
0.044
0.049
natural
natural
natural
natural TRADES/2)
TRADES2)
TRADES/21
BLY
TRADES/31
0.3
MCB score
0.0
0.5
066
soote
0015
0.4
0.00
0.3
0.2
0.55
00
69.18
54.99 59
55.10
01.15
05.63
3.08
1.21
1.33
1.42
1.59
0.0
1.39
1.54
1.63
1.72
1.00
0.00
1.17
4.4
1.62
1.81
214
Aug. dar.
elosest training meampple pla
Avg. 6 dbbt. the cltwaed training example
Any. ded. the closedd trantin mnammte
Aug
dia. the cinceed twiining Hoam pla
(a) M-O
(b) C10-0
(c) C100-0
(d) I-0
Figure 10: The NCG score examples from unseen classes and the distance to the closest training example for MNIST, CIFAR10, CIFAR100, and ImageNet-100 the feature space.
30

---

Published in Transactions on Machine Learning Research (03/2023)
natural
AT(2)
TRADES(2)
TRADES(4)
TRADES(S)
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wo0
test acc.
0.99
0.99
0.99
0.99
0.99
NCG score
0.28
0.32
0.39
0.49
0.55
Irain test acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wol
0.99
0.99
0.99
0.99
0.99
NCG score
0.14
0.21
0.27
0.50
0.51
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wo2 test acc.
0.99
0.99
0.99
0.99
1.00
NCG score
0.41
0.46
0.53
0.59
0.62
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wo3 test acc.
0.99
0.99
0.99
1.00
0.99
NCG score
0.68
0.71
0.73
0.73
0.74
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wo4
test acc.
0.99
0.99
0.99
1.00
1.00
NCG score
0.78
0.73
0.77
0.81
0.86
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-w05
test acc.
0.99
0.99
1.00
1.00
0.99
NCG score
0.61
0.63
0.65
0.68
0.69
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wor
test acc.
0.99
1.00
1.00
1.00
1.00
NCG score
0.54
0.58
0.60
0.65
0.66
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wo7
test acc.
0.99
0.99
1.00
1.00
1.00
NCG score
0.53
0.54
0.61
0.68
0.67
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-wo8
Lest acc.
0.99
0.99
0.99
1.00
0.99
NCG score
0.46
0.47
0.51
0.56
0.59
train acc.
1.00
1.00
1.00
1.00
1.00
MNIST-w09
test acc.
0.99
1.00
1.00
1.00
1.00
NCG score
0.61
0.71
0.71
0.73
0.79
Table 19: The train, test, and NCG scores of 10 MNIST datasets and 5 training methods the feature space.
31

---

Published in Transactions on Machine Learning Research (03/2023)
Table 20: The train, test, and NCG scores of nine different variations of CIFAR1O, CIFAR100, and ImgNet100 datasets and five training methods in the feature space. We use different radius for AT since not all converge well when the radius is large (r = 2) For CIFARIO and CIFAR100, we use AT(1); for ImgNet100, we use (T(.
natural
(T()5)/(1)
TRADES(2)
TRADES(4)
TRADES(8)
train acc.
1.00
1.00
1.00
1.00
1.00
CIFAR10-w00
test acc.
0.89
0.89
0.89
0.90
0.90
NCG score
0.80
0.83
0.81
0.83
0.83
train acc.
1.00
1.00
1.00
1.00
1.00
CIFAR10-wo4
test acc.
0.88
0.88
0.88
0.89
0.88
NCG score
0.82
0.84
0.82
0.85
0.85
train acc.
1.00
1.00
1.00
1.00
1.00
CTFAR10-w09
test acc.
0.88
0.88
0.88
0.89
0.89
NCG score
0.84
0.89
0.83
0.88
0.87
train
1.00
1.00
1.00
1.00
1.00
C1FAR100-wo0
test acc.
0.72
0.73
0.73
0.74
0.74
NCG score
0.63
0.70
0.69
0.68
0.68
train acc.
1.00
1.00
1.00
1.00
1.00
CLEAR100-wo4
test acc.
0.72
0.73
0.73
0.74
0.74
NCG score
0.69
0.74
0.75
0.73
0.74
train acc.
1.00
1.00
1.00
1.00
1.00
CIFAR100-wo9
test acc.
0.70
0.72
0.72
0.73
0.73
NCG score
0.66
0.74
0.72
0.71
0.71
train acc.
0.99
0.57
0.33
0.98
0.98
ImgNet 100-wo0
test acc.
0.22
0.25
0.26
0.26
0.26
NCG score
0.11
0.16
0.15
0.12
0.13
train acc.
1.00
0.56
0.32
0.98
0.98
ImgNet100-wer
test acc.
0.22
0.24
0.27
0.26
0.25
NCG score
0.13
0.15
0.18
0.14
0.15
train acc.
1.00
0.60
0.33
0.98
0.98
ImgNet100-wo2
test acc.
0.22
0.25
0.26
0.26
0.26
NCG score
0.11
0.15
0.15
0.14
0.14
32

---

Published in Transactions on Machine Learning Research (03/2023)
0.3
C.0
0.7
notural
TRADC312)
1AN
tost cocuree
0.8
0.7
TRADES12)
1.NN
TRADES(2)
0.5
06
0.4
05
TRADESI2)
0.
0.4
I/N
C33
comuption level
comppptio
comuptiin
comppttin
(a) C10 brightness
(b) C10 defocus
C10 elastic transform
(d) C10 Gaussian blur
87
TRADES(2)
natural
0.7
TRADES12)
C.6
TBADES/2)
706
TRACESI2)
1-NN
14N
65
1-NN
1:N
0.5
C.4
0.3
0.3
07
computio
level
corruption
computtoo level
(c) C100 brightness
(1) C100 defocus
(g) C100 clastic transform
(h) C100 Caussian blur
0.30
0.40
0.36
0.31
0.36
0.36
0.35
natural
0:30
0.22
TRADES:2)
NET
0.30
raturall
0.30
natural
0.25
natural TRADESI2)
c.26
TRADESC21
0.28
TRADES(2)
0.30
comrpption lovel
comnupt Invel
cormuption level
lnvel
(i) C10 brightness
(j) C10 defocus
(k) C10 clastic transform
(I) C10 Caussian blur
0.30
0.32
0:30
0.22
0.29
0.30
'.26
scrre
0.28
0.24
0.28
natural
TRAnFS?2)
0.26
natural TRADFS:2)
0.28
TRAIZF(()
natura
C.22
0.00
ratural
0.76
0.24
0.4
0.0
TRADES(21
0,22
corruption level
corrupt on level
corruption level
corruption level
(m) C100 brightness
(n) C100 defocus
(0) C100 elastic transform
(p) C100 Gaussian blur
Figure 11: The slopes of the test accuracy naturally trained models and TRADES(2) on CIFARIO in the
pixel space.
33


Reviews:
[{"review_id": "Cvgs1dUBhl", "reviewer": "Reviewer_Svr8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. Understanding the OOD behaviour of a model is an extremely problem and the attempt in this paper to quantify a form of OOD behaviour with the NCG accuracy metric can be very useful.\n\n2. The paper empirically evaluates the NCG accuracy to gain insights regarding the OOD behaviour of different models. For this purpose, the authors consider a reasonable combination of datasets, models and robust training procedures.\n\n3. Highlighting the global effect on the smoothness of the models trained with local smoothness constraints can be very critical. While it seems like the effect on the global behaviour is usually positive, it is important to understand and quantify this global effect emerging from local constraints since that is an implicit (and at times unintended) effect, and hence can be problematic in some problems and applications.\n\n4. Based on the insights from the experiments, the sub-Voronoi region based local smoothing appears to be a very well-motivated robust training scheme. It seems natural that the size of the local region in the local smoothing constraints should depend on the geometry of dataset and be adaptive instead of being uniform across all training points in the robust training (as in commonly used in adversarial training).\n\n\n### Weaknesses\n\n1. One of the main weaknesses of this paper is the lack of clear connection between the considered NCG accuracy and OOD behaviour. NCG accuracy of a model is related to how smooth a model in all directions. While smoothness is interesting, I do not get a good motivation or intuition as to why NCG accuracy is a good quantification of OOD behaviour. Without this clear connection/motivation/intuition, it is not clear what \"better-than-random\" NCG accuracy of all models or \"improved\" NCG accuracy of robustly trained models (over naturally trained models) mean. NGC accuracy implicitly quantifies smoothness of the model but that does not have any direct relationship to OOD behaviour. If there is any connection between NCG accuracy and OOD behaviour (positive or negative), what would it mean for the 1-nearest-neighbor classifier which has a NCG accuracy of 100%?\n\n\n2. The motivation seems more unclear to me with the discussion in Section 5 regarding \"NCG is an easier problem in theory than OOD detection\". This discussion is not well introduced or positioned in my opinion. First it is not clear what the \"problem of NCG\" is. Is it the problem of increasing NCG accuracy or the problem of computing NCG accuracy? From Theorem 1, NCG seems to mean \"classifying a sample with its 1-nearest-neighbor label\" but that again is not clear in its meaning. It is also not clear if these two problems (NCG vs OOD detection) can even be compared. Increasing NCG accuracy implies creating a model than matches the 1-nearest-neighbor classifier by potentially increasing smoothness of the model is all directions, and this has nothing to do with the properties of the OOD data in any way. OOD detection on the other hand relates to how similar or different the distributions of the in-distribution training data and OOD data are, with OOD detection becoming easier as the OOD data starts becoming more and more different than the in-distribution.\n\n3. For the empirical evaluation with corrupted OOD images, the claim that higher NCG accuracy implies higher test accuracy appears problematic or at least incomplete. The claim that higher NCG accuracy with corruption-based OOD implies higher test accuracy seems to imply that there is an underlying assumption that the 1-nearest-neighbor label in the pixel/feature space is the right label for the corrupted image. Why is that necessarily true? This needs better motivation, and this assumption is orthogonal to the model, and the robust training procedure. If the corruption was large enough to change the class of the 1-nearest-neighbor (in the pixel/feature space), then there would be no clear correlation between the NGC accuracy and the test accuracy.\n\n\n4. It is not clear whether the (approximate) adaptive sub-Voronoi-based locally constrained robust training schemes are a novel contribution. If it is so, it is not clear why are they excluded from the evaluation with corruption-based OOD.\n\n\n5. Finally, the precise contributions of this paper should be clarified better. Right now, it appears that the main contribution is this NCG accuracy metric and its evaluation for various models with some insights. Another partial contribution seems to be the adaptive sub-Voronoi based locally constrained robust training scheme, but this scheme is not thoroughly evaluated, and the results of the partial evaluation do not give a clear picture of its advantage. Even if the NCG accuracy metric is meaningful (which, to me, is currently in question), these contributions appear to be somewhat limited.\n\n\n\n### Questions, Concerns and Comments\n\n\n- Are all global effects of local smoothing positive or neutral or can there be negative global effects?\n\n- Why should we focus on the 1-nearest-neighbour classifier with $\\ell_2$ distance in pixel/feature space as the base model? \n\n- Regarding \"the behavior on OOD data is far from random\", why should we expect the OOD behavior of any trained model to be random?\n\n- Figure 1 is not very clear. How is it related to OOD generalization? The smoothness of the model might be different in different directions (especially in high dimensions), but how does that connect with OOD generalization? The learned model has increased or decreased smoothness is different direction based on the decision boundary it is learning. Moreover, It might be useful to consider the directions where the smoothness increases after robust training (relative to natural training).\n\n- From the empirical results, the authors seem to conclude that on OOD data, the models behave somewhat like a 1-nearest-neighbor classifier. The NCG accuracies are better than random but the raw NGC accuracies are often much too less to say that the model behaves like the 1-nearest-neighbour classifier unless I misunderstand the discussion. Furthermore, the improvement of robust training over natural training (in terms of NCG accuracy) is statistically significant, but the actual increases are still fairly small -- this might imply that the global behaviour is changing but not that drastically since the NCG accuracies of both the natural and robust training would be considered quite low. The results in Figure 6 seem to convey a similar message that the models continue to remain locally smooth -- the NCG accuracy drops as the distance increases. So there is some global effect but it does not appear to be significant.\n\n- Doesn't the difference between pixel space and feature space results boil down to whether we are enforcing smoothness across the end-to-end model or just across the final few layers of the model? In the latter case, it is not surprising that robust training is close to natural since the smoothness enforcement is only on part of the model and hence the effect is somewhat limited.\n\n- Where is figure 4 referenced? It seems to appear out of the blue and not discussed anywhere in the main paper. However, I might have missed something in the text.\n\n- The theorem statement appears incomplete with respect to the role of $\\epsilon$ and $C$ beyond just universal constants -- the sample complexity deteriorates with smaller $\\epsilon$ but it is not clear what tradeoff is present and why one should not just pick $\\epsilon \\approx 1/2$ and get a better sample complexity than that of $O(C \\log C)$. I understand that $\\epsilon$ pertains to the distribution of the data. But the role of $\\epsilon$ needs to be presented rigorously in the theorem statement.\n\n- Why should one consider corrupted data (used in the experiments) OOD especially if the corruption does not change the class of the nearest-neighbor (in pixel/feature space)? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on understanding the behaviour of computer vision models on out-of-distribution (OOD) image data. To this end, the authors propose the Nearest Category Generalization or NCG accuracy metric that measures the match between the prediction of the model and the 1-nearest-neighbor classifier, where the 1-nearest-neighbor is computed using the $\\ell_2$ metric in the input pixel space or some feature space generated by an encoder. This metric appears to implicitly evaluate the \"smoothness\" of the model, with more smooth models having higher NCG accuracy.\n\nUsing this metric and two kinds of OOD image data -- images from unseen classes and corrupted images -- the author empirically demonstrate various properties of different models. The experimental results show that robustly trained models have higher NCG accuracy than naturally trained models, and locally constrained robust training has larger global effect on the smoothness of the model than what the local constraint imposes. For OOD data involving corrupted images, the authors interpret the empirical results to claim that higher NCG accuracy can imply higher test accuracy.\n\nBased on the insights from the experiments, the authors also propose a new form of locally constrained robust training that adapts the size of the \"local region\" based on the geometry of the data, and provide various practical approximations to this form of locally constrained robust training. \n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "To me, addressing weaknesses 1, 2 and 3 are critical for securing my recommendation, with the strong suggestion that addressing weaknesses 4-5 will improve the paper even further and highlight the contributions.\n", "broader_impact_concerns": "There are not ethical implications of this work to the best of my understanding.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UIu6ge9lgk", "reviewer": "Reviewer_TdWQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The paper is well-written and easy to follow.\n- Behavior of robust networks in extrapolation is an interesting and important topic to be investigated.\n- The use of the NCG accuracy for studying OOD prediction is novel.\n- The series of experiments are well-designed and insightful.\n- The connection between NCG and OOD is somewhat surprising and interesting.\n\n### Weaknesses\n- The motivation for studying the NCG accuracy seems weak. I don't see a natural connection between NCG and OOD.\n- There might be a gap from the empirical results to the conclusion that the NCG accuracy is useful for knowing the OOD prediction performance. NCG accuracy positively correlates with OOD prediction accuracy possibly because good classifiers tend to agree with other classifiers. It might be the case that any classifier other than the 1-nearest-neighbor rule, with reasonably high accuracy, has the same property. The presented experiments do not deny this possibility.\n- The connection between NCG and OOD seems to have little practical implications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the behavior of a neural network optimized with adversarially robust training on out-of-ditribution (OOD) data. The authors empirically investigate how often the prediction given by a robust network and the label of the nearest training data agree with each other. This frequency of agreement is referred to as Nearest Category Generalization (NCG) accuracy. The results suggest that the NCG accuracy is consistently beyond the chance level, robust networks have much higher NCG accuracy than ordinarily trained networks, and in the context of prediction on corrupted examples, the NCG accuracy and the prediction accuracy have positive correlation. The paper also provides a theoretical analysis, which says that NCG is much easier than OOD detection in terms of sample complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Regarding the second weakness in the Strengths And Weaknesses section, it would be nice if the authors could show some classifier(s) other than the 1-nearest-neighbor rule do not have the property observed for NCG. That would indicate that the metric based on NCG is special in OOD prediction.\n- In the paragraph about \"Distance Metrics for NCG,\" the paper mentions, \"we believe the $\\ell_\\infty$ results would be similar.\" I wonder why we would be particularly interested in $\\ell_\\infty$. Also, what makes the authors believe so?\n- In the setup of Section 3, is the scale of the robustness radii (0.5, 1, 2, 4, 8) small enough?\n- In Table 1, what does the row AT(2)/(1)/(.5) refer to?\n- In Table 1 and 3, the scores for \"natural training\" seem very different. Why?", "broader_impact_concerns": "I do not have any concern with this paper about broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KXoXQbIQfQ", "reviewer": "Reviewer_eC2G", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. Significant experimental evaluations: The authors provide experiments with two types of OOD data with standard adversarial training methods. Remarkably, they provide statistical tests to support the validity of the significance of the experimental results to conclude NCG accuracy is higher for robust networks.\n2. The Voronoi tessellation perspective of robust training: After Section 3.2, the authors discuss how different robustness region in robust training influences the resulting performance and consider the sub-Voronoi region, which seems to be a reasonable choice. This robustness region may not have been discussed so far partially because the computation is challenging. The authors discuss some approximation methods, which are appealing.\n\n## Weaknesses\n1. Motivation is slightly unclear: The main result of this paper is to reveal a correlation between network robustness and NCG accuracy. However, I am not fully motivated because OOD data may contain unseen classes in the training phase and thus 1-NN accuracy occasionally disregards those unseen classes because 1-NN classifies any input to a known class label. Despite that the correlation seems interesting, it is unclear how NCG accuracy is helpful as an OOD detection measurement.\n2. Discussion in Section 3.1 would be a little bit confusing: In Section 3.1, the authors discuss why robust models have higher NGC accuracy and suppose that robust models may have better local smoothness and hence the predictions are locally consistent. Hence, I suppose that the authors would like to claim that OOD data tend to fall in the local balls of the training data and they are classified correctly. However, the experiments in the latter part of this section reveal that OOD data are consistently farther than the worst-case adversarial examples surrounding the training data. Though this result is somewhat intuitive, it does not seem to support higher NCG accuracy for OOD data. In other words, how the local smoothness behavior is extended to the global behavior still remains unclear. Can the authors give a little bit more discussion in this regard?\n3. The illustrative example in Figure 3 would be misleading: The illustration in Figure 3(d) seems to support the superiority of the sub-Voronoi region in the sense that we may obtain a better boundary without crossing over OOD data using this robustness region. However, what if the yellow OOD cluster is located at a slightly more right region? The sub-Voronoi region seems to induce a boundary that crosses such OOD data. That being said, the goodness of the robustness region would depend on the nature of OOD data significantly. This would be one of the reasons why several robustness regions compared in Table 3 are comparable to each other. This perspective could be further discussed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper points out that robust neural networks (such as ones trained with adversarial training and TRADES) exhibit better out-of-distribution generalization in the sense that their predictions align well with 1-nearest neighbor labels. This behavior motivates a new metric called NCG to measure OOD generalization. The authors simulate two kinds of OOD data: unseen classes and corrupted data. The robust networks admit better NCG accuracy when evaluated with these two OOD data. It is then discussed that robust networks generalize well on OOD data because their local smoothness would be extended well to OOD data. The proposed metric could be used as a cheap proxy for OOD detection.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major requests are presented in the above \"weaknesses\".\nBelow, I leave a few minor ones.\n\n- In the last paragraph of Section 1.2, the authors argue \"the NCG behavior is a consequence of the inductive bias produced by neural networks,\" which seems to lack further discussion. What kind of inductive biases do you suppose in this context?\n- In the first line of Section 3, does WRN stand for Wide-ResNet?\n- In the second line of Section 4.1, I do not see a clear meaning of \"NCG correct data\" and \"NCG incorrect data\". May I ask the authors to provide their formal meanings? Given that, the results in Section 4.1 can be better understood.\n", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an interesting metric to measure the OOD behaviour of models by measuring a surrogate for the smoothness of the model. This metric is evaluated for various different training schemes and different forms of OOD samples, highlight some insights, such as (i) adversarially trained models have increased smoothness relative to naturally trained models far beyond the robust radius, and (ii) models with higher smoothness tend to have higher testing accuracy of OOD data generated via corruption. However, there are some following issues to be addressed carefully, based on the valuable comments from three qualified reviewers.

1) According to Reviewer Svr8, the metric and it's properties need improved motivation and explanation and many things are unclear to a reader (see our reviews and discussions). Furthermore, various interpretations of empirical results do not appear to be well supported by the actual results, necessitating improved presentation of the results.

2) According to Reviewer TdWQ, 
2.1) "NCG accuracy provides a new way to evaluate training methods on unlabeled data that cannot be labeled using other information": If "evaluate" means to measure some goodness, this might be an overstatement.
2.2) "This indicates that having higher NCG accuracy may be a desirable property, as it can encourage better predictions on corrupted data.": This sentence sounds like the causal statement that "making NCG accuracy higher leads to better predictions on corrupted data." This is not confirmed by the presented experiments. Consider adding experiments or adjusting the statement.
2.3) "Nonetheless, they both suffice to provide insight into the OOD prediction behavior of robust and normal networks." This sounds as if there were nothing further to be studied.
2.4) Consider rephrasing "accuracy" in the term "NCG accuracy". Accuracy sounds like a goodness measure of performance on a task that we wish to solve.
2.5) "NCG can be much easier" than OOD detection: This can mean the OOD detection problem cannot be reduced to NCG. If so, that would be a contradiction. Please consider adding comments on that.

3) According to Reviewer eC2G, the manuscript does not fully support the validity of NCG accuracy. The authors claim "robust networks are more likely to classify OOD data with the class label of the nearest training input", which seems a reasonable claim given the experimental results. However, robust networks could classify in-distribution data with the class label of the nearest training input as well. If this happened, NCG accuracy would not be sufficiently informative to probe OOD data. I would like to see whether this actually happens or not if possible.

Hence I recommend **major** revisions, altough TMLR systems can only show **minor** revisions. We do hope that the authors can carefully respond the above comments one by one and upload a updated version for the further check. 

Decision: Accept (poster)