Rademacher Complexity, Adversarial Robustness, Generalization Bounds, Neural Networks

1 Introduction↩︎

Deep neural networks (DNNs) [3], [4] have achieved remarkable success in various machine learning tasks, including computer vision (CV) and natural language processing (NLP). However, they have been shown to be vulnerable to adversarial examples [5], [6]. More specifically, a well-trained model can perform poorly on slightly perturbed data samples. Incorporating perturbed samples into the training dataset can improve robustness in practice, but it does not always lead to satisfactory performance. One major issue arises from generalization: while training a model to fit perturbed training samples is relatively easy, such a model often fails to generalize well to adversarial examples in the test set. For instance, when applying ResNet to CIFAR-10, adversarial training can achieve nearly 100% robust accuracy on the training set, yet only 47% robust accuracy on the test set [7]. Recent works [8], [9] have mitigated the overfitting issue, but it still has a \(20\%\) robust generalization gap between robust test accuracy (approximately 60%) and robust training accuracy (around 80%). Therefore, it is interesting to provide a theoretical understanding of adversarially robust generalization. This paper focuses on Rademacher complexity.

In classical learning theory, the generalization gap can be bounded in terms of Rademacher complexity with high probability. Rademacher complexity is defined as
\[\mathcal{R}_\mathcal{S}(\mathcal{H})=\mathbb{E}_\sigma \frac{1}{n}\bigg[\sup_{h\in\mathcal{H}}\sum_{i=1}^{n}\sigma_i h(x_i,y_i)\bigg],\]
where \(\mathcal{S}=\{x_i,y_i\}_{i=1,\cdots,n}\) is the sample dataset with \(n\) samples, \(\mathcal{H}\) is the hypothesis function class, and \(\sigma_i\) are i.i.d. Rademacher random variables, i.e., \(\sigma_i\) takes values \(1\) or \(-1\) with equal probability. Techniques for deriving upper bounds on the Rademacher complexity of deep neural networks have been extensively studied, including layer-peeling [10], [11] and covering number arguments [12]. For more details, see Section 2.

[1] and [2] concurrently extended Rademacher complexity to adversarial settings. They demonstrated that the robust generalization gap can be bounded by the Rademacher complexity of the adversarial loss, defined as \(\tilde{h}(x_i, y_i) = \max_{x_i' \in \mathcal{B}(x_i)} h(x_i', y_i)\), where \(\mathcal{B}(x)\) is a norm ball around sample \(x\), and \(\tilde{\mathcal{H}}\) represents the hypothesis class of adversarial losses. This specific form of Rademacher complexity is referred to as adversarial Rademacher complexity. Their primary contribution was establishing bounds for linear function classes.

For neural networks, it may seem straightforward to extend methods for standard losses to adversarial losses. However, [1], [2] both pointed out that providing upper bounds in adversarial settings is significantly more challenging due to the presence of the \(\max\) operator in adversarial loss. As a result, they relied on surrogate losses, leaving the following question for future work:

Since 2018, several attempts have been made to tackle this problem. [13] attempted to extend the bounds on adversarial Rademacher complexity from linear functions to two-layer neural networks. [14] proposed a more meaningful surrogate loss: the FGSM loss. Broadly, existing attempts to tackle this problem can be categorized into two main approaches.

1.0.0.1 Type 1: Adversarial Loss in Shallow Networks.

The first approach focuses on obtaining closed-form solutions for the optimal adversarial examples \(x^*\) and analyzing the adversarial loss, given by \(\max_{x'} h(x',y) = h(x^*,y)\). [1], [2] introduced adversarial Rademacher complexity and provided bounds for linear functions using this method. [13] extended this analysis to two-layer neural networks, deriving bounds in this setting. However, in deeper networks, obtaining closed-form solutions becomes intractable, making it unclear how to extend this approach to multi-layer architectures and derive generalization bounds in deep neural networks.

1.0.0.2 Type 2: Surrogate Loss in Deep Networks.

This approach uses a surrogate loss \(\hat{h}(x,y) \approx \tilde{h}(x,y) = \max_{x'} h(x',y)\) to bypass the main difficulty posed by the \(\max\) operator, where the surrogate loss does not explicitly contain a \(\max\) term. Examples of \(\hat{h}(x,y)\) include tree-transformation loss [1], SDP relaxation loss [2], and FGSM loss [14]. However, this approach provides upper bounds for the Rademacher complexity of the surrogate loss rather than the adversarial loss, and thus cannot bound the robust generalization gap. For a more detailed discussion, see Appendix 9.2.

In summary, these two types of attempts aim to eliminate the \(\max\) operator using different approaches. The methods and their limitations are summarized in Table 1. To our knowledge, the problem of bounding the adversarial Rademacher complexity of deep neural networks has remained unsolved since it was first raised in 2018. In this paper, we resolve this problem and provide the first bound for the adversarial Rademacher complexity of deep neural networks. Our approach is based on the covering number, which serves as an upper bound for Rademacher complexity. In adversarial settings, this problem becomes:

The first challenge for this problem is that the closed-form expression of optimal adversarial examples is not known. To address this, we introduce a concept called intermediate adversarial examples, which allow us to bound the covering number of the linear function class without requiring access to the closed-form solution of the optimal adversarial example. Using this approach, we reproduce the bound in the linear setting. The formal definition of intermediate adversarial examples is provided later in Lemma 1.

The second challenge arises from the conflict between existing methods for calculating the covering number of DNNs and the dynamic nature of intermediate adversarial examples. Current techniques for computing the covering number of DNNs assume a static training set, whereas adversarial examples are model-dependent and evolve dynamically. To resolve this issue, we introduce a lemma called Layer-wise Induction for Adversarial Hypothesis Class, which is designed to be compatible with our intermediate adversarial examples. The formal statement of this lemma is provided later in Lemma 2. By combining these two techniques, we establish the first bound on the adversarial Rademacher complexity of DNNs.

1.0.0.3 Main Result.

For depth-\(l\), width-\(h\) fully-connected neural networks, assume that the weight matrices \(W_1,W_2,\dots,W_l\) in each of the \(l\) layers have Frobenius norms bounded by \(M_1,\dots,M_l\), and all \(n\) samples are bounded by \(B\). Then, \[\text{Adversarial Rademacher Complexity} \leq\mathcal{O}\bigg(\frac{(B+\epsilon)h\sqrt{l\log l}\prod_{j=1}^l M_j}{\sqrt{n}}\bigg).\] We provide a comparison with existing bounds in similar settings. We show that our bound is comparable to (1) the upper bound for standard Rademacher complexity and (2) the upper bound for adversarial Rademacher complexity of two-layer neural networks [13]. Additionally, we provide a lower bound for adversarial Rademacher complexity and extend the results to multi-class classification settings. Finally, we study some empirical implications of our bounds. Our experiments indicate that the weight norm is positively correlated with the robust generalization gap. These findings contribute to a deeper theoretical understanding of adversarial robustness in deep learning models.

2 Related Work↩︎

2.0.0.1 Adversarial Attacks and Defense.

Since 2013, it has been well established that deep neural networks trained using standard gradient descent are highly vulnerable to small perturbations in input data [5]–[7], [15], [16]. Research on improving the robustness of neural networks has followed two main directions. One line of work focuses on developing defense mechanisms to enhance model robustness against adversarial attacks [8], [17]. Another line aims to design stronger adversarial attacks to evaluate and challenge existing defenses [15], [18]–[20].

2.0.0.2 Robust Generalization.

Prior research has demonstrated that increasing the amount of training data can improve robust generalization [21]–[23]. Several works have analyzed generalization in adversarial settings through the lens of VC-dimension [24], [25]. [26] applied a PAC-Bayesian framework to derive generalization bounds for neural networks, which was later extended to adversarial settings by [27], [28]. [29] examined robust generalization in the context of distributional robustness, while [30] explored it from the perspective of feature purification. Additionally, [31] studied generalization properties in the setting of linear regression.

2.0.0.3 Rademacher Complexity.

[10] applied a layer-peeling technique to derive a generalization bound for depth-\(l\) neural networks. Specifically, assuming that the Frobenius norms of the weight matrices \(W_1, W_2, \dots, W_l\) are bounded by \(M_1, \dots, M_l\), and that all \(n\) input instances have \(\ell_2\)-norm bounded by \(B\), they showed that the generalization gap between the population risk and the empirical risk is bounded with high probability by \(\mathcal{O}(B 2^l \prod_{j=1}^l M_j / \sqrt{n})\). Additionally, [12] provided a spectral norm-based bound on the Rademacher complexity by controlling the covering number of the function class of deep neural networks. The relevant work on Adversarial Rademacher Complexity is discussed in the Introduction, with further details provided in Appendix 9. For a more detailed discussion, see Appendix 9.3.

3 Preliminaries↩︎

3.1 Generalization Gap and Rademacher Complexity↩︎

3.1.0.1 Generalization Gap.

In the classical machine learning framework, we consider a function class \(\mathcal{F}\) (e.g., linear functions, neural networks). The learning objective is to find a function \(f \in \mathcal{F}\) that minimizes the population risk: \[R(f)=\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(f(x),y)],\] where \(\mathcal{D}\) denotes the underlying data distribution and \(\ell(\cdot)\) is the loss function. Since \(\mathcal{D}\) is typically unknown, we minimize the empirical risk in practice. Given \(n\) independent and identically distributed (i.i.d.) samples \(\mathcal{S}=\left\{(x_1,y_1),\ldots,(x_n,y_n)\right\}\), the empirical risk is defined as: \[R_n(f)=\frac{1}{n}\sum_{i=1}^n\ell(f(x_i),y_i).\] The generalization gap is then defined as the difference between the population risk and the empirical risk: \[\text{Generalization Gap} := R(f) - R_n(f).\] Let the hypothesis class be defined as \(\mathcal{H}=\left\{h\mid h(x,y)=\ell(f(x),y), f\in\mathcal{F}\right\}\), which connects the loss function to the function class. The Rademacher complexity framework leads to the following generalization bound.

3.2 Robust Generalization Gap and Adversarial Rademacher Complexity↩︎

3.2.0.1 Robust Generalization Gap.

In the context of adversarial robustness, we define the robust population risk and robust empirical risk as follows: \[\tilde{R}(f)=\mathbb{E}_{(x,y)\sim \mathcal{D}}\max_{\|x'-x\|_p\leq\epsilon}\ell(f(x'),y)\quad \text{and}\;\quad \tilde{R}_n(f)=\frac{1}{n}\sum_{i=1}^n\max_{\|x_i'-x_i\|_p\leq\epsilon}\ell(f(x_i'),y_i).\] Throughout this paper, we focus on general \(\ell_p\) attacks where \(p\geq 1\). We denote by \(\mathcal{B}(x)\) the general perturbation set around point \(x\). For \(\ell_p\) attacks, this set is defined as \(\mathcal{B}(x)=\left\{x'\mid \|x'-x\|_p\leq\epsilon\right\}\). The robust generalization gap is then defined as: \[\text{Robust Generalization Gap} := \tilde{R}(f)-\tilde{R}_n(f).\] Let the adversarial loss be defined as \(\tilde{\ell}(f(x),y):=\max_{x'\in\mathcal{B}(x)}\ell(f(x'),y)\). We then define the adversarial hypothesis class as: \[\label{eq:adv-hypo-class} \tilde{\mathcal{H}}=\left\{\tilde{h}: \tilde{h}(x,y)=\tilde{\ell}(f(x),y), f\in\mathcal{F}\right\},\tag{1}\] and assume \(0\in \tilde{\mathcal{H}}\). Then, according to Proposition [thm:rad95vanilla], the robust generalization gap can be bounded by the Rademacher complexity of \(\tilde{\mathcal{H}}\). We have the following robust generalization bound.

The Rademacher complexity can be further upper bounded using the covering number, which we define as follows.

We now specialize this concept to hypothesis classes. Given a sample dataset \(\mathcal{S}\), we define a pseudometric on \(\mathcal{H}\) as: \(\|h\|_\mathcal{S}^2=\frac{1}{n}\sum_{i=1}^{n}h( x_i,y_i)^2\). The \(\zeta\)-covering number of \(\mathcal{H}\) is then defined as \(\mathcal{N}(\mathcal{H},\|\cdot\|_\mathcal{S},\zeta)\).

3.2.0.2 Function Class.

We consider depth-\(l\), width-\(h\) fully-connected neural networks, \[\label{hypo} \mathcal{F} = \left\{ x \mapsto W_l \rho \left( W_{l-1} \rho \left( \cdots \rho \left( W_1 x \right) \cdots \right) \right) \mid \|W_j\| \leq M_j, \;j = 1, \dots, l \right\},\tag{2}\] where \(\rho (\cdot)\) is an element-wise \(L_\rho\)-Lipschitz activation function and \(\rho (0)=0\), \(W_j\) are \(h_j\times h_{j-1}\) matrices, for \(j=1,\cdots,l\). \(h_0\) equals to the input dimension \(d\). Let \(h=\max\left\{h_0,\cdots,h_l\right\}\) be the width of the neural networks. Denote the (\(a,b\))-group norm \(\|W\|_{a,b}\) as the \(a\)-norm of the \(b\)-norm of the rows of \(W\). We consider two cases in Equation 2 : the Frobenius norm and the \(\|\cdot\|_{1,\infty}\)-norm. We use the superscript \(\mathrm{binary}\) to indicate the binary setting. In this case, functions \(f\in\mathcal{F}^\mathrm{binary}\) have scalar outputs, i.e., \(h_l=1\). Without this superscript, the notation refers to the general multiclass setting, where \(f\) outputs a vector. The corresponding function classes are denoted as \(\mathcal{F}_2\) and \(\mathcal{F}_{1,\infty}\), respectively. Additionally, let the training data be \(x_1,\cdots, x_n \in \mathbb{R}^d\). We assume that \(\|X\|_{p,\infty}= B\), where \(X\) is the data matrix whose \(i\)-th row is \(x_i^\top\).

4 Main Challenges in Bounding ARC↩︎

In this section, we discuss the fundamental challenges encountered in bounding ARC and present our approach to addressing these challenges.

The main difficulty in bounding the ARC of DNNs comes from the fact that adversarial perturbations destroy the recursive structure that underlies the existing analyses of Rademacher complexity for DNNs.

To explain this point, recall that the existing approaches for bounding the Rademacher complexity of deep neural networks mainly follow two related routes. The first route directly peels the Rademacher complexity layer by layer. Let \(\mathcal{F}_l\) denote the \(l\)-layer network class, this approach establishes a recursive relationship of the form \[\mathcal{R}_\mathcal{S}(\mathcal{H}_l) \quad \text{in terms of} \quad \mathcal{R}_\mathcal{S}(\mathcal{H}_{l-1}),\] where the last layer is peeled off and the remaining part is treated as an \((l-1)\)-layer network class. The second route bounds the Rademacher complexity through covering numbers. In this case, the key step is again recursive: one constructs the covering number of the \(l\)-layer class, denoted as \(\mathcal{N}_l\), from the covering numbers of the previous layers, schematically, \[\mathcal{N}_l \quad \text{in terms of} \quad \mathcal{N}_1,\ldots,\mathcal{N}_{l-1}.\] Although these two routes look different, both of them rely on the same implicit fixed-sample structure. At each recursive step, the input feature set to the current layer is treated as fixed once the previous layers have been handled.

More concretely, consider an \(l\)-layer neural network and write \[h_0(x)=x, \qquad h_j(x)=\sigma(W_jh_{j-1}(x)), \quad j=1,\ldots,l-1.\] In the standard, non-adversarial setting, the empirical process is evaluated on the fixed samples \(\{x_i\}_{i=1}^n\). Thus, at the \(j\)-th layer, the relevant feature set is \[\{h_{j-1}(x_i):i=1,\ldots,n\}.\] This feature set is generated from the fixed training samples and the previous layers. Hence, after the previous layers have been peeled or covered, the analysis of the next layer can be performed conditionally on this empirical feature set. This is the fixed-sample structure implicitly used by both the direct Rademacher peeling method and the covering number method.

The adversarial setting breaks this structure. In ARC, the relevant input for \(x_i\) is selected by an inner maximization, for example \[x_i^*(f) \in \arg\max_{\|x-x_i\|\le \epsilon} \ell(f(x),y_i).\] Thus the effective sample is no longer the fixed sample \(\{x_i\}_{i=1}^n\), but the network-dependent sample \[\{x_i^*(f):i=1,\ldots,n\}.\] This network dependence prevents the standard recursive arguments from going through.

For the direct Rademacher peeling route, the obstruction is the following. A recursion from an \((l-1)\)-layer ARC to an \(l\)-layer ARC would require comparing the adversarial process of the \((l-1)\)-layer subnetwork with that of the \(l\)-layer network. However, the adversarial examples associated with these two objects are generally different: \[x_i^*(W_{l-1},\cdots, W_1) \neq x_i^*(W_l,W_{l-1},\cdots, W_1).\] The former is selected according to an \((l-1)\)-layer network, while the latter is selected according to the full \(l\)-layer network. Therefore, the recursive step \[\mathcal{R}_\mathcal{S}(\tilde{\mathcal{H}}_{l-1}) \rightarrow \mathcal{R}_\mathcal{S}(\tilde{\mathcal{H}}_l)\] does not have the same fixed samples on both sides. The sample on which the \((l-1)\)-layer quantity is evaluated is not the sample that appears inside the \(l\)-layer adversarial process. This mismatch is precisely what prevents a direct layer-by-layer peeling argument.

For the covering number route, the obstruction appears in two places: one is the comparison between two nearby networks, and the other is again the recursive step. Let \(f\) and \(f'\) be two networks.

First, in the standard setting, one controls their empirical discrepancy on the same fixed samples: \[\bigl|f(x_i)-f'(x_i)\bigr|.\] In the adversarial setting, however, the two adversarial examples \[x_i^*(f)=x_i^*(W_l,\cdots,W_1) \;\text{and}\; x_i^*(f')=x_i^*(W_l',\cdots,W_1')\] are different in general. Therefore, the relevant comparison is no longer between two networks evaluated on the same input, but between two networks evaluated on different network-dependent adversarial examples.

Second, in the standard setting, this common sample set allows the covering number to be calculated recursively across layers. In the adversarial setting, however, the covering numbers of different layers are evaluated on different adversarial examples, since the adversarial examples depend on the network being covered. Consequently, similar to the direct Rademacher-complexity route, the usual layerwise covering recursion \[\mathcal{N}_1,\ldots,\mathcal{N}_{l-1} \longrightarrow \mathcal{N}_l\] does not directly go through.

This motivates us to construct an adversarial example that can play the role of a common reference point in the recursive analysis. The goal is to define layerwise adversarial examples that are not fixed in the same sense as the original samples in the standard setting, but are sufficiently stable and structured to support the desired recursions. To this end, we introduce intermediate adversarial examples. They serve as replacements for the fixed intermediate feature sets in the non-adversarial theory. They allow us to track adversarially selected inputs through the network layer by layer and thereby recover a recursive structure for the adversarial Rademacher complexity analysis.

4.1 Intermediate Adversarial Examples↩︎

In this section, we use binary classification with a one-dimensional linear function as a simple example to illustrate how intermediate adversarial examples are defined and used to bound the ARC. Following [2] and [13], we define the loss function as \(\ell(f(x), y) = \phi(y f(x))\), where \(\phi\) is a non-increasing function. Then \[\max_{x'} \ell \left( f \left( x' \right), y \right) = \phi \left( \min_{x'} y f \left( x' \right) \right).\] Assume that the function \(\phi\) is \(L_\phi\)-Lipschitz, by Talagrand’s Lemma [32], we have \(\mathcal{R}_\mathcal{S}(\tilde{\mathcal{H}})\leq L_\phi \mathcal{R}_\mathcal{S}(\tilde{\mathcal{F}}^\mathrm{binary})\), where we define the adversarial hypothesis class as \[\label{hypo2} \tilde{\mathcal{F}}^\mathrm{binary} = \left\{ \tilde{f} : (x,y) \mapsto \inf_{\left\| x - x' \right\|_p \leq \epsilon} y f \left( x' \right) \mid f \in \mathcal{F}^\mathrm{binary} \right\}.\tag{3}\] Let \(f_w(x): \mathcal{X} \rightarrow \mathbb{R}\) with \(|w| \le M\) and \(\mathcal{X}\subset\mathbb{R}\), and define its adversarial function as \[g_w(x) \triangleq \min_{x' \in [x - \epsilon,\, x + \epsilon]} f_w(x').\] For simplicity, suppose we have only one sample \(x\) with \(|x| = B\). The problem is as follows:

To help better understand Problem 1, we consider a simpler problem of a standard function class \(\mathcal{F}^\mathrm{binary} = \left\{ f_w(\cdot): \mathbb{R} \rightarrow \mathbb{R} \mid |w| \le M \right\}\).

The idea is to relate a cover of the function class to a cover of the parameter region. Consider the one-dimensional linear function \(f_w(x)=wx, w\in[-M,M].\) For two parameters \(w_1,w_2\in[-M,M]\), we have \[|f_{w_1}(x)-f_{w_2}(x)| = |(w_1-w_2)x| \leq |w_1-w_2|\,|x|.\] Therefore, if \(|x|\leq B\) and \(|w_1-w_2|\leq \epsilon_w:=\frac{\zeta}{B}\), then \(|f_{w_1}(x)-f_{w_2}(x)|\leq \zeta\). Thus, an \(\epsilon_w\)-cover of the parameter interval \([-M,M]\) induces a \(\zeta\)-cover of the function class \(\mathcal{F}^\mathrm{binary}\) on the domain \(\{x:|x|\leq B\}\). It remains to bound the size of such a parameter cover. For example, \[\left\{M, M-2\epsilon_w, M-4\epsilon_w,\ldots\right\}\] is a \(2\epsilon_w\)-spaced grid over \([-M,M]\), whose size is at most \(\frac{2M}{2\epsilon_w} = \frac{M}{\epsilon_w} = \frac{MB}{\zeta}\). Hence, for the one-dimensional linear class, the covering number satisfies \[\mathcal{N}(\mathcal{F}^\mathrm{binary},\zeta) \leq \frac{MB}{\zeta}.\]

Now we return to Problem 1 and show how to define and use intermediate adversarial examples to solve this problem. Given an original example \(x\), let \[x_1^*=\arg\inf_{\|x-x'\|\leq\epsilon} w_1 x',\quad\text{and}\quad x_2^*=\arg\inf_{\|x-x'\|\leq\epsilon} w_2x'.\] The intended idea is that \(x_1^*\) and \(x_2^*\) are two different adversarial examples derived from the same original sample \(x\), constructed against \(w_1\) and \(w_2\), respectively. Let \[\bar{x}=\begin{cases} x_2^* & if\quad w_1 x_1^*\geq w_2 x_2^* \\ x_1^* & if \quad w_1 x_1^*<w_2 x_2^* . \end{cases}.\] If \(w_1 x_1^*\geq w_2 x_2^*\), we have \(w_1x_1^*-w_2x_2^*\leq w_1x_2^*-w_2x_2^*=w_1 \bar{x}-w_2\bar{x}\). If \(w_1 x_1^*< w_2 x_2^*\), we have \(w_2x_2^*-w_1x_1^*\leq w_2x_1^*-w_1x_1^*=w_2 \bar{x}-w_1\bar{x}\). Combine these two inequalities, we have \[\label{eq:linear95perturb} \left| w_1 x_1^* - w_2 x_2^* \right| \leq \left| w_1 \bar{x} - w_2 \bar{x} \right| \leq \left| w_1 - w_2 \right| \left| \bar{x} \right| \leq \epsilon_w \left( B + \epsilon \right).\tag{4}\] The choice of \(\bar{x}\) in the two-dimensional case is illustrated in Figure 1. Consider the original sample \(x = (0,0)\). Given \(w_1\) and \(w_2\), the points \(x^*_1\) and \(x^*_2\) lie on the boundary of the \(\epsilon\)-ball in the directions opposite to \(w_1\) and \(w_2\), respectively. If we assume that the magnitude of \(w_1\) is larger than that of \(w_2\), then \(w_1^\intercal x^*_1 < w_2^\intercal x^*_2\) (In the two-dimensional case, \(wx\) becomes the inner product between \(w\) and \(x\)). Accordingly, we set \(\bar{x} = x^*_1\).

Therefore, the \(\zeta\)-cover of \(\tilde{\mathcal{F}}^\mathrm{binary}\) is no more than \(M/\epsilon_w = M(B+\epsilon) / \zeta\).

4.1.0.1 Remark 1.

This approach recovers the upper bound of ARC for linear functions, as established in [1], [2]. The main advantage of this approach is that it provides a bridge for computing the distance between two adversarial functions without requiring the closed-form solution of adversarial examples. Consequently, this method shows potential for extension to multi-layer neural networks. However, we will demonstrate an additional challenge prevents the direct application of this approach to multi-layer neural networks in the following subsection. Nevertheless, our proof reveals that the definition of \(\bar{x}\) is a crucial step. We refer to this as the intermediate adversarial example and present the corresponding lemma for general functions below.

4.2 Layer-wise Induction with Intermediate Adversarial Examples↩︎

We now return to the general multidimensional, multilayer, multiclass setting. While our approach successfully bounds the ARC for linear functions using intermediate adversarial examples, extending this method to DNNs presents inherent challenges. The primary difficulty arises from a fundamental conflict between the intermediate adversarial example approach and established methods for bounding DNN Rademacher complexity, such as layer peeling and covering number techniques. The conflict stems from the dynamic nature of intermediate adversarial examples: the point \(\bar{x}\) varies as we move from \((l-1)\)-layer to \(l\)-layer networks. This variability contradicts a key requirement of traditional methods, which rely on fixed inputs at each layer. We use the covering number approach by [12] to illustrate this challenge. Let \(X_i\) denote the fixed output of the \(i\)-th layer. The covering number of the hypothesis class \(\mathcal{H}\) is derived through induction, expressing the bound in Eq. 5 as a sum of covering numbers over matrix space of \(W_jx_{j-1}\). \[\label{eq:stddecomp} \ln \mathcal{N} \left( \mathcal{H}, \|\cdot\|_\mathcal{S}, \zeta \right) \leq \sum_{j=1}^l \sup_{\left( W_1, \dots, W_{j-1} \right)} \ln \mathcal{N} \left( \left\{ W_j x_{j-1} : \left\| W_j^\top \right\|_{2,1} \leq a_j \right\}, \|\cdot\|, \delta_j \right).\tag{5}\] for some \(\zeta\). In the adversarial setting, however, \(x_{j-1}\) is not fixed; it depends on both the weights of the preceding layers \((W_1,\ldots,W_{j-1})\) and the weights of subsequent layers \((W_j,\ldots,W_l)\). This interdependence between layers prevents the direct application of traditional covering number bounds to the adversarial setting. The same issue arises in the layer peeling approach, as detailed in Appendix 9. To address this challenge, we propose an alternative decomposition based on Lemma 1, which bounds the covering number of the adversarial hypothesis class using the covering number of the weight space.

The proof is based on Lemma 1, which provides the bridge for the layer-wise induction given in Appendix [lem:induction95of95layer]. Since the upper bound is expressed as a sum of covering numbers over the weight spaces \(W_j\) rather than the weight-input products \(W_jx_{j-1}\), it effectively resolves the issue of input dependency on subsequent layer weights.

5 Bounds for Adversarial Rademacher Complexity↩︎

5.1 Binary Classification↩︎

We begin by establishing bounds for the ARC in the binary classification setting.

The proof is based on bounding the Rademacher complexity using the covering number, which is known as Dudley’s integral. Specifically, we proceed as follows:

• We first establish an upper bound on the distance between two adversarial functions using Lemma 1 (Intermediate Adversarial Example).

• Next, we apply Lemma 2 to relate the covering number of the adversarial hypothesis class to the covering number of the weight norm.

• This reduces the problem to bounding the covering number of a norm ball, a well-established result in mathematical analysis.

The complete proof is provided in Appendix 8.

In the case of the \((1,\infty)\)-norm, the bound is similar to that of the Frobenius norm, except for the additional term \(\max\left\{1, d^{1/2 - 1/p} \right\}\). Therefore, for all \(p \geq 1\), the \((1,\infty)\)-norm bound maintains the same order as in Eq. (?? ).

We compare our bound to the bounds in similar settings. Specifically, we compare our bound with the covering number bounds for (standard) Rademacher complexity [12] and the bound of ARC in two-layer cases.

5.1.0.1 Covering Number Bound for Standard Rademacher complexity.

The work of [12] used a covering number argument to show that the generalization gap is bounded by \[\tilde{\mathcal{O}} \left( \frac{B \prod_{j=1}^l \left\| W_j \right\|}{\sqrt{n}} \left( \sum_{j=1}^l \frac{\left\| W_j \right\|_{2,1}^{2/3}}{\left\| W_j \right\|^{2/3}} \right)^{3/2} \right).\] Our bound differs in two key aspects. First, it includes an additional dependence on \(\epsilon\), which is unavoidable in adversarial settings. Second, as discussed in [26] and [11], the term \(\bigg(\sum_{j=1}^l\frac{\|W_j\|_{2,1}^{2/3}}{\|W_j\|^{2/3}}\bigg)\) admits the following bounds: \[l^{\frac{3}{2}} \leq \left( \sum_{j=1}^l \frac{\left\| W_j \right\|_{2,1}^{2/3}}{\left\| W_j \right\|^{2/3}} \right)^{3/2} \leq l^{\frac{3}{2}} h.\] On the other hand, our bound exhibits a dependence on network size of \(\mathcal{O}(\sqrt{l\log(l)}h)\). The main difference arises from the need for two distinct approaches to perform layer-wise induction in standard and adversarial settings. Compared to the upper bound on network size dependence in existing standard results, our bound maintains a comparable dependence on depth \(l\) and width \(h\).

5.1.0.2 Bound for ARC in Two-Layer Cases.

The work of [13] established that the ARC is bounded by \[\mathcal{O} \left( \frac{(B+\epsilon) \sqrt{h_1 d} \sqrt{\log n} M_1 M_2}{\sqrt{n}} \right)\] in the two-layer setting. Applying our bound to the two-layer case, we obtain \[\mathcal{O} \left( \frac{(B+\epsilon) \sqrt{h_1 d} M_1 M_2}{\sqrt{n}} \right),\] which is strictly tighter. Notably, under the same conditions for other factors, our bound exhibits a lower dependence on the sample size \(n\).

The proof is based on reducing the problem of lower bounding the ARC of DNNs to that of linear hypothesis classes, and it is provided in Appendix 8. For function classes with the \((1,\infty)\)-norm, ARC admits the same lower bound. From this bound, we observe a gap in depth \(l\) and width \(h\) between the upper and lower bounds, while the other terms remain unavoidable. In the next section, we extend the ARC analysis to multi-class classification.

5.2 Multi-Class Classification↩︎

The setting for multi-class classification follows [33]. In a K-class classification problem, let \(\mathcal{Y}=\left\{1,2,\cdots,K\right\}\). The functions in the hypothesis class \(\mathcal{F}\) map \(\mathcal{X}\) to \(\mathbb{R}^K\), the \(k\)-th output of \(f\) is the score of \(f(x)\) assigned to the \(k\)-th class.

Define the margin operator \(M(f(x),y)=[f(x)]_y-\max_{y'\neq y}[f(x)]_{y'}\), where \([f(x)]_y\) denotes the \(y\)-th output of \(f(x)\). The function makes a correct prediction if and only if \(M(f(x),y)> 0\). We consider a particular loss function \(\ell (f(x), y) = \phi_\gamma (M(f(x), y))\), where \(\gamma > 0\) and \(\phi_\gamma:\mathbb{R}\rightarrow [0,1]\) is the ramp loss: \[\label{eq:ramp} \phi_\gamma(t) = \begin{cases} 1 & t \le 0 \\ 1-\frac{t}{\gamma} & 0 < t < \gamma \\ 0 & t \ge \gamma. \end{cases}\tag{6}\] \(\phi_\gamma(t) \in [0,1]\) and \(\phi_\gamma(\cdot)\) is \(1/\gamma\)-Lipschitz. The loss function \(\ell (f(x), y)\) satisfies: \[\mathbb{1}\left( y \neq \arg\max_{y' \in [K]} \left[ f(x) \right]_{y'} \right) \leq \ell \left( f(x), y \right) \leq \mathbb{1}\left( \left[ f(x) \right]_y \leq \gamma + \max_{y' \neq y} \left[ f(x) \right]_{y'} \right).\] Define the function class \(\ell_{\mathcal{F}} := \left\{(x, y) \mapsto \phi_\gamma (M(f(x), y)) : f\in\mathcal{F}\right\}\). In adversarial training, the adversarial hypothesis class is defined as \[\label{eq:multi95function95class} \tilde{\mathcal{H}} := \left\{ (x, y) \mapsto \max_{x' \in \mathcal{B}(x)} \phi_\gamma \left( M \left( f(x'), y \right) \right) : f \in \mathcal{F}\right\},\tag{7}\] and assume \(0\in \tilde{\mathcal{H}}\). Then, the following generalization bound holds.

Using the same idea as in binary settings, we can calculate the covering number of the adversarial hypothesis class via intermediate adversarial examples. Then, we have the following bound for ARC.

The proof is based on the fact that \(\phi_\gamma(M(\cdot,y))\) is \(2/\gamma\)-Lipschitz, which is provided in Appendix 8. Notably, our bound does not introduce an additional coordinate-wise multiplicative factor in the number of classes \(K\). This should not be interpreted as saying that the bound is independent of \(K\). In the multiclass setting, the output dimension is \(h_l=K\), and the bound also depends on the last-layer norm constraint \(M_l\). Thus, the number of classes can affect the bound through the architecture and the norm constraints. The point is that our covering-number argument controls the multiclass adversarial loss class directly, rather than decomposing it into \(K\) scalar coordinate classes.

6 Experiments↩︎

6.1 Comparing Standard and Adversarial Rademacher Complexity↩︎

We now examine the relationship between the bounds for standard and adversarial Rademacher complexity. We begin by recalling the upper bound for standard Rademacher complexity from [11]: \[\label{eq:compare} \mathcal{R}_\mathcal{S}(\mathcal{H}) \leq \mathcal{O} \left( \frac{B \sqrt{l} \prod_{j=1}^l M_j}{\gamma \sqrt{n}} \right).\tag{8}\] Next, we categorize the factors in the bounds into two groups.

6.1.0.1 Algorithm-Independent Factors.

The bounds include five algorithm-independent factors: the number of samples \(n\), depth \(l\), width \(h\), sample size \(B\), and perturbation intensity \(\epsilon\). For notational convenience, we define \(C_{std} = B\sqrt{l}/\sqrt{n}\) and \(C_{adv} = (B+\epsilon)h\sqrt{l\log l}/\sqrt{n}\) as the constants for standard and adversarial Rademacher complexity, respectively. By definition, \(C_{adv} > C_{std}\).

6.1.0.2 Algorithm-Dependent Factors.

There are two remaining terms: the product of upper bounds on matrix norms, \(\prod_{j=1}^l M_j\), and the margin, \(\gamma\). By definition, these terms are independent of the algorithm. However, they are implicitly algorithm-dependent [12], [26], [34], with more discussion provided in Appendix 10.2.1. The bound is universal and holds for all neural networks with weights satisfying \(\|W_j\| \leq M_j\) for \(j = 1, \dots, l\). Conversely, once a neural network is trained with specific weight norms \(\|W_j\|\), we can set \(M_j = \|W_j\|\) for all \(j\), ensuring that the bound applies specifically to the trained network and is the tightest possible bound for it. Similarly, \(\gamma\) is set to the margin of the trained network. Thus, the two algorithm-dependent factors in the bound are the product of weight norms and the margin. We define the ratio \(W_{std} := \prod_{j=1}^l \|W_j\| / \gamma\) for standard training and \(W_{adv} := \prod_{j=1}^l \|W_j\| / \gamma\) for adversarial training. Our experimental results, presented in the next subsection and Appendix 10, consistently show that \(W_{adv} > W_{std}\).

6.1.0.3 Generalization Gap Analysis.

Let \(\mathcal{E}(\cdot)\) denote the standard generalization gap and \(\tilde{\mathcal{E}}(\cdot)\) represent the robust generalization gap. We use \(f_{std}\) and \(f_{adv}\) to denote models trained using standard and adversarial training, respectively. Our analysis aims to understand why adversarially trained models exhibit substantially larger robust generalization gaps compared to the standard generalization gaps of normally trained models (i.e., why \(\tilde{\mathcal{E}}(f_{adv})>\mathcal{E}(f_{std})\)). While prior work [35] has established that Rademacher complexity is large in these settings, we can still analyze the relationship between robust generalization gaps and our identified factors through the standard and ARC bounds:

\[\tilde{\mathcal{E}}(f_{adv})\propto C_{adv}W_{adv}\quad and \quad \mathcal{E}(f_{std})\propto C_{std}W_{std}.\]

Notably, the bounds apply universally to any model. We can analyze the standard Rademacher complexity bound for adversarially trained models, i.e., \(C_{std}W_{adv}\), and vice versa. To isolate the individual effects of factors \(C_{adv}\) and \(W_{adv}\), we examine two additional generalization gaps: the robust generalization gap of standard-trained models (\(\tilde{\mathcal{E}}(f_{std})\)) and the standard generalization gap of adversarially-trained models (\(\mathcal{E}(f_{adv})\)). These gaps help decompose the contributions of each factor: \[\tilde{\mathcal{E}}(f_{std})\propto C_{adv}W_{std}\quad and \quad \mathcal{E}(f_{adv})\propto C_{std}W_{adv}.\]

In the previous section, we identified the normalized product of weight norms \(\prod_{j=1}^l\|W_j\|/\gamma\) as a key algorithm-dependent factor in the ARC bounds. To empirically validate our theoretical analysis, we conducted extensive experiments comparing these terms between standard and adversarial training settings. Since our bounds generalize to convolutional neural networks, we evaluated VGG architectures [36] on both CIFAR-10 and CIFAR-100 datasets [37]. Our analysis encompasses 88 trained models, with additional experimental results provided in Appendix 10.

6.1.0.4 Training Protocol.

We employed SGD optimization with a three-stage learning rate schedule: 0.1 for the first 100 epochs, 0.01 for the next 50 epochs, and 0.001 for the final 50 epochs. Weight decay was primarily set to \(5\times 10^{-4}\), which was empirically determined to be optimal for robust accuracy, though we explored other values in ablation studies. For adversarial training, we implemented \(\ell_\infty\) PGD [7] with \(\epsilon=8/255\) perturbation intensity, using 20 steps during training and 40 steps during testing, with a step size of \(2/255\) for inner maximization.

6.1.0.5 Margin Computation.

Following [34], we defined margins differently for standard and adversarial training. For standard training, the margin was calculated as the 5th percentile of \(f(x_i)[y_i]-\max_{y\neq y_i} f(x)[y]\) across all training points. For adversarial training, we used the 5th percentile of margins computed on PGD-adversarial examples. Since both the standard-trained and adversarially-trained models achieved 100% training accuracy, the margins of all samples are positive. This ensures that the 5th percentile of margins is also positive. the Detailed ablation studies on percentile selection are presented in Appendix 10.3.

6.1.0.6 Higher Weight Norms in Adversarially-Trained Models.

Figure 2 compares weight norms between standard and adversarial training across VGG architectures on both CIFAR-10 and CIFAR-100 datasets². Using a logarithmic scale for visualization, our results consistently demonstrate that adversarially-trained models have larger weight norms than their standard-trained counterparts (\(W_{adv}\geq W_{std}\)). Additional ablation studies in Appendix 10 further confirm this relationship across different experimental conditions.

6.1.0.7 Analysis of Standard and Robust Generalization Gaps.

Table 2 presents standard and robust generalization gaps for both training approaches, using VGG-19 on CIFAR-10 as our primary example. Standard-trained models exhibit small standard generalization gaps (\(\mathcal{E}(f_{std})=10.45\%\)), while adversarially-trained models show larger standard generalization gaps (\(\mathcal{E}(f_{adv})=26.34\%\)). This increased gap aligns with the known phenomenon that adversarial training typically compromises standard generalization, possibly due to overfitting to adversarial examples. The robust generalization gap presents a striking contrast: standard-trained models show minimal robust generalization gaps (\(\tilde{\mathcal{E}}(f_{std})=0\)), but this is not indicative of good performance. Rather, it reflects uniformly poor robustness, with both training and test robust accuracy approaching 0%. Conversely, adversarially-trained models exhibit large robust generalization gaps (\(\tilde{\mathcal{E}}(f_{adv})=58.90\%\)). This substantial gap in robust generalization is a key phenomenon that we aim to analyze and explain.

6.1.0.8 Interpreting Zero Robust Generalization Gap in Standard Training.

Table 2 reveals that \(\tilde{\mathcal{E}}(f_{std})=0\%\) represents a degenerate case where standard-trained models achieve 100% robust training error, indicating complete failure to fit any adversarial examples in the training set. This renders both the generalization gap and its corresponding Rademacher complexity bound \(\tilde{\mathcal{E}}(f_{std})\leq\mathcal{O}(C_{adv}W_{std}/\sqrt{n})\) trivial. In contrast, the other three cases achieve near-zero training errors, providing meaningful generalization gaps. We focus our analysis on understanding why \(\tilde{\mathcal{E}}(f_{adv})>\mathcal{E}(f_{std})\) by examining the relationship \(\tilde{\mathcal{E}}(f_{adv})>\mathcal{E}(f_{adv})>\mathcal{E}(f_{std})\).

6.1.0.9 Impact of \(C_{adv}\) on Generalization Gaps.

Comparing generalization gaps for adversarially-trained models, we observe that the robust generalization gap significantly exceeds the standard generalization gap (\(\tilde{\mathcal{E}}(f_{adv})=58.90\% > \mathcal{E}(f_{adv})=26.34\%\)). Using Rademacher complexity bounds as approximations for these gaps, we can express this relationship as \(\tilde{\mathcal{E}}(f_{adv})\propto C_{adv}W_{adv}\) and \(\mathcal{E}(f_{adv})\propto C_{std}W_{adv}\). This suggests that \(C_{adv}\) directly contributes to the increased robust generalization gap, as it scales with the perturbation intensity \(\epsilon\).

6.1.0.10 Impact of \(W_{adv}\) on Standard Generalization.

When comparing standard generalization gaps, we observe that adversarially-trained models exhibit poorer generalization compared to standard training (\(\mathcal{E}(f_{adv})=26.34\% > \mathcal{E}(f_{std})=10.45\%\)). This widely observed degradation in standard generalization can be understood through Rademacher complexity bounds. Using these bounds as approximations (\(\mathcal{E}(f_{adv})\propto C_{std}W_{adv}\) and \(\mathcal{E}(f_{std})\propto C_{std}W_{std}\)), we can attribute the increased generalization gap to larger weight norms in adversarially-trained models (\(W_{adv}\)), demonstrating its positive correlation with generalization degradation.

The relationship between generalization gaps (\(\tilde{\mathcal{E}}(f_{adv})>\mathcal{E}(f_{adv})>\mathcal{E}(f_{std})\)) can be characterized by the corresponding complexity terms: \(C_{adv}W_{adv}> C_{std}W_{adv}>C_{std}W_{std}\). This analysis reveals that robust generalization challenges stem from two distinct sources: (1) an algorithm-independent component \(C_{adv}\), which is inherent to the minimax nature of adversarial training and thus unavoidable, and (2) an algorithm-dependent component \(W_{adv}\), reflecting increased weight norms in adversarially-trained models, which might be addressable through improved training techniques.

6.1.0.11 Role of Weight Decay.

Our analysis suggests that controlling weight norms could improve robust generalization. In Appendix 10.4, we investigate the effects of incrementally increasing weight decay. While larger weight decay values reduce weight norms and improve generalization, they also degrade training performance, revealing a fundamental trade-off between training accuracy and generalization. At weight decay of \(10^{-2}\), training fails completely, though notably, even in this regime, adversarially-trained models maintain larger weight norms than standard-trained models.

6.1.0.12 Neural Network Representation Capacity.

We hypothesize that the increased weight norms in adversarial training stem from fundamental representation requirements: neural networks with small weight norms appear insufficient to fit adversarial examples in the training set, forcing the optimization to converge to solutions with larger weight norms. However, as our analysis shows, these large-norm solutions typically exhibit poor generalization properties, leading to robust overfitting. While this hypothesis aligns with our observations, comprehensive validation would require large-scale experimentation beyond our current scope.

7 Conclusion↩︎

7.0.0.1 Limitation.

The main limitation is that norm-based bounds tend to be excessively large in practical scenarios. As shown in Figure 2, the bounds for VGG networks exceed \(10^9\) in experiments on the CIFAR-10 dataset. The key challenge is how to obtain tighter norm-based bounds in real-world settings, not only for adversarial robustness but also in standard scenarios. This remains an open problem.

We present the first bounds on adversarial Rademacher complexity for deep neural networks, providing new theoretical insights into robust generalization. Our analysis reveals that robust generalization challenges arise from two distinct sources: an algorithm-independent factor inherent to the adversarial setting, and an algorithm-dependent factor related to neural network weight norms. Through extensive empirical validation, we establish clear correlations between these factors and robust generalization performance. These findings open new directions for both theoretical research in understanding adversarial training and practical improvements in robust generalization methods.

8 Proofs of Technical Results↩︎

8.1 Proof of Lemma 1↩︎

8.2 Proof of Lemma [lem:induction95of95layer]↩︎

The proof of Lemma [lem:induction95of95layer] requires the following Lemma.

Now, we move the the proof of Lemma [lem:induction95of95layer].

8.3 Proof of Theorem 1 and 2↩︎

Before we provide the proof, we first introduce the Dudley’s integral.

This proposition is a well-established result in statistical learning theory, with detailed proofs available in standard references such as [38]. Using this relationship between covering numbers and Rademacher complexity, we can derive upper bounds on the Rademacher complexity of function class \(\mathcal{F}^\mathrm{binary}\) from its covering number bounds.

In the case of Frobenius norm ball of \(m\times k\) matrices, we have the dimension \(d=m\times k\) and \[\begin{align} \mathcal{N} \left( \mathcal{B}, \|\cdot\|_F, \zeta \right) \leq \left( \frac{3W}{\zeta} \right)^{m \times k}. \end{align}\] Now we move to the proof of Theorem 1 and 2.

8.4 Proof of Theorem 3↩︎

Let \(\rho(\cdot)\) be the identity activation function. The following discussion hods for both \(\ell_2\)-norm and \(\ell_{1,\infty}\) norm cases. The proof of the theorem is based on constructing a linear network. By the definition of Rademacher complexity, if \(\mathcal{H}'\) is a subset of \(\mathcal{H}\), then

\[\begin{align} \mathcal{R}_\mathcal{S}(\mathcal{H}') &=& \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h \in \mathcal{H}'} \sum_{i=1}^{n} \sigma_i h( x_i, y_i) \right] \\ &\leq& \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h \in \mathcal{H}} \sum_{i=1}^{n} \sigma_i h( x_i, y_i) \right]\\ &=& \mathcal{R}_\mathcal{S}(\mathcal{H}). \end{align}\]

This inequality follows directly from the fact that restricting the hypothesis class cannot increase the supremum in the definition of Rademacher complexity.

Therefore, it suffices to lower bound the complexity of \(\tilde{\mathcal{F}}^{\mathrm{binary}'}\) under a specific distribution \(\mathcal{D}\), where \(\tilde{\mathcal{F}}^{\mathrm{binary}'}\) is a subset of \(\tilde{\mathcal{F}}^\mathrm{binary}\). We define

\[\begin{align} \tilde{\mathcal{F}}^{\mathrm{binary}'} = \left\{ x \mapsto \inf_{\| x' - x\|_p \leq \epsilon} y M_l \cdot M_2 w^T x \mid w \in \mathbb{R}^q, \|w\|_2 \leq M_1 \right\}. \end{align}\] This formulation constrains the function class while maintaining a meaningful lower bound on its complexity.

We first prove that \(\tilde{\mathcal{F}}^{\mathrm{binary}'}\) is a subset of \(\tilde{\mathcal{F}}^{\mathrm{binary}}\). In \(\tilde{\mathcal{F}}^{\mathrm{binary}}\), we set the activation function \(\rho(\cdot)\) to be the identity mapping. Define

\[\begin{align} \label{eq:addconstraint} W_1 &=& \begin{bmatrix} w \\ 0 \\ \vdots \\ 0 \end{bmatrix} \in \mathbb{R}^{h_1 \times h_0}, \quad W_j = \begin{bmatrix} M_j & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 0 \end{bmatrix} \in \mathbb{R}^{h_j \times h_{j-1}}, \quad j = 2, \dots, l. \end{align}\tag{15}\]

Since \(\|W_j\| \leq M_j\), imposing the additional constraint in Eq. 15 on \(\tilde{\mathcal{F}}^{\mathrm{binary}}\) reduces it to \(\tilde{\mathcal{F}}^{\mathrm{binary}'}\), confirming that \(\tilde{\mathcal{F}}^{\mathrm{binary}'}\) is a subset of \(\tilde{\mathcal{F}}^{\mathrm{binary}}\).

To proceed, we need to establish a lower bound for the adversarial Rademacher complexity of linear hypothesis classes. This result follows from the work of [2], [13], which we state below.

The standard Rademacher complexity of linear hypothesis classes can be expressed as\[\mathcal{R}_S(\mathcal{G})=\frac{W}{m}\mathbb{E}_\sigma\|\sum_{i=1}^n\sigma_i x_i\|_{r*}.\] Let \(\| x_i\|=B\) with equal entries for \(i=1,\cdots,n\), by Lemma 3, we have \[\begin{align} \mathcal{R}_S(\mathcal{G})\geq\frac{W}{n}\mathbb{E}_\sigma|\sum_{i=1}^n\sigma_i|\max\{1,d^{1-\frac{1}{r}-\frac{1}{p}}\}B. \end{align}\] By Khintchine’s inequality, we know that there exists a universal constant \(c>0\) such that \[\begin{align} \mathbb{E}_\sigma|\sum_{i=1}^n\sigma_i|\geq c\sqrt{n}. \end{align}\] Then, we have \[\begin{align} \mathcal{R}_S(\mathcal{G})\geq\frac{cW}{\sqrt{n}}\max\{1,d^{1-\frac{1}{r}-\frac{1}{p}}\}B. \end{align}\] As discussed in [40], this lower bound is in tight in terms of dependence on sample size \(n\) and dimension \(d\). Therefore, \[\begin{align} \mathcal{R}_S(\tilde{\mathcal{G}})&\geq&\max\bigg\{\mathcal{R}_S(\mathcal{G}),\frac{\epsilon\max\{1,d^{1-\frac{1}{r}-\frac{1}{p}}\} W}{2\sqrt{n}}\bigg\}\\ &\geq&\frac{1}{1+2c}\mathcal{R}_S(\mathcal{G})+\frac{2c}{1+2c}\times\frac{\epsilon\max\{1,d^{1-\frac{1}{r}-\frac{1}{p}}\} W}{2\sqrt{n}}\\ &\geq&\frac{c}{1+2c}\bigg(\frac{(B+\epsilon)\max\{1,d^{1-\frac{1}{r}-\frac{1}{p}}\} W}{\sqrt{n}}\bigg). \end{align}\]

Let \(W=\prod_{j=1}^l M_j\), we have \[\begin{align} \mathcal{R}_S(\tilde{\mathcal{F}}^{\mathrm{binary}}) \geq\Omega\bigg(\frac{\max\{1,d^{1-\frac{1}{r}-\frac{1}{p}}\}(B+\epsilon)\prod_{j=1}^l M_j}{\sqrt{n}}\bigg), \end{align}\] where \(r=2\) for frobenius norm bound and \(r=1\) for \(\|\cdot\|_{1,\infty}\)-norm bound.

8.5 Proof of Theorem 4↩︎

9 Discussion on Existing Methods for Rademacher Complexity↩︎

In this section, we review existing approaches for calculating Rademacher complexity, examine related work in the field, and highlight the challenges in analyzing adversarial Rademacher complexity.

9.1 Existing Bounds for Standard Rademacher Complexity↩︎

9.1.0.1 Layer Peeling Technique.

The Rademacher complexity of multi-layer neural networks is primarily calculated using the ‘layer peeling’ technique [10]. For a function class \(\mathcal{F}\) and function \(g\), we define the composition \(g\circ\mathcal{F}\) as \(\{g\circ f| f\in\mathcal{F}\}\). Talagrand’s Lemma establishes that \(\mathcal{R}_\mathcal{S}(g\circ f)\leq L_g \mathcal{R}_\mathcal{S}(\mathcal{F})\). Applying this result to neural networks, we can show that \(\mathcal{R}_\mathcal{S}(\mathcal{F}_{l})\leq 2L_\rho M_j \mathcal{R}_\mathcal{S}(\mathcal{F}_{l-1})\), where \(\mathcal{F}_{l}\) represents the function class of \(l\)-layer neural networks. Since the Rademacher complexity of a linear function class is bounded by \(\mathcal{O}(BM_1/\sqrt{n})\), induction yields an upper bound of \(\mathcal{O}(B2^l L_\rho^{l-1}\prod_{j=1}^lM_j/\sqrt{n})\). For activation functions like ReLU where \(L_\rho=1\), we can simplify this bound by eliminating the \(L_\rho\) term.

[11] achieves an improved bound by reducing the depth dependence from \(2^l\) to \(\sqrt{l}\). Their key insight involves reformulating the Rademacher complexity expression \(\mathbb{E}_\sigma[\cdot]\) as \(\mathbb{E}_\sigma\exp\ln[\cdot]\). This transformation allows for layer peeling to be performed within the \(\ln(\cdot)\) function, effectively containing the exponential \(2^l\) term inside the logarithm and yielding the improved \(\sqrt{l}\) dependence.

9.1.0.2 Covering Number.

[12] established a generalization gap bound using covering numbers: \[\begin{align} \tilde{\mathcal{O}}\bigg(\frac{B\prod_{j=1}^l\|W_j\|}{\sqrt{n}}\bigg(\sum_{j=1}^l\frac{\|W_j\|_{2,1}^{2/3}}{\|W_j\|^{2/3}}\bigg)^{3/2}\bigg), \end{align}\] where \(\|\cdot\|\) denotes the spectral norm. Their proof employs layer-wise induction: for each layer \(j\), let \(W_j\) represent the layer’s weight matrix and \(X_j\) denote the network’s output after processing through layers 1 to \(j-1\). The bound is derived by inductively computing the matrix covering number \(\mathcal{N}(\{W_jX_j\},\|\cdot\|_2,\epsilon)\) for each layer.

9.2 Existing Bounds for Rademacher Complexity on Surrogate Loss↩︎

For linear models, ARC bounds can be derived directly from its definition [1], [2]. However, extending these analyses to multi-layer networks presents additional challenges. We begin by examining approaches that utilize surrogate loss functions.

9.2.0.1 Tree Transformation Loss.

[1] introduced a tree transformation \(T\) and demonstrated that \(\max_{\|x-x'\|\leq \epsilon}\ell(f( x),y)\leq\ell(Tf( x),y)\). This leads to an upper bound on the adversarial population risk. Specifically, for any \(\delta\in(0,1)\): \[\begin{align} \tilde{R}(f)\leq R(Tf)\leq R_n(Tf)+2L\mathcal{R}_S(T\circ\mathcal{F})+3\sqrt{\frac{\log\frac{2}{\delta}}{2n}}, \end{align}\]

where \(R_n(Tf)\) represents the empirical risk of the transformed function, \(\mathcal{R}_S(T\circ\mathcal{F})\) is the Rademacher complexity of the transformed function class, and \(L\) is the Lipschitz constant. This result bounds the robust population risk in terms of empirical risk and the standard Rademacher complexity of the transformed function class \(T\circ\mathcal{F}\). While \(\mathcal{R}_S(T\circ\mathcal{F})\) serves as an approximation of adversarial Rademacher complexity, this bound has two key limitations: the empirical risk term \(R_n(Tf)\) differs from the objective used in practical adversarial training, and the bound does not directly characterize the robust generalization gap between training and test performance.

9.2.0.2 SDP Relaxation Surrogate Loss.

In [2], the authors introduced an SDP surrogate loss to approximate the adversarial loss for two-layer neural networks. This surrogate loss is defined as: \[\begin{align} \hat{\ell}(f( x),y)=\phi_\gamma\bigg(M(f( x),y)-\frac{\epsilon}{2}\max_{k\in [K],z=\pm 1}\max_{P\succeq0, diag(P)\leq 1}\langle zQ(w_{2,k},W_1),P\rangle\bigg). \end{align}\] Using this formulation, the adversarial Rademacher complexity can be approximated by computing the Rademacher complexity of this surrogate loss function. However, this approach shares the same limitations as the previously discussed method, as it still does not directly characterize the robust generalization gap between training and test performance.

9.2.0.3 FGSM Attack Loss.

[14] analyzed Rademacher complexity in the adversarial setting by focusing on Fast Gradient Sign Method (FGSM) adversarial examples to handle the \(\max\) operation in the adversarial loss. Under specific gradient assumptions, they derived an upper bound for the adversarial Rademacher complexity using the loss \(\ell(f(x_\text{FGSM}),y)\). Their analysis requires that \(|\nabla \ell(f(x),y)|\geq\kappa\) holds for all \(x\) in the domain, where \(\kappa\) appears in the denominator of their final bound. This assumption proves problematic for two reasons: first, it is a strong condition that may not hold in practice, and second, the bound becomes unbounded as \(\kappa\) approaches zero. Moreover, since their approach modifies the original loss function, it cannot provide guarantees on the robust generalization gap.

9.3 Layer Peeling Technique for ARC↩︎

We first briefly introduce the layer peeling technique in standard settings. \[\begin{align} \mathcal{R}_\mathcal{S}(\mathcal{H}) &=& \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h \in \mathcal{H}} \sum_{i=1}^{n} \sigma_i h( x_i) \right] \\ &=& \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h' \in \mathcal{H}_{l-1}, \|W_l\| \leq M_l} \sum_{i=1}^{n} \sigma_i W_l \rho(h'( x_i)) \right] \\ &\leq& M_l \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h' \in \mathcal{H}_{l-1}} \left\| \sum_{i=1}^{n} \sigma_i \rho(h'( x_i)) \right\| \right] \\ &\leq& 2 M_l L_\rho \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h' \in \mathcal{H}_{l-1}} \sum_{i=1}^{n} \sigma_i h'( x_i) \right] \\ &=& 2 M_l L_\rho \mathcal{R}_\mathcal{S}(\mathcal{H}_{l-1}). \end{align}\] In adversarial settings, if we directly apply the layer peeling technique, we have \[\begin{align} \mathcal{R}_\mathcal{S}(\tilde{\mathcal{H}}) &=& \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h \in \mathcal{H}} \sum_{i=1}^{n} \sigma_i \max_{\| x_i - x_i' \| \leq \epsilon} h( x_i') \right] \\ &=& \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h' \in \mathcal{H}_{l-1}, \|W_l\| \leq M_l} \sum_{i=1}^{n} \sigma_i W_l \rho(h'( x_i^*(h))) \right] \\ &\leq& M_l \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h' \in \mathcal{H}_{l-1}} \left\| \sum_{i=1}^{n} \sigma_i \rho(h'( x_i^*(h))) \right\| \right] \\ &\leq& 2 M_l L_\rho \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h' \in \mathcal{H}_{l-1}} \sum_{i=1}^{n} \sigma_i h'( x_i^*(h)) \right] \\ &\neq& 2 M_l L_\rho \mathbb{E}_\sigma \frac{1}{n} \left[ \sup_{h' \in \mathcal{H}_{l-1}} \sum_{i=1}^{n} \sigma_i h'( x_i^*(h')) \right] \\ &=& 2 M_l L_\rho \mathcal{R}_\mathcal{S}(\tilde{\mathcal{H}}_{l-1}). \end{align}\]

where \(x_i^*(h)\) and \(x_i^*(h')\) denote the optimal adversarial examples for \(l\)-layer and \((l-1)\)-layer neural networks, respectively. Since \(x_i^*(h) \neq x_i^*(h')\) in general, the optimal adversarial examples differ between architectures of different depths, which prevents the direct extension of layer peeling techniques to the adversarial setting.

9.4 Comparison of Adversarial Generalization Bounds↩︎

9.4.0.1 VC-Dimension Bounds.

The VC dimension is a fundamental tool in statistical learning theory for bounding generalization gaps. Several works, including [41], [25], and [24], have extended this framework to the adversarial setting. However, these approaches fail to provide computable bounds on the adversarial generalization gap, as we explain below. Let \(\mathcal{H}\) denote the hypothesis class (for example, the set of neural networks with a fixed architecture).

[41] introduced the concept of adversarial VC dimension (AVC) and established bounds on the adversarial generalization gap in terms of \(\text{AVC}(\mathcal{H})\). However, they did not provide methods to compute the AVC for neural networks, thus leaving their bounds non-computable in practice.

[25] took a different approach by defining an adversarial function class \(\mathcal{L}_{\mathcal{H}}^{\mathcal{U}}\), where \(\mathcal{L}\) represents the loss function and \(\mathcal{U}\) denotes the uncertainty set. While their bound on the adversarial generalization gap using \(\mathcal{L}_{\mathcal{H}}^{\mathcal{U}}\) differs from the \(\text{AVC}(\mathcal{H})\) approach of [41], they similarly did not provide a method to compute their bound, rendering it non-computable in practice.

[24] analyze the case where the perturbation set \(U(x)\) is finite, containing exactly \(k\) possible adversarial examples for each sample \(x\). Under this assumption, they bound the adversarial generalization gap by: \[\begin{align} \mathcal{O} \left( \frac{1}{\zeta^2} \left( \sqrt{k \cdot VC(\mathcal{H})} \log \left( \frac{3}{2} + a \right) k \cdot VC(\mathcal{H}) \right) + \log \frac{1}{\delta} \right). \end{align}\] Since \(\text{VC}(\mathcal{H})\) can be upper-bounded by the number of network parameters, this result provides a computable bound, improving upon previous approaches. However, this computability comes with a significant limitation: the bound depends on \(k\), the number of allowed perturbed samples, which deviates from the standard notion of adversarial generalization where \(U(x)\) is an infinite set. In contrast, our bound applies to the original adversarial generalization framework where \(U(x)\) is infinite (\(k=+\infty\)).

9.4.0.2 Adversarial Generalization in Alternative Settings.

Several studies have explored adversarial generalization in specific model architectures. [31] analyzed generalization properties in linear regression, while multiple researchers [31], [42], [43] investigated adversarial generalization using Gaussian mixture models. Studies on uniform stability in adversarial training [44]–[48] suggest that poor generalization may result from the non-smooth nature of adversarial loss functions.

9.4.0.3 Related Work on Regularization and Robustness.

The connection between robustness and regularization has been widely studied in the literature. A line of work has explored Jacobian regularization, where robustness is promoted by directly penalizing the sensitivity of model outputs to input perturbations [49]–[52]. Another line has investigated weight regularization, where robustness emerges from penalizing the norm of the model parameters [29], [53], Blanchet2019robust?. Since weight decay is equivalent to \(\ell_2\) regularization, our results naturally relate to this literature, suggesting that weight decay not only controls model capacity but may also contribute to adversarial robustness. We highlight these connections to situate our contribution within the broader context of robustness through regularization. Related work by Xing and collaborators investigates adversarial robustness through robust statistics, generalization theory, training dynamics, and minimax analysis, covering topics such as robust linear regression, the generalization behavior of adversarial training, phase transitions from clean to adversarial training, and the benefit of unlabeled data for robustness [54]–[57].

9.4.0.4 Certified Robustness.

Research on certified robustness focuses on guaranteeing model performance within norm-constrained neighborhoods of training data. [58] developed certification methods through random smoothing, while [59] approached certification through differential privacy frameworks.

9.4.0.5 Geometric Perspectives on Adversarial Examples.

Several works have examined the geometric properties of adversarial examples [60], [61]. The off-manifold hypothesis, first proposed by [5], suggests that adversarial examples deviate from the underlying data manifold. Supporting this view, [62] demonstrated using generative models that adversarial examples typically occupy low-probability regions of the data distribution. Similarly, [63] employed Local Intrinsic Dimensionality (LID) to show that adversarial subspaces are both low-probability and distinct from the data submanifold.

10 Additional Experiments↩︎

In this section, we present additional experimental results to further validate our theoretical findings and explore their implications.

10.1 Experiments on VGG Architectures↩︎

Figure 3 presents experimental results for VGG-11 and VGG-13 architectures, while Figure 4 demonstrates findings for VGG-16 and VGG-19. Our analysis reveals a substantial difference in the product of Frobenius norms between standard and adversarial training methods, which corresponds to poor generalization performance in the adversarial setting.

10.1.0.1 \(\|\cdot\|_{1,\infty}\)-Norm Bounds.

The \(\|\cdot\|_{1,\infty}\)-norm bounds are shown in Figure 5. Similar the the Frobenius norm bounds,The gap of \(\prod_{j=1}^l\|W_j\|_{1,\infty}\) between adversarial training and standard training are large. But the magnitude of \(\prod_{j=1}^l\|W_j\|_{1,\infty}\) is larger than the magnitude of \(\prod_{j=1}^l\|W_j\|_F\).

10.2 Ablation Study on Margin Distribution↩︎

10.2.1 Discussion of optimizing over Gamma↩︎

By definition, these terms are independent of the algorithm. However, they are implicitly algorithm-dependent [12], [26]. The optimization over the margin parameter \(\gamma\) is standard in empirical evaluations of margin-based generalization bounds. For example, [12] derive a spectrally-normalized margin bound based on Rademacher-complexity arguments and empirically evaluate the bound as a function of the normalized margin. The experiment is reported in Figure 1 in their paper. Similarly, [34] empirically compute and compare several generalization bounds, including Rademacher-complexity-based norm bounds and spectrally-normalized margin bounds. Their public implementation³ reports the following bounds:

10.2.2 Results↩︎

Figure 6 illustrates the margin distributions at the 1st, 3rd, and 5th percentiles of the training dataset. As the robust training accuracy reaches 100%, the choice of percentile does not significantly impact our analysis. Across all percentiles, standard training consistently achieves larger margins compared to adversarial training. Since margins appear in the denominator of the Rademacher complexity upper bound, these smaller margins in adversarial training contribute, albeit modestly, to its poorer generalization performance.

10.3 Experiments on CIFAR-100↩︎

10.3.0.1 Performance Analysis.

Table 4 presents comparative results between standard and adversarial training on CIFAR-100 using VGG-16 and VGG-19 architectures. Our experiments reveal that the standard CIFAR-100 training set size of 50,000 samples is insufficient to effectively train VGG networks to acceptable performance levels. This limitation makes it challenging to analyze weight norm trends through CIFAR-100 experiments. Nevertheless, we compare the product of weight norms between standard and adversarial training methods to gain insights into their relative behaviors.

10.3.0.2 Product of Weight Norms.

Figure 7 presents the training results for VGG-16 and VGG-19 architectures on CIFAR-100. Consistent with our CIFAR-10 experiments, adversarially trained models exhibit significantly larger weight norms compared to their standard-trained counterparts.

10.4 Weight Decay↩︎

Theoretical upper bounds on adversarial Rademacher complexity suggest that adding weight regularization (weight decay) can improve generalization performance. We experimentally validate this theoretical insight in Figure 8, comparing adversarial training with and without weight decay. The results in Figures 8 (a) and (c) demonstrate that incorporating weight decay reduces the robust generalization gap. Additionally, Figures 8 (b) and (d) show that adversarial training with weight decay yields smaller weight norm products. These experimental findings establish a clear empirical connection between the robust generalization gap and weight norm products, supporting our theoretical analysis.

In Figure 9, we examine the effect of weight decay values ranging from \(1\times 10^{-3}\) to \(9\times 10^{-3}\). The training error increases with higher weight decay values. At low weight decay (\(1 \times 10^{-3}\)), the model achieves minimal training error, indicating a high capacity to fit the training data. However, as weight decay increases, the model’s flexibility is constrained, leading to higher training errors. This behavior aligns with the regularization effect of weight decay, which penalizes large weights and reduces the model’s ability to overfit. At very high weight decay values (\(9 \times 10^{-3}\)), the model risks underfitting, as excessive regularization prevents it from capturing meaningful patterns in the data.

The Frobenius norm of the model weights decreases monotonically with increasing weight decay. This trend reflects the direct impact of weight decay on the optimization process, where larger decay values impose stricter penalties on weight magnitudes. The reduction in the Frobenius norm indicates a simplification of the model, which is a key objective of regularization. However, excessively small weight magnitudes can lead to underfitting, highlighting the need for careful tuning of the weight decay parameter.

The generalization gap, defined as the difference between training and test performance, demonstrates a non-linear relationship with weight decay. At low weight decay values, the gap is large, indicating poor generalization due to overfitting. As weight decay increases, the gap narrows, reaching a minimum at intermediate values (e.g., \(3 \times 10^{-3}\) to \(7 \times 10^{-3}\)). This reduction in the gap signifies improved generalization, as the model achieves a better balance between fitting the training data and maintaining performance on unseen data. At very high weight decay values, the gap may stabilize or slightly increase, as both training and test performance degrade due to underfitting.

In conclusion, the results highlight the trade-offs associated with weight decay. Model performance deteriorates significantly within this range. At weight decay values of \(6\times 10^{-3}\) and higher, the margin becomes negative, indicating high training error. Subsequently, the weight norm to margin ratio also becomes negative. At \(9\times 10^{-3}\), the model fails to learn entirely, with both training and test errors reaching 90%. Our analysis suggests the optimal weight decay range for minimizing weight norm lies between \(1\times 10^{-3}\) and \(5\times 10^{-3}\). The smallest weight norm observed was \(6.01\times 10^{12}\) (with weight decay = \(4\times 10^{-3}\)). However, this value remains larger than the weight norm achieved through standard training (\(1.90\times 10^{12}\)). These findings emphasize the importance of selecting an appropriate weight decay value to achieve robust model performance.

References↩︎

---

1. Corresponding Author.↩︎

2. While larger models naturally exhibit higher weight norms due to their increased parameter count, our focus is on the relative difference between adversarially-trained and standard-trained models.↩︎

3. https://github.com/bneyshabur/generalization-bounds.↩︎