Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Summary:
The aim of the paper is to improve verified training. One of the problem with verified training is the looseness of the bounds employed so the authors suggest incorporating a measure of that looseness into the training loss. It is based on a reformulation of the relaxation of Weng et al.


Comments:
Page 2: "it can certify a broader class of adversaries that IBP cannot certify, like the `2 adversaries.". You can definitely use IBP to very properties against L2-adversaries. It is simply a matter of changing the way the bound is propagated through the first layer.
Page 3: It's a bit pedantic, but the convex relation of Ehlers (middle of figure 1) is not the optimal convex relaxation. It is optimal only if you assume that all ReLU non linearities are relaxed independently. See the work by Anderson et al. for some examples 
Page 5, section 4: "We investigate the gap between the optimal convex relaxationin Eq. O" There is a bit of confusion in this section. Eq O is not the optimal convex relaxation, it's the hard non-convex problem.
Section 4.1 bothers me. Equation C is the relaxed version of equation O, so they are only going to be equal if there is essentially no relaxation going on. Saying that it's possible to check whether the equivalence exists is a bit weird. The only case where this can happen is if all the terms in the sum over I_i are zero, which is essentially going to mean that no ReLU is ambiguous. (or if the c W are all positives, but that would be problematic during the optimization of the intermediate bounds given that c would make them both signs then)
Page 5, section 4.2: The authors suggest minimizing d, the gap between the value of the bound obtained, and the value of forwarding the solution of the relaxation through the actual network. Essentially, this would amount to maximizing the lower bound (which all verified training already does), at the same time as minimizing the value of the margin (p_O) on a point of the neighborhood for which we want robustness (x + delta_0). Minimizing the value of the margin is the opposite of what we would want to do, so I'm not surprised by the observation of the author that this doesn't work well.
The conclusion of the section that d can not be optimized to 0 also seems quite obvious if you think about what the problem is.

Section 4.3:
"the optimal solution of C can only be on the boundary of the feasible set." -> There is a subtlety here that I think the authors don't address. The three points they identify are the only feasible optimal solutions for solving a linear program over the feasible domain given by the relaxation of one ReLU but, when solving over the whole of C, the solution needs to be on the boundary of the feasible domain of C, which is larger than those three points.

The whole section is quite convoluted and makes very strong assumption. For Proposition 1, the condition x \in S(\delta) means that all the intermediate bound in the network must have been tight (so that the actual forwarding of an x can match the upper or lower bound used in the relaxation), and that the optimal solution of the relaxation requires all intermediate points to be at either at their maximum or their minimum. The only case I can visualise for this is essentially once again the case where there are no ambiguous ReLU and the full thing is linear.

Regarding the experiments section, it would be benefical to include in table 1 the results of Gowal et al. (On the Effectiveness of Interval Bound propagation for Training Verifiably Robust Models) for better context. The paper is already cited so it should have been possible to include those numbers, which are often better than the ones reported here.
The comparison is included in table 2, when the baseline is beaten, but this is with using the training method of CROWN-IBP and it seems like most of the improvements is due to CROWN-IBP.

Typos/minor details:
Page 2: " In addition, a bound based on semi-definite programming (SDP) relaxation was developed and minimized as the objective Raghunathan et al. (2018). (Wong & Kolter, 2017) presents an upper bound" -> citation format
Page 8: "CORWN-IBP "

Opinion:
I think that the analysis section is pretty confusing and needs to be re-thought. It provides a lot of complex discussion of when the relaxation will be exact, without really identifying that it will be when you have very few ambiguous ReLU. I think that there might be a few parallels to identify between the regularizer proposed and the ReLU stability one of Xiao et al. (ICLR2019) from that aspect. The experimental results are not entirely convicing due to the lack of certain baselines.
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: Summary:
The paper proposes two new regularizers for adversarial robustness inspired by literature on verification of ReLU neural networks for resilience to epsilon perturbations using convex relaxations. The paper shows empirically that the proposed method leads to better robustness than previous works.

Strengths:
+ The paper seems to have an interesting perspective (with the proposed looser relaxation) of the convex relaxation of an adversary adding noise at every layer in the network

Weaknesses:

*Sec. 4.1: Eqn. (O) does not have a convex relaxation, it is the exact problem which is intractable. Why are we comparing the optimal values of p*(O) and p*(C)? The paper from Salman et.al. already shows that there is a convex relaxation barrier, which essentially corresponds to this difference. In general, in Sec. 4, it is often unclear whether when we talk about p(O) if we are referring to the unrelaxed original problem or the tightest convex relaxation. For example, at the start of Sec. 4.1, it seems like we are talking about the convex relaxation and then in Sec. 4.3 it seems like we are talking about the unrelaxed problem.

*It is not clear how/ why the proposed method of relaxing (which by the way seems identical to Fast-Lin (Weng et.al.) is better than the optimal convex relaxation. Would this not lead to looser bounds? Is that the thing we are looking to investigate? Making that more clear would be useful. Perhaps it would be good to argue the proposed regularizer in this work cannot be constructed with the optimal convex relaxation. Is that true? A discussion on this would be helpful.

* The crux of the contribution seems to rest on the premise that identifying the optimal perturbation in the input space with the relaxed model, and then computing the activations with respect to that and forcing the forward pass to saturate near the margins of the relu polytope (relaxation) is a good idea. In general, it seems very unclear why this should work based on the evidence presented in the paper. Specifically with the relaxation, it might not even be guaranteed (as far as I understand) that the value of \delta_0^* that is found from problem C is even going to lie inside the L\inf norm ball around the point x, for example. Thus it is not clear to me if this is an approach for verification or a regularizer based on verification.

* Ultimately, the value of the approach in this context (as per my understanding) comes from the experiments and the results which show that there is increased robustness. It would be great to clarify a couple of details in the experiments:
1. Is the method of Wong et.al. using the looser convex relaxation (used here) or the tight convex relaxation when reporting the numbers in Table. 1? 
2. If the optimal convex relaxation can be used to construct the same regularizer as the one proposed here, it would be good to evaluate how well that does.

Overall, I am not an expert in the area but a lot of details from the writing (such as point 1 under weakness) and the theoretical justification of the regularizer are unclear to me. Thus given these (perceived) weaknesses I would lean towards weak rejection. Clarifications on these points would help me revise my score.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: Strengths:
This work proposed two regularizers that can be used to train neural networks that yield convex relaxations with tighter bounds.
The experiments display that the proposed regularizations result in tighter certification bounds than non-regularized baselines.
The problem is interesting, and this work seems to be useful for many NLP pair-wise works.
weaknesses:
Some presentation issues.
The dataset, MNIST, is not good enough for a serious research. 
More datasets need to be added to the experiments in this paper.


Comments:
This paper proposes two regularizers to train neural networks that yield convex relaxations with tighter bounds. 

Overall, the paper solves an interesting problem. Though I did not check complete technical details, the extensive evaluation results seem promising. 

1. There are some presentation issues that can be addressed. For example, on page 8, the sentence of “the family of 10small” misses a blank space.

2. In the experiments, the dataset is not a good one for evaluating the performance of the proposed idea.

In conclusion,  at this stage, my opinion on this paper is Weak Accept. 
review_title: Official Blind Review #2

Meta-review: The authors develop regularization schemes that aim to promote tightness of convex relaxations used to provides certificates of robustness to adversarial examples in neural networks.

While the paper make some interesting contributions, the reviewers had several concerns on the paper:
1) The aim of the authors' work and the distinction with closely related prior work is not clear from the presentation. In particular, the relationship to the ReLU stability regularizer (Xiao et al ICLR 2019) and the FastLin/CROWN-IBP work (https://arxiv.org/abs/1906.06316) is not very well presented in the theoretical sections or the experiments.

2) The theoretical results (proposition 1) requires very strong conditions to apply, which are unlikely to be satisfied for real networks. This calls into question the effectiveness of the framework developed by the authors.

While the paper has some interesting ideas, it seems unfit for publication in its present form. 
Decision: Reject