Convex relaxations are effective for training and certifying neural networks against norm-bounded adversarial attacks, but they leave a large gap between certifiable and empirical robustness. In principle, convex relaxation can provide tight bounds if the solution to the relaxed problem is feasible for the original non-convex problem. Therefore, we propose two regularizers that can be used to train neural networks that yield tighter convex relaxation bounds for robustness. In all of our experiments, the proposed regularizers result in higher certified accuracy than non-regularized baselines.
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.