On the Generalization Analysis of Adversarial Learning

Waleed Mustafa, Yunwen Lei, Marius KloftICML 2022 · OpenReview

Introduction

Adversarial examples—imperceptible perturbations designed to deceive machine learning models—pose a significant security challenge. While empirical methods for adversarial training have advanced rapidly, our theoretical understanding of adversarial generalization (the performance gap between training data and unseen data) has historically lagged behind.

Previous theoretical analyses suffered from several critical blind spots:

  • Additive Bias: They predominantly assumed attackers only apply additive pixel noise ($L_p$ norms), ignoring non-additive attacks like spatial transformations (e.g., rotations or shearing).
  • Model Simplicity: Most bounds were restricted to linear models or shallow networks.
  • Surrogate Losses: Analyses often relied on proxy "surrogate" losses rather than the true adversarial loss.
  • Poor Scaling: Existing math suggested the generalization gap grew by $\sqrt{K}$ as the number of classes ($K$) increased, rendering the theory unhelpful for "extreme classification" tasks.

This paper introduces a novel theoretical framework that overcomes these limitations, providing the first generalization bounds that support non-additive attacks, scale efficiently with the number of classes, and deliver "fast-rate" convergence for adversarial deep learning.

Methodological Innovations

The authors tackle the gaps in existing theory using a modular approach based on covering numbers—a mathematical way to measure the "complexity" of a function class by calculating how many "balls" of a certain size are needed to cover it.

Three key technical moves define their approach:

  1. Multi-label Perspective: By treating adversarial generalization as a form of multi-label classification, the authors successfully leverage recent advances in vector-valued learning theory.
  2. Discretization: To handle the "max" operator (where an attacker selects the worst-case noise), the infinite noise space is approximated with a finite set (a "cover"). This allows the complex adversarial loss to be bounded using the complexity of the standard, non-adversarial model.
  3. Local Rademacher Complexity: To achieve "fast-rate" results, the authors use a technique that incorporates the model's training error. If a model achieves low error during training, these "optimistic" bounds demonstrate that the generalization gap shrinks much faster ($1/n$) than standard bounds ($1/\sqrt{n}$).

Key Insights and Theoretical Results

As a theoretical paper, this work eschews empirical experiments on datasets like ImageNet in favor of rigorous mathematical proofs (culminating in Theorems 4.8 and 6.8) that apply to general classes of models and noise types.

  • Noise Complexity Outweighs Input Dimension: A major insight is that the generalization gap is driven more by the complexity of the noise set than the dimensionality of the input. For example, a rotation attack (which has only a few degrees of freedom) generalizes better than a pixel-wise additive attack, even on high-resolution images.
  • Logarithmic Scaling with Classes: The authors prove that the generalization gap only grows with $\log(K)$ rather than $\sqrt{K}$. This is a massive improvement for models dealing with thousands of categories.
  • Direct Loss Analysis for Deep Networks: Unlike previous work that used surrogate upper bounds—which can become meaningless for deep networks—this framework applies directly to the adversarial loss. For multi-layer networks, the authors derive bounds that avoid the "exponential explosion" with depth found in prior theories.
  • Spatial Transformations: The paper provides the first-ever generalization bound for adversarial spatial transformations. Because these transformations are low-dimensional (e.g., a 2x2 matrix for shearing or rotation), they exhibit highly favorable generalization properties.

Limitations and Future Directions

While these bounds are significantly more general, the authors acknowledge a lingering "curse of dimensionality" regarding the noise set. If an attacker has a very high-dimensional space of possible perturbations, the discretization used in the proof grows exponentially.

Future research directions include investigating ways to mitigate this dependence on the noise set's dimension, exploring "dimensionality reduction" for attackers to prove even tighter bounds, and applying this framework to other types of non-additive noise, such as style transfer or semantic perturbations.

Summary updated

BibTeX
@inproceedings{mustafa2022generalization,
  author = {Waleed Mustafa and Yunwen Lei and Marius Kloft},
  title = {{On the Generalization Analysis of Adversarial Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=j3_qIc6Q4lv},
}
Figure