Stronger and Faster Wasserstein Adversarial Attacks

Kaiwen Wu, Allen Houze Wang, Yaoliang Yu

Abstract

Deep models, while being extremely flexible and accurate, are surprisingly vulnerable to "small, imperceptible" perturbations known as adversarial attacks. While the majority of existing attacks focus on measuring perturbations under the $\ell_p$ metric, Wasserstein distance, which takes geometry in pixel space into account, has long been known to be a suitable metric for measuring image quality and has recently risen as a compelling alternative to the $\ell_p$ metric in adversarial attacks. However, constructing an effective attack under the Wasserstein metric is computationally much more challenging and calls for better optimization algorithms. We address this gap in two ways: (a) we develop an exact yet efficient projection operator to enable a stronger projected gradient attack; (b) we show that the Frank-Wolfe method equipped with a suitable linear minimization oracle works extremely fast under Wasserstein constraints. Our algorithms not only converge faster but also generate much stronger attacks. For instance, we decrease the accuracy of a residual network on CIFAR-10 to $3.4\%$ within a Wasserstein perturbation ball of radius $0.005$, in contrast to $65.6\%$ using the previous Wasserstein attack based on an approximate projection operator. Furthermore, employing our stronger attacks in adversarial training significantly improves the robustness of adversarially trained models.

The Limitations of $\ell_p$ Norms

Most adversarial research focuses on $\ell_p$ norm constraints (like $\ell_\infty$ or $\ell_2$), which limit how much a single pixel's value can change. However, $\ell_p$ norms are poor proxies for human vision; they don't account for geometric shifts. A tiny rotation or translation might have a huge $\ell_p$ distance but look identical to a human.

Comparison of adversarial perturbations under different metrics. Wasserstein attacks capture geometric shifts that can morph a digit's identity more effectively than pixel-wise $\ell_p$ constraints.

The Wasserstein distance (Earth Mover's Distance) is a better metric because it measures the cost of "moving" pixel mass, capturing the underlying geometry of the image. While theoretically superior, Wasserstein attacks are notoriously difficult to compute because they involve solving complex optimal transport problems. Previous attempts, such as the "Projected Sinkhorn" method, relied on crude approximations that resulted in weak attacks and slow convergence.

Efficient Wasserstein Optimization

This paper introduces two new, highly efficient algorithms for generating adversarial attacks based on the Wasserstein distance. By moving away from approximate solvers and providing exact optimization techniques, the authors demonstrate attacks that are significantly stronger and 5–7x faster than previous state-of-the-art methods.

1. PGD with Dual Projection

Projected Gradient Descent (PGD) requires "projecting" a noisy image back into the valid Wasserstein "ball." Instead of using the approximate Sinkhorn method, the authors derive a Dual Projection operator. They show that the dual problem is a univariate function that can be solved exactly and rapidly using a simple bisection method.

2. Frank-Wolfe with Dual LMO

The Frank-Wolfe algorithm is an alternative to PGD that uses a Linear Minimization Oracle (LMO). The authors develop a fast LMO using entropic regularization, which smooths the objective and allows for a stable, closed-form recovery of the adversarial image.

3. Local Transportation

To handle high-resolution images like ImageNet (where the transport matrix would have billions of entries), the researchers restrict pixel movement to a local $k \times k$ neighborhood. This enforces sparsity and makes the computation linear relative to the number of pixels.

Key Results and Insights

The researchers evaluated their methods on MNIST, CIFAR-10, and ImageNet. A major finding was that the "ghostly" outlines often seen in previous Wasserstein work were not inherent to the metric, but rather an artifact of large entropic regularization in approximate solvers. With exact solvers, perturbations are much sparser and more effective.

Convergence comparison showing that the proposed Dual Projection and Dual LMO methods achieve near-zero adversarial accuracy much faster and more reliably than the approximate Sinkhorn baseline.
  • Attack Strength: On CIFAR-10, the previous state-of-the-art Wasserstein attack only reduced a ResNet's accuracy to 65.6%. Using the proposed Dual Projection attack, accuracy plummeted to 3.4% under the same constraints.
  • Speed: The new algorithms are significantly faster. On MNIST and CIFAR-10, Dual Projection is 5–7x faster per iteration than the Sinkhorn-based approach.
  • Adversarial Training: Models trained using these stronger attacks are much more robust. For example, on MNIST, a model trained with their method achieved 59.7% accuracy against Wasserstein attacks, compared to just 0.6% for a model trained with the older Sinkhorn method.

Conclusion

By shifting the optimization from the image space to the transportation space, the authors have made Wasserstein-constrained attacks both practical and potent. While these methods still carry more computational overhead than simple $\ell_\infty$ attacks, they provide a much more realistic assessment of a model's geometric robustness and pave the way for more effective adversarial training strategies.

Summary updated

Abstract

Deep models, while being extremely flexible and accurate, are surprisingly vulnerable to "small, imperceptible" perturbations known as adversarial attacks. While the majority of existing attacks focus on measuring perturbations under the $\ell_p$ metric, Wasserstein distance, which takes geometry in pixel space into account, has long been known to be a suitable metric for measuring image quality and has recently risen as a compelling alternative to the $\ell_p$ metric in adversarial attacks. However, constructing an effective attack under the Wasserstein metric is computationally much more challenging and calls for better optimization algorithms. We address this gap in two ways: (a) we develop an exact yet efficient projection operator to enable a stronger projected gradient attack; (b) we show that the Frank-Wolfe method equipped with a suitable linear minimization oracle works extremely fast under Wasserstein constraints. Our algorithms not only converge faster but also generate much stronger attacks. For instance, we decrease the accuracy of a residual network on CIFAR-10 to $3.4\%$ within a Wasserstein perturbation ball of radius $0.005$, in contrast to $65.6\%$ using the previous Wasserstein attack based on an \emph{approximate} projection operator. Furthermore, employing our stronger attacks in adversarial training significantly improves the robustness of adversarially trained models.
BibTeX
@inproceedings{wu2020stronger,
  author = {Kaiwen Wu and Allen Houze Wang and Yaoliang Yu},
  title = {{Stronger and Faster Wasserstein Adversarial Attacks}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=SGfZ0ihOW-5},
}
Figure