Training Deep Neural Networks (DNNs) with adversarial examples often results
in poor generalization to test-time adversarial data. This paper investigates
this issue, known as adversarially robust generalization, through the lens of
Rademacher complexity. Building upon the studies by Khim and Loh (2018); Yin et
al. (2019), numerous works have been dedicated to this problem, yet achieving a
satisfactory bound remains an elusive goal. Existing works on DNNs either apply
to a surrogate loss instead of the robust loss or yield bounds that are notably
looser compared to their standard counterparts. In the latter case, the bounds
have a higher dependency on the width $m$ of the DNNs or the dimension $d$ of
the data, with an extra factor of at least $\mathcal{O}(\sqrt{m})$ or
$\mathcal{O}(\sqrt{d})$.
This paper presents upper bounds for adversarial Rademacher complexity of
DNNs that match the best-known upper bounds in standard settings, as
established in the work of Bartlett et al. (2017), with the dependency on width
and dimension being $\mathcal{O}(\ln(dm))$. The central challenge addressed is
calculating the covering number of adversarial function classes. We aim to
construct a new cover that possesses two properties: 1) compatibility with
adversarial examples, and 2) precision comparable to covers used in standard
settings. To this end, we introduce a new variant of covering number called the
\emph{uniform covering number}, specifically designed and proven to reconcile
these two properties. Consequently, our method effectively bridges the gap
between Rademacher complexity in robust and standard generalization.

对深度神经网络进行对抗性示例训练通常导致对测试时的对抗数据泛化能力差，本论文通过 Rademacher 复杂度研究了这个问题，提出了上确界对于匹配标准设置中的最优上确界的 DNN 的对抗 Rademacher 复杂度，通过计算对抗函数类的覆盖数来解决核心挑战，并引入了一种新的覆盖数变体，称为 “均匀覆盖数”，以有效地填补稳健和标准泛化中的 Rademacher 复杂度差距。

缩小差距：对健壮和标准泛化的 Rademacher 复杂性

Bridging the Gap: Rademacher Complexity in Robust and Standard  Generalization

Graph neural networks (GNNs) have gained popularity for various graph-related
tasks. However, similar to deep neural networks, GNNs are also vulnerable to
adversarial attacks. Empirical studies have shown that adversarially robust
generalization has a pivotal role in establishing effective defense algorithms
against adversarial attacks. In this paper, we contribute by providing
adversarially robust generalization bounds for two kinds of popular GNNs, graph
convolutional network (GCN) and message passing graph neural network, using the
PAC-Bayesian framework. Our result reveals that spectral norm of the diffusion
matrix on the graph and spectral norm of the weights as well as the
perturbation factor govern the robust generalization bounds of both models. Our
bounds are nontrivial generalizations of the results developed in (Liao et al.,
2020) from the standard setting to adversarial setting while avoiding
exponential dependence of the maximum node degree. As corollaries, we derive
better PAC-Bayesian robust generalization bounds for GCN in the standard
setting, which improve the bounds in (Liao et al., 2020) by avoiding
exponential dependence on the maximum node degree.

在这篇论文中，我们使用 PAC-Bayesian 框架为两种流行的图神经网络，图卷积网络（GCN）和消息传递图神经网络，提供了对抗鲁棒性泛化界限的结果。我们的结果揭示出图上扩散矩阵的谱范数、权重的谱范数以及扰动因子决定了这两个模型的鲁棒性泛化界限。同时，我们的界限避免了在标准设置中指数依赖于最大节点度的问题。作为推论，我们在标准设置中为 GCN 导出了更好的 PAC-Bayesian 鲁棒性泛化界限，避免了在（Liao 等人，2020）中对最大节点度的指数依赖。