Recent works have developed several methods of defending neural networks against adversarial attacks with certified guarantees. We propose that many common certified defenses can be viewed under a unified framework of regularization. This unified framework provides a technique for comparing different certified defenses with respect to robust generalization. In addition, we develop a new regularizer that is both more efficient than existing certified defenses and can be used to train networks with higher certified accuracy. Our regularizer also extends to an 0 threat model and ensemble models. Through experiments on MNIST, CIFAR-10 and GTSRB, we demonstrate improvements in training speed and certified accuracy compared to state-of-the-art certified defenses.
At a first glance, this paper proposed an interesting refinement of interval bound propagation (IBP). However, it has a major flaw in empirical evaluation, and the proposed "theory" and "bounds" are also questionable and have many issues.
In short, the main results of the paper in Figure 1 and Table 2 are problematic and not the right comparison, so they cannot justify the claim that the proposed method outperforms other state-of-the-art baselines like IBP.  Specifically, when comparing to IBP, the certified error should be computed by IBP; however the verification algorithm used in this paper performs extremely poor on IBP based models (giving vacuous bounds like 0%, and the authors are able to outperform this 0%).  Under fair comparison metrics (Table 12), the proposed method is worse than the IBP baseline in almost all settings. I will explain the reason the proposed method does not work in detail below.
Besides the empirical results, the "theory" developed in this paper also has several fundamental weakness (will discuss in detail below) and are lack of solid connections to robustness and the proposed "bounds"; the proposed "bounds" are questionable and are not sound bounds, and they can hardly be justified theoretically; so it is not surprising that they cannot outperform IBP, which is based on rigorous minimax robust optimization and sound over-approximations of neural networks.
On the positive side, the authors considered the ensemble of multiple IBP trained models, as well as extending IBP to L0 norm setting. Both of them are valid (but small) contributions, but they are not sufficient. Also, overall the writing of the paper is great and easy to follow and understand.
I really do not want to make the authors of this paper upset, especially, the main author might be the first time submitting a paper to ICLR or a undergraduate student new to this field. However I have to say this paper has significant flaws and should not be published. Especially, the wrong evaluation methodology used in this paper can be very misleading for new comers to this field, and misguide future research.
I encourage the authors to read my detailed comments below and learn from the failure of the proposed method. If the authors can rephrase this paper significantly (especially, removing the entire section 3), and emphasize on the contributions of ensemble or L0 perturbation, it might become a good paper for a next venue. My suggestions for improvements are below:
1. Be honest with your findings and do not try to hide the weakness of your method, and do not overclaim. Especially, the authors are aware of the problem that IBP based models are better if evaluated under IBP bounds (in Table 12), but still make strong and wrong claims that the proposed method outperforms other state-of-the-art methods in certified accuracy in Introduction.
2. For the ensemble part, consider more "smart" ensembles rather than directly adding them together. For example, we can consider balancing the accuracy and certified error of each model and choose a blend of them. IBP is a strong method, and an ensemble of IBP can yield the best defense.
3. For the L0 robustness with IBP, it is not a significant contribution alone since it only converts the L0 norm to interval bounds at the very first layer.  However the authors can consider more interesting settings, like adversarial patches or masks (https://arxiv.org/pdf/1712.09665.pdf), which can be dealt with similar techniques.
4. When evaluating a certified defense method, it is also good to conduct PGD attacks to the networks, to see how tight the certified bounds are.  If the authors attack the models in Table 1, we can actually see that IBP based models can perform much better than the proposed method. From this, the authors should have realized that the verification method they used is not appropriate to evaluating IBP.
5. Evaluation on only 200 test data points is not sufficient. Certified accuracy is computed on the entire test set (10,000 examples) in almost all previous certified defense papers (Wong et al., 2018; Mirman et al., 2018; Gowal et al., 2018; Wang et al., 2018). The authors should use a proper implementation of verification algorithm, like DiffAI (https://github.com/eth-sri/diffai), convex adversarial polytope (https://github.com/locuslab/convex_adversarial) or symbolic interval (https://github.com/tcwangshiqi-columbia/symbolic_interval). In my experience, on a single GPU they can verify small models over entire dataset (10,000 examples) within a few minutes; large models may take a few hours, but still quite reasonable. The verification method used in this paper is lesser-known and was probably implemented poorly and inefficiently. It is better to use a mature and well accepted library.
6. A Minor issue: the first paper that proposed IBP training is Mirman et al., ICML 2018 (where the "box" domain was used for training), not Gowal et al. 2018. So some sentences in Introduction and Related works are not accurate.
Now let's discuss the issues in this paper in detail, and let's focus on the empirical comparisons to IBP first.
The authors made the main claim based on Table 2 and Figure 1, where the "certified accuracy" (or most commonly referred to as "verified accuracy") for models trained using the proposed method seems to be higher than other methods, especially IBP. "Certified accuracy" is a lower bound of accuracy under any norm bounded perturbations (given a certain epsilon). Conversely, attack based methods like PGD give an upper bound, as there can be stronger attacks that further decrease accuracy.
There are many neural network verification methods to obtain certified accuracy; some of them can be particularly weak on certain models (giving vacuous lower bounds like 0%).  Generally, you choose the best possible (and computationally feasible) verification method to verify the robustness of a model. For example, if verification algorithm A gives a certified accuracy of 10%, but algorithm B gives 90% for the same model, we should use 90%. As an analogy in the adversarial attack setting, you pick the strongest possible attack to evaluate robustness: a model has high accuracy under weak FGSM attacks is not necessarily robust; conversely, a model has low certified accuracy (even 0%) does not necessarily mean it is vulnerable, as the verification method can be particularly weak on this model.
In the original IBP training paper (Gowal et al., 2018), the certified error is computed efficiently using IBP, and the error is about 8% for MNIST (epsilon=0.3), and 68% for CIFAR (epsilon=8/255).  My first hand experience on IBP can confirm that it is very easy (without too much tuning effort) to get 10% certified error for MNIST and 73-75% for CIFAR, even using small models.  These numbers translate to 90% certified accuracy on MNIST (eps=0.3) and 25-27% certified accuracy on CIFAR (eps=8/255). However, in Table 2 and Figure 1 of the paper the authors show 0% (!) certified accuracy for IBP trained models for both MNIST eps=0.3 and CIFAR eps=8/255, and their method outperforms this 0%.
Unfortunately, the verification method ("cnncert") used in this paper performs extremely poor on IBP trained models (giving vacuous bounds like 0%); IBP trained models should be certified using IBP bounds to give non-vacuous results.  What Table 2 and Figure 1 really show is the weakness of their verification method used, rather than the true robustness of the model. What we really want to show here is how robust the models are, not how good a verification method is, so we need to use the best possible verification method; for IBP trained models, using IBP for verification is almost mandatory since it not only gives tight bounds but is also much more efficient.
The authors are aware of this problem - in appendix, Table 12 (a table never discussed anywhere), they listed IBP certified error for IBP trained models.  The MNIST numbers for IBP trained models are close to those on IBP paper (90% at eps=0.3), significantly better than their method in Table 2 (68%) or Table 12 (79%). The CIFAR numbers for IBP (22.5% certified accuracy at 8/255 in Table 12) are apparently de-tuned (in my experience IBP can easily do at least 25%, and Gowal et al. reported 32%), yet it is still better than the proposed method (less than 20% in Table 2 and 12).  So under the right metrics (IBP trained models certified using IBP), even if the IBP models are detuned, they can outperform the proposed method by a large margin. The proposed method only makes IBP worse under the right metrics.
Now let's understand why the proposed method cannot improve IBP. The bounds themselves have a few issues:
1. The "s" bound is not a sound bound for interval analysis anymore, because it uses the wrong center z_nom (the correct center is (l+u)/2 if you propagate the "center" and "difference" along the network, as an alternative implementation of IBP). The author claims that it is fine since we don't need sound bounds thanks to their "theory", however the "theory" itself is implausible, as will explained below. Although this tampered "s" bounds may empirically help to improve robustness, it is not theoretically sound; training a sound bound helps to obtain better certified accuracy.
2. The "v" bound is claimed to capture second derivative of activation function. However, first of all, for ReLU the second order derivative does not exist at all. The author also argue that "v" is a finite difference based bound, however it is also not accurate since when the bounds propagate to later layers both "s" and "v" can become large, and this can be a very bad "finite difference".
3. I do agree "v" somewhat regularizes linearity (assuming the "finite difference" is partially working). However, linearity does not guaranteed to produces good robustness, nor it is necessary. In fact, we should not impose unnecessary regularization to neural networks, since any regularization restricts its learning power. In some papers on empirical defense, linearity sometimes can help to reduce PGD error; however in the certified setting, a direct surrogate to certifiable robustness like IBP usually produces the best results. The addition of unnecessary regularizations mostly makes results worse, unless you have a very good reason and demonstrate strong empirical evidence that it can significantly outperform the baseline. See https://arxiv.org/pdf/1807.09705.pdf for a case study on the failure of over-regularization.
I think the reason the authors still get a somewhat verifiable model is that the "s" bound sort of propagates a bound that is not sound but carries some similarity to IBP. IBP is a strong method so even tampering it a little bit, you can still get something.  The "v" bound implicitly regularizes the norm of weight matrices, which helps to gain better certified accuracy only under convex relaxation based verification methods.  I believe simply IBP+L1 regularization can achieve similar results as the proposed method, under the *wrong* evaluation metric in Table 2 and Figure 1. Under the correct evaluation metric, we shouldn't add this regularization term at all as it harms performance.
The "theory" developed in section 3 is unconvincing and cannot support the "bounds". There a few problems:
1. The "theory" does not help us to find a good regularizer. When the authors argue that the gradient needs to be close to an "optimal" regularizer, we don't have the optimal regularizer at hand and have no idea how to approach it. Also the inverse Hessian used for distance metric in (6) is never known, so it is impossible to say which gradient is good and which is bad.
2. The assumption that lambda is close to zero is almost never true, yet Proposition 1 and 2 strongly depends on it. In the paper the authors use lambda=0.5 (and other similar numbers) and never decay it to zero. So the proposed training method cannot be supported by the "theory".
3. The "theory" makes weak or no connection to robustness guarantees; (4) is a classical results for the connection between test error and global Lipschitz constant, and the connection between this bound and our goal (robust classifier under adversaries) is too general and too weak. A more direct formulation, like minimax robust optimization will be a much better surrogate.
4. The connection between the theory and the proposed bounds is vague; the authors claim "the gradient of a regularizer rather than its bound validity determines certified test loss", and under this sense, I can use any arbitrarily loss function and call it a "regularizer". For example, I can use a "regularizer" that encourages BAD robustness, and it still fits into the authors explanation. This is like someone publishes a proof showing that P=NP, yet you can use the same argument to show P != NP. This is embarrassing.
The bottom line: I am not saying the propositions in this paper are technically wrong (under the strong assumptions the authors proposed); at least their derivations are straightforward and simple enough to check within a few minutes. However, they are too weak to guide us to find a good training method, too far-fetched to our goal of obtaining good robustness guarantee, and too general that you can use them to prove both sides. So I don't think the "theory" is useful, and the proposed "bounds" guided by the theory has also failed to improve the baseline.
Sorry for the long comments and I hope they can be helpful for the authors.
****** Reply to general author response:
The comparison in the "certifier" table is misleading. "CNN-Cert-Zero" seems to be a special case of CROWN, with a special setting of lower bounds for ReLU. CROWN allows any slope between 0 to 1 as the lower bound, and "CNN-Cert-Zero" is just a special case of that.
Most importantly, the main issue with the paper is not the verifier used; the main issue is that the proposed method performs worse than baseline under correct evaluation, and the proposed "theory" is distracting or wrong.
The new empirical results still do not address any of my concerns - IBP still significantly outperforms the proposed method. For MNIST, Gowal et al. reported over 90% verified accuracy (the proposed method is 75%); the IBP results provided in author response has 0% verified accuracy at , which seems to be a problem or bug. For the CIFAR=8/255 case, the authors keep detuning IBP models and obtain an IBP baseline with less than 20% verified accuracy, yet the IBP model reported in literature (Gowal et al., 2018) can perform over 30%. The proposed method only performs around 20% and the performance gap is huge.
****** Conclusions after author response
After reading the author response, I am still keep my score of reject since the paper contains major technical errors. In a word, the theory is distracting or wrong, and the empirical results provided are intentionally misleading (the proposed method cannot outperform baseline under the right evaluation metrics).
The author response does not address any of my concerns raised, yet the authors insisted that their "theory" is useful (which is apparently not true according to all reviewers) and provided more confusing and misleading results. I have written a long review with detailed reasons and hope the authors can understand why the proposed method fails, but it seems they completely ignored it and did not learn anything from it.
This is quite disappointing.