PaperlayerView exact revision on arXiv

Source-linked AI summary

Wasserstein Adversarial Examples via Projected Sinkhorn Iterations

Eric Wong, Frank R. Schmidt, J. Zico Kolter

arXiv:1902.07906v2cs.LGstat.ML

TL;DR

Adversarial-example research has largely relied on ℓp threat models, which do not capture all broad image transformations. This paper introduces Wasserstein-bounded attacks with a fast approximate Sinkhorn-based projection, reducing standard CIFAR10 accuracy to 3% at radius 0.1 and raising adversarial accuracy to 76% through adversarial training.

  • Problem

    Prior adversarial-example research has focused primarily on ℓp-bounded perturbations, despite broader attacks such as transformations lying outside these threat models.

  • Method

    The paper develops Wasserstein-bounded adversarial attacks using fast approximate projection based on entropy-regularized, modified Sinkhorn iterations and local transport plans.

  • Results

    3% adversarial accuracy is obtained for a standard CIFAR10 classifier within a Wasserstein ball of radius 0.1, while adversarial training raises it to 76% with 80.7% nominal accuracy.

  • Takeaways & Limitations

    Wasserstein perturbations provide a qualitatively different adversarial threat model whose image perturbations reflect image content, and adversarial training is empirically effective against it.

  • Takeaways & Limitations

    Existing certified defenses cannot be easily extended to Wasserstein attacks because interval-bound propagation is fundamentally mismatched with Wasserstein transport.

Abstract

from arXiv · show

A rapidly growing area of work has studied the existence of adversarial examples, datapoints which have been perturbed to fool a classifier, but the vast majority of these works have focused primarily on threat models defined by $\ell_p$ norm-bounded perturbations. In this paper, we propose a new threat model for adversarial attacks based on the Wasserstein distance. In the image classification setting, such distances measure the cost of moving pixel mass, which naturally cover "standard" image manipulations such as scaling, rotation, translation, and distortion (and can potentially be applied to other settings as well). To generate Wasserstein adversarial examples, we develop a procedure for projecting onto the Wasserstein ball, based upon a modified version of the Sinkhorn iteration. The resulting algorithm can successfully attack image classification models, bringing traditional CIFAR10 models down to 3% accuracy within a Wasserstein ball with radius 0.1 (i.e., moving 10% of the image mass 1 pixel), and we demonstrate that PGD-based adversarial training can improve this adversarial accuracy to 76%. In total, this work opens up a new direction of study in adversarial robustness, more formally considering convex metrics that accurately capture the invariances that we typically believe should exist in classifiers. Code for all experiments in the paper is available at https://github.com/locuslab/projected_sinkhorn.

1. Introduction

Adversarial-example research has largely used ℓp threat models, but these do not comprehensively represent attacks such as translations and other broad transformations. The paper proposes Wasserstein-bounded perturbations and efficient methods for attacking and training models under this threat model.

  • A one-pixel image shift can be small in Wasserstein distance but large in ℓ∞ distance, whereas uniformly graying pixels has the opposite relationship.
  • Most adversarial-example research has focused on ℓ∞ and generalized ℓp threat models, leaving broad classes of attacks beyond norm balls comparatively understudied.
  • Wasserstein distance models image perturbations as the cost of moving pixel mass, producing allowable changes that can differ substantially from those in an ℓp ball.
  • The paper derives a fast approximate Wasserstein-ball projection based on a modified Sinkhorn iteration and develops efficient adversarial training methods.
  • 3% adversarial accuracy results from attacking a standard CIFAR10 classifier from 94.7% within a Wasserstein ball of radius 0.1.The radius corresponds to moving 10% of the image mass by one pixel.
  • 76% adversarial accuracy is achieved after adversarial training, while nominal accuracy remains 80.7%.

2. Background and Related Work

Prior work has concentrated on ℓp-based attacks, defenses, and verifiers, while other attack classes have received less systematic treatment. This paper uses Wasserstein distance and Sinkhorn-based computation to develop and evaluate a qualitatively different adversarial threat model.

  • The established adversarial-example literature centers on ℓ∞ and ℓp perturbations, including projected-gradient attacks, heuristic defenses, certified defenses, and verifiers.
  • Rotations, translations, and real-world attacks demonstrate that adversarial perturbations need not remain within traditional imperceptible-noise balls.
  • Standard Wasserstein computation is expensive because optimal transport uses a quadratic number of variables, motivating entropy-regularized Sinkhorn approximations.
  • The paper derives a fast approximate projection using Sinkhorn ideas and local transport plans to make Wasserstein adversarial-image generation tractable.
  • Wasserstein perturbations have inherent structure reflecting image content, unlike the perturbations considered under ℓ∞ and ℓ2 metrics.

3. Preliminaries

The preliminaries formulate projected-gradient attacks, adversarial training, and Wasserstein distance for normalized inputs and transport plans. Wasserstein distance measures the minimum cost of moving probability mass between inputs, while projection keeps iterates inside the chosen threat ball.

  • PGD-based adversarial attacks: Projected-gradient attacks iteratively take a loss-increasing step and project the result back into a threat-model ball.
  • Wasserstein distance: Figure 2 compares original, perturbation, and final images for Wasserstein and ℓ∞ MNIST attacks, showing content-structured Wasserstein changes and background attacks under ℓ∞.
  • PGD-based adversarial attacks: For an ℓ∞ ball and ℓ∞ steepest descent, the projected-gradient procedure recovers the Basic Iterative Method.
  • Adversarial training: Adversarial training minimizes loss on examples generated by running projected-gradient descent within the specified threat ball.
  • Wasserstein distance: Wasserstein distance is the minimum transport cost required to move probability mass from one distribution to another, with image costs determined by pixel movement.
  • Wasserstein distance: Inputs are normalized as non-negative data points whose masses sum to one, and transport plans encode how mass moves between input locations.

4. Wasserstein Adversarial Examples

The paper introduces Wasserstein adversarial examples as a fundamentally different threat model and develops an efficient approximate projection for generating them. Local transport plans make projected attacks practical on images while preserving feasibility within the Wasserstein ball.

  • Wasserstein threat model: Wasserstein adversarial examples define a threat model fundamentally different from typical ℓp perturbations.The approach measures perturbations through the cost of transporting pixel mass.
  • Projection method: Exact projection onto the Wasserstein ball is expensive, so the method solves an entropy-regularized projection problem using modified Sinkhorn iterations.The procedure derives a dual problem and performs block coordinate updates with an additional dual variable and quadratic term.
  • Projection method: The approximate projection relaxes only which feasible point is closest in ℓ2 norm; generated examples remain inside the actual Wasserstein ball.Thus, approximation affects projection optimality rather than membership in the threat model.
  • Projection method: Projected Sinkhorn iterates use a line search to maintain ψ ≥0, with each iteration requiring 8 O(n^2) operations.The algorithm is vectorized and returns the projected variable after alternating updates and Newton steps.
  • Local transport plans: Restricting transport to a k × k neighborhood reduces each iteration’s complexity to O(nk^2), enabling projected gradient descent and adversarial training on images.The same transport plan can be used across image channels while limiting movement within local regions.

5. Results

The experiments evaluate Wasserstein attacks across MNIST and CIFAR10 models, comparing standard, ℓ∞-robust, binarized, and adversarially trained defenses. Wasserstein adversarial training improves robustness, while provable ℓ∞ defenses transfer unevenly and interval-based certification faces a fundamental obstacle.

  • MNIST: On MNIST, Wasserstein attacks with radius 0.5 misclassify a typical classifier 50% of the time, rising to 94% at radius 1.A radius of 0.5 corresponds intuitively to moving 50% of pixel mass by one pixel.
  • MNIST: Binarization performs only marginally better than the standard MNIST model against Wasserstein perturbations.
  • MNIST: The provably ℓ∞-robust MNIST model is substantially more robust to Wasserstein attacks, requiring a significantly larger radius for the same attack success rate.
  • MNIST: MNIST adversarial training produces the best defense among the four models and does not reduce accuracy to 0%.Training uses a weaker 50-iteration projected-gradient adversary.
  • CIFAR10: At Wasserstein radius 0.1, attacks fool 97% of standard CIFAR10 ResNet18 examples, while the ℓ∞-robust model retains 61% adversarial accuracy versus 3% for the standard model.The ℓ∞-robust CIFAR10 model has only 66% nominal accuracy on unperturbed examples.
  • CIFAR10: CIFAR10 adversarial training raises adversarial accuracy from 3% to 76% at radius 0.1.The experiments use a weaker 50-iteration projected-gradient adversary during training.

6. Conclusion

The paper introduces Wasserstein adversarial perturbations and fast approximate projection, demonstrates attacks and adversarial training, and identifies limitations for provable defenses and broader threat-model characterization.

  • 6. Conclusion: Wasserstein distance defines a threat model fundamentally different from traditional ℓp perturbations and captures structurally content-dependent image perturbations.
  • 6. Conclusion: The proposed fast, approximate projection algorithm can use local transport plans to accelerate generation of Wasserstein adversarial examples on images.
  • 6. Conclusion: Adversarial training is empirically effective against Wasserstein attacks, while existing provable defenses rely on interval bounds that do not directly apply to Wasserstein balls.
  • 6. Conclusion: Efficient verification or provable training methods that avoid interval bounds remain an open question for Wasserstein and related attacks.
  • 6. Conclusion: The paper does not characterize all reasonable adversarial perturbations, leaving a gap in rigorously defining broader classes beyond ℓp and Wasserstein balls.
  • 6. Conclusion: Projection onto Wasserstein balls may also support optimization methods beyond deep learning, including ADMM, alternating projections, and Wasserstein-constrained variables.

A.1. Proof of Lemma 3

The proof derives the dual of the entropy-regularized Wasserstein projection problem by scaling the objective, introducing constraints' dual variables, and optimizing the resulting Lagrangian.

  • A.1. Proof of Lemma 3: The proof rescales the entropy-regularized Wasserstein projection objective before deriving its dual formulation.
  • A.1. Proof of Lemma 3: Dual variables α, β, and nonnegative ψ are introduced to form the Lagrangian with the projection constraints.
  • A.1. Proof of Lemma 3: KKT optimality conditions are used to characterize the optimum and obtain the dual objective g.

A.2. Proof of Lemma 4

The proof connects dual optima to primal solutions through KKT conditions and interprets the resulting Projected Sinkhorn updates as transport-matrix rescaling steps.

  • A.2. Proof of Lemma 4: Dual maximizers α*, β*, and ψ* yield the corresponding primal minimizers through the transformations established by the KKT conditions.
  • A.2. Proof of Lemma 4: Because the projection problem is strictly convex, setting dual gradients to zero produces the α and β updates, while ψ uses scalar derivative calculations.
  • A.2. Proof of Lemma 4: The α update rescales the transport matrix to sum to x, and the β update rescales it to sum to the projected value.
  • A.2. Proof of Lemma 4: The ψ update adjusts the transport plan according to whether it exceeds or falls below the maximum threshold ϵ.

B. Experimental setup

The experiments use adaptive Wasserstein budgets during adversarial training and examine optimizer settings and projection parameters, finding that λ controls blur while higher p produces blockier images and larger transport costs.

  • Experimental setup: During MNIST adversarial training, ϵ starts at 0.1, increases by 1.4 every five iterations, and ranges from 0.1 to 2.1 before termination.Projected gradient descent stops after finding an adversarial example or reaching 50 iterations.
  • Experimental setup: The training optimizer uses SGD with 0.9 momentum, 0.0005 weight decay, batch size 128, and a learning rate reduced from 0.1 to 0.01 after 10 epochs.
  • Experimental setup: During CIFAR10 adversarial training, ϵ starts at 0.01, increases by 1.5 every five iterations, and ranges from 0.01 to 0.38.Projected gradient descent terminates after finding an adversarial example or reaching 50 iterations.
  • Experimental setup: The adaptive budget scheme gradually increases ϵ from ϵmin toward ϵmax during training instead of using a fixed attack budget.The stated motivation is to extend robustness across a range of perturbation strengths.
  • Experimental setup: The parameter study varies λ and the Wasserstein cost exponent p, evaluating effects on adversarial examples and the radius where they are found.
  • Experimental setup: For λ = (1, 10) and almost all λ = 100, severe blurring prevents finding adversarial examples.
  • Experimental setup: Increasing p makes images more blocky, moves more pixels by larger amounts, and increases the ϵ radius because transport costs rise.

C.2. Size of local transport plan

Transport-plan size generally has little effect on adversarial accuracy, except for the 3 × 3 local plan, which struggles against the robust MNIST model.

  • C.2. Size of local transport plan: The paper uses a 5 × 5 local transport plan in its main experiments and compares it with alternatives such as 3 × 3 and 7 × 7 plans.
  • C.2. Size of local transport plan: 2.8% adversarial accuracy remains for the standard model at ϵ = 1.83 with the 3 × 3 local transport plan.
  • C.2. Size of local transport plan: 41% adversarial accuracy remains for the robust MNIST model at ϵ = 1.83 with the 3 × 3 local transport plan.
  • C.2. Size of local transport plan: 3 × 3 transport plans have difficulty attacking the robust MNIST model, while other plan sizes show similar performance.The comparison uses λ = 1000.

D.1. Conjugate Sinkhorn iteration

The Conjugate Sinkhorn iteration derives a Sinkhorn-like projection procedure for a related conjugate problem. It matches the Projected Sinkhorn updates except for a fixed β step.

  • D.1. Conjugate Sinkhorn iteration: Subtracting an entropy term produces an optimization problem similar to projecting onto the Wasserstein ball.
  • D.1. Conjugate Sinkhorn iteration: The derivation introduces dual variables α, β, and ψ, with ψ ≥ 0.
  • D.1. Conjugate Sinkhorn iteration: The Πij KKT optimality condition remains unchanged, while the optimality condition for z changes.
  • D.1. Conjugate Sinkhorn iteration: Minimizing with respect to α and ψ yields the same update steps as the Projected Sinkhorn iteration.
  • D.1. Conjugate Sinkhorn iteration: The Conjugate Sinkhorn iteration differs by replacing the β step with the fixed value β = λy.
Loading 1902.07906v2…