A robustness certificate against adversarial examples is the minimum distance of a given input to the decision boundary of the classifier (or its lower bound). For any perturbation of the input with a magnitude smaller than the certificate value, the classification output will provably remain unchanged. Computing exact robustness certificates for deep classifiers is difficult in general since it requires solving a nonconvex optimization. In this paper, we provide computationally-efficient robustness certificates for deep classifiers with differentiable activation functions in two steps. First, we show that if the eigenvalues of the Hessian of the network (curvatures of the network) are bounded, we can compute a robustness certificate in the l 2 norm efficiently using convex optimization. Second, we derive a computationallyefficient differentiable upper bound on the curvature of a deep network. We also use the curvature bound as a regularization term during the training of the network to boost its certified robustness against adversarial examples. Putting these results together leads to our proposed Curvature-based Robustness Certificate (CRC) and Curvature-based Robust Training (CRT). Our numerical results show that CRC outperforms CROWN's certificate when trained with our regularizer while CRT leads to higher certified accuracy compared to standard adversarial training.
This paper gives a global curvature bound for general neural networks, and used this bound for certifying robustness of neural networks. The basic techniques include writing the neural network verification problem as a constrained optimization problem (similar to [1]), and construct a Lagrangian dual for it, and discuss the situation where the dual problem is convex and can be solved efficiently. The global curvature bound is the crucial step to determine the condition that the optimization problem is convex.
The benefits of the proposed methods include efficiency (bounds m and M only need to be solved for each target label pair, and the optimization process to get the certificate is fast), and tight certified accuracy for shallow networks. Also, it can be used during training to improve the tightness of CRC bounds.  There are also a few weakness: the certificate unfortunately only works for non-ReLU networks, and only for L2 norm; for networks beyond 2 layers, CRC cannot outperform CROWN unless it is specially trained using the CRC loss.
Questions and concerns:
1. For the curvature regularization training, some comparisons against other certified defenses are needed - PGD and TRADES are not good examples since they are not certified defense methods, and 0% certified accuracy are obtained. I understand many existing works like Wong et al., 2018 only work on ReLU networks, but I believe interval bound propagation (IBP) based methods [2] should be easily applicable to any monotonic activation functions. At least, the authors should compare verified accuracy at the same epsilon settings (\pho=1.58) as in Wong et al., 2018.  In page 22 (last page of appendix in arxiv version) of [3], you can find their L2 robustness training results.  How does the certified accuracy of CRC compare to these results?
2. The paper mentions the Attack problem and proposes an attack algorithm (Algorithm 2), however I am not able to find any experiments on the attack. If the authors want to claim the contribution of curvature based attacks, some empirical results should be given, and at least compare it to a 200-step PGD baseline and see which one finds smaller adversarial examples.
3. The claim (in introduction and conclusions) that CRC is much faster than CROWN probably won't hold under a fair comparison. I believe the gradient decent based certification algorithm (Algorithm 1) was computed efficiently on GPU, where the NN is defined. For a fair comparison, it should be also compared to a GPU implementation of CROWN ([4] provides such an implementation).  In my experience, CROWN is an efficient algorithm that can be even used iteratively during training (as a certified defense [4]), so for the small networks used in this paper, it should compute bounds almost instantly on GPUs. I think it is better to revoke this claim, and in experiments the authors should clearly state that CROWN was computed on CPU so time is not comparable. 
4. Also the claim "CRC outperforms CROWN's certificate significantly" should be made clearer that it only holds for CRC trained models. According to Table 3, CRC is significantly worse than CROWN if the model is not CRC trained.  Additionally, it should be made clear that the proposed method currently only applies to L2 norm setting.
5. (Minor) There are several duplicated references, e.g., on page 9, Cohen et al., (randomized smoothing) was cited twice as two different papers; the same is with Madry et al., on page 10, and Zhang et al. (CROWN) on page 11. These causes some confusions, e.g., on page 2, when talking about the bounded Lipschitz constant, I believe the correct citation for (Zhang et al., 2018b) should be another paper [5] from the same first author which is on bounding Lipschitz constant.
Improvements and extensions:
I think the proposed method can be greatly improved by using "local curvature", where the curvature bounds m and M are computed within a local region near an input point. This is sufficient as long as our optimization does not escape this safe region, and the safe region can be naturally defined as the perturbation radius to be certified. The local curvature can be obtained by giving a tighter bounds on the second derivative of activation function, rather than considering just the worst case. Using CROWN, we can obtain pre-activation upper and lower bounds. These bounds can be used to bound the second derivative. For example, if a tanh neuron's input is bounded by -0.1 and 0.1 (those bounds can be obtained efficiently by CROWN), the second derivative of tanh is bounded between -0.197356 and +0.197356, much better than the worst case bound -0.76981 and +0.76981 used in current global curvature bound. A similar technique to bound Jacobian matrix was used in [5]. Including some results for local curvature certificates will greatly increase the contribution of this paper, and make it a complete work. I strongly encourage the authors to do so, and feel free to discuss with me on any questions.
Despite some concerns, the main contribution of giving global curvature bounds of neural networks is valid. Thus I vote for accepting this paper, however the authors should make sure to address all the concerns.
[1] Salman, Hadi, et al. "A convex relaxation barrier to tight robust verification of neural networks." arXiv preprint arXiv:1902.08722 (2019).
[2] Gowal, Sven, et al. "On the effectiveness of interval bound propagation for training verifiably robust models." arXiv preprint arXiv:1810.12715 (2018).
[3] Wong, Eric, et al. "Scaling provable adversarial defenses." Advances in Neural Information Processing Systems. 2018. https://arxiv.org/pdf/1805.12514.pdf
[4] Zhang, Huan, et al. "Towards Stable and Efficient Training of Verifiably Robust Neural Networks." arXiv preprint arXiv:1906.06316 (2019).
[5] Zhang, H., Zhang, P., & Hsieh, C. J. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. arXiv preprint arXiv:1810.11783 (2018).