PaperlayerView exact revision on arXiv

Source-linked AI summary

Rademacher Complexity for Adversarially Robust Generalization

Dong Yin, Kannan Ramchandran, Peter Bartlett

arXiv:1810.11914v4cs.LGcs.CRcs.NEstat.ML

TL;DR

Adversarial training can achieve low training error while adversarial test error remains large, motivating a theory of robust generalization. This paper analyzes ℓ∞ attacks using Rademacher complexity and finds dimension dependence across linear classifiers and neural networks, while ℓ1 constraints can remove it in a surrogate ReLU setting.

  • Problem

    Adversarial test error can remain large even when adversarial training error is minimized, leaving robust generalization for deep neural networks insufficiently understood.

  • Method

    The paper studies ℓ∞ adversarially robust generalization through Rademacher complexity for binary and multi-class linear classifiers and nonlinear feedforward neural networks.

  • Results

    The analysis proves tight bounds for binary linear classifiers, extends results to multi-class classifiers, establishes dimension-dependent neural-network bounds, and derives surrogate-loss margin bounds for one-hidden-layer ReLU networks.

  • Takeaways & Limitations

    Bounding ℓ1 norms of linear weights or neural-network weight matrices may improve adversarial generalization by avoiding explicit dimension dependence in the supported settings.

  • Takeaways & Limitations

    The stated guarantees are scoped to norm-constrained hypothesis classes and, for the dimension-independent surrogate margin result, a one-hidden-layer ReLU setting.

Abstract

from arXiv · show

Many machine learning models are vulnerable to adversarial attacks; for example, adding adversarial perturbations that are imperceptible to humans can often make machine learning models produce wrong predictions with high confidence. Moreover, although we may obtain robust models on the training dataset via adversarial training, in some problems the learned models cannot generalize well to the test data. In this paper, we focus on $\ell_\infty$ attacks, and study the adversarially robust generalization problem through the lens of Rademacher complexity. For binary linear classifiers, we prove tight bounds for the adversarial Rademacher complexity, and show that the adversarial Rademacher complexity is never smaller than its natural counterpart, and it has an unavoidable dimension dependence, unless the weight vector has bounded $\ell_1$ norm. The results also extend to multi-class linear classifiers. For (nonlinear) neural networks, we show that the dimension dependence in the adversarial Rademacher complexity also exists. We further consider a surrogate adversarial loss for one-hidden layer ReLU network and prove margin bounds for this setting. Our results indicate that having $\ell_1$ norm constraints on the weight matrices might be a potential way to improve generalization in the adversarial setting. We demonstrate experimental results that validate our theoretical findings.

1 Introduction

The paper studies why adversarially trained models may generalize poorly under ℓ∞ attacks, using Rademacher complexity across linear classifiers and neural networks.

  • Adversarial examples can induce high-confidence errors through perturbations that are often imperceptible to humans.
  • Adversarial training minimizes adversarial loss through robust optimization, but low adversarial training error does not ensure low adversarial test error.
  • The paper analyzes adversarially robust generalization for ℓ∞ attacks using Rademacher complexity in binary and multi-class linear classifiers and neural networks.
  • For linear classifiers, adversarial Rademacher complexity is never smaller than its natural counterpart and has polynomial dimension dependence unless relevant weight vectors have bounded ℓ1 norm.
  • For one-hidden-layer ReLU networks, surrogate adversarial-loss margin bounds avoid explicit dimension dependence when the first-layer weight matrix has bounded ℓ1 norm.
  • Experiments support that ℓ1 regularization can reduce adversarial generalization error, while the adversarial generalization gap increases with feature-space dimension.

2 Related Work

Related work studies adversarial generalization, robust defenses, and neural-network generalization; this paper distinguishes its lower bounds, multi-class analysis, and SDP-based surrogate-loss approach.

  • Khim and Loh provide a similar binary-classification upper bound, whereas this paper adds a matching lower bound and neural-network lower bounds.
  • This paper analyzes multi-class generalization bounds, while Khim and Loh focus only on binary classification.
  • Both works use surrogate adversarial losses, but this paper uses SDP relaxation while Khim and Loh use tree transform, making direct comparison difficult.
  • Prior work reports adversarial generalization gaps, including a Θ(d) sample requirement for separated d-dimensional spherical Gaussians under adversarial perturbations.
  • VC-dimension need not increase under adversarial attacks, while Rademacher complexity can provide tighter norm- and data-dependent bounds.
  • Provable-defense analyses using SDP or LP relaxations typically construct efficiently optimized upper bounds on adversarial risk without generalization guarantees.

3 Problem Setup

The setup defines natural and adversarial risks over bounded loss classes, then uses Rademacher complexity to control uniform convergence under ℓ∞ perturbations.

  • The learning problem minimizes population risk for hypotheses composed with a bounded loss over an unknown distribution D on feature-label pairs.
  • Generalization error is the gap between empirical risk on n i.i.d. training examples and population risk.
  • Rademacher complexity is defined from randomized sign-weighted evaluations of a function class on a sample.
  • The standard generalization theorem connects population and empirical risks uniformly over the hypothesis class through empirical Rademacher complexity.
  • Rademacher complexity measures the uniform convergence rate and can tightly bound generalization for a loss function class.
  • Under an ℓ∞ attack, the learner trains on uncorrupted samples while an adversary perturbs each input within an ℓ∞ ball to maximize loss.
  • The adversarial loss maximizes the original loss over the perturbation ball, and its function-class Rademacher complexity controls adversarial generalization.

4 Linear Classifiers

The paper analyzes adversarially robust generalization for binary and multi-class linear classifiers under ℓ∞ attacks using adversarial Rademacher complexity and margin bounds. It shows that adversarial complexity can exceed natural complexity and often has dimension dependence, while ℓ1 constraints can avoid that dependence in binary classification.

  • Binary Classification: The binary-classifier hypothesis class uses linear scores fw(x) = ⟨w, x⟩ with an ℓp norm constraint on w.The loss is represented as a nonincreasing Lipschitz function of the signed margin y⟨w, x⟩.
  • Binary Classification: Adversarial losses maximize the loss over an ℓ∞ ball around each input, and their Rademacher complexity is bounded through the corresponding adversarial function class.The contraction inequality relates the loss-class complexity to the complexity of the underlying function class.
  • Binary Classification: Theorem 2 compares natural and adversarial Rademacher complexities for ℓp-constrained linear predictors under ℓ∞ attacks.The theorem is identified as the paper’s first major result.
  • Binary Classification: Adversarial Rademacher complexity is always at least as large as natural Rademacher complexity, making adversarial uniform convergence at least as hard.The natural complexity depends on the data distribution and norm constraint without explicit dimension dependence.
  • Binary Classification: When p > 1, adversarial Rademacher complexity has unavoidable polynomial dependence on dimension d; bounded ℓ1 norm can avoid this dependence.The result gives a dimension-sensitive contrast between adversarial and natural complexity.
  • Multi-class Classification: For multi-class classifiers, scores are vectors in R^K, prediction selects the highest-scoring class, and the margin is the correct-class score minus the largest competing score.The ramp loss applies to this multi-class margin, and both natural and adversarial generalization bounds are stated.
  • Multi-class Linear Classifiers: For multi-class linear classifiers, the adversarial margin bound has explicit polynomial dependence on d when p > 1, whereas the natural bound has no dimension dependence.The paper concludes that this dimension dependence also appears in multi-class classification.

5 Neural Networks

The paper shows that ℓ∞ adversarial attacks introduce explicit dimension dependence into Rademacher complexity for neural networks, contrasting with logarithmic natural-setting dependence. It also derives surrogate-loss margin bounds whose dimension dependence can disappear under an ℓ1 constraint on the first-layer weight matrix.

  • 5.1 Comparison of Rademacher Complexity Bounds: Neural-network adversarial Rademacher complexity has an explicit dimension-dependent lower bound, unlike natural-setting bounds with only logarithmic dimension dependence.This effect arises even when weight-matrix norms are bounded and is attributed to the ℓ∞ attack.
  • 5.1 Comparison of Rademacher Complexity Bounds: For binary classification, the adversarial loss is expressed as a monotone loss applied to the worst-case signed margin over the ℓ∞ perturbation set.The robust loss uses min x′∈B∞(x, ϵ) yfW(x′) inside the loss function.
  • 5.2 Generalization Bound for Surrogate Adversarial Loss: The paper studies an SDP-based surrogate adversarial loss for one-hidden-layer ReLU networks because directly evaluating the adversarial loss can require maximizing a non-concave function.The surrogate is designed to upper-bound the adversarial loss for all inputs, labels, and weights.
  • 5.2 Generalization Bound for Surrogate Adversarial Loss: The surrogate-loss analysis uses a ramp loss composed with the multiclass margin operator and derives a margin bound for the resulting hypothesis class.The framework considers fW(x)=W2ρ(W1x) with one hidden layer and multiclass outputs.
  • 5.2 Generalization Bound for Surrogate Adversarial Loss: With bounded ℓ1 norm on the first-layer matrix, the surrogate adversarial-loss generalization bound has no explicit dimension dependence.This condition is identified as a potential way to improve adversarial generalization.

6 Experiments

Experiments on MNIST test the theory for linear classifiers and ReLU neural networks. They find lower adversarial generalization error with stronger ℓ1 regularization and larger error gaps at higher feature dimensions.

  • 6 Experiments: MNIST experiments evaluate the theoretical findings using adversarial training for multiclass linear classifiers and ReLU neural networks.The neural-network experiment uses a four-layer ReLU model and PGD attacks.
  • 6.1 Linear Classifiers: Increasing λ decreases the adversarial generalization gap for linear classifiers, supporting the usefulness of ℓ1 regularization.Each (ϵ, λ) pair was evaluated across 10 independent training runs.
  • 6.1 Linear Classifiers: Figure 1 plots adversarial generalization error against ℓ∞ perturbation ϵ and regularization coefficient λ for linear classifiers.The reported trend is that larger λ reduces the generalization gap.
  • 6.1 Linear Classifiers: When λ=0, the adversarial generalization gap increases with feature dimension d across MNIST representations.The compared dimensions are d=196, d=784, and d=3136, with image ℓ2 norms kept equal.
  • 6.2 Neural Networks: Figure 3 reports adversarial generalization errors against λ for the ReLU neural-network experiment under PGD attack.The experiment tests ℓ1-regularized adversarial training on MNIST.

7 Conclusions

The paper analyzes adversarially robust generalization through Rademacher complexity for linear classifiers and neural networks. Its results identify dimension dependence under ℓ∞ attacks and point to ℓ1 constraints as a possible mitigation.

  • 7 Conclusions: Tight adversarial Rademacher-complexity bounds show that adversarial complexity is never smaller than natural complexity for binary linear classifiers.Polynomial dimension dependence is unavoidable under bounded ℓp weights unless p=1.
  • 7 Conclusions: Neural-network adversarial Rademacher complexity also has unavoidable dimension dependence under ℓ∞ attacks.The paper additionally proves margin bounds for a surrogate adversarial loss in one-hidden-layer ReLU networks.
  • 7 Conclusions: The results indicate that ℓ1 norm constraints on weight vectors or matrices might improve adversarial generalization.The experiments validate the theoretical findings.

A Proof of Theorem 2

This proof analyzes the adversarial signed margin of binary linear classifiers over an ℓ∞ perturbation set. It uses symmetry, sign alignment, triangle inequality, and Khintchine’s inequality to establish complexity bounds.

  • A Proof of Theorem 2: The adversarial signed margin is defined by minimizing y⟨w,x′⟩ over x′ in the ℓ∞ perturbation set.For y=−1, the expression is equivalently represented using a maximum over the perturbation set.
  • A Proof of Theorem 2: The supremum over weights is attained when each weight-coordinate sign aligns with the corresponding input-coordinate sign.This sign alignment is used to characterize the relevant supremum.
  • A Proof of Theorem 2: The upper-bound proof applies the triangle inequality and then Khintchine’s inequality to control the adversarial Rademacher complexity.The proof explicitly attributes the final step to Khintchine’s inequality.
  • A Proof of Theorem 2: The lower-bound proof combines the earlier adversarial-margin relation with symmetry and the triangle inequality.This establishes the matching lower-bound direction for the adversarial complexity.

B.1 Proof of Theorem 3

The proof invokes a multi-class margin bound and specializes it to linear classifiers, completing the argument for this case.

  • The proof begins from the multi-class margin bound for any fixed γ with probability at least 1 −δ.
  • It then specializes the function class to linear classifiers satisfying ∥W⊤∥p,∞≤W.
  • This specialization completes the proof.

B.2 Proof of Theorem 4

The proof analyzes adversarial margins for linear classifiers, converts the adversarial loss through the worst-case margin, and bounds the resulting complexity using contraction and standard inequalities.

  • The adversarial loss is expressed as a maximum over perturbations of a ramp loss applied to the margin.
  • For linear classifiers, the worst-case perturbed margin is reduced to an optimization over the perturbation set B∞x(ϵ).
  • The proof uses the margin definition and properties of the ramp loss to establish the required pointwise inequalities.
  • The resulting loss-class complexity is controlled using the Ledoux-Talagrand contraction inequality and Lemma 8.1.
  • The remaining complexity terms are bounded through triangle inequality, Khintchine’s inequality, and Cauchy-Schwarz inequality.
  • The multi-class argument exploits that Q(·, ·) is linear in its first argument and applies bounds over positive semidefinite matrices with diagonal entries at most one.

C.3 Proof of Theorem 8

The proof studies the Rademacher complexity of a neural-network function class by decomposing the margin term and bounding each component with norm constraints and standard inequalities.

  • The proof defines the neural-network function class and its associated margin class before analyzing their Rademacher complexities.
  • The first complexity term is bounded using the constraint ∥W1∥1≤b1, which implies ∥W⊤1∥2,1≤b1.
  • The second term is bounded using a result from [44] together with properties of positive semidefinite matrices whose diagonal entries are at most one.
  • The derivation combines inequalities based on Khintchine’s inequality, Hölder’s inequality, the definition of Q, and direct upper bounds.
  • Combining the component bounds yields an upper bound for the Rademacher complexity, and Theorem 8 follows from Theorem 1 and Lemma 1.
Loading 1810.11914v4…