{'fraction_non_alphanumeric': 0.04739384590403507, 'fraction_numerical': 0.010635706746772753, 'mean_word_length': 4.347189060125896, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Detecting Overfitting via Adversarial Examples

The repeated community-wide reuse of test sets in popular benchmark problems raises doubts about the credibility of reported test-error rates. Verifying whether a learned model is overfitted to a test set is challenging as independent test sets drawn from the same data distribution are usually unavailable, while other test sets may introduce a distribution shift. We propose a new hypothesis test that uses only the original test data to detect overfitting. It utilizes a new unbiased error estimate that is based on adversarial examples generated from the test data and importance weighting. Overfitting is detected if this error estimate is sufficiently different from the original test error rate. We develop a specialized variant of our test for multiclass image classification, and apply it to testing overfitting of recent models to the popular ImageNet benchmark. Our method correctly indicates overfitting of the trained model to the training set, but is not able to detect any overfitting to the test set, in line with other recent work on this topic.


Introduction
Deep neural networks achieve impressive performance on many important machine learning benchmarks, such as image classification [18,19,28,27,16], automated translation [2,31] or speech recognition [9,15]. However, the benchmark datasets are used a multitude of times by researchers worldwide. Since state-of-the-art methods are selected and published based on their performance on the corresponding test set, it is typical to see results that continuously improve over time; see, e.g., the discussion of Recht et al. [25] and Figure 1 for the performance improvement of classifiers published for the popular CIFAR-10 image classification benchmark [18].  Figure 1: Accuracy of image classifiers on the CIFAR-10 test set, by year of publication (data from [25]). This process may naturally lead to models overfitted to the test set, rendering test error rate (the average error measured on the test set) an unreliable indicator of the actual performance. Detecting whether a model is overfitted to the test set is challenging, since independent test sets drawn from the same data distribution are generally not available, while alternative test sets often introduce a distribution shift.
To estimate the performance of a model on unseen data, one may use generalization bounds to get upper bounds on the expected error rate. The generalization bounds are also applicable when the model and the data are dependent (e.g., for cross validation or for error estimates based on the training data or the reused test data), but they usually lead to loose error bounds. Therefore, although much tighter bounds are available if the test data and the model are independent, comparing 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada. arXiv:1903.02380v2 [cs.LG] 14 Nov 2019 confidence intervals constructed around the training and test error rates leads to an underpowered test for detecting the dependence of a model on the test set. Recently, several methods have been proposed that allow the reuse of the test set while keeping the validity of test error rates [10]. However, these are intrusive: they require the user to follow a strict protocol of interacting with the test set and are thus not applicable in the more common situation when enforcing such a protocol is impossible.
In this paper we take a new approach to the challenge of detecting overfitting of a model to the test set, and devise a non-intrusive statistical test that does not restrict the training procedure and is based on the original test data. To this end, we introduce a new error estimator that is less sensitive to overfitting to the data; our test rejects the independence of the model and the test data if the new error estimate and the original test error rate are too different. The core novel idea is that the new estimator is based on adversarial examples [14], that is, on data points 1 that are not sampled from the data distribution, but instead are cleverly crafted based on existing data points so that the model errs on them. Several authors showed that the best models learned for the above-mentioned benchmark problems are highly sensitive to adversarial attacks [14,23,30,6,7,24]: for instance, one can often create adversarial versions of images properly classified by a state-of-the-art model such that the model will misclassify them, yet the adversarial perturbations are (almost) undetectable for a human observer; see, e.g., Figure 2, where the adversarial image is obtained from the original one by a carefully selected translation. scale, weighing machine toaster Figure 2: Adversarial example for the ImageNet dataset and the VGG16 classifier of [27], generated by a (5, −5) translation: the original example (left) is correctly classified as "scale, weighing machine," the adversarially generated example (right) is classified as "toaster," while the image class is the same for any human observer.
The adversarial (error) estimator proposed in this work uses adversarial examples (generated from the test set) together with importance weighting to take into account the change in the data distribution (covariate shift) due to the adversarial transformation. The estimator is unbiased and has a smaller variance than the standard test error rate if the test set and the model are independent. 2 More importantly, since it is based on adversarially generated data points, the adversarial estimator is expected to differ significantly from the test error rate if the model is overfitted to the test set, providing a way to detect test set overfitting. Thus, the test error rate and the adversarial error estimate (calculated based on the same test set) must be close if the test set and the model are independent, and are expected to be different in the opposite case. In particular, if the gap between the two error estimates is large, the independence hypothesis (i.e., that the model and the test set are independent) is dubious and will be rejected. Combining results from multiple training runs, we develop another method to test overfitting of a model architecture and training procedure (for simplicity, throughout the paper we refer to both together as the model architecture). The most challenging aspect of our method is to construct adversarial perturbations for which we can calculate importance weights, while keeping enough degrees of freedom in the way the adversarial perturbations are generated to maximize power, the ability of the test to detect dependence when it is present.
To understand the behavior of our tests better, we first use them on a synthetic binary classification problem, where the tests are able to successfully identify the cases where overfitting is present. Then we apply our independence tests to state-of-the-art classification methods for the popular image classification benchmark, ImageNet [8]. As a sanity check, in all cases examined, our test rejects (at confidence levels close to 1) the independence of the individual models from their respective training sets. Applying our method to VGG16 [27] and Resnet50 [16] models/architectures, their independence to the ImageNet test set cannot be rejected at any reasonable confidence. This is in agreement with recent findings of [26], and provides additional evidence that despite of the existing danger, it is likely that no overfitting has happened during the development of ImageNet classifiers.
The rest of the paper is organized as follows: In Section 2, we introduce a formal model for error estimation using adversarial examples, including the definition of adversarial example generators.
The new overfitting-detection tests are derived in Section 3, and applied to a synthetic problem in Section 4, and to the ImageNet image classification benchmark in Section 5. Due to space limitations, some auxiliary results, including the in-depth analysis of our method on the synthetic problem, are relegated to the appendix.

Adversarial Risk Estimation
We consider a classification problem with deterministic (noise-free) labels, which is a reasonable assumption for many practical problems, such as image recognition (we leave the extension of our method to noisy labels for future work). Let X ⊂ R D denote the input space and Y = {0, . . . , K −1} the set of labels. Data is sampled from the distribution P over X , and the class label is determined by the ground truth function f * : X → Y. We denote a random vector drawn from P by X, and its corresponding class label by Y = f * (X). We consider deterministic classifiers f : X → Y. The performance of f is measured by the zero-one loss: L(f, x) = I(f (x) = f * (x)), 3 and the expected error (also known as the risk or expected risk in the learning theory literature) of the classifier f is defined as where the X i are drawn from P independently of each other and Y i = f * (X i ). In the learning setting, the classifier f usually also depends on some randomly drawn training data, hence is random itself. If f is (statistically) independent from S, then L(f, X 1 ), . . . , L(f, X m ) are i.i.d., thus the empirical error rate If f and S are not independent, the performance guarantees on the empirical estimates available in the independent case are significantly weakened; for example, in case of overfitting to S, the empirical error rate is likely to be much smaller than the expected error.
Another well-known way to estimate R(f ) is to use importance sampling (IS) [17]: instead of sampling from the distribution P, we sample from another distribution P and correct the estimate by appropriate reweighting. Assuming P is absolutely continuous with respect to P on the set is the density (Radon-Nikodym derivative) of P with respect to P on E (h can be defined to have arbitrary finite values on X \ E). It is well known that the the corresponding empirical error estimator The variance of R S is minimized if P is the so-called zero-variance IS distribution, which is for all x ∈ E (see, e.g., [4,Section 4.2]). This suggest that an effective sampling distribution P should concentrate on points where f makes mistakes, which also facilitates that R S (f ) become large if f is overfitted to S and hence R S (f ) is small. We achieve this through the application of adversarial examples.

Generating adversarial examples
In this section we introduce a formal framework for generating adversarial examples. Given a classification problem with data distribution P and ground truth f * , an adversarial example generator (AEG) for a classifier f is a (measurable) mapping g : X → X such that (G1) g preserves the class labels of the samples, that is, f * (x) = f * (g(x)) for P-almost all x; (G2) g does not change points that are incorrectly classified by f , that is, Figure 3: Generating adversarial examples. The top row depicts the original dataset S, with blue and orange points representing the two classes. The classifier's prediction is represented by the color of the striped areas (checkmarks and crosses denote if a point is correctly or incorrectly classified). The arrows show the adversarial transformations via the AEG g, resulting in the new dataset S ; misclassified points are unchanged, while some correctly classified points are moved, but their original class label is unchanged. If the original data distribution is uniform over S, the transformation g is density preserving, but not measure preserving: after the transformation the two rightmost correctly classified points in each class have probability 0, while the leftmost misclassified point in each class has probability 3/16; hence, the density hg for the latter points is 1/3. Figure 3 illustrates how an AEG works. In the literature, an adversarial example g(x) is usually generated by staying in a small vicinity of the original data point x (with respect to, e.g., the 2or the max-norm) and assuming that the resulting label of g(x) is the same as that of x (see, e.g., [14,6]). This foundational assumption-which is in fact a margin condition on the distribution-is captured in condition (G1). (G2) formalizes the fact that there is no need to change samples which are already misclassified. Indeed, existing AEGs comply with this condition.
The performance of an AEG is usually measured by how successfully it generates misclassified examples. Accordingly, we call a point g(x) a successful adversarial example if x is correctly classified by f and f (g(x)) = f (x) (i.e., L(f, x) = 0 and L(f, g(x)) = 1).
In the development of our AEGs for image recognition tasks, we will make use of another condition. For simplicity, we formulate this condition for distributions P that have a density ρ with respect to the uniform measure on X , which is assumed to exist (notable cases are when X is finite, or X = [0, 1] D or when X = R D ; in the latter two cases the uniform measure is the Lebesgue measure).
The assumption states that the AEG needs to be density-preserving in the sense that (G3) ρ(x) = ρ(g(x)) for P-almost all x.
Note that a density-preserving map may not be measure-preserving (the latter means that for all measurable A ⊂ X , P(A) = P(g(A))).
We expect (G3) to hold when g perturbs its input by a small amount and if ρ is sufficiently smooth.
The assumption is reasonable for, e.g., image recognition problems (at least in a relaxed form, ρ(x) ≈ ρ(g(x))) where we expect that very close images will have a similar likelihood as measured by ρ. An AEG employing image translations, which satisfies (G3), will be introduced in Section 5. Both (G1) and (G3) can be relaxed (to a soft margin condition or allowing a slight change in ρ, resp.) at the price of an extra error term in the analysis that follows.
For a fixed AEG g : X → X , let P g denote the distribution of g(X) where X ∼ P (P g is known as the pushforward measure of P under g). Further, let h g = dP dPg on E = {x : L(f, x) = 0} and arbitrary otherwise. It is easy to see that h g is well-defined on E and h g (x) ≤ 1 for all x ∈ E: This follows from the fact that P(A) ≤ P g (A) for any measurable A ⊂ E, which holds since where the second to last equality holds because g(X) = X for any X ∈ E under condition (G2).
One may think that (G3) implies that h g (x) = 1 for all x ∈ E. However, this does not hold. For example, if P is a uniform distribution, any g : X → supp P satisfies (G3), where supp P ⊂ X denotes the support of the distribution P. This is also illustrated in Figure 3.

Risk estimation via adversarial examples
Combining the ideas of this section so far, we now introduce unbiased risk estimates based on adversarial examples. Our goal is to estimate the error-rate of f through an adversarially generated . . , X m drawn independently from P and Y i = f * (X i ). Since g satisfies (G1) by definition, the original example X i and the corresponding adversarial example X i have the same label Y i . Recalling that h g = dP/dP g ≤ 1 on E = {x ∈ X : L(f, x) = 1}, one can easily show that the importance weighted adversarial estimate obtained from (1) for the adversarial sample S has smaller variance than that of the empirical average Intuitively, the more successful the AEG is (i.e., the more classification error it induces), the smaller the variance of the estimate R g (f ) becomes.

Detecting overfitting
In this section we show how the risk estimates introduced in the previous section can be used to test the independence hypothesis that (H) the sample S and the model f are independent.
is expected to be small. On the other hand, if f is overfitted to the dataset S (in which case R S (f ) < R(f )), we expect R S (f ) and R g (f ) to behave differently (the latter being less sensitive to overfitting) since (i) R g (f ) depends also on examples previously unseen by the training procedure; (ii) the adversarial transformation g aims to increase the loss, countering the effect of overfitting; (iii) especially in high dimensional settings, in case of overfitting one may expect that there are misclassified points very close to the decision boundary of f which can be found by a carefully designed AEG. Therefore, intuitively, (H) can be rejected if |T S,g (f )| exceeds some appropriate threshold.

Test based on confidence intervals
The simplest way to determine the threshold is based on constructing confidence intervals for these estimator based on concentration inequalities. Under (H), standard concentration inequalities, such as the Chernoff or empirical Bernstein bounds [3], can be used to quantify how fast R S and R g (f ) concentrate around the expected error R(f ). In particular, we use the following empirical Bernstein bound [22]: and L(f, g(X i ))h g (g(X i )), respectively. Then, for any 0 < δ ≤ 1, with probability at least 1 − δ, where B(m, σ 2 , δ, 1) = 2σ 2 ln(3/δ) m + 3 ln(3/δ) m and we used the fact that the range of L(f, x) is 1 (the last parameter of B is the range of the random variables considered). Similarly, with probability at least 1 − δ, It follows trivially from the union bound that if the independence hypothesis (H) holds, the above two confidence intervals On the other hand, if f and S are not independent, the performance guarantees (3) and (4) may be violated and the confidence intervals may become disjoint. If this is detected, we can reject the independence hypothesis (H) at a confidence level 1 − 2δ or, equivalently, with p-value 2δ. In other words, we reject (H) if the absolute value of the difference of the estimates

Pairwise test
A smaller threshold for |T S,g (f )|, and hence a more effective independence test, can be devised if instead of independently estimating the behavior of R S and R g (f ), one utilizes their apparent correlation. Indeed, and the two terms in T i,g (f ) have the same mean and are typically highly correlated by the construction of g. Thus, we can apply the empirical Bernstein bound [22] to the pairwise differences T i,g (f ) to set a tighter threshold in the test: if the independence hypothesis (H) holds (i.e., S and f are independent), then for any 0 < δ < 1, with probability at least 1 − δ, ; we also used the fact that the expectation of each T i,g (f ), and hence that of (as discussed in Section 2.2), it follows that U ≤ 2, but further assumptions (such as g being density preserving) can result in tighter bounds.
This leads to our pairwise dependence detection method: For a given statistic (|T S,g (f )|,σ 2 T ), the largest confidence level (smallest p-value) at which (H) can be rejected can be calculated by setting the value of the statistic |T S,g (f )| − B(m,σ 2 T , δ, 2) to zero and solving for δ. This leads to the following formula for the p-value (if the solution is larger than 1, which happens when the bound (6) is loose, δ is capped at 1): Note that in order for the test to work well, we not only need the test statistic T S,g (f ) to have a small variance in case of independence (this could be achieved if g were the identity), but we also need the estimators R S (f ) and R g (f ) behave sufficiently differently if the independence assumption is violated. The latter behavior is encouraged by stronger AEGs, as we will show empirically in Section 5.2 (see Figure 5 in particular).

Dependence detector for randomized training
The dependence between the model and the test set can arise from (i) selecting the "best" random seed in order to improve the test set performance and/or (ii) tweaking the model architecture (e.g., neural network structure) and hyperparameters (e.g., learning-rate schedule). If one has access to a single instance of a trained model, these two sources cannot be disentangled. However, if the model architecture and training procedure is fully specified and computational resources are adequate, it is possible to isolate (i) and (ii) by retraining the model multiple times and calculating the p-value for every training run separately. Assuming N models, let f j , j = 1, . . . , N denote the j-th trained model and p j the p-value calculated using the pairwise independence test (6) (i.e., from Eq. 7 in Section 3). We can investigate the degree to which (i) occurs by comparing the p j values with the corresponding test set error rates R S (f j ). To investigate whether (ii) occurs, we can average over the randomness of the training runs.
For every example X i ∈ S, consider the average test is the statistic (5) calculated for example X i and model f j with AEG g j selected for model f j (note that AEGs are model-dependent by construction). If, for each i and j, the random variables T i (f j ) are independent, then so are theT i (for all i). Hence, we can apply the pairwise dependence detector (6) giving a single p-value p N . If the training runs vary enough in their outcomes, different models f j err on different data points X j , leading toσ 2 T,N <σ 2 T , and therefore strengthening the power of the dependence detector. For brevity, we call this independence test an N -model test.  First we verify the effectiveness of our method on a simple linear classification problem. Due to space limitations, we only convey high-level results here, details are given in Appendix A. We assume that the data is linearly separable with a margin and the density ρ is known. We consider a linear classifiers of the form f (x) = sgn(w x + b) trained with the crossentropy loss c, and we employ a one-step gradient method (which is an L 2 version of the fast gradient-sign method of [14,23]) to define our AEG g, which tries to modify a correctly classified point x with label y in the direction of the gradient of the cost function, yielding x = x−εyw/ w 2 , where ε ≥ 0 is the strength of the attack. To comply with the requirements for an AEG, we define g as follows: g(x) = x if L(f, x) = 0 and f * (x) = f * (x ) (corresponding to (G2) and (G1), respectively), while g(x) = x otherwise. Therefore, if x is misclassified by f , x and x are the only points mapped to x by g. This simple form of g and the knowledge of ρ allows to compute the density h g , making it easy to compute the adversarial error estimate (2). Figure 4 shows the average p-values produced by our N -model independence test for a dependent (solid lines) and an independent (dashed lines) test set. It can be seen that in the dependent case the test can reject independence with high confidence for a large range of attack strength ε, while the independence hypothesis is not rejected in the case of true independence. More details (including why only a range of ε is suitable for detecting overfitting) are given in Appendix A.

Testing overfitting on ImageNet
In the previous section we showed that the proposed adversarial-example-based dependence test works for a synthetic problem where the densities can be computed exactly. In this section we apply our estimates to a popular image classification benchmark, ImageNet [8]; here the main issue is to find sufficiently strong AEGs that make computing the corresponding densities possible.
To facilitate the computation of the density h g , we only consider density-preserving AEGs as defined by (G3) (recall that (G3) is different from requiring h g = 1). Since in (2) and (5), h g (x) is multiplied by L(f, x), we only need to determine the density h g for data points that are misclassified by f .

AEGs based on translations
To satisfy (G3), we implement the AEG using translations of images, which have recently been proposed as means of generating adversarial examples [1]. Although relatively weak, such attacks fit our needs well: unless the images are procedurally centered, it is reasonable to assume that translating them by a few pixels does not change their likelihood. 4 We also make the natural assumption that the small translations used do not change the true class of an image. Under these assumptions, translations by a few pixels satisfy conditions (G1) and (G3). An image-translating function g is a valid AEG if it leaves all misclassified images in place (to comply with (G2)), and either leaves a correctly classified image unchanged or applies a small translation.
The main benefit of using a translational AEG g (with bounded translations) is that its density h g (x) for an image x can be calculated exactly by considering the set of images x that can be mapped to x by g (this is due to our assumption (G3)). We considered multiple ways for constructing translational AEGs. The best version (selected based on initial evaluations on the ImageNet training set), which we called the strongest perturbation, seeks a non-identical neighbor of a correctly classified image x (neighboring images are the ones that are accessible through small translations) that causes the classifier to make an error with the largest confidence.
Formally, we model images as 3D tensors in [0, 1] W ×H×C space, where C = 3 for RGB data, and W and H are the width and height of the images, respectively. Let τ v (x) denote the translation of an image x by v ∈ Z 2 pixels in the (X, Y) plane (here Z denotes the set of integers). To control the amount of change, we limit the magnitude of translations and allow v ∈ V ε = {u ∈ Z 2 : u = (0, 0), u ∞ ≤ ε} only, for some fixed positive ε. Thus, we considers AEGs in the form and g(x) = x otherwise (if x is correctly classified, we attempt to translate it to find an adversarial example in {τ v (x) : v ∈ V} which is misclassified by f , but x is left unchanged if no such point exists). Denoting the density of the pushforward measure P g by ρ g , for any misclassified point x, where the second equality follows from (G3). Therefore, the corresponding density is where n(x) = v∈V I(g(τ −v (x)) = x) is the number of neighboring images which are mapped to x by g. Note that given f and g, n(x) can be easily calculated by checking all possible translations of x by −v for v ∈ V. It is easy to extend the above to non-deterministic perturbations, defined as distributions over AEGs, by replacing the indicator with its expectation P(g(τ −v (x)) = x|x, v) with respect to the randomness of g, yielding h g (x) = 1 1 + v∈V P(g(τ −v (x)) = x|x, v) .
If g is deterministic, we have h g (x) ≤ 1/2 for any successful adversarial example x. Hence, for such g, the range U of the random variables T i defined in (5) has a tighter upper bound of 3/2 instead 2 (as T i ∈ [−1, 1/2]), leading to a tighter bound in (6) and a stronger pairwise independence test. In the experiments, we use this stronger test. We provide additional details about the translational AEGs used in Appendix B.

Tests of ImageNet models
We applied our test to check if state-of-the-art classifiers for the ImageNet dataset [8] have been overfitted to the test set. In particular, we use the VGG16 classifier of [27] and the Resnet50 classifier of [16]. Due to computational considerations, we only analyzed a single trained VGG16 model, while the Resnet50 model was retrained 120 times. The models were trained using the parameters recommended by their respective authors.
The preprocessing procedure of both architectures involves rescaling every image so that the smaller of width and height is 256 and next cropping centrally to size 224 × 224. This means that translating the image by v can be trivially implemented by shifting the cropping window by −v without any loss of information for v ∞ ≤ 16, because we have enough extra pixels outside the original, centrally located cropping window. This implies that we can compute the densities of the translational AEGs for any v ∞ ≤ ε = 16/3 = 5 (see Appendix B.1 for detailed explanation). Because the ImageNet data collection procedure did not impose any strict requirements on centering the images [8], it is reasonable to assume (as we do) that small (lossless) translations respect the density-preserving condition (G3).
In our first experiment, we applied our pairwise independence test (6)   well as to a number of its randomly selected (uniformly without replacement) subsets of different sizes. Besides this being a sanity check, we also used this experiment to select from different AEGs and compare the performance of the pairwise independence test (6) to the basic version of the test described in Section 3.1.
The left graph in Figure 5 shows that with the "strongest perturbation", we were able to reject independence of the trained model and the training samples at a confidence level very close to 1 when enough training samples are considered (to be precise, for the whole training set the confidence level is 99.9994%). Note, however, that the much weaker "smallest perturbation" AEG, as well as the random transformations, are not able to detect the presence of overfitting. At the same time, the graph on the right hand side shows the relative strength of the pairwise independence test compared to the basic version based on independent confidence interval estimates as described in detail in Section 3.1: the 97.5%-confidence intervals of the error estimates R S (f ) and R g (f ) overlap, not allowing to reject independence at a confidence level of 95% (note that here S denotes the training set).
On the other hand, when applied to the test set, we obtained a p-value of 0.96, not allowing at all to reject the independence of the trained model and the test set. This result could be explained by the test being too weak, as no overfitting is detected to the training set at similar sample sizes (see Figure 5), or simply the lack of overfitting. Similar results were obtained for Resnet50, where even the N -model test with N = 120 independently trained models resulted a p value of 1, not allowing to reject independence at any confidence level. The view of no overfitting can be backed up in at least two ways: first, "manual" overfitting to the relatively large ImageNet test set is hard. Second, since training an ImageNet model was just too computationally expensive until quite recently, only a relatively small number of different architectures were developed for this problem, and the evolution of their design was often driven by computational efficiency on the available hardware. On the other hand, it is also possible that increasing N sufficiently might show evidence of overfitting (this is left for future work).

Conclusions
We presented a method for detecting overfitting of models to datasets. It relies on an importanceweighted risk estimate from a new dataset obtained by generating adversarial examples from the original data points. We applied our method to the popular ImageNet image classification task. For this purpose, we developed a specialized variant of our method for image classification that uses adversarial translations, providing arguments for its correctness. Luckily, and in agreement with other recent work on this topic [25,26,13,21,32], we found no evidence of overfitting of state-of-the-art classifiers to the ImageNet test set.
The most challenging aspect of our methods is to construct adversarial perturbations for which we can calculate the importance weights; finding stronger perturbations than the ones based on translations for image classification is an important question for the future. Another interesting research direction is to consider extensions beyond image classification, for example, by building on recent adversarial attacks for speech-to-text methods [5], machine translation [11] or text classification [12].

A Synthetic experiments
In this section, we present full details of the experiments on a simple synthetic classification problem, which we presented briefly in Section 4. These experiments illustrate the power of the method of Section 3. The advantage of the simple setup considered here is that we are able to compute the density h g in an analytic form (see Figure 6 for an illustration).
We consider linear classifiers of the form f (x) = sgn(w x + b) trained with the cross-entropy loss c ((w, b), x, y) = ln(1 + e −y(w x+b) ) where y = f * (x). We employ a one-step gradient method (which is an L 2 version of the fast gradient-sign method of [14,23]) to define our AEG g, which tries to modify a correctly classified point x with label y in the direction of the gradient of the cost function c: x = x + ε∇ x c((w, b), x, y)/ ∇ x c((w, b), x, y) 2 for some ε > 0. For our specific choice of c, the above simplifies to x = x − εyw/ w 2 . To comply with the requirements for an AEG, we define g as follows: g(x) = x if L(f, x) = 0 and f * (x) = f * (x ) (corresponding to (G2) and (G1), respectively), while g(x) = x otherwise. Therefore, if x is misclassified by f , x 0 x 1 Figure 6: Illustration of the data distribution and the linear model f (x) = sgn(w x + b) in two dimensions. The blue and green gradients show the probability density ρ of the data with true labels y = −1 and y = 1, respectively, while the white space between them is the margin with ρ = 0. The red line is the model's classification boundary with its parameter vector w shown by the purple arrow. Depending on the label, w or −w is the direction of translation used to perturbed the correctly classified data points, and the translations used by the AEG g for specific points are depicted by grey arrows: solid arrows indicate the cases where g(x) = x = x, while dashed arrows are for candidate translations which are not performed by the AEG because they would change the true label, f * (x ) = f * (x), and hence g(x) = x = x . Each original/perturbed data point is represented by a color-coded circle: the inner color corresponds to the true label (dark blue for y = −1 and dark green for y = 1) while the outer color to the model's prediction (dark blue for f (x) = −1 and dark green for f (x) = 1). Points x A and x B can be obtained from xA and xB, respectively, by applying the AEG, x A = g(xA) and x B = g(xB). Since only xA is mapped to x A by g, and g(x A ) = x A , the density (Radon-Nikodym derivative) can be obtained as hg(x A ) = ρ(x A )/(ρ(xA) + ρ(x A )) ∈ (0, 1). In the case of x B , hg(x B ) = ρ(x B )/(ρ(xB) + ρ(x B )) = 0 due to the margin. Note that the formula for hg(x A ) does not depend on whether xA or x A is in the original test set S; in the first case we call x A a "successful adversarial example" while in the second case x A is called "originally misclassified" (a similar argument holds for hg(x B )).
x C is not a successful adversarial example since L(f, x C ) = 0 (however, g(xC ) = x C according to our definition). Points xD and xE are not perturbed by our AEG, since f * (xD) = f * (x D ) and f * (xE) = f * (x E ). and x are the only points mapped to x by g. Thus, the density at x after the transformation g is L(f, x))I(f * (x) = f * (x )) and L(f, x)).

A.2 Experiment setup
We present two experiments showing the behavior of our independence test: one where the training and test sets are independent, and another where they are not.
In the first experiment a linear classifier was trained on a training set S Tr of size 500 for 50,000 steps using the RMSProp optimizer [29] with batch size 100 and learning rate 0.01, obtaining zero (up to numerical precision) final training loss c and, consequently, 100% prediction accuracy on the training data. Then the trained classifier was tested on a large test set S Te of size 10,000. 5 Both sets were drawn independently from ρ defined above. We used a range of ε values matched to the scale of the data distribution: from 10 −2 , which is the order of magnitude of the margin between two classes (0.05), to 10 2 , which is the order of magnitude of the width of the Gaussian distribution used for each classes (σ = √ 500).
In the second experiment we consider the situation where the training and test sets are not independent.
To enhance the effects of this dependence, the setup was modified to make the training process more amenable to overfitting by simulating a situation when the model has a wrong bias (this may happen in practice if a wrong architecture or data preprocessing method is chosen, which, despite the modeler's best intentions, worsens the performance). Specifically, during training we added a penalty term 10 4 w 2 1 to the training loss c, decreased the size of the test set to 1000 and used 50% of the test data for training (the final penalized training loss was 0.25 with 100% prediction accuracy on the training set). Note that the small training set and the large penalty on w 1 yield classifiers that are essentially independent of the only interesting feature x 1 (recall that the true label of a point x is sgn(x 1 )) and overfit to the noise in the data, resulting in a true model risk R(f ) ≈ 1/2.

A.3 Results
The results of the two experiments are shown in Figure 7, plotted against different perturbation strengths: the left column corresponds to the first experiment while the right column to the second. The first row presents the p-values for rejecting the independence hypothesis, calculated by repeating the experiment (sampling data and training the classifier) 100 times and applying the single-model (Section 3, labelled as N = 1 in the plots) and N -model (Section 3.3, labelled as N = 2, 10, 25, 100 in the plots) independence test, and taking the average over models (or model sets of size N ) for each ε. We also plot empirical 95% two-sided confidence intervals (N ≤ 2) or, due to limited number of p-values available after dividing 100 runs into disjoint bins of size N ≥ 10, ranges between minimum and maximum value (N = 10, 25). For all methods of detecting dependence, it can be seen that for the independent case the test is correctly not able to reject the independence hypothesis (the average p-value is very close to 1, although in some runs it can drop to as low as 0.5). On the other hand, for 10 ≤ ε ≤ 50, the non-independent model failed the independence test at confidence level 1 − δ ≈ 100%, hence, in this range of ε our independence test reliably detects overfitting.
In fact, it is easy to argue that our test should only work for a limited range of ε, that is, it should not reject independence for too small or too large values of ε. First we consider the case of small ε values. Notice that except for points g(x) ε-close (in L 2 -norm) to the true decision boundary or the decision boundary of f , g(x) is invertible: if g(x) is correctly classified and is ε-away from the true decision boundary, there is exactly one point, x, which is translated to g(x), while if g(x) is incorrectly classified and ε-away from the decision boundary of f , no translation leads to g(x) and x = g(x); any other points are ε-close to the decision boundary of either f or f * . Thus, since ρ is bounded, g(x) is invertible on a set of at least 1 − O(ε) probability (according to ρ). When ε → 0, g(x) → x, and so ρ(g(x)) → ρ(x) for all points x with |x 1 | = 0.025 (since ρ is continuous in all such x), implying h g (g(x)) ≈ 1 on these points. It also follows that L(f, x) = L(f, g(x)) can only 5 The large number of test examples ensures that the random error in the empirical error estimate is negligible.  (N > 1). The bounds plotted are either empirical 95% two-sided confidence intervals (N ≤ 2) or ranges between minimum and maximum value (N = 10, 25). Second row: Empirical two-sided 97.5% confidence intervals for the empirical test error rate RS(f ) and the adversarial risk estimate Rg(f ). On the left, R(f ) ≈ RS(f ), while R(f ) is shown separately on the right. Third row: Average densities (Radon-Nikodym derivatives) for originally misclassified points and for the new data points obtained by successful adversarial transformations (with empirical 97.5% two-sided confidence intervals). Fourth row: The empirical test error rate RS(f ) and the adversarial risk estimate Rg(f ) for a single realization with 97.5% two-sided confidence intervals computed from Bernstein's inequality, the adversarial error rate R S (f ), and the expected error R(f ) (on the right, on the left R(f ) ≈ RS(f )). Fifth row: Histograms of p-values for selected ε values over 100 runs. happen to a set of points with an O(ε) ρ-probability. This means that L(f, g(x))h g (g(x)) ≈ L(f, x) on a set of 1 − O(ε) ρ-probability, and for these points T g (x) = L(f, g(x))h g (g(x)) − L(f, x) ≈ 0. Thus, T g (X) ≈ 0 with ρ-probability 1 − O(ε). Unless the test set S is concentrated in large part on the set of remaining points with O(ε) ρ-probability, the test statistic |T S,g (f )| = O(ε) with high probability and our method will not reject the independence hypothesis for ε → 0.
To better understand the behavior of the test, the second row of Figure 7 shows the empirical test error rate R S (f ), the (unadjusted) adversarial error rate R S (f ), and the adversarial risk estimate R g (f ), together with their confidence intervals. For the non-independent model, we also show the expected error R(f ) (estimated over a large independent test set), while it is omitted for the independent model where it approximately coincides with both R S (f ) and R g (f ). While the reweighted adversarial error estimate R g (f ) remains the same for all perturbations in case of an independent test set (left column), the adversarial error rate R S (f ) varies a lot for both the dependent and independent test sets. For example, in the case when the test samples and the model f are not independent, it undershoots the true error for ε < 10 and overshoots it for larger perturbations. For very large perturbations (ε close to 100), the behavior of R S (f ) depends on the model f : in the independent case R S (f ) decreases back to R S (f ) because such large perturbations increasingly often change the true label of the original example, so less and less adversarial points are generated. In the case when the data and the model are not independent (right column), the adversarial perturbations are almost always successful (i.e., lead to a valid adversarial example for most originally correctly classified points), yielding an adversarial error rate close to one for large enough perturbations. This is because the decision boundary of f is almost orthogonal to the true decision boundary, and so the adversarial perturbations are parallel with the true boundary, almost never changing the true label of a point.
The plots of the densities (Radon-Nikodym derivatives), given in the third row of Figure 7, show how the change in their values compensate the increase of the adversarial error rate R S (f ): in the independent case, the effect is completely eliminated yielding an unbiased adversarial error estimate R g (f ), which is essentially constant over the whole range of ε (as shown in the first row), while in the non-independent case the similar densities do not bring back the adversarial error rate R S (f ) to the test error rate R S (f ), allowing the test to detect overfitting. Note that the densities exhibit similar trends (and values) in both cases, driven by the dependence of typical values of the ρ(x)/ρ(g(x)) ratio on the perturbation strength ε for originally misclassifed points (L(f, x) = 1) and for successful adversarial examples (i.e., L(f, x) = 0 and L(f, g(x)) = 1).
To compare the behavior of our improved, pairwise test and the basic version, the fourth row of Figure 7 depicts a single realization of the experiments where the 97.5% confidence intervals (as computed from Bernstein's inequality) are shown for the estimates. For the independent case, the confidence intervals of R S (f ) and R g (f ) overlap for all ε, and thus the basic test is not able to detect overfitting. In the non-independent case, the confidence intervals overlap for ε = 10 and ε = 75, thus the basic test is not able to detect overfitting with at a 95% confidence level, while the improved test (second row) is able to reject the independence hypothesis for these ε values at the same confidence level.
Finally, in the fifth row of Figure 7 we plotted the histograms of the empirical distribution of p-values for both models, over 100 independent runs (between the runs, all the data was regenerated and the models were retrained). For ε = 0.1, 5, 20, they concentrate heavily on either δ = 0 or δ = 1, and have very thin tails extending far towards the opposite end of the [0, 1] interval. This explains the surprisingly wide 95% confidence intervals for p-values plotted in the first row. In particular, the fact that some p-values for the independent model are as low as 0.5 does not mean the independence test is not reliable, because almost all calculated δ values are close or equal to 1, and the few outliers are For comparison, we also plotted in Figure 8 (left panel) the corresponding histograms for the independent model and a slightly higher attack strength, ε = 10, at which the independence tests fails for the overfitted model even without averaging (see Figure 7, first row, right panel). The histograms are all clustered in the δ region close to 1, indicating that the N -model test is not overly pessimistic.

B Translational AEGs for image classification models
For image classification we consider two translation variants that are used in constructing a translational AEG. For every correctly classified image x, we consider translations from V ε (for some ε), choosing g(x) from the set G(x) = {τ v (x) : v ∈ V ε } ∪ {x}. If all translations result in correctly classified examples, we set g(x) = x. Otherwise, we use one of two possible ways to select g(x) (and we call the resulting points successful adversarial examples): • Strongest perturbation: Assuming the number of classes is K, let l(f, x) ∈ R K denote the vector of the K class logits calculated by the model f for image x, and let l exc (f, x) = max 0≤i<K l i (f, x) − l y (f, x). We define g strongest (x) = argmax x ∈G(x) l exc (f, x ), with ties broken deterministically by choosing the first translation from the candidate set, going top to bottom and left to right in row-major order. Thus, here we seek a non-identical "neighbor" that causes the classifier to err the most, reachable from x by translations within a maximum range ε.
• Nearest misclassified neighbor: Here we aim to find the nearest image in G(x) that is misclassified. That is, letting d(x, x ) = v 2 if x = τ v (x) and ∞ otherwise, we define with ties broken deterministically as above.
The two perturbation variants are successful on exactly the same set of images, hence they lead to the same adversarial error rates R S (f ). However, they are characterized by different values of the density h g and, consequently, yield different adversarial risk estimates R g (f ) and associated p-values for the independence test. The main difference between them is that the "strongest" version is more likely to map multiple images to the same adversarial example, thus decreasing the densities for successful adversarial examples and, counterintuitively, increasing them for originally misclassified points (as their neighbors are less likely to be mapped to these points).
To better see the effect of adversarial perturbations, we also consider two random baselines that do not take into account the success of a translation in generating misclassified points: g random (x) is chosen uniformly at random from G(x) \ {x}, and g random2 (x) is chosen uniformly at random from G(x).

B.1 Maximum translations
In practice, translating an image is not always simple, as the new image has to be padded with new pixels. When (central) crops of a larger image are used (as is typical for ImageNet classifiers), translations can easily be implemented as long as the resulting new cropping window stays within the original image boundaries. Even if an image can be translated by a vector v, this limits our ability to compute h g (x ) for the adversarial image x by (8) or (9) for g strongest or g nearest . Indeed, if an image x is shifted by v ∈ V ε to generate adversarial example x , we need to examine translations of x with vectors in V ε to find the neighbors x of x potentially contributing to n(x ) when computing h g (x ).
Finally we need to consider translations of x with vectors in V ε to determine the exact value they contribute, that is, to compute the exact probabilities in (9) (see Figure 9 for an illustration). Thus, to be able to compute the density h g for the adversarial points obtained by translations from V ε , we might need to be able to perform translations within V 3ε . x x' x'' ε Figure 9: Image translations which need to be considered for a translational AEG with ε = 3. The red, blue and green balls represent the center of the original image x, adversarial example x = g(x) and another image x contributing to ρg(x ), respectively, while the semi-translucent squares of corresponding colors represent the possible translations which need to be considered for each of x, x and x . Solid light grey arrows represent the relationships x = g(x) and x = g(x ). Finally, the dashed arrow and the semi-translucent grey ball represent an alternative mapping, which has to be ruled out while calculating the value of g(x ) and, consequently, of hg(x ). It is easy to see that the colored squares (which contain the translations needing to be evaluated) extend as far as 3ε from the original image x.