Rademacher Complexity for Adversarially Robust Generalization

By Dong Yin, Kannan Ramchandran, Peter L. Bartlett. 2018

291 citations recorded by the source corpus.

Many machine learning models are vulnerable to adversarial attacks; for example, adding adversarial perturbations that are imperceptible to humans can often make machine learning models produce wrong predictions with high confidence. Moreover, although we may obtain robust models on the training dataset via adversarial training, in some problems the learned models cannot generalize well to the test data. In this paper, we focus on $\ell_\infty$ attacks, and study the adversarially robust generalization problem through the lens of Rademacher complexity. For binary linear classifiers, we prove tight bounds for the adversarial Rademacher complexity, and show that the adversarial Rademacher complexity is never smaller than its natural counterpart, and it has an unavoidable dimension dependence, unless the weight vector has bounded $\ell_1$ norm. The results also extend to multi-class linear classifiers. For (nonlinear) neural networks, we show that the dimension dependence in the adversarial Rademacher complexity also exists. We further consider a surrogate adversarial loss for one-hidden layer ReLU network and prove margin bounds for this setting. Our results indicate that having $\ell_1$ norm constraints on the weight matrices might be a potential way to improve generalization in the adversarial setting. We demonstrate experimental results that validate our theoretical findings.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Safety, Robustness & Interpretability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Safety, Robustness & Interpretability

In Statistical Learning Theory

Citations in the corpus

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “[57] jointly studies statistical learning and adversarial robustness.”
Theoretically Principled Trade-off between Robustness and Accuracy (2019, background): “Despite a large literature on the analysis of robust error in terms of generalization (Schmidt et al., 2018; Cullina et al., 2018; Yin et al., 2018) and computational complexity (Bubeck et al.”
Adversarial examples from computational constraints (2018, background): “Since the first version of the paper appeared (in May 2018), all the directions discussed above have seen lots of progress (for a small and by no means representative sample, see (Garg et al., 2018; Yin et al., 2018; Zhang et al., 2019)).”
Unlabeled Data Improves Adversarial Robustness (2019, neutral): “Recent works [52, 21, 2] study adversarial robustness from a learning-theoretic perspective, and in a number of simplified settings develop generalization bounds using extensions of Rademacher complexity.”
Are Labels Required for Improving Adversarial Robustness? (2019, background): “3, 7, 14 [51] D.”
Model complexity of deep learning: a survey (2021, background): “[99] prove that the lower bound for the Rademacher complexity of F is Ω(||X||F /n+ √ d/n).”
MaxUp: A Simple Way to Improve Generalization of Neural Network Training (2020, unknown): “There has been shown a clear trade-off between the accuracy of a classiﬁer on clean data and its robustness against adversarial attacks (see e.g., Tsipras et al., 2019; Zhang et al., 2019; Yin et al., 2019; Schmidt et al., 2018).”
Towards Deep Learning Models Resistant to Large Perturbations (2020, methodology): “…a more theoretical perspective (Attias et al., 2018; Chen et al., 2020; Cullina et al., 2018; Diochnos et al., 2019; Gilmer et al., 2018; Ilyas et al., 2019; Khim & Loh, 2018; Montasser et al., 2019; Schmidt et al., 2018; Wang et al., 2017; Yin et al., 2018; Zhai et al., 2019; Zhang et al., 2019).”
Adversarial Training Can Hurt Generalization (2019, background): “Recent work [11, 16, 5, 7] has focused on the sample complexity of learning a predictor that has high robust accuracy (robust generalization), a different objective.”
Adversarial Weight Perturbation Helps Robust Generalization (2020, background): “Compared with standard generalization (on natural examples), training DNNs with robust generalization (on adversarial examples) is particularly difficult [27], and often possesses significantly higher sample complexity [20, 58, 28] and needs more data [42].”
Overfitting in adversarially robust deep learning (2020, background): “, 2018) and Rademacher complexity (Yin et al., 2018).”
Cross-Entropy Loss Functions: Theoretical Analysis and Applications (2023, background): “…et al., 2021; Kontorovich & Attias, 2021; Montasser et al., 2022), robust generalization (Khim & Loh, 2018; Attias et al., 2019; Xing et al., 2021; Yin et al., 2019; Schmidt et al., 2018; Awasthi et al., 2020; Attias et al., 2022b; Xiao et al., 2022; Viallard et al., 2021; Bubeck & Sellke, 2021;…”
Improved OOD Generalization via Adversarial Training and Pre-training (2021, background): “Compared with other uniform convergence generalization bounds which increase with the model capacity (e.g., Rademacher complexity (Yin et al., 2019) or entropy integral (Sinha et al., 2018)), our bounds are superior for models with high capacity.”
The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization (2020, methodology): “One is the linear loss function (cid:96) ( x, y ; w ) = − y (cid:104) w, x (cid:105) where w ∈ Θ = { w ∈ R d |(cid:107) w (cid:107) ∞ ≤ W } and W > 0 is a positive constant, similar to [Chen et al., 2020, Yin et al., 2019, Khim and Loh, 2018].”
Precise Tradeoffs in Adversarial Training for Linear Regression (2020, background): “The notions of capacity and complexity in the presence of adversarially perturbed inputs (a.k.a. adversarially robust learnability) have also been studied in a series of interesting papers [BLPR19, CBM18, KL18, YRB19, MHS19].”
A Kernel Perspective for Regularizing Deep Neural Networks (2018, unknown): “In concurrent work, Khim & Loh (2018); Yin et al. (2019) derive similar bounds in the context of fully-connected networks.”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, methodology): “It is argued in [51] that robust generalization is also harder using Rademacher complexity.”
Adversarial Robustness with Semi-Infinite Constrained Learning (2021, background): “…imply the robust uniform for L steps do 5: , where ξ i ∼ Laplace (0 , I ) and i = 1 , . . . , m 7: end for 8: end for 10: until convergence convergence property (8a), there is a growing body of evidence which suggests that this property does in fact hold for the function class of DNNs [68, 79, 80].”
Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, methodology): “Prior works rely on relaxations of the adversarial loss to bound adversarially robust generalization for neural nets [Khim and Loh, 2018, Yin et al., 2018].”