Towards neural networks that provably know when they don't know
Authors: Alexander Meinke
Matthias Hein
Venue:  (2020)

Abstract: It has recently been shown that ReLU networks produce arbitrarily over-confident predictions far away from the 
training data. Thus, ReLU networks do not know when they don't know. However, this is a highly important property in safety
critical applications. In the context of out-of-distribution detection (OOD) there have been a number of proposals to mitigate this problem but none of them are able to make any mathematical guarantees. In this paper we propose a new approach to OOD which overcomes both problems. Our approach can be used with ReLU networks and provides provably low confidence predictions far away from the training data as well as the first certificates for low confidence predictions in a neighborhood of an out-distribution point. In the experiments we show that state-of-the-art methods fail in this worst-case setting whereas our model can guarantee its performance while retaining state-of-the-art OOD performance.

TOWARDS NEURAL NETWORKS THAT PROVABLY KNOW WHEN THEY DON'T KNOW
Alexander Meinke University of Tübingen
Matthias Hein
University of Tübingen
ABSTRACT
It has recently been shown that ReLU networks produce arbitrarily over-confident predictions far away from the training data. Thus, ReLU networks do not know when they don't know. However, this is a highly important property in safety critical applications. In the context of have been a number of proposals to mitigate this problem but none of them are able to make any mathematical guarantees. In this paper we propose a new approach OOD which overcomes both problems. Our approach be used with ReLU networks and provides provably low confidence predictions far away from the training data as well the first certificates for low confidence predictions in a neighborhood of an out-distribution point. In the experiments we show that state- of-the-art art methods fail in this worst-case setting whereas our model can guarantee its performance while retaining ofatcoof-the-arr OOD performance
detection (OOD) there
INTRODUCTION
Deep Learning Models are being deployed in growing number of applications. As these include more and more systems where safety a concern, it is important to guarantee that deep learning models work as one expects them to. One topic that has received lot of attention in this area is the problem of adversarial examples, in which a model's prediction can be changed by introducing a small perturbation an originally correctly classified sample. Achieving robustness against this type of perturbation is an active field of research. Empirically, adversarial training (Madry et al. 2018)
performs well and provably robust models have been developed (Hein & Andriushchenko 2017
Wong & Kolter, 2018
Raghunathan et al. 2018 Mirman et al. 2018 Cohen et al. (219)).
On the other end of the spectrum it is also important to study how deep learning models behave far away from the training samples. A simple property every classifier should satisfy is that far away from the training data, it should yield close to uniform confidence over the classes: knows when it does not know. However, several cases of high confidence predictions far away from the training data have been reported for neural networks, c.g. fooling images (Nguyen et al. 2015). for -ff-iii-iitiittiinn (OOD) images (Hendrycks & Gimpel| 2017a) in medical diagnosis (Leibig et al.) 2017). Morcover, it has been observed that, even on the original task, neural networks often produce overconfident predictions (Guo et al., 2017). Very recently, it has been shown theoretically that the class of ReLU networks (all neural networks which use a piecewise affine activation function), which encompasses almost all standard models, produces predictions with arbitrarily high confidences far away from the training data (Hein et al.] 2019). Unfortunately, this statement holds for almost all such networks and thus without a change the architecture one cannot avoid this phenomenon.
Traditionally, the calibration of the confidence of predictions has been considered on the in- distribution (Guo et al. 2017 Lakshminarayanan et al. (0177a). However these techniques cannot be used for detection (Leibig et al. 2017). Only recently the detection of OOD inputs (Hendrycks & Gimpel (017a) has been tackled. The existing approaches are roughly of two types: first, postpro- cessing techniques that adjust the estimated confidence (De & Taylor 2018 Liang et al., 2018)
which includes the baseline ODIN. Second, modification of the classifier training by integrating generative models like a VAE or GAN in order to discriminate out-distribution from in-distribution
data (Lee et al. 2018a; Wang et al. 2018 Lee et al. 2018b) or approaches which enforce low
Coode httphh///gttthbbbbbbbbp
exMe wwweinke/cceve Fied-ccrtee aata--eettai---neeaaanntt

---

1.0
0.9
0.8
0.5
Figure 1: Illustration on toy dataset: We show the color-coded confidence in the prediction (yellow indicates high confidence maxy P(y|=) s 1, whereas dark purple regions indicate low confidence maxy p(y(z) R 0.5) for normal neural network (left) and our CCU neural network (right). The decision boundary is shown in white which is similar for both models. Our CCU-model retains high-confidence predictions in regions close to the training data, whereas far away from the training the CCU-model outputs close to uniform confidence. In contrast the normal neural network is over-confident everywhere except very close to the decision boundary.
confidence OOD inputs during training (Hein et al. 2019 Hendrycks al. 2019). Worst-case aspects of OOD detection have previously been studied in Nguyen et al. (2015); Schott et al. (2018):
Hein al. (211);; Sehwag et al. 2019), but robustness guarantees have yet been proposed for this setting. A generalization guarantee for an out-of-distribute- aware of, it is quite different from the type of
detection scheme is provided in Liu
al. 2018). While this is the only guarantee guarantees we present in this paper. In particular, none of those approaches are able to guarantee that neural networks produce low confidence predictions far away from the training data. We prove that our classifier satisfies this requirement even when we use ReLU networks as the classifier model without loosing performance on either the prediction task on the mi-distribution nor the OOD detection performance, see Figure for an illustration. Moreover, our technique allows give upper bounds on confidence over a whole neighborhood around a point (worst-case guarantees). We show that most state-of-the-arr OOD methods can be fooled by maximizing the confidence in this ball even when starting from uniform noise images, which should trivial to identify. The central difference from existing
is that we have Bayesian framework for in-and out-distribution, where we model in-and ait-iistribution separately. In this framework our algorithm for training neural networks follows directly as maximum likelihood estimator which is different from the more ad-hoc methods proposed in the literature. The usage of Gaussian mixture models as the density estimator is then the essential key to get the desired provable guarantees.
A GENERIC MODEL FOR CLASSIFIERS WITH CERTIFIED LOW CONFIDENCE FAR AWAY FROM THE TRAINING DATA
The model which we propose in this paper assumes that samples from an out-distribution are given to us. In image recognition we could either see the set of all images as a sample from the out- distribution (Hendrycks et al. 2019) or consider the agnostic case where we use use uniform noise on [0, 1]d as maximally uninformative out-distribution. In both settings one tries to discriminate images from images coming from a particular image recognition task and the
these out-distributin task is to get low confidence predictions on the out-distribution images vs. higher confidence on the images from the actual task. From the general model we derive under minimal assumptions a Mexximum-likelihan estimators for in- and out-distribution jointly. As all of these quantities the conditional distribution p(y (r) we get guarantees by controlling the density estimates far away from the training data. This is crucial difference the approaches Le al. (2018s) Sab; Wang et al. (2018): (eendrycks et al. (2019) which empirically yield good OOD performance but are not able to certify the detection mechanism.
approach where one trains both a classifier for the actual task and density
coupled in our model for
2. PROBABILISTIC MODEL FOR IN- AND OUT-DISTRIBUTION DATA
We assume that there exists joint probability distribution p(y. xr) over the in- and out-distribution data, where y are the labels in {I..... ........T M). M is the number of classes, and x E Rd, where d the input dimension. In the following. denote the underlying prohabilities/densittes, with p(y(2:) resp.
2

---

p(z) and the estimated quantities with p(y|z)) and p(x). We are mainly interested in discriminative framework, i.e. we want to estimate p(y|æ) æ) which one can represent via the conditional distribution of the in-distribution p(ylær i) and out-distribution p(u|æ,, o):
p(y|x) ply|z ())( + p(y o)p() plyla, (p(p)()pp))))) + p(yl (
(I)
p()li)p(( + p(z)))(())
Note that at first it might seem strange to have conditional distribution p(y|z, o) for out-distribution data, but until now we have made no assumptions about what in-and out-distribution are. A realistic scenario would be that at test time we are presented with instances from other classes (out-
distribution) for which we expect a close to uniform p(yl2,, o).
Our model for (()) has the same form as p(y](r)
p(ylx) flylar ()) (i) + Hyya o)0(z)o))(())
p (i) + p(x)o)p(o)
Typically, out-distribution data has no relation to the actual task and thus we would like to have uniform confidence over the classes. Therefore we set in our model
1 and 2(y E efv(2)' DE (L, M
efo(a)
p(ylz,
(3)
where f: R - R MM is the classifier function (logits). This framework is generic for classifiers trained with the cross-entropy (CE) loss (as the softmax function is the correct link function for the CE loss) and we focus in particular on neural networks. For a ReLU network the classifier function ff is componentwise a continuous piecewise affine function and has been shown to produce asymptotically arbitrarily highly confident predictions (Hein et al.) 2019), i.e. the classifier gets more confident in its predictions the further it moves away from its training data. One of the main goals of our proposal fix this behavior of neural networks in a provable way.
Note that with the choice of p(y) xr o) and non-zero priors for p(i), p(o). the full model p(y| can be seen as calibrated version of p(ylæz, i). where p(y]z) = p(y]z, i) for inputs with p(æli) >> p(xlo) M if p(x: i) < p(z]l)) However, note that only the confidence in the prediction p(ylar) affected, the classifier decision is still done according to p(y| i) as the calibration does not change the ranking. Thus even if the OOD data came from the classification task we would like to solve, the trained classifier's performance would be unaffected, only the confidence in the prediction would be damped.
and p(ylar [z) 1
For the marginal out-distribution f(roo) there are two possible scenarios. In the first case one could concentrate on the worst case where we assume that p(x(o) is maximally uniformative (maximal entropy). This means that p(x(o) is uniform for bounded domains e.g. for images which are in [0, 1] p(rlo)) 1 for all [0, 1]d, or p(z(o) is a Gaussian for the domain of Rd (the Gaussian has maximum entropy among all distributions of fixed variance). However, in this work we follow the approach of deendrycks et al.) (2019) where they used the 80 million tiny image dataset (Torralbal et al. 2008) as proxy of all possible images. Thus we estimate the density of p(z(o) using this data.
In order get guarantees, the employed generative models for p(arli) and p(zrl)) have to be chosen in a way that allows one to control predictions far away from the training data. Variational autoencoders
(VAEs) (Kingma & Welling) 2014: Rezende et al. 2014), normalizing flows (Dinh et al. 2016 Kingma & Dhariwal, 2018) and generative adversarial networks (GANs) (Goodfellow et al. 2014
are powerful generative models. However, there is no direct way to control the likelihood far away from the training data. Moreover, it has recently been discovered that VAEs, flows and GANs also suffer from overconfident likelihoods (Nalisnick et al., 2019 Hendrycks et al. 2019) far away from the data they are supposed to model as well as adversarial samples (Kos et al. 2017).
For (()o and p(a)() we use Gaussian mixture model (GMM) which is less powerful than a VAE but has the advantage that the density estimates can be controlled far away from the training data:
Kg
M(x,MK)) 20
K,
d(x,))))
d(z, mx)
p(a11))
Σ
Ork exp
p(x(o)
Σ
31 exp
207
(4)
k=
where K2 K2 E IN are the number of centroids and d RRd x R
-
is the metric
d(x,y) = C & (xr - 4)
3

---

with C' being positive definite matrix and
O K, (2 det C)) B1 Ko (2m0f det C)
We later fix as a slightly modified covariance matrix of the in-distribution data (see Section [ for details). Thus one just has to estimate the centroids μa, and the variances o 07. The idea of this metric to use distances adapted to the data-distribution. Note that equation 4 is a properly normalized density in Rd
2.2
MAXIMUM LIKELIHOOD ESTIMATION
Given models for ply (z) and p(x) we effectively have a full generative model and apply maximum likelihood estimation get the underlying classifier p(y|æ, i) and the parameters of the Gaussian mixture models p(z/)), p(arro o).. The only free parameter left is the probability p(i), f(() which we write compactly as À Mo) In principle this parameter should be set considering the potential cost of over-confident predictions. In our experiments we simply fix == 1.
A(a)
E log (((),)) - (p..)))p(a.))
E log (f(yl=)) + log(((x))),
(#.))~((a.))
E log plyla, ()p())))(() + 1 (P(2)o))()) (x,))~((a.))
log (p(x)1)p(1) + ((rlo)p(o)). (5)
((r)))(()) ((z)o)p(o)
In practice, we have to compute empirical expectations from finite training data from the in- distribution (Iz, 11 and out-distribution (z)))21- Labels for the out-distribution could be gen- erated randomly via p(y|z, o) NT but we obtain an unbiased estimator with lower variance by averaging over all classes directly, as was done in Lee et al. 8a); Hein et al. (211)) Heendrycks) al. (2019). Now we can estimate the classifier f and the mixture model parameters μ, V, via
arg max f.p.,a00
Σ 72
1 The
log (p(y))z)) +
A
Σ
log (p(mlz,))
no
M
j=l
1
log
(pg()(z)))
+
log(p(z)))
(6)
74
no
with
p(ulz) pul ()p(()l)) + (a)o) and p(x) x (p(zli) + Ap(2lo)).
p(z]1) Ap(z(o)
Due to the bounds derived in Section we denote our method by Certified Certain Un- certainty (CCU). Note that if one uses standard neural network model with softmax, i.c.
p(ylz) = p(y|),,)) Em= ef then the first term in equation 6 would be the cross-entropy loss for the in-distribution data and the second term the cross entropy loss for the out-distribution data with uniform distribution over the classes. For this choice of p(y(x) and neglecting the terms for p(x) we recover the approach of Hein et al. (2019); Hendrycks et al. (2019) for training classifier which outputs uniform confidence predictions on out-distribution data where p(t)
edu(x)
3(0) corresponds to that
regularization parameter A. The key difference in our approach is that p(y(æ) p(yla, and the estimated densities for in- and out distribution p(z+)) and p(z))) lead to confidence calibration of z(y|z). and in turn the of the classifier influences the estimation of p(ar) i) and p(z(o). The major advantage of our model is that we can give guarantees on the confidence of the classifier decision far away from the training data.
PROVABLE GUARANTEES FOR CLOSE TO UNIFORM PREDICTIONS FAR AWAY FROM THE TRAINING DATA
In this section we provide two types of guarantees on the confidence of classifier trained according model in equation 6 The first says that the classifier has provably low confidence far away
4

---

from the training data, where explicit bound the minimal distance is provided, and the second provides an upper bound on the confidence in a ball around given input point. The latter bound resembles robustness guarantees for adversarial samples (Hein & Andriushchenko (2017: [Wng & Kolter 2018: Raghunathan et al. 2018 Mirman et al. 2018) and is quite different from the purely
empirical evaluation done in OOD detection papers as we show in Section
We provide our bounds for a more general mixture model which includes our GMM in equation Das a special case. To our knowledge, these are the first such bounds for neural networks and thus it is the first modification of a ReLU neural network so that it provably "knows when it does not know" (Hein al. 2019) the sense that far away from the training data the predictions are close to uniform over the classes.
Theorem 3.1. Let (x: :i y be the training set of the in-distributtin and let the model for the conditional probability be given as
(1)
p(ylz) ())((())) + 1)
Vx E Rdd R. EEEEER f1, M).
(8)
p(z(1) + Ap(z)o)
where X =
p(o) p(2)
> O and let the model for the marginal density of the in-distribution p(xr)i) and
out-distribution p(zlo) be given by the generalized GMMs
Kg
d(z,pan)) 20
((x,M))
p(x1i))
Σ
ah exp
p(x1o) = Σ 31 exp
20
K=O
with ak Bi and Pki vn
Idd wk I,... Ki, 1 1, I,..., Ko and d Rd x gd +
R+ a metric.
Let = E Rdd and define k* argmin d(z.pe)
= arg min d(z, s.). il...,
I:....,K; ok
1' = arg max B1 exp I= Im1,..,,K. K.
(-
dlam)) and A 6 1. For any c > 0, ifmmmin 02 > max 0n and 201
2
M
1x ax
mini
d(z, x3) 2 d(xe,, pkx) +d(pu, vr-
+0p-
log
(9)
Br.
then it holds for all m E {l....,M M that
1
p(ml=)= <
M (1 (1)
(10)
In particular, if min, ((2,x,) 0o, then p(ml2) + W
The proof is given in Appendix A Theorem 3.1 holds for any multi-class classifier which defines for each input a probability distribution over the labels. Given the parameters of the GMM's it quantifies which distance of input z to the training set the classifier achieves close to uniform confidence. The theorem holds even if we use ReLU classifiers which in their unmodified form have been shown to produce arbitrarily high confidence far away from the training data Hein et al. (2019). This is first step towards neural networks which provably know when they don't 't know.
In the next corollary, we provide an upper bound on the confidence over a ball around given data point. This allows to give "confidence guarantees" for whole volume and thus is much stronger than the usual pointwise evaluation of OOD methods.
Corollary 3.1. Let xo E Rd and R > 0, then with À
((o) holds p(S)
1 1 + M
max d(
p(ylar) S
M 1+ 6
(11)
X
Eve, as exp
max maxfdleguun R
where Ko Ae exp
2m
(d( 1-
207
The proof is in the Appendix B We show in Section 4 that even though OOD methods achieve low confidence noise images, the maximization of the confidence in ball around noise point (adversarial noise) yields high confidence predictions for OOD methods, whereas our classifier has provably low confidence, certified by Corollary 3.1 The failure of OOD methods shows that the certification of entire regions is an important contribution of CCU which goes beyond the purely sampling-based evaluation.
5

---

EDI
MNIST
FANIST
SVIUN
CIFARI00 CIFARIO
Mog 10125
birdra.5
plane: 0.10
Mointan: 0.33
Figure 2: Adversarial Noise: We maximize the confidence of the OOD methods using PGD in the ball around uniform noise sample (seed images, left) on which CCU is guaranteed by Corollary [3. to yield less than 1.1 maximal confidence. For each OOD method we report the image with the highest confidence. Maha and MCD use scores where lower is more confident (indicated by *). If we do not find sample that has higher confidence/lower score than the median of the in-distribution. we highlight this boldface. All other OOD methods fail on some dataset, see Table [ for a quantitative version. ODIN at high temperatures always returns low confidence, value of 0.1 is not informative.
4 EXPERIMENTS
We evaluate the worst-case performance of various OOD detection methods within regions for which CCU yields guarantees and by standard OOD on MNIST (LeCun et al.) 1998). FashionMNIST (Xiao
et al. 2017), , SVHN (Netzer et al.) 2011), CIFAR10 10 and CIFART00 (Krizhevsky & Hinton 2009). We show that all other OOD methods yield undesired high confidence predictions in the certified low confidence regions of CCU and thus would not detect these inputs as out-distribution For calibrating hyperparameters resp. training we use for all OOD methods the 80 Million Tiny Images (Torralba al. 2008) as out-distribution Hendrycks et al. 2019) which yields fair and realistic comparison.
CCU: As the Euclidean metric is known to be a relatively bad distance between two images we instead use the distance d(x, y) c- v) where C is generated follows. We calculate
the covariance matrix C' on augmented in-distribution samples (see C. Let (A₁, u,)( be the sigenvalues/eigenveeooss of C". Then we set
C max(>; 10-6 maxy X JyJuu
(12)
that is we fix lower bound on the smallest eigenvalue so that C' has full rank. In Hendrycks & Gimpel (2017b) similar metric has been used for detection of adversarial images. We choose K, K. 100 as the number of centroids for the GMMs. We initialize the in-GMM on augmented in-data using the EM algorithm with spherical covariance matrices in the transformed space, in equation 4 For the out-distribution we use subset of 20000 points for the initialization. While, initially holds that Vk. a < 0₁, as required Theorem 3.T. this is not guaranteed during the optimization of equation 6 Thus, enforce the constraint during training by setting: 0 + max ,, 2 max; σ3 at every gradient step. Since the "classifier" and "density" terms in equation have very different magnitudes choose small learning rate of le for the parameters in the GMMs. It is also crucial to not apply weight decay to these parameters. The other hyperparameters are chosen as in the base model below.
Benchmarks: For all OOD methods we use LeNet on MNIST and a Resnet18 (for GAN and MCD use VGG) otherwise. The hyperparameters used during training be found in Appendix

---

Base
MCD
EDL
DE
GAN
ODIN
Maha
ACET
OE
CCU
MNIST
TE
0.5
0.4
0.4
0.4
0.8
0.5
0.9
0.6
0.7
0.6
SR
100.0
99.0
100.0
100.0
43.5
100.0
100.0
0.0
100.0
0.0
AUC
1.4
8.6
0.0
7.3
54.4
0.0
11.7
100.0
35.2
100.0
SVHN FMNIST
TE
4.8
5.8
5.2
4.9
5.7
4.8
4.8
4.8
5.7
4.9
SR
100.0
72.5
100.0
100.0
99.0
100.0
100.0
0.0
100.0
0.0
AUC
0.0
47.1
0.0
0.4
39.5
0.0
18.8
100.0
35.7
100.0
TE
2.9
3.9
3.1
2.4
4.2
2.9
2.9
3.2
4.1
3.0
SR
100.0
73.5
100.0
100.0
0.0
100.0
100.0
3.0
100.0
0.0
AUC
0.0
34.1
0.0
0.0
100.0
0.0
0.0
96.5
0.0
100.0
CIFARIOO CIFAR10
TE
5.6
11.7
7.0
6.7
11.7
5.6
5,6
6.1
4.7
5.8
SR
100.0
90.5
100.0
100.0
100.0
100.0
100.0
0.0
100.0
0.0
AUC
0.0
23.9
0.0
0.0
25.3
0.0
0.0
99.9
0.0
100.0
TE
23.3
45.3
31.1
27.5
43.8
23.3
23.2
25.2
24.7
25.9
SR
100.0
100.0
100.0
100.0
89.5
100.0
100.0
3.5
100.0
0.0
AUC
0.1
17.3
0.0
0.2
15.3
0.0
0.0
95.8
2.5
100.0
Table 1: Worst-case performance of different OOD methods in neighborhoods around uniform noise points certified by CCU. We report the clean test error (TE) on the in-distribution (GAN and MCD use VGG). The success rate (SR) is the fraction of adversarial noise points for which the confidence/score inside the ball is higher than the median of the in-distribution' contidence/score. The AUC quantifies detection of adversarial noise versus in in-distribution. All values in %.
The AUC (area under ROC) is computed by treating in-distribution versus out-distribution two-class problem using the confidence/score of the method as criterion. Alternatively one could report the AUPR (area under precision-recal curve) which we do in Appendix G MCD: Monte- Carlo Dropout (Gal & Ghahramani] (0166) uses dropout at train and at test time. Since it is not clear where put the dropout layers in ResNet, we use VGG instead. We take the softmax from 7 forward passes (Shafaci et al., 2018) and use the mean of the output for prediction and the variance score. EDL: Evidential deep learning (Sensoy al. 2018) replaces the softmax layer of a neural network and introduces a different loss function that encourages better uncertainty estimates. DE: Deep ensembles (Lakshminarayann models that were adversarially trained via FGSM (Goodfellow et al. (015) with step size 0.01. GAN: The framework of confidence-calibaan alongside classifier such that the GAN's generator is encouraged to generate points close to but not on the in-distribution. On these points one then enforces uniform confidence. We used their provided code to train VGG this way, as we were unable to adapt the method to ResNet with an acceptable test error (e.g. TE< 30% on SVHN). ODIN: ODIN (Liang et al. 2017) consists of e/a/T
al. 2017b) average the softmax outputs of five
classifiers (Lee et al., 2017) relies on training a GAN
two parts: a temperature 7 by which one rescales the logits before the softmax layer E. ctr7 and
a preprocessing step that applies a single FGSM-step (Goodfellow et al. 2015) of length before evaluating the input. The two parameters are calibrated on the out-distribution. Maha: The approach in Lee et al.] (2018c) is based on computing a class-conditional Mahalanobis distance in feature space and applying an ODIN-like preprocessing step for each layer. Following Ren al. (2019) we use single-layer version of Lee et al. (2018c) on our networks' penultimate layers because the multi-layer version in the original code does not support gradient-baser attacks. OE: Outlier exposure (Hendrycks et al.) 2019) enforces uniform confidence on large out-distribution. We use their provided code to train a model with our chosen architecture. ACET: Adversarial confidence enhanced training (ACET) (Hein et al. 2019) enforces low confidence an out- aut-distribution by running adversarial attacks during training. order to make the comparison with OE more meaningful
ball around points from
80M tiny images draw the seeds rather than smoothed uniform noise as in Hein et al. (0019). We refer to Appendix F for a discussion of the influence of this choice on the results.
Some of the above OOD papers optimize their hyperparameters on a validation set for each out- distribution they test However, this leads to different classifiers for each out-distribution dataset
7

---

Base
MCD
EDL
DE
GAN
ODIN
Maha
ACET
OE
CCU
FMNIST
97.4
93.1
99.3
99.2
99.4
98.7
96.8
100.0
99.9
99.9
MNIST
EMNIST
89.2
82.0
89.0
92.1
92.8
88.9
91.6
95.0
95.8
92.0
GrCIFAR10
99.7
94.7
99.7
100.0
99.1
99.9
98.7
100.0
100.0
100.0
Noise
100.0
95.2
99.9
100.0
99.3
100.0
97.2
100.0
100.0
100.0
Uniform
95.2
87.9
99.9
97.9
99.9
98.2
100.0
100.0
100.0
100.0
FMNIST
MNIST
96.7
82.7
94.5
96.7
99.9
99.0
96.7
96.4
96.3
97.8
EMNIST
97.5
87.3
95.6
97.1
99.9
99.3
97.5
97.6
99.3
99.5
GrCIFAR10
91.0
92.3
84.0
86.1
85.3
93.0
98.2
96.2
100.0
100.0
Noise
97.3
94.0
95.6
97.4
98.9
98.9
98.9
97.8
100.0
100.0
Uniform
96.9
93.3
95.6
98.3
93.2
98.8
99.1
100.0
97.6
100.0
CIFAR 10
95.4
91.9
95.9
97.9
96.8
95.9
97.1
95.2
100.0
100.0
CIFAR 1O0
94.5
91.4
95.6
97.6
96.1
94.8
96.7
94.8
100.0
100.0
SVHN
LSUN _R
95.6
92.0
95.3
97.9
99.0
96.5
97.2
97.1
100.0
100.0
Imagenet-
94.7
91.8
95.7
97.7
97.8
95.1
96.8
97.3
100.0
100.0
Noise
96.4
93.1
97.1
98.2
96.2
82.7
98.0
95.8
97.8
97.4
Uniform
96.8
93.1
96.5
95.6
100.0
97.9
97.8
100.0
100.0
100.0
SVHN
95.8
81.9
92.3
90.3
83.9
96.7
91.5
93.7
98.8
98.2
CIFARIO
CIFAR LO0
87.3
78.6
87.3
88.2
82.9
87.5
82.8
86.9
95.3
94.2
LSUN CR
91.9
81.3
90.8
92.0
89.9
93.3
89.2
91.2
98.6
98.2
Imagenet-
87.5
78.4
88.2
87.7
84.0
88.1
84.1
86.5
94.7
93.3
Noise
96.5
79.9
88.9
90.3
81.8
97.6
94.4
94.8
97.3
97.0
Uniform
96.8
81.0
89.9
96.6
73.0
98.8
100.0
100.0
98.8
100.0
SVHN
78.8
59.2
80.4
83.2
75.9
81.3
77.5
73.9
93.5
94.2
CIFAR100 10A
CIFARIO IO
78.6
58.9
73.3
76.3
69.3
79.5
59.9
77.2
81.6
80.2
LSUN CR
81.0
59.4
74.2
81.6
79.8
81.4
79.7
78.0
95.4
95,9
Imagenet-
80.8
59.2
76.0
78.2
73.9
81.3
70.8
79.5
83.8
81.4
Noisc
73.4
58.7
65.9
67.5
73.6
76.8
90.6
62.9
86.9
94.6
Uniform
93.3
62.0
29.8
36.6
100.0
93.5
94.3
100.0
99.1
100.0
Table 2: AUC (in- versus out-distribution detection based on confidence/score) in percent for different OOD methods and datasets (higher is better). OE and CCU have the best OOD performance.
which seems unrealistic as we want to have good generic OOD performance and not for particular dataset. Thus we keep the comparison realistic and fair by calibrating the hyperparameters of all methods on a subset of 80M tiny images and then evaluating on the other unseen distributions.
Certified robustness against adversarial noise: We sample uniform noise images as they are obviously out-distribution for all tasks and certify using Corollary [.1 the largest ball around the uniform noise sample on which CCU attains at most 1.1- uniform confidence, that is 1.1% on CIFAR100 and 11% on all other datasets. We deseribe how to compute the radius of this ball in Appendix D In principle it could be possible that the certified balls contain training or test images. In Appendix we show that this is not the case. We construct adversarial noise samples for all OOD methods by maximizing the confidencemmniinizing the score via PGD attack with 500 steps and 50 random restarts on this ball. Further details of the attack can be found in Appendix C.2 In Table show the results of running this attack the different models. We used 200 noise images and we report clean test error on the in-distribution. the success rate (SR) (fraction of adversarial noise points for which the confidence resp. score inside the ball is higher resp. lower than the median of the in-distribution' 's confidence/sccre) and the AUC for the separation of the generated adversarial noise images and the in-distribution based confidence/score. By construction, see Corollary our method provably makes no overconfident predictions but we nevertheless run the attack on CCU as well. We note that only CCU performs perfectly on this task for all datasets all other OOD methods fail at least on one dataset, most of them on all. We also see that ACET achieves very robust performance which may be expected Nevertheless, even though they are very rare, nigh-confidence adversarial noise images for ACET can be found on SVHN, 10 and CIFAR 100 and ACET has no guarantees. We illustrate the generated adversarial noise images for all methods in Figure]
does some kind adversarial training for OOD detection.
8

---

OOD performance: For each dataset and method we report the AUC for the binary classification problem of discriminating in- and out-distribution based on confidence resp. score. The results are shown in Table [ The list of datasets we use for OOD detection can be seen in Table 2 LSUN CR refers to only the classroom class of LSUN and Imagenet- is a subset of 10000 resized Imagenet validation images, that have overlap with
100 classes. The noise dataset was obtained as in Hein et al. (019) by first shuffling the pixels of the test images in the in-distribution and then smoothing them by Gaussian filter of uniformly random width, followed by a rescaling so that the images have full range. GrCIFAR 10 refers to the images in CIFARIO R10 being grayscaled and resized to 28x28 and Uniform describes images sampled uniformly at random from j0. 1 We see that OE and CCU have the best OOD performance. MCD is worse than the base model which confirms the results found in Leibig al. (017)) that MCD is not useful for OOD. DE outperforms EDL but is not much better than the baseline for CIFAR 10 and CIFAR 1000 The performance of Maha is worse than what has been reported in Lee et al. (2018c) which can have two reasons. We just use their version where one uses the scores only from the last layer and we do not calibrate hyperparameters for each test set separately but just once on the Tiny Image dataset. Especially on CIFARIO found that the results depend strongly the step size. The results of ACET, GAN and ODIN are mixed but clearly outperform the baseline. Comparing Table [ and Table 2 we see that most models perform well when evaluating on uniform noise but fail when finding the worst case in small neighborhood around the noise point. Thus we think that such worst-case analysis should become standard in OOD evaluation.
5 CONCLUSION
In Hein et al. (2019) it has recently been shown that ReLU networks produce arbitrarily highly confident predictions far away from the training data, which could only be resolved by a modification of the network architecture. With CCU we present such a modification which explicitly integrates a generative model and provably show that the resulting neural network produces close to uniform predictions far away from the training data. Moreover, CCU is the only OOD method which can guarantee low confidence predictions over a whole volume rather than just pointwise and we show that all other OOD methods fail in this worst-case setting. CCU achieves this without loss in test accuracy or OOD performance. In the future it would be interesting to use more powerful generative models for which one can also guarantee their behavior far away from the training data. This is currently not the case for VAES and GANs (Nalisnick et al. 2019 Hendrycks et al. 2019
ACKNOWLEDGMENTS
The author acknowledge support from the BMBF through the Tübingen AI Center (FKZ: (11S18039A) and by the DFG TRR 248, project number 389792660 and the DFG Excellence Cluster "Machine Learning -New Perspectives for Science", EXC 2064/1, project number 390727645, The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Alexander Meinke.
REFERENCES
H. H. Bauschke and J. M. Borwein. On projection algorithms for solving convex fcasibility problems. SIAM Review, 38:367-426, 1996.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. 1rXiv:1902.02913 2019.
T. DeVries and G. W. Taylor. Learning confidence for out-o--distributiin detection in neural networks. preprint, 100.::1802.04665.1 2018.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv:1605.08803, 2016.
Y. Gal and Z. Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In /CMI., 2016.

---

1. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
IJ Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In NeurIPS, 2014.
C. Guo, G. Pleiss, Y. Sun, and K. Weinberger. On calibration modern neural networks. In ICML, 2017.
M. Hein and M. Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In NeurIPS, 2017.
M. Hein, M. Andriushchenko, and J. Bitterwolf. Why ReLU networks yield high-confidence predictions far away from the training data and how to mitigate the problem. In CVPR, 2019.
D. Hendrycks and K. Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. In ICLR, 2017a.
D. Hendrycks, M. Mazeika, and T. Dietterich. Deep anomaly detection with outlier exposure. In ICLR, 2019.
Dan Hendrycks and Kevin Gimpel. Early methods for detecting adversarial images. In ICLR Workshop Track Proceedings, 2017b.
Dan Hendrycks and Kevin Gimpel. baseline for detecting misclassified and out-of-distribution examples in neural networks. 2017c.
Diederik Kingma and Max Welling. Auto-encoding variational bayes. In ICLR, 2014.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In NeurIPS, pp. 10215-10224, 2018.
Kos, I. Fischer, and Song. Adversarial examples for generative models. ICLR Workshop, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
B. Lakshminarayanam, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In NeurlPS, 2017a
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. NeurIPS, pp- 6402-6413, 20170 2017b.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-232) 1998.
K. Lee, H. Lee, K. Lee, and Shin. Training confidence-cclibraaedd classifiers for detecting out-of- distribution samples. In ICLR, 2018a.
K. Lee, Lee, K. Lee, and Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. In NeurlPS, 2018b.
Kimin Lee, Honglak Lee, Kibok Lee, and Jinwoo Shin. Training confidence-calibrated classifiers for detecting out-of-distribution samples. arXiv:1711.09325, 2017.
Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. In NeurIPS, 7 7167-7177, 2018c.
C. Leibig. V. Allken, M. S. Ayhan, P. Berens, and S. Wahl. Leveraging uncertainty information from deep neural networks for disease detection. Scientific Reports, 2017.
S. Liang, Y. Li, and R. Srikant. Enhancing the reliability of -utto--diitribution image detection in neural networks. In ICLR, 2018.
10

---

Shiyu Liang, Yixuan Li, and R Srikant. Enhancing the reliability of out-of-distribution image detection neural networks. arXiv:1706.0200 2017.
Si Liu, Risheek Garrepalli, Thomas Dietterich, Alan Fern, and Dan Hendrycks. Open category detection with PAC guarantees. In PMLR, 2018.
A. Madry, Makelov, Schmidt, D. Tsipras, and A. Valdu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
M. Mirman, T. Gehr, and M. Vechev. Differentiable abstract interpretation for provably robust neural networks. In ICML, 2018.
E. Nalisnick, A. Matsukawa, Y. Whye Teh, D. Gorur, and B. Lakshminarayanan. Do deep generative models know what they don't know? In ICLR, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. AISTATS, 2011.
A. Nguyen, J. Yosinski, and J. Clune. Deep neural networks easily fooled: High confidence predictions for unrecognizable images. In CVPR, 2015.
A. Raghunathan, Steinhardt, and P. Liang. Certified defenses against adversarial examples. In ICLR, 2018.
Jie Ren, Peter J Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark DePristo, Joshua Dillon, and Balaji Lakshminarayanan. Likelihood ratios for ofdiiiibbbttnn detection. In NeurlPS, 2019.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. 2014.
L. Schott, Rauber, M. Bethge, and W. Brendel. Towards the first adversarially robust neural network model on mnist. preprint, arXiv: 100iv::800.00P 805.09190v3. 2018.
Vikash Sehwag, Arjun Nitin Bhagoji, Liwei Song, Chawin Sitawarin, Daniel Cullina, Mung Chiang, and Prateek Mittal. Better the devil you know: An analysis of evasion attacks using out-of- distribution adversarial examples. preprint, arXiv:1905.01722 2019.
Murat Sensoy, Lance Kaplan, and Mclih Kandemir. Evidential deep learning to quantify classification uncertainty. In NeurlPS, pp. 3179-3189, 2018.
Alireza Shafaei, Mark Schmidt, and James Little. Does your model know the digit 6 is not cat? less biased evaluation of" outlier" detectors. arXiv:1809.047299 2018.
Antonio Torralba, Rob Fergus, and William T Freeman. 80 million tiny images: A large data set for nomparametric object and scene recognition. IEEE transactions on pattern analysis and machine intelligence, 30(1 19588119977 2008
W. Wang, A. Wang, A. Tamar, X. Chen, and P. Abbeel. Safer classification by synthesis. preprint, arXiv:1711.0853442 2018.
E. Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In ICML, 2018.
H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms. preprint, arXiv: (iti::1700.07744:5 2017.

---

A APPENDIX PROOF OF THEOREM 3.1
Theorem 3.1. Let U.) be the training set of the training distribution. We define the model for the conditional probability over the classes y {l,..., M given x as
p(yla) f(yl i)p(z))) + #(10) p(x))) + }p(x)o)
(13)
where X M() > and M > 1. Further, let the model for the marginal density of the in-distribution p(j)
p(x]1) and out-distribution p(z)o) be given by the generalized GMMs
K.
OKk exp (- d(æ,, 1x)²
Ka
d(x, uz)
M(xli)
Σ k=0
p(x(o)) =
Σ 1=0
3r exp
20
207
with ogg 31 > and uis v E Rd
vk = -.....K. 1 I,...,
Ko and d Rdd x Rd + R4 a metric.
Let 2 E Rdd and define k* = arg min d(ap))))
arg min ((2, v;), 1" i=
k= "k
arg min Bi exp (- d(s.m)) and A 287
s. oz.
For any > if miny 01 max dg and
I.
2
1
2
M -
E. ah
min:=1.... d(2, xx) 2 d(xie, m16)) ) d(wu= u-))
+
+0
log
A
VA
A
c)
B1-
(14)
then it holds for all m E (l..... M that
1
p(ml2) 1 M
(1 c).
(15)
In particular, if min, d(z, + oo, then p(mlz) + #
Proof. The proof essentially hinges on upper bounding -(=)) p(ajo) using the specific properties of the
Gaussian mixture model. We note that
p(ylz)= plyl=, ())(()))) + (oroo) p(rli) )
1 1+ M p(r)))
M 1 p(x (t)
1
M 1
piZ
M
A (()
X p(z
The last step holds because the function g(E)
1+ 1+
is monotonically increasing
0g M and
pg
-1
-2 -2
(16)
0g
(1 + E)²
0e
(1+E)3
As the second deriviative is negative for & 2 0, is concave for ę 2 0 and thus
1 1+ ME
ag
I+E =((E)= S ( +
(E -0) = + (M 1)g.
(17)
ac 5=0
In order to achieve the required result we need to show that M-1 plals) away from the training data.
< for x sufficiently far pizlo
We note that
p(x
Es O exp
d(z,az)² 20
max; exp
d(a,un)² 20²
Σx Ork
p
Σ, 31 exp
d(u.M1)²
max Br exp
d(x. )²
201
20
Σn O exp
d(Ir, p(6) )2
d(x, 11- )2
Br-
20
20
12

---

where k. arg min d(a,)))
and 1* arg max 31 exp(
d(z.m)) 207
Using the triangle inequality,
207
d1x S d( Mk-) : get the desired condition
Ex Onk exp Sp.
d( 11- (o-)dd(r,,/,)
+ d(
S
20
287.
8%
20%.
1
Thus we get with a = 200 the quadratic inequality
1 ), b dip and c d 20q.
d = log
B,-
8%
20%
M-1
Ee
- d(x,, pkx- )aa + d(x, pa )b ccsd
where d < 0 for sufficiently small e. We get the solution
b
d
ba
+ max
0,
2a
a
4a
holds, using v + S va + V for a 00
b
0, c c-d d
6²
c
2a
+
max
+
2a
+
V
One can simplify
b
2 87.
d(ux,,
ob. d(px-, ,p.))
d(px. 1/-))
2
a
07-
o
0-
0f. o%h
of.
-
c
o
d(pu,, vV-)2
oh. d d(pkk v2-)2
d d v1-)
2
a 0f.
20
0% ot
07.
Noting that d(x, ) 2 |d(x, x.-) d(z;;, Mk- we get that
d(z,x;,) d(I., pk-) +
implies M- p(al())
p<|p] I The last statement follows directly by noting that by assumption a > 0 (independently of the choice of l* and ky and c, dd(,,,, are bounded as K;, Ko, n are finite. 1 rewrite the required condition as
With A o
2 A
2 A
M M-12 11-1E E ok
d(x, 2 d(sr,Mu)) ) + d(ux- 11-))
+ 0:-
log
_c
Br.
B APPENDIX - PROOF OF COROLLARY 3.1
Corollary 3.1. Let xo E Rdd and R > 0, then with >
plo) holds P(3)
1 1 M
max p(ulz) <
(18)
d R
M 1 1+ b
E or exp
max (al R.O
where b
2n
Ro exp
(d(innarr) R)2
20
Proof. From the previous section we already know that p(y|z) S 1. 1+
M 1+ as long as p(al))
p(=po) <
Now separately bound the numerator and denominator within ball of radius R around z0-
13

---

For the numerator have
K -
dia.ng)
max d(a.2o)
((l
Σ
a
max e d(
201
(19)
k=1
min d(z,aoo gR
d(r,, 1xx)
Oy exp
20
k=
(max {d(us, xo) R2, 03) 20
OC exp
(20)
k=1
where we have lower bounded
min d(0,20)5R
d(r, pk) via the reverse triangle inequality
min d(2,20)5R
((x,114)
2
min
[d(xo: mx) d(x,
d(a,20)5R
min (d(xo: Mk) d(zu, Hol). d(2,20)sR 2 max {d(zo, uR) - r, 0}.
MM max
(21)
The denominator can similarly be bounded via
K.
min d(a.ro)$1
p(x(0)
3t min
2%
(22)
d(a.ro)$
Ke 31 exp
max d(n.2o)SR
d(I, 112
209
1=1
K.
(d( 11) + +R)
B1 exp
(23)
203
1=1
With both of these bounds in place the conclusion immediately follows.
C APPENDIX EXPERIMENTA DETAILS
Unless specified otherwise we use ADAM on MNIST with a learning rate of 1e 3 and SGD with learning rate 0.1 for the other datasets. The learning decrease all learning rates by a factor of 10 after 50, 75 and 90 epochs. Our batch size is 128, the total number of epochs 100 and weight decay is
for the GMM is always le 5. We
5e 4.
When training ACET, OE and CCU with 80 million tiny images we pick equal batches of in- and out-distribution data (corresponding p(i) = p(o)) and concatenate them into batches of size 256. Note that during the 100 epochs only a fraction of the 80 million tiny images are seen and so there is no risk of over-fitting.
C.I DATA AUGMENTATION
Our data augmentation scheme uses random crops with padding of pixels on MNIST and FMNIST. SVHN, CIFARIO and CIFAR 100 the padding width is 4 pixels. For SVHN we fill the padding with the value at the boundary and for CIFAR we apply reflection at the boundary pixels. On top of this we include random horizontal flips on CIFAR. For MNIST and FMNIST we generate 60000 such samples and for SVHN and CIFAR 50000 samples by drawing from the clean dataset without replacement. This augmented data is used to calculate the covariance matrix from equation During the actual training use the same data augmentation scheme in standard fashion.
C.2 ATTACK DETAILS
We begin with a step size of 3 and for each the 50 restarts we randomly initialize at some point in the ellipsoid. Whenever gradient step successfully decreases the losses increase the step size by
14

---

MINIST
FMNIST
CIFARIO
CIFAR100
80
100
0.3
0.4
0.5
8.25
8.50
0.75
9.00
3.6
3.8
4.0
3.6
R
Figure 3: Histograms of bounds: Certified radius in transformed space for different datasets.
a factor 1.1. Whenever the loss increases instead we use backtracking and decrease the step size by factor of 2. We apply normal PGD using the 12-norm in the transformed space to ensure that we stay on the ellipsoid and after each gradient step we rotate back into the original space to project onto the box [0, 1] The result is not guaranteed be on the ellipsoid so after the 500 steps we use the alternating projection algorithm (Bauschke & Borwein, 1996) for 10 steps which is guaranteed to converge point in the intersection of the ellipsoid and the box because both of these sets convex.
D APPENDIX FINDING THE CERTIFIABLE RADIUS
Since Corollary 3.1 does not explicitly give radius, one has to numerically invert the bound. The bound
b(t) = Σk at exp
(- _.axx ( R.0)²
20
(24)
MRn Ko
Bi exp
(d(aro 2i ) n3
20
monotonically increasing in R. Thus, for given sample zo one can fix desired bound max p(xl()= S t/ where v E M) and then find the unique solution
V M
b(R)
X
(25)
for via bisection. This radius it will then represent the maximal radius, that one can certify using Corollary 3.1 The presumption is, of course, that for It 0 one has a sufficiently low bound in the first place, i.e. that a solution exists. our experiments on uniform noise we did not encounter single counterexample this assumption. We show the radii for the different datasets in Figure B
E APPENDIX ANALYSIS OF THE CERTIFIED BALLS AROUND UNIFORM NOISE IMAGES
As observe in Figure the images which maximize the confidence in the certified ball around the uniform noise image are sometimes quite far away from the original noise image. As CCU 1 so the predicted probability certifies low confidence (the maximal confidence is less than 1.1 X J
distribution over the classes is very close to the uniform distribution) over the whole ball, it is natural question what these balls look like and what kind of images they contain. In particular, is in general not desired that the certified balls contain images from the training and test set. For each dataset certified balls around 200 uniform noise images and for each of the certified balls we check if it contains training or test images of the corresponding dataset. We found that even though certified balls are large, not a single training or test image was contained in any of them. This justifies the use of our proposed threat model.
different problem could be that our threshold 1.1 for the certification is too high and that many M predictions the test set have confidence less than this threshold. For this purpose we report in Table 3 the smallest predicted confidence of CCU on the test set T, that is
min 2ET ye yE ())
max p(y(a))
15

---

min p(y)z)
#
<
111 M
%
<
MNIST 33.08
0
0
FMNIST
28.77
0
0
SVHN 10.02
20
0.08
CIFARIO 10.01
529
5.29
CIFARTO0
1.03
130
1.30
Table 3:
Lowest confidence that CCU attains on the test set (in percent) well as total number of test points on which confidence is lower than our imposed bound of L.1
for each dataset and the total number of test samples where the confidence is below L.1 While for Mr
MNIST and FMNIST, this never happens, and for SVHN this is negligible (less than 0.1% of the test set), for CIFARIO and CIFAR 100 this happens in 5.3% resp. 1.3% of the cases.
In theory, this could impair our AUC value for the detection of adversarial noise. However, in practice our bound for the confidence is quite conservative as the bound is only tight in very specific configurations of the centroids of the Gaussian mixture model which are unlikely to happen for any practical dataset, meaning that the actual maximal confidence in the certified region is typically significantly lower. In fact the AUC values of CCU are always 100% which means that for all 200 certified balls the maximal value of the confidence of CCU in any of these balls (found by our PGD attack algorithm) is lower than the minimal confidence of all predictions on the test set as reported in Table 3 On the other hand assuming here also a worst case scenario in the sense we assume that the upper bound of the maximal confidence attained in all 200 certified balls. then the (certified) AUC value would be: 99.92% for SVHN, 94.71% for CIFAR 10, and 98.70% for CIFAR 100. Note that this theoretical lower bound on our performance is still better than all other models' empirical performance on this task, as reported in Table on both CIFAR 10 and CIFAR 100, and only marginally below the perfect AUC of GAN on SVHN.
F APPENDIX PERFORMANCE OF ACET WHEN TRAINED ON ADVERSARIAL UNIFORM NOISE
Similar to our CCU, ACET et al. (2019) requires that one chooses a model for the out-distribution in order to generate their "adversarial noise" during training. We trained the ACET model with the same out-distribution model as for all other models namely using the tiny image dataset as suggested Hendryeks et al. (2019) with PGD attack that starts at the original point and takes 40 FGSM steps in order to maximize the maximal confidence over the classes. We use backtracking and halve the step size whenever the loss does not increase. However, the authors of Hein et al. (2019) used smoothed uniform noise and loo -threat model during training. Since worst case analysis for OOD is based on attacking uniform noise images, this suggests that training ACET with uniform noise should improve the performance of ACET for the worst case analysis. We report below the results of ACET2 (the original model in the paper using tiny images for training is called ACET) based on attacking using uniform noise images during training with a -threat model with 0.3 as suggested in Hein et al. (2019). We report the normal OOD performance in Table 4 and the worst case analysis of adversarial noise in Table 5 While it is not surprising that ACET outperforms ACET2 on the standard OOD detection task in Table during training, the worse performance of ACET2 for the worst case analysis in Table is at first sight counter-intuitive. However, note that the threat model of the attacks in our worst case analysis is the Mahalanobis-type (2-type metric, see 12 while ACET2 uses an 40 atttack model with = 0.3 during training. As the size of the balls for the Mahalanobis-type 12-type metric is quite large, there is not much overlap between the two sets. This explains why ACET2 fails here. In summary, we have shown that by using tiny images as out-distribution during training, ACET improves in terms of OOD detection performance over ACET2, which is similar to the version suggested in Hein et al. (0019).
[ as it has seen more realistic "noise" images
G APPENDIX PRECISION AND RECALL
In addition to the AUC presented in Table 2 we follow Hendrycks & Gimpel 2017c) and report the area under the precision/recall curve (AUPR). Precision specific threshold is defined as the
16

---

MNIST
ACET
ACET2
FMNIST
ACET
ACET2
FMNIST
100.0
99.8
MNIST
96.4
96.5
EMNIST
95.0
93.5
EMNIST
97.6
97.3
GrCIFARIO
100.0
100.0
GrCIFAR10
96.2
91.6
Noise
100.0
100.0
Noise
97.8
97.1
Uniform
100.0
100.0
Uniform
100.0
100.0
SVHN
ACET
ACET2
CIFARIO
ACET
ACET2
CIFARIO
95.2
94.2
SVHN
93.7
82.8
CIFARI00
94.8
93.7
CIFARI00
86.9
85.3
LSUN_GG
97.1
96.1
LSUN_CO CR
91.2
88.5
Imagenet-
97.3
95.6
Imagenet-
86.5
84.8
Noise
95.2
95.2
Noise
94.8
91.2
Uniform
100.0
100.0
Uniform
100.0
100.0
CIFARI00
ACET
ACET2
SVHN
73.9
84.6
CIFARIO
77.2
77.0
LSUN CR
78.0
80.0
Imagenet-
79.5
79.4
Noise
62.9
66.3
Uniform
100.0
100.0
Table 4: OOD detection performance (AUC in percent) for ACET (trained around tiny images) and ACET2 (trained around uniform noise).
ACET
ACET2
MNIST
TE
0.6
0.6
SR
0.0
0.0
AUC
100.0
100.0
FMNIST
TE
4.8
4.6
SR
0.0
0.0
AUC
100.0
100.0
SVHN
TE
3.2
3.0
SR
3.0
95.5
AUC
96.5
5,4
CIFARI0
TE
6.1
7.1
SR
0.0
64.5
AUC
99.9
35.9
CIFART00
TE
25.2
26.2
SR
3.5
96.5
AUC
95.8
14.6
Table 5: OOD detection performance (test error, AUC and success rate in percent) for ACET (trained around tiny images) and ACET2 (trained around uniform noise).
17

---

Base
MCD
EDL
DE
GAN
ODIN
Maha
ACET
OE
CCU
FMNIST
97.5
89.4
99.4
99.4
99.4
98.8
97.0
100.0
99.9
99.9
MNIST
EMNIST
77.9
60.0
77.3
84.5
85.5
78.4
74.4
90.9
91.4
84.3
GrCIFAR10
99.7
91.1
99.8
100.0
99.5
99.9
98.9
100.0
100.0
100.0
Noise
100.0
75.5
99.8
100.0
99.2
100.0
96.5
100.0
100.0
100.0
Uniform
97.2
82.8
99.9
98.8
99.9
98.9
100.0
100.0
100.0
100.0
MNIST
97.6
79.3
95.9
97.5
99.9
99.2
97.2
97.4
97.0
98.3
FMNIST
EMNIST
96.8
74.2
94.6
96.1
100.0
98.9
96.5
97.0
98.6
99.1
GrCIFAR10
92.2
92.7
86.9
90.8
82.3
92.9
98.6
96.8
100.0
100.0
Noise
93.8
78.6
91.6
92.5
95.4
95.4
97.0
95.3
100.0
100.0
Uniform
97.8
93.0
97.1
98.8
95.4
99.1
99.4
100.0
98.2
100.0
CIFARIO
97.2
96.2
98.5
99.2
98.6
97.3
99.0
97.3
100.0
100.0
CIFAR 100
96.7
95.8
98.3
99.0
98.2
96.6
98.8
97.0
100.0
100.0
SVHN
LSUN CR
99.9
99.9
99.9
100.0
100.0
99.9
100.0
100.0
100.0
100.0
Imagenet-
96.8
96.2
98.3
99.1
98.9
96.9
98.9
98.3
100.0
100.0
Noise
89.1
83.6
95.6
96.8
94.5
50.3
97.0
87.3
95.6
93.3
Uniform
98.5
97.0
98.7
98.5
100.0
98.9
99.3
100.0
100.0
100.0
SVHN
92.3
71.1
90.7
87.4
80.5
92.7
85.9
91.0
98.5
97.5
CIFARIO
CIFAR 100
86.3
80.0
89.3
89.8
84.0
85.5
83.4
87.4
95.6
94.6
LSUN CR
99.7
99.2
99.7
99.7
99.7
99.7
99.6
99.7
100.0
99.9
Imagenet-
84.6
79.2
89.8
88.6
84.9
84.2
84.4
85.4
94.8
93.2
Noise
88.1
55.7
70.4
82.7
68.6
87.7
84.9
84.0
93.8
94.7
Uniform
97.8
83.4
94.5
98.0
82.4
99.1
100.0
100.0
99.2
100.0
SVHN
67.4
52.9
72.0
75.6
63.4
71.0
69.1
59.4
89.6
90.8
CIFAR 100
CIFAR
80.9
66.1
75.8
79.1
72.5
81.3
61.2
79.7
84.8
83.7
LSUN CR
99.3
98.3
99.0
99.3
99.2
99.3
99.2
99.1
99.9
99.9
Imagenet-
81.9
67.1
78.8
80.7
76.5
82.0
73.8
80.8
85.3
83.3
Noise
51.0
36.1
34.1
47.8
44.2
56.4
79.5
25.9
69.5
88.9
Uniform
95.6
66.1
53.1
60.0
100.0
96.0
96.4
100.0
99.5
100.0
Table 6: AUPR (in- out-distribution detection based confidence/score) in percent for different OOD methods and datasets (higher is better). OE and CCU have the best OOD performance.
number of true positives (tp) over the sum of true positives and false positives (fp), i.e.
tp
precision
(26)
tp + fp
Recall is defined as
tp
recall
(27)
+ fn
where is the number of false negatives. We report the AUPR for all models and all datasets in T Qualitatively we find that the results do not differ from the ones reported in Table
18


Reviews:
[{"review_id": "Sye38MQptH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper uses a generative model to assign anomaly scores. By its construction, it can provide provable performance guarantees. Experiments do not make unreasonable assumptions such as the ability to peak at the test data, unlike much previous work.\nMy primary concern is that they should show performance on CIFAR-100 not just CIFAR-10, and I certainly hope these experiments will be included during the rebuttal. Overall experimentation is thorough and competently executed, and the proposed technique is sufficiently novel.\n\nSmall comments:\n\n> adv OOD detection with uniform ball perturbed\nThis is a good way of formulating adversarial OOD detection.\n\nA possibly related work is _Early Methods for Detecting Adversarial Images_ (2016) since it uses covariance matrix information for detecting adversarial examples. This paper should cite _Open Category Detection with PAC Guarantees_ by Liu et al. (ICML 2018) since this also involved provable guarantees for OOD detection.\n\nUpdate: my concerns are addressed but my sentiment is still that this is a 6.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygIxqKcYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper provides a method to train neural networks with guarantees on outputting probabilities/scores close to uniform on inputs that are out of domain.\nPrecisely, on some point x_0, we can obtain the largest radius such that on inputs in the ball around x_0 the classifier outputs some predetermined  maximum score. \nThe paper combines a simple generative model (mixture of Gaussian) for modeling in-distribution vs. out of distribution. The simplicity allows to obtain guarantees on the probability of an input being considered out of class. The model output p(y | x) critically uses the probability of being out of distribution. Hence guarantees on being detected as out of distribution translate to guarantees on p(y|x) being close to uniform.\n\nDecision: I vote for accepting the paper. The paper has some clear strengths. However, I have some concerns regarding experiments and comparison to previous work. It would be great if the authors could clarify. \n\nStrengths: The paper’s methodolgy is clearly written.  The modeling is clear and sound. Overall, this idea is a promising approach to obtain networks that are provably under-confident far from training examples. The training cost for this approach is comparable to standard training, and the approach seems scalable and broadly applicable in general. \n\nThe experimental evaluation is also clearly described. Worst-case evaluation of OOD (out of domain) performance seems novel and the gains not this objective using the proposed approach of this paper are interesting and promising. \n\nConcerns: While the paper explains the proposed method well, the description of previous work and relation to previous work is inadequate. After spending some hours reading the cited paper, I am still confused about what’s the novelty of this work at a high level. \nThis work uses p(x|i) and p(x|o) in the computation of p(y|x) during inference, where i and o are in distribution and out of distribution respectively. This is crucial to obtain guarantees one performance. However, how does this compare to other previous work that also uses some kind of generative modeling to model in/out distribution? A bunch of papers are cited in the introduction as doing this, but the relationship to the proposed work is unclear.\n\n— I have a major experimental concern: When comparing against ACET, the baseline of performing adversarial style training on random noise inputs seems more appropriate since it’s closer to the evaluation metric (which picks random noise as out of domain and not 80M Tiny Images). What does the performance of this ACET baseline look like?\n\n— During evaluation, how do you ensure that the radius is not too large such that it has images that the model should actually be confident on (close to in distribution samples). A flip-side is how sensitive the performance is to the score chosen for choosing the radius for computing the valid set of images for the adversary? It’s possible that the 11%  threshold is too high? What’s the minimum confidence of CCU on the test images?\n\nMinor comments on writing: \n—K_i, K_0 are not defined when writing the expression for GMM\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BkxIutEqtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a novel approach for OOD detection; in particular their approach comes with worst-case guarantees without compromising on performance. \n\nThe manuscript is clearly written and I only have some concerns regarding the evaluation. \nFirst, while the authors include with MCD an uncertainty-aware training approach, I miss more state-of-the-art methods with substantially better OOD performance, including Evidential Deep Learning (Sensoy et al, NeurIPS 2018) and Deep Ensembles. In particular a comparison to EDL would be interesting, since a similar entropy-encouraging term in the loss function is used during training, resulting is maximum entropy for OOD samples. \nSecond, I would have liked to see precision and recall of the OOD detection task in addition to AUC, allowing a more meaningful/complete comparison between the approaches. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of confidence on neural network predictions for out-of-distribution (OOD) samples. The authors propose an approach for training neural networks such that the OOD prediction is uniform across classes. The approach requires samples from in- and out-of distribution and relies on a mixture of Gaussians for modelling the distributions, allowing to obtain theoretical guarantees on detecting OOD samples (unlike existing techniques).

The main concerns of the reviewers have been addressed during the rebuttal. If this approach does not outperform state-of-the-art in practice, providing such theoretical guarantees is an important contribution.

All reviewers agree that this paper should be accepted. I therefore recommend acceptance.
Decision: Accept (Poster)