Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks

Abstract

Adversarial or test time robustness measures the susceptibility of a classifier to perturbations to the test input. While there has been a flurry of recent work on designing defenses against such perturbations, the theory of adversarial robustness is not well understood. In order to make progress on this, we focus on the problem of understanding generalization in adversarial settings, via the lens of Rademacher complexity. We give upper and lower bounds for the adversarial empirical Rademacher complexity of linear hypotheses with adversarial perturbations measured in $l_r$-norm for an arbitrary $r\ge 1$. This generalizes the recent result of [Yin et al.'19] that studies the case of $r=\infty$, and provides a finer analysis of the dependence on the input dimensionality as compared to the recent work of [Khim and Loh'19] on linear hypothesis classes. We then extend our analysis to provide Rademacher complexity lower and upper bounds for a single ReLU unit. Finally, we give adversarial Rademacher complexity bounds for feed-forward neural networks with one hidden layer. Unlike previous works we directly provide bounds on the adversarial Rademacher complexity of the given network, as opposed to a bound on a surrogate. A by-product of our analysis also leads to tighter bounds for the Rademacher complexity of linear hypotheses, for which we give a detailed analysis and present a comparison with existing bounds.

References in corpus (14)

• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
• Adversarially Robust Generalization Requires More Data
• Robustness May Be at Odds with Accuracy
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• Adversarial Training Can Hurt Generalization
• Adversarial examples from computational constraints
• Attacking the Madry Defense Model with $L_1$-based Adversarial Examples
• Adversarial Robustness May Be at Odds With Simplicity
• An Alternative Surrogate Loss for PGD-based Adversarial Testing
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Adversarial Risk Bounds via Function Transformation
• On Robustness to Adversarial Examples and Polynomial Optimization
• Adversarial Examples from Cryptographic Pseudo-Random Generators

Cited by in corpus (4)

• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• Calibration and Consistency of Adversarial Surrogate Losses
• Understanding the Generalization Benefit of Model Invariance from a Data Perspective
• A Finer Calibration Analysis for Adversarial Robustness