Adversarial training has been recognized as a strong defense against adversarial attacks. In this paper, we propose a powerful second-order attack method that reduces the accuracy of the defense model by Madry et al. (2017). We demonstrate that adversarial training overfits to the choice of the norm in the sense that it is only robust to the attack used for adversarial training, thus suggesting it has not achieved universal robustness. The effectiveness of our attack method motivates an investigation of provable robustness of a defense model. To this end, we introduce a framework that allows one to obtain a certifiable lower bound on the prediction accuracy against adversarial examples. We conduct experiments to show the effectiveness of our attack method. At the same time, our defense model achieves significant improvements compared to previous works under our proposed attack.
This paper makes two different contributions in the field of adversarial training and robustness.
First the authors introduce a new type of attack that exploits second-order information while traditional attacks typically rely on first-order information.
Another contribution is a theorem that using the Renyi divergence certifies robustness of a classifier by adding Gaussian noise to pixels.
Overall, I find that the paper lacks clarity and does not properly contrast their work to existing results. They are also some issues with the evaluation results. I provide detailed feedback below.
1) Prior work
a) Connection between adversarial defense and robustness to random noise
This connection is established in Fawzi, A., Moosavi-Dezfooli, S. M., & Frossard, P. (2016). Robustness of classifiers: from adversarial to random noise. In Advances in Neural Information Processing Systems (pp. 1632-1640).
b) Connection between minimal perturbation required to confuse classifier and its confidence was discussed for the binary classification in Section 4 of
Fawzi, Alhussein, Omar Fawzi, and Pascal Frossard. "Analysis of classifiers’ robustness to adversarial perturbations." Machine Learning 107.3 (2018): 481-508.
c) The idea to compute the distribution of classifier outputs when the input is convolved with Gaussian noise was already “anticipated” in Section V of the following paper which relates the minimum perturbation needed to fool a model to it’s misclassification rate under Gaussian convolved input:
Lyu, Chunchuan, Kaizhu Huang, and Hai-Ning Liang. "A unified gradient regularization family for adversarial examples." Data Mining (ICDM), 2015 IEEE International Conference on. IEEE, 2015.
These papers should be discussed in the paper, please elaborate how you see your contribution regarding the results derived there.
2) Second-order attack introduced in the paper
I think they are a number of important details that are ignored in the presentation.
a) Regarding the assumption that the gradient vanishes in the difference of the loss, I think the authors should elaborate as to why this is a reasonable assumption to make. If we assume that the classifier has been trained to optimality then expanding the function at this (near-)optimum would perhaps indeed yield to a gradient term of small magnitude (assuming the function is smooth). However, nothing guarantees that the magnitude of the gradient term is negligible compared to the second-order information. The boundary of the classifier could very well be in a region of low-curvature.
b) The approximation of the second-order information is rather crude. However, the update derived is very similar to PGD with additional noise. In optimization, the use of noise is known to extract curvature, see e.g. (Xu & Yang, 2017) who showed that noisy gradient updates act as a noisy Power method that extracts negative curvature direction.
Xu, Y., & Yang, T. (2017). First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time. arXiv preprint arXiv:1711.01944.
3) Issue of "degenerate global minimum": The authors argue that multistep attacks also suffer from this issue. However, the PGD attack of Madry is also initialized at a random point within the uncertainty ball around x, i.e. PGD attack first adds random noise to x before iteratively ascending the loss function. This PGD update + noise at first iteration seem rather similar to the update derived by the authors that uses random noise at every iteration. It could therefore be that the crude approximation of second-order information is not so different from previous work. This should be further investigated either theoretically or empirically.
4) Lack of details regarding some important aspects in the paper
a) “Note the evaluation requires adjustment and computing confidence intervals for p(1) and p(2), but we omit the details as it is a standard statistical procedure”
The authors seem to sweep this under the carpet but this estimation procedure gives only an estimate of the required quantities p(1) and p(2), which I think would require adjusting the result in the theorem to be a high probability bound (or an expectation bound) instead of a deterministic result.
b) “the noise is not necessarily added directly to the inputs but also to the first layer of a DNN. Given the Lipschitz constant of the first layer, one can still calculate an upper bound using our analysis. We omit the details here for simplicity”
What exactly changes here? How do you estimate the Lipschitz constant in practice?
5) Main theorem needs to be contrasted to previous results
The main Theorem uses the Renyi divergence certifies robustness of a classifier by adding Gaussian noise to pixels. There are already many results in the field of robust optimization that already derive similar results, see e.g.
Namkoong, H., & Duchi, J. C. (2017). Variance-based regularization with convex objectives. In Advances in Neural Information Processing Systems (pp. 2971-2980).
Gao, R., & Kleywegt, A. J. (2016). Distributionally robust stochastic optimization with Wasserstein distance. arXiv preprint arXiv:1604.02199.
Can you elaborate on the difference between your bounds and these ones? You do mention some of them require strong assumptions such as smoothness but this actually seems like a mild assumption (although some activation functions used in neural nets are indeed not smooth).
6) Adversarial Training Overfit to the Choice of norms
The main theorem derived in the paper uses the l_2 norm. What can be said regarding other norms?
7) Experiments:
a) the authors only report accuracies for attacks whose l2-norm is smaller than a fixed constant 0.8. However, this makes the results difficult to interpret and the authors should instead state the signal to noise ratio, i.e. dividing the l2-norm of the perturbation by the l2-norm of the image. Otherwise, it is not clear how strong or weak such perturbations are. (In particular, the norm depends on the dimension of the image, so l2-norms of perturbations for MNIST and CIFAR10 are not comparable).
b) In Section 6.2, the authors state that an l_infty trained model is vulnerable against l_2 perturbations. Why not training the model under both l_infty and l_2 perturbations?
c) Figure 1
Based on the results predicted in Theorem 2, it seems it would be more interesting to evaluate the largest L for which the classifier predictions are the same. Why did you report a different results?
8) Other comments
section 2.1: “Note this distribution is different from the one generated from softmax”. Why/How is this different?
connection to EOT attack’: authors claim: E_{d∼N(0,σ2I)} [∇_x L(θ, x, y)|x+d] = ∇_x E_{d∼N(0,σ2I)} [∇_x L(θ, x, y)|x+d]. There is a typo on the RHS where ∇_x is repeated twice. This is also the common reparametrization trick so could cite 
Kingma, D. P., & Welling, M. (2013). Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114.