# ADVERSARIAL RADEMACHER COMPLEXITY OF DEEP NEURAL NETWORKS

**Anonymous authors**
Paper under double-blind review

ABSTRACT

Deep neural networks are vulnerable to adversarial attacks. Adversarial training is
one of the most effective algorithms to increase the model’s robustness. However,
the trained models cannot generalize well to the adversarial examples on the test
set. In this paper, we study the generalization of adversarial training through
the lens of adversarial Rademacher complexity. Current analysis of adversarial
Rademacher complexity is up to two-layer neural networks. In adversarial settings,
one major difficulty of generalizing these results to deep neural networks is that
we cannot peel off the layer as the classical analysis for standard training. We
provide a method to overcome this issue and provide upper bounds of adversarial
Rademacher complexity of deep neural networks. Similar to the existing bounds
of standard Rademacher complexity of neural nets, our bound also includes the
product of weight norms. We provide experiments to show that the adversarially
trained weight norms are larger than the standard trained weight norms, thus
providing an explanation for the bad generalization performance of adversarial
training.

1 INTRODUCTION

Deep neural networks (DNNs) (Krizhevsky et al. (2012); Hochreiter & Schmidhuber (1997)) have
become successful in many machine learning tasks such as computer vision (CV) and natural language
processing (NLP). But they are shown to be vulnerable to adversarial examples (Szegedy et al. (2013);
Goodfellow et al. (2014)). A well-trained model can be easily attacked by adding a small perturbation
to the original data. Adversarial training is one of the most effective algorithms to defend against
adversarial attacks. However, generalization is one of the main issues of adversarial training. An
adversarially-trained model will overfit the adversarial examples on the training dataset, and it cannot
generalize well to the adversarial examples on the testset. For example, in the experiment of training
ResNet (He et al. (2016)) on CIFAR-10 (Krizhevsky et al. (2009)), Projected gradient descent (PGD)
adversarial training achieves 100% robust accuracy on the training set, but it only gets 45% robust
accuracy on the test set (Madry et al. (2017)). Recent works (Gowal et al. (2020); Rebuffi et al.
(2021)) mitigate the overfitting issue, but it still has a 20% generalization gap between robust test
accuracy (60%) and training accuracy (80%). On the other hand, a standard trained model can
generalize well to the test set with a 5% generalization gap. To understand why the generalization of
adversarial training behaves differently from standard training, we study the generalization issue of
adversarial training through the lens of Rademacher complexity.

In classical machine learning theory, Rademacher complexity measures the generalization capacity
of machine learning models. For depth-d neural networks, assuming that the weight matrices
_W1, W2, · · ·, Wd in each of the d layers have Frobenius norms bounded by M1, · · ·, Md, and all_
the data x have ℓ2-norm bounded by B, given m training samples, the generalization gap between
population risk and empirical risk scales as O(B2[d][ Q][d]l=1 _[M][l][/][√][m][)][ with high probability (Neyshabur]_
et al. (2015)). Another works provide different norm-based complexity, such as ∥· ∥1,∞-norm
(Bartlett & Mendelson (2002)) and spectral norm (Bartlett et al. (2017)). The work of (Golowich
et al. (2018)) reduces the dependence on depth-d from 2[d] to _√d. The proofs of the above bounds are_

based on the induction on layers, which is also called the ‘peeling off’ techniques. For more details,
see section 3.


-----

In adversarial training, adversarial Rademacher complexity was first introduced in (Yin et al. (2019);
Khim & Loh (2018)) to measure the robust generalization gap. They prove that the robust generalization gap of linear function (x → _w[T]_ **_x) scales as O((B + ϵ)M/[√]m), where M is the upper bound of_**
norm of the weights w and ϵ is the perturbation intensity of adversarial attacks. Awasthi et al. (2020)
provides an upper bound in two-layers neural network cases. For depth-2, width-h neural networks,
with high probability, the generalization gap scales as ((B + ϵ)[√]hqM1M2 log m/m), where q
_O_

is the dimension of the data x.

p

One might think it is straightforward to use the induction methods in (Neyshabur et al. (2015);
Golowich et al. (2018)) to extend the adversarial Rademacher complexity in (Yin et al. (2019); Khim
& Loh (2018)) to multi-layers cases. However, it seems challenging to apply their induction methods
to adversarial cases. Let the adversarial loss be max∥x−x′∥≤ϵ ℓ(f (x[′]), y) and f is a DNN. We cannot
peel off the layer because of the max operation in the adversarial loss. The work of (Khim & Loh
(2018)) and (Gao & Wang (2021)) also indicate the difficulty of analyzing adversarial Rademacher
complexity of DNNs. They analyze other variants of adversarial Rademacher complexity, which are
quite different from the original adversarial Rademacher complexity. See more detailed discussions
of these works in section 3. To our knowledge, direct analysis of the original adversarial Rademacher
complexity is largely missing.

In this paper, we analyze the adversarial Rademacher complexity of deep neural networks. Specifically,
for depth-d, width-h fully connected neural networks, with high probability, the robust generalization
gap scales as

_d_
(B + ϵ)h√d log d _l=1_ _[M][l]_
_O_ _√m_ _._

Similar to the existing bounds of standard Rademacher complexity of deep neural nets, the bound Q 
includes the product of weight norms _l=1_
empirically show that the adversarially trained weight norms are larger than the standard trained[∥][W][l][∥][, but they are trained by different algorithms. We]
weight norms, which provide an explanation why adversarial training did not generalize well. Our

[Q][d]
contributions are listed as follow:

1. We provide a method and give upper and lower bounds for the adversarial Rademacher
complexity of deep neural nets. Compared to standard Rademacher complexity, the bound
has a higher-order dependence on the depth and width and an additional factor ϵ.

2. We provide experiments to analyze the relationship between the generalization gap and
the adversarial Rademacher complexity. We show that one of the reasons why adversarial
training cannot generalize well is the large weight norms of an adversarially-trained model.

2 PRELIMINARIES

2.1 GENERALIZATION GAP AND RADEMACHER COMPLEXITY

**Generalization Gap.** We start from the classical machine learning framework. Let F be the
hypothesis class (e.g. Linear functions, Neural networks). The goal of the learning problem is to find
_f_ to minimize the population risk R(f ) = E(x,y) [ℓ(f (x), y)], where is the true distribution,
_∈F_ _∼D_ _D_
_ℓ(_ ) is the loss function. Since is unknown, we minimize the empirical risk in practice. Given m

_·_ _D_ _m_
i.i.d samples S = (x1, y1), _, (xm, ym)_, the empirical risk is Rm(f ) = _m[1]_ _i=1[[][ℓ][(][f]_ [(][x][i][)][, y][i][)]][.]
_{_ _· · ·_ _}_

The generalization gap or generalization error is defined as follow:
P

Generalization Gap := R(f ) _Rm(f_ ).
_−_

**Rademacher Complexity.** A classical measure of the generalization error is Rademacher complexity (Bartlett & Mendelson (2002)). Given the hypothesis class H, the (empirical) Rademacher
complexity is defined as

_m_

1
( ) = Eσ sup _σih(xi, yi)_ _,_
_RS_ _H_ _m_ _h_

_∈H_ _i=1_
 X 

where σi are i.i.d Rademacher random variables, i.e. σi equals to 1 or −1 with equal probability.
Define the function class ℓ = _ℓ(f_ (x), y) _f_, we have the following generalization bound.
_F_ _{_ _|_ _∈F}_


-----

**Proposition 1. (Mohri et al. (2018); Bartlett & Mendelson (2002)) Suppose that the range of the loss**
_function ℓ(f_ (x), y) is [0, C]. Then, for any δ ∈ (0, 1), with probability at least 1 − _δ, the following_
_holds for all f ∈F,_

_R(f_ ) ≤ _Rm(f_ ) + 2CRS (ℓF ) + 3Cs log2m [2]δ _[.]_

2.2 ROBUST GENERALIZATION GAP AND ADVERSARIAL RADEMACHER COMPLEXITY

**Robust Generalization Gap.** Let _ℓ[˜](f_ (x), y) := max∥x′−x∥p≤ϵ ℓ(f (x[′]), y) be the adversarial loss.
The adversarial population risk and the adversarial empirical risk are


_R˜(f_ ) = E(x,y) max _and_ _R˜m(f_ ) = [1]
_∼D_ _x[′]_ _x_ _p_ _ϵ_ _[ℓ][(][f]_ [(][x][′][)][, y][)] _m_
_∥_ _−_ _∥_ _≤_


max _i[)][, y][i][)][,]_
_x[′]_ _x_ _p_ _ϵ_ _[ℓ][(][f]_ [(][x][′]
_i=1_ _∥_ _−_ _∥_ _≤_

X


respectively. In this paper we consider general ℓp attacks for p ≥ 1. The robust generalization gap is
defined as follow:
Robust Generalization Gap := R[˜](f ) _Rm(f_ ).
_−_ [˜]

Let the adversarial hypothesis class be _ℓ[˜]_ = _ℓ(f_ (x), y) _f_, according to Proposition 1, we
_F_ _{[˜]_ _|_ _∈F}_
have the following adversarial generalization bound.

**Proposition 2. (Yin et al. (2019)) Suppose that the range of the loss function** _ℓ[˜](f_ (x), y) is [0, C].
_Then, for any δ ∈_ (0, 1), with probability at least 1 − _δ, the following holds for all f ∈F,_


log [2]δ

2m [.]


_R˜(f_ ) ≤ _R[˜]m(f_ ) + 2CRS (ℓ[˜]F ) + 3C


**Binary Classification.** We first discuss the binary classification case, then we discuss the extension
to the multi-class classification case in section 5. Following (Yin et al. (2019); Awasthi et al. (2020)),
we assume that the loss function can be written as ℓ(f (x), y) = φ(yf (x)) where φ is a non-increasing
function. Then
max
**_x[′][ ℓ][(][f]_** [(][x][′][)][, y][) =][ φ][(min]x[′][ yf] [(][x][′][))][.]

Assume that the function φ is Lφ-Lipschitz, by Talagrand’s Lemma (Ledoux & Talagrand (2013)),
we have RS (ℓ[˜]F ) ≤ _LφRS_ ( F[˜]), where we define the adversarial function class as

˜ = _f[˜] : (x, y)_ inf (1)
_F_ _{_ _→_ **_x_** **_x[′]_** _p_ _ϵ_ _[yf]_ [(][x][′][)][|][f][ ∈F}][.]
_∥_ _−_ _∥_ _≤_

**Adversarial Rademacher Complexity.** We define RS( F[˜]) as adversarial Rademacher complexity.
Our goal is to give upper bounds for adversarial Rademacher complexity. Then, it induces the
guarantee of the robust generalization gap.

**Hypothesis Class.** We consider depth-d, width-h fully-connected neural networks,

_F = {x →_ _Wdρ(Wd−1ρ(· · · ρ(W1x) · · · )), ∥Wl∥≤_ _Ml, l = 1 · · ·, d},_ (2)

where ρ( ) is an element-wise Lρ-Lipschitz activation function, Wl are hl _hl_ 1 matrices, for
_l = 1, · · ··, d. We have hd = 1 and h0 = q is the dimension of the data x. Let h × = max−_ _{h0, · · ·, hd}_
be the width of the neural networks. Convolution neural networks are also included in this hypothesis
class because convolution layer can be viewed as a special form of fully-connected layer. 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,
Frobenius norm and ∥· ∥1,∞-norm in equation (2). Additionally, we assume that ∥X∥p,∞ = B.

2.3 RADEMACHER COMPLEXITY AND COVERING NUMBER

**Covering Number.** Our solution for adversarial Rademacher complexity is based on the covering
number. We first provide the definition of covering number.


-----

**Definition 1 (ε-cover). Let ε > 0 and (V,d(·, ·)) be a metric space, where d(·, ·) is a (pseudo)-metric.**
_C ⊂_ _V is an ε-cover of V, if for any v ∈_ _V, there exists v[′]_ _∈C s.t. d(v, v[′]) ≤_ _ε. Define the smallest_
_|C| as ε-covering number of V and denote as N_ (V, d(·, ·), ε).

Next, we define the ε-covering number of a function class . Given the sample dataset S =
1 _Fm_
(x1, y1), _, (xm, ym)_ with xi R[d], let _f_ _S_ [=] _m_ _i=1_ _[f]_ [(][x][i][, y][i][)][2][ be a pseudometric of]
_{_ . Define the · · · _ε-covering number of}_ _∈_ be _∥(_ _∥[2],_ _S, ε). Let D be the diameter of_ with

_FD = 2 maxf_ _∈F ∥f_ _∥S._ _F_ _N_ _F_ _∥· ∥_ P _F_
**Proposition 3 (Dudley’s integral). The Rademacher complexity R(F) satisfiy**

_D/2_

_S(_ ) log ( _,_ _S, ε)dε._
_R_ _F_ _≤_ _√[12]m_ 0 _N_ _F_ _∥· ∥_

Z

p

The proof of Dudley’s integral can be found in statistic textbooks (e.g. (Wainwright (2019))). Based
on this, we can bound the covering number of the function class F to give an upper bound of the
Rademacher complexity.

3 RELATED WORK

**Adversarial Attacks and Defense.** Starting from the work of (Szegedy et al. (2013)), it has now
been well known that deep neural networks trained via standard gradient descent based algorithms
are highly susceptible to imperceptible corruptions to the input data (Goodfellow et al. (2014); Chen
et al. (2017); Carlini & Wagner (2017); Madry et al. (2017)). This has led to a series of work aimed at
training neural networks robust to such perturbations (Wu et al. (2020); Gowal et al. (2020); Wu et al.
(2020)) and works aimed at designing more sophisticated attacks to attack the classifiers (Athalye
et al. (2018); Tramer et al. (2020); Chen et al. (2017)).

**Adversarial Generalization.** The work of (Schmidt et al. (2018); Raghunathan et al. (2019); Zhai
et al. (2019)) have shown that in some scenarios achieving adversarial generalization requires more
data. The work of (Attias et al. (2021); Montasser et al. (2019)) explains generalization in adversarial
settings using VC-dimension. Cullina et al. (2018) studies PAC-learning guarantees in the adversarial
setting via VC-dimension. VC-dimension usually depends on the number of parameters in the model,
while Rademacher complexity usually depends on the weight matrices. Rademacher complexity
usually provides tighter generalization bounds (Bartlett (1998)). Neyshabur et al. (2017b) uses a
pac-bayesian approach to provide a generalization bound for neural networks. Sinha et al. (2017)
study the generalization of an adversarial training algorithm in terms of distributional robustness. The
work of (Xing et al. (2021a;b); Javanmard et al. (2020)) study the generalization properties in the
setting of linear regression. Gaussian mixture models are used to analyze adversarial generalization
(Taheri et al. (2020); Javanmard et al. (2020); Dan et al. (2020)). The work of (Allen-Zhu & Li
(2020)) explains adversarial generalization through the lens of feature purification.

**Adversarial Rademacher Complexity.** Researchers have analyzed adversarial Rademacher complexity in linear and two-layers neural networks cases. In linear cases, the upper bounds can be
directly derived by definition (Khim & Loh (2018); Yin et al. (2019)). In two-layers neural networks
cases, an upper bound is derived using Massart’s Lemma (Awasthi et al. (2020)). It seems that these
proofs cannot be extended to multi-layers cases. Moreover, based on the definition of adversarial
function class _F[˜] in equation (1), the candidate functions are not composition functions, but with an_
inf operation in front of the neural networks. Then, the induction on layers seems not applicable in
calculating adversarial Rademacher complexity for deep neural networks. The works of (Khim &
Loh (2018)) and (Gao & Wang (2021)) indicate the difficulty of analyzing adversarial Rademacher
complexity. They analyze other variants of adversarial Rademacher complexity of DNNs. The first
one introduce tree transformation, but it overestimates the adversarial loss. The second one considers
fast gradient sign methods (FGSM) adversarial examples, but it also requires additional assumption
on the gradient.
In Appendix B, we provide the details of the above bounds and discuss why these methods seem
not applicable in multi-layers cases. We also provide a comparison of adversarial generalization
in Rademacher complexity framework and other frameworks. In the next section, we provide our
solution of adversarial Rademacher complexity based on covering number and analyze each factor in
the upper bound.


-----

4 OUR SOLUTION OF ADVERSARIAL RADEMACHER COMPLEXITY

The following Theorem states an upper bound of adversarial Rademacher complexity in the Frobenius
norm cases.
**Theorem 1 (Frobenius Norm Bound). Given the function class F in equation (2) under Frobbe-**
_nius Norm, and the corresponding adversarial function class_ _F[˜] in equation (1). The adversarial_
_Rademacher complexity of deep neural networks_ _S( [˜]) satisfies_
_R_ _F_


1
_S( [˜])_ 1, q 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ)L[d]ρ[−][1]
_R_ _F_ _≤_ _√[24]m max{_ _}_ _∥_ _∥_ _∞_


_Ml._ (3)

_l=1_

Y


_hlhl_ 1 log(3d)
_−_
_l=1_

X


_By assuming that Lρ = 1, p_ 2, **_X_** _p,_ = B, and h = max _h0,_ _, hd_ _, we have_
_≤_ _∥_ _∥_ _∞_ _{_ _· · ·_ _}_

(B + ϵ)h _d log(d)_ _l=1_ _[M][l]_
_S( [˜])_ _._ (4)
_R_ _F_ _≤O_ _√m_
 p [Q][d] 

Because of the inf operation of the function in _F[˜], we cannot peel off the layers or calculate the_
covering number by induction on layers. Our proof is based on calculating the covering number of _F[˜]_
directly. Below we sketch the proof. The completed proof is provided in Appendix A.

**Step 1: Diameter of** _F[˜]._ We first calculate the diameter of _F[˜]. We have_


1
2 max _f_ _S_ 2L[d]ρ[−][1] max 1, q 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ)
_f˜_ _∥_ [˜]∥ _≤_ _{_ _}_ _∥_ _∥_ _∞_
_∈F[˜]_


∆
_Ml_ = D.

_l=1_

Y


**Step 2: Distance to** _F[˜][c]._ Let Cl be δl-covers of {∥Wl∥F ≤ _Ml}, l = 1, 2, · · ·, d. Let_

= _f_ _[c]_ : x _Wd[c][ρ][(][W][ c]d_ 1[ρ][(][· · ·][ ρ][(][W][ c]1 **_[x][)][ · · ·][ ))][, W]l[ c]_**
_F_ _[c]_ _{_ _→_ _−_ _[∈C][l][, l][ = 1][,][ 2][ · · ·][, d][}]_

and [˜] = _f[˜] : (x, y)_ inf
_F_ _[c]_ _{_ _→_ **_x_** **_x[′]_** _p_ _ϵ_ _[yf]_ [(][x][′][)][|][f][ ∈F] _[c][}][.]_
_∥_ _−_ _∥_ _≤_

For all _f[˜] ∈_ _F[˜], we need to find the smallest distance to_ _F[˜][c], i.e. we need to calculate the_

max min _f_ _f_ _[c]_ _S._
_f˜∈F[˜]_ _f˜[c]∈F[˜][c][ ∥]_ [˜] − [˜] _∥_

(x, y), given f and f _[c], let x[∗]_ = arg inf **_x_** **_x′_** _p yf_ (x[′]) and x[c] = arg inf **_x_** **_x′_** _p yf_ _[c](x[′])._
_∀_ _∈D_ _∥_ _−_ _∥_ _∥_ _−_ _∥_

**_x[c]_** _if_ _f_ (x[∗]) _f_ _[c](x[c])_
Let z = **_x_** _if_ _f_ (x[∗]) ≥ < f _[c](x[c])_ and gb[a][(][z][) =][ W][b][ρ][(][· · ·][ W][a][+1][ρ][(][W][ c]a 1 _[z][)][ · · ·][ )))][.][ Then]_

_[· · ·][ ρ][(][W][ c]_



_Dδl_

2Ml


_f_ (z) _f_ _[c](z)_ = _gd[0][(][z][)][ −]_ _[g]d[d][(][z][)][| ≤|][g]d[0][(][z][)][ −]_ _[g]d[1][(][z][)][|][ +][ · · ·][ +][ |][g]d[d][−][1](z)_ _gd[d][(][z][)][| ≤]_
_|_ _−_ _|_ _|_ _−_


_l=1_


Let δl = 2Mlε/dD, l = 1, _, d, we have max ˜f_ [min][ ˜]f _[c]_ _f_ _f_ _[c]_ _S_ _l=1_ 2DδMll
_· · ·_ _∈F[˜]_ _∈F[˜][c][ ∥]_ [˜] − [˜] _∥_ _≤_ [P][d] _[≤]_ _[ε][.]_

**Step 3: Covering Number of** _F[˜]._ Then, We can calculate the ε-covering number N ( F[˜], ∥· ∥S, ε).
Because _F[˜][c]_ is a ε-cover of _F[˜]. The cardinality of_ _F[˜][c]_ is

_d_

( [˜], _S, ε) =_ [˜] ( [3][dD] _l=1_ _[h][l][h][l][−][1]_ _._ (5)
_N_ _F_ _∥· ∥_ _|F_ _[c]| ≤_ 2ε [)]P

**Step 4: Integration.** By Dudley’s integral, we obtain the bound in Theorem 1.

Remark: Step 2 is the critical step in the proof. In words, if we calculate the covering number of the
class of d-layers neural nets directly, we only need to define the optimal adversarial example one
time. Then we can calculate the other things using this adversarial example. In contrast, if we want to
do it layer by layer, the optimal adversarial example will be changed when we add or peel off a layer.
This is why the induction methods fail in adversarial settings.


-----

**Theorem 2 (** 1, -Norm Bound). Given the function class _in equation (2) under_ 1, _-norm,_
_∥· ∥_ _∞_ _F_ _∥· ∥_ _∞_
_and the corresponding adversarial function class_ _F[˜] in equation (1). The adversarial Rademacher_
_complexity of deep neural networks_ _S( [˜]) satisfies_
_R_ _F_


_RS( F[˜]) ≤_ _√[24]m_ (∥X∥p,∞ + ϵ)L[d]ρ[−][1]


_hlhl_ 1 log(3d) _Ml._ (6)
_−_
_l=1_ _l=1_

X Y


In the case of ∥· ∥1,∞-norm, the bound is similar to the bound in the Frobenius norm case except the
term max{1, q[1][/][2][−][1][/p]}. Therefore, for all p ≥ 1, the ∥· ∥1,∞-norm bound have the same order in
equation (4).

**Theorem 3 (Lower Bound). Given the function class of DNNs F in equation (2), and the corre-**
_sponding adversarial function class_ _F[˜] in equation (1). Exist sample dataset S, s.t. the adversarial_
_Rademacher complexity of deep neural networks_ _S( [˜]) satisfies_
_R_ _F_

_S( [˜])_ Ω (B + ϵ) _dl=1_ _[M][l]_ _._ (7)
_R_ _F_ _≥_ _√m_
 Q 

The proof of the above Theorem is based on constructing a scalar network and is provided in Appendix
A. The gap between the upper bound and the lower bound is the dependence on depth-d and width-h,
_h[√]d log d. In the next section, we extend the adversarial Rademacher complexity to the Multi-class_
classification cases.

5 MARGIN BOUNDS FOR MULTI-CLASS CLASSIFICATION

5.1 SETTING FOR MULTI-CLASS CLASSIFICATION

The setting for multi-class classification follows (Bartlett & Mendelson (2002)). In a K-class
classification problem, let Y = {1, 2, · · ·, K}. The functions in the hypothesis class F map X to
R[K], the k-th output of f is the score of f (x) assigned to the k-th class.

Define the margin operatorprediction if and only if M M((ff((xx)), y, y)) = [ > 0f. We consider a particular loss function(x)]y −maxy′≠ _y[f_ (x)]y′ . The function makes a correct ℓ(f (x), y) =
_φγ(M_ (f (x), y)), where γ > 0 and φγ : R → [0, 1] is the ramp loss:


1 _t ≤_ 0
1 _γ_ 0 < t < γ
_−_ _[t]_

0 _t ≥_ _γ._


_φγ(t) =_

The loss function ℓ(f (x), y) satisfies:


1(y = arg max (8)
_̸_ _y[′]_ [K][[][f] [(][x][)]][y][′] [)][ ≤] _[ℓ][(][f]_ [(][x][)][, y][)][ ≤] [1][([][f] [(][x][)]][y][ ≤] _[γ][ + max]y[′]=y[[][f]_ [(][x][)]][y][′] [)][.]
_∈_ _̸_

Define the function class ℓ := (x, y) _φγ(M_ (f (x), y)) : f . Since φγ(t) [0, 1] and
_F_ _{_ _7→_ _∈F}_ _∈_
_φγ(_ ) is 1/γ-Lipschitz, by combining (8) with Theorem 1, we can obtain the following direct corollary

_·_
as the generalization bound in the multi-class classification.

**Corollary 1 (Mohri et al. (2018)). Consider the above multi-class classification setting. For any**
_fixed γ > 0, we have with probability at least 1 −_ _δ, for all f ∈F,_


P(x,y)
_∼D_


_y_ = arg max
_̸_ _y[′]_ [K][[][f] [(][x][)]][y][′]
_∈_


log [2]δ

2m [.]


_≤_ _m[1]_


_i=1_ 1([f (xi)]yi ≤ _γ + maxy[′]≠_ _y[[][f]_ [(][x][i][)]][y][′] [) + 2][R][S][(][ℓ][F] [) + 3]

X


In adversarial training, let B[p]x[(][ϵ][) =][ {][x][′][ :][ ∥][x][′][ −] **_[x][∥][p]_**

_[≤]_ _[ϵ][}][ and we define the adversarial function]_
class _ℓ[˜]F := {(x, y) 7→_ maxx′∈Bx[p] [(][ϵ][)][ ℓ][(][f] [(][x][′][)][, y][) :][ f][ ∈F}][. We have]


-----

**Corollary 2 (Yin et al. (2019)). Consider the above adversarial multi-class classification setting.**
_For any fixed γ > 0, we have with probability at least 1 −_ _δ, for all f ∈F,_

P(x,y) **_x[′]_** B[p]x[(][ϵ][)][ s.t.][ y][ ̸][= arg max]
_∼D_ _∃_ _∈_ _y[′]_ [K][[][f] [(][x][′][)]][y][′]

 _∈_ 


log [2]δ

2m [.]


_≤_ _m[1]_


1( **_x[′]i_** **_xi_** [(][ϵ][)][ s.t.][ [][f] [(][x]i[′] [)]][y]i _i[)]][y][′]_ [) + 2][R][S][(˜]ℓ ) + 3
_i=1_ _∃_ _[∈]_ [B][p] _[≤]_ _[γ][ + max]y[′]≠_ _y[[][f]_ [(][x][′] _F_

X


5.2 ADVERSARIAL RADEMACHER COMPLEXITY

Under the multi-class setting, we have the following bound for adversarial Rademacher complexity.
**Theorem 4. Given the function class F in equation (2) under Frobbenius Norm, and the correspond-**
_ing adversarial function class_ _F[˜] in equation (1). The adversarial Rademacher complexity of deep_
_neural networks RS(ℓ[˜]F_ ) satisfies


1

_S(ℓ[˜]_ ) 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ)L[d]ρ[−][1]
_R_ _F_ _≤_ _γ[48][√][K]m_ [max][{][1][, q] _}_ _∥_ _∥_ _∞_


_Ml._ (9)

_l=1_

Y


_hlhl_ 1 log(3d)
_−_
_l=1_

X


1
The 1, -norm bound is similar, except the term max 1, q 2 _[−]_ _p[1]_ . Below we sketch the proof.
_∥· ∥_ _∞_ _{_ _}_

Step 1: Let _F[˜][k]_ = {(x, y) → inf _∥x′−x∥≤ϵ([f_ (x[′])]y − [f (x[′])]k), f ∈F}1, then RS(ℓ[˜]F ) ≤
_KRS(ℓ[˜]F_ _k_ ). Step 2: By the Lipschitz property of φγ(·), RS(ℓ[˜]F _k_ ) ≤ _γ_ _[R][S][(][F]_ _[k][)][. Step 3: The]_

calculation of _S( [˜]_ ) follows the binary case.
_R_ _F_ _[k]_

5.3 COMPARISON OF THE BOUNDS

Now, we compare the difference between the bounds for (standard) Rademacher complexity and
adversarial Rademacher complexity. We have shown that

_d_

_B√d_ _l=1_ _[M][l]_ (B + ϵ)h√d log d _l=1_ _[M][l]_
_RS(ℓF_ ) ≤O _γ[√]m_ and RS(ℓ[˜]F ) ≤O _γ[√]m_ _,_ (10)

where we use the upper bound of [Q][d] _S(_ ) in (Golowich et al. (2018)). Q 
_R_ _F_

**Algorithm-Independent Factors.** In the two bounds, the algorithm-independent factors include
Sample size B, perturbation intensity ϵ, depth-d, and width-h. To simplify the notations, we let
_Cstd = B√d and Cadv = (B_ +ϵ)h[√]d log d be the constants in standard and adversarial Rademacher

complexity, respectively. We simply have Cadv > Cstd.
**Algorithm-Dependent Factors. In the two bounds, the margins γ and the product of the ma-**
trix norms _l=1_ To simplify the notations, we de
_[∥][W][l][∥]_ [depend on the training algorithms.]
fine Wstd := _l=1_

_[∥][W][l][∥][/γ][ if the training algorithm is standard training. Correspondingly, let]_
_Wadv :=_ [Q]l=1[d]
conduct experiments to show that[Q][∥][d][W][l][∥][/γ][ if the training algorithm is adversarial training.] Wadv > Wstd. [ In the next section, we]

**Notation of generalization gaps.[Q][d]** In the next section, we use E(·) and _E[˜](·) to denote the standard_
and robust generalization gap. We use fstd and fadv to denote the standard- and adversarially-trained
model. Our goal is to understand why the robust generalization gap of an adversarial training model
is large, which is quite different from the standard generalization gap of a standard-trained model,
i.e., we want to analyze why [˜](fadv) > (fstd). Based on the standard and adversarial Rademacher
_E_ _E_
complexity bounds, it is suggested that

˜(fadv) _CadvWadv_ _and_ (fstd) _CstdWstd._
_E_ _∝_ _E_ _∝_

To analyze the individual effect of factors Cadv and Wadv, we further introduce two kinds of
generalization gaps, the robust generalization gap of a standard-trained model ( [˜](fstd)) and the
_E_
standard generalization gap of an adversarially-trained model ( (fadv)). The standard and adversarial
_E_
Rademacher complexity suggest that

˜(fstd) _CadvWstd_ _and_ (fadv) _CstdWadv._
_E_ _∝_ _E_ _∝_


-----

6 EXPERIMENT

As we discuss in the previous section, the product of weight norm _l=1_
algorithm-dependent factors controlling the generalization gap. We provide experiments comparing[∥][W][l][∥] [and the margin][ γ][ are]
the difference between these terms in standard and adversarial settings. Since the bounds also hold

[Q][d]
for convolution neural networks, we consider the experiments of training VGG networks (Simonyan
& Zisserman (2014)) on CIFAR-10 (Krizhevsky et al. (2009)). We use the experiments on VGG-19
to illustrate the results. Other experiments are provided in Appendix C.

VGG-19

(a) (b) (c) (d)

Figure 1: Product of the Frobenius norm in the experiments on CIFAR-10. The red lines are the results
of standard training. The blue lines are the results of adversarial training. (a): Standard Generalization
gap, the blue line represents (fadv) and the red line represents (fstd). (b): Robust Generalization
_E_ _E_
Gap, the blue line represents [˜](fadv) and the red line represents [˜](fstd). (c): _l=1_
_E_ _E_ _[∥][W][l][∥][F][ of the]_
neural networks. (d): _l=1_
red line represents Wstd. _[∥][W][l][∥][F][ /γ][ of the neural networks, the blue line represents][Q][d]_ _[ W][adv][ and the]_

**Training Settings.** [Q]For both standard and adversarial training, we use the stochastic gradient[d]
descent (SGD) optimizer, along with a learning rate schedule, which is 0.1 over the first 100 epochs,
down to 0.01 over the following 50 epochs, and finally be 0.001 in the last 50 epochs. For adversarial
settings, we adopt the ℓ PGD adversarial training (Madry et al. (2017)). The perturbation intensity
_∞_
is set to be 8/255. We set the number of steps as 20 and further increase it to 40 in the testing phase.
For the stepsize in the inner maximization, we set it as 2/255. In Corollary 2, we need to use the
optimal adversarial examples to calculate the margin and the robust generalization gap, but it is
unknown in practice. We use the PGD adversarial examples as substitutes.

**Calculation of Margins.** We adopt the setting in (Neyshabur et al. (2017a)). In standard training,
we set the margin over training set to be 5[th]-percentile of the margins of the data points in S. i.e.
Prc5 _f_ (xi)[yi] maxy=yi f (x)[y] (xi, yi) _S_ . In adversarial settings, we set the margin over
_{_ _−_ _̸_ _|_ _∈_ _}_
training set to be 5[th]-percentile of the margins of the PGD-adversarial examples of S. The choice of
5[th]-percentile is because the training accuracy is 100% in all the experiments. We provide ablation
studies about the percentile in the Appendix C.

**Standard and Robust Generalization Gap.** In Figure 3 (a) and (b), we plot the standard and
robust generalization gap of both standard-trained and adversarially-trained models. We use the
results using 50000 training samples to discuss the experiments. Firstly, in Figure 3 (a), we can see
that (fstd) is small (=10.45%). On the other hand, an adversarial-trained model has a larger standard
_E_
generalization gap ( (fadv)=26.34%). It is a widely observed phenomenon that adversarial training
_E_
hurts standard generalization. One reason is that adversarial training overfits the adversarial examples
and performs worse on the original examples. Secondly, in Figure 3 (b), the robust generalization
gap of a standard-trained model is very small ( [˜](fstd) = 0). It is because the standard-trained model
_E_
can easily be attacked on both the training set and test set. Then, the robust training accuracy and
test accuracy are closed to 0%. Therefore, the robust generalization gap is also 0. On the contrary,
˜(fadv)=58.90%, i.e. the adversarial generalization is bad. This is also observed in the previous
_E_
studies, and we aim to discuss the reasons.
**Adversarially-trained Models Have Larger Weight Norms, i.e. Wadv > Wstd.** In Figure 3 (c),
we can see that the _l=1_ _l=1_

_[∥][W][l][∥][F][ of adversarial training is much larger than the][ Q][d]_ _[∥][W][l][∥][F][ of]_
standard training. In (d), the _l=1_
to the Figures in (c),[Q] W[d] _adv is larger than[∥][W][l][∥][F] W[ is divided by]std. One of the reasons why[ γ][, we can see that the Figures is similar] Wadv > Wstd is neural_
networks need more capacity to fit the adversarial examples.

[Q][d]


-----

Table 1: Comparison of the four kinds of generalization Gap introduced in Section 5.3. The
experiments are training VGG-19 on CIFAR-10. Notice that [˜](fstd)=0% is a degenerated case, with
_E_
training error=100%. In the other three cases, the training errors≈0%.

Standard-trained models Adversarially-trained models

Types of Generalization Gaps Standard Robust Standard Robust
Training Errors 0% 100% 0% 0.02%
Test Errors 10.45% 100% 26.34% 58.92%
Generalization Gaps (fstd)=10.45% ˜(fstd)=0% (fadv)=26.34% ˜(fadv)=58.90%
_E_ _E_ _E_ _E_

_E˜(fstd)=0% is a degenerated case._ In Table 1, we show the training and test errors for all kinds
of generalization gaps. We can see that the robust training error for a standard-trained model is equal
to 100%. Since the model does not fit any adversarial examples in the training set, there is nothing to
generalize to the adversarial examples in the test set. The generalization gap becomes meaningless.
And the Rademacher complexity bound [˜](fstd) (CadvWstd/[√]m) becomes a trivial bound. In
_E_ _≤O_
the other three cases, the training errors are all ≈0%. The generalization gaps are meaningful. We
aim to analyze why [˜](fadv) > (fstd) by analyzing [˜](fadv) > (fadv) > (fstd).
_E_ _E_ _E_ _E_ _E_

**The effect of Cadv.** We first compare the difference between _E[˜](fadv) and E(fadv). We can see_
that [˜](fadv) = 58.90% > (fadv) = 26.34%. For an adversarially-trained model, the robust
_E_ _E_
generalization gap is larger than the standard generalization gap. If we use the bounds of adversarial
and standard Rademacher complexity as approximations of the robust and standard generalization
gap, i.e., _E[˜](fadv) ∝_ _CadvWadv and E(fadv) ∝_ _CstdWadv,_ _E[˜](fadv) > E(fadv) can be explained by_
_Cadv > Cstd since Wadv are the same in the two bounds._

**The effect of Wadv.** Similarly, we compare the difference between E(fadv) and E(fstd). We
can see that (fadv) = 26.34% > (fstd) = 10.45%. This is a widely observed phenomenon
_E_ _E_
that adversarial training hurts standard generalization. It can also be explained by the Rademacher
bounds. If we use the bounds of standard Rademacher complexity as approximations, i.e., (fadv)
_E_ _∝_
_CstdWadv and E(fstd) ∝_ _CstdWstd,_ _E[˜](fadv) > E(fadv) can be explained by Wadv > Wstd._

In summary, we can use a simple formula to explain why [˜](fadv) > (fadv) > (fstd) through the
_E_ _E_ _E_
lens of Rademacher complexity. That is

_CadvWadv > CstdWadv > CstdWstd._

The difficulty of adversarial generalization comes from two parts, the constant Cadv and the weight
norms Wadv. The first part Cadv is independent of the algorithms. It comes from the minimax
problem of adversarial training itself, and it cannot be avoided. The second part Wadv depends on
the algorithms. Therefore, the product of the weight norms is an important factor for the robust
generalization of adversarial training.

**Ablation Studies.** We provide other ablation studies in Appendix C. First, we consider different
VGG architecture and give the experiments on VGG-11, 13, and 16. Secondly, We consider different
percentile of the margins of the training dataset. Thirdly, we provide the experiments on ∥·∥1,∞-norm.
We can see that the ∥· ∥1,∞-norm bound has a larger magnitude than the Frobenius norm bound.
Then, we provide the experiments on CIFAR-100. Finally, the large weight norms suggest adding
a regularization term on the weights during training. We provide experiments with and without
weight decay and see that the one with weight decay has a smaller generalization gap and a smaller
_d_
_l=1_
gap and the product of weight norms.[∥][W][l][∥][F][ /γ][. These experiments suggest the strong relationship between robust generalization]
Q

7 CONCLUSION

In this paper, we first provide upper bounds for the adversarial Rademacher complexity of deep neural
networks. Then, we experimentally investigate these bounds and show that the product of weight
norms is a key factor explaining why adversarial training cannot generalize well. We think our results
will motivate more theoretical research to understand adversarial training and empirical research to
improve the generalization of adversarial training.


-----

REFERENCES

Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust
deep learning. arXiv preprint arXiv:2005.10190, 2020.

Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of
security: Circumventing defenses to adversarial examples. arXiv preprint arXiv:1802.00420, 2018.

Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for adversarially robust learning. 2021.

Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear
hypotheses and neural networks. In International Conference on Machine Learning, pp. 431–441.
PMLR, 2020.

Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural
networks. arXiv preprint arXiv:1706.08498, 2017.

Peter L Bartlett. The sample complexity of pattern classification with neural networks: the size of the
weights is more important than the size of the network. IEEE transactions on Information Theory,
44(2):525–536, 1998.

Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and
structural results. Journal of Machine Learning Research, 3(Nov):463–482, 2002.

Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017
_ieee symposium on security and privacy (sp), pp. 39–57. IEEE, 2017._

Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order
optimization based black-box attacks to deep neural networks without training substitute models.
In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15–26, 2017.

Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized
smoothing. In International Conference on Machine Learning, pp. 1310–1320. PMLR, 2019.

Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of evasion
adversaries. arXiv preprint arXiv:1806.01471, 2018.

Chen Dan, Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially robust
gaussian classification. In International Conference on Machine Learning, pp. 2345–2355. PMLR,
2020.

Qingyi Gao and Xiao Wang. Theoretical investigation of generalization bounds for adversarial
learning of deep neural networks. Journal of Statistical Theory and Practice, 15(2):1–28, 2021.

Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg,
and Ian Goodfellow. Adversarial spheres. arXiv preprint arXiv:1801.02774, 2018.

Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of
neural networks. In Conference On Learning Theory, pp. 297–299. PMLR, 2018.

Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial
examples. arXiv preprint arXiv:1412.6572, 2014.

Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering
the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint
_arXiv:2010.03593, 2020._

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image
recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition,
pp. 770–778, 2016.

Sepp Hochreiter and Jurgen Schmidhuber. Long short-term memory.¨ _Neural computation, 9(8):_
1735–1780, 1997.


-----

Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training
for linear regression. In Conference on Learning Theory, pp. 2034–2078. PMLR, 2020.

Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint
_arXiv:1810.09519, 2018._

Marc Khoury and Dylan Hadfield-Menell. On the geometry of adversarial examples. arXiv preprint
_arXiv:1811.00525, 2018._

Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097–1105,
2012.

Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified
robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security
_and Privacy (SP), pp. 656–672. IEEE, 2019._

Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes.
Springer Science & Business Media, 2013.

Xingjun Ma, Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck,
Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local
intrinsic dimensionality. arXiv preprint arXiv:1801.02613, 2018.

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.
Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083,
2017.

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
2018.

Omar Montasser, Steve Hanneke, and Nathan Srebro. Vc classes are adversarially robustly learnable,
but only improperly. In Conference on Learning Theory, pp. 2512–2530. PMLR, 2019.

Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural
networks. In Conference on Learning Theory, pp. 1376–1401. PMLR, 2015.

Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring generalization in deep learning. arXiv preprint arXiv:1706.08947, 2017a.

Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrallynormalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564, 2017b.

Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Adversarial
training can hurt generalization. arXiv preprint arXiv:1906.06032, 2019.

Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Timothy Mann. Fixing data augmentation to improve adversarial robustness. _arXiv preprint_
_arXiv:2103.01946, 2021._

Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. In Advances in Neural Information Processing
_Systems, pp. 5014–5026, 2018._

Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image
recognition. arXiv preprint arXiv:1409.1556, 2014.

Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with
principled adversarial training. arXiv preprint arXiv:1710.10571, 2, 2017.

Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend:
Leveraging generative models to understand and defend against adversarial examples. arXiv
_preprint arXiv:1710.10766, 2017._


-----

Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow,
and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.

Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Asymptotic behavior of adversarial
training in binary classification. arXiv preprint arXiv:2010.13275, 2020.

Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to
adversarial example defenses. arXiv preprint arXiv:2002.08347, 2020.

Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.

Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. arXiv preprint arXiv:2004.05884, 2020.

Yue Xing, Qifan Song, and Guang Cheng. On the generalization properties of adversarial training. In
_International Conference on Artificial Intelligence and Statistics, pp. 505–513. PMLR, 2021a._

Yue Xing, Ruizhi Zhang, and Guang Cheng. Adversarially robust estimate and risk analysis in linear
regression. In International Conference on Artificial Intelligence and Statistics, pp. 514–522.
PMLR, 2021b.

Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust
generalization. In International Conference on Machine Learning, pp. 7085–7094. PMLR, 2019.

Runtian Zhai, Tianle Cai, Di He, Chen Dan, Kun He, John Hopcroft, and Liwei Wang. Adversarially
robust generalization just requires more unlabeled data. arXiv preprint arXiv:1906.00555, 2019.


-----

A PROOF OF THE THEOREMS

A.1 PROOF OF THEOREM 1

**Theorem 1 (Frobenius Norm Bound). Given the function class F in equation (2) under Frobbe-**
_nius Norm, and the corresponding adversarial function class_ _F[˜] in equation (1). The adversarial_
_Rademacher complexity of deep neural networks_ _S( [˜]) satisfies_
_R_ _F_


1
2 _p_
_S( [˜])_ 1, q _[−]_ [1] ( **_X_** _p,_ + ϵ)L[d]ρ[−][1]
_R_ _F_ _≤_ _√[24]m max{_ _}_ _∥_ _∥_ _∞_


_hlhl_ 1 log(3d)
_−_
_l=1_

X


_Ml._

_l=1_

Y


_By assuming that Lρ = 1, p_ 2, **_X_** _p,_ _B, and h = max_ _h0,_ _, hd_ _, we have_
_≤_ _∥_ _∥_ _∞_ _≤_ _{_ _· · ·_ _}_

(B + ϵ)h _d log(d)_ _l=1_ _[M][l]_
_S( [˜])_ _._
_R_ _F_ _≤O_ _√m_
 p [Q][d] 

Because of the inf operation of the function in _F[˜], we cannot peel off the layers or calculate the_
covering number by induction on layers. Our proof is based on calculating the covering number of _F[˜]_
directly. Before we provide the proof, we first introduce the following lemma.

**Lemma 1 (Covering number of norm-balls). Let B be a ℓp norm ball with radius W** _. Let d(x1, x2) =_
**_x1_** **_x2_** _p. Define the ε-covering number of B as_ ( _, d(_ _,_ ), ε), we have
_∥_ _−_ _∥_ _N_ _B_ _·_ _·_

_N_ (B, d(·, ·), ε) ≤ (1 + 2W/ε)[q].

In the case of Frobenius norm ball of m × n matrices, we have the dimension q = m × n and

_N_ (B, ∥· ∥F, ε) ≤ (1 + 2W/ε)[m][×][n] _≤_ (3W/ε)[m][×][n].

**Lemma 2. if x[∗]i** _[∈{][x]i[′]_ _[|∥][x][i][ −]_ **_[x][′]i[∥][p][ ≤]_** _[ϵ][}][, we have]_

**_x[∗]i_** _r_ _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ).
_∥_ _[∥][r][∗]_ _[≤]_ [max][{][1][, q][1][−] [1] _}_ _∥_ _∥_ _∞_


Proof: If p ≥ _r[∗], by Holder’s inequality with 1/r[∗]_ = 1/p + 1/s,

1
**_x[∗]i_** _i_ [=][ ∥][1][∥][s][∥][x][∗]i [=][ q] _s_ **_x[∗]i_** [=][ q][1][−] _r[1]_ _[−]_ _p[1]_ **_x[∗]i_**
_∥_ _[∥][r][∗]_ _[≤]_ [sup][ ∥][1][∥][s][∥][x][∗][∥][p] _[∥][p]_ _∥_ _[∥][p]_ _∥_ _[∥][p][.]_

Equality holds when all the entries are equal. If p < r[∗], we have

**_x[∗]i_** _i_
_∥_ _[∥][r][∗]_ _[≤∥][x][∗][∥][p][.]_

Equality holds when one of the entries of θ equals to one and the others equal to zero. Then


**_x[∗]i_** _r_ _[−]_ _p[1]_ **_x[∗]i_**
_∥_ _[∥][r][∗]_ _[≤]_ [max][{][1][, q][1][−] [1] _}∥_ _[∥][p]_

_≤_ max{1, q[1][−] _r[1]_ _[−]_ _p[1] }(∥xi∥p + ∥xi −_ **_x[∗]i_** _[∥][p][)]_

max 1, q[1][−] _r[1]_ _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ).
_≤_ _{_ _}_ _∥_ _∥_ _∞_

**Lemma 3. Let A be a m × n matrix and b be a n-dimension vector, we have**

_A_ _b_ 2 _A_ _F_ _b_ 2.
_∥_ _·_ _∥_ _≤∥_ _∥_ _∥_ _∥_

_Proof: let Ai be the rows of A, i = 1 · · · m, we have_


(Aib)[2]
_≤_
_i=1_

X


_∥Ai∥2[2][∥][b][∥][2]2_ [=]
_i=1_

X


_Ai_ 2
_∥_ _∥[2]_
_i=1_

X


_∥b∥2[2]_ [=][ ∥][A][∥][F][ ∥][b][∥][2][.]


_∥A · b∥2 =_


-----

**Step 1: Diameter of** _F[˜]._ We first calculate the diameter of _F[˜]. ∀f ∈F, given (xi, yi), let x[∗]i_ [=]
inf **_xi_** **_x[′]i[∥][p][≤][ϵ][p][ yf]_** [(][x]i[′] [)][, and we let][ x][l]i [be the output of][ x]i[∗] [pass through the first to the][ l][ −] [1][ layer, we]
_∥_ _−_
have

_f[˜](xi, yi)_ = inf _i[)][|]_
_|_ _|_ _|_ **_xi_** **_x[′]i[∥][p][≤][ϵ][p][ yf]_** [(][x][′]
_∥_ _−_

= |Wdρ(Wd−1x[d]i _[−][1])|_

(i)
_≤∥Wd∥F · ∥ρ(Wd−1x[d]i_ _[−][1])∥2_
= ∥Wd∥F · ∥ρ(Wd−1x[d]i _[−][1]) −_ _ρ(0)∥2_

(ii)
_≤_ _LρMd∥Wd−1(x[d]i_ _[−][1])∥2_
_≤· · ·_


_L[d]ρ[−][1]_
_≤_

_L[d]ρ[−][1]_
_≤_


_Ml_ _W1x[∗]i_
_l=2_ _∥_ _[∥][2]_

Y

_d_

_Ml_ **_x[∗]i_**
_l=1_ _· ∥_ _[∥][2]_

Y


(iii)
_L[d]ρ[−][1]_
_≤_


1
_Ml max_ 1, q 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ),
_{_ _}_ _∥_ _∥_ _∞_
_l=1_

Y


where inequality (i) is because of Lemma 3, inequality (ii) is because of the Lipschitz propertiy of
activation function ρ(·), inequality (iii) is because of Lemma 2. Therefore, we have

1 _m_ [1]2 1 _d_ ∆
2 max _f_ _S = 2_ _f[˜](xi, yi)_ 2L[d]ρ[−][1] max 1, q 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ) _Ml_ = D.
_f˜_ _∥_ [˜]∥ _m_ _|_ _|[2]_ _≤_ _{_ _}_ _∥_ _∥_ _∞_
_∈F[˜]_  _i=1_  _l=1_

X Y

**Step 2: Distance to** _F[˜][c]._ Let Cl be δl-covers of {∥Wl∥F ≤ _Ml}, l = 1, 2, · · ·, d. Let_

= _f_ _[c]_ : x _Wd[c][ρ][(][W][ c]d_ 1[ρ][(][· · ·][ ρ][(][W][ c]1 **_[x][)][ · · ·][ ))][, W]l[ c]_**
_F_ _[c]_ _{_ _→_ _−_ _[∈C][l][, l][ = 1][,][ 2][ · · ·][, d][}]_

and [˜] = _f[˜] : (x, y)_ inf
_F_ _[c]_ _{_ _→_ **_x_** **_x[′]_** _p_ _ϵ_ _[yf]_ [(][x][′][)][|][f][ ∈F] _[c][}][.]_
_∥_ _−_ _∥_ _≤_

For all _f[˜] ∈_ _F[˜], we need to find the smallest distance to_ _F[˜][c], i.e. we need to calculate the_

max min _f_ _f_ _[c]_ _S._
_f˜∈F[˜]_ _f˜[c]∈F[˜][c][ ∥]_ [˜] − [˜] _∥_

(xi, yi), i = 1, _, n, given_ _f[˜] and_ _f[˜][c]_ with _Wl_ _Wl[c]_
_∀_ _· · ·_ _∥_ _−_ _[∥][F][ ≤]_ _[δ][l][,][ l][ = 1][,][ · · ·][, d][, consider]_

_f[˜](xi, yi)_ _f_ _[c](xi, yi)_
_|_ _−_ [˜] _|_

= inf _i[)][ −]_ inf _i[)][|]_
_|_ **_xi_** **_x[′]i[∥][p][ y][i][f]_** [(][x][′] **_xi_** **_x[′]i[∥][p][ y][i][f][ c][(][x][′]_**
_∥_ _−_ _∥_ _−_


Let
_x[∗]i_ [= arg] inf _i[)][,]_ and _x[c]i_ [= arg] inf _i[)][,]_
**_xi_** **_x[′]i[∥][p][ y][i][f]_** [(][x][′] **_xi_** **_x[′]i[∥][p][ y][i][f][ c][(][x][′]_**
_∥_ _−_ _∥_ _−_

we have
_f[˜](xi, yi)_ _f_ _[c](xi, yi)_
_|_ _−_ [˜] _|_
=|yif (x[∗]i [)][ −] _[y][i][f][ c][(][x]i[c][)][|]_
=|f (x[∗]i [)][ −] _[f][ c][(][x]i[c][)][|][.]_

Let

**_x[c]i_** _if_ _f_ (x[∗]i [)][ ≥] _[f][ c][(][x]i[c][)]_
_zi =_
**_xi_** _if_ _f_ (x[∗]i [)][ < f][ c][(][x]i[c][)]



-----

Then,

Define gb[a][(][·][)][ as]


_f[˜](xi, yi)_ _fc(xi, yi)_
_|_ _−_ [˜] _|_
=|f (x[∗]i [)][ −] _[f][ c][(][x]i[c][)][|]_
_f_ (zi) _f_ _[c](zi)_ _._
_≤|_ _−_ _|_

_gb[a][(][z][) =][ W][b][ρ][(][W][b][−][1][ρ][(][· · ·][ W][a][+1][ρ][(][W][ c]a_ _[· · ·][ ρ][(][W][ c]1_ _[z][)][ · · ·][ )))][.]_


In words, for the layers b ≥ _l > a in gb[a][(][·][)][, the weight is][ W][l][, for the layers][ a][ ≥]_ _[l][ ≥]_ [1][ in][ g]b[a][(][·][)][, the]
weight is Wl[c][. Then we have][ f] [(][z][i][) =][ g]d[0][(][z][i][)][,][ f] [(][z][i][) =][ g]d[L][(][z][i][)][. We can decompose]


_f_ (zi) _f_ _[c](zi)_
_|_ _−_ _|_

=|gd[0][(][z][i][)][ −] _[g]d[d][(][z][i][)][|]_

= _gd[0][(][z][i][)][ −]_ _[g]d[1][(][z][i][) +][ · · ·][ +][ g]d[d][−][1](zi)_ _gd[d][(][z][i][)][|]_
_|_ _−_

_gd[0][(][z][i][)][ −]_ _[g]d[1][(][z][i][)][|][ +][ · · ·][ +][ |][g]d[d][−][1](zi)_ _gd[d][(][z][i][)][|][.]_
_≤|_ _−_

To bound the gap _f_ (zi) _f_ _[c](zi)_, we first calculate _gd[l][−][1](zi)_ _gd[l]_ [(][z][i][)][|][ for][ l][ = 1][,][ · · ·][, d][.]
_|_ _−_ _|_ _|_ _−_


(11)


_gd[l][−][1](zi)_ _gd[l]_ [(][z][i][)][|]
_|_ _−_

= _Wdρ(gd[l][−][1]1[(][z][i][))][ −]_ _[W][d][ρ][(][g]d[l]_ 1[(][z][i][))][|]
_|_ _−_ _−_

(i)
_Wd_ _F_ _ρ(gd[l][−][1]1[(][z][i][))][ −]_ _[ρ][(][g]d[l]_ 1[(][z][i][))][∥][2]
_≤∥_ _∥_ _∥_ _−_ _−_

(ii)
_LρMd_ _gd[l][−][1]1[(][z][i][)][ −]_ _[g]d[l]_ 1[(][z][i][)][∥][2]
_≤_ _∥_ _−_ _−_

(iii)
= LρMd _Wd_ 1ρ(gd[l][−][1]2[(][z][i][))][ −] _[W][d][−][1][ρ][(][g]d[l]_ 2[(][z][i][))][∥][2]
_∥_ _−_ _−_ _−_
_≤· · ·_


_≤L[d]ρ[−][l]_ _Mj∥Wlρ(gl[l]−[−]1[1][(][z][i][))][ −]_ _[W][ c]l_ _[ρ][(][g]l[l]−[−]1[1][(][z][i][))][∥][2]_

_j=l+1_

Y


where (i) is due to Lemma 3, (ii) is due to the bound of _WL_ and the Lipschitz of ρ( ), (iii) is
_∥_ _∥_ _·_
because of the definition of gb[a][(][z][)][. Then]

_gd[l][−][1](zi)_ _gd[l]_ [(][z][i][)][|]
_|_ _−_


_≤L[d]ρ[−][l]_ _Mj∥Wlρ(gl[l]−[−]1[1][(][z][i][))][ −]_ _[W][ c]l_ _[ρ][(][g]l[l]−[−]1[1][(][z][i][))][∥][2]_

_j=l+1_

Y

_d_

=L[d]ρ[−][l] _j=l+1_ _Mj∥(Wl −_ _Wl[c][)][ρ][(][g]l[l]−[−]1[1][(][z][i][)))][∥][2]_

Y

_d_

(i)
_L[d]ρ[−][l]_ _Mj_ _Wl_ _Wl[c]_ _l_ 1[(][z][i][)))][∥][2]
_≤_ _j=l+1_ _∥_ _−_ _[∥][F]_ _[∥][ρ][(][g][l]−[−][1]_

Y

_d_

(ii)
_≤_ _L[d]ρ[−][l]_ _Mjδl∥ρ(gl[l]−[−]1[1][(][z][i][)))][∥][2][,]_

_j=l+1_

Y


(12)


-----

where inequality (i) is due to Lemma 3, inequality (ii) is due to Lemma 3 the assumption that
_∥Wl −_ _Wl[c][∥][F][ ≤]_ _[δ][l][. It is lefted to bound][ ∥][ρ][(][g]l[l]−[−]1[1][(][z][i][)))][∥][∞][, we have]_

_ρ(gl[l][−]1[1][(][z][i][)))][∥][2]_
_∥_ _−_

=ρ(gl[l]−[−]1[1][(][z][i][)))][ −] _[ρ][(0)][∥][2]_

_Lρ_ _gl[l][−]1[1][(][z][i][))][∥][2]_
_≤_ _∥_ _−_

=Lρ∥Wl[c]−1[ρ][(][g]l[l]−[−]2[2][(][z][i][)))][∥][2]

_≤Lρ∥Wl[c]−1[∥][F]_ _[∥][ρ][(][g]l[l]−[−]2[2][(][z][i][)))][∥][2]_ (13)

_≤LρMl−1∥ρ(gl[l]−[−]2[2][(][z][i][)))][∥][2]_
_≤· · ·_

_l_ 1
_−_ 1

_L[l]ρ[−][1]_ _Mj max_ 1, q 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ).
_≤_ _{_ _}_ _∥_ _∥_ _∞_

_j=1_

Y

combining inequalities (12) and (13), we have

_gd[l][−][1](zi)_ _gd[l]_ [(][z][i][)][|]
_|_ _−_

_d_

_≤L[d]ρ[−][1]_ _j=1Ml[M][j]_ _δl max{1, q_ 12 _[−]_ _p[1] }(∥X∥p,∞_ + ϵ) (14)

Q

= _[Dδ][l]_ _._

2Ml

Therefore, combining inequalities (15) and (14), we have
_f_ (zi) _f_ _[c](zi)_
_|_ _−_ _|_

_gd[0][(][z][i][)][ −]_ _[g]d[1][(][z][i][)][|][ +][ · · ·][ +][ |][g]d[d][−][1](zi)_ _gd[d][(][z][i][)][|]_
_≤|_ _d_ _−_ (15)

_Dδl_

_._

_≤_ 2Ml

_l=1_

X

Then


_Dδl_

2Ml


max min _f_ _f_ _[c]_ _S_
_f˜_ _f˜[c]_ _−_ [˜] _∥_ _≤_
_∈F[˜]_ _∈F[˜][c][ ∥]_ [˜]

Let δl = 2Mlε/dD, l = 1, · · ·, d, we have


_l=1_


_Dδl_

_ε._
2Ml _≤_


max min _f_ _f_ _[c]_ _S_
_f˜_ _f˜[c]_ _−_ [˜] _∥_ _≤_
_∈F[˜]_ _∈F[˜][c][ ∥]_ [˜]


_l=1_


**Step 3: Covering Number of** _F[˜]._ We then calculate the ε-covering number N ( F[˜], ∥·∥S, ε). Because
_F˜[c]_ is a ε-cover of _F[˜]. The cardinality of_ _F[˜][c]_ is


_d_

(i)

_l_
_|C_ _|_ _≤_
_l=1_

Y


_d_

_d_

( [3][M][l] )[h][l][h][l][−][1] =( [3][dD] _l=1_ _[h][l][h][l][−][1]_ _,_
_l=1_ _δl_ 2ε [)]P

Y


( [˜], _S, ε) =_ [˜] =
_N_ _F_ _∥· ∥_ _|F_ _[c]|_


where inequality (i)) is due to Lemma 1.

**Step 4, Integration.** By Dudley’s integral, we have

_D/2_

_S( [˜])_ log ( [˜], _S, ε)dε_
_R_ _F_ _≤_ _√[12]m_ 0 _N_ _F_ _∥· ∥_

Z q

_D/2_ _d_

_≤_ _√[12]m_ Z0 vu( _l=1_ _hlhl−1) log(3dD/2ε)dε_

u X

12D _dl=1t[h][l][h][l][−][1]_ 1/2
= qP√m Z0 log(3d/2ε)dε.

p


(16)


-----

Integration by part, we have


1/2

log(3d/2ε)dε

0

Z

p

= [1] 3[√]πerfc( log 3d) +

2


p 2 p

3[√]πexp( log 3d ) +

_≤_ 2[1] _−_


p

_√π_

= [1] + log 3d

2 _d_

 

p

2 log 3d

_≤_ 2[1]

 
p

= log 3d.
p

Plug equation (17) to equation (16), we have


log 3d


log 3d

p


(17)


1
_S( [˜])_ 1, q 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ)L[d]ρ[−][1]
_R_ _F_ _≤_ _√[24]m max{_ _}_ _∥_ _∥_ _∞_

A.2 PROOF OF THEOREM 2


_hlhl_ 1 log(3d)
_−_
_l=1_

X


_Ml._

_l=1_

Y


**Theorem 2 ((** 1, -Norm Bound). Given the function class _in equation (1) under_ 1, _-norm,_
_∥·∥_ _∞_ _F_ _∥·∥_ _∞_
_and the corresponding adversarial function class_ _F[˜] in equation (2). The adversarial Rademacher_
_complexity of deep neural networks_ _S( [˜]) satisfies_
_R_ _F_


_RS( F[˜]) ≤_ _√[24]m_ (∥X∥p,∞ + ϵ)L[d]ρ[−][1]


_hlhl_ 1 log(3d)
_−_
_l=1_

X


_Ml._

_l=1_

Y


The proof is mimilar to the proof of the Frobenius norm bound. We first introduce the following
inequality.

**Lemma 4. Let A be a m × n matrix and b be a n-dimension vector, we have**

_∥A · b∥∞_ _≤∥A∥1,∞∥b∥∞._

_Proof: let Ai be the rows of A, i = 1 · · · m, we have_

_∥A · b∥∞_ = max |Aib| ≤ max ∥Ai∥1∥b∥∞ = ∥A∥1,∞∥b∥∞.

**Step 1: Diameter of** _F[˜]._ We first calculate the diameter of _F[˜]. ∀f ∈F, given (xi, yi), let x[∗]i_ [=]
inf **_xi_** **_x[′]i[∥][p][≤][ϵ][p][ yf]_** [(][x]i[′] [)][, and we let][ x][l]i [be the output of][ x]i[∗] [pass through the first to the][ l][ −] [1][ layer, we]
_∥_ _−_
have


-----

_f[˜](xi, yi)_ = inf _i[)][|]_
_|_ _|_ _|_ **_xi_** **_x[′]i[∥][p][≤][ϵ][p][ yf]_** [(][x][′]
_∥_ _−_

= |Wdρ(Wd−1x[d]i _[−][1])|_

(i)
_≤∥Wd∥1,∞_ _· ∥ρ(Wd−1x[d]i_ _[−][1])∥∞_
= ∥Wd∥F · ∥ρ(Wd−1x[d]i _[−][1]) −_ _ρ(0)∥∞_

(ii)
_≤_ _LρMd∥Wd−1(x[d]i_ _[−][1])∥∞_
_≤· · ·_


_L[d]ρ[−][1]_
_≤_


_Ml_ **_x[∗]i_**
_l=1_ _· ∥_ _[∥][∞]_

Y


(iii)
_L[d]ρ[−][1]_
_≤_


_Ml(∥X∥p,∞_ + ϵ),
_l=1_

Y


where inequality (i) is because of Lemma 4, inequality (ii) is because of the Lipschitz propertiy of
activation function ρ(·), inequality (iii) is because of Lemma 2. Therefore, we have

_m_ [1]2 _d_

1 ∆
2 max _f_ _S = 2_ _f[˜](xi, yi)_ 2L[d]ρ[−][1]( **_X_** _p,_ + ϵ) _Ml_ = D.
_f˜_ _∥_ [˜]∥ _m_ _|_ _|[2]_ _≤_ _∥_ _∥_ _∞_
_∈F[˜]_  _i=1_  _l=1_

X Y

whereStep 2: Distance to Wl[i] [is the][ i][th][ row of]F[˜][c]. _[ W]Let[ i]l_ _C[. Let]l[i]_ [be][ δ][l][-covers of][ {∥][W][ i]l _[∥][1][ ≤]_ _[M][l][}][,][ l][ = 1][,][ 2][,][ · · ·][, d][,][ i][ = 1][,][ · · ·][, h][l][,]_

= _f_ _[c]_ : x _Wd[c][ρ][(][W][ c]d_ 1[ρ][(][· · ·][ ρ][(][W][ c]1 **_[x][)][ · · ·][ ))][, W]l[ ci]_** _l_ _[, i][ = 1][,][ · · ·][, h][l][, l][ = 1][,][ 2][ · · ·][, d][}]_
_F_ _[c]_ _{_ _→_ _−_ _∈C[i]_

and [˜] = _f[˜] : (x, y)_ inf
_F_ _[c]_ _{_ _→_ **_x_** **_x[′]_** _p_ _ϵ_ _[yf]_ [(][x][′][)][|][f][ ∈F] _[c][}][.]_
_∥_ _−_ _∥_ _≤_

For all _f[˜] ∈_ _F[˜], we need to find the smallest distance to_ _F[˜][c], i.e. we need to calculate the_

max min _f_ _f_ _[c]_ _S._
_f˜∈F[˜]_ _f˜[c]∈F[˜][c][ ∥]_ [˜] − [˜] _∥_

(xi, yi), i = 1, _, n, given_ _f[˜] and_ _f[˜][c]_ with _Wl[i]_ _l_
_∀Wl_ _Wl[c]_ _· · ·_ _|_ _[−]_ _[W][ ci][| ≤]_ _[δ][l][,][ i][ = 1][,][ · · ·][, h][l][,][ l][ = 1][,][ · · ·][, d][, we have]_
_∥_ _−_ _[∥][1][,][∞]_ _[≤]_ _[δ][l][. By the same argument as the step 2 of the proof o Theorem 3, we have]_


_Dδl_

2Ml


max min _f_ _f_ _[c]_ _S_
_f˜_ _f˜[c]_ _−_ [˜] _∥_ _≤_
_∈F[˜]_ _∈F[˜][c][ ∥]_ [˜]

Let δl = 2Mlε/dD, l = 1, · · ·, d, we have


_l=1_


_Dδl_

_ε._
2Ml _≤_


max min _f_ _f_ _[c]_ _S_
_f˜_ _f˜[c]_ _−_ [˜] _∥_ _≤_
_∈F[˜]_ _∈F[˜][c][ ∥]_ [˜]


_l=1_


**Step 3: Covering Number of** _F[˜]._ We then calculate the ε-covering number N ( F[˜], ∥·∥S, ε). Because
_F˜[c]_ is a ε-cover of _F[˜]. The cardinality of_ _F[˜][c]_ is


_hl_ (i)

_|Cl[i][|]_ _≤_
_i=1_

Y


_d_

_d_

( [3][M][l] )[h][l][h][l][−][1] =( [3][dD] _l=1_ _[h][l][h][l][−][1]_ _,_
_l=1_ _δl_ 2ε [)]P

Y


( [˜], _S, ε) =_ [˜] =
_N_ _F_ _∥· ∥_ _|F_ _[c]|_


_l=1_


where inequality (i)) is due to Lemma 1.


-----

**Step 4, Integration.** By the same argument as the step 4 of the proof o Theorem 1, integration by
part, we have


_RS( F[˜]) ≤_ _√[24]m_ (∥X∥p,∞ + ϵ)L[d]ρ[−][1]

A.3 PROOF OF THEOREM 3


_hlhl_ 1 log(3d)
_−_
_l=1_

X


_Ml._

_l=1_

Y


**Theorem 3 (Lower Bound). Given the function class F in equation (2), and the coressponding**
_adversarial function class_ _F[˜] in equation (1). Exist sample dataset S, s.t. the adversarial Rademacher_
_complexity of deep neural networks_ _S( [˜]) satisfies_
_R_ _F_

(B + ϵ) _dl=1_ _[M][l]_
_S( [˜])_ Ω _._
_R_ _F_ _≥_ _√m_
 Q 

The proof of the above Theorem is based on constructing a scalar network. By the definition of
Rademacher complexity, if H[′] is a subset of H, we have


( ) = Eσ
_RS_ _H[′]_


_σih(xi, yi)_ _≤_ Eσ
_i=1_

X 


sup
_h∈H[′]_


sup
_h∈H_


_σih(xi, yi)_ = RS (H).
_i=1_

X 


Therefore, it is enough to lower bound the complexity of _F[˜][′]_ in a particular distribution D, where _F[˜][′]_

is a subset of _F[˜]. Let_
˜ = **_x_** inf
_F_ _[′]_ _{_ _→_ **_x[′]_** **_x_** _p_ _ϵ_ _[yM][d][ ·][ M][2][w][T][ x][|][w][ ∈]_ [R][q][,][ ∥][w][∥][2][ ≤] _[M][1][}][.]_
_∥_ _−_ _∥_ _≤_

We first prove that _F[˜][′]_ is a subset of _F[˜]. In_ _F[˜], we let the activation function ρ(·) be a identity mapping._
Let

_w_ _Ml_ 0 0

_· · ·_

_W1 =_  0.  _Wl =_  0. 0. _· · ·_ 0.  _l = 2,_ _, d._ (18)

.. .. .. .. _· · ·_

 0   0 0 0
   _· · ·_ 
  _[∈]_ [R][h][1][×][h][0] _[,]_   _[∈]_ [R][h][l][×][h][l][−][1] _[,]_

Then, we have ∥Wl∥≤ _Ml and_ _F[˜] with additional constraint in equation (18) reduce to_ _F[˜][′]. In other_
words, _F[˜][′]_ is a subset of _F[˜]._

It turns out that we need to lower bound the adversarial Rademacher complexity of linear hypothesis.
The results are given by the work of (Yin et al. (2019); Awasthi et al. (2020)). Below we state the
result.
**Proposition 4. Given the function class G = {x →** _yw[T]_ **_x|w ∈_** R[q], ∥w∥r ≤ _W_ _} and_ _G[˜] = {x →_
inf _∥x′−x∥r≤ϵ yw[T]_ **_x|w ∈_** R[q], ∥w∥r ≤ _W_ _}, the adversarial Rademacher complexity RS( G[˜]) satisfies_

_r_ _[−]_ _p[1]_ _W_

_S( [˜])_ max _S(_ ), [ϵ][ max][{][1][, q][1][−] [1] _}_ _._
_R_ _G_ _≥_ _R_ _G_ 2[√]m
 

Since the standard Rademacher complexity


_m_

_RS(G) =_ _[W]m_ [E][σ][∥] _i=1_ _σixi∥r∗,_

X


let **_xi_** = B with equal entries for i = 1, _, m, by Lemma 2 we have_
_∥_ _∥_ _· · ·_


_S(_ ) = _[W]_
_R_ _G_ _m_ [E][σ][|]


_σi_ max 1, q[1][−] _r[1]_ _[−]_ _p[1]_ _B._
_|_ _{_ _}_
_i=1_

X


-----

By Khintchine’s inequality, we know that there exists a universal constant c > 0 such that


_m_

_σi_ _c[√]m._
_| ≥_
_i=1_

X


Eσ|


Then, we have

Therefore,


_RS(G) =_ _√[cW]m max{1, q[1][−]_ _r[1]_ _[−]_ _p[1] }B._

_r_ _[−]_ _p[1]_ _W_

_S( [˜])_ max _S(_ ), [ϵ][ max][{][1][, q][1][−] [1] _}_
_R_ _G_ _≥_ _R_ _F_ 2[√]m



1 2c _r_ _[−]_ _p[1] }W_
_≥_ 1 + 2c _c_ _[R][S](B[(][F] +[) +] ϵ) max1 + 2c1, q[×]1[ ϵ]−[ max]r1_ _[−]_ _p[1]_ _[{][1]W2[, q][√][1]m[−]_ [1]

_{_ _}_ _._

_≥_ 1 + 2c _√m_

 

Let W = _l=1_ _[M][l][, we have]_

[Q][d] _S( [˜])_ Ω max{1, q1− _r1_ _[−]_ _p[1] }(B + ϵ)_ _l=1_ _[M][l]_ _,_

_R_ _F_ _≥_ _√m_
 [Q][d] 

where r = 2 for frobenius norm bound and r = 1 for ∥· ∥1,∞-norm bound.


A.4 PROOF OF THEOREM 4

**Theorem 4. Given the function class F in equation (2) under Frobbenius Norm, and the correspond-**
_ing adversarial function class_ _F[˜] in equation (1). The adversarial Rademacher complexity of deep_
_neural networks RS(ℓ[˜]F_ ) satisfies


1

_S(ℓ[˜]_ ) 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ)L[d]ρ[−][1]
_R_ _F_ _≤_ _γ[48][√][K]m_ [max][{][1][, q] _}_ _∥_ _∥_ _∞_


_hlhl_ 1 log(3d)
_−_
_l=1_

X


_Ml._

_l=1_

Y


1
The (1, ∞)-norm bound is similar, except the term max{1, q 2 _[−]_ _p[1] }._

Proof: Firstly, we have

_ℓ˜(f_ (x), y) = max
**_x_** **_x[′]_** _ϵ_ _[φ][γ][(][M]_ [(][f] [(][x][)][, y][))]
_∥_ _−_ _∥≤_

=φγ( inf
**_x_** **_x[′]_** _ϵ_ _[M]_ [(][f] [(][x][)][, y][))]
_∥_ _−_ _∥≤_

=φγ( inf
**_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [max]y[′]=y[[]][f] [(][x][)]][y][′] [))]
_∥_ _−_ _∥≤_ _̸_

=φγ( inf
**_x_** **_x[′]_** _ϵ_ _y[inf][′]=y[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][y][′] [))]
_∥_ _−_ _∥≤_ _̸_

=φγ( inf inf
_y[′]=y_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][y][′] [))][.]
_̸_ _∥_ _−_ _∥≤_

= max inf
_y[′]=y_ _[φ][γ][(]_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][y][′] [))][.]
_̸_ _∥_ _−_ _∥≤_

Define
_h[k](x, y) =_ inf
**_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][k][) +][ γ][1][(][y][ =][ k][)][,]
_∥_ _−_ _∥≤_

we now prove that

max inf _φγ(h[k](x, y))._
_y[′]=y_ _[φ][γ][(]_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][y][′] [)) = max]k
_̸_ _∥_ _−_ _∥≤_

If
inf inf
_y[′]=y_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][y][′] [)][ ≤] _[γ,]_
_̸_ _∥_ _−_ _∥≤_


-----

we have
inf inf
_y[′]=y_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] _[f]_ [(][x][)]][y][′] [)) = inf]k _[h][k][(][x][, y][)][.]_
_̸_ _∥_ _−_ _∥≤_

If
inf inf
_y[′]=y_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][y][′] [)][ > γ,]
_̸_ _∥_ _−_ _∥≤_

we have
_φγ( inf_ inf
_y[′]=y_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][y][′] [)) =][ φ][γ][(inf]k _[h][k][(][x][, y][)) = 0][.]_
_̸_ _∥_ _−_ _∥≤_

Therefore, we have

_ℓ˜(f_ (x), y) = φγ(inf _φγ(h[k](x, y))._
_k_ _[h][k][(][x][, y][)) = max]k_

Define H[k] = {h[k](x, y) = inf _∥x−x′∥≤ϵ([f_ (x)]y − _f_ (x)]k) + γ1(y = k)|f ∈F}, we have


(i) (ii)
_R(ℓ[˜]F_ ) _≤_ _KR(φγ ◦H[k])_ _≤_ _[K]γ_ _[R][(][H][k][)][,]_ (19)

where inequality (i) is the Lemma 9.1 of (Mohri et al. (2018)), inequality (ii) is due to the Lipschitz
property off _[k](x, y) + γ φ1γ((y·) =. Now, define k). Define the function class f_ _[k](x, y) = inf_ _∥x−x′∥≤ϵ([f_ (x)]y − _f_ (x)]k), we have h[k](x, y) =

= _f_ _[k](x, y) =_ inf
_F_ _[k]_ _{_ **_x_** **_x[′]_** _ϵ[([][f]_ [(][x][)]][y][ −] [[][f] [(][x][)]][k][)][|][f][ ∈F}][.]
_∥_ _−_ _∥≤_


We have


( ) = [1]
_R_ _H[k]_ _m_ [E][σ][ sup]h[k]∈H[k]

= [1]

_m_ [E][σ][ sup]h[k]∈H[k]

= [1]

_m_ [E][σ][ sup]h[k]∈H[k]

= [1]

_m_ [E][σ][ sup]f _[k]∈F_ _[k]_


_σih[k](xi, yi)_
_i=1_

X


_f_ _[k](x, y) + γ1(y = k)_


_σi_
_i=1_

X


_m_

_σif_ _[k](x, y) + [1]_

_m_ [E][σ]

_i=1_

Xm

_σif_ _[k](x, y)_
_i=1_

X


_σiγ1(y = k)_
_i=1_

X


=R(F _[k])_

Finally, we need to bound the Rademacher complexity of R(F _[k]). Notice that_

[f (x)]y − [f (x)]k = (Wd[y] _[−]_ _[W][ k]d_ [)][ρ][(][W][d][−][1][(][ρ][(][· · ·][ W][1][(][x][)][ · · ·][ )))][,]

and we have _Wd[y]_ _d_
have _∥_ _[−]_ _[W][ k][∥][F][ ≤]_ [2][M][l][. By Theorem 3 (the results in binary classification case), we]


1
( ) 1, q 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ)L[d]ρ[−][1]
_R_ _F_ _[k]_ _≤_ _√[48]m max{_ _}_ _∥_ _∥_ _∞_

Combining inequalities (20) and (19), we obtain that


_Ml._ (20)

_l=1_

Y


_hlhl_ 1 log(3d)
_−_
_l=1_

X


1

_S(ℓ[˜]_ ) 2 _[−]_ _p[1]_ ( **_X_** _p,_ + ϵ)L[d]ρ[−][1]
_R_ _F_ _≤_ _γ[48][√][K]m_ [max][{][1][, q] _}_ _∥_ _∥_ _∞_


_hlhl_ 1 log(3d)
_−_
_l=1_

X


_Ml._

_l=1_

Y


B DISCUSSION ON EXISTING METHODS FOR RADEMACHER COMPLEXITY

In this section, we discuss the related work, discuss the existing methods in calculating Rademacher
complexity, and identify the difficulty of analyzing adversarial Rademacher complexity.


-----

B.1 EXISTING METHODS

**‘Layer Peeling’ Bounds.** The main idea of calculating the Rademacher complexity of multi-layers
neural networks is the ‘peeling off’ technique (Neyshabur et al. (2015)). We denote g ◦F as the
function class {g ◦ _f_ _|f ∈F}. By Talagrand’s Lemma, we have RS_ (g ◦ _f_ ) ≤ _LgRS_ (F). Based
on this property, we can obtain ( _l)_ 2LρMl ( _l_ 1), where _l is the function class of_
_RS_ _F_ _≤_ _RS_ _F_ _−_ _F_
_l-layers neural networks. Since the Rdemacher complexity of linear function class is bounded by_
_O(BM1/[√]m), we can get the upper bound O(B2[d]L[d]ρ[−][1]_ _dl=1_ _[M][l][/][√][m][)][ by induction. We can]_
remove the Lρ by assuming that Lρ = 1 (e.g. Relu activation function).
Q

Golowich et al. (2018) improves the dependence on depth-d from 2[d] to _√d. The main idea is to_

rewrite the Rademacher complexity Eσ[·] as Eσ exp ln[·]. Then, we can peel off the layer inside the
ln(·) function and the 2[d] now appears inside the ln(·).

**Covering Number Bounds.** Bartlett et al. (2017) uses a covering numbers argument to show that
the generalization gap scale as


_B_ _dl=1_

_[∥][W][l][∥]_
_√m_
 Q


3/2
_,_
 


_Wl_ 2,1
_∥_ _∥[2][/][3]_

_Wl_
_∥_ _∥[2][/][3]_


_l=1_


where ∥· ∥ is the spectral norm. The proof is based on the induction on layers. Let Wl be the weight
matrix of the present layer and Xl be the output of X pass through the first to the l − 1 layer. Then,
one can compute the matrix covering number ( _WlXl_ _,_ 2, ϵ) by induction.
_N_ _{_ _}_ _∥· ∥_

**Adversarial Generalization Bounds.** Researchers have analyzed adversarial Rademacher complexity in linear and two-layers neural networks cases. In linear cases, the upper bounds can be
directly derived by definition (Khim & Loh (2018); Yin et al. (2019)). In two-layers neural networks
cases, an upper bound is derived using Massart’s Lemma (Awasthi et al. (2020)). These proofs cannot
be extended to multi-layers cases. Moreover, based on the definition of adversarial function class
_F˜ in equation (1), the candidate functions are not composition functions, but with an inf operation_
in front of the neural networks. Then, the induction on layers seems not applicable in calculating
adversarial Rademacher complexity for deep neural networks. The works of (Khim & Loh (2018))
and (Gao & Wang (2021)) indicate the difficulty of analyzing adversarial Rademacher complexity.
They analyze other variants of adversarial Rademacher complexity of DNNs.

**‘Tree Transformation’ Bound.** Khim & Loh (2018) introduces a tree transformation T and shows
that max∥x−x′∥≤ϵ ℓ(f (x), y) ≤ _ℓ(Tf_ (x), y). Then, we have the following upper bound for the
adversarial population risk. For δ ∈ (0, 1),


log [2]δ

2m [.]


_R˜(f_ ) _R(Tf_ ) _Rm(Tf_ ) + 2L _S(T_ ) + 3
_≤_ _≤_ _R_ _◦F_


It gives an upper bound of the robust population risk by the empirical risk and the standard Rademacher
complexity of T _f_ . _S(T_ ) can be viewed as an approximation of adversarial Rademacher
_◦_ _R_ _◦F_
complexity. However, the empirical risk Rm(Tf ) is not the objective in practice. This analysis does
not provide a guarantee for robust generalization gaps.

**FGSM Attack Bound.** The work of (Gao & Wang (2021)) tries to provide an upper bound for
adversarial Rademacher complexity. To deal with the max operation in the adversarial loss, they
consider FGSM adversarial examples. Then, the adversarial loss max∥x′−x∥≤ϵ ℓ(x, y) becomes
_ℓ(f_ (xF GSM ), y). By some assumptions on the gradient, they provide an upper bound for the
Rademacher complexity of ℓ(f (xF GSM ), y). However, the bound includes some parameters of the
assumptions on the gradients, and FGSM underestimates the adversarial examples. It is hard to
use this bound to analyze adversarial generalization. Therefore, the existing bounds give limited
interpretations in understanding the generalization of adversarial training.


-----

B.2 WHY LAYER PEELING IS NOT APPLICABLE IN ADVERSARIAL SETTING?

We first take a look at the layer peeling technique.


1
( ) = Eσ
_RS_ _H_ _m_

1
= Eσ

_m_

_≤_ _MdEσ_


sup
_h∈H_


_σih(xi)_
_i=1_

X


_σiWdρ(h[′](xi))_
_i=1_

X


sup
_h[′]∈Hd−1,∥Wd∥≤Md_


_σiρ(h[′](xi))_
_i=1_

X


sup
_h[′]∈Hd−1_


sup _σih[′](xi)_
_h[′]∈Hd−1_ _i=1_ 

X


_≤_ 2MdLρEσ


= 2MdLρRS (Hd−1),

In adversarial settings, if we directly apply the layer peeling technique, we have


1
( [˜]) = Eσ
_RS_ _H_ _m_



1
= Eσ

_m_


_≤_ _MdEσ_


sup _σi_ max _i[)]_
_h_ **_xi_** **_x[′]i[∥≤][ϵ][ h][(][x][′]_**
_∈H_ _i=1_ _∥_ _−_

X


sup _σiWdρ(h[′](x[∗]i_ [(][h][)))]
_h[′]∈Hd−1,∥Wd∥≤Md_ _i=1_

X


_σiρ(h[′](x[∗]i_ [(][h][)))]
_i=1_

X


sup
_h[′]∈Hd−1_


1
2MdLρEσ sup _σih[′](x[∗]i_ [(][h][))]
_≤_ _m_  _h[′]∈Hd−1_ _i=1_ 

Xm

1
= 2MdLρEσ sup _σih[′](x[∗]i_ [(][h][′][))]
_̸_ _m_  _h[′]∈Hd−1_ _i=1_ 

X

= 2MdLρRS ( H[˜]d−1),

where x[∗]i [(][h][)][ is the optimal adversarial example given a][ d][-layers neural networks,][ x]i[∗][(][h][′][)][ is the]
optimal adversarial example given a d − 1-layers neural networks. x[∗]i [(][h][)][ ̸][=][ x]i[∗][(][h][′][)][ is the main]
reason why layer peeling cannot be directly extended to the adversarial settings.

This is the main reason why the work we introduce above studied the variants of adversarial
Rademacher complexity. Once they take off the max operation by some approximation (e.g., let
max _x_ _x′_ _ϵ ℓ(f_ (x), y) _ℓ(Tf_ (x), y)), they don’t have the issue x[∗]i [(][h][)][ ̸][=][ x]i[∗][(][h][′][)][ and they can]
_∥_ _−_ _∥≤_ _≤_
use the layer peeling technique to bound the variants of adversarial Rademacher complexity. The
main drop back is that they change the definition of adversarial Rademacher complexity. These
bounds cannot provide theoretical guarantee on the robust generalization gap.

B.3 WHY COVERING NUMBER CAN HELP AVOIDING THIS ISSUE?

In our opinion, it is hard to modify the procedure of layer peeling such that it is applicable in
adversarial settings. Therefore, we try to bound the adversarial Rademacher complexity in a different
way, using the covering number. In the proof of Theorem 1, we can see that we can avoid the issue of
**_x[∗]i_** [(][h][)][ ̸][=][ x]i[∗][(][h][′][)][. Specifically, when we calculate the covering number of the whole function class][ ˜]F
directly, we only need to define the optimal adversarial examples x[∗]i [for a][ d][-layer neural networks.]
We don’t need to consider the optimal adversarial examples of neural networks with fewer layers.
This is the benefit of covering numbers.


-----

B.4 COMPARISON OF DIFFERENT ADVERSARIAL GENERALIZATION BOUNDS

**VC-Dimension Bounds.** A classical approach in statistical learning is to use VC dimension to
bound the generalization gap. It is thus natural to apply the VC-dim framework to adversarial setting,
as (Cullina et al. (2018); Montasser et al. (2019); Attias et al. (2021)) did. However, these works did
not provide a computable bound on the adversarial generalization gap, as explained next. let H be
the hypothesis class (e.g. the set of neural networks with a given architecture).

In the work of (Cullina et al. (2018)), the authors defined adversarial VC-dim (AVC) and gave an
bound on adversarial generalization gap with respect to AV C(H). However, they did not show how
to calculate AVC of neural works. Therefore, their paper did not provide a computable bound for
adversarial generalization gap.

In the work of(Montasser et al. (2019)), the authors defined the adversarial function class as
_LH[U]_
, where L is the loss and U is the uncertainty set. They bound the adversarial generalization gap
by
_LH[U]_ [, which is different from][ AV C][(][H][)][ of (Cullina et al. (2018)). However, the authors did not]
provide a computable bound of as well, which means that their paper did not provide a computable
bound of the adversarial adversarial generalization gap.

In the work of (Attias et al. (2021)), the authors assume that the perturbation set U (x) is finite, i.e.,
for each sample x, there are only k adversarial examples that can be chosen. They showed that the
adversarial generalization gap can be bounded by


1

_ε[2][ (]_




_kV C(_ ) log( [3]
_H_ 2 [+][ a][)][kV C][(][H][)) + log 1]δ


Note that there is a computable bound of V C(H), which is the number of parameters, thus in terms
of ”computable”, this bound is stronger than the previous two. However, this comes at a price: their
bound depends on k, the number of allowed examined perturbed samples. This is a deviation from the
original notion of adversarial generalization, where U (x) is assumed to be an infinite set (k ̸= +∞).
In contrast, our bound is for the ”original” adversarial generalization gap, which allows k = +∞.

**Adversarial Generalization Bounds in Other Settings.** The work of (Xing et al. (2021a;b); Javanmard et al. (2020)) study the generalization properties in the setting of linear regression. Gaussian
mixture models are used to analyze adversarial generalization (Taheri et al. (2020); Javanmard et al.
(2020); Dan et al. (2020)).

**Certified robustness.** A series of works study the certified robustness within the norm constraint
around the original data. Cohen et al. (2019) privides an analysis on certified robustness via random
smoothing. Lecuyer et al. (2019) studies certified robustness through the lens of differential privacy.

**Other Theoretical Studies on Adversarial Examples.** A series of works (Gilmer et al. (2018);
Khoury & Hadfield-Menell (2018)) study the geometry of adversarial examples. The off-manifold
assumption tells us that the adversarial examples leave the underlying data manifold (Szegedy et al.
(2013)). Pixeldefends (Song et al. (2017)) uses a generative model to show that adversarial examples
lie in a low probability region of the data distribution. The work of (Ma et al. (2018)) uses Local
Intrinsic Dimensionality (LID) to argues that the adversarial subspaces are of low probability, and lie
off the data submanifold.

C ADDITIONAL EXPERIMENTS

In this section, we provide additional experiments.

C.1 EXPERIMENTS ON VGG-11 AND VGG-13

In Figure 2, we show the experiments on VGG-11 and VGG-13. As we can see, the results are
the same as the results in Figure 3, the gap of product of Frobenius norm between standard and
adversarial training is large, which yields bad generalization.


-----

(a) (b) (c) (d)

(e) (f) (g) (h)


Figure 2: Product of the Frobenius norm in the experiments on VGG networks. The red lines are
the results of standard training. The blue lines are the results of adversarial training. The first row
are the experiments on VGG-11. The second row are the experiments on VGG-13. (a) and (e):
Generalization gap. (b) and (f): Margin γ over training set. (c) and (g): _l=1_

_[∥][W][l][∥][F][ of the neural]_
networks. (d) and (h): _l=1_

_[∥][W][l][∥][F][ /γ][ of the neural networks.]_

[Q][d]

[Q][d]

VGG-16

(a) (b) (c) (d)


(e) (f) (g) (h)

Figure 3: Product of the Frobenius norm in the experiments on CIFAR-10. The red lines are the
results of standard training. The blue lines are the results of adversarial training. The first row is
the experiments on VGG-16. The second row is the experiments on VGG-19. (a) and (e): Standard
Generalization gap. (b) and (f): Robust Generalization Gap. (c) and (g): _l=1_

_[∥][W][l][∥][F][ of the neural]_
networks. (d) and (h): _l=1_

_[∥][W][l][∥][F][ /γ][ of the neural networks.]_

[Q][d]

[Q][d]

1, **-Norm Bounds.** The 1, -norm bounds are shown in Figure 4. Similar the the Frobenius
_∥·∥_ _∞_ _∥·∥_ _∞_
norm bounds,The gap of _l=1_

_[∥][W][l][∥][1][,][∞]_ [between adversarial training and standard training are large.]
But the magnitude of _l=1_ _l=1_

_[∥][W][l][∥][1][,][∞]_ [is larger than the magnitude of][ Q][d] _[∥][W][l][∥][F][ .]_

[Q][d]

[Q][d]


-----

(a) (b) (c) (d)

Figure 4: Product of the ∥· ∥1,∞-Norm in the experiments on CIFAR-10. The red lines are the
results of standard training. The blue lines are the results of adversarial training. (a) _l=1_

_[∥][W][l][∥][1][,][∞]_
of VGG-16 networks. (b) _l=1_ _l=1_

_[∥][W][l][∥][1][,][∞][/γ][ of VGG-16 networks. (c)][ Q][d]_ _[∥][W][l][∥][1][,][∞]_ [of VGG-19]
networks. (d) _l=1_ [Q][d]

_[∥][W][l][∥][1][,][∞][/γ][ of VGG-19 networks.]_

[Q][d]

C.2 ABLATION[Q][d] STUDY OF MARGINS

In Figure 5, we show the results of the margins in 1[th], 3[th], and, 5[th]-percentile of the training dataset.
Since the (robust) training accuracy is 100%, the choice of percentile will not affect the results. As
we can see in the Figure, in all the cases, the margins of standard training are larger than the margins
of adversarial training. Since the margins appear in the divider in the upper bound of Rademacher
complexity, the margins of the training dataset have some small effects on the bad generalization of
adversarial training.

C.3 EXPERIMENTS ON CIFAR-100

**Perfomance.** In Table 2, we show the performance of standard training and adversarial training
on CIFAR-100 using VGG-16 and 19 networks. We can see that using smaller number of training
samples is unable to train an acceptable VGG-networks on CIFAR-100. Therefore it is hard use only
50000 training samples to study the trends of the weight norm using the experiments on CIFAR-100.
We compare the product of weight norm between standard and adversarial training.

**Product of Weight Norms.** In Figure 6, we show the results of on training VGG-19-16 and VGG19 on CIFAR-100. Similar to the experiments on CIFAR-10, we can see that the adversarially trained
models have larger weight norm that that of the standard trained model.


Table 2: Accuracy of standard and adversarial training on CIFAR-100 using VGG-16 and 19 networks.
For standard training model, we shows the clean accuracy. For adversarial training model, we show
the robust accuracy against PGD attacks.

No. of Samples 10000 20000 30000 40000 50000

VGG-16-STD 0.26 0.44 0.54 0.60 0.63
VGG-16-ADV 0.12 0.15 0.17 0.18 0.19
VGG-19-STD 0.32 0.47 0.53 0.58 0.62
VGG-19-ADV 0.12 0.16 0.17 0.19 0.21

C.4 WEIGHT DECAY

The upper bounds of adversarial Rademacher complexity suggest adding a regularization term on the
weights to improve generalization, which is essentially weight decay. In Figure 7, we provide the
experiments of adversarial training with and without weight decay. In Figure 7 (a) and (c), we can
see that adversarial training with weight decay has a smaller robust generalization gap. In Figure 7
(b) and (d), adversarial training with weight decay have a smaller product of weight norms. These
experiments show the relationship between the robust generalization gap and the product of weight
norms.


-----

(a) (b) (c) (d)

(e) (f) (g) (h)


(i) (j) (k) (l)

Figure 5: Ablation study of margins. The first to the 4[th] rows are the experiments on VGG-11, 13,
16, and 19, respectively.

VGG-16

(a) (b) (c) (d)


(e) (f) (g) (h)

Figure 6: Product of the Frobenius norm in the experiments on VGG networks on CIFAR-100. The
red lines are the results of standard training. The blue lines are the results of adversarial training.
The first row are the experiments on VGG-16. The second row are the experiments on VGG-19. (a)
and (e): Generalization gap. (b) and (f): Margin γ over training set. (c) and (g): _l=1_

_[∥][W][l][∥][F][ of the]_
neural networks. (d) and (h): _l=1_

_[∥][W][l][∥][F][ /γ][ of the neural networks.]_

[Q][d]

[Q][d]


-----

(a) (b) (c) (d)

Figure 7: Experiments on the effects of weight decay. (a) Robust generalization gap with or without
weight decay on VGG-16. (b) Frobenius norm with or without weight decay on VGG-16. (c) Robust
generalization gap with or without weight decay on VGG-19. (d) Frobenius norm with or without
weight decay on VGG-19.

D OPEN PROBLEM

In this section, we list some open problems.

**How to bridge the gap between the upper bound and the lower bound?** There are two ways:
one way is to show a depth/width-dependent lower bound as the reviewer suggested (increase lower
bound); another way is to show a depth/width-independent upper bound (reduce upper bound). We
briefly discuss which way is possible, and then discuss the technical challenges in both ways.

Which way is more likely to be true? If the upper bound can be improved to be depth-widthindependent (thus matching our lower bound), then fundamentally the lower bound cannot be
improved. Such a possibility exists. Actually, we are more inclined to this possibility, i.e., we tend to
believe it is more promising to reduce the upper bound to be depth-width-independent, rather than
increasing the lower bound. Anyhow, we don’t have strong evidence of this possibility.

Technical challenge on increasing the lower bound (obtain a depth/width-dependent lower bound). In
the current analysis, we construct a class of scalar networks to provide the lower bound. We obtain a
closed-form expression of the adversarial examples. To obtain a depth/width-dependent lower bound,
we need to: i) construct a more general function class of neural networks, and ii) then calculate the
optimal adversarial examples in this class of neural networks. Currently, the challenge lies in the first
step (construction). We have not tried hard to construct the function class so far, and we leave it to
future work.

Can we reduce the upper bound (remove the dependence on depth/width in the upper bound)? This
seems quite difficult by the current analysis. More specifically, the dependence h[√]dlogd is probably
unavoidable by our current approach of calculating the covering number. Despite the technical
difficulty, we suspect that reducing the upper bound is doable by using a new tool other than covering
number and layer peeling. This is surely nontrivial.

**Why adversarial training yields larger weight norms?** In our opinion, it is because we require
the additional capacity of the neural networks to fit the adversarial examples. As in the discussion of
the work of (Neyshabur et al. (2017a)), we require more capacity of the model to fit random labels.
A model with larger weight norms has a better ability to fit the training data. There might be other
reasons, for example, the loss landscape of the minimax problem of adversarial training, the implicit
bias of PGD attacks, or the implicit bias of adversarial training.

**Is the widely used regularization techniques essentially reducing weight norms?** In adversarial
training, there are many training tricks to reduce overfitting and yield better generalization, for
example, stochastic weight averaging, early stopping, adversarial weight perturbation, and cyclic
learning. It is an open problem that whether these techniques are related to the weight norms.

**How to design better algorithms to improve generalization?** Our analysis suggests that adding
regularization to the weight norms could improve generalization. The explicit regularization to


-----

control the weight norms is weight decay, which is widely used. How to design implicit control on
the weight norms is an open problem.


-----

