Non-Asymptotic Bounds for Adversarial Excess Risk under Misspecified Models

Changyu Liu, Yuling Jiao, Junhui Wang, Jian HuangarXiv 2023 · DOI · arXiv

Abstract

This research establishes a rigorous theoretical framework for adversarial training under model misspecification, where the target function is not perfectly representable by the chosen neural network. By deriving non-asymptotic convergence rates for adversarial excess risk, the authors quantify the mathematical trade-off between generalization and approximation errors, providing new insights into the robustness-accuracy dilemma.

Introduction: The Challenge of Model Misspecification

Deep learning models are highly susceptible to adversarial perturbations—small, intentional changes to input data that trigger incorrect outputs. While adversarial training is a standard defense, theoretical analysis often assumes a "well-specified" model where the target function exists within the hypothesis class. In practice, however, neural networks are merely approximations of complex real-world functions. This paper addresses this gap by investigating how adversarial training performs when the model is misspecified.

Methodology

The authors evaluate robust estimators using adversarial excess risk, which they decompose into two primary components:

  1. Generalization Error ($E_{gen}$): Error stemming from finite sample sizes.
  2. Approximation Error ($E_{app}$): Error resulting from the network's inability to perfectly capture the target function.

The study focuses on Feedforward Neural Networks (FNNs) with Lipschitz constraints, assuming the target function belongs to a Hölder space. A significant contribution is the proof that standard point-wise adversarial risk is equivalent to a distributional attack measured by the $\infty$-th Wasserstein distance.

Comparison of this work with existing literature across attack types, model classes, and error components.

Key Insights

  • Equivalence Theorem: Theorem 1 demonstrates that under specific smoothness conditions, point-wise adversarial risk is identical to risk from distributional shifts, enabling the use of optimal transport theory for bounding risk.
  • Robustness-Accuracy Trade-off: The paper provides a mathematical proof that adversarial robustness inherently impacts accuracy in natural settings, framing it as a consequence of excess risk bounds rather than just an empirical observation.
  • Complexity vs. Robustness: A clear trade-off exists where increasing network complexity (width and depth) reduces approximation error but simultaneously increases generalization error.

Key Results

The research establishes non-asymptotic upper bounds for adversarial excess risk. The convergence rates vary significantly based on the chosen loss function, as detailed in the derived bounds for different risk measurements.

Summary of non-asymptotic error bounds for various loss functions and risk measurements derived in this work.
  • General Lipschitz Loss: Achieves a rate of approximately $O(n^{-\alpha/(2d+3\alpha)})$.
  • Quadratic Loss (Regression): Yields a tighter bound of $O(n^{-2\alpha/(2d+5\alpha)})$.

These results indicate that the "cost" of robustness is reflected in error bounds that are generally slower than the minimax rates for standard, non-adversarial nonparametric estimation.

Limitations and Future Directions

While providing a foundational framework, the study notes several areas for expansion:

  • Unbounded Support: Current analysis requires Lipschitz-type conditions which may be violated by quadratic loss if the response variable is unbounded.
  • Label Perturbations: The focus remains on input feature perturbations; future work could consider adversarial noise in labels ($Y$).
  • Lower Bounds: The current work provides upper bounds; establishing minimax lower bounds would confirm if these rates are the absolute optimal for misspecified adversarial training.

Summary updated

Abstract

We propose a general approach to evaluating the performance of robust estimators based on adversarial losses under misspecified models. We first show that adversarial risk is equivalent to the risk induced by a distributional adversarial attack under certain smoothness conditions. This ensures that the adversarial training procedure is well-defined. To evaluate the generalization performance of the adversarial estimator, we study the adversarial excess risk. Our proposed analysis method includes investigations on both generalization error and approximation error. We then establish non-asymptotic upper bounds for the adversarial excess risk associated with Lipschitz loss functions. In addition, we apply our general results to adversarial training for classification and regression problems. For the quadratic loss in nonparametric regression, we show that the adversarial excess risk bound can be improved over those for a general loss.
BibTeX
@misc{liu2023non,
  author = {Changyu Liu and Yuling Jiao and Junhui Wang and Jian Huang},
  title = {{Non-Asymptotic Bounds for Adversarial Excess Risk under Misspecified Models}},
  year = {2023},
  eprint = {2309.00771},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.00771},
}
Figure