Year: 2021

Abstract:
A fundamental question in adversarial machine learning is whether a robust classifier exists for a given task. A line of research has made progress towards this goal by studying concentration of measure, but without considering data labels. We argue that the 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 that accounts for label uncertainty, resulting in more accurate intrinsic robustness measures for benchmark image classification problems.

heading: 1 INTRODUCTION
text: Since the initial reports of adversarial examples against deep neural networks (Szegedy et 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; Tramer et al., 2020). PGD-based adversarial training (Mądry et al., 2018) and its variants (Zhang et al., 2019; Carmon et al., 2019) are among the few heuristic defenses that have not been broken so far, but these methods still fail to produce satisfactorily robust classifiers, even for classification tasks on benchmark datasets like CIFAR-10. Motivated by the empirical hardness of adversarially-robust learning, a line of theoretical works (Gilmer et al., 2018; Fawzi et al., 2018; Mahloujifar et al., 2019a; Shafahi et al., 2019) have argued that adversarial examples are unavoidable. In particular, 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 a more thorough discussion of related work.)
We argue that the standard concentration of measure problem, which was studied in all of the aforementioned works, is not sufficient to capture a 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 of label uncertainty (Definition 4.1), 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 on the CIFAR-10 and CIFAR-10H (Peterson et al., 2019) datasets demonstrate that error regions induced by state-of-the-art classification models all have high label uncertainty (Section 6.1), which validates the proposed label uncertainty constrained concentration problem.
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 is able to produce a more accurate characterization of intrinsic robustness limit for benchmark datasets such as CIFAR-10 (Section 6.2) than was possible using prior methods that do not consider labels. We also provide empirical evidence showing that both the clean and robust accuracies of stateof-the-art 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 lowercase boldface letters to denote vectors and use [k] to denote {1, 2, . . . , k}. We use In to denote the n × n identity matrix. For any set A, |A| denotes its cardinality, pow(A) is all its measurable subsets, and 1A(·) is the indicator function of A. Consider metric probability space (X , µ,∆), where ∆ : X × X → R≥0 is a distance metric on X . Define the empirical measure of µ with respect to a data set S sampled from µ as µ̂S(A) = ∑ x∈S 1A(x)/|S|. Denote by B (x,∆) the ball around x with radius measured by ∆. The -expansion of A is defined as A (∆) = {x ∈ X : ∃ x′ ∈ B (x,∆) ∩ A}. When ∆ is free of context, we simply write B (x) = B (x,∆) and A = A (∆).

heading: 2 PRELIMINARIES
text: 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); Bubeck et al. (2019); Mahloujifar et al. (2019a;b); Zhang et al. (2020b); Prescott et al. (2021). Definition 2.1 (Adversarial Risk). Let (X , µ,∆) be a metric probability space of instances and Y be the set of possible class labels. Assume c : X → Y is a concept function that gives each instance a label. For any classifier f : X → Y and ≥ 0, the adversarial risk of f is defined as:
AdvRisk (f, c) = Pr x∼µ
[ ∃ x′ ∈ B (x) s.t. f(x′) 6= c(x′) ] .
The adversarial robustness of f is defined as: AdvRob (f, c) = 1−AdvRisk (f, c).
When = 0, adversarial risk equals to the standard risk. Namely, AdvRisk0(f, c) = Risk(f, c) := Prx∼µ[f(x) 6= c(x)] holds for any classifier f . Other definitions of adversarial risk have been proposed, such as the one used in Mądry et al. (2018). These definitions are equivalent to the one we 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) to capture the maximum adversarial robustness with respect to some set of classifiers: Definition 2.2 (Intrinsic Robustness). Consider the input metric probability space (X , µ,∆) and the set of labels Y . Let c : X → Y be a concept function that gives a label to each input. For any set of classifiers F ⊆ {f : X → Y} and ≥ 0, the intrinsic robustness with respect to F is defined as:
AdvRob (F , c) = 1− inf f∈F
{ AdvRisk (f, c) } = sup f∈F {AdvRob (f, c)}.
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 et al. (2018); Mahloujifar et al. (2019a;b); Zhang et al. (2020b), selected F in Definition 2.2 as the set of imperfect classifiers Fα = {f : Risk(f, c) ≥ α}, where α ∈ (0, 1) is set as a small constant that reflects the best classification error rates achieved by state-of-the-art methods.
Concentration of Measure. Concentration of measure captures a ‘closeness’ property for a metric probability space of instances. More formally, it is defined by the concentration function: Definition 2.3 (Concentration Function). Let (X , µ,∆) be a metric probability space. For any α ∈ (0, 1) and ≥ 0, the concentration function of (X , µ,∆) is defined as:
h(µ, α, ) = inf E∈pow(X )
{µ(E ) : µ(E) ≥ α}.
The standard notion of concentration function considers a 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 `2-norm distance metric, and was generalized by Prescott et al. (2021) to other `p norms.

heading: 3 STANDARD CONCENTRATION IS INSUFFICIENT
text: We first explain a 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 to capture a realistic intrinsic robustness limit because it ignores data labels.
Connecting Intrinsic Robustness with Concentration of Measure. Let (X , µ,∆) be the considered input metric probability space, Y be the set of possible labels, and c : X → Y be the concept function that gives each input a label. Given parameters 0 < α < 1 and ≥ 0, the standard concentration problem can be cast into an optimization problem as follows:
minimize E∈pow(X )
µ(E ) subject to µ(E) ≥ α. (3.1)
For any classifier f , let Ef = {x ∈ X : f(x) 6= c(x)} be its induced error region with respect to c(·). By connecting the risk of f with the measure of Ef and the adversarial risk of f with the measure of the -expansion of Ef , 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 f
AdvRisk (f, c) subject to Risk(f, c) ≥ α.
To be more specific, the following lemma characterizes the connection between the standard concentration function and the intrinsic robustness limit with respect to the set of imperfect classifiers:
Lemma 3.1 (Mahloujifar et al. (2019a)). Let α ∈ (0, 1) and Fα = {f : Risk(f, c) ≥ α} be the set of imperfect classifiers. For any ≥ 0, it holds that
AdvRob (Fα, c) = 1− h(µ, α, ).
Lemma 3.1 suggests that the concentration function of the input metric probability space h(µ, α, ) can be translated into an adversarial robustness upper bound that applies to any classifier with risk at least α. If this upper bound is shown to be small, then one can conclude that it is impossible to learn an adversarially robust classifier, as long as the learned classifier has risk at least α.
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 -expansion with regard to the input metric probability space (X , µ,∆), 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(µ, α, ) will remain the same for the considered metric probability space. In sharp contrast, learning an adversarially-robust classifier depends on the joint distribution of both the inputs and the labels.
Moreover, when the standard concentration function is translated into an intrinsic limit of adversarial robustness, it is defined with respect to the set of imperfect classfiers Fα (see Lemma 3.1). The only restriction imposed by Fα is that the classifier (or equivalently, the measure of the corresponding error region) has risk at least α. This fails to consider whereas whether the classifier is learnable or not under the given classification problem. Therefore, the intrinsic robustness limit implied by standard concentration AdvRob (Fα, c) could be much higher than AdvRob (Flearn, c), where Flearn 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 state-of-theart 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 we 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 a simple Gaussian mixture model. Let X ⊆ Rn 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: x ∼ µ = 12N (−θ, σ 2In) + 1 2N (θ, σ
2In), then labeled by a concept function c(x) = sgn(θ>x), where θ ∈ Rn and σ ∈ 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.1, 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 metric. The optimal solution to the standard concentration problem (3.1) is a halfspace, either
H− = {x ∈ X : θ>x+ b · ‖θ‖2 ≤ 0} or H+ = {x ∈ X : θ>x− b · ‖θ‖2 ≥ 0},
where b is a parameter depending on α and θ such that µ(H−) = µ(H+) = α. Remark 3.3. Theorem 3.2 suggests that for the Gaussian mixture model, the optimal subset achieving the smallest -expansion under `2-norm distance metric is a halfspaceH, which is far away from the boundary between the two Gaussian classes for small α. When translated into the intrinsic robustness problem, the corresponding optimal classifier f has to be constructed by treatingH as the only error region, or more precisely f(x) = c(x) if x /∈ H; f(x) 6= c(x) otherwise. This optimally constructed classifier f , however, does not match our intuition of what a predictive classifier would do under the considered Gaussian mixture model. In particular, since all the inputs inH and their neighbours share the same class label and are also far away from the boundary, examples that fall intoH should be easily classified correctly using simple decision rule, such as k-nearest neighbour or maximum margin, whereas examples that are close to the boundary should be more likely to be misclassified as errors by supervisedly-learned classifiers. This confirms our claim that standard concentration is not sufficient for capturing a meaningful intrinsic robustness limit.

heading: 4 INCORPORATING LABEL UNCERTAINTY IN INTRINSIC ROBUSTNESS
text: The previous section discusses why standard concentration of measure fails to satisfactorily capture an intrinsic limit on adversarial robustness. In this section, we first propose a new concentration estimation framework by imposing a constraint based on label uncertainty (Definition 4.1) on the search space with respect to the standard concentration problem (3.1). Then, we explain why this yields a more realistic intrinsic robustness limit.
First, we introduce several notations for defining label uncertainty. Let (X , µ) be the input probability space and Y = {1, 2, . . . , k} denote the complete set of labels. A function η : X → [0, 1]k is said to capture the full label distribution (Geng, 2016; Gao et al., 2017), if [η(x)]y corresponds to the description degree of y to x for any x ∈ X and y ∈ Y , and ∑ y∈[k][η(x)]y = 1 holds for any x ∈ X . For classification tasks that rely on human labeling, one can 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 ∈ pow(X ), 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 , µ) be the input probability space and Y = {1, 2, . . . , k} be the complete set of class labels. Suppose c : X → Y is a concept function that assigns each input x a label y ∈ Y . Assume η : X → [0, 1]k is the underlying label distribution function, where [η(x)]y represents the description degree of y to x. For any subset E ∈ pow(X ) with measure µ(E) > 0, the label uncertainty (LU) of E with respect to (X , µ), c(·) and η(·) is defined as:
LU(E ;µ, c, η) = 1 µ(E) ∫ E { 1− [ η(x) ] c(x) + max y′ 6=c(x) [ η(x) ] y′ } dµ.
We define LU(E ;µ, c, η) as the average label uncertainty for all the examples that fall into E , where 1− [η(x)]c(x) + maxy′ 6=c(x)[η(x)]y′ represents the label uncertainty of a single example {x, c(x)}. The range of label uncertainty is [0, 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 as likely to be the ground-truth label as the assigned label; label uncertainty of 2 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∈pow(X ) µ(E ) subject to µ(E) ≥ α and LU(E ;µ, c, η) ≥ γ, (4.1)
where γ ∈ [0, 2] is a constant. When γ is set as zero, (4.1) simplifies to the standard concentration of measure problem. In this work, we set the value of γ to roughly represent the label uncertainty of the error region of state-of-the-art classifiers for the given classification problem.
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 γ. Theorem 4.2. Define Fα,γ = {f : Risk(f, c) ≥ α, LU(Ef ;µ, c, η) ≥ γ}, where α ∈ (0, 1), γ ∈ (0, 2) and Ef = {x ∈ X : f(x) 6= c(x)} is the error region of f . For any ≥ 0, it holds that
inf E∈pow(X )
{µ(E ) : µ(E) ≥ α, LU(E ;µ, c, η) ≥ γ} = 1−AdvRob (Fα,γ , c).
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 toFα,γ and is guaranteed to be no greater than AdvRob (Fα). Although both AdvRob (Fα) and AdvRob (Fα,γ) can serve as valid robustness upper bounds for any f ∈ Fα,γ , the latter one would be able to capture a more meaningful intrinsic robustness limit, since state-of-the-art 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 6 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 to 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., 2021a;b) provides a systematic method to identify label errors in a 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-10 (see Appendix E), 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 a 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.

heading: 5 MEASURING CONCENTRATION WITH LABEL UNCERTAINTY CONSTRAINTS
text: Directly solving (4.1) requires the knowledge of the underlying input distribution µ and the groundtruth label distribution function η(·), which are usually not available for classification problems. Thus, we consider the following empirical counterpart of (4.1):
minimize E∈G
µ̂S(E ) subject to µ̂S(E) ≥ α and LU(E ; µ̂S , c, η̂) ≥ γ, (5.1)
where the search space is restricted to some specific collection of subsets G ⊆ pow(X ), µ is replaced by the empirical distribution µ̂S with respect to a set of inputs sampled from µ, and the empirical label distribution η̂(x) is considered as an empirical replacement of η(x) for any given input x ∈ 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 η̂ is close to the ground-truth label distribution function η, the empirical estimate of label uncertainty LU(E ; µ̂S , c, η̂) is guaranteed to be close to the actual label uncertainty LU(E ;µ, c, η). 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 , µ) be a probability space and G ⊆ pow(X ) be a collection of subsets of X . Assume φ : N×R→ [0, 1] is a complexity penalty for G. If η̂(·) is close to η(·) in L1-norm with respect to µ, i.e. ∫ X ‖η(x)− η̂(x)‖1dµ ≤ δη , where δη ∈ (0, 1) is a small constant, then for any α, δ ∈ (0, 1) such that δ < α, we have
Pr S←µm
[ ∃ E ∈ G and µ(E) ≥ α : ∣∣LU(E ;µ, c, η)− LU(E ; µ̂S , c, η̂)∣∣ ≤ 4δ + δη α− δ ] ≤ φ(m, δ).
Remark 5.2. Theorem 5.1 implies the generalization of concentration under label uncertainty constraints (see Theorem C.3 for a formal argument of this and its proof in Appendix C.5). To be more specific, if we choose G and the collection of its -expansions, G = {E : E ∈ G}, in a careful way such 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. Moreover, define h(µ, c, η, α, γ, ,G) = infE∈G{µ(E ) : µ(E) ≥ α,LU(E ;µ, c, η) ≥ γ} as the generalized concentration function under label uncertainty constraints. Then, based on a similar proof technique used for Theorem 3.5 in Mahloujifar et al. (2019b), we can further show that if G also satisfies a universal approximation property, then with probability 1, h(µ, c, η, α, γ − δη/α, ) ≤ lim
T→∞ h(µST , c, η̂, α, γ, ,G(T )) ≤ h(µ, c, η, α, γ + δη/α, ), (5.2)
where T stands for the complexity of G and ST denotes a set of samples of size m(T ). Appendix C.4 provides a formal argument and proof for (5.2). It 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 an error limit of δη/α on parameter γ. When the difference between the empirical label distribution η̂(·) and the underlying label distribution η(·) is negligible, it 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 a specific perturbation metric. This section presents a heuristic algorithm for estimating the least-expansive subset for optimization problem (5.1) when the metric is `2-norm or `∞-norm. We choose G as a union of balls for the `2-norm distance metric and set G as a union of hypercubes for `∞-norm (see Appendix B for the formal definition of union of `p-balls). It is worth noting that such choices of G 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. Inspired by the algorithm for `2 proposed in Mahloujifar et al. (2019b), we propose to place the balls for `2 (or the hypercubes for `∞) in a sequential manner, and search for the best placement that satisfies the label uncertainty constraint using a greedy approach. Algorithm 1 in Appendix D gives pseudocode for the search algorithm. It initializes the feasible set of the hyperparmeters Ω as an empty set for each placement of balls (or hypercubes), then enumerates all the possible initial placements, Sinit(u, k), such that its empirical label uncertainty exceeds the given threshold γ. Finally, among all the feasible ball (or hypercube) placements, it records the one that has the smallest -expansion with respect to the empirical measure µ̂S . In this way, the input region produced by Algorithm 1 serves as a good approximate solution to the empirical problem (5.1).

heading: 6 EXPERIMENTS
text: 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 η(·) 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.

heading: 6.1 ERROR REGIONS HAVE LARGER LABEL UNCERTAINTY
text: Figure 1(a) shows the label uncertainty scores for several images with both the soft labels from CIFAR10H and the original class labels from CIFAR-10 (see Appendix F for more illustrations). Images with low uncertainty scores are typically easier for humans to recognize their class category (first row of Figure 1(a)), whereas images with high uncertainty scores look ambiguous or even misleading (second and third rows). Figure 1(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 to 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 and CIFAR-10H 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 error region. The results are shown in Figure 2 (see Appendix G for experimental details).
Figures 2(a) and 2(b) demonstrate the relationship between label uncertainty and standard risk for various classifiers produced by standard training and adversarial training methods under `∞ perturbations with = 8/255. In addition, we plot the label uncertainty with error bars of randomly-selected images from the CIFAR-10 test dataset as a reference. As the model classification accuracy increases,
the label uncertainty of its induced error region increases, suggesting the misclassified examples tend to have higher label uncertainty. This observation holds consistently for both standard and adversarially trained models with any tested network architecture. Figure 2(c) summarizes the error region label uncertainty with respect to the state-of-the-art adversarially robust models documented in RobustBench (Croce et al., 2020). Regardless of the perturbation type or the learning method, the average label uncertainty of their misclassified examples all falls into a range of (0.17, 0.23), whereas the mean label uncertainty of all the testing CIFAR-10 data is less than 0.1. This supports our hypothesis that error regions of state-of-the-art classifiers tend to have larger label uncertainty, and our claim that intrinsic robustness estimates should account for labels.

heading: 6.2 EMPIRICAL ESTIMATION OF INTRINSIC ROBUSTNESS
text: In this section, we apply Algorithm 1 to estimate the intrinsic robustness limit for the CIFAR-10 dataset under `∞ perturbations with = 8/255 and `2 perturbations with = 0.5. We set the label uncertainty threshold γ = 0.17 to roughly represent the error region label uncertainty of state-ofthe-art classification models (see Figure 2). In particular, we adopt a 50/50 train-test split over the original 10, 000 CIFAR-10 test images (see Appendix G for experimental details).
Figure 3 shows our intrinsic robustness estimates with γ = 0.17 when choosing different values of α. 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 `p-ball 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-the-art adversarially robust models in RobustBench (Croce et al., 2020). For concentration estimation methods, the plotted values are the empirical measure of the returned optimally-searched subset (x-axis) and 1− the empirical measure of its -expansion (y-axis). Compared with the baseline estimates, our label-uncertainty constrained intrinsic robustness estimates are uniformly lower across all the considered settings (similar results are obtained under other experimental settings, see Table 1 in Appendix F). Although both of these estimates can serve as legitimate upper bounds on the maximum achievable adversarial robustness for the given task, our estimate, which takes data labels into account, being closer to the robust accuracy achieved by state-of-the-art classifiers indicates it is a more accurate characterization of intrinsic robustness limit. For instance, under `2 perturbation with = 0.5, the best adversarially-trained classification model achieves approximately 73% robust accuracy with 10% clean error, whereas our estimate indicates that the maximum robustness one can hope for is about 83% as long as the classification model has at least 10% clean error. In contrast, the intrinsic robustness limit implied by standard concentration is as high as 88% for the same setting, which again shows the insufficiency of standard concentration.

heading: 6.3 ABSTAINING BASED ON LABEL UNCERTAINTY
text: Following the definition of label uncertainty, and our experimental results in the previous subsections, we expect classification models to have higher accuracy on examples with low label uncertainty. Here, we report on experiments to study the effect of abstaining based on label uncertainty on both clean and robust accuracies.
We use Carmon et al. (2019)’s state-of-the-art adversarially-trained classification model, which achieves 89.7% clean accuracy and 59.5% robust accuracy against `∞ perturbations with = 8/255 on CIFAR-10 (additional experiments using a different classification model are provided in Appendix F). By sorting all the test CIFAR-10 images based on label uncertainty, we evaluate the model performance with respect to different percentages of included examples. Figure 4 shows the clean and robust accuracy curves of the considered classification model on different subsets of examples. The model achieves approximately 65% robust accuracy on the 9,000 test CIFAR-10 images with label uncertainty below 0.22, but only achieves slightly above 20% robust accuracy on the 1,000 images with label uncertainty greater than 0.22.
The accuracy curves shown in Figure 4 suggest a potential way to improve the robustness of classification systems is to enable the classifier an option to abstain on examples with high uncertainty score. Since the originally-assigned class labels of these examples are already disputable, it would be very hard to defend against adversarial perturbations to these examples. As an illustration, if we 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 model clean accuracy will be improved from 89.7% to 90.3%, while the robust accuracy will increase from 59.5% to 60.4%. This is close to the maximum robust accuracy that can be achieved with a 2% abstention rate (0.595/(1 − 0.02) = 0.607). This result points to abstaining on examples in high label uncertainty regions as a promising path towards achieving adversarial robustness.

heading: 7 CONCLUSION
text: We argue that 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 state-of-the-art classification models all tend to have high label uncertainty. This motivates us to propose 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.

heading: ETHICS STATEMENT
text: 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 as 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. Because of anonymity requirement, we do not disclose our funding sources here, but can attest that they are from scientifically-focused government funding agencies and raise no potential conflicts.

heading: REPRODUCIBILITY STATEMENT
text: We provide the source code in the supplemental material with instructions on how to reproduce the experimental results presented in this paper. Details of our experimental setup and methods are provided in Appendix G, 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.

heading: A RELATED WORK
text: This section summarizes the work related to ours, beyond the brief background provided in the Introduction. First, we 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.

heading: A.1 TRAINING ADVERSARIALLY ROBUST CLASSIFIERS
text: 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 adversarial perturbations. Heuristic defense mechanisms (Goodfellow et al., 2015; Papernot et al., 2016; Guo et al., 2018; Xie et al., 2018; Mądry et al., 2018) had been most popular until many of them were broken by stronger adaptive adversaries (Athalye et al., 2018; Tramer et al., 2020). The only scalable defense which seems to hold up well against adaptive adversaries is PGD-based adversarial
training (Mądry et 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) or make use of additional training data (Carmon et al., 2019; Alayrac et al., 2019). Nevertheless, the best current adversarially-trained classifiers can only achieve around 60% robust accuracy on CIFAR-10 against `∞ perturbations with strength = 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.

heading: A.2 THEORETICAL UNDERSTANDING ON INTRINSIC ROBUSTNESS
text: Given the unsatisfactory status quo of building adversarially robust classification models, a line of research (Gilmer et al., 2018; Fawzi et al., 2018; Mahloujifar et al., 2019a; Shafahi et al., 2019; Dohmatob, 2019; Bhagoji et al., 2019) attempted to explain the adversarial vulnerability from a 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 to typical image classification tasks, since whether or not natural image distributions are concentrated is unknown.
To address this question, Mahloujifar et al. (2019b) proposed a general way to 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 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.

heading: B FORMAL DEFINITIONS
text: In this section, we introduce the formal definitions of complexity penalty and union of `p-balls that are used in Section 5. To begin with, we lay out the definition of complexity penalty that is defined for some collection of subsets G ∈ pow(X ). VC dimension and Rademacher complexity are commonly-used examples of such a complexity penalty. Definition B.1 (Complexity Penalty). Let G ⊆ pow(X ). We say φ : N× R→ [0, 1] is a complexity penalty for G, if for any δ ∈ (0, 1), it holds that
Pr S←µm
[ ∃ E ∈ G : |µ̂S(E)− µ(E)| ≥ δ ] ≤ φ(m, δ).
Next, we provide the formal definition of union of `p-balls as follows: Definition B.2 (Union of `p-Balls). Let p ≥ 1. For any T ∈ Z+, define the union of T `p-balls as
B(T ; `p) = { ∪Tt=1 B (`p) rt (ut) : ∀t ∈ [T ], (ut, rt) ∈ Rn × Rn≥0 } ,
When p =∞, B(T ; `∞) corresponds to the union of T hypercubes.

heading: C PROOFS OF MAIN RESULTS
text: In this section, we provide detailed proofs of our main results, including Theorem 3.2, Theorem 4.2, Theorem 5.1 and the argument presented in Remark 5.2.

heading: C.1 PROOF OF THEOREM 3.2
text: In order to prove Theorem 3.2, we 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 (Rn, µ) be the n-dimensional Gaussian space equipped with the `2-norm distance metric. Consider an arbitrary subset E ∈ pow(Rn), supposeH is a half space that satisfies µ(H) = µ(E). Then for any ≥ 0, we have
µ(E ) ≥ µ(H ) = Φ ( Φ−1 ( µ(E) ) + ) ,
where Φ(·) is the cumulative distribution function of N (0, 1) and Φ−1(·) 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 forN (−θ, σ2In) and µ+ be the probability measure forN (θ, σ2In), then by definition, we have µ = µ−/2 + µ+/2. Consider the optimal subset E∗ = argminE∈pow(X ){µ (E) : µ(E) ≥ α}.
Note that the standard concentration function h(µ, α, ) is monotonically increasing with respect to α, thus µ(E∗) = α holds for any continuous µ. Let α− = µ−(E∗) and α+ = µ+(E∗). According to the Gaussian Isoperimetric Inequality Lemma C.1, it holds for any ≥ 0 that
µ(E∗ ) = 1
2 µ−(E∗ ) +
1 2 µ+(E∗ ) ≥ 1 2 Φ(Φ−1(α−) + ) + 1 2 Φ(Φ−1(α+) + ). (C.1)
Note that the equality of (C.1) can be achieved if and only if E∗ is a half space. Next, we show that there always exists a half space H ∈ pow(X ) such that µ−(H) = α− and µ+(H) = α+. Let f−(·), f+(·) be the PDFs of µ− and µ+ respectively. For any x ∈ X , f−(x) and f+(x) are always positive, thus we have
f+(x) f−(x) =
exp { − 12σ2 (x− θ) >(x− θ) }
exp { − 12σ2 (x+ θ)>(x+ θ) } = exp(2θ>x σ2 ) .
This implies that the ratio of f+(x)/f−(x) is monotonically increasing with respect to θ>x.
Consider the following extreme half space H− = {x ∈ X : θ>x + b · ‖θ‖2 ≤ 0} such that µ(H−) = α. We are going to prove µ−(H−) ≥ µ−(E∗) = α− and µ+(H−) ≤ µ+(E∗) = α+. Consider the sets E∗ ∩ (H−){ and (E∗){ ∩H−, we have
µ+ ( E∗ ∩ (H−){ ) µ− ( E∗ ∩ (H−){ ) ≥ inf x∈E∗∩(H−){ exp ( 2θ>x σ2 ) ≥ sup
x∈(E∗){∩H−
( 2θ>x
σ2
) ≥ µ+ ( (E∗){ ∩H− ) µ− ( (E∗){ ∩H−
) . (C.2)
Note that we also have µ+ ( E∗ ∩ (H−){ ) + µ− ( E∗ ∩ (H−){ = µ+ ( (E∗){ ∩H− ) + µ− ( (E∗){ ∩H− ) . (C.3)
Thus, combining (C.2) and (C.3), we have µ+ ( E∗ ∩ (H−){ ) ≥ µ+ ( (E∗){ ∩H− ) and µ− ( E∗ ∩ (H−){ ) ≤ µ− ( (E∗){ ∩H− ) ,
Adding the term µ+ ( E∗ ∩H− ) or µ− ( E∗ ∩H− ) on both sides, we further have
µ+(H−) ≤ µ+(E∗) = α+ and µ−(H−) ≥ µ−(E∗) = α−.
On the other hand, consider the half space H+ = {x ∈ X : θ>x − b · ‖θ‖2 ≥ 0} such that µ(H+) = α. Based on a similar technique, we can prove
µ−(H+) ≥ µ+(E∗) = α+ and µ−(H+) ≤ µ−(E∗) = α−.
In addition, let H = {x ∈ X : w>x + b ≤ 0} be any half space such that µ(H) = α. Since both µ+ and µ− are continuous, as we rotate the half space (i.e., gradually increase the value of w>θ), µ−(H) and µ+(H) will also change continuously. Therefore, it is guaranteed that there exists a half space H ∈ pow(X ) such that µ−(H) = α− and µ+(H) = α+. This further implies that the lower bound of (C.1) can be always be achieved.
Finally, since we have proved the optimal subset has to be a half space, the remaining task is to solve the following optimization problem:
min H∈pow(X )
1 2 Φ ( Φ−1 ( µ−(H) ) + ) + 1 2 Φ ( Φ−1 ( µ+(H) ) + )
s.t. H = {x ∈ X : w>x+ b ≤ 0} and µ(H) = α. (C.4)
Construct function g(u) = Φ ( Φ−1(u) + ) + Φ ( Φ−1(2α − u) + ) , where u ∈ [0, 2α]. Based on the derivative of inverse function formula, we compute the derivative of g with respect to u as follows
dg(u)
du = 1√ 2π exp
{ − (Φ −1(u) + )2
2
} · dΦ −1(u)
du
+ 1√ 2π exp
{ − (Φ −1(2α− u) + )2
2
} · dΦ
−1(2α− u) du
= exp { − (Φ −1(u) + )2
2
} · exp { (Φ−1(u))2
2 } − exp { − (Φ −1(2α− u) + )2
2
} · exp { (Φ−1(2α− u))2
2 } = exp(− 2/2) · [ exp ( − Φ−1(u) ) − exp ( − Φ−1(2α− u) )] .
Noticing the term exp(− Φ−1(u)) is monotonically decreasing with respect to u, we then know that g(u) is monotonically increasing in [0, α] and monotonically decreasing in [α, 2α]. 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 α− and α+, we can immediately prove the optimality results of Theorem 3.2.

heading: C.2 PROOF OF THEOREM 4.2
text: 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 Theorem 4.2. Let E∗ be the optimal solution to (4.1), then µ(E∗ ) corresponds to the optimal value of (4.1). We are going to show 1−AdvRob (Fα,γ , c) = µ(E∗ ) by proving both directions.
First, we prove 1− AdvRob (Fα,γ , c) ≥ µ(E∗ ). Let f be any classifier within Fα,γ , and E(f) be the corresponding error region of f . According to the definitions of risk and adversarial risk, we have
Risk(f, c) = µ(E(f)) and AdvRisk (f, c) = µ(E (f)),
where E (f) represents the -expansion of E(f). Since f ∈ Fα,γ , we have
Risk(f, c) = µ(E(f)) ≥ α and LU(E(f);µ, c, η) ≥ γ.
Thus, by (4.1), we obtain that
1−AdvRob (f, c) = AdvRisk (f, c) = µ(E (f)) ≥ µ(E∗ ).
By taking the infimum over f over Fα,γ on both sides, we prove 1−AdvRob (Fα,γ , c) ≥ µ(E∗ ).
Next, we show that 1−AdvRob (Fα,γ , c) ≤ µ(E∗ ). We construct a classifier f∗ such that f∗(x) = c(x) if x 6∈ E∗; f∗(x) 6= c(x) otherwise.
Note that by construction, E∗ corresponds to the error region of f∗. Thus according to the definitions of risk and adversarial risk, we know
Risk(f∗, c) = µ(E∗) ≥ α and AdvRisk (f∗, c) = µ(E∗ ). Since LU(E∗;µ, c, η) ≥ γ, we know the error region label uncertainty of f∗ is at least γ. Thus, by definition of intrinsic robustness, we know 1−AdvRob (Fα,γ , c) ≤ AdvRisk (f∗, c) = µ(E∗ ). Finally, putting pieces together, we complete the proof.

heading: C.3 PROOF OF THEOREM 5.1
text: Proof of Theorem 5.1. For simplicity, denote by lu(x; c, η) = 1− [ η(x) ] c(x) +maxy′ 6=c(x) [ η(x) ] y′ the label uncertainty of a given input x with respect to c(·) and η(·). Let E be a subset in G such that µ(E) ≥ α and |µ(E) − µ̂(E)| ≤ δ, where δ is a constant much smaller than α. Then according to Definition 4.1, we can decompose the estimation error of label uncertainty as:
LU(E ;µ, c, η)− LU(E ; µ̂S , c, η̂) = 1
µ(E) ∫ E lu(x; c, η) dµ− 1 µ̂S(E) ∫ E lu(x; c, η̂) dµ̂S
=
( 1
µ(E) − 1 µ̂S(E) ) · ∫ E
lu(x; c, η) dµ︸ ︷︷ ︸ I1
+ 1
µ̂S(E) ∫ E [ lu(x; c, η)− lu(x; c, η̂) ] dµ︸ ︷︷ ︸
I2
+ 1
µ̂S(E) (∫ E lu(x; c, η̂) dµ− ∫ E lu(x; c, η̂) dµ̂S ) ︸ ︷︷ ︸
I3
.
Next, we upper bound the absolute value of the three components, respectively. Consider the first term I1. Note that 0 ≤ lu(x; c, η) ≤ 2 for any x ∈ X , thus we have | ∫ E lu(x; c, η) dµ| ≤ 2µ(E). Therefore, we have
|I1| ≤ ∣∣∣∣ 1µ(E) − 1µ̂S(E) ∣∣∣∣ · 2µ(E) ≤ 2µ̂S(E) · |µ(E)− µ̂S(E)|. As for the second term I2, the following inequality holds for any x ∈ X
|lu(x; c, η)− lu(x; c, η̂)| ≤ ∣∣∣∣[η(x)− η̂(x)]c(x)∣∣∣∣+ ∣∣∣∣ maxy′ 6=c(x) [η(x)]y′ − maxy′ 6=c(x) [η̂(x)]y′ ∣∣∣∣ ≤ ∥∥η(x)− η̂(x)∥∥
1 ,
where the second inequality holds because |maxi ai −maxi bi| ≤ maxi |ai − bi| for any a, b ∈ Rn. Therefore, we can upper bound |I2| by
|I2| ≤ 1
µ̂S(E) ∫ E ∥∥η(x)− η̂(x)∥∥ 1 dµ ≤ 1 µ̂S(E) ∫ X ∥∥η(x)− η̂(x)∥∥ 1 dµ ≤ δη µ̂S(E) .
For the last term I3, since 0 ≤ lu(x; c, η) ≤ 2 holds for any x ∈ X , we have
|I3| ≤ 2 µ̂S(E) · ∣∣µ(E)− µ̂S(E)∣∣.
Finally, putting pieces together, we have
|LU(E ;µ, c, η)− LU(E ; µ̂S , c, η̂)| ≤ 4 µ̂S(E) · ∣∣µ(E)− µ̂S(E)∣∣+ δη µ̂S(E) ≤ 4δ + δη α− δ ,
provided µ(E) ≥ α and |µ(E)− µ̂S(E)| ≤ δ. Making use of the definition of complexity penalty for G completes the proof of Theorem 5.1.

heading: C.4 PROOF OF REMARK 5.2
text: 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 is inspired by Theorem 3.5 in Mahloujifar et al. (2019b).
Theorem C.2 (Formal Statement of Remark 5.2). Consider the input metric probability space (X , µ,∆), the concept function c and the label distribution function η. Let {G(T )}T∈N be a series of collection of subsets over X . For any T ∈ N, assume φT and φT are complexity penalties for G(T ) and G (T ) respectively, and η̂ is a function such that ∫ X ‖η̂(x)− η(x)‖1dx ≤ δη .
Define h(µ, c, η, α, γ, ,G) = infE∈G{µ(E ) : µ(E) ≥ α,LU(E ;µ, c, η) ≥ γ} to be the constrained concentration function. We simply write h(µ, c, η, α, γ, ) when G = pow(X ). Given a sequence of datasets {ST }T∈N, where ST consists of m(T ) i.i.d. samples from µ and a sequence of real numbers {δ(T )}T∈N with δ(T ) ∈ (0, α/2), if the following assumptions holds:
1. ∑∞ T=1 φ T (m(T ), δ(T )) <∞
2. ∑∞ T=1 φ T (m(T ), δ(T )) <∞
3. limT→∞ δ(T ) = 0
4. limT→∞ h(µ, c, η, α, γ, ,G(T )) = h(µ, c, η, α, γ, ) 1
5. h is locally continuous w.r.t. α and γ at (µ, c, η, α, γ ± δη/α, , pow(X )),
then with probability 1, we have
h(µ, c, η, α, γ − δη/α, ) ≤ lim T→∞ h(µST , c, η̂, α, γ, ,G(T )) ≤ h(µ, c, η, α, γ + δη/α, ).
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 , µ,∆) be a metric probability space and G ⊆ pow(X ). Define h(µ, c, η, α, γ, ,G) = infE∈G{µ(E ) : µ(E) ≥ α,LU(E ;µ, c, η) ≥ γ} as the generalized concentration function under label uncertainty constraints. Then, under the same setting of Theorem 5.1, for any γ, ∈ [0, 1], α ∈ (0, 1] and δ ∈ (0, α/2), we have
Pr S←µm
[ h(µ, c, η, α− δ, γ − δ′, ,G)− δ ≤ h(µ̂S , c, η̂, α, γ, ,G)
≤ h(µ, c, η, α+ δ, γ + δ′, ,G) + δ ] ≥ 1− 6φ(m, δ)− 2φ (m, δ),
where δ′ = (4δ + δη)/(α− 2δ) and φ is the complexity penalty for G .
In addition, we also make use of the Borel-Cantelli Lemma to prove Theorem C.2. Lemma C.4 (Borel-Cantelli Lemma). Let {ET }T∈N be a series of events such that ∑∞ T=1 Pr[ET ] < ∞. Then with probability 1, only finite number of events will occur.
Now we are ready to prove Theorem C.2.
Proof of Theorem C.2. Let ET be the event such that h ( µ, c, η, α− δ(T ), γ − δ′(T ), ,G(T ) ) − δ(T ) > h ( µ̂ST , c, η̂, α, γ, ,G(T ) ) or
h ( µ, c, η, α+ δ(T ), γ + δ′(T ), ,G(T ) ) + δ(T ) < h ( µ̂ST , c, η̂, α, γ, ,G(T ) ) ,
δ′(T ) = (4δ(T ) + δη)/(α− 2δ(T )) for any T ∈ N. Since δ(T ) < α/2, thus according to Theorem C.3, for any T ∈ N, we have
Pr[ET ] ≤ 6φT (m(T ), δ(T )) + 2φT (m(T ), δ(T ))).
1It is worth nothing that this assumption is satisfied for any family of collections of subsets that is a universal approximator, such as kernel SVMs and decision trees.
By Assumptions 1 and 2, this further implies ∞∑ T=1 Pr[ET ] ≤ 6 ∞∑ T=1 φT (m(T ), δ(T )) + 2 ∞∑ T=1 φT (m(T ), δ(T ))) <∞. Thus according to Lemma C.4, we know that there exists some j ∈ N such that for all T ≥ j, h ( µ, c, η, α− δ(T ), γ − δ′(T ), ,G(T ) ) − δ(T ) ≤ h(µ̂ST , c, η̂, α, γ, )
≤ h ( µ, c, η, α+ δ(T ), γ + δ′(T ), ,G(T ) ) + δ(T ), (C.5)
holds with probability 1. In addition, by Assumptions 3, 4 and 5, we have
lim T→∞
h ( µ, c, η, α− δ(T ), γ − δ′(T ), ,G(T ) ) = lim T1→∞ lim T2→∞ h ( µ, c, η, α− δ(T1), γ − δ′(T1), ,G(T2)
) = lim T1→∞ h ( µ, c, η, α− δ(T1), γ − δ′(T1),
) = h ( µ, c, η, α, γ − δη/α, ) ,
where the second equality is due to Assumption 4 and the last equality is due to Assumptions 3 and 5. Similarly, we have
lim T→∞
h ( µ, c, η, α+ δ(T ), γ + δ′(T ), ,G(T ) ) = h ( µ, c, η, α, γ + δη/α, ) .
Therefore, let T goes to∞ in (C.5), we have h ( µ, c, η, α, γ − δη/α, ) ≤ lim T→∞ h ( µ̂ST , c, η̂, α, γ, ,G(T ) ) ≤ h ( µ, c, η, α, γ + δη/α, ) .

heading: C.5 PROOF OF GENERALIZATION OF CONCENTRATION THEOREM
text: Proof of Theorem C.3. First, we introduce some notation. Let h(µ, c, η, α, γ, ,G) be the optimal value and g(µ, c, η, α, γ, ,G) be the optimal solution with respect to the following generalized concentration of measure problem with label uncertainty constraint:
minimize E∈G
µ(E ) subject to µ(E) ≥ α and LU(E ;µ, c, η) ≥ γ. (C.6)
Note that the difference between (C.6) and (4.1) is that the feasible set of E is restricted to some collection of subsets G ⊆ pow(X ). Correspondingly, we let h(µ̂S , c, η̂, α, γ, ,G) and g(µ̂S , c, η̂, α, γ, ,G) be the optimal value and optimal solution with respect to the empirical optimization problem (5.1).
Let E = g(µ, c, η, α + δ, γ + δ′, ,G) and Ê = g(µ̂S , c, η̂, α, γ, ,G), where δ′ will be specified later. Note that when these optimal sets do not exist, we can select a set 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
Pr S←µm
[ |µ̂S(Ê)− µ(Ê)| ≥ δ ] ≤ φ(m, δ). (C.7)
Since µ̂S(Ê) ≥ α by definition, (C.7) implies that
Pr S←µm
[ µ(Ê) ≤ α− δ ] ≤ φ(m, δ). (C.8)
In addition, according to Theorem 5.1, for any δ ∈ (0, α/2), we have
Pr S←µm [∣∣LU(Ê ;µ, c, η)− LU(Ê ; µ̂S , c, η̂)∣∣ ≤ 4δ + δη α− 2δ ] ≤ 2φ(m, δ), (C.9)
where the inequality holds because of (C.8) and the union bound. Since LU(Ê ; µ̂S , c, η̂) ≥ γ by definition, (C.9) implies that
Pr S←µm
[ LU(Ê ;µ, c, η) ≤ γ − 4δ + δη
α− 2δ
] ≤ 2φ(m, δ). (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 S←µm
[ µ(Ê ) ≤ h(µ, c, η, α− δ, γ − δ′, ,G) ] ≤ 3φ(m, δ), (C.11)
where we set δ′ = 4δ+δηα−2δ . Note that according to the definition of φ , we have
Pr S←µm
[ |µ(Ê )− µS(Ê )| ≤ δ ] ≤ φ (m, δ), (C.12)
thus combining (C.11) and (C.12) by union bound, we have
Pr S←µm
[ µ̂S(Ê ) ≤ h(µ, c, η, α− δ, γ − δ′, ,G)− δ ] ≤ 3φ(m, δ) + φ (m, δ). (C.13)
This completes the proof of one-sided inequality of Theorem C.3. The other side of Theorem C.3 can be proved using the same technique. In particular, we have
Pr S←µm
[ µ̂S(Ê ) ≥ h(µ, c, η, α+ δ, γ + δ′, ,G) + δ ] ≤ 3φ(m, δ) + φ (m, δ). (C.14)
Combining (C.13) and (C.14) by union bound completes the proof.

heading: D HEURISTIC SEARCH ALGORITHM
text: The pseudocode of the heuristic search algorithm for the empirical label uncertainty constrained concentration problem (5.1) is shown in Algorithm 1.
Algorithm 1: Heuristic Search for Robust Error Region under `p(p ∈ {2,∞}) Input : a set of labeled inputs {x, c(x), η̂(x)}x∈S , parameters α, γ, , T
1 Ê ← {}, Ŝinit ← {}, Ŝexp ← {}; 2 for t = 1, 2, . . . , T do 3 klower ← d(α|S| − |Ŝinit|)/(T − t+ 1)e, kupper ← (α|S| − |Ŝinit|); 4 Ω← {}; 5 for u ∈ S do 6 for k ∈ [klower, kupper] do 7 rk(u)← compute the `p distance from u to the k-th nearest neighbour in S \ Ŝinit; 8 Sinit(u, k)← {x ∈ S \ Ŝinit : ‖x− u‖2 ≤ rk(u)}; 9 Sexp(u, k)← {x ∈ S \ Ŝexp : ‖x− u‖2 ≤ rk(u) + };
10 if LU(Sinit(u, k), µ̂S , c, η̂) ≥ γ then 11 insert (u, k) into Ω 12 (û, k̂)← argmin(u,k)∈Ω{|Sexp(u, k)| − |Sinit(u, k)|}; 13 Ê ← Ê ∪ Ball(û, rk̂(û)); 14 Ŝinit ← Ŝinit ∪ Sinit(û, k̂), Ŝexp ← Ŝexp ∪ Sexp(û, k̂);

heading: Output : Ê

heading: E ESTIMATING LABEL ERRORS USING CONFIDENT LEARNING
text: The proposed concentration estimation framework relies on the knowledge of human soft labels to determine which example has label uncertainty exceeding a certainty threshold. Since most machine learning datasets do not provide such information like CIFAR-10H, this raises the question of how to extend our method to the setting where human soft labels are unavailable.
We make an initial attempt to address the aforementioned issue using the confident learning approach of Northcutt et al. (2021a). Their goal was to identify label errors for a dataset, which is closely related to label uncertainty. The method first computes a confidence joint matrix based on the predicted probabilities of a pretrained classifier, then selects the top examples based on a ranking rule, such as
self-confidence or max margin. If we are able to approximate human label uncertainty from the raw inputs and labels, or identify the set of examples with high label uncertainty, then we can immediately adapt our proposed framework by leveraging such estimated results. However, we observe only a 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 on 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. (2021a). Figure 5(a) 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-errors. 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. It implies that there is 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 in Figure 5(b). We treat examples with human label uncertainty exceeding 0.5 as the ‘ground-truth’ uncertain images, and vary the size of produced set of label errors to 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.
Moreover, Figure 6 visualizes the human label distribution and estimated label distribution on CIFAR10. We compute the estimated label uncertainty of each CIFAR-10 testing examples by replacing the human label distribution with the predicted probabilities of the trained model. It can be seen that there exists a misalignment between the human label distribution and the distribution estimated using some neural network. This again confirms that label errors produced by confident learning are not guaranteed to be examples that are difficult for humans.

heading: F OTHER EXPERIMENTS
text: This appendix provides additional experimental results, supporting our arguments in Section 6.
Visualization of label uncertainty. Figure 7 shows some CIFAR-10 images with the original CIFAR10 labels and the CIFAR-10H human uncertainty labels. The label uncertainty score is computed based on Definition 4.1 and provided under each image.
There are a few examples with high label uncertainty, whose CIFAR-10 label contradicts with the CIFAR-10H soft label (see the first two images in Figure 7(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 1 summarizes our estimated intrinsic robustness limits produced by Algorithm 1 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-art classification models (see Figure 2), use ∈ {4/255, 8/255, 16/255} for `∞ and ∈ {0.5, 1.0, 1.5} for `2. Note that we also compare our estimate with the intrinsic robustness limit implied by the standard concentration by setting γ = 0 for each setting.
We perform a 50/50 train-test split on the CIFAR-10 test images: we obtain the optimal subset with the smallest -expansion on the training dataset based on Algorithm 1 and evaluate it on the testing dataset. We report both the empirical measure of the optimally-found subset (Empirical Risk in 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 a more accurate characterization of intrinsic robustness compared with standard one.
Abstaining based on label uncertainty. Figure 8 shows the effect of abstaining based on label uncertainty using Wu et al. (2020)’s state-of-the-art adversarially-trained classification model under `2 perturbation with = 0.5. The accuracy curves show a similar trend to those presented in Section 6.3, which again suggests that abstaining on examples with high label uncertainty is a promising way to improve model robustness.

heading: G DETAILED EXPERIMENTAL SETTINGS
text: In this section, we specify the details of the experiments presented in Section 6. The robustness results of all the adversarially-trained 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 a NVIDIA GeForce RTX 2080 Ti Graphics card.
Error Region Label Uncertainty. We explain the experimental details of Figure 2. For standard trained classifiers, we implemented five neural network architecture, including a 4-layer neural net with two convolutional layers and two fully-connected layers (small), a 7-layer neural net with four convolutional layers and three fully-connected layers (large), a ResNet-18 architecture (resnet18), ResNet-50 architecture (resnet50) and a WideResNet-34-10 architecture (wideresnet). We trained the small and large model using a Adam optimizer with initial learning rate 0.005, whereas we trained the resnet18, resnet50 and wideresnet model using a SGD optimizer with initial learning rate 0.01.
All models are trained using a piece-wise learning rate schedule with a decaying factor of 10 at epoch 50 and epoch 75, respectively. For Figure 2(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 (Mądry 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 2(b) respectively. Both ResNet-18 (resnet18) and WideResNet-34-10 (wideresnet) architecture are implemented for each training method. A 10-step PGD attack (PGD-10) with step size 2/255 and maximum perturbation size 8/255 is used for each model during training. In addition, each model is trained for 200 epochs using a 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 at epoch 10, 20, . . . , 200 respectively.
Estimation of Intrinsic Robustness. For Figure 3, we first conduct a 50/50 train-test split over the 10, 000 CIFAR-10 test images, then run Algorithm 1 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 α parameter. Next, we evaluate the empirical measure of the optimally-searched subset (denoted by empirical risk in Figure 3) and the empirical measure of its -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 in Figure 3.

Review summaries:
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$. 

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.

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.