Adversarial Rademacher Complexity of Deep Neural Networks
Authors: Jiancong Xiao
Yanbo Fan
Ruoyu Sun
Zhi-Quan Luo
Venue: ICLR 2022 Submitted (2022)
Keywords: Adversarial Robustness
Generalization
Rademacher complexity

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.

Under review as a conference paper at ICLR 2022
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 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 method 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.
INTRODUCTION
Deep neural networks (DNNs) Krizhevsky et al. Hocchriier Schmidhuber (1997) have )
become successful in many machine learning tasks such computer vision (CV) and natural language processing (NLP). But they are shown to be vulnerable to adversarial examples (Szegedy et al. (2013); Goodfellow 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- -rraaieelly-traieeed 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 the test set (Madry et al. (2017)). Recent works (Gowal al. 2022)); Rebuffi al. (2021)) mitigate the overfitting issue, but it still has 20% generalization gap between robust test accuracy (60%) and training accuracy (80%). On the other hand, 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 Wi, 22,-. ..... Wa in each of the d layers have Frobenius norms bounded by MI.... MM. and all the data æ have fy-norm bounded by B, given m training samples, the generalization gap between population risk and empirical risk scales O I M//mm) with high probability (Ncyshabur ct al. (2015)). Another works provide different norm-ban based complexity, such as || 1.00 -norm -norm
(Bartlett & Mendelson (2002)) and spectral norm (Bartlett et al. (2017)). The work of (Golowich
al. (2018)) reduces the dependence on depth-d from 2d to vd. The proofs of the above bounds based on the induction on layers, which is also called the 'peeling off" techniques. For more details,
section 3

---

Under review as a conference paper at ICLR 2022
In adversarial training, adversarial Rademacher complexity was first introduced in (Yin al. (2019)
Khim & Loh (2018) to measure the robust generalization gap. They prove that the robust generaliza- tion gap of linear function (z w" æ) scales as (( + e) /m), where M is the upper bound of norm of the weights w and e is the perturbation intensity of adversarial attacks. Awasthi et al. (2020)
provides upper bound in two-layers neural network cases. For depth-2, width-h neural networks, with high probability, the generalization gap scales O(BB + e)/hgM M2v log m/m), where q is the dimension of the data æ.
One might think it is straightforward use the induction methods in (Neyshabur al. 2015) Golowich et al. (2018) to cxtend the adversarial Rademacher complexity in (Yin et al. (2019) Khim Loh| (2018)) to multi-layers cases. However, seems challenging apply their induction methods to adversarial cases. Let the adversarial loss be |ax]|x==' Se ((f(x'), v) 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 (202I)) also indicate the difficulty of analyzing adversarial Rademacher complexity of DNNs. They analyze other variants 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
of [B (B+c)lldlood Vm
Mi
Similar the existing bounds of standard Rademacher complexity of deep neural nets, the bound includes the product of weight norms I[= [|Will, but they are trained by different algorithms. We empirically show that the adversarially trained weight norms are larger than the standard trained weight norms, which provide an explanation why adversarial training did not generalize well. Our 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 higher-order dependence on the depth and width and an additional factor c.
2. We provide experiments 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 the large weight norms of an adversarially-train 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 E F to minimize the population risk R(f) = (= w)>-(((( (x). v)], where D is the true distribution, ((-) is the loss function. Since D is unknown, we minimize the empirical risk in practice. Given m ii.d samples S (#11811).
(Im vm)H }. the empirical risk is Rm, (f) = 1 I ((.()
The generalization gap or generalization error is defined as follow:
Generalization Gap R(f) Rm
Rademacher Complexity. A classical measure of the generalization error is Rademacher com- plexity (Bartlett & Mendelson (2002)). Given the hypothesis class H. the (empirical) Rademacher complexity is defined as
Rs(H) = E. sup Σ on v,)],
hER
where o, are i.i.d Rademacher random variables, i.c. o, equals to 1 or -1 with equal probability. Define the function class l vL)l(=) E F}. we have the following generalization bound.
2

---

Under review as a conference paper at ICLR 2022
Proposition 1. Moohri et al. (2018; Bartlert & Mendelson 2002 Suppose that the range of the loss function ((f(z), 9) is [0, CJ. Then. for any E (0, with probability at least - 6, the following holds for all f F.
log A
R() S (m) 2CRs((() + (
2m
2.2 ROBUST GENERALIZATION GAP AND ADVERSARIAL RADEMACHER COMPLEXITY
Robust Generalization Gap. Let ((f(()))) v) == max x' -ll, Se ((f(f(()))))))))))))(())) y) be the adversarial loss. The adversarial population risk and the adversarial empirical risk are
R( = (x,))) max (((('),)) and Rm( = Σ we--llsse
max e(f(a)), Us), Se
1=1
respectively. In this paper we consider general Ep attacks for p 2 1. The robust generalization gap is defined as follow:
Robust Generalization Gap R(f) Rf)(f).
Let the adversarial hypothesis class be é (é([(x). E F), according to Proposition 1 we have the following adversarial generalization bound.
Proposition 2. Yin et al. (2019)) Suppose that the range of the loss function {(f(),, v) is [0, CJ. Then, for any d E (0, 1). with probability at least 1 the following holds for all f E F,
log ard
R(f) - Rm (f)+ +30
2m
Binary Classification. We first discuss the binary classification case, then we discuss the extension the multi-class classification case in section Following (Yin al. (2019); Awasthi al. (2020). we assume that the loss function can be written as (()()), v) Φly I (x) where á is non-increasing
function. Then
max (f (x'), v) = <min (
Assume that the function @ is T by Talagrand's Lemma (Ledoux & Talagrand (2013)
have ((=( Lo Rs(F). (F), where define the adversarial function class
f= 1 (x, lam==lll,s
inf ya 2f EF.
Adversarial Rademacher Complexity. We define (F) as adversarial Rademacher complexity. Our goal 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= Wa ... )), |Will s M,, 1... 1....d), .d],
(2)
where p(-) is an element-wise -ipsscit activation function, Wi are h; x h matrices, for 1= 1. d. We have ha and hy is the dimension the data æ. Let max (ho...... ha) 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 (a, b)-group norm ||[]| Ila.b as the a-norm of the b-norm of the rows of W. We consider two cases, Additionally, we assume that |X]] |X||p.oe B.
Frobenius norm and 10 norm in equation
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.

---

Under review as a conference paper at ICLR 2022
Definition (e-cover). L 0 and ..((;.)) be metric space, where d(:,) :) is (aseudo)-metric C V is an E-cover of , for any u E V. there exists v' E C s.t. d(e, v") S E. Define the smallest [C] as E-covering mumber of V and denote as (V, d(. -).))
Next, we define the E-covering number of function class F. Given the sample dataset S {(21. ".), (am, Bmm] with 2; E R. let [l = EE= f(z,, y1)² be a pseudometric of F. Define the e-covering number of F be (F, lls,e). Let D be the diameter of F with
D = 2 max ||/]|s
Proposition 3 (Dudley's integral). The Rademacher complexity R(F) satisfiy
12
/
D/2
Rs(F) S
VlogN(F, lls: e)de.
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 J 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 al. (2014); Chen ct al. (Crlliiarliiii & Wagner 20:7):10m (0 et al. (2017)) This has led to a series of work aimed at training neural networks robust to such perturbations (Wu al. (2020); Gowal et al. (2020): Wu et al. (2020) and works aimed at designing more sophisticated attacks to attack the classifiers (Athalye) ct al. 2018); Tramer et al. 2020); Chen et al. (2017).
Adversarial Generalization.
The work of (Schmidt et al. 2018 Raghunathan et al. 2019 Zhai
jt al. (2019) have shown that in some scenarios achieving adversarial generalization requires more data. The work of (Attias et al. ( 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 pac-bayesian approach to provide a generalization bound for neural networks. [Sinha et al. (001)) 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 analyze adversarial generalization
(Taheri et al. (2020); Javanmard et al. (2020): Dan et al. (2020)) The work of (Allen-Zhh & Li (2000) explains adversarial generalization through the lens of feature purification.
Adversarial Rademacher Complexity. Researchers have analyzed adversarial Rademacher com- plexity in linear and two-layers neural networks cases. In linear cases, the upper bounds can be directly derived by definition (Khim & Lohj (2018); Yin et al. (2019)). In two-layers neural networks cases, an upper bound derived using Massart's 's Lemma (Awasthi al. (2020)) It seems that these proofs cannot be extended to multi-layers cases. Moreover, based on the definition of adversarial function class FF in equation 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 (202T)) 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.
I the candidate functions are not composition functions, but with an
In Appendix [. we provide the details of the above bounds and discuss why these methods seem not applicable 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

---

Under review as a conference paper at ICLR 2022
4 OUR SOLUTION OF ADVERSARIAL RADEMACHER COMPLEXITY
The following T'eeorem states an upper bound of adversarial Rademacher complexity in the Frobenius norm cases.
Theorem (Frobenius Norm Bound). Given the function class F in equation under Frobbe- nius Norm, and the corresponding adversarial function class F in equation The adversarial Rademacher complexity of deep neural networks (s(F) satisfies
24 Vm
(F) I
max (1,
[II 1,00 + +c)
huh log(3d)
II 1=1
Mi.
(3)
1=1
By assuming that L, p s 2, | I,,00 B, and h max fho ,hal, we have
BB () dlog(d) Il Mi
Rs(F) < 0
(4)
Vm
Because of the inf operation of the function in F, we cannot peel off the layers 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
Step 1: Diameter of F.
We first calculate the diameter of F. We have
max feF
llflls s 2 max - H|| X p.00 + c)
M - D. [=1
Step 2: Distance to fe. Let Ci be covers of (1[WilFF S Mi). 1 1,2, Let
F= (ff x WSp p( ((Wfx) ( Wf G,1=112--
and f (f (x,
+ inf
|| || yf(x')lf FF}.
For all f F, need find the smallest distance to Fe, i.e. need calculate the
min |I - lls... JeF fe
v(I,y) D, given f and f", let x- arg inf -/ yf vf(x') and xF arg inf = yf (x').
x if f(x') ) 2 (x)))) and (z) Wop(.- W... p(Wf=) .))) Then
Let {
if f(x') (x(x))
D
[f(z) - fz)) = (z)( - (x)l s 19)(2) - gd(2)) + ... +1gh 19 (2) g3(2)) S
2M
Let 6, 2Me//dD 1 1,... d, we have max fet f |l fells Σ Di=1 2M:
D6: < E.
Step 3: Covering Number of F. Then, We can calculate the e-covering number N [ls.e).
Because Fe is a E-cover of F. The cardinality of f is
N(F 11- (ls.sss) 1 < 3dD
E hyh1-1
(5)
2c
Step 4: Integration. By Dudley's integral, we obtain the bound in Theorem
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 calculate the other things using this adversarial example. In contrast, if want to do it layer by layer, the optimal adversarial example will be changed when we add or peel off layer. This is why the induction methods fail in adversarial settings.
5

---

Under review as a conference paper at ICLR 2022
Theorem 2 (11.0 Norm Bound). Given the function class F in equation 2 under - lo norm. and the corresponding adversarial function class F in equation (7). The adversarial Rademacher complexity of deep neural networks (F)(F) satisfies
d II Mi.
24 Vm [1|
Rs(F)=
S
10:00 + +c)2g-
huh log (3d)
1=1
In the case of || ||1,00 -norm, -norm,, the bound is similar to the bound in the Frobenius norm case except the term max {1, /// Therefore, for all p 2 1, the || 011, -norm -norm bound have the same order in equation (4).
Theorem (Lower Bound), Given the function class of DNNs F in equation (2) and the corre- sponding adversarial function class F in equation (7). Exist sample dataset S, s.t. the adversarial
Rademacher complexity of deep neural networks Rs(FF) satisfies
(B
Mc
Rs(F) 2 St
Vm
The proof of the above Theorem 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, hy / d. In the next section, extend the adversarial Rademacher complexity to the Multi-class classification cases.
MARGIN BOUNDS FOR MULTI-CLASS CLASSIFICATION
5.1 SETTING FOR MULTI-CLASS CLASSIFICATION
The setting for multi-class classification follows (Bartlett & Mendelson (2022) ) In a K-class classification problem, let y (1.2.... KK. The functions in the hypothesis class map X' to RK, the k-th output of f is the score of f(x) assigned to the k-th class.
(x))]y The function makes correct prediction if and only if (x(), y) > 0. We consider particular loss function {(f(z),))
Define the margin operator M (x)) v) [f())]y [
e, (M((x)) v)). where y and Φ, E [0, 1] is the ramp loss:
1
t
(t())
1
D<t<>
0
127.
The loss function {(((x), y) satisfies:
1 A arg max [f()), 8( {(f())))) & ([f(x)) <> 7 max(f(x)]))
(8)
>'E[K]
v'
Define the function class E == ((x,)) de (M(( F.. Since o (t) E [0, 1] and
(-) is 1 1/y-Lipschitz, by combining (8) with Theorem 1 we can obtain the following direct corollary as the generalization bound in the multi-class classification.
Corollary (Mohri al. (2018)). Consider the above multi-class classification setting. For any fixed y > 0, we have with probability at least 1 - 6, for all f E F,
P P(Ray)D {
y # arg max [f())]g
y s'Elk]
log ?
[(f((x))lu 5 max(f(x;)ll) + 2Rs((()))))))) + +31 y'
2m
In adversarial training, let (c) = fx': || - æ11 S c) and we define the adversarial function class := = {(x,)) max (f((''), y) f F}. We have

---

Under review as a conference paper at ICLR 2022
Corollary Yin et al. 2019)). Consider the above adversarial multi-class classification setting. For any fixed y > O, we have with probability at least 1 6, for all f E F.
Ple.))D 3x' E (e) s.I. y F arg max (s('')) y'ElK]
log 2/2
1(3 E B2 (e) s.t. [f(x))y S m
+31
8'
2m
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 (7. The adversarial Rademacher complexity of deep neural networks Rs({z) satisfies
Rs((r) S 7/m
48K
max (1, (1,+ 11 p.00 16)
Σ 1=1
hahi log (3d)
II t=1
M.
(9)
The ||. nnomm bound is similar, except the term max (1xx11,00 (1, (1,g.-).... Below we sketch the proof. Step 1: Let F ((x,y) + inf infip/"= - ((())))), E F}, then Rs(Ey) I (Rs((zx). Step 2: By the Lipschitz property of (-), Rs((xx) s Rs(FF)) Step 3: The
calculation of (F*) follows the binary case.
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
Bvd
d 1=
M1
and Rs((=) s o (B (B+ M1
Rs((F) S o
(10)
7/m
where we use the upper bound of RF(F) in Golowich et al. (2018))
Factors. In the two bounds, the algorithm-independen factors include Sample size B. perturbation intensity e, depth-d, and width-h. To simplify the notations, we let
Catd = Bvd d and Cadv = (B + /olg be the constants in standard and adversarial Rademacher complexity, respectively. We simply have Cadv Cata-
Algorithn-Dependent Factors. In the two bounds, the margins 7 and the product of the trix norms Hi ||Wil depend on the training algorithms. To simplify the notations, we de- fine W.td = I [Will/y if the training algorithm is standard training. Correspondingly: let W Wade = II= W/ll// the training algorithm adversarial training. In the next section, we conduct experiments to show that Wadv > Wstd-
Notation of generalization gaps. In the next section, we use E(- and E(-) to denote the standard and robust generalization gap. We use fetd and fadu denote the standard- and adversarially-tren -traaddd model. Our goal is to understand why the robust generalization gap of an adversarial training model large, which quite different from the standard generalization gap of a standard-trained model, i.e. we want to analyze why E(fadu) > & {fsta). Based on the standard and adversarial Rademacher complexity bounds, is suggested that
E(fadu) CadyWark and E(fsta) CstaWatdt
To analyze the individual effect of factors Cadv and Wadv: we further introduce two kinds of generalization gaps, the robust generalization gap of a handard-trainee model (E(faa) and the standard generalization gap of adversarially-traine model (E (f(av))) The standard and adversarial Rademacher complexity suggest that
E(Sata Godu Wstd and E(Sadv) x CstaWado. ado-
7

---

Under review as a conference paper at ICLR 2022
6 EXPERIMENT
As we discuss in the previous section, the product of weight norm I |Will and the margin ? are algorithm-dependen factors controlling the generalization gap. We provide experiments comparing the difference between these terms in standard and adversarial settings, Since the bounds also hold 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 Appendix C
stoudard Goneralmtion dep
Adbutt sener Inttan GSp
Product of jroberkut RATtY
14l5
Product nammarrarge
18
VGG-19
2.14
2.5
08-
03
015
310
Farter chomree
(8)
(b)
(c)
(d)
Figure 1: Product of the Frohenius 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 E {(fadu) and the red line represents E {(sta). (b): Robust Generalization Gap, the blue line represents & {fade) and the red line represents (fsta). (c): II |Wille of the neural networks. (d): ITi_ ||Wille/y of the neural networks, the blue line represents Wadv and the red line represents Wold-
Training Settings. For both standard and adversarial training, we use the stochastic gradient 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 lo PGD adversarial training (Madry et al. (017)). 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 [ 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, set the margin over training set to be 5th peeceentile of the margins of the data points in S. i.c. Pres (f (z; [ys] - maxyfu. [<)] 34) E S}. In adversarial settings, we set the margin over training set to be 5th -percenttlee of the margins of the PGD- adveraavesaaial examples of S. The choice of 5th -prreeeeteeeee 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-traine -taineddd and adversarially-trainee models. We use the results using 50000 training samples to discuss the experiments. Firstly, in Figure 3 (a), we can see that E {(sra) is small (=10.45%). ) On the other hand, an adversarial-trained model has a larger standard generalization gap (E(fad))=26.33 22).3%.) It is widely observed phenomenon that adversarial training hurts standard generalization. One reason is that adversarial training overfits the adversarial examples and performs worse on the original examples. Secondly, in Figure B (b), the robust generalization
gap of a standard-traines -aaaaaddd----edddd---- model is very small (É(fst)) 0). It is because the standard-trained model 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 O. On the contrary, ((aax)=58.990 90%, i.e. the adversarial generalization is bad. This is also observed in the previous studies, and we aim to discuss the reasons.
Adversarially-traanee Models Have Larger Weight Norms, i.e. Wad > Watd- In Figure 3 (c), we can see that the I [|ill standard training. In (d), the I [|Wi]|r to the Figures in (c). Wadv is larger than W.td- One of the reasons why Wadv > W std is neural networks need more capacity to fit the adversarial examples.
F of adversarial training is much larger than the I[ [[ of r is divided by 7, we can that the Figures is similar
8

---

Under review as a conference paper at ICLR 2022
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 ) a degenerated case, with training error=100%. In the other three cases, the training errors~0%
Standard-trained models
Adversarially-traine models
Types of Generalization Gaps
Standard
Robust
Standard
Robust
Training Errors Test Errors
0%
100%
0%
0.02%
10.45%
100%
26.34%
58.92%
Generalization Gaps
E 11044)=10
{(aaa)=00%
=
{fsta)=00% is a degenerated case. In Table we show the training and test errors for all kinds of generalization gaps. We 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 E(fat)
that the robust training error for a standard-trained model is equal
(Cedde Wstd/ /m) becomes a trivial bound. In the other three cases, the training errors are all =0%. The generalization gaps are meaningful. We aim to analyze why {fadv) > E(fsta) by analyzing & {fadv) > E(fadv) > E(fata).
The effect of Codv- We first compare the difference between E(fado) and E(fado). We can see that {(faav) = 58.90% > {(Sado) = 26.34%. For an adversarially-traiee model, the robust generalization gap is larger than the standard generalization gap. If and standard Rademacher complexity as approximations of the robust and standard generalization gap, i.e., E (faáv) x Cado Wadv and {ffdv) xx Cata Wadu, {(adu) > E(fadv) can be explained by Cude >> Coed since W Wado are the same in the two bounds.
the bounds of adversarial
The effect of W ado Similarly, we compare the difference between {(fav) and E(ftt)) We see that E(fadv) 26.34% E(fata) 10.45%. This is widely observed phenomenon 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(fado) & CstaWads adv and E(ftta x Watd {(favv) > E(favo can be explained by Wade >> Watd- In summary, we can use simple formula to explain why E(fudo) > {(fadv) > E(foca) through the lens of Rademacher complexity. That
Wads > CataWade adv > CstaWsta-
The difficulty of adversarial generalization comes from two parts, the constant Cads and the weight norms W The first part Cadv is independent of the algorithms. It comes from the minimax problem of adversarial training itself, and cannot be avoided. The second part Wade depends on the algorithms. Therefore, the product of the weight norms is 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 || norm. We can see that the 10 111.ce-norm -norm bound has larger magnitude than the Frobenius norm bound. CIFAR-100. Finally, the large weight norms suggest adding
Then, we provide the experiments a regularization term on the weights during training. We provide experiments with and without weight decay and see that the with weight decay has smaller generalization gap and smaller IL |Will |/ //>. These experiments suggest the strong relationship between robust generalization gap and the product of weight norms.
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 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.

---

Under review as a conference paper at ICLR 2022
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 Carlimi, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint 1rXiv:1802.00422 2018.
Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for adversari- ally 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. Opectrally-norallii margin bounds for neural networks. arXiv preprint arXiv: 0eerr7766..4499. 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. 7oo: Zeroth order optimization based black-box attacks 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 1.4.:::80060147711 2018.
Chen Dan, Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially robust gaussian classification. In International Conference 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.03599 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 Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
10

---

Under review as a conference paper at ICLR 2022
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pp. 4034-2078. PMLR, 2020.
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv:1810.0951/ 2018.
Mare Khoury and Dylan Hadfield-Menell. On the geometry of adversarial examples. arXiv preprint /rXiv:/8/1.0022 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 convolu- tional 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. 356-672. IEEE, 2019.
privacyy
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:180I.02611 2018
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 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. 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 general- ization in deep learning. arXiv preprint arXiv: (ee.: 2017a
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized 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. arX6v:1906.00032, 2019.
Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Tim- othy Mann. Fixing data augmentation to improve adversarial robustness. arXiv preprint arXiv:2/03.01946, 2021.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially robust generalization requires more data. 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: 1556, 2014.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. arXiv preprint 1005517700.0571, 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: 1110//11100000 2017.
11

---

Under review as a conference paper at ICLR 2022
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties 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, Cam- bridge University Press, 2019.
Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust general- ization. arXiv preprini 20xx::0004005844, 2020.
Yue Xing. Qifan Song, and Guang Cheng. On the generalization properties of adversarial training. In International Conference on Artificial Intelligence and Statisties, 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: 190.. 2019.
12

---

Under review as a conference paper at ICLR 2022
A PROOF OF THE THEOREMS
A.1 PROOF OF THEOREM 1
Theorem (Frobenius Norm Bound). Given the function class F in equation (2) under Frobbe- nius Norm, and the corresponding udversarial function class Ff in equation (1). The udversarial Rademacher complexity of deep neural networks (F( satisfies
RF(FF= S
24 Vm
max max
X|| 11:00 +c)L d-1
Σ hohu-1 log (3d) II
Mi.
1=1
By assuming that L = 1, p $ | 1,00 S B, and h = max . .ha). we have
(B ( ( dlog(d) II Mi
Rs(F) < o
Vm
Because of the inf operation of the function 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 J directly. Before we provide the proof, we first introduce the following lemma.
Lemma (Covering number of norm-balls) Let B be lg norm ball with radius W. Let d(x1, | Z2llp- Define the e-covering number of B as N (B, E,), we have
NBB e.)) s (1+ 2W/E)9
In the of Frobenius norm ball of matrices, we have the dimension q = and N(B, || (|,,e) (1 2W/c) S (3W/c)mxn.
Lemma 2. if E {,/]|< æ1I1p S c}, we have
|| |+ S max (1, 1,/1->=-)//+/ 0,,00 + +c)-
Proof: If 2 r", by Holder's inequality with 1/r" 1/p + 1/s,
| ||+- S sup || 1p = ||| az 1lp = q² | l1 = 9¹ x²= 1-1 $100 1p.
Equality holds when all the entries are equal. p < r", we have
| ||r Σ | llp-
Equality holds when one the entries of 0 equals to one and the others equal to zero.
Then
|| < max (0,x((1, 1, - }|105 ll
< max (1, 1- - (1l=sll + ||:0 aF(lp))
< maxx(, 1-- - 1pp.0 + c).
Lemma 3. Let A be m X n matrix and be a n-dimension vector, we have
||A b112 S ||
Proof: let Ag be the of A, 1 1... m, have
m
m
372
14 bl1b
Σ (A,b)2
Σ
|A
|
||
13

---

Under review as a conference paper at ICLR 2022
Step 1: Diameter of F. We first calculate the diameter of F. Vf F, given (æ,, V.). let x; inf - (x.), and we let at be the output of at pass through the first to the 1 layer, we have
((.x,11)] =
inf vf(xa)) | -
Wap -1-
|Walle 1 )|1
|Walee 1lp(Wa-12 p())ll
Ma 1112
< 1:g-1
d-1
1=2
[-d-1
Mr -
1=1
(11)) $
Mr max X + E),
where inequality (i) is because of Lemmaa 3, inequality (ii) is because of the Lipschitz propertiy of activation function p(-), inequality (iii) is because of Lemma Therefore, we have
d
2 max
[ills = fet
1 m
(())))))))
< 21 max mmxmm(111)) (1,x², p.00 + +e)
II [=1
M - D.
Step 2: Distance to Fo.
Let G be covees (l[Walle & Mi), ( 1,2, Let
F (f Wäp(WW p(- ((Ff)) ... )), WF C, 1,2 .d}
and frv ( (x.
inf y (f(')\/ EF). + | |=>="|,
For all E F, we need find the smallest distance to fe, i.c we need to calculate the
max min || - folss
feF feE
....,,,, V(r,, - -,.... n. given f and fe with IW; - Willr -0,1=1 1,... consider
If vi) f((,..))))) vi)l
=| ||: |
inf (1((x())
inf (ar))
||l, |
Let
x7 arg
inf (x(), and a5 = arg 1
inf ys (xr))
||
-
we have
If v.) - fz vi)l -lvi((x)) - (=
=I5(x;) - (z(xx))
Let
xf if f(x)) 2 (xx x if [(x)) (m))
2
14

---

Under review as a conference paper at ICLR 2022
Then,
lf( vi) - fela,, vell -1((=")-f(x;) - -z)(z))
-
Define (-)
(x(2) = Wop(WW-1P(:.. - Wa+1p(We... (WWi) ((Wf))...)))
In words, for the layers b > a in (.), the weight is Wi, for the layers 2 2 1 in 98 (.). the weight is Wy. Then we have f(z) (2.). f(z) of (z)). We can decompose
If(=) (=:)
(1,) 0((2)1
(11)
==)( (d(=)) +... Fd 1-1 (z)) (z(=
<110(=,) 22(=1) +... d- (=x) (((=
To bound the gap [s(z)) [z))) we first calculate l g((ا,م) for l = 1,.., d.
19 - (2.) g(((2)1
= -Waplo Wap(s
|aal
(9)
2 d4 (2-)l12
(00
d spz- II - 2=1+1
where (i) due Lemma (ii) is due to the bound of || and the Lipschitz of p(-), (ii) is because of the definition of o8 (2). Then
14 (2.) ga(2.))
ST d-
II MolWip((lHH(s)) - (>)()>+<>)))>>
j=1+1
= = d--1
II j=1+1
- -
(12)
( d d--
II j=H+1
- (
II Mgbilo((/=+()))))111
s=H+1
15

---

Under review as a conference paper at ICLR 2022
where inequality (i) is due Lemma 3, inequality (ii) is due to Lemma 3 the assumption that [ - Wfll S 6g. is lefted to bound (x))) we have
(z)))
= -
(13)
S1P M, max (|| + c).
combining inequalities 12 and
(33
we have
s=(=))]
= Mj
< $1.-1
d--1
81 max
p,00 +c)
(14)
M1
D8;
2M
Therefore, combining inequalities
15 and 14), we have
[f(z)
(z))
$ (1))
gd(21)) + (x1) gd(2))l
(15)
d
Do
2Mi
1=1
Then
D8
max min
- Mls
fer f
2M
Let 8 = 2Mi//dD, 1,00 -,.... d, we have
d
D6
max min FEF fEEF
|| f'lls
<
<
2M
1=1
Step Covering Number F. We then calculate the e-covering number N(F, 11-1ls,sss)))) E). Because fo is a e-cover of F. The cardinality of f
N(F || [|s. =|=1
II 1=1
(5)
d
3M
=
3dd
Sdd ) lihe
81
25
where inequality (i) due Lemma 1.
Step 4, Integration.
By Dudley's 's integral, we have
12
D/2
VlogN(E.1 lls. e)ds
Rs(F)s s
Vm
12
D/2
h1l4 log (3dD/2e)d /2
(16)
Vm
Jo
1=1
12D
Σd 1==1
hihh-1
(
Vlog(3d/25)ds
/m
16

---

Under review as a conference paper at ICLR 2022
Integration by part, we have
1/2
V /log(3d/22)) )de
3 //Terfol / /log 3d) + / log 3d
3 3/Texp(- -onll-vvooge Vlog v log 3d
(17)
V Vlog 3d
2 2ooo 3d
log 3d.
Plug equation 17 equation
16 have
Rx(FF v m
24
max - ]1 l,co + +e)
h log(3d)
Mr II 1=1
A.2 PROOF OF THROREM 2
Theorem (1. Bound), Given the function class F in equation (1) under || and the corresponding adversarial function class IE in equation (2). The adversarial Rademacher complexity of deep neural networks Rx(F) satisfies
10l1,,---ooo norm.
d
Rs(F) I
/m (|X
24 pp + +)
Σ hyh4 log (3d) II M.
The proof mimilar to the proof of the Frobenius norm bound. We first introduce the following inequality.
Lemma 4. Let A be x n matrix and be n-dimension vector, we have
||A - bl100 S ||Alli..ol1|bla..
Proof: let Ag be the rows of A, i= 1... m, have
|A - bllco = max |Abbl S max ||A, = ||A||1.00||||6
Step 1: Diameter of F. We first calculate the diameter of F. vʃ E F, given (æ,, wi), let a inf =.]l[llss,, vf(x)) and we let a be the output of x; pass through the first to the l layer, we have
17

---

Under review as a conference paper at ICLR 2022
inf [0 Se
yz(2
Wapp( W Wa-120 xxx
Wall
)0
|WallF 11 -100l=
(2 olo
-d-1
Mr |
(60) x
M 11.00 +),
where inequality (i) is because Lemma 4, inequality (ii) is because of the Lipschitz propertiy of activation function p(-), inequality (iii) is because of Lemma 2. Therefore, we have
2 max [lflls = jeB
f(m w.)e))
s 21. ( p,00 + +c) M D.
II 1=1
Step 2: Distance to Fo. Let Cj be dy-covers of (|W7]11 Mi), 1 1,2, ... ,d, 1.... hi,
where Wi is the 1th row of Wi. Let
-WW .. )), W = F ( : W p(Wfx)
= "...,,,,,,,, 1,2...,d
and f = ( (x,
yf(w')// EF.. inf || | 1, Se
For all f F, we need to find the smallest distance to Fe, ie. we need to calculate the
max min II l'l
fer fefe
v(a,, vi), i 1,... n. given J and je with [ W < .......,,,........ 1 d, we have [| - 11 S di. By the same argument the step of the proof Theorem 3, we have
d
D8
max min feF f.
- falls
2M
Let 6; = 2M/eddD,1=1 11:=1,1.. d, we have
d
Dō;
max min TEF feE
|| fells <
Σ < E.
2M
Step 3: Covering Number of F. We then calculate the e-covering number N/ (1-lss,sss.)) E). Because Fo is a e-cover of F. The cardinality of F is
d A
3M,
.dd.
N(F, |l [ls. e) =1 III
ci
-(30))
81
25
t=
1=1
where inequality (i) is due Lemma 1.
18

---

Under review as a conference paper at ICLR 2022
Step 4, Integration. part, we have
By the same argument as the step 4 of the proof Theorem 1, integration by
d
d
24 - Vm (| p.:0 + e)Lp
Rs(F)
Σ
hih
(3d(3d) II Mr
A.3 PROOF OF THEOREM 3
Theorem (Lower Bound). Given the function class F in equation (2), and the coressponding adversarial function class F equation (1), Exist sample dataset S, s.t. the adversarial Rademacher complexity of deep neural networks RF(F) satisfies
(B+
I M
Rs(F) Ω
m
The proof of the above Theorem is based on constructing a scalar network. By the definition of Rademacher complexity, if H.' a subset of H. we have
Rs(H(') = E,g - sup Σ m. hET!
oohlais v:)] < E
sup NEW
Σ
aahh(a, ve) = Rs(HH)-
Therefore, is enough to lower bound the complexity of Fr in a particular distribution D, where f a subset of F. Let
F' F'= fa
inf || -011 Se
Myw" x w R w| S M1}. yMa-
We first prove that F is a subset of F. In F, we let the activation function p(-) be identity mapping. Let
M 0
0 0 ...
W1
E
R
xho
Wi =
E R Rlihhe-1, 1 == 2.... ,d. (18)
Then, we have W|] < Mt and F with additional constraint in equation words, F is subset F.
18 reduce to F In other
turns that need lower bound the adversarial Rademacher complexity 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 9 {a - ywu x/w E R2, ([lle S W) and ② {x ywu ar w IR9, ||l]|r S W), the udversarial Rademacher complexity RR Rs(9) satisfies
inf inf [nf| -elle
1
Rs(3)= 2 max Rs(g),
2/m
Since the standard Rademacher complexity
W
Rs(9)
E Σ o, Ilr
m
let ||a.||| = B with equal entries for 1,... m. Lemma we have
Rs(9)= =
E2 as max (1, -
m i=l
19

---

Under review as a conference paper at ICLR 2022
By Khintchine's inequality, know that there exists universal constant such that
E o
com.
Then, we have
Rg( = cW
mm max 11, -
Therefore,
emax (1, 9
W. WW
Rs(()= 2 max RF(F),
2/m
1
2c
<max (max(1,9
RF(F)
+ 2c
1+ 20
2/m
(B+ max ( [1, 1111-+-31 3W
+
1 2c
m
Let W = -I Mr, we have
Rs (F) 20 max (1, 1-
+ (B+ M
vm
where r = 2 for frobenius norm bound and r r= for || -nor 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 (I). The adversarial Rademacher complexity of deep neural networks Rs( satisfies
Rs((F) S
7 m max 1
48K
X|| p.00 c)
Σ
d
h4h4 log(3d) II M.
The (1, -noomm bound similar, except the term max (1. -
Proof: Firstly, we have
[(f(x),))
max (M((x())) v))
||a-n'll 1l
5 inf M(f(x).v))
2 ||ar ||
inf
(1((x)) (ax(](())))>))
= dy ||0- I'
inf
inf ([f(=)], [f())))))
= - inf inf ([(())] [(x))v)))
V' |--x'
max Φ5( inf ([f(=)], [f(x))
F" ||
Define
1² (xx v)
inf (I(())), [f(x)]))) 7 =k),
Im Se
we now prove that
max Φ2( ( inf (I(())) - [f(m)) = max de (1.((1 ())
y' 11-s5
If
inf inf ([(())) (f(x))r) sn
s' ||
20

---

Under review as a conference paper at ICLR 2022
have
inf
inf (If(z)ly f(x))y)) inf h" h" 9)
y'vy l
If
inf
inf
([f(z)) (f(x))br) ?
n'*y || |l=-s"/s
we have
Φ inf inf v'zu v ([f())ly [f(x)),)) @inf 1tth (z, y)) = O.
Therefore, we have
(((()),)) Φ. (inf (xx y)) = max o (1 (x: y))
&
Define 71th (x. y) in f(x))a + (y (2) K
=>]f k)lff F), we have
R(ex) S ( o H²) S R(H)))
(19)
where inequality (i) is the Lemma 9.1 of MMhrii et al. (2018), ) inequality (ii) is due to the Lipschitz property of (-). Now, define (xx y) = inf jn | (z)), f(x)]{), we have (x y) (xx,y) + 7 k). Define the function class
F = (2, = inf || Is-- ([f(x)), - [F
We have
m
R(H*)
Eng sup h EHL
oh (a.;
Ear sup ht* E*#
Σ Ti
5 (1,
+ +y k)
i=1
Fag sup h**
Σ
oi (x,
+
F. Σ
1 =k)
t=1
1=1
m
Eg sup
o (x.
m
JEEF
=R(FF)
Finally, we need to bound the Rademacher complexity of R(F)). Notice that
[f(=)lμ [f(x)]} (W3 WW (z))...))
and we have IW have
W 2M, By Theorem 3 (the results in binary classification case),
R(F*)
48
max (a, (1, -- [[I 11,00 + e)
hyh log(3d)
II Mr.
(20)
Vm
1=1
Combining inequalities 20
and 19 we obtaín that
48K Rs({z) <
max 1, g - X|| p.00 + +e)
d
hy44 log
II
d
Mr
m m
B DISCUSSION ON EXISTING METHODS FOR RADEMACHER COMPLEXITY
In this section, we discuss the related work, discuss the existing methods calculating Rademacher complexity, and identify the difficulty of analyzing adversarial Rademacher complexity.
21

---

Under review as a conference paper at ICLR 2022
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 9 F as the function class {g fIf E F). By Talagrand's Lemma, we have Rg o f) I Rs().. Based on this property, can obtain Rs(FF) s where Fi is the function class of I-layers neural networks. Since the Rdemacher complexity of linear function class is bounded by III Mi/ by induction. We can
D(BM//Vm) we can get the upper bound O remove the Lp by assuming that Lp (e.g. Relu activation function).
Golowich al. 2018) improves the dependence on depth-d from 2 to vd. The main idea is to rewrite the Rademacher complexity [-] as E, exp In[-]- Then, we can peel off the layer inside the In(-) function and the 2" now appears inside the In(-).
Covering Number Bounds.
Bartlett et al. (017) uses covering numbers argument to show that
the generalization gap scale as
B BIE IWill mm
| 2/3 3/2
2/3
where || is the spectral norm. The proof is based on the induction on layers. Let Wi be the weight matrix of the present layer and X2 be the output of X pass through the first to the - layer. Then, one can compute the matrix covering number (((WXX)), || (12,e) by induction.
Adversarial Generalization Bounds. Researchers have analyzed adversarial Rademacher com- plexity in linear and two-layers neural networks cases. In linear cases, the upper bounds can be directly derived by definition (Khim & Lohj (2018); Yin et al. (2019)) ). In two-layers neural networks cases, an upper bound is derived using Massart's s Lemma (Awasthi et al. (2020)) These proofs cannot be extended multi-layers cases. Moreover, based the definition of adversarial function class F in equation (1. the candidate functions are not composition functions, but with an inf operation in front 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 (202I) indicate the difficulty of analyzing adversarial Rademacher complexity. They analyze other variants of adversarial Rademacher complexity of DNNs.
Khim & Loh (2018) introduces tree transformation T and shows that max ((I(x),)) v) < (T)()), v)- Then, we have the following upper bound for the adversarial population risk. For e (0,
'Tree Transformation' Bound.
log 2
R()) R(T)) & Rm (T)( 2LRs 3/
2m
It gives upper bound of the robust population risk by the empirical risk and the standard Rademacher complexity of T a f. (T o F) can be viewed as an approximation adversarial Rademacher complexity. However, the empirical risk (T)) 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 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 ma {(x,, y) becomes ((f(#FGMM) v). By some assumptions on the gradient, they provide upper bound for the Rademacher complexity of ((f(#)GMM) y). However, the bound includes some parameters of the assumptions 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.
22

---

Under review as a conference paper at ICLR 2022
B.2 WHY LAYER PEELING NOT APPLICABLE IN ADVERSARIAL SETTING?
We first take a look at the layer peeling technique.
m
Rs(H) = E8 m.
sup o.h(aa)) NER
1=1
1 -Eo- m
m Wap(h'(ax)) (x:))
sup I.lall.
< Ma
1
sup Li
Σ ozp(h((as)) (a:))
$ L B
sup MEHHa
m
m=
2MaL,Rs
In adversarial settings, if we directly apply the layer peeling technique, we have
1
m
Rx) E, m
sup hEH
oi
max a
h(x()]
i=1
20 -
Se
1
= E
sup
or (a
MEHHa
S.aa
m
Σ (x;
$ Mg
sup MEHa-
m
1
m
22Mg
<
sup La
Σ
a. a (z)
m
1
# 2Mg
sup MEHa
a. (zf((z)(h)))
1=1
R((aa,)
where 2; (h) is the optimal adversarial example given d-layers neural networks, x; (h') is the optimal adversarial example given a 1-layers neural networks. (h) * x;²) is the main reason why layer peeling cannot be directly extended to the adversarial settings.
This 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 se {(f(x)))) S f(T) y)), they don't have the issue (h) & (h') and they can use the layer peeling technique 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, try to bound the adversarial Rademacher complexity in a different way, using the covering number. the proof of Theorem 1, we can see that we can avoid the issue of x; (h) * x; (h'). Specifically, when we calculate the covering number of the whole function class F directly, only need to define the optimal adversarial examples x for 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.
23

---

Under review as a conference paper at ICLR 2022
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 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 given architecture).
In the work of (Cullina et al. (2018), the authors defined adversarial VC-dim (AVC) and gave an bound adversarial generalization gap with respect to AVC(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 L where L the loss and the uncertainty set. They bound the adversarial generalization gap by C2 which is different from AV AVC( of (Cullina et al. (018))) However, the authors did not provide 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 al. (202I)), the authors assume that the perturbation set (x)) is finite, i.c.. for each sample æ. there are only k adversarial examples that can be chosen. They showed that the adversarial generalization gap can bounded by
3 (VEVC(H) log(; / + a))VC(H)) + +og )
Note that there is a computable bound of VC(H), which is the number of parameters, thus in terms of "commutable", 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 adversarial generalization, where U(x) assumed be an infinite set (k * +00). In contrast, our bound is for the "original" adversarial generalization gap, which allows k +00.
Adversarial Generalization Bounds in Other Settings. The work of (Xing al. (202 a b Ja
vanmard 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 HadfieldMMenel] (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 generative model to show that adversarial examples lie in low probability region of the data distribution. The work of (Ma 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 show the experiments VGG-11 and VGG-13. As see, the results 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.
24

---

Under review as a conference paper at ICLR 2022
Protucto THOATRR
Prodect narraaaagg
VGG-11
1.0
3000
20.6
3003
6000
250
2000
3068
3606
40000
50.0
3000
2006
3050
4000
300
500
350
3400
4000
300
(8)
(b)
(C)
(d)
3.-
VGG-13
34-
28
7.
245
155
1.5
35
3000
3000 4000
3059
-200
30008
30.06
-0000
3200
200
4000
30003
20000
-000
(e)
(f)
(g)
(h)
Figure 2: Product of the Frobenius norm in the experiments VGG networks. The red lines
the results of standard training. The blue lines are the results of adversarial training. The first row
the experiments on VGG-11. The second row the experiments on VGG-13. (a) and (e):
Generalization gap. (b) and (f): Margin over training set. (c) and (g): I[ [|Wi]] of the neural networks. (d) and (h): I ||i]ll/Y of the neural networks.
0.5
VGG-16
2:1
1.5
033
075
011
31
(8)
(c)
(d)
Standard Coneralationomm Cap
labuak Sencre kazzet Cap
Prodacur Interra
Productal hamraVagge
2.15
32
VGG-19 19
9.75
035
518
(e)
(h)
Figure 3: Product of the Frobenius norm the experiments on CIFAR-I0. 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 (c): Standard Generalization gap. (b) and (f): Robust Generalization Gap. (c) and (g): I ||[]] of the neural networks. (d) and (h): I ||Wllee/ of the neural networks.
I|- ol Norm Bounds. The || norm bounds are shown in Figure 4 Similar the the Frobenius norm bounds, The gap of [[ || between adversarial training and standard training are large. But the magnitude of [[ /i is larger than the magnitude of [[ [[l]..
25

---

Under review as a conference paper at ICLR 2022
Podtucel Rere
PRODUC FOrTIAMArge
Preeedt narraaarge
25
100
20.0
20327 4000
2.00
2507
2008
20.00
-0.00
30.00
3000
20.86
3000
4000
X59
1000
2.00
2008
-0.25
1000
(a)
(b)
(C)
(d)
Figure 4: Product of the || -Norm in the experiments CIFAR-10 10. The red lines the
results of standard training. The blue lines are the results adversarial training. (a) II Willl of VGG-16 networks. (b) I [[Wi] of VGG-16 networks. (c) I |Will of VGG-19
networks. (d) II ||Will,,s// of VGG-19 networks.
C.2 ABLATION STUDY OF MARGINS
In Figure we show the results of the margins in th 3th, and, 5th -eeepeecee of the training dataset. Since the (robust) training accuracy 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 we show the performance of standard training and adversarial training CIFAR-100 using VGG-16 and 19 networks. We 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 study the trends of the weight norm using the experiments CIFAR-100. We compare the product of weight norm between standard and adversarial training.
Product of Weight Norms. In Figure we show the results of on training VGG-19-16 and VGG- 19 on CIFAR-100. Similar to the experiments on 100 we can see that the adversarially trained models have larger weight norm that that the standard trained model.
Table 2:
Accuracy standard and adversarial training on CIFAR- 100 using VGG- and 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-I6-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 WRIGHT 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 smaller robust generalization gap. Figure (b) and (d), adversarial training with weight decay have smaller product of weight norms. These experiments show the relationship between the robust generalization gap and the product weight norms.
26

---

Under review as a conference paper at ICLR 2022
1 percentile
3000
2006
3000
6000
250
2000
3008
40000
5040
1000
2006
3050
4000
3000
5000
3153
3460
4005
300
(8)
(b)
(C)
(d)
3 pereenttle
2000
3000
X00
1200
3008
30.0
-0000
3000
300
4000
3000
30050
4000
(e)
(h)
5th -pereentlle
2.5
S.merd ommp
Figure 5: Ablation study of margins. The first to the 4th rows are the experiments on VGG-11, 13, 16, and 19, respectively.
Generall alaoraalinn
Product proberk
PP temoniorin
VGG-16
1.8
22
04
Farter chmmme
(8)
(b)
(c)
(d)
Geserdlasoon Gap
Nargh
ofddactor i-bberka hery
Lo/todacte insonnu VemenNrron
VGG-19 19
62
$230
13.23
12223
10200
E.51
220
2.22
(e)
(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 adversarial training. The first row are the experiments on VGG-16. The second row are the experiments on VGG-19, (a)
and (c): Generalization gap. (b) and (f): Margin over training set. (c) and (g): I[= Will of the neural networks. (d) and (h): I[= [Wllee/> /> of the neural networks.
27

---

Under review as a conference paper at ICLR 2022
0.70
HEBETLL Narr AN222
R005s De oution C4p
0.00
0.80
0.6
0.0
10
12
044
0.4
04
0300
62
050
3000
2053
20.66
40.00
30000
3000
2000
3:30
4000
30020
2000
2003
36.6
-0.00
30000
3000
20.6
3000
4000
X69
(8)
(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 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 two ways: one way is to show bound); another way is to show depthhwwdth-indeeeene briefly discuss which way is possible, and then discuss the technical challenges in both ways.
seaphh/wwtt--eepeddee lower bound as the reviewer suggested (increase lower upper bound (reduce upper bound). We
Which way is more likely to be true? If the upper bound be improved to be depth-width- independent (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 increasing the lower bound. Anyhow, we don't 't have strong evidence of this possibility.
rather than
Technical challenge on increasing the lower bound (obtain a hypth/width-dependee lower bound). In the current analysis, we construct class of scalar networks to provide the lower bound. We obtain a lower bound, we need to: i) construct 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.
closed-form expression of the adversarial examples. To obtain a heephh/widh--dependee
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 hy /dllogd 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 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 require the additional capacity of the neural networks to fit the adversarial examples. As in the discussion of the work of (Neyshabur et al. (0177a), 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
28

---

Under review as a conference paper at ICLR 2022
control the weight norms is weight decay, which is widely used. How to design implicit control on the weight norms is an open problem.
29


Reviews:
[{"review_id": "vyYb7rWGeag", "reviewer": "Reviewer_dFnk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Relevant topic of theoretical investigation of adversarial examples and adversarial training, that has gained traction in recent years.\n- Improved theoretical result over prior art.\n- Meaningful experiments based on the theoretical results, that suggest some reasons why adversarial training does not generalize well.\n- Clear and well-written paper (a few typos remain).\n\nWeaknesses:\n- It would be great if the paper included a comparison to existing adversarial bounds based on Rademacher complexity or other frameworks, e.g., plotted for a toy example or small network. Lacking this, it is harder to judge the improvement the current paper makes over prior results in terms of tightness of the bound. Moreover, it might be worth comparing the contribution to other types of theoretical approaches in the field, e.g., the provable methods that the paper cites.\n\nQuestions and other comments:\n- It would be good to underline that the bounds provided also hold for convolutional neural networks earlier than the experiments section (or, more generally, what layers are covered).\n- What is the impact of using PGD adversarial examples in practice instead of the optimal perturbation?\n- Is it reasonable to consider a loss in the range 0-1 for neural networks?\n- Are Rademacher complexity bounds tight enough for neural networks to be informative or applicable in practice?\n\n[Update post discussion] I am raising my rating by one point, following the exchanges below.", "summary_of_the_paper": "This paper proposes new generalization bounds for adversarial training in neural networks based on the Rademacher complexity. These are more general than previous results in that they apply to neural networks of any depth. Experiments are performed on CIFAR-10 and CIFAR-100 with multiple VGG architectures. These, related with the main quantities appearing in the proposed bounds, provide an explanation for the limited generalization capacity of adversarial training.", "summary_of_the_review": "Good theoretical result supported by experimental evaluation on relevant topic.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "j84L6QQvyOp", "reviewer": "Reviewer_Vmod", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the main contribution of this paper is interesting. It directly overcomes the difficulties in deriving adversarial Rademacher complexity rather than using other variants. It provides both the upper bound and lower bound, both of which are important. \n\nHowever, there are still a lot of things that can be improved in this paper. Below are my major concerns towards this paper (ordered in importance). My rating is currently weak accept given the importance of the upper and lower bounds, but it could be adjusted based on the author response towards my concerns. \n\n[1] My understanding towards the adversarial training and the adversarial Rademacher complexity is that, both adversarial-trained and standard-trained neural networks have their own standard Rademacher complexity and adversarial Rademacher complexity. So \"the generalization gap of adversarial training loss and adversarial testing loss\" is larger than \"the generalization gap of standard training loss and standard testing loss\" for both adversarial-trained (denote as A and B) and standard-trained neural networks (denote as C and D), i.e. A>B and C>D. On the other hand, through experiments, it is observed that the adversarially trained neural networks obtains larger norms, so its generalization is worse, i.e. A>D. Is my understanding correct? Is it essential to provide evidence for A>C or B>D in other to conclude A>D? In Figure 1, what does the \"generalization gap\" refer to?\n\nIn addition, could you provide some insights on why the norm of adversarially trained model is larger? Why does increasing the samples size lead to a larger norm/margin? Also, given these observations, is there any way to improve the generalization performance of adversarial training? Is there any implications on the loss landscape of adversarial robust neural networks? The current Section 6 displays some observations but no detailed insights.\n\n[1](as important as the above) The current proof of Theorem 3 only says \"By the results of the lower bounds of ..., we obtain that ...\". Please provide more details on the existing results and how to obtain the final result. Please provide some concrete illustrations to this either in pdf or in the discussion. \n\n[3] The literature review of generalization of adversarial training in this paper only considers those about Rademacher complexity. There are many other studies working on the generalization from other theoretical aspects. Below are some important articles. Please do some literature research in this general area of theoretical study and include in this paper.\n\n-----------------Papers which provide both upper bound and lower bound-----------------\n\nDan, Chen, Yuting Wei, and Pradeep Ravikumar. \"Sharp statistical guaratees for adversarially robust gaussian classification.\" International Conference on Machine Learning. PMLR, 2020.\n\nXing, Yue, Ruizhi Zhang, and Guang Cheng. \"Adversarially Robust Estimate and Risk Analysis in Linear Regression.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n-----------------Papers about generalization properties-----------------\n\nAllen-Zhu, Zeyuan, and Yuanzhi Li. \"Feature purification: How adversarial training performs robust deep learning.\" arXiv preprint arXiv:2005.10190 (2020).\n\nJavanmard, Adel, Mahdi Soltanolkotabi, and Hamed Hassani. \"Precise tradeoffs in adversarial training for linear regression.\" Conference on Learning Theory. PMLR, 2020.\n\nJavanmard, Adel, and Mahdi Soltanolkotabi. \"Precise statistical analysis of classification accuracies for adversarial training.\" arXiv preprint arXiv:2010.11213 (2020).\n\nTaheri, Hossein, Ramtin Pedarsani, and Christos Thrampoulidis. \"Asymptotic behavior of adversarial training in binary classification.\" arXiv preprint arXiv:2010.13275 (2020).\n\nWu, Dongxian, Shu-Tao Xia, and Yisen Wang. \"Adversarial Weight Perturbation Helps Robust Generalization.\" Advances in Neural Information Processing Systems 33 (2020).\n\nXing, Yue, Qifan Song, and Guang Cheng. \"On the Generalization Properties of Adversarial Training.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\nZhai, Runtian, et al. \"Adversarially robust generalization just requires more unlabeled data.\" arXiv preprint arXiv:1906.00555 (2019).\n\n\n[4] The main idea of this paper is not hard to follow, and the authors make a lot of comparison to existing literature. It would be great if the authors could make it clear about the following questions when describing the proof steps in Theorem 1:\n\n   (1) Which steps are different from the derivation of standard Rademacher complexity? Which steps are not essential? If we use Theorem 1 and take \\epsilon=0, what steps should we modify to obtain the standard Rademacher complexity mentioned in Section 5.3?\n\n   (2) Which steps are different from the literature about adversarial Rademacher complexity? Which steps do they skip?\n\n   (3) Could you explain the remark after before Theorem 2 in detail?\n\n\n\nMinor issue (not ordered in importance):\n\n[5] When mentioning your contributions in the last paragraph of Section 1, could you write some descriptions? \n    (1) For the first contribution, is there any interesting findings in the bound?\n    (2) For the second contribution, could you answer your why question? \n\n[6] Please consider remove Proposition 1 and 2, and move Proposition 3 to the appendix. Proposition 1 and 2 do not help deepen the understanding of the main goal of this paper. Similarly, please shorten Section 3 for inequalities which are unrelated to the main goal. \n\n", "summary_of_the_paper": "This paper overcomes some technical difficulties to provide adversarial Rademacher complexity of deep neural networks. Compared with existing literature which try to show other variants of adversarial Rademacher complexity, this paper directly works on adversarial Rademacher complexity itself. This paper provides both the lower bound and the upper bound. Besides, this paper conduct numerical experiments to combine with the theoretical bound to justify why adversarial training has a worse generalization than standard training.", "summary_of_the_review": "This paper provides some important results about the adversarial Rademacher complexity so I vote for weak acceptance. But there are many issues towards the experiments, proofs, and the writing of this paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XBu2HuRJSj", "reviewer": "Reviewer_DjdD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1.\tThis paper provides new bounds for adversarial Rademacher complexity. \n2.\tThis paper is well written and easy to read.\n\nWeaknesses: \n\nThe empirical validation in this paper seems insufficient:\n\n1. Although the authors verified that the product of weight norm in adversarial training is indeed much larger than that in standard training, I think this is not a strong empirical verification of the proposed bound. The reason is there existing some constants in the bounds in adversarial training and standard training, which may be different. Therefore, simply comparing the product of the weight norm is not rigorous. I would like to see more discussion on this. We know that some of the existing deep learning theory may be only mathematically correct, thus providing sufficient empirical evidence to show the consistence between the theory and practice is important. \n\n2. There exists a product of the weight norm in the proposed bound, which implies that the trained model can generalize better if this product is smaller. Therefore, can we use some techniques to regularize this product during training to improve the generalization ability. The authors are recommended to give such kind of experiments to support their theoretical results. \n\n====after rebuttal===\n\nAfter reading the response from the authors, I raised my rating. ", "summary_of_the_paper": "In this paper, the authors developed an upper bound of adversarial Rademacher complexity, which includes the product of weight norms. This implies that the large weight norm hinders from achieving good generalization performance in adversarial. The authors also empirically show that the product of weight norm in adversarial training is indeed much larger than that in standard training. ", "summary_of_the_review": "1. This paper provides a new complexity bound for adversarial training. \n2. The empirical validation of this paper is insufficient. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9LnLFyUo1gc", "reviewer": "Reviewer_Ma5T", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The question investigated in the paper (described above) is natural and was posed as an open question by previous papers.\n\nThe main technique seems reasonable. \n\nThe experiments suggest that the change in the margin and the product of the weight norm may explain the larger generalization gap  (compared to the standard generalization).\n\nWeakness: showing a depth/width-dependent lower bound could have been nice.\n\n-Citing the paper https://arxiv.org/pdf/1810.02180.pdf (ALT19 and JMLR) is very relevant in the section \"Adversarial Generalization\".\nIt provides uniform convergence results In the case of a finite number of perturbations for a mixture of classifiers. The analysis goes through the Rademacher complexity as well.\n\n-In section 3: d^2 should be 2^d?", "summary_of_the_paper": "The main result of the paper is an upper bound on the Rademacher Complexity of neural networks in the case of adversarial examples (meaning, analyzing it with respect to the robust loss class).\n\nPrevious bounds for linear classifiers and shallow neural networks were investigated by Yin et al. (2019) and Awasthi et al. (2020).\nThe known methods for upper bounding the Rademacher Complexity for deep neural networks in the standard case don't apply in this case.\n\nThe main idea in this paper is to analyze the covering numbers directly (as opposed to calculating them by induction on the layers).\n ", "summary_of_the_review": "I recommend accepting the paper.\n\nI read the overview of the main proof, but not the fully detailed proof.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper made a solid theoretical contribution on the adversarial  generalization bounds of multi-layer neural networks.

However, the paper, at the current form, has many issues in the claim that "the product of the norm can explain the generalization gap":

(1). Weight decay. The authors uses the weight norm as the proxy for generalization gap, however, it is unclear to me that "adversarial trained networks have a larger generalization gap" can be explained by the product of weight norms. To carefully verify this, the authors have to at least carefully tune the weight decay, to the largest possible extend so the generalization error is not hurt, and compare the product of the weight norms in this scenario.  Without weight decay, the neural networks might learn a lot of redundancies in the weights (especially with adversarial training)  which makes the product of the norm to be too large. 

The authors do perform experiments showing that with weight decay, the generalization gap becomes smaller and the norms become smaller, however, it is totally unclear to me that the weight decay considered in the experiments are actually optimal -- It could still be the case that with proper weight decay, the product of the norms in adversarial training is actually smaller comparing to that of the clean training. 


Moreover, the authors should also clarify that **the product of the norms, according to the experiments, are simply too large and they can not be used in the theoretical result to get any meaningful generalization bounds**.



(2). The product of the norm in Rademacher complexity  is tight: This  claim only holds for neural networks with 1 neurons per layer. Once there are more than one neurons, there can simply be one neuron that learns f(x) and the other learns -f(x) and they completely cancels each other. So the product of the norm is obviously NOT TIGHT for any neural network with MORE than ONE NEURON per layer. In fact, the gap can be INFINITELY large. 


Unfortunately, I like the paper very much and I hope this paper could be published, however, the claims  "the product of the norm can explain the generalization gap" is simply too misleading and ill-supported. I encourage the authors to completely remove this claim and submit the paper to COLT.
Decision: Reject