Asymptotic Behavior of Adversarial Training in Binary Classification

Hossein Taheri, Ramtin Pedarsani, Christos ThrampoulidisarXiv 2020 · OpenReview

Abstract

It has been consistently reported that many machine learning models are susceptible to adversarial attacks i.e., small additive adversarial perturbations applied to data points can cause misclassification. Adversarial training using empirical risk minimization is considered to be the state-of-the-art method for defense against adversarial attacks. Despite being successful in practice, several problems in understanding generalization performance of adversarial training remain open. In this paper, we derive precise theoretical predictions for the performance of adversarial training in binary classification. We consider the high-dimensional regime where the dimension of data grows with the size of the training data-set at a constant ratio. Our results provide exact asymptotics for standard and adversarial test errors of the estimators obtained by adversarial training with $\ell_q$-norm bounded perturbations ($q \ge 1$) for both discriminative binary models and generative Gaussian-mixture models with correlated features. Furthermore, we use these sharp predictions to uncover several intriguing observations on the role of various parameters including the over-parameterization ratio, the data model, and the attack budget on the adversarial and standard errors.

Introduction

Machine learning models are notoriously fragile; a tiny, calculated "adversarial" nudge to an input can flip a correct prediction to a wrong one. Adversarial Training (AT)—where the model is trained on these perturbed examples—is currently the gold-standard defense. However, our understanding of AT remains largely empirical. While it works in practice, we lack a rigorous theory to explain why or how it generalizes. For instance, how does the "budget" (the size of the allowed perturbation) during training affect performance at test time? Does the "double descent" phenomenon seen in standard learning also occur in robust learning? This research moves beyond trial and error to provide exact mathematical predictions for these behaviors in high-dimensional settings.

Methodology

The study employs a sophisticated mathematical framework called the Convex-Gaussian-Min-max-Theorem (CGMT). Standard analysis of machine learning models often struggles when the number of features ($p$) and the number of data points ($m$) are both very large. CGMT allows researchers to "scalarize" a complex, high-dimensional optimization problem—such as training a robust classifier—into a much simpler set of scalar equations.

While CGMT has been used to analyze standard training, this work extends the technique to handle the inner maximization problem inherent in adversarial training, where the adversary seeks the worst possible perturbation for every data point. The analysis covers both $\ell_2$ and $\ell_\infty$ norm-bounded attacks and accounts for correlated features.

As a theoretical work, the paper focuses on synthetic statistical models where the ground truth is known:

  • Gaussian Mixture Models (GMM): Data points are drawn from two Gaussian distributions representing two classes.
  • Generalized Linear Models (GLM): Labels are generated by passing a linear combination of features through a link function (e.g., Logistic or Signed models).

The theoretical formulas are validated using numerical simulations to show that asymptotic (infinite-limit) predictions match real-world training results with remarkable accuracy.

Key Results

The primary contribution is the derivation of precise equations (Theorems 1 and 3) that predict test error based on training parameters. A key finding is that in the limit of infinite data, the estimators produced by adversarial training converge to the Bayes optimal robust error.

Adversarial and standard test errors versus the over-parameterization ratio $\delta$.

As shown in the figure above, there is a near-perfect overlap between the theoretical predictions (solid lines) and empirical results (markers) from gradient descent experiments. Notably, for binary classification with common decreasing losses (like Hinge or Logistic loss), the "double descent" spike disappears in adversarial training; error simply decreases as the data-to-parameter ratio ($\delta = m/p$) improves.

Key Insights and Ideas

The precise characterization reveals several intriguing behaviors:

  • AT Can Help Standard Accuracy: In certain under-parameterized regimes, a small amount of adversarial training actually improves the model's performance on clean, non-adversarial data compared to standard training.
  • The Training Budget Surplus: To achieve optimal robust performance, the optimal training budget ($\epsilon_{tr}$) is typically larger than the actual attack budget ($\epsilon_{ts}$) the model will face at test time.
Adversarial test error as a function of the training budget $\epsilon_{tr}$.

As illustrated in the plot of adversarial error versus $\epsilon_{tr}$, there is a clear minimum for different over-parameterization ratios, suggesting that carefully tuning the training budget is critical for maximizing robustness.

Conclusion

This work provides the first precise theoretical characterization of adversarial training in high-dimensional binary classification. While currently restricted to linear classifiers and additive $\ell_q$ norm attacks, it establishes a foundation for understanding robust generalization. Future directions include extending this framework to Random Features and Neural Tangent Kernels (NTK), bringing the theory closer to explaining the behavior of deep neural networks.

Summary updated

Abstract

It has been consistently reported that many machine learning models are susceptible to adversarial attacks i.e., small additive adversarial perturbations applied to data points can cause misclassification. Adversarial training using empirical risk minimization is considered to be the state-of-the-art method for defense against adversarial attacks. Despite being successful in practice, several problems in understanding generalization performance of adversarial training remain open. In this paper, we derive precise theoretical predictions for the performance of adversarial training in binary classification. We consider the high-dimensional regime where the dimension of data grows with the size of the training data-set at a constant ratio. Our results provide exact asymptotics for standard and adversarial test errors of the estimators obtained by adversarial training with $\ell_q$-norm bounded perturbations ($q \ge 1$) for both discriminative binary models and generative Gaussian-mixture models with correlated features. Furthermore, we use these sharp predictions to uncover several intriguing observations on the role of various parameters including the over-parameterization ratio, the data model, and the attack budget on the adversarial and standard errors.
BibTeX
@misc{taheri2020asymptotic,
  author = {Hossein Taheri and Ramtin Pedarsani and Christos Thrampoulidis},
  title = {{Asymptotic Behavior of Adversarial Training in Binary Classification}},
  year = {2020},
  eprint = {2010.13275},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.13275},
}
Figure