Provable Robustness of Adversarial Training for Learning Halfspaces with Noise

Difan Zou, Spencer Frei, Quanquan Gu

Abstract

This paper provides a rigorous theoretical analysis of adversarial training (AT) for learning robust halfspaces in the presence of agnostic label noise. While adversarial training is widely used in practice, its theoretical properties—particularly when data is not perfectly separable—have remained poorly understood. We demonstrate that for distributions satisfying certain anti-concentration properties, such as isotropic log-concave distributions, standard AT using convex losses (like binary cross-entropy) achieves a robust classification error of $\tilde O(\sqrt{\mathsf{OPT}_{2,r}})$ for $\ell_2$ perturbations. Furthermore, we show that employing a nonconvex sigmoidal loss allows AT to achieve a significantly improved robust error of $O(\mathsf{OPT}_{2,r})$. These results extend to $\ell_\infty$ perturbations with a dependence on the dimension $d$. To our knowledge, this is the first work to prove that adversarial training yields robust classifiers in noisy, non-separable settings.

Introduction

Deep learning models are notoriously vulnerable to adversarial examples—small, intentionally crafted perturbations that cause incorrect classification. Adversarial Training (AT), which incorporates these perturbations into the training loop via a min-max optimization framework, is the most effective empirical defense. However, most existing theoretical guarantees for AT assume that the data is perfectly linearly separable with a clear margin.

In real-world scenarios, data is often "noisy" due to overlapping class distributions or mislabeled examples. This paper addresses this gap by analyzing AT under agnostic label noise, a challenging setting where no specific assumptions are made about the relationship between features and labels. We focus on the fundamental problem of learning halfspaces (linear classifiers) and provide the first provable guarantees for AT in this context.

Theoretical Framework

Problem Setting

We consider the task of finding a halfspace that minimizes the robust classification error. Let $\mathsf{OPT}_{p,r}$ denote the minimum robust error achievable by any halfspace against an adversary restricted to an $\ell_p$ ball of radius $r$. The goal is to determine if standard AT algorithms can approach this optimal value even when the data is noisy.

Distributional Assumptions

Our analysis applies to distributions that satisfy anti-concentration and anti-anti-concentration properties. These properties are naturally satisfied by a broad class of distributions, including isotropic log-concave distributions (e.g., Gaussian and uniform distributions over convex sets). These assumptions ensure that the data mass is sufficiently distributed, preventing the classifier from being easily "tricked" by noise concentrated in a small region.

Methods: Convex vs. Nonconvex Loss

We analyze two primary algorithmic approaches to adversarial training:

  1. AT with Convex Surrogates: This represents the standard practice of using convex loss functions like binary cross-entropy or hinge loss. The algorithm uses a min-max approach: the inner loop finds the worst-case perturbation, and the outer loop updates weights via gradient descent.
  2. AT with Nonconvex Sigmoidal Loss: We introduce Projected Stochastic Adversarial Training (PSAT), which utilizes a specialized nonconvex sigmoidal loss. This loss function acts as a smoother approximation of the 0-1 classification error, which is the ultimate metric of interest.

Key Findings

The Limitation of Convex Losses

A significant insight of this work is the "square root gap." When using standard convex losses, AT achieves a robust error of approximately $O(\sqrt{\mathsf{OPT}})$. This suggests that while convex surrogates are computationally efficient, they may have a fundamental theoretical limit in noisy environments, preventing them from reaching the true optimal robust error.

The Advantage of Nonconvexity

By switching to a nonconvex sigmoidal loss, we prove that the error rate can be improved to $O(\mathsf{OPT}_{2,r})$ for $\ell_2$ perturbations. This demonstrates that the choice of loss function is a critical factor in achieving optimal provable robustness. The sigmoidal loss more effectively ignores outliers and noise that would otherwise skew a convex objective.

The Cost of $\ell_\infty$ Robustness

The paper also quantifies the difficulty of defending against $\ell_\infty$ perturbations (where every feature can be modified). For these cases, the error bounds include factors of the dimension $d$ (e.g., $d^{1/4}$). This provides a theoretical explanation for why $\ell_\infty$ robustness is significantly harder to achieve in high-dimensional spaces compared to $\ell_2$ robustness.

Conclusion

This research bridges the gap between the empirical success of adversarial training and its theoretical foundations. By proving that the standard "inner-maximization, outer-minimization" loop converges to a robust solution even with agnostic noise, we provide a formal justification for the techniques used by practitioners.

While this work focuses on halfspaces, it lays the groundwork for future analysis of multi-layer neural networks. The transition from linear models to deep architectures remains a major open challenge, as does the relaxation of distributional assumptions to accommodate data residing on low-dimensional manifolds.

Summary updated

Abstract

We analyze the properties of adversarial training for learning adversarially robust halfspaces in the presence of agnostic label noise. Denoting $\mathsf{OPT}_{p,r}$ as the best robust classification error achieved by a halfspace that is robust to perturbations of $\ell_{p}$ balls of radius $r$, we show that adversarial training on the standard binary cross-entropy loss yields adversarially robust halfspaces up to (robust) classification error $\tilde O(\sqrt{\mathsf{OPT}_{2,r}})$ for $p=2$, and $\tilde O(d^{1/4} \sqrt{\mathsf{OPT}_{\infty, r}} + d^{1/2} \mathsf{OPT}_{\infty,r})$ when $p=\infty$. Our results hold for distributions satisfying anti-concentration properties enjoyed by log-concave isotropic distributions among others. We additionally show that if one instead uses a nonconvex sigmoidal loss, adversarial training yields halfspaces with an improved robust classification error of $O(\mathsf{OPT}_{2,r})$ for $p=2$, and $O(d^{1/4}\mathsf{OPT}_{\infty, r})$ when $p=\infty$. To the best of our knowledge, this is the first work to show that adversarial training provably yields robust classifiers in the presence of noise.
BibTeX
@inproceedings{zou2021provable,
  author = {Difan Zou and Spencer Frei and Quanquan Gu},
  title = {{Provable Robustness of Adversarial Training for Learning Halfspaces with Noise}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=D5bcPgSIYMA},
}
Figure