PAC-Bayesian Spectrally-Normalized Bounds for Adversarially Robust Generalization
Authors: Jiancong Xiao
Ruoyu Sun
Zhi-Quan Luo
Venue: NeurIPS 2023 poster (2023)
Keywords: Pac-Bayes
Adversarial Robustness
Generalization

Abstract: Deep neural networks (DNNs) are vulnerable to adversarial attacks. It is found empirically that adversarially robust generalization is crucial in establishing defense algorithms against adversarial attacks. Therefore, it is interesting to study the theoretical guarantee of robust generalization. This paper focuses on norm-based complexity, based on a PAC-Bayes approach (Neyshabur et al., 2017). The main challenge lies in extending the key ingredient, which is a weight perturbation bound in standard settings, to the robust settings. Existing attempts heavily rely on additional strong assumptions, leading to loose bounds. In this paper, we address this issue and provide a spectrally-normalized robust generalization bound for DNNs. Compared to existing bounds, our bound offers two significant advantages: Firstly, it does not depend on additional assumptions. Secondly, it is considerably tighter, aligning with the bounds of standard generalization. Therefore, our result provides a different perspective on understanding robust generalization: The mismatch terms between standard and robust generalization bounds shown in previous studies do not contribute to the poor robust generalization. Instead, these disparities solely due to mathematical issues. Finally, we extend the main result to adversarial robustness against general non-$\ell_p$ attacks and other neural network architectures.

PAC-Bayesian Spectrally-oormalized Bounds for Adversarially Robust Generalization
Jiancong Xiao!"", Ruoyu Sun 2.3,4,,, Zhi- Zhi-Quan 2,44 University of Pennsylvania, PA, USA
Scool of Data Science, The Chinese University of Hong Kong, Shenzhen, China Shenzhen International Center for Industrial and Applied Mathemates
'Shenzhen Research Institute of Big Data
jcxiaodupenn.co edu,, (sunruoyu, patuuoyu,uuozq.. luozq]eechhl edu. cn
Abstract
Deep neural networks (DNNs) are vulnerable to adversarial attacks. It is found empirically that adversarially robust generalization is crucial in establishing de- fense algorithms against adversarial attacks. Therefore, it is interesting to study the theoretical guarantee of robust generalization. This paper focuses on norm-based complexity, based on PAC-Bayes approach (Neyshabur et al., 2017b). The main challenge lies in extending the key ingredient, which a weight perturbation bound in standard settings, to the robust settings. Existing attempts heavily rely on addi- tional strong assumptions, leading loose bounds. In this paper, we address this issue and provide spectrally-normaaizae robust generalization bound for DNNs. Compared to existing bounds, our bound offers two significant advantages: Firstly, it does not depend on additional assumptions. Secondly, it is considerably tighter, aligning with the bounds of standard generalization. Therefore, our result provides different perspective on understanding robust generalization: The mismatch terms between standard and robust generalization bounds shown in previous studies do not contribute to the poor robust generalization. Instead, these disparities solely due to mathematical issues. Finally, we extend the main result to adversarial robustness against general non-&p attacks and other neural network architectures.
Introduction
Even though deep neural networks (DNNs) have impressive performance on many machine learning tasks, they are often highly susceptible to adversarial perturbations imperceptible to the human eye (Goodfellow et al., 2015; Madry al., 2018). They have received enormous attention in the machine learning literature over recent years and a large number of defense algorithms (Gowal et al., 2020; Rebuffi et al., 2021) are proposed to improve the robustness in practice. Nonetheless, it still fails to deliver satisfactory performance. One major challenge stems from adversarially robust generalization. For example, Madry et al. (2018) demonstrated that the robust generalization gap extend up to 50% on CIFAR-10. In contrast, the standard generalization gap is notably small practical settings. Hence, theoretical question arises: Why is there huge difference between standard generalization and robust generalization? This paper focuses on norm-based generalization analysis.
In classical learning theory, one of the most well-known findings is that the generalization bound for neural networks depends on the norms of their layers (Bartlett, 1998). To further explore the generalization of deep learning, series of work aimed at improving the norm-based bound (Bartlett &
Work done while CUHK(SZ). Corresponniigg Authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Mendelson, 2002; Neyshabur et al., 2015; Golowich et al., 2018), mainly using tools of Rademacher complexity. The tightest bound given by Bartlett et al. (2017), using covering number approach. Neyshabur et al. (2017b) gave different and simpler proof based on PAC-Bayes analysis, presented an almost equally tight bound. The key step involves bounding the change in output of the predictors in response to slight variations in the predictor parameters. In particular, considering fw (x) as the predictor parameterized by w, the crucial component for providing the generalization bound lies in bounding the gap [fw(x) fw((x) (x)), where w and w' are close. The weight perturbation bound, which addresses this aspect, is presented Lemma 2 of Neyshabur et al. (2017b).
To comprehend the limited robust generalization capabilities of deep learning, a line of research endeavors to extend the norm-based bounds into robust settings. However, this has proven to be a challenging mathematical problem, as researchers have attempted the mentioned approaches including the Rademacher complexity (Khim & Loh, 2018; Yin et al., 2019; Awasthi et al., 2020), covering number (Gao & Wang, 2021; Xiao et al., 2022a; Mustafa et al., 2022), and the PAC-Bayes analysis (Farnia al., 2018). yet a satisfactory solution remains elusive. For more details, see Section 2.
We use the PAC-Bayesian approach as an ex- ample illustrate the mathematical challenge. The weight perturbations in adversarial settings differ from those in standard settings. When considering two predictors f-()) and fw((+) the adversarial examples against these predic- tors are distinct, leading to a gap referred to as robust weight perturbation (defined later in
Weight Permnrsnoon Bounds 2017)
Leans.
Stondred Gentriizioo
Bound
(Thooren
Main challenge
inspyr
Lemaro 10
Robost Weight Pottursation (Frootem
Robust Generati sioon iisnnd Problenc
Problem 1). It remains unclear how to estab- lish bound for robust weight perturbation. The combined changes in input and weights can po- tentially cause a significant alteration in the func- tion value. The main challenge is illustrated in Figure I, the details of which will be provided in Section 6.2. As result, Farnia et al. (2018) introduced additional assumption to control this gap and provide bounds in adversarial settings. However, the assumption imposed limitations on the effectiveness of the bounds due to two reasons: Firstly, the assumption of sharp gradients throughout the domain is strong requirement. Secondly, without this assumption, the bounds become bounded (=+))). Similarly, other existing norm-based bounds also depend on additional assumptions or involve higher-order terms in certain factors.
Figure I: Demonstration of the main challenge of providing robust generalization bound. The weight perturbation bound (Neyshabur et al., 2017b) seems hard to extend to adversarial settings.
Given that the existing robust generalization bounds are much larger than standard generalization bounds, these results suggest possible hypothesis: The significant disparity between standard and robust generalization in practical scenarios could potentially be attributed to the mismatch terms between the standard bounds and the robust bounds. However, verifying this hypothesis is challenging because it remains unclear whether the existence of these terms or assumptions is due to mathematical issues. Therefore, the current bounds are insufficient to address the main theoretical question.
In this paper, we address this problem and present PAC-BByes spectrally- normalized robust gen- eralization bound without additional assumptions. Our robust generalization bound is tight as the standard generalization bound, with an additional factor representing the perturbation intensity Furthermore, our bound is strictly smaller than the previous generalization bounds proposed in adversarial robustness settings. To provide an initial overview of the main result, we begin by defining the spectral complexity of a dllayer neural network fw as follows:
((fw) = 1I_
Eaw / IW.
i=1
where W; is the weights of fw in each of the d layers.
Theorem (Informal). Let m be the number of samples and the training samples x is bounded by B. e is the attack intensity. Let fw X + k be d-layer feedforward network. Then, with high probability, we have
Robust Generalization S (0
2

---

When 6 = O, the bound reduces to the standard generalization bound presented by Neyshabur et al. (2017b). Our results give a different perspecitve from existing bounds. The additional factors or assumptions are solely due to mathematical considerations. Our findings suggest that the implicit difference of the spectral complexity 4 ((fw) likely contributes to the significant disparity between standard and robust generalization.
Technical Proof. It is shown that the robust weight perturbation not controllable with- out additional assumptions. Therefore, exist- ing tools are not sufficient to derive the bounds. The main technical tools to derive the bounds are two folds. Firstly, we introduce crucial inequality to address this problem, which is the preservation of weight perturbation bound under lp attack. Secondly, (Neyshabur et al., 2017b) in terms of the margin operator. This modification enables the applica- tion the aforementioned inequality. To further extend the bound more general settings, establish framework that allows us to derive robust generalization bound from its corre- sponding standard generalization bound. The framework's demonstration is presented in Figure 2, and detailed information regarding Figure 2 will be provided in Section 6.3.
Pertaflation
Lenza 7.1
SSendeed Firmeraliotinn Bonné (Theorem
Openatoe 6.1)
(Key Lemma)
imply
Pertafrativnn Margin Operator (Lomana 6.2)
Lamma 7.2
Robusl Geneniivation Bound (thoerers
restructure the proof by
Figure 2: Demonstration of the framework: per- turbation bound of robustified function. Under this framework, a standard generalization bound directly implies a robust generalization bound.
Furthermore, extend the results to encompass general settings. Firstly, although fp adversarial attacks are widely used, real-world attacks are not always bounded by the lp norm. Hence, we extend the results to cover general attacks. Secondly, achieved with WideResNet (Rebuffi et al., 2021; : Croce et al., 2021), we demonstrate that the results be extended to other DNN structures, such ResNet.
the current state-of-the-arr robust performance is
The contributions are listed as follows:
1. Main result:
We provide PAC-Bayesian opectrally-normalizedd robust generalization bound without any additional assumption. The derived bound is as tight as the standard generaliza- tion bound and tighter than the existing robust generalization bound.
2. Our results give a different perspecitve from existing bounds. The significant disparity between standard and robust generalization in practical scenarios is not attributed to the mismatch terms between the standard bound and the robust bound. The implicit difference of the spectral complexity ((/w) possibly contributes to the significant disparity.
3. We provide a general framework for robust generalization analysis. We show how obtain a robust generalization bound from a given standard generalization bound.
4. We extend the result to general adversarial attacks and other neural networks architectures.
2 Related Work
Adversarial Attack. Adversarial examples were first introduced in (Szegedy et al., 2014). Since then, adversarial attacks have received enormous attention (Papernot et al., 2016; Moosavi-Dezfool al., 2016; Carlini & Wagner, 2017). Nowadays, attack algorithms have become sophisticated and powerful. For example, Autoattack (Croce & Hein, 2020) and Adaptive attack (Tramer et al., 2020). Therefore, we consider theoretical analysis on robust margin loss (defined later in Eq. (4)) against any norm-based attacks. Real-world attacks are not always norm-bounded (Kurakin et al., 2018). Therefore, we also consider non-&, attacks (Lin al., 2020; Xiao et al., 2022c) in See. 7.
Adversarially Robust Generalization. Even enormous algorithms were proposed to improve the robustness of DNNs (Madry et al., 2018; Tramèr et al., 2018; Gowal al., 2020; Rebuffi et al., 2021), the performance was far from satisfactory. One major issue is the poor robust generalization, robust overfitting (Rice et al., 2020). A series of studies (Xing et al., 2021; Xiao al., 2022b,d; Ozdaglar al., 2022) have delved into the concept of uniform stability within the context of adversarial training.
3

---

However, these analyses focused on general Lipschitz functions, without specific consideration for neural networks.
Rademacher Complexity. Rademacher complexity can provide similar spectral norm general- ization bound as PAC-Bayesian bound (Theorem 2). Rademacher complexity was extended to adversarial settings for linear classifier (Khim & Loh, 2018; Yin al., 2019) and two-layers neural networks ( (Awasthi et al., 2020). As for DNNs, they found that it was mathematically difficult and provided some discussions on surrogate losses rather than the adversarial loss.
Covering Number. Rademacher complexity can be bounded terms of the covering number of the function class, as discussed in (Bartlett et al., 2017). Nevertheless, calculating the covering number for an adversarial function class is also shown to be challenging problem. Gao & Wang (2021) considered adversarial Ioss against FGSM attacks, employing similar assumptions to those of (Farnia et al., 2018), resulting in a bound similar to Theorem 3. Additionally, Xiao al. (2022a) and Mustafa et al. (2022) introduced two different methods, respectively, to compute the covering number for adversarial function classes. However, the bounds obtained through these methods remain notably larger when compared to those in standard settings. The related research on Rademacher complexity and covering number help proves the difficulty of the problem we are addressing.
PAC-Bayes Analysis. We mainly compare our results to the previous PAC-Bayesian spectrally- normalized bounds (Neyshabur et al., 2017b; Farnia et al., 2018), which we have already discussed in the introduction. We will provide more details later. The workshop version of this paper is presented in (Xiao al., 2023). Other PAC-Bayes frameworks for tackling adversarial robustness also exist. Viallard et al. (2021) explored a distinct adversarial attack targeting the loss of the Q-weighted majority vote over the posterior distribution Q. Mustafa et al. (2023) introduced non-vacuous PAC-Bayes bound designed for stochastic neural networks.
3 Preliminaries
3.1 Notations
We mainly follow the notations of (Neyshabur al., 2017b). Consider the classification task that maps the input x E X to the label y E Rt. The output of the model is a score for each of the classes. The class with the maximum score will be the prediction of the label of x. A sample dataset S= [(x1, V/),,.. ... (Xm, Bmm) with m training samples is given. The l2 norm of each of the samples J; is bounded by B, i.e., ||a|||2 S B, i 1.... m. Let [ and [[]], denote the Frobenius norm and the spectral norm of the weights W, respectively.
Fully-Connected Neural Networks. Let (x) X' + R be the function computed by d-layer feed-forward network for the classification task with parameters w = vec ([W))=))) fw (x) = Wa o( x(,).)((())) here Φ is the ReLU activation function. Let fü (x) denote the output of layer before activation and h be an upper bound on the number output units each layer. We can then define fully-connected feed-forward networks recursively: / (x) = Wix and f (x) = W. (x)). Section 7, we extend the results to ResNet (He et al., 2016), since the otate-of-the-arr art robust performance is built WideResNet (Rebuffi et al., 2021; Croce et al., 2021).
3.2 Standard Margin Loss and Robust Margin Loss
Standard Margin Loss. For any distribution DD and margin y > O, the expected margin loss is defined as follows:
(fw)) = ((xx)) [x)()( S v + max fw (x)li]
j4y
Let (fw) be the empirical estimate of the above expected margin loss. Since setting 7 = corresponds to the classification loss, we will use Lo(fw) and Lo(fw) to refer to the expected loss and the training loss. The loss Ly defined this way bounded between and 1.
Robust Margin Loss. Adversarial examples are usually crafted by an attack algorithm. Let gade (x) be an algorithm output and 8t (x) be the maximizer of the following maximization problem
max L { (x + 8).8), [8

---

where l is the loss function of the predicted label and true label. Without explicit specification, || refers to the lg norm. The robust margin loss is defined follows:
(f =P (x).))
Ex' [c) (x') S max fw fw (x)()
3
(4)
=I (x.,))
S max fw fw (x o (x))
3fy
Let Rr, (fw) be the empirical estimate of the above expected robust margin loss. The robust margin loss requires the whole norm ball around the original example x to be labelled correctly, which is the goal of bosm-based adversarial robustness. By replacing 62 (x) by 80d (x) in the above definition, we denote Re (fw) as the margin loss against attacks adv. The work of (Farnia et al., 2018) consider three attacks: fast gradient sign method (FGSM or FGM), projected gradient method (PGM), and wasserstein risk minimization (WRM), i.e., adv FGSM, PGM, and WRM. They provided three different bounds for these adversarial attacks respectively. However, methods for generating these adversarial examples becoming significantly more sophisticated and powerful. For example, Autoattack (Croce Hein, 2020) in default settings is a collection four attacks to find adversarial examples. Therefore, bound of robust margin loss against single attack provides a limited robustness guarantee to a machine learning model. In fact, Autoattack collects different attacks attempt and to provide close lower estimation of (f(f)). Therefore, this paper focuses on the robust margin loss.
Robust Generalization Bound
In this section, we will first provide our main result of robust generalization.
Theorem 1 (Main Result: Robust Generalization Bound). For any B, d, h 0, let fw :' R be a d-layer feedforward network with ReLU activations. Then, for any 8,7 > 0, with probability 8 over a training size m. for any w, we have:
(
(B +) (nth) In dm 5
SO 50 Rolsw) - (l.(Sw)
2m
where (ffw) IIo
[
1==1
[W
the spectral complexity of fw- [Wall
Remark. Theorem is presented under lg attacks to simplify the notation. For other Ep attacks, suppose all the samples v; have l, norm bounded by and [|ő|| S 6, the robust generalization bound is to replace (B + E) by ma J E) in Theorem 1, where is the dimension of the samples Zt.
Theorem provides the first PAC- MAC-Bayesian bound in adversarial robustness settings without introduc- ing new assumptions. Fixing other factors, the generalization gap goes 0 as m D0.
Theorem 2 (Standard Generalization Bound (Neyshabur al., 2017b)). For any B,d, h 0, let [w X' - & be a d-layer feedforward network with ReLU activations. Then, for any ō, 7 >> 0, with probubility 8 over a training size m. for any w, have:
(v
B2d In ( In dm 5
Lo(fw) - [n((f))
3m
where (ffw) II
Comparison with Existing Standard Generalization Bounds. Comparing the robust generaliza- tion bound in Theorem with the standard generalization bound in Theorem 2, the only difference a factor of the attack intensity which is unavoidable in adversarial settings. In other words. B and B + are the magnitudes of the clean and adversarial examples, respectively. Therefore, our main result is as tight as the standard generalization bound in Theorem 2.
5

---

Theorem 3 (Robust Generalization Bound (Farnia et al., 2018)). For any B, d. h > O, let fw : X - E be a d-layer feedforward network with ReLU activations. Consider an FGM attack with noise power according to Euclidean norm || 2- Assume that [VV (x), u)ll 2 K, Vx e-close to X.
Then, for any 6, y > O, with probability 2 1 over a training set of size m, for any w, we have:
[B + e) In (
/. (fw)
+ In dm
Rodion (fw) Regti (Sw) SO
-2m
d
d W
d 2 II (W
om (fw) = II W. [W (1+ (lgm)
and C
Will2
=1
For robust generalization bounds of PGM or WRM adversarial attacks, the bounds have similar forms as in Theorem 3, with different constants Cram and Cwrm.
Remark:
Comparison with Existing Robust Generalization Bounds. Comparing Theorem 1 and Theorem 3, the difference of the upper bounds is the difference of 4 and 4/9m, where 5 contains an additional term C Therefore, our bound is tighter. Moreover, the robust generalization gap is much larger than the FGSM generalization gap based on the observation in practice. We provide a tighter upper bound for a larger generalization gap.
Additionally, the term Cf could be very large. Notice that Theorem 3 requires {(fw (x), y) to be sharp w.r.t. x for all x E X. is hard to verify and i could be small. Therefore, if we remove the additional assumption [Vx(([((x), v 2 R. we have Clam - +0 as K - 0 and the upper bound in Theorem 3 goes infinity.
It is also worth noting that our bound is tighter than other norm-based robust generalization bounds derived in Rademacher complexity and covering number approaches, since these bounds are larger than their standard counterpart, the bound given by (Bartlett al., 2017).
5 Analysis of Adversarially Robust Generalization
As mentioned in the introduction, the robust generalization gap is much larger than the standard generalization gap in practical scenarios. What factors contribute to such significant difference? Previous norm-based bounds might lead to the following hypothesis: The significant disparity could potentially be attributed to the additional terms assumptions between the standard bound and the robust bound. Our result provides a different perspective: They are solely due to mathematical considerations. The following three factors are (implicitly) different in Theorem I and Theorem 2 and possibly contribute to the significant disparity.
Clean Sample and Adversarial Example (B and B e). The only difference between the bounds in Theorem 1 and Theorem 2 lies the factor e. In this context, B represents the magnitude of clean samples, while B + signifies the magnitude of adversarial examples. This factor holds less significance in improving robust generalization, as is unlikely be controlled during the training of DNNs.
Standard Margin and Robust Margin (7). The margin y remains consistent in both of these two bounds, but it is implicitly different in the definitions of standard margin loss and robust margin loss. The robust margin is smaller due to the smaller distance between two adversarial examples. As it is discussed in (Neyshabur et al., 2017a), y is usually considered to normalize the spectral complexity discussed below.
-aandard-Trained and Adversarially-Trainee Parameters (#(fw)). The spectral complexity (ffw) is implicitly different because the weights w of the standard- trained and adversarially aaversarially-trainedd trained models are distinct. The spectral complexity & induced by adversarial training significantly larger. We conducted experiments training MNIST, CIFAR-10 10, and CIFAR-100 datasets on VGG networks, see Appendix C. See also the work of (Xiao et al., 2022a) for more discussion about the experiments of weights norm of adversarially complexity (f(w) likely contributes to the huge difference between standard generalization and robust generalization.
models. The margin-normalized spectral

---

Main Challenge of Robust Generalization Bound and Proof Sketch
6.1 PAC-Bayesian Framework
The PAC-Bayesian framework (McAllester, 1999) provides generalization guarantees for randomized predictors drawn from a learned distribution Q (as opposed to a single predictor) that depends on the training data set. In particular, let fw be predictor parameterized by w. We consider the distribution Q over predictors the form fw+u. where
a random variable and w considered to be fixed. Given a prior distribution P over the set of predictors that is independent of the training data, the PAC- Bac-Bayes theorem states that with probability at least 8, the expected loss of fw+u can be bounded as follows
2 (KL (w ul P) + In 2m
Bu [oo[fwtu] S Bu [fo[[o] + +2/
(5)
m
To get a bound on the margin loss Lo(sw) for a single predictor fw. we need to relate the expected loss, E. (f over distribution Q, with the loss Lo(fw) for single model. The following lemma provides this relation.
Lemma 4 (Neyshabur et al. (2017b)). Let fw(x) x R be any predictor (not necessarily neural network) with parameters w. and P be any distribution on the parameters that is independent of the training data. Then, for any Y, 5 >> O, with probability 2 1 5 over the training set of size m,
for any w, and any random perturbation u s.I. P. maaxxx (f - J (x)x <
we
have:
KL + u|| P) + In 6m
Lo(fw) S (y(fw) + VV
m
As it is discussed in (Neyshabur et al., 2017a), the KL-divergence is evaluated for fixed w and is random. Lemma 4 is not specific to neural networks and generally holds for any functions. Providing Lemma it is left provide bound of []f bound,3 3 This framework can be directly extended to adversarially robust settings by replacing (fw+u(()) - fw (x)ll2 by [lf++u(x+ + 8ado (x)) fw(x + 5ado 8ado(x)))le (x))ll2 (Farnia et al., 2018). For more details, see Appendix B.
fw (x)]l2 to obtain the final generalization
6.2 Main Challenge
Based on Lemma 4, to provide an upper bound of robust margin loss is to solve the following problem:
Problem 1. How to provide a bound of
[ x + owdr
Sw ( 5ader (x))]l2?
We refer to the gap in Eq. (6) as robust weight perturbation. To the best of our knowledge, it remains unclear how to establish a bound for robust weight perturbation. In standard settings, when we perturb the weights from w to + u, the input x remains the same. The change in function values is solely attributable the change weights. However, the situation becomes much more complex in adversarial settings. If we perturb the weights from w to + the adversarial attacks also vary from 8ndo (x) to gæde u (x). The combined changes in input x and weights w may result in a substantial change in function values. The challenge of Problem I can be observed in previous studies.
Farnia al. (2018) introduced additional assumptions to bound Eq. (6). For instance, for FGSM and PGM attacks, they assumed [x (x). v)] 2 к for all x c-close to X. This parameter appears in the bound of Eq. (6) as well as the final generalization bound. To the best of our knowledge, there has been no attempt at 8 (x). It is not because such research is unimportant (as mentioned in Sec. 3), but rather due to the challenge presented by Problem In this case, remains unclear what assumptions can be made to bound Eq. (6). The related work on Rademacher complexity analysis demonstrates the difficulty, as researchers have found it challenging to bound robust margin loss and have instead resorted to bounding robust loss against soled attack with additional assumptions. Further discussion on this topic can be found in Sec. 2.
It is because (x) fw(x)]l xo (x))+u(x) fw (x)]222
7

---

Our solution to this problem consists of two steps. Step 1: We recognize that a general and reasonable bound for Eq. (6) without additional assumptions may not exist. To address this, we establish bound for similar expression, namely the weight perturbation of margin operator, without requiring any additional assumptions. To develop this bound, we introduce generalization framework called "Perturbation Bounds of Robustified Function", which can be further extended to analyze other neural network structures, Step 2: We modify Lemma 4 to incorporate the weight perturbation bound that we have introduced. By combining these two steps, we are able to address the challenges and provide a robust generalization bound.
6.3 Perturbation Bounds of Robustified Function
In this section, we consider functions 9w 9w(x) parameterized by the weights of neural network. We
mainly consider scalar value functions Iw (x) X - R. For example, 9w (x) can be the jth output of neural network fw (x) the margin operator fw (x) maxjøy fw (x) [il, the robust margin operator.
Definition 1 (Local Perturbation Bounds), Given x X, we say gw (x) has a (LI, La) -local perturbation bound w.r.t. w, if
d
(gw(x) Iw (x)l S Σ
L:Il: - Will
where L, can be related to w, w' and x.
Eq. (7) controls the change of the output of functions Iw (x) given slight perturbation the weights of DNNs. The following Lemma is the key Lemma to estimate perturbation bounds of the robustified function, which is defined as inf x lis Iw (x'). The reason why we require gw (x) be scalar functions is that we can define their corresponding robustified functions.
Lemma (Key Lemma). if (w(x) has a [x], ... AA(xx))locaal perturbation bound, i.c.,
d
(xw(x) gw (x)l S
Σ
A | Will.
1=1
the robustified function inf [ Iw 9w(x') (x') has (A1(x) + +E). Ad((x) + e)) local perturbation bound.
Proof: Let x(w) = arg inf ||x [nffix-''lsse Iw (x'), x(w') arg inf ix ix-xx Iw (x'), Then,
inf Ix-xxss.
gw (x')
inf 9w (x)) 1axx(l9(((v)))) Sw (x(W)) l9w (ow gw (x(w'))
1|x xx
is because gw (ww(x()) gw (x( (w')) S gw (x(')))) Iw (x(w')) and gw (x(w)) Iw (x(w)) 5
Bwr (x(w)) - Iw (x(w)). Therefore.
inf (x(x') inf [x=
1x-xx Iw (x') Σ A. will S Σ A:(xx| +elx|+))][[2 -WIl--
Lemma 5 shows that the local perturbation bound of the robustified function inf inf[j-=x'Iss Iw (x') can be estimated by the local perturbation bound of the function gw (x), which is the key to provide robust generalization bounds.
6.4 Perturbation Bounds of Margin Operator
It should be noted that Lemma 5 is unable to provide a bound for Problem 1. In order to utilize Lemma 5, we shift our focus the margin operator, which is scalar function.
Margin Operator. Following the notation of (Bartlett et al., 2017), we define the margin operator of the true label y given and of pair of two classes (i.j) as
M (x) y) = fw (x) - max fw (x) M (fw (x), (x)] - fw (x) jøy
8

---

Robust Margin Operator. Similarly, we define the robust margin operator of the true label y and of pair of two classes (i,j) given x as
RM (x)())))) = inf (fw(x')ll) ||x- |xx-x(l|se
max fw fw(x') GG),
and
jFy
RM((((X) = inf (fw(x') Sw (xw(x')) (x)) Ix-x'lse
respectively. Based on Lemma 5, it is left to provide the form of A; for the margin operator.
Lemma 6. Let fw be d-layer neural networks with Relu activation. The following local perturbation bounds hold.
1. Given x and j. the margin operator M (fw ix). has a (A1 tion bound w.r. w, where A, = 2e IT | And
Au(x)) Au(xx))locaal perturba-
1
-
2eB
[1ill2
(8)
W
2. Given x and i, the robust margin operator RM (MW[w( (x),
has a locally (A1((x)
+
.., Aa([x] [[x] e))-local perturbation bound w.rlt w. And
d
d Will
U Will
B + + RM - (f B
(9)
The proof of Lemma 6. is adopted from Lemma 2 in (Neyshabur et al., 2017b), and the proof of
Lemma 6.2 is combination of Lemma and Lemma 6.1. It is important note that Eq. (9) provides a bound for similar but different form of robust weight perturbation compared to Eq. (6), indicating that Problem I has not been fully resolved. However, we are fortunate that the subsequent lemma demonstrates that Eq. (9) is sufficient to yield the final robust generalization bound.
Lemma 7. Let [x) X - B& be any predictor with parameters w, and P be any distribution on the parameters that is independent of the training data. Then, for any 7, > with probability
2 1 - 6 over the training set of size m. for any and any random perturbation u s.t.
Pu [maxx MMM (f)(uux)), M(f (x), (x),
1 2
we have:
(w(w + u P) +
In 6m
Lo(sw) & (.g(fw) + +1
m
Jel RM (f=-((()))), RM (x), < 31 N
1 2' we have:
KL + u + In 6m 8
Ro(fw) S (f(w)) + +4/
m
Remark: Lemma 7 shows that we can replace the robust weight perturbation (Eq. (6)) by the weight perturbation of the robust margin operator. The proof is deferred to the Appendix.
Now that we have established the complete framework of the perturbation bound of robustified function to derive the robust generalization bound, we are ready to prove Theorem 1. By following the proof of (Neyshabur et al., 2017b), we can replicate the standard generalization bound by combining Lemma and 7. Similarly, we can obtain the robust generalization bound by combining Lemma 6.2 and 7.2. The flowchart illustrating this process is presented in Figure 2. Additionally, Lemma 5 serves as a crucial link between the robust margin operator and the margin operator, thus establishing the connection between the robust generalization bound and the standard generalization bound.

---

7 Extension of the Main Result
The provided framework allows us extend the result 1) general non-lp adversarial attacks and 2) other neural network structures.
Extension to Non-lp Adversarial Attacks. Even though most of the adversarial robustness studies focused on norm- com-bounded attacks, real-world attacks are not restricted in the bp-ball. We consider the following general adversarial attack problem:
((f((x').)) x'EC(x)
where C(x) can be any reasonable constraint given the original example Assume that max.es IaXx) [x]] D. In words, the norm of the adversarial examples is bounded by D.
Theorem 8 (Robust Generalization Bound for non-l, attack.). For any D,d, h, let fw X - +F B be a d-layer feedforward network with ReLU activations. Then, for any 8, > O, with probability 2 8 over a training set size m. for any w, have:
(fw) ley (Sw) 5o (1 De (n(d))((Jw)) + In dm
32m
where (ffw) 11 W
Diml
and nl stands for non-lp adversarial attacks. [[il
The proof is based on slight modification of Lemma 5.
Extension to Other Neural Networks Structure. The framework we have established enables us to extend the PAC-Bayesian generalization bound from standard settings to robust settings, provided that the standard generalization bound is also obtained using this framework. Importantly, this extension is independent of the structure of the neural networks.
ResNet. Consider neural network: (x) Wix and (x) = Wid(F+ + f (x).
ResNet in practice could be complicated. We use this structure for illustration.
Theorem 9 (Robust Generalization Bound for ResNet), For any D, d, h, let Sw : X' - R2 be d-layer ResNet with ReLU activations. Then, for any d, Y O, with probability 2 8 over training set of size m, for any w, we have:
(B + +)+2) (nch)) + In dm
RolfRN) (FRN)) 00
3mm
where ((JN)) = IT +1) Dd
IW
[[W:+1++1]=
8 Conclusion
Limitation. The primary limitation lies in the fact that norm- based bounds tend to excessively large in practical scenarios. As illustrated in Table 1, the bounds for VGG networks surpass 10" in the experiments on CIFAR- 10 dataset. The challenge at hand is how to achieve smaller norm-based bounds in practical contexts, not only in adversarial settings but also in standard settings. This remains an open problem.
In this paper, we introduce a PAC-Bayesian proof constructed based on the framework of the perturbation bound the robustified function. This established framework enables us to extend the generalization bound from standard settings to robust settings, as well as to generalize the results to encompass various adversarial attacks and DNN architectures. The simplicity of this framework makes it valuable tool for analyzing robust generalization in machine learning.
robust generalization bound. The
10

---

Acknowledgement
We would like thank all the anonymous reviewers for their comments and suggestions. This paper is supported in part by the National Key Research and Development Project under grant 2022YF41003900; Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project dation of Artificial Intelligence, Department of Science and Techonology of Guangdong Province. The work of Zhi Chi-Quan Luo is supported by NSFC-61731001 and the Guangdong Provincial Key Laboratory of Big Data Computing.
Guangdong Key Lab on the Mathematical Foun-
References
Awasthi, P., Frank, N., and Mohri, M. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pp. 431-441. PMLR, 2020.
Bartlett, P. L. 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 Information Theory, 44(2):525-536, 1998.
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Carlini, N. and Wagner, D. Towards evaluating the robustness of neural networks. In 2017 ieee symposium security and privacy (sp), pp. 39-57. IEEE, 2017.
Croce, F. and Hein, M. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. International conference on machine learning, pp. 2206-2216. PMLR, 2020.
Croce, F., Andriushchenko, M., Sehwag, V., Debenedetti, E., Flammarion, N., Chiang, M., Mittal, P., and Hein, M. Robustbench: standardized adversarial robustness benchmark. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
Farnia, F., Zhang, J., and Tse, D. Generalizable adversarial training via spectral normalization. In International Conference on Learning Representations, 2018.
Gao, Q. and Wang, X. Theoretical investigation of generalization bounds for adversarial learning of deep neural networks. Journal of Statistical Theory and Practice, 15(2):1-28, 2021.
Golowich, N., Rakhlin, A., and Shamir, O. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. stat, 1050:20, 2015.
Gowal, S., Qin, C., Uesato, J., Mann, T., and Kohli, P. Uncovering the limits of adversarial training against norm-bounder adversarial examples. arXiv preprint vrXiv:2010.03593 2020.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Khim, J. and Loh, P.-. Adversarial risk bounds via function transformation. arXiv preprint 1rX.v:1810.09519, 2018
Kurakin, A., Goodfellow, J., and Bengio, S. Adversarial examples in the physical world. In Artificial intelligence safety and security, pp. 99-112. Chapman and Hall/CRC, 2018.
Lin, W.-A., Lau, C. P., Levine, A., Chellappa, R., and Feizi, S. Dual manifold adversarial robustness: Defense against Ip and non-lp adversarial attacks. Advances Neural Information Processing Systems, 33:3487-3498, 2020.
11

---

Madry, A.. Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant adversarial attacks. International Conference on Learning Representations, 2018.
McAllester, D. A. Pac-bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory, pp. 164-170, 1999.
Gloosavi-Dezfooll S.-M., Fawzi, A., and Frossard, P. Deepfool: a simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2574-2582, 2016.
Mustafa, W. Lei, Y., and Kloft, M. On the generalization analysis of adversarial learning. In International Conference on Machine Learning. pp. 11174-6116.. PMLR, 2022.
Mustafa, W., Liznerski, P., Wagner, D., Wang, P., and Kloft, M. Non-vacuous pac- mac-bayes bounds for models under adversarial corruptions. 2023.
Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1486 1401. PMLR, 2015.
Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. Exploring generalization in deep learning, Advances neural information processing systems, 30, 2017a.
Neyshabur, B., Bhojanapalli, S., and Srebro, N. A pac-bayesian approach to spectrally-norrmalzze margin bounds for neural networks. arXiv preprint arXiv: 2017b.
Ozdaglar, A., Pattathil, S., Zhang, J., and Zhang, What is good metric to study generalization of minimax learners? Advances in Neural Information Processing Systems, 15:38190-3888 2022.
Papernot, N., McDaniel, P., Jha, S., Fredrikson, M., Celik, Z. B., and Swami, A. The limitations of deep learning in adversarial settings. In 2016 IEEE European symposium on security and privacy (EuroS&P) P). pp. 372 387. IEEE, 2016.
Rebuffi, S.-A., Gowal, S.. Calian, D. A., Stimberg, F., Wiles, O., and Mann, T. Fixing data augmentation improve adversarial robustness. arXiv preprint wxXiv:2103.01446 2021.
Rice, I.., Wong, E.,, and Kolter, Z. Overfitting in adversarially robust deep learning. In International Conference Machine Learning, pp. 8093-8104 8104. PMLR, 2020.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. In 2nd International Conference Learning Representations, ICLR 2014, 2014.
Tramèr, F., Kurakin, A., Papernot, N., Goodfellow, I., Boneh, D., and McDaniel, P. Ensemble adver- sarial training: Attacks and defenses. International Conference on Learning Representations, 2018.
Tramer, F., Carlini, N., Brendel, W., and Madry, A. On adaptive attacks adversarial example defenses. Advances in neural information processing systems, 33:1633-1645, 2020.
Tropp, J. A. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12:389-434. 2012.
Viallard, P.. VIDOT, G. E., Habrard. A., and Morvant, E. A PAC-bayes analysis of adversarial robustness. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL htt..https://ppereevieee wttper/ewwiieeeeetonttnorma net/forummidd sUBSPoxU3L5.
Xiao, J., Fan, Y.. Sun, R., and Luo, Z.-Q. Adversarial rademacher complexity of deep neural networks. arXiv preprint arXiv:2211.1496 2022a.
Xiao, J., Fan, Y., Sun, R., Wang, J., and Luo, Z.-Q. Stability analysis and generalization bounds of adversarial training. Advances Neural Information Processing Systems, 35:15446-15455 2022b.
12

---

Xiao, J., Yang, L., Fan, Y., Wang, J., and Luo, Z.QQ. Understanding adversarial robustness against on-manifold adversarial examples. arXiv preprint arXiv:2210.004430, 2022c.
Xiao, J., Zhang, J., Luo, Z.-Q., and Ozdaglar, E. Smoothed-sgdmax: A innipitt-inspiredd algorithm to improve adversarial generalization. In NeurIPS ML Safety Workshop. 2022d.
Xiao, J., Sun, R., and Luo, Z.-Q. Pac-bayesian adversarially robust generalization bounds for deep neural networks. In The Second Workshop on New Frontiers in Adversarial Machine Learning, 2023.
Xing, Y., Song, Q., and Cheng, G. On the algorithmic stability of adversarial training, In Thirty-Fifth Conference on Neural Information Processing Systems, 2021. URL https::/ net/ forum/id=xx201FFIj..
Yin, D., Kannan, R., and Bartlett, Rademacher complexity for adversarially robust generalization. In International Conference on Machine Learning, pp. 7085-7094, PMLR, 2019.
13

---

A Proof of Theorems
The proof of the key lemma (Lemma 5), which establishes a connection between the margin operator and the robust margin operator, presented in the main content.
We still need to demonstrate that the properties in PAC-Bayee Bayes analysis hold for both the margin operator and the robust margin operator. The following proofs are adapted from the work of (Neyshabur et al., 2017b), with the steps being kept independent of the (robust) margin operator. We will begin by finishing the proofs of Lemma and Lemma 7. Afterward, we will proceed to complete the proof of Theorem I, which is our primary result.
A.1 Proof of Lemma
Proof of Lemma 6.1:
For any E [k].
[fw+u(x)](]] (x) Ilf - fw(x))12
For any i.j E [k],
LM(ffuu(x)),.... i.j) ((fw(x),,, - 2 (x) - (x) S 21llf
(x)
Therefore, it is left bound [ (x) - fw (x)]l- Is provided in (Neyshabur al., 201 7b), provide the proof here for reference. Let D. (x)+ für (x)) We will prove using induction that for any 2 0:
A 1 2)
14112
xx/2
The above inequality together with (1 + 2)² I proves the lemma statement. The induction base
clearly holds since Au |x x12 = 0. For any 2 1, we have the following:
A (Wi+1* + U141) 0i @f (x) W (f
(Wi+1 U1+1) ( (x)) (x)()))) + (
< ([Wi+1ll2 + 11:++1112) (x - (f (x)) + 1|uttlll ( (x))
S (1]W41ll + |1 [ [x)x) + 11 (x)
A. (1 (|+++112)) [|U (x)
where the last inequality is by the Lipschitz property of the activation function and using ((0) The Eg norm of outputs of layer is bounded by |x|, IT ||W and by the lemma assumption have |10+1112 & [|We+lll- Therefore, using the induction step, we get the following bound:
A < A. 1 4) [Wetalla + ||Uetalla |x|2
II
Wall
5=1
+
8
1) [[5ll22
|x]2
Σ
[W5112
|15
|[
|1041112
|xl2 II [Will
S41
j=1
H+1
/1+1
|
[W5ll
[x]
[5llpa
Then we complete the proof of Lemma 6.1. By combining Lemma 6.1 and Lemma 5, we directly obtain Lemma 6.2.
14

---

A.2 Proof of Lemma
The proof of Lemma 7.1 and 7.2 is similar. We provide the proof Lemma 7.2 below. The proof of Lemma 7.1 follows the proof of Lemma 7.2 by replacing the robust margin operator by the margin operator.
Let w' = w + u. Let Sw be the set perturbations with the following property:
Sw C <(w' w'
7 (M((W(X)) 2
max XJE
[RM((w
Let q be the probability density function over the parameters w'. We construct new distribution Q over predictors fw where w restricted to Sw with the probability density function:
[q(W) 7( (w) = 7 0
W E Sw otherwise.
Here Z is a normalizing constant and by the lemma assumption Z IP [w' E Swl 2 1.- By the definition of Q, we have:
max (x). RM (x), 7 X
Since the above bound holds for any x in the domain X, get the following a.s.:
Rolfw) < Ry (fw) Ry (f()x) S (,
Now using the above inequalities together with the equation (5), with probability 1 8 over training set we have:
Rf( S Ewr
Rg (fw)
2(KL PP) + 1
< Eww
[Rg (fw)
+ +
2mz 2(KL (W|[P) In
< (R((w) -2
KL (w') (P) In 6m 8
< (R + +4V
The last inequality follows from the following calculation.
Let Sh denote the complement set of Sw and q denote the density function q restricted St and normalized. Then,
KL(gllp) (KL()l)) + (1 Z)KL( (p) -H()),
where H(2) - 7 - (1- 1) 2) < is the binary entropy function. Since KI. is always positive, we get,
1 KL(@llp) 7 [KL())p) H - 2)K < ((( 1).
A.3
Proof of Theorem
Given the local perturbation bound the robust margin operator and Lemma 5, the proof of Theorem 1 follows the procedure of the proof of Theorem 2.
Let (ITL_ [W.
and consider a network with the normalized weights W, || W.. Due to the homogeneity of the ReLU, have that for feedforward networks with ReLU activations
1/d
8
15

---

fw = fw. and so the (empirical and expected) loss (including margin loss) is the same for w and w. We can also verify that (IT- [[Wrlla) (I W and
|wa]] W and so the excess [w.
[Wale Will
error in the Theorem statement is also invariant to this transformation. It is therefore sufficient to prove the Theorem only for the normalized weights w, and hence assume w.l.o.g. that the spectral norm is equal across layers, i.e. for any layer i, [| =
Choose the distribution of the prior P to be (N 12), and consider the random perturbation a~ (0, I² with the same which we will set later according to 3. More precisely, since the prior cannot depend on the learned predictor w its norm, we will set based on an approximation 3. For each value of 3 on a pre-determined grid, we will compute the PAC-Bayes bound, establishing the generalization guarantee for all w for which | 31 S f. and ensuring that each relevant value of 3 is covered by some 3 on the grid. We will then take a union bound over all 3 on the grid. For now,
we will consider a fixed 3 and the w for which | 3 < 3, and hence ! g I 3d S egd-1
Since u ~ (0, I) we get the following bound for the spectral norm of U; (Tropp, 2012):
PU;~N(0,021 [|| > t] S 2he /2/h0²
Taking a union bond over the layers, we get that, with probability 2 1.2 the spectral norm of the perturbation Ug in each layer bounded by a / In(4dh). Plugging this spectral norm bound into the Lipschitz of robust margin operator we have that with probability at least 2'
max k.j( XEX
(Xw i,) (M)(f(x))
(10)
||U1l2
<2e(B B e)B
Σ
B
=e(B + c)
Σ
|1tll2 S () /
In(4dh) < +)
7 2
(11)
where we choose o = 42d B+-)) (4hhdd to get the last inequality, the first inequality is Lemma
6.2. The second inequality is the tail bound above. Hence, the perturbation u with the above value of a satisfies the assumptions of the Lemma 4.
We now calculate the KL-term in Lemma 4 with the chosen distributions for and u, for the above value of a.
KL(w + u P)
w 2
df + c)28ad-21
1 2/ In(4/d)
Will
2a
27
32d d (B+ 2
|Wail
50
1
I
11
W: 11
00
(B + 6) 2 (ndh)
|W
Hence, for any B. with probability 2 1 5 and for all w such that, |,3 | < 3 we have:
(B - e) Indh) IW
Dd_
[1
+
Will
Ro(fw) < (fw))) +
(12)
For other lp attacks, the results are directly obtained by Lemma 4 of (Xiao et al., 2022a).
A.4 Proof of Theorem 8
It is based on slight modification of the key lemma. if (x(() has (A1 x|,, Adlx()-local perturbation bound, i.e.,
19w (x) gw (x)l 5 A A WIll.
16

---

. the robustified function inf ((((e) Iw (x') has a (A1 ... -)-ocl perturbation bound.
Proof: Let
x x(w) = arg inf Iw Ow(x') (x'; x'EC(x))
x(w') = arg inf Iw (x'),
x' x'EO(x)
Then,
inf x Iw (w((x')
inf
Sw (x')
11x 1x-x(1ss
max 1ow (w)) Ow (x(w))), 1/1 low (ow (x(w')) 1) - Iw (x(wW))) 1)1.
It because Iw (x(w)) ) - 9w (x( (w)) S Iw (x(w") )) gw (x(w')) and gwr (x(ww)) Iw (x(w)) 5
gw (x(w)) - 9w (x(()) Therefore,
inf
Sw(x')
inf |x-xx1ls Iw (x'))
x x I.
A - WI'l
A.DII, -WIl.
Therefore, combining the local perturbation bound and Lemma 7.2, we complete the proof.
A.5 Proof of Theorem
As shown in the proof of Lemma 6, it left bound ll [w(x)] ff+u(x) - fü (x))2 2' We will prove using induction that for any 0:
Let A,
A s 1+ 2) II (11,ll12 +)) x12
l1 +1
The above inequality together with (1 + a)²² S e proves the lemma statement. The induction base
clearly holds since Ag |x x|2 = 0. For any 2 1, we have the following:
A
(W,-1 + 11+1) 6. ( (x)) - 14 + (f f (x))[2
(W,-1 1++1) (0: (n (x)) (f (x)) + Uf (x)) + (x) f (x))l2 d. (x) + |1 (f( + +A,
S (|]Ws+1l2++1// + 11 p (5 ( (f+
S (I]Wi+1ll2 + ||0 21 / (x) - (x), 2 + |l0 ll (x)12 + A.
-. (IIW |1 1) + |10 22 (x))2
where the last inequality is by the Lipschitz property of the activation function and using (00) = 0. The lg norm of outputs of layer bounded by |x|2 -T)z,(( Will, 2l2 + 1) and by the lemma assumption we have |lu++1 l1a S à |[ 12- Therefore, using the induction step, we get the following bound:
A+t1 S A:
1 2 ([W5+1ll2 + 1) + ||05+1 112 1x|2
II W +
1=1
1 (1+2) ++1 ++1
[[ +11 +11)
|
|1++1
i+1 [X
1x12
[[ +1)
(115 +1)
(1[W+1ll) +1)
1=1
$ (1+2)
141
(14
|1U1|2
[[ +11
|x|
(I[W, +1)
Therefore, the margin operator of ResNet is locally (Ai ... Ad/x()-Lipschitz w.r.t w, where
A; 2c (lll + 1)/( 1).
[=1
17

---

For any 6, > O, with probability 2 1 - over a training set of size m. for any w, we have:
Lo(RR) - (JRN)
B2d (n(h))0())) + In dm 8
0o
By a combination Lemma and Lemma 7, for any 6,7 > O, with probability 2 5 over a training set of size m, for any w, have:
Ro(FRN) (fRN)))
B (nth) + In dm
7
where (ffRN) II (1WWlll + +)) D
|| IP
B PAC-Bayesian Framework for Robust Generalization
PAC-Bayes analysis (McAllester, 1999) is framework to provide generalization guarantees for randomized predictors drawn from learned distribution Q (as opposed to single predictor) that depends the training data set. The expected generalization gap over the posterior distribution Q can be bounded terms the Kullback-Leibhe divergence between the prior distribution P and the posterior distribution Q, (L(()))))
direct corollary of Eq. (5) that, the expected robust error of fw+u can be bounded as follows Bu [Ro (fw+u)]
2 (KL (w + ul In
(13)
SRuu (Fu](R""((wtu)) +2
By slight modification Lemma 4, the following lemma given in the work of (Farnia al., 2018) shows how to obtain an robust generalization bound.
Lemma 10 (Farnia et al. (2018)). Let fx) X R be any predictor (not necessarily a neural network) with parameters w, and P be any distribution the parameters that is independent of the training data. Then, for any > O, with probability 2 1 8 over the training set of size m, for any w, and any random perturbation
P. [maxxxx [ + godv (x)) J + gado (x))
2. we have:
KL (w + ullP) In m -
R (fw) < Reddo(f)) + +
Table 1: Comparison of the empirical results of the standard generalization bound and robust generalization in the experiment of training MNIST, CIFAR-IP 10 and CIFAR-IOS 100 on VGG networks.
MNIST
CIFAR-10
CIFAR- 100
Standard Generalization Gap
1.13%
9.21%
23.61 %
Bound in Theorem (Neyshabur et al., 2017b)
1.33 104
1.34 10
3.41 10
Robust Generalization Gap
9.67%
51.41%
78.82%
Bound in Theorem (Farnia al., 2018)
NA
NA
NA
Bound in Theorem (Ours)
3.23 10a
5.97 1010
1.66 1013
C Empirical Study of the Generalization Bounds
The spectral complexity (f(w) induced by adversarial training is significantly larger. We conducted experiments training MNIST, CIFAR-I0, and CIFAR- 100 datasets using VGG-19 networks, following
18

---

the training parameters described in (Neyshabur et al., 2017a).* The results are presented in Table evident that adversarial training can induce larger spectral complexity, resulting larger generalization bound. We refer the readers to our previous work (Xiao et al., 2022a) for more experiments results about norm-based complexity of adversarially-trained models. These experiments align with the findings presented by (Bartlett et al., 2017), indicating: 1) spectral complexity scales with the difficulty of the learning task, and 2) the generalization bound is sensitive to this complexity.
"The settings of standard training follows the experiments in https://gittub.ccmm/bbeee com/bneyshabbur/ feneralization boundd.dd..
'The settings of adversarial training follows the experiments in htttp:///gttatb.cc////aaooggggg Adversarial ailr-alllee Rademacher- RaaeeaachelRRdddmccchhrrrr Redemaccher-CCompeeitt
19


Reviews:
[{"review_id": "OeFuGIISzC", "reviewer": "Reviewer_nNum", "summary": "This paper provides a tighter bounds for robust generalization compared to previous results and as tight as standard generalization.", "questions": "Please see the weaknesses part.", "limitations": "There is no discussion on limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies an important topic on adversarial robustness and provide a tighter bound with detailed theoretical analysis.\n2. The paper is well-written and the conclusions are sound as far as I understand (I didn't check the proof in Appendix).", "weaknesses": "* As the paper is an improvement on Farnia et al. (2018), thus the technical novelty is less significant. \n* The authors should explain why a tighter upper bound is insightful for the robustness community. In my understanding, the robust generalization bound is usually used to explain which factor affects the robust generalization, or why robust generalization is worse than standard generalization. The authors should discuss more on the implications from the new result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thanks Reviewer nNum for the comments and questions.\n___\n**Q1:** As the paper is an improvement on Farnia et al. (2018), thus the technical novelty is less significant.\n\n**A:** Thanks for the question. the technical novelty of our research goes beyond mere improvement. The **technical novelty** is the **most important** part in our work.\n\nLet us clarify below. \n\nFirstly, we provided a detailed comparison with Farnia et al. (2018) only because we both employ the Pac-bayes approach. This comparison aims to shed light on the mathematical difficulties involved in deriving robust bounds. However, it should not be mistaken as implying that our results are merely incremental improvements on Farnia et al. (2018). The discussion of Farnia et al. (2018) aims to convey two messages:\n\n1) Existing technique cannot provide a robust bound, unless new assumption is introduced.\n\n2) New mathematical tools is needed to prove a robust generalization bound.\n\nSecondly,  as we discussed in line 117-130, related work in this field (no less than 7 papers, including Farnia et al.,'s Pac-Bayes approach) tried to extend the norm-based bounds to robust settings. However, the main difficulty is mathematics. The inclusion of supplementary assumptions or additional term presented in these work is less than ideal. These adjustments were made as a compromise due to mathematical issue. However, an ideal bound should be a clean extension of the generalization bound in standard settings.\n\nTherefore, the technique to provide such an extension is important to the community. The significance of our paper lies in providing the math technique to resolve this problem.\n\nFinally, since this is a common question, we provide our answer regarding the **significance of our result** in more detailed in “common question 1”. We understand our comparison to Farnia et al. (2018) mislead the reviewers to consider our work is incremental. We will make revision to address this concern. \n\nWe believe our detailed answer in \"common question 1\" could address your concern.\n\n---\n**Q2:** The authors should explain why a tighter upper bound is insightful for the robustness community.\n\n**A:** Thanks for the question. Our bound offers **significant new insights** into adversarial robustness. It is discussed in Section 5. We understand the main concern or confusion come from the fact that we did not emphasize it is new. We will make necessary revision to distinguish old and new information.\n\nAs this is a common question from reviewers, we discuss the new insight of our result above in “common question 2”.\n\n___\nWe hope our responses have addressed your questions adequately. If you have any further inquiries, please feel free to ask."}, {"review_id": "s1Ed5PSk3f", "reviewer": "Reviewer_AB19", "summary": "In this work, authors use PAC-Bayesian bound to characterize the generalization gap of adversarial robustness. Their work is mostly based on the bound derived from (Neyshabur et al., 2017b) so the resulting bound is valid for a deterministic model.  \n", "questions": "I do not have further questions. I think the theoretical contribution is incremental so it may further increase my score if more empirical evaluations are conducted. ", "limitations": "It might be nice to include such a paragraph. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The major contribution from this work is the new PAC-Bayesian bound for adversarial robustness. The bound works for both Lp and non-Lp cases on both feed-forward networks and ResNets. Authors also compare their bounds with existing ones that only target specific attacks, and show their bounds are more generic. I appreciate the paper’s contribution of the bound (but I do have a question regarding the tightness of the bound which I will elaborate in the next part). The paper has pushed the use of PAC-Bayesian theories to scenarios beyond standard generalization. \n", "weaknesses": "The first weakness of the paper is probably that this newly derived bound largely relies on the work from Neyshabur et al., which has been phrased as an advantage of Theorem 1 being tight at least as Neyshabur et al.’s. However, this might be misleading as I believe the correct description would be when $\\epsilon=0$ Theorem 1 reduces to Theorem 2 so they are as tight as each other. I am not sure I understand what does it mean for Theorem 1 and 2 to be equally tight when $\\epsilon > 0$? Do you mean that what is in the big O notation is around the same magnitude? However, I do not see the value of $p$ (in $\\ell_p$) plays any role in the new bound and the paper talks about the general $\\ell_p$ robustness, thus I assume the bound works in any $\\ell_p$ space. I hereby have the following question, if the bound is p–norm-agnostic, how come it is equally tight for all $p$? Does this bound simply characterize the robustness of the model in the largest ($\\ell_\\infty$) perturbation ball for a given $\\epsilon$? If that is the case, perhaps the derived bound is pretty loose for $\\ell_2$ perturbations. Can you elaborate more here (and in the paper) about the tightness of the bound for different $p$. \n\nAnother weakness is the empirical study to demonstrate the tightness of the bound in Table 1. This table is poorly captioned because I do not know how these models are trained, what architectures are used, what $\\epsilon$ and attack techniques are used to report the numbers. Also, what does $\\infty$ means for Theorem 3? Does this mean the assumption about gradient norm in Theorem 3 does not hold? Do you have experiments about the gradient norms? Moreover, I think it might be useful to use more models and more statistically significant numbers to show the proposed bound is tighter, like the measurement done in this paper [1]. \n[1] Jiang, Y., Neyshabur, B., Mobahi, H., Krishnan, D., & Bengio, S. (2019). Fantastic Generalization Measures and Where to Find Them. ArXiv, abs/1912.02178.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thanks Reviewer AB19 for the comments and questions.\n\n**Comment.**  I think the theoretical contribution is incremental.\n\nA. Thanks for the comment, we will first answer this comment in the beginning. The technical novelty of our research goes beyond mere improvement. The **technical novelty is the most important part** in our work. Let us clarify below.\n\nFirstly, we provided a detailed comparison with Farnia et al. (2018) only because we both employ the Pac-bayes framework. This comparison aims to shed light on the mathematical difficulties involved in deriving robust bounds. However, it should not be mistaken as implying that our results are merely incremental improvements on Farnia et al. (2018). The discussion of Farnia et al. (2018) aims to convey two messages:\n\n1) Existing technique cannot provide a robust bound, unless new assumption is introduced.\n\n2) New mathematical tools is needed to prove a robust generalization bound.\n\nWe understand our comparison to Farnia et al. (2018) mislead the reviewers to consider our work is incremental. We will make revision to address this concern. Please see our detailed answer to common question 1.\n___\n**Q1.** The first weakness of the paper is probably that this newly derived bound largely relies on the work from Neyshabur et al., which has been phrased as an advantage of Theorem 1 being tight at least as Neyshabur et al.’s. \n\nA. Thanks for the question. I consider this aspect to be a strength rather than a weakness. It is essential to note that this particular question is connected to \"common question 1,\" and we believe that the answer provided in our response to \"common question 1\" adequately addresses your concern.\nIn summary, the bound presented by Neyshabur et al. holds significant value as a benchmark bound. Our findings successfully resolve the question that has spanned several years, namely, the tightness of a robust generalization bound.\n___\n**Q2.** However, this might be misleading as I believe the correct description would be when ϵ=0 Theorem 1 reduces to Theorem 2 so they are as tight as each other. I am not sure I understand what does it mean for Theorem 1 and 2 to be equally tight when ϵ>0? \n\nA. Thank you for your question. Understanding the concept of \"equally tight\" can be viewed from two perspectives:\n\nAt the first level, you are correct that as ε approaches 0, Theorem 1 converges to Theorem 2. Consequently, the two bounds become equally tight in this scenario.\n\nAt the second level, when ε is greater than 0, it implies two things:\n\n1) The term \"B\" (clean sample) in the standard bound corresponds to \"B + ε\" (adversarial example) in the robust bound.\n\n2) The other factors in both bounds remain the same.\n\nTo elaborate further, it is proved that \"B + ε\" exists in the lower bound, as demonstrated in Theorem 3 by Xiao et al. in 2022. As a result, when deriving the robust bound, we should replace \"B\" with \"B + ε\". Moreover, since the other factors remain unchanged in both bounds, this is why Theorem 1 and Theorem 2 are deemed equally tight.\n\nXiao, J., Fan, Y., Sun, R., and Luo, Z.-Q. Adversarial rademacher complexity of deep neural networks. arXiv preprint arXiv:2211.14966, 2022.\n___\n**Q3.** Do you mean that what is in the big O notation is around the same magnitude? \n\nA. No, it is not what we mean. Even though the answer is provided above, it is also important to notice that the big O notation omit a number 42 for both bounds.\n___\n**Q4:** However, I do not see the value of p (in ℓp) plays any role in the new bound and the paper talks about the general ℓp robustness, thus I assume the bound works in any ℓp space.\n\nA. Thanks for the question, the main result (Theorem 1) is stated in ℓ2 norm. It is easy to calibrate the results to other ℓp attack by a factor $n^{1/2-1/p}$, where $n$ is the dimension of $x$. We delete this discussion when we condensed the article to 9 pages. Thanks for pointing it out, and we realize that deleting this part will cause unnecessary confusion. We will add the discussion to the updated version.\n___\n**Q5.** Another weakness is the empirical study to demonstrate the tightness of the bound in Table 1. \n\nA. Thanks for the questions. There exists a misunderstanding of Table 1. Table 1 aims to show the effect of spectral complexity on standard and robust generalization. The discussion about Table 1 is provided in Sec. 5.\n\nTable 1 is not to prove the tightness of the bound. Actually, we don’t need any experiments to show the proposed bound is tighter. The proposed bound is strictly tighter since we reduce an additional positive term. \n\nWe hope the fact above can address your main concern. The following detail questions are about fair comparison, which is not related to the main concern if our answer above is helpful. Yet we can still provide our answer.\n\n**Q5.1.** Training details\n\nAs we state in Line 214, the experiment follows [3]. We use VGG-19 networks. As for adversarial training, we use a standard PGD-20 attacks with $\\epsilon=0.5$.\n\n[3] Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. Exploring generalization in deep learning. arXiv preprint arXiv:1706.08947, 2017a.\n\n**Q5.2.** Also, what does ∞ means for Theorem 3? Does this mean the assumption about gradient norm in Theorem 3 does not hold? Do you have experiments about the gradient norms?\n\n∞ means the bound is unbounded without additional assumption, as we state in line 198. Actually, it is highly non-trivial to estimate the lower bound of the gradient norms over the whole domain. We would like to replace ∞ by N/A in Table 1.\n\n**Q5.3.** Moreover, I think it might be useful to use more models and more statistically significant numbers to show the proposed bound is tighter.\n\nWe don’t need any experiments to show the proposed bound is tighter. In mathematics, the proposed bound is strictly tighter.\n___\nWe hope our responses have addressed your questions adequately. If you have any further inquiries, please feel free to ask."}, {"review_id": "xViOjyaSlM", "reviewer": "Reviewer_FsEL", "summary": "This paper improves previous PAC-Bayesian bounds on robust generalization. The previous bound in Farnia et al. (2018) has a term that is not bounded, and this work provides a bound to that term using the Lipschitzness of feed-forward ReLU networks. The basic idea is that coordinate-wise Lipschitzness preserves under L-inf perturbation.", "questions": "See above.\n\n**Post rebuttal note:** I have read the rebuttal and other reviews. I prefer to keep my score.", "limitations": "Limitations are not discussed.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I am quite familiar with this field and spent 3 hours reviewing this paper. Though I do not closely follow the robust generalization line of research, I believe that this work could be helpful to people working in the same direction. The overall framework is very clear and the results are intuitive and easy to understand. Though there are some confusing parts in some sections and the writing can still be improved, overall this looks like a nice paper and should make it to NeurIPS.\n\nThe overall framework is clean, and the proofs are easy to read. I quickly checked all the proofs, and they look good to me. I am not 100% sure that all proofs are sound, but even if there are small errors, they should be fixable because the results are very intuitive.", "weaknesses": "My only concern is that the significance of this work might not be obvious to a person who is not very familiar with this field. This work is addressing a very specific issue in a previous theorem, and while this issue is important, I think the authors should clarify more about why it is important, what is the main challenge and how this paper fixes it, right at the beginning of the paper. Right now I would say that those things are quite scattered. For example, the main challenge is in Section 6.2. I think the authors could include the following in the intro:\n- What is the main issue in the previous PAC-Bayes bounds?\n- Why is it difficult to fix this issue?\n- What additional assumptions does this work make in order to fix this issue?\n- What is the main technical contribution in the proof of this work?\n\nAs someone very familiar with learning theory and adversarial robustness, I can find the answers to these questions easily in the paper. However, if the authors want to appeal this work to a more general audience, I suggest them rearrange the paper a little bit, and discuss these questions in the intro.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thanks Reviewer FsEL for the comments and questions.\n\n**Comment 1.** My only concern is that the significance of this work might not be obvious to a person who is not very familiar with this field. \n\nA. Thanks for the suggestions. We understand that the significance of this work might not be obvious to general readers. We will clarify \n\n1)\tWhy the targeted problem is an important unsolved problem? And\n\n2)\tWhy our result is significantly important?\n\nin Intro. Such discussion is also provided in our answer to common question 1.\n\n\n**Detailed suggestion.** I think the authors could include the following in the intro.\n\nA. Thanks for the suggestions. Some of them (2,3) are already provided in intro. The others (1,4) are discussed but not emphasized. We provided our detailed answer and detailed modification below.\n\n**S1.** What is the main issue in the previous PAC-Bayes bounds?\n\nThis in discussed in line 55-56. We will add: “The inclusion of these supplementary assumptions and an additional term is less than ideal. These adjustments were made as a compromise to address mathematical complexities.\"\n\n**S2.** Why is it difficult to fix this issue?\n\nThis is discussed line 48-51. \n\n**S3.** What additional assumptions does this work make in order to fix this issue?\n\nThis is discussed in line 58.\n\n**S4.** What is the main technical contribution in the proof of this work?\n\nThe technical contribution is detailed in the paragraph titled \"Technical Contribution\" on line 73. The current exposition is presented at a high level; we will now provide a more specific breakdown to the updated version:\n\nOur approach to solving this problem involves two main aspects:\n\n1) We introduce a crucial inequality to address this problem, which is the preservation of weight perturbation bound under lp attack.\n\n2) We restructure the proof by Neyshabur et al., in terms of the margin operator. This modification enables the application of the aforementioned inequality.\n"}, {"review_id": "8O0TAWWktX", "reviewer": "Reviewer_Ccn3", "summary": "This work tries to develop a PAC-Bayesian spectrally-normalized robust generalization bound.", "questions": "ref Weaknesses", "limitations": "ref Weaknesses", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This work tries to understand robustness from theoretical perspective.", "weaknesses": "1. unclear definitions:  \nsecond line in Eq. (4)  \n$\\mathbf{x}(\\mathbf{w})=\\arg \\inf_{\\left\\|\\mathbf{x}-\\mathbf{x}^{\\prime}\\right\\| \\leq \\epsilon} g_{\\mathbf{w}}(\\mathbf{x})$ (I guess it's $\\mathbf{x}(\\mathbf{w})=\\arg \\inf_{\\left\\|\\mathbf{x}-\\mathbf{x}^{\\prime}\\right\\| \\leq \\epsilon} g_{\\mathbf{w}}(\\mathbf{x'})$)  \n$\\mathbf{x}(\\mathbf{w}')=\\arg \\inf_{\\left\\|\\mathbf{x}-\\mathbf{x}^{\\prime}\\right\\| \\leq \\epsilon} g_{\\mathbf{w}'}(\\mathbf{x})$  \n$\\inf_{\\left\\|\\mathbf{x}-\\mathbf{x}^{\\prime}\\right\\| \\leq \\epsilon} g_{\\mathbf{w}}(\\mathbf{x})$  \netc\n\n2. Assumptions are not clearly described before theorem 1:  \nWhat are the conditions on $B$ and $\\gamma$ for your theorem?  \nE.g., Neyshabur et al. (2017b) assumes $\\mathcal{X}_{B, n}=[ \\mathbf{x} \\in \\mathbb{R}^n \\quad | \\quad ||\\mathbf{x}||_2 \\leq B ]$  and  $\\mathbb{P}_\\mathbf{u} [\\max_\\mathbf{x} | f_\\mathbf{w+u}(\\mathbf{x})-f_\\mathbf{w}(\\mathbf{x}) |_\\infty<\\frac{\\gamma}{4} ] \\geq \\frac{1}{2}$ (or $\\ell_2$ norm).  \n\n3. Miss citation for Line 482.  \n\n4. What is $||W_i-W_i||$?\n\n5. Please provide the details from Eq. (10) to Eq. (11).  \n\n6. As claimed in the contribution: **without any additional assumption**, **as tight as**, **how to obtain a robust generalization bound**.  \nMy concerns are: **Does this bound provide new information for us?**  In my opinion, for (middle or large) DNNs, PAC-Bayes is not a tight bound but may provide inspiration for us to get a better generalization model. For the bound of this work, it just replaces $B$ with $B+\\epsilon$. To me, it simply implies that $||\\mathbf{x}||_2\\le B$ (clean data), $||\\delta||_2\\le \\epsilon$ (attack radius) thus $||\\mathbf{x}+\\delta||_2\\le B+\\epsilon$ (adversarial data), but it holds no significant meaning.  \n\nFor the above reasons, I think this work should be rejected. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thanks Reviewer Ccn3 for the comments and questions.\n___\n**Q1, Q3 and Q4.** Unclear definition, what is $W_i-W_i$. Miss citation.\n\nA: Thanks for pointing out the typo and missing citation. Some prime’ are missed due to the full/half width issue. We fixed the typo in the updated version. In $W_i-W_i’$, the second one should be $W_i’$. The second line in Eq. (4) is equal to the first line. Line 482 is the tail bound [1].\n\n[1] Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389–434, 2012.\n___\n**Q2:** What are the conditions on B and γ for your theorem?\n\nA. Thanks for the question. B and γ are well-defined before the Theorem and it is the same as that in Neyshabur et al., 2017. \n\nB is first defined in line 65. It is the magnitude of the training sample. We will also add $||x||_2\\leq B$ for all training samples $x$ in line 135.\n\n$\\gamma$ is defined in line 147. It is the margin of the function value between true label and the max of false label.\nIt is important to note that $\\gamma$ is also the margin in Neyshabur et al., 2017. There exists a misunderstanding that $P_{u}\\left[\\max_{x \\in X} |f_{w+u}(x)-f_{w}(x)|_\\infty <\\frac{\\gamma}{4} \\right]\\geq \\frac{1}{2}$ is not the assumption of $\\gamma$. This inequality is the condition for Lemma 4, and it only serves as a bridge to prove the generalization bound.\n\n___\n**Q5.** Please provide the details from Eq. (10) to Eq. (11).\n\nA. Thanks for the question. The first inequality is Lemma 6.2 (Eq. (9)). The second inequality is the tail bound (line 482).\n\nQ1-5 is about the typos or further detials. We will fixed it in the updated version. Below we answer your main question. \n___\n**Q6:** Does this bound provide new information for us?\n\n**A:** Our main result offers **valuable and new information** into adversarially robust generalization. It is discussed in Section 5. We understand the main concern or confusion come from the fact that we did not emphasize it is new. We will make necessary revision to distinguish old and new information.\n\nThe answer is provided above in common question 2. We hope it adequately addresses your concerns.\n\nWe hope you also review our response to \"common question 1\" for additional context. Understanding the historical background of the theory of norm-based complexity is crucial in comprehending the significance of our findings. Further details will be provided below. Following your thought, we decomposed the question into two questions: \n\n1) the significant meaning of the bounds and \n\n2) the inspiration to get better model.\n\n___\n**Q6.1.** the **significant meaning** of the bounds.\n\nA. replacing B by B + ε has its natural meaning.\n\nIn standard generalization bound: standard generalization ≤ B × spectral complexity means that **standard generalization** is related to **clean samples** and spectral norm (of DNNs).\n\nIn robust generalization bound: robust generalization ≤ (B + ε) × spectral complexity means that **adversarially robust generalization** is related to **adversarial examples** and spectral norm (of DNNs).\n\nTherefore, replacing B by B + ε has a natural meaning: it replaced clean samples by adversarial examples from standard to robust generalization. \n\nThe important message of the bounds lies in the spectral complexity, rather than the training samples.\n___\n**Q6.2.** The **inspiration** to provide better model.\n\nAs you mentioned, the bound may provide inspiration for us to get a better generalization model. Let us discuss about the inspiration.\n\n**Firstly, why standard generalization bound is important?**\n\nIt is proved that **standard generalization ≤ B × spectral complexity**. While the term \"B\" may not be directly controllable, the spectral complexity is within our control. Therefore, focusing on the controllable factor of spectral complexity presents a potential avenue to enhance generalization performance.\n\n**Secondly, why robust generalization bound is important?**\n\nIt lies in the widely observed phenomenon where deep neural networks (DNNs) exhibit strong standard generalization but poor robust generalization. It is important to see what factors contribute to this difference. Then, the mismatch factors between standard and robust bound provide rich information to understand the disparity between standard and robust generalization.\n\n**Previous result** showed that **robust generalization≤ (B + ε) × spectral complexity and other factors**. $B+\\epsilon$ (the adversarial example) is not controllable but the other factors are controllable. Therefore, spectral complexity and other factors (width, gradient, addition assumptions) are all potential factors to improve robustness.\n\nHowever, it is hard to verify which factors are more important, since we don’t know whether these bounds are tight in terms of additional factors, and whether these factors can be further reduced. Therefore, providing a better bound is an important problem in learning theory. Our paper give an affirmative answer. \n\n**We prove that robust generalization ≤ (B + ε) × spectral complexity.**\n\nTherefore, we dismiss the possibility of other factors (width, gradient, assumptions). At least from theory perspective, these other factors are solely comes from mathematic issue. It inspires engineers to pay more attention to spectral complexity as a potential factor to improve robustness. It is crucial to emphasize that the inspiration discussed is solely derived from our result.\n\nWe hope our explanation can help understand why our result is important from an inspiration perspective.\n\n___\nOverall, we believe our work provide a fundamental result to the learning theory comunity. Currently, the score \"Soundness: 1 poor\" and \"Contribution: 1 poor\" is very unfair to our work. We hope our answer can address your concern. We hope you can reconsider the significance of our work. If you have any further inquiries, please feel free to ask."}]

Author rebuttal:
We thanks all the Reviewers for the comments and questions. We will first answer three common questions.

**Common Question 1:** Significance of the result. (Reviewer nNum & AB19)

**A:** Our finding is not just an incremental improvement on Farnia et al. (2018); it holds **significant importance** in the field of learning theory, as highlighted by Reviewer FsEL. Let us clarify below.

Short version:

There's an important unsolved question over the past few years: Is there a clean/tight extension of norm-based generalization bound to robust settings? 

No less than 7 papers (The work discussed in line 117 to 130) aimed at solving this problem. However, they have faced mathematical challenges. The most important contribution of our paper is to provide the **mathematical technique** (Presented in Sec. 6) to resolve this problem.

We understand our comparison to Farnia et al. (2018) **mislead the reviewers to consider our work is incremental.** However, this comparison aims to shed light on the mathematical difficulties involved in deriving robust bounds. We will make revision to address this concern.
___
Long version:

**1) Importance benchmark of norm-based generalization bounds.**

Firstly, norm-based complexity stands as a crucial generalization measure for ML models. This field has seen significant interest, with numerous published papers (not less than 30) exploring this topic. In 2017, Neyshabur et al. introduced a spectral-normalized bound for standard settings, using Pac-Bayes approaches. After that, progress in the field of norm-based bounds for standard training has experienced a temporary stall in recent years, with no tighter bounds being proposed.

(Additionally, similar spectral norm bound is provided by Bartlett et al., 2017 using covering number approach. The above-mentioned two results hold fundamental significance and have been widely discussed in prominent ML courses, such as Stanford CS229M (Lecture 5) and MIT Statistical Learning Theory (Lecture 16).)

As such, Neyshabur et al.,'s (or Bartlett et al.,'s) bounds serve as essential 'benchmark' generalization bounds. Therefore, we refer to this bound as 'benchmark bound'. A direct question arises. 


**2) Fundamental question: Is there a clean/tight extension of norm-based bound to robust settings?**

However, this question troubles the community in the last few years.

Researchers found that it is mathematically challenging to derive robust bounds using both Pac-bayes approach (Farnia et al., 2018) and covering number approaches (the work discussed in lines 117-130). 

As a result, these work often consider simplifying cases or introducing additional assumptions to bypass the difficulty. The resulting robust bounds is much larger than the standard bound, exhibit higher dependence on factors, such as depth and width, or include additional terms. It remains uncertain whether further reduction is possible. Such attempts did not offer a clean bound for robust generalization.

The significance of our paper lies in providing the math technique to resolve this problem. We demonstrate that the robust generalization bound can achieve the benchmark bound. All the higher dependencies on factors, additional terms, or extra assumptions can be eliminated.

**3) Our paper resolve this question.**

More importantly, our results temporarily close this question, without a tighter (norm-based) bound for standard generalization, no tighter (norm-based) bound for robust generalization will be provided. 

___
**Common Question 2:** New insight to the robustness community. (Reviewer nNum & Ccn3)

**A: Our bound offers significant new insights into adversarial robustness**, as discussed in Sec. 5. One main source of confusion stems from the fact that we did not emphasize this crucial information in Sec. 5 cannot be provided by previous research.  We will make necessary revision to distinguish old and new information.

Let us explain it below.

It is widely recognized that deep neural networks (DNNs) demonstrate good standard generalization ability but often exhibit poor robust generalization. A key question that needs to be addressed is:

**What factors contribute to such a significant difference?** (Line 204)

Previous studies have shown that the robust bound is much larger than the standard bound. Therefore, the mismatch term between these two bounds might be a contributing factor to the significant difference. For instance, the robust bound might have a higher dependence on width or include an additional term related to gradient information. Such factors (width, gradient) could potentially explain the disparity between standard and robust generalization.

**Current Hypothesis: The significant difference is due to Robust Bound >> Std Bound.**

However, verifying this hypothesis has been challenging because it remains unclear whether the existence of these factors is due to mathematical issues.

Our results provide a definitive answer and dismiss this possibility. In essence,

**Our result: Robust Bound $\approx$ Std Bound.**

We have shown that the additional factors (dependence, additional terms, assumptions) are solely due to mathematical considerations. Consequently, from a norm-based complexity perspective, they do not contribute to the significant disparity.

Therefore, in Section 5, we focus on attack intensity and spectral complexity. 

From the norm-based complexity perspective, we show that only **attack intensity** and **spectral complexity**, (but not other factors), contribute to the significant disparity. We believe this is a significant new insights into adversarial robustness.

___

**Common Question 3: Limitation.**

We provide the limitation below, which will be added to Sec. Conclusion.

The main limitation is that the norm-based bounds are all large in practice, as it is shown in Table 1. How to obtain smaller bound in a practical scenario is an open problem.

Meta-review: The reviewers appreciated the improvements in the bound compared to previous work.
The main contribution compared to Farnia '18 and Neyshabur '17 is that the authors use a different perturbation quantity (perturbation of margin) for robust compared to standard generalization that allows tighter bounds with fewer assumptions, based on the Pac-Bayes framework (as in previous works) - the writing is also quite clear in pointing this out. As usual, it's unclear if these bounds are useful in practice, but that is a criticism that applies to deep learning theory in general...
Decision: Accept (poster)