← Back to Publications

PDPGD: Primal‑Dual Proximal Gradient Descent Adversarial Attack

Alexander Matyasko, Lap‑Pui Chau · arXiv:2106.01538 · 2021

Abstract

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 $\ell_p$-norm minimisation, such as $\ell_{\infty}$-, $\ell_1$-, and $\ell_0$-norms, we introduce primal-dual proximal gradient descent attack. We show in the experiments that our attack outperforms current state-of-the-art $\ell_{\infty}$-, $\ell_2$-, $\ell_1$-, and $\ell_0$-attacks on MNIST, CIFAR-10 and Restricted ImageNet datasets against unregularised and adversarially trained models.

TL;DR

Algorithm: Primal‑Dual Proximal Gradient Descent (PDPGD)

Inputs: image $\mathbf{x}$, label $y$, initial $\mathbf{r}^{(0)}$, iterations $T$, step sizes $\theta_{\mathbf{r}}$, $\theta_{\lambda}$.

Output: adversarial perturbation $\mathbf{r}$.

1. Initialize $\mathbf{r} \leftarrow \mathbf{0}$ and choose $\lambda^{(0)} \ge 0$.
2. For $k = 1,\dots,T$:
   1. Compute $\nabla_{\mathbf{r}}^{(k)} = \nabla_{\mathbf{r}}\,\mathcal{L}(\mathbf{x}+\mathbf{r}^{(k)}, y)$ for the chosen loss.
   2. Compute $\nabla_{\lambda}^{(k)}$ from the Lagrangian $\mathbb{L}_{\lambda}(\mathbf{r}^{(k)}, \lambda^{(k)})$.
   3. Primal update $$\mathbf{r}^{(k+1)} = \Pi_{C}^{\mathbf{x}}\!\left( \operatorname{prox}_{\,\theta_{\mathbf{r}}\,\lambda\,\|\cdot\|_p}\!\big(\mathbf{r}^{(k)} - \theta_{\mathbf{r}}\, \nabla_{\mathbf{r}}^{(k)}\big) \right)$$
   4. Dual update $$\lambda^{(k+1)} = \Pi_{\Lambda}\!\left( \lambda^{(k)} + \theta_{\lambda}\, \nabla_{\lambda}^{(k)} \right)$$
   5. Keep best: if $\hat{k}(\mathbf{x}+\mathbf{r}^{(k+1)}) \neq y$ and $\|\mathbf{r}^{(k+1)}\| \le \|\mathbf{r}\|$, then set $\mathbf{r} \leftarrow \mathbf{r}^{(k+1)}$.

Notes: $\Pi_C^{\mathbf{x}}$ clips $\mathbf{x}+\mathbf{r}$ to $[0,1]^N$; $\operatorname{prox}$ uses norm‑specific closed forms (see “Proximal operators used” below); $\Pi_{\Lambda}$ enforces $\lambda \ge 0$.

Core Idea

The goal of a white-box adversarial attack is to find the smallest possible perturbation to an input that causes a neural network to make a mistake. The norm of the minimal perturbation is a fundamental measure of a model's robustness and can be used to compare different models and defence methods. The problem of finding the minimal adversarial perturbation can be stated as the following constrained optimization problem:

$$ \min_{\mathbf{r}} \; \|\mathbf{r}\|_p \;\; \text{s.t.}\;\; \hat{k}(\mathbf{x}+\mathbf{r}) \neq y, \;\; \mathbf{x}+\mathbf{r} \in [0,1]^N $$

Current white-box adversarial attacks can be broadly divided into two main approaches with some drawbacks:

1. Penalized Optimization (e.g., C&W, EAD): These methods convert the problem into a penalized form, $\lVert r\rVert_p + \lambda \cdot \mathcal{L}(x+r, y)$, but require a slow and costly binary search over the penalty weight $\lambda$ to find the minimal perturbation.
2. Norm-Constrained Optimization (e.g., PGD): These methods maximize the model's loss within a fixed-size $\varepsilon$-ball, $\lVert r\rVert_p \le \varepsilon$. To find the minimal perturbation, one must run the attack multiple times, scanning through different values of $\varepsilon$, which is also costly.

To address these limitations, we view the optimisation above as a two‑player game over the Lagrangian $\mathcal{L}(\mathbf{r},\lambda) = \|\mathbf{r}\|_p + \lambda\,g(\mathbf{x}+\mathbf{r})$, where $g$ encodes a surrogate misclassification constraint. The first player minimises the Lagrangian wrt the adversarial noise; the second player maximises the Lagrangian wrt the regularisation penalty, which penalises the first player for violating the misclassification constraint. We solve this game using a primal-dual gradient descent algorithm, which simultaneously updates the primal variable (the perturbation) and the dual variable (the penalty weight).

Plain subgradient descent converges slowly for non-smooth penalties, such as $\ell_0$-, $\ell_0$- and $\ell_\infty$-norms (rate $O(1/\sqrt{T})$), and fails entirely for non-differentiable norms such as $\ell_0$-norm. Our primal–dual proximal gradient descent (PDPGD) algorithm fixes this. Our PDPGD attack uses the following update rules:

$$\mathbf{r}_{t+1} = \operatorname{prox}_{\eta\,\|\cdot\|_p}\big(\mathbf{r}_t - \eta\,\nabla_{\mathbf{r}} \, g(\mathbf{x}+\mathbf{r}_t)\,\lambda_t\big), \quad \lambda_{t+1} = \big[\lambda_t + \gamma\, g(\mathbf{x}+\mathbf{r}_{t+1})\big]_+$$

For non‑smooth norms we apply the appropriate proximal operators (e.g., hard‑thresholding for $\ell_0$, soft‑thresholding for $\ell_1$, projection/clipping for $\ell_\infty$); see the full paper for details. For RGB images we also introduce a grouped $\ell_0^G$ proximal step to reduce the number of perturbed pixels. Our attack avoids repeated restarts over penalty weights and directly targets minimal‑norm adversarial examples.

Experiments on MNIST, CIFAR‑10, and Restricted ImageNet show that PDPGD consistently finds lower‑norm adversarial examples with fewer iterations than C&W/EAD/FAB and without the $\varepsilon$ scans required by PGD. It performs strongly against both standard and adversarially trained models across $\ell_{\infty}$, $\ell_2$, $\ell_1$, and $\ell_0$ norms.

@article{matyasko2021pdpgd,
  title         = {PDPGD: Primal-Dual Proximal Gradient Descent Adversarial Attack},
  author        = {Matyasko, Alexander and Chau, Lap{-}Pui},
  year          = {2021},
  month         = jun,
  journal       = {arXiv e-prints},
  eid           = {arXiv:2106.01538},
  archiveprefix = {arXiv},
  eprint        = {2106.01538},
  primaryclass  = {cs.LG}
}