Training Deep Neural Networks (DNNs) that are robust to norm bounded adversarial attacks remains an elusive problem. While verification based methods are generally too expensive to robustly train large networks, it was demonstrated by Gowal et al. (2019)  that bounded input intervals can be inexpensively propagated from layer to layer through deep networks. This interval bound propagation (IBP) approach led to high robustness and was the first to be employed on large networks. However, due to the very loose nature of the IBP bounds, particularly for large/deep networks, the required training procedure is complex and involved. In this paper, we closely examine the bounds of a block of layers composed of an affine layer, followed by a ReLU, followed by another affine layer. To this end, we propose expected bounds (true bounds in expectation), which are provably tighter than IBP bounds in expectation. We then extend this result to deeper networks through blockwise propagation and show that we can achieve orders of magnitudes tighter bounds compared to IBP. Using these tight bounds, we demonstrate that a simple standard training procedure can achieve impressive robustness-accuracy trade-off across several architectures on both MNIST and CIFAR10.
Disclaimer: I have already reviewed this paper for another conference. I re-read it to assess the modifications made by the authors but I am aware of the comments that they received in the previous round of reviews. I'm also re-raising some concerns that I made in a previous review that the authors didn't address.
Summary
Interval Bound Propagation (IBP) is a fast method to propagate bounds through the activation of a Neural Network. It is however quite loose. The authors of this paper propose a different way of propagating the bounds, which is not a rigorous bound computation method, but for which they show that, with some strong assumptions on the distribution of the weights, the expectation of the generated results are valid bounds that are tighter than the ones generated by IBP.
The paper explains clearly the "how" of how these bounds are achieved. Equation 3 and the paragraph before it are good. (Essentially, as long as a ReLU is not in a "blocking" state where all its input are negative, treat it as an identity, and do a forward pass of the center of the input region). 
The logical argument explaining the "why" these are valid is harder to understand and could be clarified. My understanding so far is:
- All the analysis is dependent on all weights being drawn from iid gaussian of zero mean.
- In addition to that, there is an assumption (Assumption 1) between the relation of bounds of network with random weight and some quantity (L_approx, U_approx) with random uniform inputs x. 
The proof is done that the expectation of the bound proposed is "correct" with regards to (L_approx, U_approx) but then, the relation to the true bounds is given by the Assumption?
So the relation to the true bounds is only given by the Assumption?
Regarding the experiments:
* The caption of Figure 1 is misleading. It says that it shows that the proposed bounds are a super set of the interval bounds, while they are actually not (ratio is strictly smaller than 1). You can argue that they are close, but now that they are a superset when they aren't!
* The reporting of Figure 5 and 6 is weird because according to the text, each datapoint seems to be the average robustness of networks trained with different hyperparameters, so it's hard to interpret.
* I appreciate the effort of the author to include experiments involving a MIP solver returning the true bounds. This is very helpful in building confidence that the bounds generated are correct. How is the real network trained? Is this based on a robustly trained network or is it just standard training? Is 99% the nominal accuracy?
In general, I think that the paper would be better if there was more discussion of the failure modes of the method. There are easy to identify failure cases where the proposed bound is incorrect or loose. My opinion is that the paper would be stronger if it acknowledged them but then made the points that the bounds proposed are still good most of the time (which their experiment show) and useful (for example for training where the exact correctness of the bounds may not be the most important), rather than ignoring them and pretending that the bounds are perfect.
[From previous review]
Simple example of a network where the results would be quite loose, while IBP is tight:
Two layer NN, x = 0 \in R^n, eps = 1, W1 = 1000 * Identity, b1 = -999 * 1_n, a2 = -10 1_{1,n} , b2 = 0
u1 would be all positive, so the matrix M would simply be the identity.
L_M = a2^T M b1 - eps | a2^T M A1| vec(1) = (-10)*(-999)*n - 10 * (1000) * n = -19990 * n
U_M = a2^T M b1 + eps | a2^T M A1| vec(1) = (-10)*(-999)*n + 10 * (1000) * n = n
The actual bound (which also correspond in that case to what would be computed by IBP) is
L_gt = -10*n
u_gt = 0
Comments:
* "We prove to be true bounds in expectation" -> This is a bad formulation that should be rephrased. The expectation of the proposed bound is correct with regards to the expectation of the true bounds, but "True in expectation" is a bad formulation that doesn't reflect what is happening. Maybe True in expectation would mean that E_{A_1, a_2}(indicator(L_true > L_M)) -> 1 as n grows
* The assumption about gaussian weights in A1 and a2 seems strong but is at least partially motivated at the end of 3.2 (although not all networks are trained with l2 regularizer) What about the iid assumption? In case of a CNN for example, the weights are shared, so definetely won't fit this framework?
* I think that the paper would benefit from having some discussion of other methods that can derive "bounds" which may not actually be bounds. The works by Stefan Webb (A Statistical Approach to Assessing Neural Network Robustness, ICLR 2019) or Tsui Wei Weng (Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach, ICLR 2018) being others of the top of my head . While this paper clearly propose to do things very differently, I think the discussion would have been very valuable.
* While reviewing the paper, I also spotted some strong similarities between the methods proposed (particularly subsection 3.3) and the Fastlin method. The computation mechanism of Fastlin (propagate recursively  from the end through the linear layers and through diagonal matrices that replace the ReLU activation function) is exactly the same as the proposed one (Fastlin goes through the notational burden of handling the bias). The only difference is in the way the coefficients of the diagonal matrix are computed. (here, it's 0 if the Relu is blocking, and 1 otherwise. Fastlin has 0 if blocking, 1 if passing but a coefficient in between (u/u-l) if the reLU is ambiguous).
If that connection is correct, then the benefits of the proposed methods are limited: neither Fastlin nor IBP dominate each other, and the computational costs for Fastlin is higher, due to having to propagate the full linear maps here noted G from the end to the input to obtain the bounds, as the authors seem to have also realised ("it is expensive to compute our bounds using the procedure in Section 3.3, so instead, we obtain matrices Mi using the easy-to-compute IBP upper bounds.")
Opinion:
I am bothered by the framing of the results that the authors employ, as their theoretical results are, to the best of my understanding, dependent on strong assumptions. Some of the experimental results are also over-exaggerated (caption saying that things are superset while the experimental results show something different), and the relation and contextualization with regards to existing literature is lacking ( both against other works with similar aims but different methods, and with works with similar method but a slightly different aim)
Typos:
Page 7, "are are much"
Page 8,"When kappa=0", no need for uppercase
The references should ideally be cleaned and put in a consistent format. In the text of the paper, Some citation have first name + last name of one author, some have two out of all the authors, some have the et al. format.... It's all over the place. 
In the References section, some authors list are shuffled (at least the "Scaling provable adversarial" paper), some are missing the conference where paper where cited and just cite the arxiv version