Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: In this paper, the authors studied the role of loss landscape in training certifiable robust models. The authors reviewed linear relaxation based methods, and showed that Interval Bound Propagation (IBP) is a special case of linear relaxation based methods. Although linear relaxation based methods have a tighter bound on worst case loss with adversarial perturbations than IBP based method, the authors found in numerical studies that towards the end of training, IBP outperforms linear relaxation based methods. The authors hypothesized that this was because IBP loss landscape was more smooth, which helped optimization. The authors demonstrated in a theorem that IBP loss was indeed more smooth under certain assumptions. Based on this insight, the authors proposed a favorable landscape method. The authors showed in numerical studies that the sum over the worst-case margin for each class is lowest for their method. The loss of their method is also the most smooth among competing methods. Their method achieved a consistent performance in a range of perturbations, which is not achieved in competing methods.

The paper is clearly written. The insight is interesting, and could help future researchers.

On page 4, in Figure 1, what is the mathematical definition of "variation"? Why does the variation of CROWN-IBP first increase, and then decrease? A related question is why does the proportion of unstable ReLu first increase and then decrease in CROWN-IBP? Does it have something to do with the curvature shown in Figure 1 (right)?

One page 7, it would be great to also show the comparison of training time between these methods.

review_title: Good paper with interesting findings

final_score: rating: 3: Clear rejection
review_content: This paper claims to make three contributions:  (i) a theoretical and experimental demonstration that the driving force behind performance in certifiable training methods is loss landscape smoothness (ii) a new training method and domain designed to have a smooth loss landscape (iii) an evaluation showing their new training method performs comparably to the state of the art.


Pros:
* The paper provides some experimental analysis support a hypothesis that has been conjectured since Mirman et al. (2018), that smooth loss landscapes produced by smoother transformers (zSmooth/hSmooth) would improve training.  
* The paper does show experimentally that certain methods tend to have less smooth loss landscapes.  
* The theoretical result connects the smoothness of the relaxed gradient approximations to the smoothness of the loss landscape, which may be useful for designing future certifiable training methods.

Cons:
* In terms of accuracy and verified error, the proposed system performs comparably to some pre-existing systems.  The main claim that the authors have identified an important factor for improving certified training remains unsupported by the inability to improve noticeably upon results from prior work.
* The authors do not compare it to the state of the art, COLT [1], which achieves for example 21.6/39.5 (standard, verified error) compared to this paper’s 31.49/49.42 results on CIFAR10 2/255.  This is a much more significant difference than for any of the comparisons made to other work in this paper.
* It is unclear how fast the proposed method is.  No comparison appears to be made on training speed or memory usage compared with other systems.  Given comparable accuracy and verified error results, I would not see a reason to use this system if this one is slower.
* I am not sure about the utility of the experiment on tightness and Figure 3.  Different methods could have different scales of loss while producing similarly verifiable networks (as this paper in fact demonstrates).  Further, even the worst case margin for a class could be fooled by a network with entirely  zero weights.  
* Loss value is also compared between methods in Figure 1.
* The paper claims that state of the art methods such as CROWN-IBP and CAP are held back by their non-smooth loss landscapes while failing to meaningfully outperform them.  5 out of 10 of the standard accuracies are worse than CROWN-IBP’s for example.
* Section 4.1 claims that the experiments show that “the non-smoothness of the relaxed gradient approximation of linear relaxations negatively affects their performance” yet the evidence presented is circumstantial, and not capable of indicating causality.
* Section 4.2 claims that the theoretical analysis states that some landscapes are more favourable  than others, whereas in fact it only demonstrates the smoothness of some landscapes not their “favourability.” 
* The paper leaves out additional related work.  In particular, I would like to see a discussion of the difference between the analysis used by Fastened Crown [2].

While this paper does provide a new technique with some theoretical justification, unfortunately neither the theoretical justification or experimental results are significant enough to recommend acceptance.  Furthermore, because the paper’s central assumption, that a smooth loss landscape leads to better results, is unsupported by their own experimental results, I must rate the paper a rejection.

[1] Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2020.
[2] Lyu, Z., Ko, C.-Y., Kong, Z., Wong, N., Lin, D., and Daniel, L. Fastened crown: Tightened neural network robustness certificates.  In AAAI, 2020.

=========================================================================================
Update:

While some of my points have been addressed and the quality of the paper has been improved, my main concern, that the experiments do not support the central claim.  

The authors argue that because their method has a smoother loss landscape then similar methods, it performs better.  In the updated paper, the evidence that the method performs better than similar methods has been made clearer, but the improvement is is still marginal.  The more pressing matter however is that the conclusion that the cause of the improvement is from a change in the loss landscape smoothness is based only on a qualitative comparison of only five methods (as the benefit is not consistent between methods in any category).  This is enough to at best demonstrate a weak correlation, but not enough to demonstrate causation. 


review_title: Central claims unsupported by evaluation

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper studies why training with looser bounds (IBP) can outperform tighter linear relaxation based methods in certified defense. The authors argue that this is because IBP has a smoother loss landscape compared to linear relaxation based methods. Then the paper proposes to optimize the lower bound in the CROWN relaxation for unstable ReLU neurons during training, for tighter bounds and a smoother loss landscape.

Pros:
* This paper studies an important problem in certified defense and tries to improve linear relaxation based certified defense methods, especially CROWN. 
* This paper novelly proposes to optimize the lower bound in the relaxation for unstable ReLU neurons to train tighter bounds in certified defense. 
* The paper showed some improvement on test verifier error, compared to CROWN-IBP(1->1), and it also showed improvement on tightness and loss smoothness.

Cons:
* The link between the motivation and the proposed method is not well justified. Paragraph “Favorable Landscape” somewhat explains the connection between optimizing the lower bound in relaxation and improving loss landscape. But it states that the benefit comes from preferring dead ReLU neurons to unstable ones. If the proposed method is actually trying to make more unstable neurons dead, the paper does not discuss or compare with paper Xiao et al., 2018 (https://arxiv.org/pdf/1809.03008.pdf) which directly adds a regularization to induce ReLU stability. 
* It does not seem to make sense that the proposed method can prefer to have dead neurons via optimizing the relaxation for unstable neurons. With such an optimization, bounds of unstable neurons become tighter, so how can such tighter bounds make the model favor unstable neurons less than CROWN-IBP with relatively looser bounds?
* As the paper mentions that CROWN-IBP does not penalize unstable ReLU neurons with (|u|<=|l|), but how about just make the lower bound equal to the upper bound as Fast-lin (Weng et al., 2018, https://arxiv.org/abs/1804.09699) does, so the lower bound is non-zero for unstable neurons? 
* An improvement over CROWN-IBP(1->1) is shown in the paper. However, the proposed method does not make enough improvement over CROWN-IBP(1->0). The improvement on CIFAR10 with eps=8/255 or 16/255 is very small (error 69.70 v.s. 69.97, 77.87 v.s. 77.88), while there is a large performance drop on MNIST with eps=0.3/0.4 (increased error 7.07->9.79 and 12.35->15.42). What will the performance of the proposed method look like if a changing $\beta$ is used in training?
* This paper missed some previous works, e.g., Xiao et al., 2018 and Weng et al., 2018 as mentioned above. More discussions or comparisons with them may be needed.

==========================================================================================

Update after rebuttal:

Thanks for the detailed author response. I think the paper is interesting in providing an analysis on how optimizing the linear relaxation in CROWN (although the verification method itself seems to be similar as the one in Fastened CROWN in AAAI 2020) can lead to better loss smoothness and tightness, which seems to improve the performance of certified training. The author replies have addressed some of my concerns in my initial review. However, there are still some outstanding concerns:

1. After more consideration, I think the “More favorable landscape” paragraph is still insufficient to address the second point in my above cons. The author response argues that some “$(p/q)$” have looser or tighter bounds, but these are considered for relaxation *locally*, not the tightness on the final output, while the relaxation optimized in the paper is to tighten the final output. Thus it remains unclear why tighter final bounds with improvement from the unstable ReLU neurons makes the model favor unstable neurons less.

2. AnonReviewer2 has reminded me that the “Fastened CROWN” work had a similar method about optimizing the lower bound of the linear relaxation in verification, which seems to be very similar to the method proposed in this paper, in terms of the verification part in certified training. Although this paper focuses on certified training and has some different analysis, the major modification on the method is still on the verification part, and thus I agree that a discussion on the comparison with Fastened CROWN should not be missed. The authors did not add it in the discussion period.

3. It is promising that the proposed method outperformed the modified CROWN-IBP ($\beta=1$) and IBP, and there seems to be a significant margin. But the proposed method fails to make a significant improvement compared to the original CROWN-IBP (the 1->0 one), e.g., the improvement on CIFAR-10 eps=8/255 or 16/255 is negligible. 

Overall, I am keeping my recommendation as rejection for the current version of the manuscript. 


review_title: Important problem and interesting method; but discussions and experiments are limited

Meta-review: The authors argue that tighter relaxations for certified robustness suffer from a worse loss landscape and thus are outperformed by the much simpler and less tight IBP relaxation and come up with a new relaxation to overcome this problem. 

After the rebuttal there still remain doubts about the reasoning regarding the loss landscape (even though I acknowledge that the authors have invested significant amount of work to support their hypothesis). Moreover, the differences to existing certified training methods is small or the proposed method performs worse while being significantly more expensive (in particular if one takes into account the results which are reported on the IBP-Crown github page where the reported numbers are significantly lower than reported in the present paper) so that the benefit is unclear.

Thus the majority of the reviewers still suggests rejection and I agree with that even though I think that the paper has its merits and I encourage the authors to continue this line of work. For a next version, the authors should evaluate all the methods ideally with an exact verification method resp. use the best relaxation for all methods. Otherwise the differences can come just from the weaker relaxation but not from a difference in real robustness.


Decision: Reject