Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification

Abstract

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 $\Theta (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$.

25 pages, 1 figure. Accepted by ICML 2020

References in corpus (7)

• Explaining and Harnessing Adversarial Examples
• Theoretically Principled Trade-off between Robustness and Accuracy
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Lower Bounds on Adversarial Robustness from Optimal Transport
• On Robustness to Adversarial Examples and Polynomial Optimization
• Precise Tradeoffs in Adversarial Training for Linear Regression
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks

Cited by in corpus (2)

• Adversarially Robust Estimate and Risk Analysis in Linear Regression
• Exploring Adversarial Robustness of Deep Metric Learning