Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper proposes an approach for computing more refined estimates of robustness in comparison w/ existing linear approximation approaches that only give a yes or no answer with regard to robustness guarantees for a given lp-norm ball with radius epsilon. The nice thing is that as the linear-approximations get better, the contributions in this paper would continue to help. 

The paper makes two key algorithmic/theoretical contributions:
1. An approach to obtain a better estimate of the radius of the l-p ball where the NN is provably robust. This result is fairly straightforward, and relies on computing the distance of a point to the boundary of adversarial polytope.

2. An approach to exploit the fact that the pixel values are restricted to specific bounds, which might allow us trim away some regions from the l-p norm balls around a given input image w.r.t which we want to be robust, while computing the robustness. This I think is a more interesting contribution. 


I am leaning towards a reject, however I am open to changing my score. I have several key concerns:

1. Verified Training: Why is there no comparison with IBP and IBP+Crown (Zhang 2019) -- it seems like an appropriate comparison to make. Particularly, when the current paper refers and discusses both of the above works. 

2. I am not sure that comparison with CRO entirely suffices in my opinion. Would it be possible to compare with the tighter SDP based approaches (Raghunathan et al., NeurIPS'19 and Dvijotham et al., UAI'19)? Is there a specific reason to not compare (other than that the SDP based approach is not a linear approximation, and probably is much slower)? 

My main concern here is the utility of pushing boundaries with the linear approximation, while there are potentially tighter relaxations?

3. You claim no overhead compared to CROWN. Don't the greedy-optimization steps add some overhead, or am I missing something? How expensive are they? (It's possible I might have missed some discussion in this regard. If so, please point me in the right direction and that should suffice)

4. Can you plot the distributions of the certified epsilon? Are there a few samples for which you can certify a much larger epsilon (than just saying not robust) or are there a lot of samples where you can only show a tiny bit of robustness (compared to CROWN saying not robust)? 

The gains in the average robustness are somewhat small, and these gains alone are not convincing without being able to see how these gains were obtained. 

Minor Comment:
Missing reference to MixTrain for B' < B helps. 

Update:
Thanks for the detailed response!

1. This makes sense, the first bit seems obvious --> if you don't train with IBP, you won't get much out of IBP and this is reasonably well known. 

Table 5: When trained with IBP and verifying with IBP, it seems to do better or quite comparable to train/verify with PER --- in this sense, the gains seem quite marginal.

2. Since a part of the contribution claimed in this paper is improved robustness guarantees for pre-trained networks, I do feel that comparisons with the UAI'19 paper or the NeurIPS'18 paper would be nice -- however, I do agree that the computational tractability of KW/FastLin/IBP are much more favorable.

3. Thanks -- it is much more clear now.

4. The distributions for MMR/PER seem quite similar and most of the gain seems to come at the lower end (small eps). 
This still remains my biggest concern -- I was hoping that the distributions would diverge a bit more at larger eps, but this is difficult to confirm with the current set of plots.

These plots, as of the current version, are not very useful -- a CDF plot as opposed to a histogram would be much more illustrative in terms of comparing the different approaches. Overlaying them with different opacity might also be useful. 

I am still leaning towards a weak reject. I am not sure how the scoring system works, the scores are distributed unevenly -- I would judge this a 5 on the 1-10 scale. However, going by the wording, I will stay with a 3.
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: This paper proposes a certifiable NN training method, "polyhedral envelope
regularization" (PER) for defending against adversarial examples.  The defense
is based on the same linear relaxation based outer bounds of neural networks
(KW/CROWN) used in many previous works.  The paper makes a few new (but small)
technical contributions:

1. this paper uses a different loss function (7), which is essentially Hinge
loss on the lower bounds of distance to decision boundary. Previous works like
KW used cross-entropy loss on the lower bound of prediction margin instead,
which was based on minimax robust optimization theory. But I am not fully
convinced if the new loss function is better or not.

2. in (5), the authors solve the bounded input case more carefully than
previous works.  (5) is trivial to solve in the L infinity case and has been
used in previous works like (Wong & Kolter 2018, Gowal et al., 2018 and Zhang
et al., 2019); but solving it for other norms requires some efforts, and this
paper proposes a good solution for it (Algorithm 2);

3. In previous works like KW/CROWN, to find the largest certifiable radius, a
binary search is needed. The authors proposes a very small improvement to the
binary search process by setting the lower bound of search to the largest
epsilon that is certifiable using the current linear relaxations obtained from
a larger epsilon.

The authors does not improve any bounds proposed in KW/CROWN, and they reuse
the same bounds. I see the main contribution as the new hinge-like loss
function for training, and a more careful procedure to find the largest
certifiable radius in bounded input case.

Empirically, the improvement of the proposed algorithm is limited - based on
Table 1 it is hard to say if PER is better than KW or not. PER+at outperforms
KW sometimes, however it is not a completely fair comparison, as we can add a
PGD based adversarial training loss to KW as well, as done in DiffAI (Mirman et
al., https://github.com/eth-sri/diffai).

Questions:

1. In my personal experience I usually found Hinge loss not as effective as
cross-entropy loss in deep learning based tasks probably due to its
non-smoothness. The claim that (7) is better than cross-entropy loss is that it
does not overregularize the network. The authors should provide more evidence
to show if this argument holds, e.g., plotting the norm of weight matrices
during the training for the two losses to show that it can reduce
overregularization.

2. I think the metric ACB KW and ACB CRO (average certified radius of KW/CROWN)
in Table 1 and 2 are confusing and not fair. In KW and CROWN's evaluation,
giving an epsilon, if an example cannot be certified due to epsilon to large
(i.e., ||A|| \epsilon + b > 0), certifiable radius will be count as 0 (flat
line in Figure 1(a)). In this paper, the authors instead in this case use -b /
||A|| as the certifiable radius. This is merely a different way of evaluation,
and I don't see this as a contribution, as the "improvement" does not come from
a tighter bound.  In the same sense, I don't think Figure 1(a) and the
discussions on page 3 are appropriate characterization of KW/CROWN. PEC uses
exactly the same linear bounds as in KW/CROWN, and has the same certification
power.

3. For L2 based perturbations, in Table 1, the epsilon used for MNIST is too
small. It is better to use an epsilon that is aligned with previous works. For
example in Wong et al., 2018 (https://arxiv.org/pdf/1805.12514.pdf), page 22,
you will find the epsilon used for MNIST and CIFAR.

4. As discussed above, it is probably not fair to compare PER+at with KW. A new
baseline like KW+at should also be considered.

5. For norms other than L infinity norms, solving (5) for getting $d$ can be
time consuming (Algorithm 2). How much additional time does it comparing
to KW?

Overall, I cannot recommend accepting this paper due to its limited theoretical
contribution as well as unconvincing empirical results comparing to previous
methods. I suggest rephrasing some parts of the paper and providing more
experimental results as discussed above.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: Summary:
There exists several method (KW, Crown, zonotope transformers) which essentially propagate linear lower and upper bound through the network (bounds is a linear function of the input variables). So far, to check for robustness, these methods propagated the bounds until the last layer (+ margin computation) and then concretized them and compared the result to zero to see if the studied radius was safe or not. This paper highlights the fact that in the case where the studied radius is not safe, it is possible to extract a safe radius from the linear bound.

The authors then show that:
-> this can be used to make binary search to find the larger verifiable epsilon faster (by providing a lower bound on epsilon even when failing to verify, rather than simply when succeeding verification)
-> this can be employed during the training process to improve regularization, similarly to another previously proposed method (Croce et al.). While the methods are similar, the bounds are much less conservative than Croce's one and should therefore be more helpful

The presentation of the content is quite clear, and Figure 1.a is extremely useful in conveying the benefits of the method.

Experimental validation is thorough:
-> Comparing the ACB KW and ACB PEC columns in Table 1 and 2, for all type of activation functions, shows that this is as expected a strict improvement in the generated bound.
-> Comparing the various rows in Table 1 shows the improvement with regards to other methods, both in terms of clean accuracy (this produces less over-regularization), while maintaining similar or better robust accuracy.
-> Table 6 shows the benefit in the application to binary search.

Opinion:
This paper is clearly written and I think that it's an interesting insight and that the authors do a good job at conveying its usefulness. I'm happy for this paper to be accepted.


review_title: Official Blind Review #3

Meta-review: The authors develop a new technique for training neural networks to be provably robust to adversarial attacks. The technique relies on constructing a polyhedral envelope on the feasible set of activations and using this to derive a lower bound on the maximum certified radius. By training with this as a regularizer, the authors are able to train neural networks that achieve strong provable robustness to adversarial attacks.

The paper makes a number of interesting contributions that the reviewers appreciated. However, two of the reviewers had some concerns with the significance of the contributions made:
1) The contributions of the paper are not clearly defined relative to prior work on bound propagation (Fast-Lin/KW/CROWN). In particular, the authors simply use the linear approximation derived in these prior works to obtain a bound on the radius to be certified. The authors claim faster convergence based on this, but this does not seem like a very significant contribution.

2) The improvements on the state of the art are marginal.

These were discussed in detail during the rebuttal phase and the two reviewers with concerns about the paper decided to maintain their score after reading the rebuttals, as the fundamental issues above were not 

Given these concerns, I believe this paper is borderline - it has some interesting contributions, but the overall novelty on the technical side and strength of empirical results is not very high.
Decision: Reject