PDPGD: Primal-Dual Proximal Gradient Descent Adversarial Attack
  State-of-the-art deep neural networks are sensitive to small input
perturbations. Since the discovery of this intriguing vulnerability, many
defence methods have been proposed that attempt to improve robustness to
adversarial noise. Fast and accurate attacks are required to compare various
defence methods. However, evaluating adversarial robustness has proven to be
extremely challenging. Existing norm minimisation adversarial attacks require
thousands of iterations (e.g. Carlini & Wagner attack), are limited to the
specific norms (e.g. Fast Adaptive Boundary), or produce sub-optimal results
(e.g. Brendel & Bethge attack). On the other hand, PGD attack, which is fast,
general and accurate, ignores the norm minimisation penalty and solves a
simpler perturbation-constrained problem. In this work, we introduce a fast,
general and accurate adversarial attack that optimises the original non-convex
constrained minimisation problem. We interpret optimising the Lagrangian of the
adversarial attack optimisation problem as a two-player game: the first player
minimises the Lagrangian wrt the adversarial noise; the second player maximises
the Lagrangian wrt the regularisation penalty. Our attack algorithm
simultaneously optimises primal and dual variables to find the minimal
adversarial perturbation. In addition, for non-smooth $l_p$-norm minimisation,
such as $l_{\infty}$-, $l_1$-, and $l_0$-norms, we introduce primal-dual
proximal gradient descent attack. We show in the experiments that our attack
outperforms current state-of-the-art $l_{\infty}$-, $l_2$-, $l_1$-, and
$l_0$-attacks on MNIST, CIFAR-10 and Restricted ImageNet datasets against
unregularised and adversarially trained models.
