Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
This work addresses the lack of statistical understanding in adversarial robustness for machine learning, offering foundational theoretical guarantees that are broadly applicable across various perturbation types.
The paper tackles the problem of establishing statistical guarantees for adversarially robust classification under a Gaussian mixture model, providing the first optimal minimax excess risk bounds in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), with a lower bound of order Θ(e^{-(1/8+o(1)) r^2} d/n) and an efficient estimator achieving this rate.
Adversarial robustness has become a fundamental requirement in modern machine learning applications. Yet, there has been surprisingly little statistical understanding so far. In this paper, we provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification, under Gaussian mixture model proposed by \cite{schmidt2018adversarially}. The results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting. For the Gaussian mixtures with AdvSNR value of $r$, we establish an excess risk lower bound of order $Θ(e^{-(\frac{1}{8}+o(1)) r^2} \frac{d}{n})$ and design a computationally efficient estimator that achieves this optimal rate. Our results built upon minimal set of assumptions while cover a wide spectrum of adversarial perturbations including $\ell_p$ balls for any $p \ge 1$.