Many machine learning models are vulnerable to adversarial attacks. It has been observed that adding adversarial perturbations that are imperceptible to humans can make machine learning models produce wrong predictions with high confidence. Although there has been a lot of recent effort dedicated to learning models that are adversarially robust, this remains an open problem. In particular, it has been empirically observed that although using adversarial training can effectively reduce the adversarial classification error on the training dataset, the learned model cannot generalize well to the test data. Moreover, we lack a theoretical understanding of the generalization property of machine learning models in the adversarial setting. In this paper, we study the adversarially robust generalization problem through the lens of Rademacher complexity. We focus on $\ell_\infty$ adversarial attacks and study both linear classifiers and feedforward neural networks. For binary linear classifiers, we prove tight bounds for the adversarial Rademacher complexity, and show that in the adversarial setting, the Rademacher complexity is never smaller than that in the natural setting, 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 also exists in the Rademacher complexity of the $\ell_\infty$ adversarial loss function class. We further consider a surrogate adversarial loss 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.

本文主要研究了机器学习模型的鲁棒性问题，特别是针对 l∞ 攻击所造成的影响，并考察了基于 Rademacher 复杂度的鲁棒泛化问题。研究表明，通过限制权重矩阵的 l1 范数可能是提高在对抗环境下的泛化性能的有效方法。

对抗鲁棒泛化的Rademacher复杂度