PaperlayerView exact revision on arXiv

Source-linked AI summary

Theoretically Principled Trade-off between Robustness and Accuracy

Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, Michael I. Jordan

arXiv:1901.08573v3cs.LGstat.ML

TL;DR

The theory behind the robustness–accuracy trade-off in adversarial defense remains incomplete. This paper tightly bounds robust error using natural and boundary errors, derives TRADES, and reports state-of-the-art performance across threat models, including a NeurIPS 2018 challenge win.

  • Problem

    Theoretical treatment of the trade-off between adversarial robustness and natural accuracy, including surrogate-loss tightness, remains limited.

  • Method

    The paper decomposes robust error into natural and boundary errors, derives a tight differentiable surrogate upper bound, and minimizes it through TRADES.

  • Results

    TRADES outperforms state-of-the-art methods under black-box and white-box threat models and wins the NeurIPS 2018 Adversarial Vision Challenge.

  • Takeaways & Limitations

    The analysis supports regularized surrogate-loss defense design that explicitly balances natural and robust errors while providing theoretical guarantees.

  • Takeaways & Limitations

    The analysis studies population risk functions and leaves finite-sample generalization analysis for future work.

Abstract

from arXiv · show

We identify a trade-off between robustness and accuracy that serves as a guiding principle in the design of defenses against adversarial examples. Although this problem has been widely studied empirically, much remains unknown concerning the theory underlying this trade-off. In this work, we decompose the prediction error for adversarial examples (robust error) as the sum of the natural (classification) error and boundary error, and provide a differentiable upper bound using the theory of classification-calibrated loss, which is shown to be the tightest possible upper bound uniform over all probability distributions and measurable predictors. Inspired by our theoretical analysis, we also design a new defense method, TRADES, to trade adversarial robustness off against accuracy. Our proposed algorithm performs well experimentally in real-world datasets. The methodology is the foundation of our entry to the NeurIPS 2018 Adversarial Vision Challenge in which we won the 1st place out of ~2,000 submissions, surpassing the runner-up approach by $11.41\%$ in terms of mean $\ell_2$ perturbation distance.

1 Introduction

The paper addresses the unresolved trade-off between adversarial robustness and natural accuracy by decomposing robust error into natural and boundary error. This analysis motivates TRADES, a regularized surrogate-loss defense that achieves strong empirical results, including first place in the NeurIPS 2018 Adversarial Vision Challenge.

  • Motivation: Adversarial defense remains challenging because robust classification’s robust 0-1 loss is NP-hard to optimize even when ϵ = 0, motivating surrogate losses.Existing provable defenses can ignore performance on non-adversarial examples, leaving the robustness–accuracy trade-off theoretically unresolved.
  • Theoretical contribution: Robust error decomposes into natural error and boundary error, yielding differentiable upper bounds that are tightest uniformly over probability distributions and measurable predictors.The boundary error measures how likely inputs are close to the ϵ-extension of the decision boundary.
  • Algorithmic contribution: TRADES optimizes a regularized surrogate loss whose empirical-risk term promotes natural accuracy while its regularizer pushes the decision boundary away from data to improve robustness.The formulation is inspired directly by the theoretical decomposition of robust error.
  • Experimental contribution: The proposed algorithm outperforms state-of-the-art methods under both black-box and white-box threat models and wins the NeurIPS 2018 Adversarial Vision Challenge.The methodology won first place out of ~2,000 submissions, surpassing the runner-up by 11.41% in mean ℓ2 perturbation distance.

2 Preliminaries

The preliminaries define natural, robust, and boundary errors for binary classification, establish their relationship, and motivate surrogate-loss bounds for trading robustness against accuracy. A toy example illustrates that classifiers optimizing natural and robust error can differ, while classification-calibrated losses provide the analytical framework for tractable bounds.

  • Error Definitions: Robust error requires a misclassification within an ϵ-ball, whereas natural error evaluates only the unperturbed instance; thus Rrob(f) ≥ Rnat(f), with equality when ϵ = 0.These quantities are defined under a bounded-ϵ threat model for score functions f: X → R.
  • Error Definitions: Boundary error counts correctly classified instances lying within ϵ of the classifier’s decision boundary and contributes to the robust-error decomposition.The boundary error is defined as Rbdy(f) := E1{X ∈ B(DB(f), ϵ), f(X)Y > 0}.
  • Robustness–Accuracy Trade-off: In the toy example, the Bayes optimal classifier achieves minimal natural error but large robust error, while the all-one classifier achieves optimal robust error but large natural error.The example uses a uniform instance distribution over [0, 1] and compares the Bayes rule with a classifier that always predicts positive.
  • Surrogate-Loss Framework: The proposed goal is to introduce weights favoring natural or boundary error and derive tight differentiable upper bounds using classification-calibrated surrogate losses.The motivation is computational: direct minimization of the 0-1 losses in natural and robust error is intractable.
  • Surrogate-Loss Framework: Classification calibration requires that predictions with a sign inconsistent with the Bayes rule incur strictly larger surrogate risk whenever η ≠ 1/2.Examples include hinge, sigmoid, exponential, and logistic losses.
  • Surrogate-Loss Framework: The ψ-transform is the largest convex lower bound on the relevant conditional risk gap and is non-decreasing, continuous, convex, and zero at 0.These properties support bounding excess robust error through the surrogate-loss framework.

3 Relating 0-1 loss to Surrogate Loss

This section develops theoretical guarantees for binary classification by relating robust error to surrogate-loss minimization and decision-boundary effects. Under additional loss conditions, the resulting upper bound is tight up to an arbitrarily small constant.

  • Surrogate-loss guarantee: The analysis guarantees performance for surrogate-loss minimization when using a classification-calibrated loss.The result is stated under conditions including Assumption 1 and applies to measurable predictors and probability distributions.
  • Decision-boundary effect: Adversarial vulnerability is governed by the probability that correctly classified data lie within an ε-neighborhood of the model’s decision boundary.Small perturbations can move such points across the boundary and cause misclassification.
  • Tightness: The lower bound matches the Section 3.1 upper-bound analysis up to an arbitrarily small constant.The additional limiting condition holds for all losses listed in Table 2.
  • Tightness: Theorem 3.2 shows that the upper bound is tight when the non-negative loss satisfies limx→+∞φ(x) = 0.The theorem assumes |X| ≥2, Assumption 1, ξ > 0, and θ ∈[0, 1].

4 Algorithmic Design for Defenses

The section develops TRADES by combining natural-error minimization with a robustness regularizer based on prediction differences between clean and adversarial examples. It extends the formulation to multiclass and semi-supervised settings and compares its theoretically motivated optimization with prior defenses.

  • Optimization: TRADES minimizes natural loss plus a robustness regularizer measuring the prediction difference between f(X) and adversarial f(X′).The adversarial example is selected by maximizing the calibrated loss within the perturbation set, scaled by λ.
  • Optimization: TRADES is named as the proposed tradeoff-inspired adversarial defense via surrogate-loss minimization.
  • Differences with Adversarial Logit Pairing: Unlike ALP, TRADES generates adversarial examples by solving its inner maximization and uses a classification-calibrated loss with theoretical guarantees.ALP instead simulates examples with FGSMk and uses an ℓ2 loss between f(X) and f(X′) without theoretical guarantees.
  • Heuristic algorithm: The multiclass extension replaces φ with a multiclass calibrated loss, such as cross-entropy, and approximately solves the minimax problem by alternating gradient descent.The empirical formulation uses model output vectors, label-indicator vectors, and a positive regularization parameter λ.
  • Semi-supervised learning: TRADES can be applied to semi-supervised learning because its robustness term does not depend on labels, allowing additional unlabeled data to improve its empirical approximation.

5 Experimental Results

Experiments verify TRADES’s theoretical upper-bound tightness and its predicted robustness–accuracy trade-off across MNIST and CIFAR10. Comparisons under white-box and black-box attacks, plus the adversarial competition, demonstrate strong empirical robustness and a first-place result.

  • Hyperparameter sensitivity: As 1/λ increases, natural accuracy decreases while robust accuracy increases on MNIST and CIFAR10, confirming the predicted robustness–accuracy trade-off.The natural-accuracy decline is smaller on MNIST than CIFAR10, which the paper attributes probably to MNIST’s easier classification task.
  • White-box and black-box robustness: TRADES significantly improves robust accuracy under white-box attacks in comparisons with prior defense models.The evaluation covers MNIST and CIFAR10 and uses FGSMk attacks with 40 iterations on MNIST and 20 iterations on CIFAR10.
  • White-box and black-box robustness: Black-box evaluations on MNIST and CIFAR10 compare defense models using two source models and report results in Tables 6 and 7.The attacks use ε = 0.3 with 40 iterations on MNIST and ε = 0.031 with 20 iterations on CIFAR10.
  • Adversarial competition: 1st place: the competition entry surpassed the runner-up by 11.41% in mean ℓ2 perturbation distance.The entry applied the paper’s methodology to train ResNet models in the black-box Tiny ImageNet competition.

6 Conclusions … B.1 Proof of Theorem 3.1

The paper concludes that its robustness–accuracy analysis yields a tight worst-case bound motivating TRADES, while related work and proof sections position and establish the main results.

  • 6 Conclusions: The paper studies adversarial defenses for structural perturbations and the trade-off between robustness and accuracy.It bounds the gap between robust error and optimal natural error.
  • 6 Conclusions: TRADES is motivated as a regularized surrogate loss for adversarial training by the paper’s robustness–accuracy bounds.Experiments on real datasets and an adversarial competition demonstrate the proposed algorithms’ effectiveness.
  • A Other Related Works: Adversarial attacks include FGSM, its multi-step FGSMk or PGD extension, black-box adaptations, MI-FGSM, and LBFGS attacks.FGSM and FGSMk approximately solve linearized maximization problems, while iterative attacks can be adapted to black-box settings using a similar white-box network.
  • A Other Related Works: Prior robust-optimization defenses train networks on adversarial examples but lack theoretical guarantees and do not consider the accuracy–robustness trade-off.One-step and multi-step methods instantiate the inner maximization framework.
  • A Other Related Works: Relaxation-based defenses address difficult nonconvex inner maximization through convex outer approximations of reachable activation sets.These methods progressed from one-hidden-layer networks toward larger models and tighter approximations.
  • A Other Related Works: Theoretical work studies robustness bounds, computational hardness, robust-training sample complexity, and uniform convergence of adversarial error.The cited literature also examines the existence of robustness–accuracy trade-offs.
  • B Proofs of Main Results: The proofs section establishes the paper’s main results, including Theorem 3.1 under a nonnegative loss with φ(0) ≥1 and Assumption 1.The theorem applies to any measurable predictor, probability distribution, and λ > 0.
  • B.1 Proof of Theorem 3.1: Theorem 3.1’s proof derives inequalities using an adversarial-ball expectation and classification-calibrated loss, with the final step yielding the stated second inequality.The proof explicitly attributes the first inequality’s final bound to choosing φ as a classification-calibrated loss.

B.2 Proof of Theorem 3.2 · C Extra Theoretical Results

Theorem 3.2 is proved by constructing a two-point distribution and classifier under specified loss and regularization conditions, while Section C introduces additional theoretical results for adversarial defenses.

  • B.2 Proof of Theorem 3.2: The adversarial loss term is bounded by E max X′∈B(X,ϵ) φ(f(X′)f(X)/λ).The supplied proof excerpt also states that this quantity can be made smaller than ϵ′.
  • B.2 Proof of Theorem 3.2: Under Assumption 1 and |X| ≥ 2, Theorem 3.2 asserts the existence of a probability distribution, function f, and λ > 0 for admissible φ, ξ, and θ.The theorem applies to any non-negative loss φ with φ(x) → 0 as x → +∞, any ξ > 0, and θ ∈ [0, 1].
  • B.2 Proof of Theorem 3.2: The proof reduces the result to establishing the theorem’s second inequality, because the first follows directly from Theorem 3.1.This reduction is stated explicitly at the start of the proof.
  • B.2 Proof of Theorem 3.2: The construction represents θ as γα1 + (1 − γ)α2 and selects two distinct points with probabilities γ and 1 − γ.The parameters γ, α1, and α2 lie in [0, 1], and the construction uses continuity of ψ to obtain the required approximation.
  • B.2 Proof of Theorem 3.2: The constructed classifier f is negative on all data points and approximately minimizes conditional risks at the two selected points.The proof chooses f so that each conditional risk is within ϵ/3 of the corresponding H− value.
  • C Extra Theoretical Results: Section C states that it provides extra theoretical results concerning adversarial defenses.No specific result from that section is included in the supplied passage.

C.1 Adversarial vulnerability under log-concave distributions … D.1 Experimental setup in Section 5.3.1

The appendix establishes that linear classifiers minimize adversarial boundary vulnerability under products of log-concave measures, derives related generalization and decomposition results, and details supplementary TRADES experiments. The experiments standardize architectures and training settings while using stronger multi-step adversarial examples for regularization.

  • C.1 Adversarial vulnerability under log-concave distributions: Under products of log-concave measures, linear classifiers minimize boundary-neighborhood mass among balanced classifiers.The result applies to distributions including Gaussian and uniform measures over balls.
  • C.1 Adversarial vulnerability under log-concave distributions: Theorem C.1 shows adversarial boundary-neighborhood mass grows at least Ω(ϵ), with the linear classifier achieving the minimum.A linear classifier under a product Gaussian measure with mean 0 and variance 1/(2π) achieves the lower bound.
  • C.1.1 Proofs of Theorem C.1: The proof applies a log-concave isoperimetric inequality to the positive-class event, comparing arbitrary classifiers with the halfspace represented by a linear classifier.For balanced sets, the halfspace [0, ∞) × R^(d−1) solves the isoperimetric problem under the Gaussian comparison measure.
  • C.2 Margin based generalization bounds: The appendix derives a robust generalization bound for norm-constrained linear classifiers using margin-based lemmas and structural risk minimization.Algorithm 2 searches across margin parameters by solving minimax optimization problems.
  • C.3 A lemma: Lemma C.6 decomposes conditional robust error into probabilities of adversarial sign changes weighted by the conditional label probability η(x) and its complement.The decomposition distinguishes attacks that change predictions from positive and negative labels.
  • D Extra Experimental Results: Additional experiments evaluate the effectiveness of the proposed TRADES method.These results are presented as extra experimental verification.
  • D.1 Experimental setup in Section 5.3.1: The supplementary comparison uses WRN-34-10 with the same batch size and learning rate across methods, while replacing one-step regularization attacks with FGSMk cross-entropy examples.The authors report that FGSM regularization cannot defend against FGSMk white-box attacks; Table 5 combines reimplemented, author-provided, and previously reported models.

D.2 Extra attack results in Section 5.3.1

This section provides extra white-box attack results for TRADES, covering multiple attack methods listed across Tables 5 and 8.

  • Extra white-box attack results for TRADES are provided in Table 8.
  • The reported attacks include FGSMk, DeepFool (ℓ∞), LBFGSAttack, MI-FGSM, C&W, FGSM, and DeepFool (ℓ2).

D.3 Extra attack results in Section 5.3.2

The section reports extra black-box FGSM attack results for TRADES and prior defense models on MNIST and CIFAR10, presented in Tables 9 and 10. The comparisons identify parenthesized source models that provide gradients to attackers.

  • Extra black-box attack results: Tables 9 and 10 present extra black-box FGSM attack comparisons between TRADES and prior defense models.The results are organized by dataset and attack setting.
  • MNIST: The black-box FGSM attack is evaluated on the MNIST dataset.
  • CIFAR10: The black-box FGSM attack is evaluated on the CIFAR10 dataset.
  • Attack setup: Models shown inside parentheses are source models that provide gradients to adversarial attackers.

D.4 Experimental setup in Section 5.3.2 · D.5 Interpretability of the robust models trained by TRADES · D.5.1 Adversarial examples on MNIST and CIFAR10 datasets

The setup evaluates Madry’s MNIST and CIFAR10 models with FGSM20, while the interpretability section generates smallest-ℓ∞ adversarial perturbations for Natural, Madry’s, and TRADES models using Foolbox.

  • D.4 Experimental setup in Section 5.3.2: 96.01% is the robust accuracy of [MMS+18]’s CNN model on MNIST.The evaluation uses FGSM20, the same white-box attack introduced in Section 5.3.1.
  • D.4 Experimental setup in Section 5.3.2: 47.66% is the robust accuracy of [MMS+18]’s WRN-34-10 model on CIFAR10.The evaluation uses FGSM20, the same white-box attack introduced in Section 5.3.1.
  • D.5 Interpretability of the robust models trained by TRADES: The MNIST and CIFAR10 examples are adversarial examples generated for interpretability analysis.The section provides adversarial examples on both datasets.
  • D.5.1 Adversarial examples on MNIST and CIFAR10 datasets: Foolbox3 [RBB17] generates adversarial examples with the smallest perturbations under the ℓ∞norm distance.This identifies the implementation used to construct the examples.
  • D.5.1 Adversarial examples on MNIST and CIFAR10 datasets: FGSMk is the white-box attack used to generate examples on the Natural, Madry’s, and TRADES models described in Section 5.The attack is applied across the models included in the paper’s Section 5 experiments.
  • D.5.1 Adversarial examples on MNIST and CIFAR10 datasets: In Foolbox, FGSMk corresponds to foolbox.attacks.LinfinityBasicIterativeAttack.The passage specifies the exact Foolbox attack implementation.

D.5.2 Adversarial examples on Bird-or-Bicycle dataset

A spatial-transformation-invariant variant of TRADES was applied to ResNet-50 models on the unrestricted bird-or-bicycle dataset. Boundary-attack adversarial images around the robust model’s decision boundary contained features of both classes while remaining correctly classified.

  • The bird-or-bicycle dataset contains 30,000 224 × 224 pixel images labeled either ‘bird’ or ‘bicycle’.
  • A spatial-transformation-invariant variant of TRADES trained robust ResNet-50 models against unrestricted adversarial examples involving structural perturbations and spatial transformations.The listed threat models include rotations, translations, and resizing.
  • Boundary attack with random spatial transformation generated adversarial images near the robust model’s decision boundary.Boundary attack is a black-box method that searches for data points near the decision boundary.
  • Adversarial images around the decision boundary of the robust model had features of both ‘bird’ and ‘bicycle’.
  • The robust model correctly recognized adversarial examples whose ground-truth labels were ‘bicycle’ or ‘bird’, despite visible features of the opposite class.
Loading 1901.08573v3…