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 (19)

• Explaining and Harnessing Adversarial Examples
• Theoretically Principled Trade-off between Robustness and Accuracy
• Adversarially Robust Generalization Requires More Data
• Robustness May Be at Odds with Accuracy
• Robustness and Regularization of Support Vector Machines
• Are Labels Required for Improving Adversarial Robustness?
• Towards Fast Computation of Certified Robustness for ReLU Networks
• Adversarial examples from computational constraints
• Rademacher Complexity for Adversarially Robust Generalization
• Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
• Adversarially Robust Generalization Just Requires More Unlabeled Data
• Understanding and Mitigating the Tradeoff Between Robustness and Accuracy
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Lower Bounds on Adversarial Robustness from Optimal Transport
• Adversarial Risk Bounds via Function Transformation
• On Robustness to Adversarial Examples and Polynomial Optimization
• Adversarial Examples from Cryptographic Pseudo-Random Generators
• Precise Tradeoffs in Adversarial Training for Linear Regression
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks

Cited by in corpus (3)

• Adversarially Robust Estimate and Risk Analysis in Linear Regression
• Asymptotic Behavior of Adversarial Training in Binary Classification
• Exploring Adversarial Robustness of Deep Metric Learning