PaperlayerView exact revision on arXiv

Source-linked AI summary

Certifying Some Distributional Robustness with Principled Adversarial Training

Aman Sinha, Hongseok Namkoong, Riccardo Volpi, John Duchi

arXiv:1710.10571v5stat.MLcs.LG

TL;DR

Neural networks remain vulnerable to adversarial examples, while existing defenses and verification methods offer limited rigorous guarantees or prohibitive computation. This paper trains models through a Lagrangian relaxation of Wasserstein distributional robustness, using worst-case training-data perturbations. For smooth losses, the procedure provides moderate robustness and efficient population-loss certification with little computational or statistical cost, and empirical evaluations match or outperform less-principled methods.

  • Problem

    Neural networks are vulnerable to adversarial examples, while heuristic defenses lack rigorous attack-class guarantees and formal verification is generally NP-hard or prohibitively expensive.

  • Method

    The paper uses a Lagrangian penalty formulation of Wasserstein distributional robustness and trains with worst-case perturbations of sampled training data.

  • Results

    For smooth losses, the procedure achieves moderate robustness with essentially no computational or statistical cost, efficiently certifies worst-case population loss, and matches or outperforms heuristic adversarial training.

  • Takeaways & Limitations

    Principled adversarial training can provide certified robustness across many machine-learning models and scenarios while remaining computationally practical for smooth networks.

  • Takeaways & Limitations

    The robustness certificates can be too large for practical security-critical use because their bounds depend on covering numbers and dimension, and smoothness bounds can be prohibitively loose for deep architectures.

Abstract

from arXiv · show

Neural networks are vulnerable to adversarial examples and researchers have proposed many heuristic attack and defense mechanisms. We address this problem through the principled lens of distributionally robust optimization, which guarantees performance under adversarial input perturbations. By considering a Lagrangian penalty formulation of perturbing the underlying data distribution in a Wasserstein ball, we provide a training procedure that augments model parameter updates with worst-case perturbations of training data. For smooth losses, our procedure provably achieves moderate levels of robustness with little computational or statistical cost relative to empirical risk minimization. Furthermore, our statistical guarantees allow us to efficiently certify robustness for the population loss. For imperceptible perturbations, our method matches or outperforms heuristic approaches.

1 Introduction

The paper replaces heuristic adversarial training with a distributionally robust formulation that perturbs the data distribution within a Wasserstein neighborhood. Its procedure provides computational, statistical, and population-level robustness guarantees for smooth losses while matching or outperforming heuristic methods on imperceptible perturbations.

  • Motivation: Neural networks can fail under seemingly imperceptible perturbations, while existing attack, defense, and verification methods provide limited rigorous guarantees or are computationally prohibitive.Model failures are especially costly in performance-critical systems such as autonomous perception and tumor detection.
  • Distributionally robust formulation: The paper formulates robustness through distributionally robust optimization over distributions near the data-generating distribution P0.The uncertainty set is a Wasserstein neighborhood, and the approach targets worst-case population loss.
  • Proposed procedure: The proposed training procedure augments parameter updates with worst-case perturbations of sampled training data using a Lagrangian penalty surrogate.The unknown P0 is replaced by its empirical distribution during training.
  • Guarantees: For smooth losses, moderate robustness against imperceptible perturbations is achievable with essentially no computational or statistical cost relative to ERM.The penalty makes the inner perturbation problem strongly concave when γ is sufficiently large.
  • Guarantees: The method provides an efficiently computable certificate for worst-case population loss and generalizes protection learned from training-data perturbations to test data.A simple implementation takes 5–10× as long as stochastic-gradient ERM and matches runtimes of other adversarial-training procedures.
  • Relation to prior work: Prior distributionally robust methods often require restrictive convex losses or costs, whereas this work develops direct methods for a larger class relevant to machine learning.Existing Wasserstein-ball approaches can be tractable only for limited classes of convex losses and costs.

2 Proposed approach

The approach solves a Lagrangian relaxation of Wasserstein distributional robustness by combining adversarial inner optimization with stochastic parameter updates. Smoothness and a sufficiently large penalty make the inner problem strongly concave, enabling convergence guarantees, robustness certificates, and efficient training, while nonsmooth ReLU networks can make worst-case perturbation search NP-hard.

  • Strong concavity: If the loss is smooth in z and γ is at least its smoothness constant L, the penalized inner objective is strongly concave in z.This structure makes the robust surrogate efficiently computable and supports gradient-based optimization.
  • Wasserstein robustness and duality: The method uses a transportation cost and Wasserstein uncertainty set, then replaces prescribed-radius robustness with a Lagrangian penalty problem.The robust surrogate maximizes loss minus γ times the perturbation cost for each data point.
  • Optimization algorithm: Algorithm 1 samples z_t from P0, approximately maximizes the penalized loss over a perturbed example, and updates θ_t using its gradient.The parameter update is projected onto Θ using a stochastic-gradient step.
  • Convergence: For convex losses in θ, the relaxed problem is efficiently solvable, while for nonconvex losses stochastic gradient methods converge to stationary points under sufficient penalty and smoothness conditions.The nonconvex guarantee applies when γ is at least L_zz.
  • Convergence: Approximate inner maximization has a fixed effect on optimization accuracy independent of T, and the method achieves standard smooth nonconvex optimization convergence rates.The stochastic-gradient rate matches that available for standard smooth nonconvex optimization.
  • Limits of tractability: Smoothness is essential: worst-case perturbation search is NP-hard for broad classes of feedforward networks with ReLU activations.Replacing ReLUs with sigmoids or ELUs makes the stated tractability results applicable to deep learning.

3 Certificate of robustness and generalization

The paper derives efficiently computable, data-dependent certificates for worst-case population loss under Wasserstein perturbations and shows that training-set robustness generalizes to test data.

  • Certificate of robustness: The method provides a data-dependent upper bound on worst-case population loss for any robustness level ρ, certifying population robustness.The bound is optimal at the robustness level achieved for the empirical distribution.
  • Generalization: Training-set adversarial perturbations generalize to the test set, with the achieved empirical robustness concentrating around its population counterpart.The result holds uniformly over θ under stated boundedness, Lipschitz, and smoothness assumptions.
  • Certificate of robustness: The empirical worst-case loss certifies robustness to population Wasserstein perturbations up to level bρn.This gives a data-dependent guarantee for the worst-case population loss.
  • Generalization: The guarantees retain the usual ERM-style uniform convergence structure through covering numbers of the model class.For finite-dimensional Θ, the robustness guarantee scales linearly with dimension d.
  • Certificate of robustness: The certificate γρ + E_bPn[φγ(θ; Z)] is efficiently computable and is tightest at the achieved robustness level bρn(θ).The transport mappings and achieved robustness are computable for sufficiently large γ.
  • Generalization: For sufficiently large γ, the transportation map and test loss can be computed efficiently to bound sensitivity to a sample and its predicted labeling.The result applies when the penalty is large enough for the relevant small-ρ bound to be tight.

4 Bounds on smoothness of neural networks

The paper bounds neural-network smoothness by imposing layer-wise Lipschitz assumptions and propagating them through the network, enabling explicit guarantees for smooth-activation models.

  • Network bounds: The network notation composes weight matrices with nonlinear operations, including pooling and activation functions in convolutional networks.The Jacobian JxFl(θ; x) denotes the input Jacobian of the layer mapping.
  • Assumptions: The smoothness analysis assumes each network layer and its Jacobian are Lipschitz with respect to the ℓ2 and operator norms.The assumptions require positive layer Lipschitz constants to exclude degenerate constant-output layers.
  • Examples: For average pooling, the layer satisfies the smoothness assumption with an explicitly bounded L0 determined by the pooling structure.The bound uses minimum and maximum pooling-set sizes and the maximum number of index appearances.
  • Examples: For sigmoid activation, the stated constants are L0 = 1/4 and L1 = 1/10.The first constant follows from the maximum derivative, while the second bounds derivative variation.
  • Examples: For ELU activation with α = 1, the stated smoothness constants are L0 = L1 = 1.These examples provide concrete layer-wise constants for the paper’s smoothness assumptions.
  • Network bounds: A network layer is shown to be αl-Lipschitz, while its input Jacobian is βl-Lipschitz under the layer-wise assumptions.These bounds apply to every layer l = 1, …, L.
  • Classification loss: The resulting softmax-loss analysis bounds the input-gradient Lipschitz constant for classification networks with smooth activations.The paper uses the softmax loss ℓ(θ; (x, y)) = −log p_y(θ; x).

5 Experiments

Experiments compare WRM with ERM and gradient-based adversarial training across synthetic, MNIST, Stanford Dogs, and reinforcement-learning settings. WRM provides certified or empirically stronger robustness in several settings, while its guarantees depend on the smooth-loss regime and sufficiently large γ.

  • 5.1 Visualizing the benefits of certified robustness: WRM, ERM, and FGM produce different synthetic-data classification boundaries, with WRM generally pushing boundaries farther outward.For ELU models, WRM yields an axisymmetric boundary that hedges against perturbations in all directions.
  • 5.1 Visualizing the benefits of certified robustness: The robustness certificate is nearly tight near the achieved training robustness level and provides guarantees for other robustness radii.This comparison is reported for WRM with ELU activations on synthetic data and MNIST.
  • 5.2.1 The MNIST dataset: >99% test-set accuracy is achieved by all MNIST methods at the training robustness levels, while adversarial methods outperform ERM under PGM attacks.WRM offers more robustness than the other evaluated methods under both 2-norm and ∞-norm PGM attacks, despite training with Euclidean cost.
  • 5.2.1 The MNIST dataset: WRM produces the most stable loss surface across adversarial perturbation levels among the evaluated MNIST training methods.Qualitative examples show WRM misclassifications that are consistently reasonable to human observers, unlike the other models with the same consistency.
  • 5.2.2 The Stanford Dogs dataset: On Stanford Dogs, the authors evaluate WRM with both semantic-feature and raw-pixel perturbations, including a large-scale fine-tuning experiment.The raw-pixel experiment fine-tunes the whole ResNet-50 with γ = 1.0 and compares WRM against other adversarial-training baselines.
  • 5.3 Robust Markov decision processes: In cart-pole reinforcement learning, the robust model greatly outperforms the nominal model in harder perturbed environments and learns more efficiently in the original environment.The authors hypothesize that robustness-induced perturbations may encourage better exploration.

6 Discussion and future work

The paper presents distributional robustness as a principled way to efficiently protect models against small perturbations, while identifying substantial limits for large adversarial budgets and current statistical guarantees.

  • 6 Discussion and future work: The method efficiently guarantees distributional robustness through simple adversarial data perturbations, using only smoothness assumptions on the loss.The authors emphasize simplicity and applicability across models and machine-learning scenarios.
  • 6 Discussion and future work: Empirical evaluations show that the method matches or outperforms less-principled adversarial training techniques.The paper frames this result as applying to the perturbation settings evaluated in its experiments.
  • 6 Discussion and future work: Theoretical guarantees are limited because the optimization result applies only to small robustness levels and a limited class of Wasserstein costs.The statistical guarantees rely on infinity-norm covering numbers, which can become prohibitively large for deep networks.
  • 6 Discussion and future work: The work focuses on small-perturbation attacks; for large adversarial budgets, the method becomes another heuristic and certifiably secure training remains an open question.The paper also notes that large-budget attacks can make perturbations perceptible or target critical image regions.
  • 6 Discussion and future work: Figure 9 compares test misclassification error across FGM and IFGM attacks, Euclidean and infinity norms, and adversarial perturbation levels.The vertical bars mark the training perturbation level and estimated radius in selected panels.
  • 6 Discussion and future work: WRM’s gradient-based misclassifications are consistently reasonable to humans, unlike those of other models in the comparison.The paper connects these reasonable misclassifications with learned representations whose gradients are interpretable.

A.3 MNIST Experiments with varied γ

The experiment varies WRM’s training penalty while evaluating every model against a fixed adversary, revealing smooth degradation beyond the training budget and diminishing gains at smaller penalties.

  • A.3 MNIST Experiments with varied γ: Performance degradation remains smooth even when the evaluation adversary has more budget than the adversary used during training.This behavior is consistent with the bound using η = γ.
  • A.3 MNIST Experiments with varied γ: Decreasing γ produces diminishing gains in achieved robustness, measured by test error against the fixed γadv adversary.The paper relates this pattern to the inner problem becoming inefficiently computable for small γ.
  • A.3 MNIST Experiments with varied γ: Figure 11 evaluates stability and test error for WRM models trained with various γ values against a fixed adversary γadv.The fixed adversary is indicated by a vertical bar in the figure.

A.4 MNIST experiments with a larger adversarial budget

With larger adversarial budgets, WRM loses its formal guarantees once the inner problem is no longer strongly concave, and its advantage over heuristic methods becomes less consistent. WRM remains competitive for imperceptible attacks but performs worse against large perturbations.

  • Guarantee regime: For over 10% of the data, the inner supremum is no longer strongly concave, so WRM no longer has performance guarantees.At large desired robustness values, the method becomes heuristic like the other approaches.
  • Small training budget: In the small-budget regime, WRM matches the performance of other adversarial-training techniques.This regime corresponds to large γ and small ǫ.
  • Large training budget: With a large training budget, WRM outperforms heuristic methods against imperceptible Euclidean- and ∞-norm attacks.The comparison is reported for both attack norms.
  • Large training budget: WRM also outperforms the heuristics on natural images, indicating a smaller price of robustness.This result is presented as consistent with its performance on imperceptible attacks.
  • Large training budget: Against large adversarial budgets, WRM performs worse than the other methods, especially for ∞-norm attacks.Figures compare test misclassification error across perturbation levels and attack methods.

A.6 MNIST experiments when γ is chosen according to Section 4

The MNIST experiments examine whether WRM can simultaneously retain clean accuracy, achieve appreciable robustness, and use γ above the theoretical bound. The results show a trade-off: robustness and clean accuracy are difficult to obtain together under the stated constraint.

  • Experimental setup: The chosen MNIST architecture cannot easily achieve all three goals: γ above Corollary 4’s bound, benchmark-level clean accuracy, and a noticeable difference between WRM and ERM.The benchmark target is less than 10% test error on clean MNIST data.
  • Regularization: Weight regularization lowers the Corollary 4 bound, with stronger regularization applied to earlier network layers.The bound scales exponentially with the depth-weighted norms of earlier-layer weights.
  • Trade-off: High clean accuracy and appreciable adversarial robustness occur at the expense of γ < γ̄.For γ ≳ γ̄, clean accuracy remains high but robustness resembles ERM.
  • Trade-off: For the most regularized models, large γ yields appreciable robustness, but regularization is too heavy to preserve good clean-data performance.This describes the strongest regularization setting in Table 5.

B.2 Proof of Lemma 1

The proof establishes regularity of the optimized inner objective and then uses approximate inner maximizers with stochastic gradient updates. It also connects the relevant decision and optimization formulations to NP-hardness.

  • Inner optimizer regularity: Strong convexity makes the optimizer z⋆(θ) unique and supports a Lipschitz dependence of z⋆ on θ.The proof derives the dependence by combining strong-convexity inequalities with Hölder’s inequality.
  • Differentiability: Under continuity and inf-compactness assumptions, the optimized objective is directionally differentiable and has gradient ∇f̄(θ) = gθ(θ, z⋆(θ)).Uniqueness of the inner optimizer permits the envelope-style argument.
  • Stochastic updates: The stochastic method uses an ε-approximate inner maximizer to form gradient steps, with errors measured relative to ∇θφγ(θt; zt).The analysis tracks the potentially biased errors introduced by approximate inner optimization.
  • Stochastic updates: When γ exceeds the smoothness constant Lzz, the inner objective is strongly concave, enabling the progress analysis for the stochastic updates.The proof uses λ = γ − Lzz as the strong-concavity parameter.
  • Complexity: The associated decision problem reduces to the optimization problem, while 3-SAT reduces to the decision problem, making the optimization problem NP-hard.The decision problem has polynomially verifiable certificates, and one optimization-oracle call solves it.

B.5 Proof of Theorem 3

The theorem proof first derives a deterministic distributionally robust bound from duality, then controls empirical-to-population deviation using concentration and complexity arguments. Substituting the empirical robustness radius yields the stated high-probability result.

  • Duality bound: Strong duality provides a deterministic bound relating the distributionally robust objective to the penalized surrogate for every ρ, distribution Q, and γ.This is the starting point for both theorem bounds.
  • Statistical control: The empirical expectation of the robust surrogate concentrates around its population counterpart at the usual rate.The proof invokes bounded differences, Rademacher complexity, and entropy-integral arguments.
  • High-probability guarantee: Substituting the empirical robustness radius into the deterministic bound gives the second result with probability at least 1 − e^-t.The final step uses strong duality again.

B.7 Proof of Theorem 4

The proof establishes attainment and concentration properties for the worst-case distribution, then derives smoothness and efficient proximal updates for adversarial perturbations.

  • B.7 Proof of Theorem 4: P ∗ is attained for all P0 under the stated compactness and continuity conditions.The argument uses uniform tightness, Prohorov’s theorem, Wasserstein continuity, and monotone convergence.
  • B.7 Proof of Theorem 4: The transportation map is unique, well-defined, and smooth in θ when γ > Lzz.These properties support the subsequent representation of worst-case expectations and concentration analysis.
  • B.7 Proof of Theorem 4: A covering argument combined with Lipschitz bounds, Hoeffding’s inequality, and a union bound yields the desired uniform concentration result.The proof treats cases where the transport cost or loss is Lipschitz in the relevant argument.
  • B.7 Proof of Theorem 4: For ∥·∥∞ perturbations, the adversarial objective is written as a penalized maximization of ℓ(θ; z) − γc(z, z0), with c determined by the norm penalty.The resulting surrogate loss is φγ(θ; z0) = supz∈Z{ℓ(θ; z) − γc(z, z0)}.
  • B.7 Proof of Theorem 4: The proximal algorithm alternates a gradient step for the smooth loss with a proximal step for the non-smooth penalty.The proximal update can be computed efficiently by sorting the coordinatewise deviations from z0.
  • B.7 Proof of Theorem 4: Unlike iterated fast sign gradients, the update moves toward the sign of zt + λt∇f(zt) − z0 and is modulated by βt.This update accounts for the perturbation relative to the natural example rather than using only the loss gradient’s sign.

C.1 Proof of Proposition 7

The proposition proves the closed-form proximal update by reducing its optimality conditions to a scalar equation involving sorted coordinate deviations.

  • C.1 Proof of Proposition 7: The proof uses Moreau decomposition and Fenchel conjugacy to characterize the proximal solution.It introduces the conjugate of a convex lower semi-continuous function and reduces the update to a condition on the transformed variable.
  • C.1 Proof of Proposition 7: Sorting |w − z0| into a decreasing vector v reduces the remaining characterization to a scalar equation for β.The proof then invokes an elementary lemma for nonzero nonnegative vectors with decreasing coordinates.
  • C.1 Proof of Proposition 7: The scalar equation has a solution β′ in (0, ∥v∥∞), obtained from monotonicity and a sign change of the defining function.A threshold index j′ is selected so that vj′ > β′ ≥ vj′+1.
  • C.1 Proof of Proposition 7: The resulting candidate satisfies the optimality condition, establishing the claimed proximal update.The proof concludes by identifying β′ with β⋆ and applying the preceding lemma.
Loading 1710.10571v5…