Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies why tighter convex relaxations for certifiably robust training do not always lead to better robustness guarantees. They hypothesize that this is due to optimization issues in the loss landscape, and back this up with empirical experiments and some theory. They use this knowledge to propose a modification to the certified training procedure to improve the training procedure and get improved robustness guarantees. 
main_review: Overall I enjoyed reading this paper. It studies an open question which to my knowledge hasn't been resolved yet: why tighter relaxations don't lead to better robustness guarantees. Although this may not be the complete story (i.e. there may be other factors at play here), the authors provided what seemed to me to be a compelling argument as for how the optimization procedure can have a role in this behavior (backed up both theoretically and empirically). These findings seem to have real impact, with the improvements in robustness certification in their proposed variation of CROWN-IBP. I have two main critiques: 

First, I found that trying to decipher and parse the findings of this paper was perhaps unnecessarily difficult. Much of the work is muddled in dense, complex notation, and there are numerous long equations scattered in-line in the text. Consequent it took me quite a bit of effort to really figure out what was going on here, and this may deter other readers from picking up on this work. 

Second, from the certification experiments, it would seem that although there are improvements across a range of epsilon, the proposed method seems to hurt for the smallest epsilon. Is there any intuition or explanation for why this is the case? It would be nice to include some discussion of this, i.e. as a potential limitation. 
limitations_and_societal_impact: I would have liked a discussion on why the analysis does not seem to help in the case of smaller epsilon, as mentioned in the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper investigate the reason for why IBP training have better performance than the methods with tighter bounds. And it propose that the main reason for this difference is the loss landscape. The paper also designs a new certifiable training method based on their explanation.
main_review: The topic of this paper is important in certified training and their conclusion is interesting, but I have some concerns about the theoretical and experimental results in this paper.

1. In theorem 2, the paper proposed to bound the loss landscape by an upper bound and use this result to conclude that $g^{(m)}$ is major in shaping the loss landscape. However,  the influence of $g^{(m)}$ on the upper bound can not be extend to the difference off loss landscape without a discussion on the tightness of the inequality.
2. The proposed method can bring about two influence. First, it may smooth $g$. Second it can tighter the bound. Both of these two difference can benefit the training, and is there any discussions available?
3. For the experiment part, it seems that the result for IBP training is not satisfying compared to some new results from IBP[1], and this requires more comparison and discussions.
[1] Fast Certified Robust Training with Short Warmup
limitations_and_societal_impact: Yes, the author has included the limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper observes that the smoothness of the loss landscape correlates with the certified performance for training certifiably robust models. The authors then design a trick to encourage the smoothness by finding sparser lower bounds parameter $\underline{\boldsymbol{a}}$.
main_review: The perspective of exploring the smoothness of the loss landscape for training certifiably robust models is interesting. Experimental results support the claim that SOTA methods have favorable optimization properties. Theoretical analyses also reveal to some extent the connection between the loss gradient difference and the relaxed gradient approximations. However, I would like to give the following comments:

1. The connection between the relaxed gradient approximation and the sparse $\underline{\boldsymbol{a}}$ is only established in a simple and small example. This hinders the utility of the connection for deeper networks, such as the models used in experiments.
2. I can understand why the optimization trick in Eq. 7 may be helpful. However, the justification (line 263~271) for its implicit sparsity is not easy to follow. Could you explain this point more intuitively?
3. Could one directly minimize $\|\nabla_{\boldsymbol{w}} \boldsymbol{g}^{(m)}\|$ or $\|\boldsymbol{W}^{T}\|$ in line 236 to encourage the smoothness?
4. In the case of $\epsilon=8/255$, the resulting performance is inferior to CROWN-IBP(1->0). This means that either smoothness itself is not the key factor, or the proposed sparsity trick is suboptimal for large $\epsilon$. Either way, it undesirably affects the impact of the paper.
5. In Figure 3, are the loss and tightness evaluated on the training set (as in Appendix B of [1]) or the test set? Could you provide more details?

At the moment, I’m on the border for this paper and would be happy to adjust my rating based on the discussion and revision.

[1] Zhang et al. Towards Stable and Efficient Training of Verifiably Robust Neural Networks
limitations_and_societal_impact: The limitations of the work are well discussed. Discussion about the potential negative societal impact is lacking.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper compare the two main stream methods of certifiable robust training: linear relaxation methods and bound propagation methods. By theoretical and empirical analysis, the author claim that, despite tight bounds of the output, linear relaxation methods suffer from worse loss landscape and thus obtain poorer performance. In the end, the authors propose a new methods with both tight bounds and benign loss landscape.
main_review: Strength:

As far as what I know, this paper is the first compare linear relaxation methods with bound propagation method in the view of loss landscape. This is a very interesting aspect and extensive empirical findings support the authors' claim. The paper points out the pros and cons of both types of method, which is intrinsic and useful for researchers to design more powerful algorithms. The new method proposed by the authors achieve good performance as well. 

Concerns and Questions:

1. [Line 84-85] There are indeed some methods training provably robust networks by randomized smoothing, such as https://arxiv.org/abs/1906.04584. So it is inappropriate to say "They focus solely on the tightness of the certified bounds". However, I would agree that the training methods based on randomized smoothing is not suitable to compare with the baselines here, because their guarentees are probabilistic. 

2. [Proof of Theorem 1] I think the author should assume the Hessian matrix is positive definite here, and by the context there is no implication about this ($\theta_{t}$ is an arbitrary parameter instead of local minima). This assumption is necessary, because the first inequality in the formula between line 640 and 641 assumes $\triangledown_{\theta} \mathcal{L}^{\epsilon_t}(\theta_t)^T H_t^{\epsilon}\triangledown_{\theta} \mathcal{L}^{\epsilon_t}(\theta_t)$ is a positive number.

3. [Proof of Theorem 1] I don't understand why the authors assume $\alpha = 2$ in line 643, it looks like $\alpha = 1$ leads to a tight bound.

4. [Equation (5)] I would not agree with the approximation here. $\Delta_t$ is based on the gradient of $\mathcal{L}^{\epsilon_t}$, while $H^{\epsilon}_t$ is the Hessian matrix of a point for $\mathcal{L}^{\epsilon}$, the adversarial budgets are different.

5. [Theorem 2] There is not enough discussion about the third term of the inequality (6). It seems that the author assume that the constant $L^{(m)}$ does not depend on the linear approximation, however, this is not true. The authors should justify this to make the theoretical claim more rigorous.

Summary:

Despite the concerns above, I still believe this is a good paper, well written and easy to follow, with interesting obvervation and convincing claims. I think it will be useful for the whole community. My main complain is that the theoretical part needs improving to make it more rigorous. I strongly encourage the authors to address the concerns pointed above during the rebuttal period, after which I will do a re-evaluation.
limitations_and_societal_impact: The authors briefly discuss this in the Section 7. I would encourage the authors to highlight this more.
review_title: null

Meta-review: I think this paper should be accepted. The paper looks at the area of certifiably robust training which is an important area. The paper poses a novel interesting question (why methods with a loose bound can perform better) and explains it using a new pespective (smoothness of the optimisation landscape). The explanation boilds down to a trade-off between smoothness and tightness. Furthermore, the authors propose a new certifiable training method that combines the smoothness and tightness and shows that it performs favorably in a wide range of perturbations. There is a concern related to the rigorousness of the proof but reading the discussion I believe the authors can address them in the final version.
Decision: Accept (Poster)