Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################

Summary: 

In this paper, the authors propose an additional "abstain/detection" loss term into training, so that the classifier can either robustly classify or detect an adversarial attack. They extend the interval bound propagation method for certified robustness under L_infity perturbations (a simple bounding in changes of the weight after each NN layer application, using a box constraint). Hyperparameters in the objective trade-off between clean and adversarial accuracy. 

##########################################################################

Reasons for score: 
 
Overall, I think the paper is borderline. I like the idea of adding an "abstain" error term in the loss during training, and I like that the authors have derived some (simple) bounds on the min-max formulations. They show some benefit of addition of abstain/detection in the training. However, my major concern is that if these results could also be obtained without adding these losses in the objective, but by simply comparing "closeness" or confusion in the class labels from the classifier, and abstaining from classification as a post-processing step instead. What is the benefit of adding this to the training? 
 
##########################################################################

Pros: 

The authors are trying to break the loop of adversarial training and subsequent adaptive attacks, by developing "provably robust" methods.

The idea of incorporating an "abstain" loss term at the training stage, and trading it off with the true error in classification is interesting. They further modify the loss slightly to exclude true and abstain classes (perhaps, driven by experiments). 

They obtain (simple) convex upper bounds on the loss functions and minimize these. 

##########################################################################

Cons: 

1. Choice of the loss functions: why the specific choice? Loss for misusing abstain class or mislabeling the true label could be something more general. 

2. Choice of hyperparameters: How does one select \lamba_1 and \lambda_2 in practice? The authors mention a few practical ways (also used by authors in related works), e.g., ramp down of \kappa etc. Why are these good choices?

3. Clarity in the writing: The paper is unclear at many places- for example, it is nowhere mentioned that the maximum weighted class is finally chosen, and the interval bounds are not propagated at this last layer. Algorithm 1 is explained nowhere in the paper, except in a psuedocode. 

4. Can similar benefits in adversarial robustness be obtained by post-processing an adversarially trained model?
 
##########################################################################

Questions during rebuttal period: 

 
Please address and clarify the cons above 

 
#########################################################################


review_title: Borderline

final_score: rating: 7: Good paper, accept
review_content: Summary: 
This paper deals with the problem of bounding the amount of errors that a model can make when attacked by an adversary limited to small perturbation of an input image. Similarly to previous paper, it proposes to extend the classifier with a detector to identify adversarial examples. As opposed to previous papers, the authors suggest to perform formal verification to prove that the samples are either robustly classified or abstained on (as opposed to testing the classifier + detector adversarially which would have left open the question of whether or not the attack against the pair was done in an adequate way). The method used for this is based on the simple IBP algorithm but the authors propose a proper encoding of the max(abstain_logit, gt_logit). They also follow the IBP strategy of using the bound resulting from verification as part of the training objective in order to encourage the network to behave properly.
Experimental results are reported on MNIST and CIFAR-10, and shows that there are scenarios in which the behaviour caused by this algorithm might be desirable.The experimental protocol for training network with the proposed method is described in significant amount of details and it should be possible to reproduce experimental results based on the description.

The crux of the paper lies in redefining the way accuracy should be computed in the case of an abstain option and adjusting verification and robust training methodologies for it. The accuracy is computed in the following way:
* For natural images, the prediction is considered correct only if the output is the correct class.
* For perturbed image, the prediction can be either the correct class OR the abstain class.
This might be sensible, but unless I'm mistaken, this could lead to degenerate cases where the network could achieve a verified error of 0 while having a standard error of 100% (see below). It's regrettable that we lose the property of the verified error rate being an upper bound on the standard error rate.

If I'm not mistaken, the results in Table 1 are hard to evaluate because the methods proposed by the authors is the only one that considers an abstain class, which gives it leeway to "cheat". A pathological example of this would be a network always outputting "abstain". If I understand correctly, it would be classified as having 0% verified error, while having 100% standard error. A moderate version of this is what can be observed for all the pairs (except CIFAR10-eps=16) : standard error goes up compared to IBP while verified error goes down. 
Figure 1. is however quite helpful in showing that there might be some benefit in the proposed approach if the goal of an application leans more towards "Never making bad predicitions" rather than "Always making good predicitions".

Comments:
- I am not entirely sure of the premise of the papers that "adversarial examples is something that we can defend against". I am not convinced that people are worried about an attacker crafting attacks to fool their classifier. The problem is that we want our classifiers to be robust to small perturbation, because that's a desirable property and adversarial examples is a sign that this property is not met. 

There might be some potential extension to this paper in the direction of OOD detection. Out of Distribution examples tend to make the classifier perform poorly. There is also a glut of methods that claims to be able to detect out of distribution examples without any formal guarantees so I would encourage the authors to look in that direction for extensions to their work.

Opinion: The paper is quite interesting to read, and as far as I can tell is the first one to apply verification methods to the detection of adversarial examples. This is a welcome contribution as opposed to all the methods that claim to detect attacks but can not provide any guarantees.
review_title: Good paper, combining verification methods and adversarial example detection

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a new defense method based on adding a reject class to a classifier trained for robust classification. The paper has merits, it is formally sound and it improves the SOA. However, my rating is not so high for the following reasons:

- Only a short paragraph at the end is devoted to the natural-vs-robust error trade-off and the comparison is done only with IBP (another defense method of 2018). In my opinion this important trade-off is being neglected. What is the point of developing classifiers that are robust to AEs when they are not robust to other normal images (like those found in the test set)?
- Adding a reject class may not seem fair. Particularly, the paper states (p.4) "the classification/detection tasks is considered successful if the input is classified either as the correct class y or as the abstain class a; as both cases prevent misclassification of the adversarially perturbed input as a wrong class". I do not agree with that; it should be considered successful only if the input is classified as the correct class y, period. The "abstain" class is just a reject option, which is not the same as the correct classification. One can always resort to rejection to improve the error rate in the non-rejected part of the dataset. When there is a reject option in the system the figure of merit should be the ratio between error and rejection rate, while in your case you are using only error as the figure of merit. What would be the error-reject trade-off curve of the base classifier in these same datasets? 

Also, I could not understand the relative weights lambda 1 and 2 in Eq. 14. Are they correct? shouldn't there be a weight also for the first term Lrobust? Likewise in Eq. 18 you state that for lambda1=0 the training reduces to that of Gowal but the weight terms are different in Eqs. 18 and 7.

Minor: 
- When referencing an equation you should capitalise the first letter E. 
- "plotted in 2"
- "network can increase robust"
review_title: Provably robust classification of adversarial examples with detection

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper aims to train networks that can map a possibly $\ell_\infty$-perturbed input to its class provably or map this input to the “abstain class” provably. This is achieved by training on the IBP output boxes together with a new loss function. The method diverts from the classical setting in which the classifier needs to be robust, by allowing the classifier to abstain. While this is an interesting idea, the paper seems to be rushed and not carefully written. The notation could be improved and presentation could be simplified. It seems as if the results from related work (Balunovic et. al. [3] and Mirman et. al. [4]) are missing in Table 1 and thus are not compared against. Further, some questions remain open after reading the paper:

Questions:
- Would the idea to have an explicit “abstain” together with the loss function work also for randomized smoothing [1]? How would the results look like?
- Have you tried to use certification methods using tighter relaxations like k-ReLU[2]?
- In Equation 8: Is this here for all $i$?
- How would your method perform when using COLT [3]?

Comments:
- in equation 3, it seems to me as if the second ‘+’ for $\underline{z}_l$ should be a ‘-’, similar for $\overline{z}_l$
- in equation 6: $\ell_{\text{xent}}$ should be defined before used

The comparison in the evaluation is not complete, questions remain open after reading the paper and evaluation is missing, hence this is a reject for me. 


[1] Cohen et. al.: 'Certified Adversarial Robustness via Randomized Smoothing'. http://proceedings.mlr.press/v97/cohen19c/cohen19c.pdf

[2] Singh et. al.: 'Beyond the Single Neuron Convex Barrier for Neural Network Certification'. http://papers.nips.cc/paper/9646-beyond-the-single-neuron-convex-barrier-for-neural-network-certification.pdf

[3] Balunovic et. al.: 'Adversarial Training and Provable Defenses: Bridging the Gap'. https://openreview.net/pdf?id=SJxSDxrKDr

[4] Mirman et. al.: 'A Provable Defense for Deep Residual Networks'. https://arxiv.org/pdf/1903.12519.pdf

######################

After reading the author's response: While i still think that extending the experimental evaluation along the axes described above would improve this work, i decided to raise my score. 
review_title: Missing comparison to related work and experiments. 

Meta-review: The paper studies the problem of certified adversarial robustness when the classifier has a reject option (realized here as an additional class) where the certification is done by adapting IBP-techniques to this particular problem setting.

Pro: As previous approaches to adversarial robustness with reject option have often be shown to be non-robust as one could circumvent both detector and classifier simultaneously with an adaptive attack, the idea to do this instead with a certified approach is interesting and could potentially initiate more research in this direction.

Con: 
- The approach seems to some extent trade-off robust error with normal error which seems in particular true for MNIST where a stronger loss in normal error is less acceptable. 

Comments:
- One reviewer mentioned that such a certified approach could be interesting for OOD detection. This has been done recently in:
Julian Bitterwolf, Alexander Meinke, Matthias Hein
Certifiably Adversarially Robust Detection of Out-of-Distribution Data, NeurIPS 2020
which should be cited in the present paper.
- While the empirical PGD-attacks done in this paper are strong, sometimes PGD fails due to gradient obfuscation, I would thus recommend to use additionally a black box attack or the recent AutoAttack.

Decision: Accept (Poster)