Provable Robustness of Adversarial Training for Learning Halfspaces with Noise

Difan Zou, Spencer Frei, Quanquan Gu

Adversarial training (AT) is widely considered the gold standard for defending neural networks against malicious perturbations. However, theoretical understanding of why it works has historically been limited to "clean," realizable settings where data is perfectly separable. In the real world, datasets are messy, containing mislabeled examples, overlapping classes, and outliers.

In their ICML 2021 paper, Difan Zou, Spencer Frei, and Quanquan Gu provide the first theoretical guarantees that adversarial training can produce robust classifiers even in the presence of agnostic label noise. By analyzing both standard convex losses and non-convex sigmoidal losses, the authors demonstrate mathematically that AT successfully learns robust halfspaces (linear classifiers) and achieves nearly optimal robust classification error.

The Challenge of Agnostic Noise

Most theoretical work on adversarial robustness assumes a "realizable" setting, meaning there exists a perfect classifier that can separate the data with a clear margin. Real-world datasets, however, are agnostic.

The primary challenge in this agnostic setting is that the "robust loss"—the objective AT attempts to minimize—is notoriously difficult to analyze. It involves an inner maximization problem (finding the worst-case perturbation for every single data point) coupled with an outer minimization problem (updating the model weights). When arbitrary noise is introduced, it becomes unclear whether the gradient descent process will converge to a robust solution or simply destabilize.

Methodology: Convex vs. Non-Convex Losses

The authors focus on learning halfspaces, defined as $f(x) = \text{sign}(w^\top x)$, under $\ell_p$ perturbations. They analyze two main algorithmic approaches to understand how different loss functions behave under noise:

  1. Adversarial Training with Convex Surrogates: This approach uses standard losses like cross-entropy or hinge loss. The authors show that standard AT efficiently minimizes the robust empirical risk.
  2. Projected Stochastic Adversarial Training (PSAT) with Sigmoidal Loss: The authors introduce a variant that utilizes a non-convex sigmoidal loss. This loss is specifically designed to be more robust to outliers than convex losses, which tend to be overly sensitive to "hard" noisy examples.

The theoretical analysis relies on soft margin conditions and anti-concentration properties of the data distribution. These properties ensure that the data is not excessively concentrated near the decision boundary, allowing the algorithm to find a stable, robust hyperplane.

Theoretical Setting

As a foundational theoretical paper, this work evaluates performance on mathematically defined distributions rather than empirical benchmarks like ImageNet or CIFAR-10. The analysis assumes:

  • Log-concave isotropic distributions: A broad class of distributions that includes the standard Gaussian and uniform distributions over convex sets.
  • Agnostic Label Noise: A general noise model where no assumptions are made about the relationship between the features $x$ and the labels $y$.

Key Findings and Error Bounds

A major insight from the paper is that convex losses are sub-optimal for robustness. While cross-entropy is the industry standard, the authors prove that a non-convex sigmoidal loss provides significantly tighter error bounds because it prevents noisy outliers from disproportionately skewing the decision boundary.

The authors measure success by comparing the learned model's error to $\mathsf{OPT}_{p,r}$, the best possible robust error any halfspace could achieve. The key theoretical results include:

  • For $\ell_2$ perturbations (Convex Loss): AT achieves a robust error bounded by $O(\sqrt{\mathsf{OPT}_{2,r}})$.
  • For $\ell_2$ perturbations (Sigmoidal Loss): AT improves this bound to $O(\mathsf{OPT}_{2,r})$, which is nearly optimal.
  • For $\ell_\infty$ perturbations: The error is bounded by $O(d^{1/4} \mathsf{OPT}_{\infty,r})$. The $d^{1/4}$ factor represents the geometric "price" paid for the $\ell_\infty$ ball in high-dimensional spaces, highlighting that in high dimensions, there is more room for adversarial perturbations to hide.

Essentially, the paper proves that if a robust classifier exists, adversarial training is guaranteed to find one that is nearly as good, even if the training data is riddled with errors.

Limitations and Future Directions

The primary limitation of this work is its scope: the analysis is restricted to halfspaces. While halfspaces are the fundamental building blocks of neural networks, they are strictly linear, whereas modern deep learning relies on multi-layer non-linear architectures.

The authors suggest that the next frontier is extending these provable robustness guarantees to multi-layer neural networks (e.g., ReLU networks) and exploring more complex, structured noise models beyond agnostic noise, such as adversarial label flipping. Ultimately, this paper serves as a crucial theoretical foundation, proving that the most popular defense mechanism in deep learning is mathematically sound at its most basic level.

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 classification erro...
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