Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.
- 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.
- 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 

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.

summary_of_the_review: The paper, contribution, and discussion are clear and well written. It is an interesting paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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$. 
main_review: **Novelty**:
The formulation and inclusion of label uncertainty are novel. 

**Clarity**:
The 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. 
1) 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.  
2) In multiple places, the authors mention *robust accuracy*. However, there lacks any formal definition of this term.
3) 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. 

**Technical questions**:
While I think the paper is mathematically rigorous, there are some confusing descriptions that hinder understanding. 
1) 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. 
2) 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. 

**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.  

**Other concerns**:
1) 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. 

2) 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.  

**Relevant Discussion**:
The 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?  

[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).

[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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
main_review: **Strengths**
- 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. 
- The writing and organization of this paper are great, which makes it easy to follow.
- The theoretical analysis is detailed and convincing. 

**Weaknesses & Questions**
- 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. 
- Could the claims of this paper be used to improve the performance of adversarial attacks and defenses?
- 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_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.
review_title: null

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)