Sample Complexity of Robust Linear Classification on Separated Data

Robi Bhattacharjee, Somesh Jha, Kamalika ChaudhuriICML 2021 · OpenReview

Introduction

It is a well-known phenomenon in machine learning that training adversarially robust models requires significantly more data than training standard, simply accurate models. Prior theoretical work proved this sample complexity gap by analyzing overlapping data distributions (such as mixtures of Gaussians), where the classifier that minimizes standard error is fundamentally different from the one that minimizes robust error.

However, in many real-world safety-critical tasks, data from different classes is actually well-separated. This raises a critical question: Does the sample complexity gap between standard and robust learning still exist if the data is perfectly separated?

This paper investigates the "realizable" case for robust classification—linearly $r$-separable data—where a single linear classifier can achieve both zero standard error and zero robust error at an $\ell_p$ perturbation radius $r$. Surprisingly, the authors prove that even when a perfectly robust and accurate classifier exists, robust learning still requires significantly more data than standard learning unless the classes are separated by a margin much larger than the robustness radius.

The Geometry of Robust Classification

Decision boundaries for standard vs. robust classification

The core reason for this gap lies in the geometry of robust hypothesis classes. Just because a perfectly robust classifier exists does not mean it is easy to find. The set of "astute" (robust) classifiers is a much smaller, stricter subset of accurate classifiers.

As illustrated above, a standard classifier ($f_{std}$) might successfully separate the classes but pass dangerously close to the data points. Finding the strictly robust classifier ($f_{rob}$) that maintains a margin $r$ requires observing training examples that are extremely close to the decision boundary. The number of these critical boundary points needed to pin down the robust classifier scales linearly with the data dimension $d$.

Methods and Key Results

The authors tackle this problem through theoretical analysis, establishing both lower and upper bounds on expected loss:

  • A Provable $\Omega(d)$ Gap: The authors define a family of linearly $r$-separable distributions with a constant "aspect ratio" (the ratio of the data's $\ell_2$ diameter to its $\ell_2$ margin). They mathematically prove that for this family, the expected standard loss of a max-margin classifier is $O(1/n)$ (where $n$ is the number of samples). In stark contrast, the expected robust loss for any algorithm is at least $\Omega(d/n)$ (where $d$ is the dimension). This establishes a strict dimensional penalty for robustness.
  • Dimension-Independent Upper Bound: To show when robust learning is efficient, they introduce the concept of a robust margin—the margin that remains after accounting for the adversarial perturbation radius $r$. If the data has a robust aspect ratio $\rho_r(\mathcal{D})$ (derived from this robust margin), their proposed Adversarial-Perceptron algorithm achieves an expected robust loss of $O(\rho_r(\mathcal{D})^2 / n)$. Because this bound depends only on the robust aspect ratio and not $d$, it proves that highly separated data (where the standard margin is much larger than $r$) requires fewer samples to learn robustly.
  • Kernel Extension: The authors generalize their algorithm to an Adversarial-Kernel-Perceptron, allowing it to operate in embedded spaces for non-linear decision boundaries. This kernelized version achieves a similar upper bound of $O(\rho_r^K(\mathcal{D})^2 / n)$, showing the upper bound logic extends to non-linear classifiers.

Key Insights

  1. Separability doesn't erase the robust penalty: You still suffer a dimension-dependent penalty in sample complexity compared to standard learning, even when classes are perfectly separated.
  2. Excess margin saves the day: If the data is extremely well-separated—meaning the standard margin $\gamma$ is significantly larger than the robustness radius $r$—the sample complexity becomes dimension-independent again. In this regime, robust learning behaves much like standard SVM/perceptron learning.
  3. Norm mismatch: While adversarial perturbations are measured in a general $\ell_p$ norm ($p > 1$), the margin that dictates sample complexity is always measured in the $\ell_2$ norm.

Limitations and Future Work

The $\Omega(d/n)$ lower bound is specifically proven for linear classifiers. While the authors successfully generalized their upper bounds to Kernel Classifiers, they note that the effects of the robustness radius in embedded kernel spaces are considerably less well-behaved than in standard linear cases.

The primary direction for future work is fully generalizing the lower bounds to robust kernel classification. Additionally, the authors suggest that future theoretical work on adversarial sample complexity should explicitly factor in data separability, as it fundamentally changes the learning dynamics.

Summary updated

Abstract

We consider the sample complexity of learning with adversarial robustness. Most prior theoretical results for this problem have considered a setting where different classes in the data are close to...
BibTeX
@inproceedings{bhattacharjee2021sample,
  author = {Robi Bhattacharjee and Somesh Jha and Kamalika Chaudhuri},
  title = {{Sample Complexity of Robust Linear Classification on Separated Data}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=B5-m4KOni89},
}
Figure