Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors provide an extensive characterization of calibration and consistency for surrogates to the l2 robust 0-1 loss, along the lines of what Bartlett et al. and Steinwart provided for the standard 0-1 loss.  They demonstrate that convex losses and supremum-based convex losses are not calibrated, and further that calibration is in general not sufficient to guarantee consistency.  This corrects a previous incorrect assertion made by Bao et al. in a COLT 2020 paper.  They provide experiments which corroborate their results. 
main_review: The results in this paper are, to my knowledge, significant.  Consistency and calibration of convex surrogates to the standard 0-1 loss is by now a classical topic with over a decade of serious research in the area.  Given the numerous questions about the existence of adversarially robust classifiers in complicated hypothesis classes, the study of calibration and consistency in this setting is important.  Although Bao et al. (2020) analyzed consistency and calibration of surrogates to the l2 robust 0-1 loss, the authors demonstrate that they made serious errors throughout their work, thus this work helps address a significant problem with previous work.  They also provide a number of significant extensions of the (incorrect) work of Bao et al, providing analysis of how the calibration and consistency results differ when using linear/relu hypothesis classes as well as the classes of neural networks and all measurable functions.  

I found the exposition clean and friendly to read in the main section, which was impressive given the large number of results presented in the paper.  (I did not have time to read the proof details in the appendix.)  I don't have any significant issues with the paper, but below are a few minor points that I think could help improve the paper.

(1) Figure 1 is unreadable.  Even zooming to maximum on computer, it wasn't possible to see what was happening.  Please re-make the figure and give a more descriptive caption.

(2) A figure for the Segments experiment, showing what the distribution looks like, would be helpful.

(3) For experiments, it wasn't clear to me how the authors calculated the minimizer of the robust 0-1 loss for different settings; is there an exact formula that is possible from using the constructed distribution?  If not, how?

(4) Further discussion on the computational tradeoffs of adversarial consistency would improve the paper.  The results suggest that in order for consistency to hold in this setting, one must use non-convex surrogates, leaving open the question of how to minimize such surrogates, even in the linear hypothesis setting.  Recent work has shown that in the non-robust linear hypothesis setting, minimizers of convex surrogates have sub-optimal performance for learning linear classifiers in the non-realizable setting, while minimizing nonconvex surrogates with gradient descent leads to nearly-optimal guarantees [1'].  Likewise, the current state-of-the-art algorithms for learning robust linear classifiers in the non-realizable setting are based on a supremum-based *non*-convex surrogate in the language of the paper, i.e. adversarial training on a non-convex sigmoidal loss, with convex surrogates having less strong guarantees (although with no lower bounds proving a separation) [2'].  It would be worth commenting on these two works, e.g. around lines 189-191. 


[1'] Non-Convex SGD Learns Halfspaces with Adversarial Label Noise. Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis. NeurIPS 2020

[2'] Provable Robustness of Adversarial Training for Learning Halfspaces with Noise. Difan Zou, Spencer Frei, Quanquan Gu.  ICML 2021

** Post rebuttal **

I'm happy with the author response and am sticking with my strong recommendation for acceptance. 
limitations_and_societal_impact: Adequately addressed
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a detailed analysis on the H-calibration and H-consistency of adversarial surrogate losses. 

It shows that some common used losses for adversarial training are not H-calibrated.  

Some theoretical results on the characterization of H-calibration are established.  The paper also proves that some surrogate losses are indeed H-calibrated.

Some additional theoretical results on H-consistency are established too.


main_review: 1. This paper contains too many theorems, definitions, propositions, and corollaries. It is very difficult to track the main ideas, especially for those who are not familiar with this area.

2. There is a key reference Bao et al. (2020). It seems that this paper is questioning that many results in Bao et al. (2020) are wrong results. Is it possible to make a summary what results in Bao et al. (2020) are not correct and how to correct them?

3. There is a gap between the theory and the practice. Can you provide some numerical analysis on some benchmark datasets by using the proposed H-consistency losses? It would be interesting to see the benefit over the commonly uses loss functions.

4. The perturbation ball is fixed to be the $\ell_2$ ball. Can the analysis be extended to other perturbation such as the $\ell_\infty$ ball?   

5. For the proofs of these theorems, is there any novel techniques beyond the current references? 

6. Is it straightforward to extent the current analysis from binary classification to multiple-class classification?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper provides an extensive analysis of the satisfiability of H-calibration and H-consistency for surrogate losses in binary classification, where the evaluation metric is not the standard 0-1 loss but the adversarial 0-1 loss. The adversarial 0-1 loss is a pointwise loss defined on an input x by calculating the supremum of the 0-1 loss value of a point that can perturb around x within a ball of a pre-specified radius. This paper reveals a negative result showing that many surrogate losses are not H-consistent, especially the convex losses.  This paper also reveals a positive result of a certain class of non-convex losses that can be H-consistent under some assumptions. Synthetic experiments were also provided to justify the relevance of theoretical findings.
main_review: Although this paper looks theoretically heavy and dense at glance, I found that reading this paper was a very enjoyable experience. The paper is very well-written. The authors did a very good job to provide motivation and intuitive explanations for most theoretical results presented in this paper. I appreciate the fact that both margin-based losses and their supremum version are both studied. Also, the hypothesis class considered in this paper goes beyond a simple linear model. Furthermore, it resolves some issues of recent work. Overall, I found the theoretical results of this paper are highly significant and definitely help to improve our understanding of a surrogate loss behavior in adversarially robust classification. Thus, I vote for a strong acceptance for this paper.

Weaknesses:
1. Perhaps more illustration at the beginning of the paper can improve the readability for readers who are not familiar with adversarial surrogate losses, margin losses, a regularity condition for $\mathcal{H}$. Due to space limitations, I understand that doing all this can be quite challenging but it may still be worth considering.
2. One may criticize that the result is limited to the binary classification case, but I think the result only on the binary classification is already sufficient.
3. Some parts of the paper may not be self-contained enough since many contents are deferred to Appendix (deferring the proof is perfectly acceptable in my opinion). But for example, in experiments, my impression is that it is necessary to write down a loss function form (provided in Appendix C.1).

Questions:
1. It is very insightful that H-calibration does not imply H-consistency. Nevertheless, in the setting of adversarial classification considered here, can we say that H-calibration is a "necessary" condition for H-consistency? I believe so but it was not stated clearly in the paper in my understanding or perhaps I missed it. If so, then the notion of H-calibration is still very useful to filter out some surrogate losses without checking the H-consistency condition.
2. Is there any existing results of Fisher consistency in the context of adversarial classification before this paper? If not, do I understand correctly that when we use $\mathcal{H}_{\textrm{all}}$, we are considering a notion of standard Fisher consistency (i.e., infinite sample consistency) and this paper is the first to prove such results?
3. I am a bit confused around Lines 156--160. it is said that studying regular $mathcal{H}$ is enough because Theorem 6, which is specific for symmetric hypothesis set, states that "if $\mathcal{H}$ is NOT regular, then any surrogate loss is $\mathcal{H}$-calibrated. My understanding is that for non-regular set, it causes the definition of $\mathcal{H}$-calibration to be useless, however, since $\mathcal{H}$-calibration is not equivalent to $\mathcal{H}$-consistency, wouldn't this mean they might be worth considering?
4. How strong the requirement that $\mathcal{H}$ is symmetric is? Is this the case for most hypothesis classes we can think of? 
5. Is there other settings that H-calibration does not imply H-consistency other than adversarially robust classification? If I understood correctly, I guess this setting is not the first work that has this phenomenon. Thus, it could be useful to discuss this phenomenon a little bit more to suggest that it is not special only for adversarially robust classification (if space allows). To my knowledge, if I understand correctly, I am aware that in AUC-optimization, calibration also does not imply consistency in the all measurable function cases [1][2]. 
6. Does a relaxed assumption to obtain H-calibration that does not require the Bayes $(\ell_0, \mathcal{H})$-risk to be zero in Theorem 21--23  equivalent to saying that the model misspecification does not occur (i.e., it is well-specified)?
7. Do the presented numbers in Table 1 sufficient to tell that surrogate risks of all candidate losses were successfully minimized? If not, is there a way to do that (maybe it is difficult...)? 
8. Is it straightforward to extend this framework to the multiclass case? 

[1] Uematsu and Lee, On Theoretically Optimal Ranking Functions in Bipartite Ranking, JASA, 2016

[2] Gao and Zhou, On the consistency of AUC pairwise optimization, IJCAI, 2015 (Lemma 3).

Minor comments:
1. The use of \citep and \citet are mixed in a strange way. I am not sure if this was intentional. For example, I think Line 72, many parts in Appendix B, Line 79, 122, 132, 133, 162, 237, 342, 345, 364, 365 should be \citet in my understanding.

Update: I have read other reviews and authors' feedback. I believe this paper did a great job and therefore my score remains unchanged (strong accept).
limitations_and_societal_impact: The discussion was adequate.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on the H-calibration and H-consistency of loss functions in terms of adversarial robustness. The authors claim that the reason for the difficulty in achieving the adversarial robustness is related to the current convex surrogate losses. Theoretically, they showed the limitation of H-calibration of convex loss functions and surrogate loss functions. Furthermore, they rejected the result from previous studies which provides the relationship between H-calibration and H-consistency, and found a condition that the relationship working correctly. They proposed a non-convex loss function to satisfy H-calibration and experimentally showed the advantages of the proposed loss.
main_review: Strength.
* Well-written theorems and their assumptions.
* New proposed surrogate loss.

Weakness.
* A more generalized analysis is needed: The authors use l2 norm for adversarial perturbations. How about l1 norm or l_inf norm?
* A question on the writing: Why Theorem 9 and Corollary 11 are disparted not as in Section 4.1?
* The generalization of proposed \rho-margin loss: The reasonable inspiration of proposing \rho-margin loss is not clear. How about other non-convex surrogate losses?
* Explanations on experiment details: In table 1, why the results on \phi_1 and \phi_2 are missing? Do the results are consistent with other perturbation extent \gamma? The theoretical proof of the optimal value in the unit circle experiment (\theta=0.7855) is missing.
* Lack of experiments: This paper suggests a new loss, however, the advantage of the suggested loss is not strongly supported due to the lack of experiments. Zhang et al. [1] similarly proposed a new loss and provided the proof of the calibration of the proposed loss, then included the extensive experiments on MNIST and CIFAR10. If there are more experiments on bigger data, the claims in the paper becomes more convincing.

I would be happy to raise my score if the authors could address the weakness.

[1] Zhang, H., Yu, Y., Jiao, J., Xing, E., El Ghaoui, L., & Jordan, M. (2019, May). Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning (pp. 7472-7482). PMLR.
limitations_and_societal_impact: Refer to the main review.
review_title: null

Meta-review: I agree with the reviewers that this paper makes substantive contributions to understanding the role of surrogate losses in adversarial learning. To make the paper more accessible, I encourage the authors to make the exposition (at least the first few sections) more friendly to readers who don’t have an extensive background in learning theory.
Decision: Accept (Spotlight)