Understanding Intrinsic Robustness Using Label Uncertainty
Authors: Xiao Zhang
David Evans
Venue: ICLR 2022 Poster (2022)
Keywords: Concentration of Measure
Intrinsic Adversarial Robustness
Label Uncertainty

Abstract: A fundamental question in adversarial machine learning is whether a robust classifier exists for a given task. A line of research has made some progress towards this goal by studying the concentration of measure, but we argue standard concentration fails to fully characterize the intrinsic robustness of a classification problem since it ignores data labels which are essential to any classification task. Building on a novel definition of label uncertainty, we empirically demonstrate that error regions induced by state-of-the-art models tend to have much higher label uncertainty than randomly-selected subsets. This observation motivates us to adapt a concentration estimation algorithm to account for label uncertainty, resulting in more accurate intrinsic robustness measures for benchmark image classification problems.

Published as a conference paper at ICLR 2022
UNDERSTANDING INTRINSIC ROBUSTNESS USING LABEL UNCERTAINTY
Xiao Zhang
David Evans
Department of Computer Science University of Virginia shawn@virginia.edu
Department of Computer Science University of Virginia
evans@virginia.edu
ABSTRACT
A fundamental question in adversarial machine learning is whether a robust classi- fier exists for a given task. A line of research has made some progress towards this goal by studying the concentration of measure, but we argue standard concentration fails to fully characterize the intrinsic robustness of classification problem since it ignores data labels which are essential any classification task. Building on a novel definition of label uncertainty, we empirically demonstrate that error regions induced by state-of-the models tend to have much higher label uncertainty than randomly-selecter subsets. This observation motivates us adapt a concentration estimation algorithm to account for label uncertainty, resulting in more accurate intrinsic robustness measures for benchmark image classification problems.
INTRODUCTION
Since the initial reports of adversarial examples against deep neural networks (Szegedy al., 2014;
Goodfellow et al., 2015), many defensive mechanisms have been proposed aiming to enhance the robustness of machine learning classifiers. Most have failed, however, against stronger adaptive attacks (Athalye et al., 2018 8; Tramer et al., 2020). PGD-based adversarial training (Mądry et al., 2018 and its variants (Zhang et al., 2019; Carmon al., 2019) are among the few heuristic defenses that have not been broken so far, but these methods still fail produce satisfactorily robust classifiers, for classification tasks on benchmark datasets like CIFAR-1O. Motivated by the empirical hardness of adversarially-roous. learning, line of theoretical works (Gilmer et al., 2018; Fawzi al., 2018; Mahloujifar et al., 2019 Shafahi et al., 2019) have argued that adversarial examples are unavoidable. In partieular, these works proved that as long as the input distributions are concentrated with respect to the perturbation metric, adversarially robust classifiers do not exist. Recently, Mahloujifar et al. (2019b) and Prescott et al. (2021) generalized these results by developing empirical methods for measuring the concentration of arbitrary input distributions to derive an intrinsic robustness limit, (Appendix A provides more thorough discussion of related work.)
We argue that the standard concentration of measure problem, which was studied in all of the afore- mentioned works, not sufficient to capture realistic intrinsic robustness limit for a classification problem. In particular, the standard concentration function is defined as an inherent property regarding the input metric probability space that does not take account of the underlying label information. We argue that such label information is essential for any supervised learning problem, including adversarially robust classification, so must be incorporated into intrinsic robustness limits.
Contributions. We identify the insufficiency of the standard concentration of measure problem and demonstrate why it fails to capture a realistic intrinsic robustness limit (Section 3). Then, we introduce the notion label uncertainty (Definition 4.), which characterizes the average uncertainty of label assignments for an input region. We then incorporate label uncertainty in the standard concentration measure as an initial step towards a more realistic characterization of intrinsic robustness (Section 4). Experiments the CIFAR- 10 and CIFAR- -OH (Peterson et al., 2019) datasets demonstrate that error regions induced by state-of-tte the-art classification models all have high label uncertainty (Section 6. 1), which validates the proposed label uncertainty constrained concentration problem.

---

Published as a conference paper at ICLR 2022
Adversaria Robustries
0.9
Adversaria Robustness
0.9
0.8
0.7
0.7
0.0
0.5
1.838
cecantrotor daone
uncemmeiyy
0.5
Sctuelierch model
TaburtJench Mooes
0.00
0.05
0.10
0.15
0.00
0,05
0.10
0.15
Risk
Risk
(a) foo perturbations
(b) E2 perturbations
Figure I: Intrinsic robustness estimates for classification tasks on CIFAR-10 under (a) fox pertur- bations with e = 8/255 and (b) & perturbations with = 0.5. Orange dots are intrinsic robustness estimates using the method in Prescott et al. (2021), which does not consider labels; green dots show the results using our methods that incorporate label uncertainty; blue dots are results achieved by the state-of-the-art udversarially-traine models in RobustBench (Croce et al., 2020). Three fundamental causes behind the adversarial vulnerability can be summarized as imperfect risk (red region), concentration of measure (orange region) and existence of uncertain inputs (green region).
By adapting the standard concentration estimation method in Mahloujifar et al. (2019b), we propose an empirical estimator for the label uncertainty constrained concentration function. We then theoretically study the asymptotic behavior of the proposed estimator and provide a corresponding heuristic algorithm for typical perturbation metrics (Section 5). We demonstrate that our method able to produce more accurate characterization of intrinsic robustness limit for benchmark datasets than was possible using prior methods that do not consider labels (Section 6.2). Figure illustrates the intrinsic robustness estimates resulting from our label uncertainty approach on two CIFAR- 10 robust classification tasks. The intrinsic robustness estimates we obtain by incorporating label uncertainty are much lower than prior limits, suggesting that compared with the concentration of measure phenomenon, the existence of uncertain inputs may explain more fundamentally the adversarial vulnerability of state-of-the-art robustly-traines models. In addition, also provide empirical evidence showing that both the clean and robust accuracics of state-of-the-an robust classification models are largely affected by the label uncertainty of the tested examples, suggesting that adding an abstain option based on label uncertainty is a promising avenue for improving adversarial robustness of deployed machine learning systems (Section 6.3).
Notation. We use [K] to denote 21, k) and use I, to denote the set A. |A|] denotes its cardinality, pow(.A) all its measurable subsets, and 1l (-) is the indicator function of A. Consider metric probability space (X, A), where A X' X' - R2z is distance metric on X. Define the empirical measure of μa with respect to a data set S sampled from as (A) Exes [z)88 Denote by B, (2, A) the ball around with radius measured by A. The e-expansion of A is defined A.) {o X xx E (x, nAA) When A is free of context, we simply write B, = (2, A) and A. (A)..
identity matrix. For any
2 PRELIMINARIES
Adversarial Risk. Adversarial risk captures the vulnerability of a classifier against adversarial perturbations. In particular, we adopt the following adversarial risk definition, which has been studied in several previous works, such as Gilmer et al. (2018) 8); Bubeck et al. (2019); Mahloujifar et al. (2019a;b); Zhang et al. (2020b); Prescott et al. (2021).
Definition 2.1 (Adversarial Risk). Let (X' n. A) be metric probability space of instances and ) be the set of possible class labels. Assume c X - y is a concept function that gives each instance a label. For any classifier X y and 2 0, the adversarial risk of f is defined as:
AdvRisk, (S,c) c) Pr [3 xx E (xx) f(x' # c(x')).
The adversarial robustness of is defined AdvRob, (J,c) AdvRisk, (J,c).
2

---

Published as a conference paper at ICLR 2022
When 0, adversarial risk equals to the standard risk. Namely, AdvRisko = Risk(f, PIæ=z & c(=)] holds for any classifier f. Other defimitions of adversarial risk have been proposed, such the one used in Madry et al. (2018). These definitions equivalent to the one use, as long as small perturbations preserve the labels assigned by c(.)-
Intrinsic Robustness. The definition of intrinsic robustness was first introduced by Mahloujifar et al. (2019b) capture the maximum adversarial robustness with respect some set of classifiers:
Definition 2.2 (Intrinsic Robustness). Consider the imput metric probability space (X, Hr A) and the set of labels V. Let c: y be a concept function that gives label to each input. For any set of classifiers F S X + } and c 2 0, the intrinsic robustness with respect to F is defined as: AdvRob, (F,
inf (AdwRisk,(J,c)) = -sup (ud(oooobb((Je)) JEF
FEF
According to the definition of intrinsic robustness, there does not exist any classifier in F with adversarial robustness higher than AdvRob, (F, c) for the considered task. Prior works, including Gilmer al. (2018); Mahloujifar et al. (2019a:b); Zhang et (2020b), selected JF Definition 2.2 as the set of imperfect classifiers Fa {f Risk(f, c) 2 a where a E (0, 1) is set as small constant that reflects the best classification error rates achieved by state-of-the-ie art methods.
Concentration of Measure. Concentration of measure captures a 'closeness' property for metric probability space of instances. More formally, it is defined by the concentration function:
Definition 2.3 (Concentration Function). Let (X, μr, A) be a metric probability space. For any a E (0, 1) and 0,, concentration function is defined as: h(u,, c) inf ( m(E) a).
The standard notion of concentration function considers special case of Definition 2.3 with 1/2 (e.g., Talagrand (1995)). For some special metric probability spaces, one can prove the closed-form solution of the concentration function. The Gaussian Isoperimetric Inequality (Borell, 1975; Sudakov & Tsirelson, 1974) characterizes the concentration function for spherical Gaussian distribution and f--norm distance metric, and was generalized by Prescott al. (2021) to other l norms.
STANDARD CONCENTRATION IS INSUFFICIENT
We first explain fundamental connection between the concentration of measure and the intrinsic robustness with respect to imperfect classifiers shown in previous work, and then argue that standard concentration fails capture realistic intrinsic robustmess limit because ignores data labels.
Connecting Intrinsic Robustness with Concentration of Measure. Let (X, A) be the consid- ered input metric probability space, y be the set of possible labels, and e X +> 3 be the concept function that gives each input label. Given parameters 0 a < and concentration problem can be cast into an optimization problem as follows:
the standard
minimize (EE.) subject to p( 2a [Epow(
(3.1)
For any classifier f. let E, {x X f(x) + c(x)) be its induced error region with respect c(-). By connecting the risk of f with the measure of E and the adversarial risk of f with the measure of the e-expansion of E,, Mahloujifar et al. (2019a) proved that the standard concentration problem (3.1) is equivalent to the following optimization problem regarding risk and adversarial risk:
minimize AdvRisk, (J,c) subject to Risk(J, c) 2 a.
f
To be more specific, the following lemma characterizes the connection between the standard concen- tration function and the intrinsic robustness limit with respect the of imperfect classifiers:
Lemma 3.1 (Mahloujifar et al. (2019a)). Let a E (0, 1) and F. [ Risk(f, 2 a) be the set of imperfect classifiers. For any 2 0, it holds that AdvRob, (F.,
Lemma 3.1 suggests that the concentration function of the input metric probability space h(u, a, e) can be translated into an adversarial robustness upper bound that applies any classifier with risk at
3

---

Published as a conference paper at ICLR 2022
least If this upper bound is shown to be small, then one conclude that it is impossible to learn an udversarially robust classifier, as long as the learned classifier has risk at least a.
Concentration without Labels Mischaracterizes Intrinsic Robustness. Despite the appealing relationship between concentration of measure and intrinsic robustness, we argue that solving the standard concentration problem is not enough to capture a meaningful intrinsic limit for adversarially robust classification. The standard concentration of measure problem (3.1), which aims to find the optimal subset that has the smallest c-expansion with regard to the input metric probability space (X, μi, A), does not involve the concept function c(-) that determines the underlying class label of each input. Therefore, no matter how we assign the labels to the inputs, the concentration function h(,, a, <) will remain the same for the considered metric probability space. In sharp contrast, learning an ad adversarially-robus classifier depends on the joint distribution of both the inputs and the labels.
Moreover, when the standard concentration function translated into an intrinsic limit of adversarial robustness, it is defined with respect to the set of imperfect classfiers Fa (see Lemma 3.1). The only restriction imposed by Fa is that the classifier (or equivalently, the measure of the corresponding error region) has risk at least a. This fails to consider whether the classifier is learnable or not under the given classification problem. Therefore, the intrinsic robustness limit implied by standard concentration AdvRob, (Fa, e) could be much higher than (alvRob,(FFeee c). where Fiemm denotes the set of classifiers that can be produced by some supervised learning method. Hence, it is not surprising that Mahloujifar et al. (2019b) found that the adversarial robustness attained by sffte-of-the- art robust training methods for several image benchmarks is much lower than the intrinsic robustness limit implied by standard concentration of measure. In this work, to obtain a more meaningful intrinsic robustness limit restrict the search space of the standard concentration problem (3.1) by considering both the underlying class labels and the learnability of the given classification problem.
Gaussian Mixture Model. We further illustrate the insufficiency of standard concentration under simple Gaussian mixture model. Let X' C R" be the input space and y {-1, +1} be the label space. Assume all the inputs are first generated according to a mixture of 2-Gaussian distribution: J } 0 o I + ]N, IT),,, then labeled by concept function c(x>) = sgn(O TTaa m)) where 0 E IR" and a E R are given parameters (this concept function is also the Bayes optimal classifier, which best separates the two Gaussian clusters). Theorem 3.2, proven in Appendix C.I, characterizes the optimal solution to the standard concentration problem under this assumed model. Theorem 3.2. Consider the above Gaussian mixture model with &2 perturbation metrie. The optimal solution to the standard concentration problem (3.1) is a halfspace, either
H-_ {I E X: 0 x b. ||0]|2 S 0} or H4 fxr X: 0 x - b- |0| 0},
where b is parameter depending on and O such that ((H_) = ,(H+))
Remark 3.3. Theorem 3.2 suggests that for the Gaussian mixture model, the optimal subset achieving the smallest e-expansion under f2-norm distance metric is halfspace H. which is far away from the boundary between the two Gaussian classes for small a. When translated into the intrinsic robustness problem, the corresponding optimal classifier ff has to be constructed by treating 7 as the only error region, or more precisely fxx = c( (z) if x & H: fax + c(x) otherwise. This optimally constructed classifier however, does not match our intuition of what predictive classifier would do under the considered Gaussian mixture model. In particular, since all the inputs in H and their neighbours share the same class label and also far away from the boundary, examples that fall into H should be easily classified correctly using simple decision rule, such as k-nearest neighbour or maximum margin, whereas examples that are close the boundary should be more likely to be misclassified as errors by supervisedly- learmedd classifiers. This confirms our claim that standard concentration is not sufficient for capturing meaningful intrinsic robustness limit.
INCORPORATING LABEL UNCERTAINTY IN INTRINSIC ROBUSTNESS
In this section, we first propose a new concentration estimation framework by imposing constraint based on label uncertainty (Definition 4. on the search space with respect to the standard problem (3.1). Then, explain why this yields more realistic intrinsic robustness limit.
Let (X, pi) be the input probability space and y = 21.2.... ..}} be the set of labels. n X + |0, 1 is said to capture the full label distribution (Geng, 2016; Gao et al., 2017), if [n(=)] corresponds
4

---

Published as a conference paper at ICLR 2022
to the description degree of for any X' and y E V and Eve(s) [n(2)], = 1 holds for any X. For classification tasks that rely on human labeling, one approximate the label distribution for any input by collecting human labels from multiple human annotators. Our experiments use the CIFAR- 10H dataset that did this for the CIFAR-10 test images (Peterson et al., 2019).
For any subset & E ('') we introduce label uncertainty to capture the average uncertainty level with respect to the label assignments of the inputs within E:
Definition 4.1 (Label Uncertainty). Let (X, 11) be the input probability space and y = {1, 2, ................................ ,k) be the complete set of class labels. Suppose c: X + J is concept function that assigns each input a a label y/ E y. Assume 7) X - [0, 1] is the underlying label distribution function, where [n7 x) represents the description degree of y to For any subset & E pow(X)) with measure uu(E) > 0, the label uncertainty (LU) of & with respect to (X, p)). c(-) and mn()) is defined as:
1 LU, p(E) / { [n(x)) c(x))
[n(x)] } du.
+ max y V'(((a)
We define LU(E; 14, c, n) as the average label uncertainty for all the examples that fall into &, where 1 [n(=)]l(()) + ma(x)" [n(x)) )] represents the label uncertainty of a single example c(x)) The range of label uncertainty is 2]. For a single input, label uncertainty of 0 suggests the assigned label fully captures the underlying label distribution; label uncertainty of 1 means there are other classes likely be the ground-truth label as the assigned label; label uncertainty of means the input is mislabeled and there is a different label that represents the ground-truth label. Based on the notion of label uncertainty, we study the following constrained concentration problem:
minimize ((E)) subject to 1(E) 2 and LU(E; c, m)) 2 7
(4.1)
('pow((')
where 7 E [0, is a constant. When y is set as zero, (4.1) simplifies to the standard concentration of measure problem. In this work, we set the value of y roughly represent the label uncertainty of the ttt-he-art art classifiers for the given classification problem.
error region of state-of wate-offthhe-ar
Theorem 4.2, proven in Appendix C.2, shows how (4.1) captures the intrinsic robustness limit with respect to the set of imperfect classifiers whose error region label uncertainty is at least 7.
Theorem 4.2. Define Fa.y {/ Risk(f,c) c) 2 a, LU(E;; (4, n, 2 7), where E (0, 1), 7 E (0, 2) and E = f0 E X: f(x) + c(x)) is the error region of f. For any e 2 0, it holds that inf (u(E.) m(8)= 2 a, LU(E; 2 7) = 1 AdvRob, (Fay,.). [Epow(X)
Compared with standard concentration, (4.1) aims to search for the least expansive subset with respect to input regions with high label uncertainty. According to Theorem 4.2, the translated intrinsic robustness limit is defined with respect to Fa,y and is guaranteed to be no greater than AdvRob Although both AdvRob, (Fa)) and AdvRob. (Fa,r) can serve as valid robustness upper bounds for any f E Fa,g. the latter would be able to capture more meaningful intrinsic robustness limit, since sate-of-the--ae classifiers are expected to more frequently misclassify inputs with large label uncertainty, as there is more discrepancy between their assigned labels and the underlying label distribution (Section provides supporting empirical evidence for this on CIFAR-10).
Need for Soft Labels. The proposed approach requires label uncertainty information for training examples. The CIFAR-10H dataset provided soft labels from humans that enabled our experiments, but typical machine learning datasets do not provide such information. Below, we discuss possible avenues estimating label uncertainty when human soft labels are not available and are too expensive to acquire. A potential solution is to estimate the set of examples with high label uncertainty using the predicted probabilities of a classification model. Confident learning (Natarajan et al., 2013; Lipton et al.. 2018; Huang et al., 2019; Northcutt et al., 2021b;a) provides systematic method to identify label errors in dataset based on this idea. If the estimated label errors match the examples with high human label uncertainty, then we can directly extend our framework by leveraging the estimated error set. Our experiments on CIFAR-I0 (see Appendix G), however, suggest that there is a misalignment between human recognized errors and errors produced by confident learning. The existence of such misalignment further suggests that one should be cautious when combining the estimated set of label errors into our framework. As the field of confident learning advances to produce more accurate estimator of label error set, it would serve as a good alternative solution for applying our framework to the setting where human label information is not accessible.
5

---

Published as a conference paper at ICLR 2022
5 MEASURING CONCENTRATION WITH LABEL UNCERTAINTY CONSTRAINTS
Directly solving (4.1) requires the knowledge of the underlying input distribution μe and the ground- truth label distribution function n7-), which usually not available for classification problems. Thus, we consider the following empirical counterpart of (4.1):
minimize (Es(E.) subject to EEG
As(E)) 2 a and LU(E: c, f) 2 7,
(5.1)
where the search space is restricted to some specific collection of subsets G C pow( μ is replaced by the empirical distribution ïss with respect set of inputs sampled from f4, and the empirical label distribution f)x)) is considered as an empirical replacement of (2x) for any given input z E S.
Theorem 5.1, proven in Appendix C.3, characterizes a generalization bound regarding the proposed label uncertainty estimate. It shows that if G is not too complex and f) is close to the ground-trute label distribution function 7), the empirical estimate of label uncertainty (U Tis e, 7)) is guaranteed
to be close to the actual label uncertainty LUU(;; jr, c, 11). The formal definition of the complexity penalty with respect to a collection of subsets is given in Appendix B.
Theorem 5.1 (Generalization of Label Uncertainty). Let (X, uu) be probability space and G C
(x)(X)) be collection of subsets of X. Assume & N x IR + [0, 1] is complexity penalty for G. If
n(.) is close to 17(-) in L -norm with respect to p. i... fx [l)(()) [I S 8n. where By E (0. 1)
a small constant, then for any a, 8 E (0, 1) such that 8 < a, we have
45 6n
Pr Smp
E E 9 and (ME)= a: LU(E: ( cm
S
a a- s @(m, 8).
Remark 5.2. Theorem 5.1 implies the generalization of concentration under label uncertainty constraints (see Theorem C.3 for formal argument of this and its proof in Appendix C.S). If we choose G and the collection of its e-expansions, G. = {E E E G). in a careful way that both of their complexities are small, then with high probability, the empirical label uncertainty constrained concentration will be close to the actual concentration when the search space is restricted to G.
m(E) 2 a, pt, 2 7) as the generalized concentration function under label uncertainty constraints. Then, based on similar proof technique used for Theorem 3.5 in Mahloujifar et al. (2019b), we can further show that if G also satisfies universal approximation property, then with probability 1.
Moreover, define h(u, c, 1, a, Y, C, 9) infgegfu(ES
(14 C, 0, - 5, c) S lim h(s G, 9. az r. (()) S h(p,, ai,,,,n,,,, 5,/a, c), (5.2)
T
where T stands for the complexity of G and Sy denotes a set of samples of size mT)). Appendix C.4 provides formal argument and proof for (5.2). is worth noting that (5.2) suggests that if we increase both the complexity of the collection of subsets G and the number of samples used for the empirical estimation, the optimal value of the empirical concentration problem (5.1) will converge to the actual concentration function with error limit of ó on parameter y. When the difference between the empirical label distribution (i)) and the underlying label distribution 77-)) is negligible, is guaranteed that the optimal value of (5.1) asymptoptically converges to that of (4.1).
Concentration Estimation Algorithm. Although Remark 5.2 provides a general idea how to choose G for measuring concentration, it does not indicate how to solve the empirical concentration problem (5.1) for specific perturbation metric. This section presents a heuristic algorithm for estimating the least-expansive subset for optimization problem (5.1) when the metric is & én-norm or &oo -oom. We choose G union of balls for the fz-norm distance metric and set G as a union of hypercubes for -nom (see Appendix B for the formal definition of union of ba-balls). It is worth noting that such choices of & satisfy the condition required for Theorem C.2, since they are universal approximators for any set and the VC-dimensions of both G and G. are both bounded (see Eisenstat & Angluin (2007) and Devroye et al. (2013)).
The remaining task is to solve (5.1) based on the selected G. Following Mahloujifar et al. (2019b), we place the balls for lg (or the hypercubes for txo) in a sequential manner, and search for the best placement that satisfies the label uncertainty constraint using greedy approach. Algorithm I in Appendix D gives pseudocode for the search algorithm. It initializes the feasible set of the hyperparmeters Ω as empty set for each placement of balls (or hypercubes), then enumerates all

---

Published as a conference paper at ICLR 2022
0.4 quartt
0.0 quartts
5000
Frequu ency
4000
3000
Monaeiy X0c
2000
Datipaan, Sicat, 4-deat 5-dag T-horom Bask
Exampla-wise Label Uncartainty
(a) Illustration of CIFAR-10 and CIFAR-10H
(b) Label Uncertainty Distribution
Figure (a) Visualization of the CIFAR-10 test images with the soft labels from CIFAR- IOH, the original assigned labels from CIFAR-10 10 and the label uncertainty scores computed based on Definition 4.1. (b) Histogram the label uncertainty distribution for the CIFAR-10 test dataset.
the possible initial placements, Smit (u, k), such that its empirical label uncertainty exceeds the given threshold y. Finally, among all the feasible ball (or hypercube) placements, it records the one that has the smallest e-expansion with respect the empirical measure jıs. In this way, the input region produced by Algorithm serves as a good approximate solution to the empirical problem (5.1).
6 EXPERIMENTS
We conduct experiments on the CIFAR- 10H dataset (Peterson et al., 2019). which contains soft labels reflecting human perceptual uncertainty for the 10,000 CIFAR- 10 test images (Krizhevsky & Hinton, 2009). These soft labels can be regarded as an approximation of the label distribution function nn.) at each given input, whereas the original CIFAR- 10 test dataset provides the class labels given by the concept function c(-). We report on experiments showing the connection between label uncertainty and classification error rates (Section 6.1) and that incorporating label uncertainty enables better intrinsic robustness estimates (Section 6.2). Section 6.3 demonstrates the possibility of improving model robustness by abstaining for inputs in high label uncertainty regions.
6.1 ERROR REGIONS HAVE LARGER LABEL UNCERTAINTY
Figure 2(a) shows the label uncertainty scores for several images with both the soft labels from CIFAR- 10H and the original class labels from CIFAR 10 (see Appendix for more illustrations). Images with low uncertainty scores are typically easier for humans to recognize their class category (first row of Figure 2(a)), whereas images with high uncertainty scores look ambiguous or even misleading (second and third rows). Figure 2(b) shows the histogram of the label uncertainty distribution for all the 10, 000 CIFAR-10 test examples. In particular, more than 80% of the examples have label uncertainty scores below 0.1, suggesting the original class labels mostly capture the underlying label distribution well. However, around 2% of the examples have label uncertainty scores exceeding 0.7, and some 400 images appear be mislabeled with uncertainty scores above 1.2.
We hypothesize that ambiguous or misleading images should also be more likely to be misclassified as errors by state-of-the-art machine learning classifiers. That is, their induced error regions should have larger that typical label uncertainty. To test this hypothesis, we conduct experiments on CIFAR-10 10 and CIFAR- -OH datasets. More specifically, we train different classification models, including intermediate models extracted at different epochs, using the CIFAR-10 training dataset, then empirically compute the standard risk, adversarial risk, and label uncertainty of the corresponding eтror region. The results shown in Figure 3 (see Appendix E for experimental details).
Figures 3(a) and 3(b) demonstrate the relationship between label uncertainty and standard risk for various classifiers produced by standard training and adversarial training methods under tox perturba- tions with = 8/255. In addition, we plot the label uncertainty with error bars of randomly-selecte images from the CIFAR- 10 test dataset as reference. As the model classification accuracy increases, the label uncertainty of its induced error region increases, suggesting the misclassified examples tend have higher label uncertainty. This observation holds consistently for both standard and
7

---

Published as a conference paper at ICLR 2022
0.0
1804 rowetaiig
Fir.
(a) Standard Training
(b) Adversarial Training
(c) RobustBench
Figure 3: Visualizations of error region label uncertainty versus standard risk and adversarial risk
with respect to classifiers produced by different machine learning methods: (a) Standard- classifiers with different network architecture; (b) addersarially-trriine classifiers using different learning algorithms; (c) Stateooftthe-ar adversarially robust classification models from RobustBench.
0.9
(Intrinsic) Robustries
Intriisicc Robustmess
0.9
0.7
0.8
0.6
talfspace Ty 00]
0.7
half-paoc (r
typercuses ( 6)
0.00
0.35
0.10
0.15
8
0.05
0.10
0.15
Standard Risk
Standard Risk
(a) Lo perturbations 8/255)
(b) la perturbations (c 0.5)
Figure 4: Estimated intrinsic robustness based on Algorithm with 0.17 under (a) foo pertur- bations with = 8/255; and (b) & perturbations with c 0.5. For comparison, we plot baseline estimates produced without considering label uncertainty using a half-space searching method (Prescott et al., 2021) and using union hypercubes or balls (Algorithm I with 7 = 0). Robust accuracies achieved by state-of-the-art RobustBench models are plotted in green.
adversarially trained models with any tested network architecture. Figure 3(c) summarizes the error region label uncertainty with respect to the statc-of-the-ar adversarially robust models documented in RobustBench (Croce al., 2020). Regardless of the perturbation type the learning method, the average label uncertainty of their misclassified examples all falls into a range of (0.17,0. 0.23), whereas the mean label uncertainty of all the testing CIFAR-IO data is less than 0.1. This supports our hypothesis that error regions of state-of-the-arr classifiers tend to have larger label uncertainty, and our claim that intrinsic robustness estimates should account for labels.
6.2 EMPIRICAL ESTIMATION OF INTRINSIC ROBUSTNESS
In this section, we apply Algorithm estimate the intrinsic robustness limit for the CIFAR-I0 dataset under &oo perturbations with 8/255 and & perturbations with e = 0.5. We set the label uncertainty threshold y 0.17 to roughly represent the error region label uncertainty of of the-art classification models (see Figure 3). In particular, we adopt 50/50 train-test split over the original 10, 000 CIFAR-I0 10 test images (see Appendix for experimental details).
Figure 4 shows our intrinsic robustness estimates with 0.17 when choosing different values of a. We include the estimates of intrinsic robustness defined with F. as a baseline, where no label uncertainty constraint is imposed (> 0). Results are shown both for our b,-bll searching method and the half-space searching method in Prescott et al. (2021). We also plot the standard error and the robust accuracy of the state-of- ofrthe-art adversarially robust models in RobustBench (Croce et al., 2020). For concentration estimation methods, the plotted values are the empirical measure of the returned aptimally-searchee subset (r-axis) and the empirical measure of its e-expansion (y-axis).
8

---

Published as a conference paper at ICLR 2022
1.00
1.00
0.95
0.90
0.85
Accuracy
Accuracy
0.80
0.25
0.80
0.65
0.75
robust ecc
0.5
0.3 077
0.4
05
0.73
0.0
0.3
ratio abstalned high uncertainty inouts
ratio of ebstained high uncertainty inputs
(a) Carmon et al. (2019)
(b) Wu et al. (2020)
Figure 5: Accuracy curves for different adverssriillly-raieeee classifiers, varying the abstaining ratio of CIFAR-10 images with high label uncertainty score: (a) Carmon et al. (2019) for foo perturbations with 8/255; (b) Wu et al. (2020) for f2 perturbations with 0.5. Corresponding cut-off values of label uncertainty are marked on the r-axis with respect to percentage values of {0.02, 0.1, 0.2).
Compared with the baseline estimates, are uniformly lower across all the considered settings (similar results are obtained under other experimental settings, Table in Appendix F). Although both of these estimates serve as legitimate upper bounds on the maximum achievable ad versariial robustness for the given task, our estimate, which takes data labels into account, being closer the robust accuracy achieved by state- of-the-art classifiers indicates it is more accurate characterization of intrinsic robustness limit. For instance, under foo perturbations with = 8/255, the best adversarially-tran trained classification model achieves 66% robust accuracy with approximately 8% clean error, whereas our estimate indicates that the maximum robustness one can hope for is about 82% as long as the classification model has at least 8% clean error. In contrast, the intrinsic robustness limit implied by standard concentration is as high as 90% for the same setting, which again shows the insufficiency of standard concentration.
constrained intrinsic robustness estimates
6.3 ABSTAINING BASED ON LABEL UNCERTAINTY
Based on the definition of label uncertainty, and our experimental results in the previous subsections, expect classification models to have higher accuracy examples with low label uncertainty. Figure shows the results of experiments to study the effect of abstaining based on label uncertainty on both clean and robust accuracies using adversarially-traine
CIFAR-10 classification models from 8/255) and Wu et al. (2020) (Ez, 0.5). We first sort all the test CIFAR-10 images based on label uncertainty, then evaluate the model performance with respect to different abstaining ratios of top uncertain inputs. The accuracy curves suggest that potential way improve the robustness of classification systems enable the classifier an option to abstain on examples with high uncertainty score.
Carmon et al. (2019) (foo.
For example, if allow the robust classifier of Carmon et al. (2019) to abstain on the 2% of the test examples whose label uncertainty exceeds 0.7, the clean accuracy improves from 89.7% to 90.3%, while the robust accuracy increases from 59.5% 60.4%. This is close to the maximum robust accuracy that could be achieved with a 2% abstention rate (0.595/ /11 0.02) 0.607). This result points to abstaining on examples in high label uncertainty regions as a promising path towards achieving adversarial robustness.
CONCLUSION
Standard concentration fails to sufficiently capture intrinsic robustness since it ignores data labels. Based on the definition of label uncertainty, we observe that the error regions induced by of the-art classification models all tend to have high label uncertainty. This motivates us to develop an empirical method to study the concentration behavior regarding the input regions with high label uncertainty, which results in more accurate intrinsic robustness measures for benchmark image classification tasks. Our experiments show the importance of considering labels in understanding intrinsic robustness, and further suggest that abstaining based on label uncertainty could be a potential method to improve the classifier accuracy and robustness.

---

Published as a conference paper at ICLR 2022
AVAILABILITY
An implementation our method, and code for reproducing our experiments, is available under an open source license from: http://ghtib.ooookbaaccnnnniinip lu.
ACKNOWLEDGEMENTS
This work partially funded by award from the National Science Foundation (NSF) SaTC program (Center for Trustworthy Machine Learning, # #1804603).
ETHICS STATEMENT
Our work is primarily focused on deepening our understanding of intrinsic adversarial robustness limit and the main contributions in this paper are theoretical. Our work could potentially enable construction of more robust classification systems, as suggested by the results in Section 6.3. For most applications, such autonomous vehicles and malware detection, improving the robustness of classifiers is beneficial to society. There may be scenarios, however, such as face recognition where uncertainty and the opportunity to confuse classifiers with adversarial perturbations may be useful, so enabling more robust classifiers in these domains may have negative societal impacts.
REPRODUCIBILITY STATEMENT
Details of our experimental setup and methods are provided in Appendix E, and all of the datasets we use are publicly available. In addition, we state the assumptions for our theoretical results in each theorem. Detailed proofs of all the presented theorems are provided in Appendix C.
REFERENCES
Jean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang, Alhussein Fawzi, Robert Stanforth, and Pushmeet Kohli. Are labels required for improving adversarial robustness? In NeurIPS, 2019.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, 2018.
Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Lower bounds on adversarial robustness from optimal transport. In NeurIPS, 2019.
Christer Borell. The Brunn-Minkowski inequality in Gauss space. Inventiones mathematicae, 30(2): 207-216, 1975.
Sebastien Bubeck, Yin Tat Lee, Eric Price, and llya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning, 2019.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. In NeurIPS, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning, 2020.
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Nicolas Flammarion, Mung Chiang, Prateck Mittal, and Matthias Hein. RobustBench: standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.0966 2020.
Luc Devroye, László Györfi, and Gábor Lugosi. Probabilistic Theory of Pattern Recognition. Springer, 2013.
10

---

Published as a conference paper at ICLR 2022
Elvis Dohmatob.
Generalized no free lunch theorem for adversarial robustness. In International Conference on Machine Learning, 2019.
David Eisenstat and Dana Angluin. The VC dimension of k-fold union. Information Processing Letters, 101(5):111-18,, 2007.
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi, Adversarial vulnerability for any classifier. In NeurIPS, 2018.
Bin-Bin Gao, Chao Xing, Chen- Wei Xie, Jianxin Wu, and Xin Geng. Deep label distribution learning with label ambiguity. IEEE Transactions on Image Processing, 26(6):2825-288) 2017.
Xin Geng. Label distribution learning. IEEE Transactions on Knowledge and Data Engineering, 28 (7):1734-1748, 2016.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, and lan Goodfellow. Adversarial spheres. 1801:080010027:: 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In International Conference on Computer Vision, 2019.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using input transformations. In ICLR, 2018.
Jinchi Huang, Lie Qu, Rongfei Jia, and Binqiang Zhao. O2U-Net: A simple noisy label detection approach for deep neural networks. International Conference on Computer Vision, 2019.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Ryen Krusinga, Sohil Shah, Matthias Zwicker, Tom Goldstein, and David Jacobs. Understanding the (un juterprrrrttyyilliity of natural image distributions using generative models. arXiv: 1901.9149, 2019.
Michel Ledoux. Isoperimetry and Gaussian analysis. In Lectures on Probability Theory and Statistics. Springer, 1996.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In NeurIPS, 2019.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International Conference Machine Learning, 2018.
Saeed Mahloujifar, Dimitrios Diochnos, and Mohammad Mahmoody. The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. AAAI Conference Artificial Intelligence, 2019a.
Saeed Mahloujifar, Xiao Zhang, Mohammad Mahmoody, and David Evans. Empirically measuring concentration: Fundamental limits on intrinsic robustness. In NewrIPS, 2019b.
Aleksander Mądry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. ICLR, 2018.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NeurIPS, 2013.
Curtis Northcutt, Anish Athalye, and Jonas Mueller. Pervasive label emrors in test sets destabilize machine learning benchmarks. NeurIPS (Datasets and Benchmarks Track), 2021a.
Curtis Northcutt, Lu Jiang, and Isaac Chuang. Confident learning: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research, 70:1373-1411, 2021b.

---

Published as a conference paper at ICLR 2022
Nicolas Papemot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation defense to adversarial perturbations against deep neural networks. In IEEE Symposium on Security and Privacy, 2016.
Joshua C Peterson, Ruairidh M Battleday, Thomas Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In International Conference Computer Vision, 2019.
Jack Prescott, Xiao Zhang, and David Evans. Improved estimation of concentration under f--norm distance metrics using half spaces. In ICLR, 2021.
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. In ICLR, 2018.
Ali Shafahi, W. Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? In ICLR, 2019.
Vladimir Sudakov and Boris Tsirelson. Extremal properties of half-spaces for spherically invariant measures. Zapiski Nauchnykh Seminarov Leningrad Otdel Mathematical Institute Steklov (LOMI), 41:14-24, 1974.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Études Scientifiques, 81(1):73-205 1995.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In NeurIPS, 2020.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, 2018.
Eric Wong, Frank R Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In NewrlPS, 2018.
Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust general- ization. NeurlPS, 2020.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. In ICLR, 2018.
Hongyang Zhang. Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference Machine Learning, 2019.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In ICLR, 2020a.
Xiao Zhang, Jinghui Chen. Quanquan Gu, and David Evans. Understanding the intrinsic robustness of image distributions using conditional generative models. In International Conference Artificial Intelligence and Statistics (AISTATS), 2020b.
A RELATED WORK
This section summarizes the work related to ours, beyond the brief background provided in the Introduction. First, discuss the line of research aiming to develop robust classification models against adversarial examples. Then, we introduce the line of works which focus on understanding the intrinsic robustness limit.
12

---

Published as a conference paper at ICLR 2022
A.1 TRAINING ADVERSARIALLY ROBUST CLASSIFERS
Witnessing the vulnerability of modern machine learning models to adversarial examples, extensive studies have been carried out aiming to build classification models that can be robust against adver- sarial perturbations. Heuristic defense mechanisms (Goodfellow et al., 2015; Papernot al., 2016; Guo et al., 2018; Xie et al.. 2018; Mądry et al., 2018) had been most popular until many of them were broken by stronger adaptive adversaries (Athalye et al., 2018; Tramer al., 2020). The only scalable defense which seems to hold up well against adaptive adversaries is PGD-based adversarial training (Madry al., 2018). Several variants of PGD-based adversarial training have been proposed. which either adopt different loss function (Zhang et al., 2019; Wu et al., 2020) make use of additional training data (Carmon al., 2019; Alayrac et al., 2019). Nevertheless, the best current ad serssarriall-ttainne classifiers only achieve around 65% robust accuracy CIFAR-10 against lo perturbations with strength e = 8/ 8/255, even with additional training data (see the leaderboard in Croce et al. (2020)).
To end the arms race between heuristic defenses and newly designed adaptive attacks that break them, certified defenses have been developed based on different approaches, including linear programming (Wong& & Kolter, 2018; Wong et al., 2018), semidefinite programming (Raghunathan et al., 2018), interval bound propagation (Gowal et al., 2019; Zhang et al., 2020a) and randomized smoothing (Cohen et al., 2019; Li et al., 2019). Although certified defenses are able to train classifiers with robustness guarantees for input instances, most defenses can only scale to small networks and they usually come with sacrificed empirical robustness, especially for larger adversarial perturbations.
A.2 THEORETICAL UNDERSTANDING ON INTRINSIC ROBUSTNESS
Given the unsatisfactory status quo of building adversarially robust classification models, line of research (Gilmer et al., 8; Fawzi et al., 2018; Mahloujifar et al., 2019a; Shafahi et al., 2019, 9; Dohmatob, 2019; Bhagoji et al., 2019) attempted explain the adversarial vulnerability from theoretical perspective. These works proved that as long as the input distribution is concentrated with respect to the perturbation metric, adversarially robust classifiers cannot exist. At the core of these results is the fundamental connection between the concentration of measure phenomenon and an intrinsic robustness limit that capture the maximum adversarial robustness with respect to some specific set of classifiers. For instance, Gilmer et al. (2018) showed that for inputs sampled from uniform n-spheres, a model-independent robustness upper bound under the Euclidean distance metric can be derived using the Gaussian Isoperimetric Inequality (Sudakov & Tsirelson, 1974; Borell, 1975). Mahloujifar et al. (2019a) generalized their result to any concentrated metric probability space of inputs. Nevertheless, it is unclear how to apply these theoretical results typical image classification tasks, since whether or not natural image distributions are concentrated is unknown.
To address this question, Mahloujifar et al. (2019b) proposed general way empirically measure the concentration for any input distribution using data samples, then employed it to estimate an intrinsic robustness limit for typical image benchmarks. By showing the existence of a large gap between the limit implied by concentration and the empirical robustness achieved by state-of-the-art ad adversarial training methods, Mahloujifar et al. (2019b) further concluded that concentration of measure can only explain a small portion of adversarial vulnerability of existing image classifiers. More recently, Prescott et al. (2021) further strengthened their conclusion by using the set of half-spaces to estimate the concentration function, which achieves enhanced estimation accuracy. Other related works (Fawzi et al., 2018; Krusinga et al., 2019; Zhang et al., 2020b) proposed estimating lower bounds on the concentration of measure by approximating the underlying distribution using generative models. None of these works, however, consider data labels. Our main results show that data labels are essential for understanding intrinsic robustness limits.
B FORMAL DEFINITIONS
In this section, we introduce the formal definitions of complexity penalty and union of balbll that are used Section 5. To begin with, we lay out the definition of complexity penalty that is defined for some collection of subsets G pow(??). VC dimension and Rademacher complexity are commonly-un examples of such a complexity penalty.
13

---

Published as a conference paper at ICLR 2022
Definition B.1 (Complexity Penalty). Let 9 S pow(Xt). We say o N:Nx [0, 1] is complexity penalty for G, if for any E (0, 1), it holds that
Pr Sm
E g: (is(E)) (( 2 8| S (mm, 6).
Next, we provide the formal definition of umion of e b-bllls as follows:
Definition B.2 (Union of fy-Balls). Let p 1. For any T E Z+, define the union of T e--balls as
(p) - { Uf=1 BK (u.): A2 E [T], (u,, m) ER R }
When p oo, B(T; (m) corresponds to the union of T hypercubes.
C PROOFS OF MAIN RESULTS
In this section, we provide detailed proof' of our main results, including Theorem 3.2, Theorem 4.2, Theorem 5.1 and the argument presented in Remark 5.2.
C.I PROOF OF THEOREM 3.2
In order to prove Theorem 3.2, make use of the Gaussian Isoperimetric Inequality (Sudakov & Tsirelson, 1974; Borell, 1975). The proof of such inequality can be found in Ledoux (1996).
Lemma C.1 (Gaussian Isoperimetric Inequality). Let (R", (s) be the n-dimensional Gaussian space equipped with the 22-norm distance metric. Consider an arbitrary subset & E pow(R"), suppose H is a half space that satisfies p(H) p(E). Then for any 2 0, we have
((E.) (HL) E q (m(E)) +),,
where (-) is the cumulative distribution function of (V 1) and Φ (-) is its inverse function.
Now we are ready to prove Theorem 3.2.
Proof of Theorem 3.2. To begin with, we introduce the following notations. Let μ... be the probability measure for (--0, I,), and μu+ be the probability measure for (0,, III,), then by definition, we have μ = /2/2 + p4/2 /2. Consider the optimal subset E = argming (me(E) u(() 2 a).
Note that the standard concentration function h(,, a, e) is monotonically increasing with respect to a, thus )(E*)= holds for any continuous μr. Let the Gaussian Isoperimetric Inequality Lemma C.1, it holds for any 2 0 that
(E"E)) and 04 (E")... According to
1 m(E)) 2 (E-(E)) +
1 ( ( +)) +
2 I 2
2 ( ((00(((4) + +e..
(C.1)
Note that the equality (C.1) can be achieved if and only E is half space.
Next, we show that there always exists half space H E pow(X') such that (H) a and 44(H)) (H) = a4. Let f-).. (-) be the PDFs μ_ and μ4 respectively. For any x X, (x) and
f4 (x) are always positive, thus we have
(x) exp(
20 0)TT (x 0)} + 0)
1
(0 x
exp
f- exp
(x 0)}
0²
20d
This implies that the ratio of f+ fx (x) is monotonically increasing with respect to 0 x.
Consider the following extreme half space H_ fo X 0T x b. ||0|2 S 0} such that u(H-) = a. We are going to prove μ (H-) 2 (8*) = a and nu (7L S 14 (8*) a+.
Consider the sets Ex n (HL and (E+)C n H., we have
p+ (3 n (HL n_ 8- n (H-) >
120T. x o2
100Tg x o²
h ( n.H (8+) H-)
inf exp
sup (E(E-)mmH
=
(C.2)
14

---

Published as a conference paper at ICLR 2022
Note that we also have
p- (E* n (HL)9) p (E*
nH- + (()
(())
(C.3)
Thus, combining (C.2) and (C.3), we have
J+ (E" n (HL))) 2 μ+ (4)((()))))
( n and -- n (H-)9) ((E)
Adding the term μ+ (8 0 H or 1 (E* H-) on both sides, we further have
n4 (H-) p (E*) a+ and μ --
2 n (E*) = aa-
(-))=
On the other hand. consider the half space H4 fo E X 0 x b- 0012 2 0} such that ((H+) = a. Based on similar technique, we can prove
P- (H4+) 2 (4())) a+ and 1- S 1- (E*) =
In addition, let = {o X' w x + 0} be any half space such that ((H) 144 and μ are continuous, as we rotate the half space (i.e., gradually increase the value of w O), (H( and u4 (H() will also change continuously. Therefore, it is guaranteed that there exists half space H E pow(()) such that μr- (H) = a and μ4 (H) 0.4 This further implies that the lower bound of (C.1)
Since both
be always be achieved.
Finally, since we have proved the optimal subset has to be half space, the remaining task is to solve the following optimization problem:
min HEpow(X)
- 2 + (M (H0) + +) + + ( (u+ (H)) E)
2
(C.4)
s.t. f E X: w b and m(H) = a.
Construct function su)) the derivative inverse function formula, we compute the derivative of g with respect to u as follows
o Φ (u) + e) + ( (2a u) c), where [0, 2a). Based on
dg(u)
1
(Φ (u) + +
d$ (u)
exp
du
22
2
du
(2a u) + )
dΦ-1((e u)
+
exp
v 2m
2
du
(u) +)
( (u))²
exp
eep
2
( u) +e)²
{Φ (Φ-1 u))²
exp
eepp
2
exp(-22/2)
exp( - c (w)) -exp( - cT - - wi)
Noticing the term (())- is monotonically decreasing with respect to we then know that g(u) is monotonically increasing in [0, a] and monotonically decreasing in [a, 2a]. Therefore. this suggests that the optimal solution to (C.4) is achieved when (H) reaches its maximum or its minimum. According to the previous argument regarding the range of a and a4,, we can immediately prove the optimality results of Theorem 3.2.
C.2 PROOF OF THEOREM 4.2
In this section, we prove Theorem 4.2 based on techniques used in Mahloujifar et al. (2019a) for proving the connection between the standard concentration function and intrinsic robustness with respect to the set of imperfect classifiers.
Proof of Theurem 4.2. Let Ex be the optimal solution to (4.1), then yu(E)) corresponds to the optimal value (4.1). We are going to show 1 - (d = ((E)) by proving both directions.
First, we prove AdvRob, (Fa,,, c) 2 ((E)). Let f be any classifier within Fa,y, and {(f) be the corresponding error region of f. According to the definitions of risk and adversarial risk, we have
Risk(f. ((E()) and AdvRisk ((E(()))
15

---

Published as a conference paper at ICLR 2022
where Ee(f) represents the c-expansion of E(f). Since f Fa,,, we have Risk(f, = ((E(f)) 2 a and LU( 27.
Thus, by (4.1), we obtain that
2 - AdvRob = AdvRisk, 2 (LE)).
By taking the infimum over f over Fa,, on both sides, we prove 1 - AdvRob. (Fa c) 2 u(E)).
Next, we show that AdvRob, (Fa, c) S ((E)). We construct classifier f such that c(a:) otherwise.
(*)x) c(a:) if ; I" (x)
Note that by construction, 0x corresponds to the error region f* Thus according to the definitions of risk and adversarial risk, we know
Risk( c) = μ(E*) 2 and AdvRisk, c)) ;c)==((E))
p,, Since T.U C, 1)) 7 we know the error region label uncertainty of f is least 7. Thus, by definition of intrinsic robustness, know 1 Ad
(Fam S AdvRisk, = pl
Finally, putting pieces together, we complete the proof.
C.3 PROOF OF THEOREM 5.1
Proof of Theorem 5.1. For simplicity, denote by lu( c, 1- [n)())) (-((a=(xx)) c(x) max, so(m) [n(x)] y the label uncertainty of given input æ with respect to c(-) and 17(-). Let & be subset in G such that ((E)= 2 and (p(E) f(EE) S 6, where 8 is constant much smaller than a. Then according to Definition 4.1, we can decompose the estimation error of label uncertainty as:
LU(E: LU(E:As, m(E) Je Iu(z; dp
1
1
Iu(a;; c, 7 dis
As(E) S Iu(xx; c, du
1 U(E)
is(E))
po(E) L [l((z; lu(x; c, n) du
12
()(()) (ʃ Iu(z;; n du Iu(x;; dās
Is
Next, we upper bound the absolute value of the three components, respectively.
Consider the first term I1- Note that 0 < lu(x;;,)) 2 for any X. thus we have [. [u( e, n) dpl < ()) Therefore, we have
44 < (x(E)
2n(E)= < (s((E)
|n(E) - As(())
(s((E)
As for the second term 1z. the following inequality holds for any X
[lu(a;;,)) lu(æ; 7) < [m( 7xx) c(2))
max ('
[n(x=]]
max
[+(x)]
< |[(()) 7)x))1
||
where the second inequality holds because max; a; max; bil I max; la: byl for any b E R2. Therefore, we can upper bound [Z2] by
1 [Tl Ps(E) / [|((>) 7m))], dp TTs(E) / ||(()) 71)))1 dp S ())
1
8n
16

---

Published as a conference paper at ICLR 2022
For the last term I3, since 0 I lu(x;; c, 7) holds for any E X, we have
2 Iu(E) - (s(E))
Mal S A))())
Finally, putting pieces together, we have
5n
46 + og
LU(E:),C,)) LU(E; S (S(E)
|u(E) - iss(E) +
[E)(E)
- 5
provided (u{E) 2 a and |x(E) - N [Es(E) S 6. Making use of the definition of complexity penalty for completes the proof of Theorem 5.1.
C.4 PROOF OF REMARK 5.2
Before presenting the proofs, we first lay out the formal statement of Remark 5.2 in Theorem C.2. The proof technique of Theorem C.2 inspired by Theorem 3.5 in Mahloujifar al. (2019b).
Theorem C.2 (Formal Statement of Remark 5.2). Consider the input metric probability space (X, μ. A), the concept function and the label distribution function 1). Let [ be series of collection of subsets over X. For any N, assume o² and o- are complexity penalties for ((T) and (T) respectively, and 17 is a function such that fx [17((z) - r7(x)) 1 1 S 6..
e, Define 14,,, a, (,,, 9) = infgee(u(EE) u(() 2 a, LU(E: c, 2 7} to be the constrained concentration function. We simply write h(,,, C,, 7; e) when
pow(2). Given sequence of datasets {Sr hTeN. where ST consists of mT)) i.i.d. samples from μ and sequence of real numbers {Ō(T))TeN with ö(T) E (0, a/2). the following assumptions holds:
1. Σr= o" (m(TT, <0
2. Er=1 o² (m(T), ((T)) < co
3. lim 5(T)) =0
4. limy hu,,, c, 7, (,,)) = h(,
5. h is locally continuous w.r.t. and y at (14, a, + e,/or,,, pow(A)))
then with probability 1, we have
hu, n,n,,, Sn/0, s lim hlus,, n, 7, G(T) < h(,, a T-200
To prove Theorem C.2, we use the following theorem regarding the generalization of concentration under label uncertainty constraints. The proof of Theorem C.3 is provided in Appendix C.5.
Theorem C.3 (Generalization of Concentration). Let (X, μ4, A) be metric probability space and
C (2))... Define 1(,, c, 7) a; 7, () inf (u(E.) ((()) 2 a, LU(E; c, 2 } the generalized concentration function under label uncertainty constraints. Then, under the same setting of Theorem 5.1, for any 7, [0, 1), (0, and 8 E (0, a/2), have
Pr [M,,,, 8,7 8' e, 9) Smpm
h( a, 7,6,9)
hhu,c,n, 8, 8 c. + where 8' (48 + 6,) 25) and d. is the complexity penalty for G..
60(m, 8) - 2m, 8),
In addition, we also make use of the Borel-Cantell Lemma to prove Theorem C.2. Lemma C.4 (Borel-Cantelli Lemma). Let (Er)res be a series of events such that Σ Pr Pr(Er] <
Then with probability only finite number of events will occur.
Now we are ready to prove Theorem C.2.
It is worth nothing that this assumption is satisfied for any family of collections of subsets that is universal approximator, such kernel SVMs and decision trees.
17

---

Published as a conference paper at ICLR 2022
Proof of Theorem C.2. Let Ey be the event such that
hlu,c, a ( - h(As, C, a, or
n, (o00maaa-0(0)77+7(70,0)e, (T) (48(T) + 6,,) 28(T)) for any T N. Since ((T) < a/2, thus according to Theorem
+ 6(T) h ( G2 7. a; e, ((T)),
C.3, for any T E N, we have
Pr[Er] S 66 60 (m(T),,(T)) 2 (m(T), 8(T)))
By Assumptions and 2, this further implies
Σ Pr[Er] S Σ (m((()) +
oe (m((), <0.
T=1
T=1
Thus according Lemma C.4, we know that there exists some j N such that for all T 2 j.
C,, 17, - 8(T), 7 (T)),,, - 5(T) s h(Ms, 7, + 8(T),
I 77, (
(C.5)
holds with probability 1. In addition, by Assumptions 3, and 5, we have
li (,,,,, 5(T), ((T)
T-00
lim lim h - 9(T)))
Ti T1 T20
lim - - (Ti))
Ti-+00
=hp,,mm, -,, a,)
where the second equality is due Assumption 4 and the last equality is due Assumptions and 5, Similarly, we have
lim a T-00
Therefore, let T goes to x in (C.5), we have
hp,e,,,,,7 - 6 c) I lim (,, +.t.:..e..tttt.................,
C.5 PROOF OF GENERALIZATION OF CONCENTRATION THEOREM
Proof of Theorem C.3. First, we introduce some notation. Let h(,, c. 77, a, 7: c, () be the optimal value and g(p, C, a, e, G) be the optimal solution with respect to the following generalized concentration of measure problem with label uncertainty constraint:
minimize (EE)) subject to ju()) 2 and LU(E; 27 SEg
(C.6)
Note that the difference between (C.6) and (4.1) is that the feasible set of E is restricted to some collec- tion of subsets G pow(X)). Correspondingly. we let h(jss c, 17, a: y, c, 9) and g c, 7, a, 7, 7,,,9) be the optimal value and optimal solution with respect to the empirical optimization problem (5.1).
+ 0,7 + 6, and E = g e, îi o, 6, G),, where 8' will be specified later. Note that when these optimal sets do not exist, we can select for which the expansion is arbitrarily close to the optimum, then every step of the proof will apply to this variant. According to the definition of complexity penalty, we have
Let m = s(1,
Pr Stum
(is( ((E) 8) < (6m,
(C.7)
Since p=)(E) 2 a by definition, (C.7) implies that
Pr (m(E) S - -5] s $6mm, 8).
(C.8)
Stmm
18

---

Published as a conference paper at ICLR 2022
In addition, according to Theorem 5.1, for any d a0, have
[LU(C.u...)- LUCE S S Stmpm
46 8n
- 20(m, 6),
(C.9)
a 2
where the inequality holds because of (C.8) and the union bound. Since LU(E:ps.c definition, (C.9) implies that
2 y by
LU(E: 57 48 8n
Pr Stmpe
a 20(m, d).
(C.10)
Based on the definition of the concentration function h, combining (C.8) and (C.10) and making use of the union bound, we have
Pr St
(m(E.) & -. v 30(m, 8),
(C.11)
where we set 8 48 24
Note that according to the definition of de, we have
Pr
[lm(E)) (s((E)) s 26 S (m 0),
(C.12)
Stpm
thus combining (C.11) and (C.12) by union bound, we have
Se-jam [ & h(μ, c, n, a 6.7 c, - o] s 30(m, 8) + @. 8).
(C.13)
This completes the proof of one-sided inequality of Theorem C.3. The other side Theorem C.3 can be proved using the same technique. In particular, we have
Pr Jis(Ed
2 h(p, c, n. +. c, +6] 30(m, 6) + de (m,,
(C.14)
Semjum
Combining (C.13) and (C.14) by union bound completes the proof.
D HEURISTIC SEARCH ALGORITHM
The pseudocode of the heuristic search algorithm for the empirical label uncertainty constrained concentration problem (5.1) is shown in Algorithm 1.
Algorithm I: Heuristic Search for Robust Error Region under 4p E (2, oo))
Input a set of labeled inputs {xr, c(x)), )(x)) wES, parameters a, C,
E 0.. Smit +- (), Sexp 0
for 1. 1= -,2,....,
- hlower + -Sint (T - + 1)1, kupper f- (ar(S) [Smitt) Ω Q+ 0:
for S do
for 1s E [klowers Kupper] do
ru(u)= + compute the l, distance from u to the k-th nearest neighbour in S S
Suir(u, k) {o E S Smit || ulI2 S rx(u));
Sexp (u, k) t {x E S Seep || -ull2 S (w) c]:
LU (u, k), As. c, 7) 2 then
10
insert (u, k) into Ω
(ū. k) < argmin S1xxp (u, k) Siiia (u, k}:
12
+ θ rg()):
13
S.n + Sun U Smmi (ū, Re), Sexp + Soxp U Sexp ii, Ic);
14
Output: 3
19

---

Published as a conference paper at ICLR 2022
E DETAILED EXPERIMENTAL SETTINGS
In this section, we specify the details of the experiments presented in Section 6. The robustness results of all the adversarially-trainee models from RobustBench (Croce et al., 2020) are evaluated using the auto attack (Croce& & Hein, 2020). All of our experiments are conducted using a GPU server with NVIDIA GeForce RTX 2080 Ti Graphies card.
Error Region Label Uncertainty. We explain the experimental details of Figure 3. For standard trained classifiers, we implemented five neural network architecture, including a 4-layer neural net with two convolutional layers and two fully- collectddd layers (small), 7-layer neural net with four convolutional layers and three fully-connected layers (large), a ResNet-18 architecture (resner 18), ResNet-50 architecture (resne150) and WideResNet-33-10 architecture (wideresnet). We trained the small and large model using a Adam optimizer with initial learning rate 0.005, whereas we trained the resner18, resnet50 and wideresnet model using a SGD optimizer with initial learning rate 0.01. All models are trained using piece-wise learning rate schedule with a decaying factor of 10 at epoch 50 and epoch 75, respectively. For Figure 3(a), we plotted the label uncertainty and standard risk for the intermediate models obtained at epochs 5, 10. 100 for each architecture. In addition, we also randomly selected different subsets of inputs with empirical measure of 0.05, 0.10, 0.95 and plotted their corresponding label uncertainty with error bars.
For adversarially trained classifiers, we implemented the vanilla adversarial training method (Madry et al., 2018) and the adversarial training method with adversarial weight perturbation (Wu et al., 2020), which are denoted as AT and AT-AWP in Figure 3(b) respectively. Both ResNet-18 18 (resnet18) and WideResNNtt3444
(wideresnet) architecture are implemented for each training method. A 10-step PGD attack (PGD-10 (O) with step size 2/ 2/255 and maximum perturbation size 8/23 3/255 is used for each model during training. In addition, each model is trained for 200 epochs using SGD optimizer with initial learning rate 0.1 and piece-wise learning rate schedule with a decaying factor of 10 at epoch 100 and epoch 150. We record the intermediate models epoch 10, 20, 200 respectively.
Estimation of Intrinsic Robustness. For Figure 4, we first conduct 50/50 50 train-test split over the 10, 000 CIFAR-10 test images, then run Algorithm for each setting on the training dataset to obtain the optimal subset. Here, we choose the value of {0.01, 0.02. 0.15) and tune the parameter T for each a parameter, Next, we evaluate the empirical measure of the optimally-searcie (denoted by empirical risk in Figure 4) and the empirical measure of its e-expansion using the testing dataset, and translate it into an intrinsic robustness estimate. Finally, we plot the empirical risk and the estimated intrinsic robustness for each parameter setting Figure 4.
subset
F ADDITIONAL EXPERIMENTS
This appendix provides additional experimental results, supporting our arguments in Section 6.
Visualization of label uncertainty. Figure 6 shows some CIFAR-10 images with the original CIFAR- 10 labels and the CIFAR- 10H human uncertainty labels. The label uncertainty score computed based on Definition 4.1 and provided under each image.
There are few examples with high label uncertainty, whose CIFAR-10 10 label contradicts with the CIFAR- 10H soft label (see the first two images in Figure 6(a)), indicating they are actually mislabeled. The images with uncertainty scores around 1.0 do appear to be images that are difficult for human to recognize, whereas images with lowest uncertainty scores look clearly representative of the labeled class. These observations show the usefulness of the proposed label uncertainty definition.
Estimation of Intrinsic Robustness. Table summarizes our estimated intrinsic robustness limits produced by Algorithm I for different hyperparameter settings. In particular, we set 0.05 and = 0.17 to roughly reflect the standard error and the label uncertainty of the error regions with respect to the state-of-the-arr classification models (see Figure 3), use {4/255,8 8/255, 16/255) for &or and c E (0.5, 1.0, 1.5) for lz. Note that we also compare our estimate with the intrinsic robustness limit implied by the standard concentration by setting
for each setting.
We perform a 30/50 train-tess split on the CIFAR-10 10 test images: we obtain the optimal subset with the smallest e-expansion the training dataset based on Algorithm 1 and evaluate it the testing
20

---

Published as a conference paper at ICLR 2022
Accerait L.ML
soomiarr 1755
L752
urcatarto
613
51 423224774
Daarplans, 2-gatemoziee 2-rdd 3-stl 4-derr.2 2-dog. B-lrog. N-tore, Bultis, 9-trock)
0-arpiane 1-cuismoblle 2.brd. 3-p0, 4ederr Sacorr 6-bog Jatrew B-stip p-trud)
(a) Highest Uncertainty Score
(b) Lowest Uncertainty Score
Incerianty 0350
soonlarly 0393
urcntasty:
Lece 3.035
Picelanty
avootantyy
eroatenter
Dalrplane: Ivautommbiee 2-aid. 3estt E-deer, 1-dag. 6-frog, 7.hors,, B-thlo, S-ruck)
@aiipaare: 1-sutomobile, 2-bied 3-car, 4ideer. Sicoo, 6-fro,, 7-norse, Biship 9-trac))
(c) Uncertainty Score around 1.0
(d) Uncertainty Score around 1.0
Figure 6: Illustration of human uncertainty labels and label uncertainty of CIFAR-10 test images. Each subfigure shows a group of images with certain level of uncertainty score.
dataset. We report both the empirical measure of the optimally-found subset (Empirical Risk Table 1), and the translated intrinsic robustness estimate. These results show that our estimation of intrinsic robustness generalizes from the training data to the testing data, and support the argument that our estimate is accurate characterization of intrinsic robustness compared with standard one.
G ESTIMATING LABEL ERRORS USING CONFIDENT LEARNING
The proposed concentration estimation framework relies on the knowledge of human soft labels to determine which example has label uncertainty exceeding certainty threshold. Since most machine learning datasets do not provide such information like CIFAR-10E this raises the question of how to extend our method to the setting where human soft labels are unavailable.
We make initial attempt to address the aforementioned issue using the confident learning approach of Northcutt et al. (2021b). Their goal was to identify label emror for dataset, which closely related to label uncertainty. The method first computes confidence joint matrix based the predicted probabilities pretrained classifier, then selects the top examples based on ranking rule, such as self-confidence max margin. If we able approximate human label uncertainty from the raw
21

---

Published as a conference paper at ICLR 2022
Table 1: Summary of the main results using method for different settings CIFAR-10 dataset.
We conduct 5 repeated trials for each setting to record the mean statistics and its standard deviation.
Empirical Risk (%)
Intrinsic Robustness (%)
Metric
T
training
testing
training
testing
0.0
5.80 1 0.04
4.50 + 0.21
93.48 0.10
93.86 1 0.26
4/255
0.17
5
5.84 + 0.10
5.06 = 0.82
92.03 + 0.45
92.61 = 1.12
0.0
10
5.77 + 0.01
1.76 + 0.27
92.89 0.11
92.36 + 0.33
0.05
8/255
0.17
10
5.77 + 0.02
1.85 + 0.58
90.91 + 0.53
90.98 + 1.03
0.0
5.68 + 0.04
5.30 + 0.33
88.44 + 0.47
87.89 + 1.24
16/25s
0.17
5.67 + 0.25
4.79 + 0.75
81.96 + 1.69
83.83 + 2.37
0.0
5.76 + 0.00
5.41 + 0,60
93.78 + 0.10
93.51 + 0.67
0.17
5.76 + 0.00
5.36 + 0.14
91.89 0.38
91.70 + 0.49
0.0
5.76 + 0.00
6.00 + 0.50
92.93 + 0.06
92.22 1 0.55
8/
0.05
1.0
0.17
5.76 1 0.00
5.32 + 0.29
87.86 0.79
87.75 + 0.58
0.0
5.76 + 0.00
5.67 + 0.56
91.98 19880000 0.13
91.82 + 0.65
1.5
0.17
5.76 1 0.00
5.69 1 0.45
83.33 2.04
82.87 + 2.50
ert
non-err
0.20
0.5
Predision Rate
Density
0.15
0.05
0.0
0.00
0.25
0.50
0.75
1.00
1.25 1.50 175
0.0
0.2
0.4
0.6
0.8
10
HLman Label Uncertainty
Recal
(a) Error versus Non-error
(b) Precision Recall Curve
Figure 7: Illustration of misalignment label errors recognized by human and those identified by confident learning (a) Distribution of human label uncertainty between errors and non-errors estimated using confident learning; (b) Precision-recall curve for estimating the of examples with human label uncertainty exceeding 0.5.
inputs and labels, or identify the set of examples with high label uncertainty, then we can immediately adapt proposed framework by leveraging such estimated results. However, observe only weak correlation between the set of label errors that are produced by confident learning and the set of examples with high human label uncertainty.
We conduct the experiments on CIFAR-10 and identify the set of label errors based on confident learning. We train a ResNet-50 based classification model the CIFAR-10 training data, and select examples in the CIFAR-10 test dataset as labeling errors using the best ranking method suggested in Northcutt et al. (2021b). Figure 7()) compares the distribution of human label uncertainty (based on the human soft labels from CIFAR-10H) between the set of estimated label error and non-erron Although the set of examples estimated as label error have relative higher human label uncertainty compared with non-errors, there exist over 30% of estimated label errors have 0 label uncertainty for human annotators. implies that there a mismatch between label errors identified by human and that estimated using confident learning techniques. This is further confirmed by the precision-recall curve presented Figure 7(b). We treat examples with human label uncertainty exceeding 0.5 as the 'ground-trute truth' uncertain images, and vary the size of produced set of label errors plot the precision and recall curve. The fact that precision rate is uniformly lower than 0.25, indicating that over 75% of the estimate error examples have human label uncertainty less than 0.5.
22

---

Published as a conference paper at ICLR 2022
A1514
ST CATEAA
hen 13h
CIN 2e
2011
0114
A1314
Gurmpane,, 1- suutombbrls, 2bb, S-car, didder, S-cee, 6 fog, 7-hom Baship (.track
Daarparne 1-steomobile, 2 land. S-eal 4ideen 5-deg, 6ifrog 2-hore Biatip, trtruck
31
ine
FIRL BAN BE 1AM
8CL
612345570
12
31
④ Arplann Nutomebii 2 Bis. rac. dene deg. mmg homa B Righp mrink
Amplann Nutommbiln 2 hec, Tew. dene cing frng hores B dig mrurk
Figure 8: Visualization of label distribution of top uncertain CIFAR-10 10 test images estimated using confident learning approach. Both human and estimated label distribution are plotted in each figure. The corresponding label uncertainty scores are computed and provided under each image, while the original CIFAR-10 label is highlighted in blue above each image.
Figure visualizes the human label distribution and estimated label distribution on CIFAR-10 10. We compute the estimated label uncertainty of each CIFAR-10 testing examples by replacing the human label distribution with the predicted probabilities the trained model. can be seen that there exists misalignment between the human label distribution and the distribution estimated using neural network. This again confirms that label errors produced by confident learning are not guaranteed to be examples that difficult for humans.
23


Reviews:
[{"review_id": "z7zHUGDgLeI", "reviewer": "Reviewer_jR8K", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "**Strengths**\n- The motivation of this paper is very clear. The authors point out the issues of the prior methods clearly. Besides, this paper explains why the class labels are important to be involved well. \n- The writing and organization of this paper are great, which makes it easy to follow.\n- The theoretical analysis is detailed and convincing. \n\n**Weaknesses & Questions**\n- Part of the explanation is not very detailed and confused. For example, the definition of label uncertainty in this paper is not very intuitive. It is expected for some explanations at a high level. \n- Could the claims of this paper be used to improve the performance of adversarial attacks and defenses?\n- I am concerned about the availability of soft labels and the effectiveness of confident learning methods for estimating label uncertainty. This may limit the application of the proposed method in the real world.", "summary_of_the_paper": "This paper focuses on adversarial learning, which is one of the hottest topics in machine/deep learning. The authors are concerned that the standard concentration of measure problem in prior works cannot capture realistic intrinsic robustness well. In this paper, the information of class labels is therefore introduced into intrinsic robustness limits. Both theoretical analysis and experimental results are provided. ", "summary_of_the_review": "This paper focuses on an important problem in adversarial learning. The motivation, writing, and theoretical analysis are appreciated, though there are some mentioned issues needed to be addressed. Therefore, in my view, this paper reaches the acceptance line of ICLR. I recommend accepting it. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "it3PmTP-so", "reviewer": "Reviewer_zzwx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Novelty**:\nThe formulation and inclusion of label uncertainty are novel. \n\n**Clarity**:\nThe paper is well written. Mathematical notations and definitions are clear and consistent. The majority of the technical content is clear. However, a few points remain unclear. \n1) Figure 4 captions are not clear. I assume that in figure 4 (a), examples are sorted in ascending label uncertainty order, and in figure 4 (b), examples are sorted in descending label uncertainty order.  \n2) In multiple places, the authors mention *robust accuracy*. However, there lacks any formal definition of this term.\n3) Why is *empirical measure* denoted as *empirical risk* in figure 3 and several other places? I would appreciate it if the authors could elaborate on the relationship between the empirical measure and empirical risk. It seems that they are equivalent numerically. \n\n**Technical questions**:\nWhile I think the paper is mathematically rigorous, there are some confusing descriptions that hinder understanding. \n1) This work claims to achieve a more accurate robustness estimate by deriving an *upper bound* on the intrinsic robustness, and in figure 3, the proposed method demonstrates uniformly lower values compared to the baseline. Confusingly, prior work [1] also claims to achieve a more accurate estimate. However, prior work [1] derived a *lower bound*. It is not clear which work provides a better estimate since there is no direct discussion on the importance of upper and lower bounds and no direct empirical comparison. Overall, I am confused about what constitutes a *better* estimate. This is also related to the next question. \n2) in experiment section 6.2, the authors claim that being closer to the robust accuracy indicates a more accurate characterization of intrinsic robustness. It is not clear why this is the case because there is no discussion on the relationship between intrinsic robustness and robust accuracy. This seems to be the core statement supporting the paper's claim that including label uncertainty indeed improves estimation. \n\n**Significance**: This line of works focuses on empirically estimating the intrinsic robustness of a dataset. Prior works [1] conclude that concentration of measure is not the main contributor to adversarial vulnerability. It is not clear what conclusions we can draw from this paper regarding the source of adversarial vulnerability.  \n\n**Other concerns**:\n1) The paper lists many prior works. However, there is no direct comparison with them other than a baseline.  While there is a theoretical difference, i.e., prior works do not include label uncertainty, it is not clear if they produce less accurate robustness estimates. \n\n2) Abstaining from uncertain predictions seems to be a rather indirect way to address the robustness issue. It is equivalent to counting only confident predictions in order to improve accuracy.  \n\n**Relevant Discussion**:\nThe paper proposes a new formulation of label uncertainty. It seems that the concept of label uncertainty also relates to the concept of *aleatoric uncertainty* [2] that captures the inherent ambiguity of label assignment. Is it possible to extend the current framework to include other definitions of label uncertainty?  \n\n[1] Prescott, Jack, Xiao Zhang, and David Evans. \"Improved Estimation of Concentration Under $\\ell_p $-Norm Distance Metrics Using Half Spaces.\" arXiv preprint arXiv:2103.12913 (2021).\n\n[2] Hüllermeier, Eyke, and Willem Waegeman. \"Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods.\" Machine Learning 110.3 (2021): 457-506.", "summary_of_the_paper": "The paper proposes to include label uncertainty (LU) in the formulation of the concentration of measure problem which has been deemed the cause of adversarial vulnerability. It suggests that the current formulation of intrinsic robustness based on concentration measures is insufficient because of the exclusion of label information. The paper demonstrates a more accurate estimation of intrinsic robustness. Practically, in the original concentration of measure problem, a search algorithm finds the least $\\epsilon$-expansion set $\\mu(\\varepsilon_\\epsilon)$ given a concentration constraint $\\mu(\\varepsilon)>\\alpha$ from a selected collection of data sets. The new formulation adds a label uncertainty constraint to this search algorithm: the label uncertainty of the set $\\varepsilon$ must be larger than $\\gamma$. ", "summary_of_the_review": "The paper is mathematically rigorous and well-motivated. However, some unclear descriptions hinder understanding of the paper fully and it lacks direct empirical comparisons to prior works. I would be happy to raise my score if the authors can address my questions. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fVo9d1oF4pi", "reviewer": "Reviewer_rWcj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The paper is clearly written. Especially, I liked that the paper carefully delivers the preliminaries and adequately covers the literature. I also feel the theory and method are well-motivated, and addresses an important problem of estimating the upper bound of adversarial robustness achievable by the current state-of-the-art classifiers. The Gaussian mixture model example given in Section 3 clearly presents the motivation of the method.\n- One may still concern, however, that the theory (and the empirical method from it) is largely based on Mahloujifar et al. (2019) with some incremental points of considering label uncertainty upon it. Nevertheless, I still feel the work is worth to be shared to the community, given that incorporating label uncertainty for intrinsic robustness is yet a novel aspect, suggesting some useful insights not only for the context of adversarial robustness, but for, e.g., confidence calibration or label noises.\n- I also think the experimental results can be a weakness of the paper. Although the paper confirms their major claims focusing on CIFAR-10H, one may concern that there is no straightforward way to extend these results into other datasets, especially when there is no uncertainty information available. This can reduce the technical significance of the proposed method. The paper could present some results on other datasets with an approximative label uncertanty, e.g., as done in Appendix E on CIFAR-10.", "summary_of_the_paper": "The paper improves the previous results on the intrinsic robustness (i.e., an upper bound on the adversarial robustness over a set of classifiers) based on concentration of data distribution, by incorporating the constraint on the label uncertainty of the models. Specifically, the paper tightens the upper bound on the adversarial robustness given a family of models with error rates $\\ge \\alpha$, by additionally assuming that the average label uncertainty must be $\\ge \\gamma$. This requires an information of label uncertainty for each data sample, so the paper leveraged CIFAR-10H (CIFAR-10 with human-annotated uncertainty) in their experiments. Experimental results on CIFAR-10/CIFAR-10H show that the proposed upper bound can be practically computable, and improves the previous upper bound given the knowledge of CIFAR-10H.", "summary_of_the_review": "Overall, I found the paper is clearly written, well-motivated, and addresses an important problem. Although I feel one may concern on the technical contribution and experimental results, I still feel the work is worth to be shared to the community, given that incorporating label uncertainty for intrinsic robustness is yet a novel aspect, suggesting some useful insights not only for the context of adversarial robustness, but for, e.g., confidence calibration or label noises.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8jKktUgdYVS", "reviewer": "Reviewer_HNrN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "The paper is clear and well written. The main concepts and motivation are clearly introduced and described. Discussion is also clear and informative, showing the relations of label uncertainty with model classification errors.\n", "summary_of_the_paper": "The paper discusses model robustness, claiming that the current studies on the concentration of measurement do not consider label uncertainty. Hence the presented work defines the concept of label uncertainty and suggests a concentration of measurement that incorporates this uncertainty to bring a more accurate model robustness assessment. \n", "summary_of_the_review": "The paper, contribution, and discussion are clear and well written. It is an interesting paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was praised for being clearly written, well-motivated, and for addressing an important problem: measuring intrinsic robustness.
It improves the previous results on intrinsic robustness based on concentration of data distribution, by incorporating the constraint on the label uncertainty of the models.
This requires information on label uncertainty for each data sample rarely available (here CIFAR-10H is considered), but could open new directions for future work on adversarial robustness, confidence calibration or label noises.
Decision: Accept (Poster)