Algorithmic Stability Based Generalization Bounds for Adversarial Training

Thank you very much for your careful review and your positive feedback!

Regarding your comments:

• It seems that the framework in this paper can not provide a proper description for the $Q(c^*)$ term, we need to calculate it according to the concrete choice of $J, \pi$. However, to make this framework more significant, examples of how to calculate $Q(c^*)$ and how to choose $c^*$ should be added. Note: I mean examples in practice but not examples with overly simple assumptions (such as the assumption on the second moment in lines 293-294 and the assumption in Corollary 5.2 that a term is bounded by $B$ with probability 1). Just like the VC dimension, if we can not calculate the VC dimension of some hypothesis classes, the bound with the VC dimension is meaningless.

We agree that it would be nice to have a better characterization of the term $Q(c^*)$. In this paper, the introduction of this term is to bring in a better handle for driving the bound to decay at the rate of $1/n$. It mainly serves as an analytic technique at the moment. Nonetheless we appreciate your suggestion and will look into the possibility of better characterizing the term when more structural assumptions are incorporated in the loss function or in the network structure.

• Typo: in line 149, it should be "the label space $\mathcal{Y}$ is finite"

Thank you very much for pointing out this typo. We have fixed the typo.

• A minor issue: many equations in this paper are numbered, in fact, the equations that are not used later need not be numbered. For example, equation (2) is not used.

Thank you very much for pointing this out. For the time being, to avoid causing any inconvenience for the reviewers during the rebuttal phase, we will retain these equation numbers, allowing the reviewers to easily refer to specific equations in the paper. The unused equation numbers will be removed in the final revised version of the paper.

• In lines 87-88, the paper says that "the bound convergence to a constant, this helps explain the robust overfitting phenomenon". In fact, a lower bound of the generalization gap that converges to a constant can explain overfitting. However, an upper bound can not because your bound may not be tight enough.

You are correct and we fully agree. The statement lacks rigor. We have removed the statement in our manuscript.

Thank you very much for your careful review! To address your concerns and questions, we have performed additional theoretical analysis and experiments and include the results temporarily in Appendix E.2 (from line 1124) of our paper.

Regarding your questions and concerns:

(1) While the paper considers the algorithmic stability of PGD attack, a missing component is the convergence of PGD attack. Intuitively, if we always use a fixed attack direction, then the algorithmic stability is not largely affected by the attack. However, the attack is not efficient. When using PGD attack, there is supposed to have a trade-off: with more iterations, the stability gets worse, but the attack becomes stronger. If at the test stage the attacker uses a very strong attack, e.g., AA attack, then balancing the attack effectiveness and stability is essential to obtain a better robust testing performance. Could the authors elaborate more from this perspective?

Thank you very much for this interesting question and perspective. We now have included a new section Appendix E.2 in the revised paper, which provides a convergence analysis of the PGD attacks. We now summarize the results here (for more details and more precise statements of our results, please refer to Appendix E.2)

We consider PGD attacks with the mapping $G$ that satisfies the following condition: $\nabla_{x}f(w,x,y)^{T}G(\nabla_{x}f(w,x,y))>0$, for any $(x,y)\in {\cal X}\times {\cal Y}$ and any $w\in{\cal W}$. Note that this condition simply requires the direction of the modified gradient $G(\nabla_{x}f(w,x,y))$ aligned near the direction of the original gradient, within 90 degree angle. Then we have the following result (Lemma E.1 in the revised paper)

Lemma E.1 Suppose that $f(w, x, y)$ satisfies the condition (22).Let $x^*= J^* (x;y,w)$ and suppose that $\nabla_x f(w, x^*,y)=0$. Suppose $\|G(\nabla_{x}f(w,x,y))\|^2\le C$ for any $(w,x,y)$. Then performing the $K-$step PGD with step size $\lambda=\frac{1}{\sqrt{K}}$ results in

$f(w, x^*, y)-\frac{1}{K}\sum_{k=1}^{K}f(w, x^k, y)\le \frac{(2C+d^*)}{2K} + \frac{d^* (\eta^2 + \eta + 1)}{2}$

where $d^* = \max\limits_{k\in \{ 1,\cdots, K \} } \Vert x^k -x^* \Vert ^2$ and $x^k := T^k _{x, y} (x; w)$ denotes the perturbed instance generated by the $k-$step PGD with $k\le K$.

This result bounds the difference between the maximal loss $f(w, x^*, y)$ and the average of the losses achieved by $K$-step PGD (averaged over the $K$ steps). If the achieved loss $f(w, x^k, y)$ increases over the K steps, the result implies

$f(w, x^*, y)-f(w, x^K , y)\le \frac{(2C+d^*)}{2K} + \frac{d^* (\eta^2 + \eta + 1)}{2}$

Notably this upper bound decays with $K$, but converges to a positive constant. This should come as no surprise since without stronger conditions or knowledge on $f$ (e.g., concavity), it is hopeless to have PGD attacks to reach the true maximal loss value $f(w,x^*, y)$.

If we further assume loss functions $f(w,x,y)$ to be concave in $x$ and consider the "raw-gradient (RG)"-PGD where the mapping $G$ is taken as the identity map, we have the following convergence upper bound for PGD by directly adapting the Theorem 3.7 in [Bubeck et al, 2015convex] (Lemma E.2 of the revised paper):

Lemma E.2 Suppose that $f(w, x, y)$ satisfies the condition (22) and is concave in $x$. Let the mapping $G$ be the identity map. Then the $K-$ step PGD with step size $\lambda=\frac{1}{\eta}$ satisfies

$f(w, x^*, y) - f(w, x^K, y) \le \frac{3\eta \|x - x^*\|^2 + f(w, x^*, y)-f(w, x, y)}{K}$

where $x^*= J^* (x;y,w)$ and $x^K:=T^K _{x, y}(x; w)$.

The bound obviously vanishes with $K$.

Dear Reviewer,

As the rebuttal period is ending, we hope to hear your comments on our reply to your review. In case you have further questions, please let us know in your earliest convenience, so that we can make an effort to respond before the rebuttal period ends. If we have addressed all your concerns, please consider raising your score. Thank you.

• Results of Section 6: The authors mention the connection between adversarial training and steepest descent methods, but it is clear that this has been the motivation for the iterative solution of the inner maximization problem since the introduction of adversarial training. Furthermore, the experiments fail to highlight anything new, in my understanding (basically optimising an $\ell_\infty$ objective yields better coverage against $\ell_\infty$ attacks).

There have been a misunderstanding regarding Section 6 of our paper. This section is not intended to explain "the connection between adversarial training and steepest descent methods," as stated by the reviewer. The beginning of the section intends to explain why the sign function (or the sign gradient) is specifically used in PGD rather than the raw gradient. Note that this peculiar choice of sign function is not related to the $\infty-$norm ball used in the projection step of PGD. We will elaborate this below.

In Section 6, we investigate the effects of replacing the sign function with alternative operators $G_p$. Importantly, the projection step in PGD consistently operates with respect to the same $\infty-$norm ball, regardless of the choice of $G_p$.

Each iteration of PGD involves a gradient ascent step followed by a projection step. The emergence of the sign function arises from treating the gradient ascent step as maximizing a locally linear approximation of the loss function.

Specifically, at the $k-$th iteration of PGD where $x^ k$ is to be updated by PGD, the loss function is approximately considered to be linear within a $p-$norm ball (i.e., $\mathbb{B} _ p (x^ k , \lambda _ p)$ ) around $x^ k$ (not around $x$) with radius $\lambda _ p$ . If this norm ball is chosen as $\mathbb{B} _ {\infty}(x^ k, \lambda)$, the sign function naturally arises in the gradient ascend step of the PGD. However, this does not mean choosing $\mathbb{B} _ p (x^ k, \lambda _ p)$ as $\mathbb{B} _ {\infty}(x^ k, \lambda)$ is the only option. We therefore investigate the norm ball $\mathbb{B}_{p}(x^k, \lambda_p)$ with other choices of $p$. This merely corresponds to the linear approximation of the loss function within different local ranges. Consequently, $G_p$ in different forms results.

It is also important to emphasize that both $\mathbb{B} _ {p}(x^ k, \lambda _ p)$ and $\mathbb{B} _ {\infty}(x^ k, \lambda)$ are different from $\mathbb{B} _ {\infty}(x, \epsilon)$ that is used in the projection step of PGD. Regardless the choice of $\mathbb{B} _ {p}(x^ k, \lambda _ p)$ in determing $G _ p$ for the gradient ascend step of PGD, the projection step always operates using the same $\infty-$norm ball $\mathbb{B}_{\infty}(x, \epsilon)$ . We suspect the reviewer might have confused these two types of norm balls when first reading our paper, leading to a misunderstanding of Section 6.

Finally, to the best of our knowledge, the perspective of replacing the sign function with $G_p$ and analyzing its effects is novel. Contrary to the comment that this approach "fails to highlight anything new," we believe this original angle offers valuable insights into understanding the generalization of AT.

• Unclear contributions: The paper does not clearly describe how the derived bounds differ from those of Xiao et al. (2022b) and Wang et al. (2024). In particular, the bounds from these prior works are not presented, and they are solely critiqued on the basis that they do not vanish with increasing sample size. Furthermore, the criticism of the non-smoothness of the loss function adopted in prior work seems unfounded ("The source of the non-smoothness is, however, not explained in their work"). Even for linear models under $\ell_\infty$ perturbations, a cross-entropy loss is non-smooth. Hence, the property of non-smoothness is well-motivated.

Regarding your comment that "The paper does not clearly describe how the derived bounds differ from those of Xiao et al. (2022b) and Wang et al. (2024)...", we note that this has been clarified in our response to Reviewer e9T9 and we also have incorporated the detailed comparison with Xiao et al. (2022b) and Wang et al. (2024) into the revised manuscript from Line 1392 in Appendix F. We invite the reviewer to read that discussion.

Regarding your next critique on our statement that "The source of the non-smoothness is, however, not explained in their work", we believe there might have been some misinterpretation. To clarify, this statement is not intended as a critique of Xing et al. (2021) for assuming non-smoothness of the adversarial loss. Rather, it highlights that the non-smoothness property used in Xing et al (2021) is not characterized at any quantitative level. In fact, the development of Xing et al (2021) does not rely on any quantitative specification of the non-smoothness and directly invokes the previous result of Bassily et al (2020) .

Nonetheless we recognize that this statement wasn't clear enough, and we have revised it to "The non-smoothness is however not quantitatively characterized in their work".

• Unclear motivation for experiments: The authors seem to identify the sign function in the solution of the inner maximization problem in the robust objective as problematic, and they suggest an alternative based on a smooth approximation. However, they do not show any benefits in terms of robustness with the new method. Furthermore, the fact that for small $\gamma$ we do not observe overfitting and the generalization gap is small appears to be a trivial observation, as the evaluation basically approaches the standard case of no perturbations. In short, it is not a good method for finding worst-case $\ell_\infty$ perturbations.

We suspect that the reviewer misunderstood this part of the paper.

The motivation of introducing ${\rm tanh}_{\gamma}$ function in our experiments stems directly from the theoretical analysis presented in the previous section, where the purpose, as we stated in the original paper (line 387 in the current manuscript), is "To investigate how the expansiveness property affects generalization". It is not proposing a new AT algorithm. The experiments are designed to empirically validate our theoretical analysis.

Thank you for taking the time to read our paper. We acknowledge that our manuscript contains minor typos and has room for improvement. Given the extensive use of mathematical notations, we understand that fully grasping the content may require some patience.

However, we would like to note that the other three reviewers have found our paper to be "clear", "easy to follow" and "easy to understand", or "the writing is good". We have now fixed the typos and kindly invite you to revisit the paper.

For your comments and questions:

• Poor presentation: There are many instances where the text is not polished, with numerous grammatical errors (see the non-comprehensive list at the end of the Weaknesses). Additionally, the presentation of the technical results could be substantially improved (e.g., Theorem 4.1: remind the reader of the constants $\beta, \Gamma_X$). Furthermore, the authors should mention in the introduction that all of their results are solely about $\ell_\infty$ perturbations.

We have fixed the typos and the grammatical errors that you mentioned.

Regarding your next critique that " the presentation of the technical results could be substantially improved (e.g., Theorem 4.1: remind the reader of the constants $\beta, \Gamma_X$).", we would like to note that in Theorem 4.1 of our original manuscript, we have explicitly stated at the beginning that "Suppose that $f$ satisfies the conditions (6) and (7). ". The constants $\beta, \Gamma_X$ are introduced in conditions (6) and (7).

Regarding your suggestion that "the authors should mention in the introduction that all of their results are solely about $\ell_\infty$ perturbations.", this has been clearly stated in the original version of the paper (Section 3, current line number 152), as stated "Each adversarial attack (or adversarial perturbation) on input $x$ is assumed to live in an $\infty$-norm ball "

We will consider emphasizing this in the Introduction section of the final manuscript, provided that page limit allows.

• Introduction of many ad-hoc terms to denote well-established concepts: In many places, the authors use obscure words to define concepts that are well-defined in learning theory. For instance, lines 258-259: "mis-matched generalization gap" — this is just the standard generalization gap of a predictor trained robustly. Several such choices make it difficult for readers to comprehend the contributions of this work. Similarly, with so-called "RG-PGD" and the "expansiveness property" (a relaxed notion of Lipschitz continuity).

Regarding your critique that "For instance, lines 258-259: 'mis-matched generalization gap' — this is just the standard generalization gap of a predictor trained robustly.", we suspect that the reviewer might have mis-read this line of statement: this notion is not the standard generalization gap for a predictor trained robustly, but includes it as a special case. Specifically, the "standard generalization gap of a predictor trained robustly" is a type of "mis-matched generalization gap" when $J=J^{\rm id}$ and $\pi$ is a particular perturbation.

We acknowledge that our paper introduces several new terms for the ease of reference and improved clarity. They seem to be have been appreciated by other reviewers.

The limitation of the framework in [2]: We would like to note that when the standard loss $f$ satisfies the Assumption 4.1 in [2] (or condition (7) in our paper), in fact every $J-$loss (for any arbitrary $J$, including but not limited to $J^*$) is $2\Gamma_{\cal X}\epsilon-$approximately smooth. To see this:

$\Vert \nabla_{w_1}f_{J}(w_1, x, y)-\nabla_{w_2} f_{J}(w_2, x, y)\Vert$

$=\Vert\nabla_{w_1}f(w_1, J(x;y, w_1), y)-\nabla_{w_2}f(w_2, J(x;y, w_2), y)\Vert$

$\le \beta \Vert w_1 - w_2 \Vert + \Gamma_{\cal X} \Vert J(x;y, w_1) - J(x;y, w_2) \Vert \quad (1)$

$\le \beta \Vert w_1 - w_2 \Vert + \Gamma_{\cal X} (\Vert J(x;y, w_1) - x \Vert+ \Vert x-J(x;y, w_2) \Vert)\quad (2)$

$\le \beta \Vert w_1 - w_2 \Vert + 2\Gamma_{\cal X}\epsilon \quad (3)$

where inequality (1) follows from Assumption 4.1 in [2]. Inequality (2) and (3) are derived by using the triangle inequality and the condition that $\Vert J(x;y,w)-x \Vert \le \epsilon$ for any $w \in {\cal W}$.

Due to the fact that all the $J-$losses have the same approximate smoothness parameter $\eta$, the generalization bounds derived for different $J-$loss, based on the framework in [2], will be the same. This type of generalization bound ignores the influence of the perturbations used in AT on generalization and is therefore unable to explain the experimental observations in our work where different choices of perturbations indeed have distinct impact on generalization.

Difference of our approach from [2]: In this paper, we depart from the approach of [2], which ignores the specific properties of perturbation $J$, and take a different route which considers the impact of $J$ measured via its expansiveness parameter. Our approach allows us to analyze how different perturbations used in AT affect its generalization performance. Our bounds, derived based on the expansiveness parameter, also avoid having the non-vanishing term (like the first term in Theorem 5.1 of [2]) when the expansiveness parameter is finite. Only in the case when the expansiveness parameter is unbounded, our results are similar to [2], where the generalization bound contains a non-vanishing term.

The UAS parameter of AT characterizes the gap $\Vert w-w' \Vert$ where $w=A(S)$ and $w'=A(S')$ are the model parameters produced by the AT algorithm on two nearly identical datasets $S\simeq S'$. Intuitively, the difference between $w$ and $w'$ arises from the single different example in $S$ and $S'$ (where larger training sample size $n$ tends to reduce the probability of using that single different example to update model parameters in AT), and gets "magnified" by the perturbation $J$ along the AT training trajectory. The expansiveness parameter of $J$ that we define effectively captures this "magnification" factor. Thus, the eventual difference between $w$ and $w'$ depends on not only the sample size $n$ but also the expansiveness parameter of $J$. Then our exploitation of the expansiveness of $J$ brings sample size $n$ into our bound.

Thank you very much for your careful review! We have fixed the typo in our paper. To address your concerns and questions, we have conducted additional experiments and include the results temporarily in Appendix E of our paper.

Regarding your concerns:

• "Authors claim that their upper bound converges to zero with increasing number of training samples and the ones of [1,2] do not. This is misleading as [1,2] do not consider the expansiveness of the attack operator and the bound provided in this work, in the same setup as [1,2] does not vanish with $n$ (see lines 369-371)."

We acknowledge that our bound does not vanish when $J$-loss defined using sign-PGD. However, we note that although the behavior of our bound in this specific setting is similar to that in [1,2], our setup for this result and the setup of the results in [1,2] should not be taken as the same. For example, the main result in [2] (Theorem 5.1) states, using our notations, that for any $J$-loss satisfying the various assumptions in [2], the geneneralization bound does not vanish. However, in our paper, we show that only for $J$-loss defined using sign-PGD, our bound does not vanish.

For $J$-losses satisfying the conditions of Theorem 5.1 in [2], we show that there exists a broad family of $J$-losses for which our generalization bound does vanish. That is, for this family of $J$-losses (namely, those having bounded expansiveness), our results are stronger than that in [1, 2]. This is further elaborated when we address your next comment.

• "The difference with the previous bounds is not clearly covered in the paper. The proof technique and assumptions are very similar to [1,2], nevertheless the bounds in [1,2] are not presented in the work and there is no discussion about how to integrate previous bounds with the expansiveness setup introduced in this work, making it difficult to assess the contributions. It would be nice to add a discussion about which role expansiveness plays in the result of [1,2], i.e., can it result in a vanishing upper bound with $n$? It would also be good to have a table comparing the different upper bounds."

Since the work of [1] is built upon the framework in [2], we here only present the connections and differences between [2] and our work.

Summary of generalization bounds in [2]: First we would like to note that our problem setting includes the setting in [2] as a special case. Specifically, the generalization gap discussed in [2] corresponds to the generalization gap ${ \rm GG} _ {n} (J^*, A _ {J^*})$ defined in our work, where the perturbations in both $J-$loss and the AT algorithm are taken as the optimal adversarial perturbation $J^{*}$.

Our work and [2] both take the Lipschitzness and smoothness conditions of the standard loss $f$ as the starting point, but derive generalization bounds from different perspectives: the work in [2] defines and proposes to study the $\eta-$approximate smoothness of the adversarial loss ( $f^*$ in our notation) and derive generalization bounds based on this quantity. Our work define the notion of $c-$expansiveness of the perturbation operator (e.g., $J^{*}$) and show how this quantity affects generalization performance of AT.

For completeness, we here present the definition of $\eta-$approximate smoothness, rewrite the Definition 4.1 of [2] using our notations.

Definition ($\eta-$approximate smoothness [2]) A loss function $f_J$ is called $\eta-$approximately $\beta-$gradient Lipschitz if there exists $\beta>0$ and $\eta>0$ such that for any $(x,y)\in {\cal X}\times {\cal Y}$ and for any $w_1, w_2 \in {\cal W}$ we have ​ $\Vert \nabla f_J(w_1, x, y)-\nabla f_J(w_2, x, y) \Vert \le \beta \Vert w_1-w_2 \Vert + \eta$ The work in [2] then derives generalization bounds for loss functions that are $\eta-$approximately smooth. For example, after replacing the notations in [2] with ours, Theorem 5.1 of [2] shows that if $f_{J}$ is $\eta-$approximately $\beta-$gradient Lipschitz, convex in $w$ for all $(x,y)$ and the standard loss $f$ satifies the same Lipschitz condition in (6) of our paper (or Assumption 4.1. in [2]), then their bound in Theorem 5.1 becomes ​ ${\rm GG}_ {n} (J, A _ {J}) \le \frac{L _ {\cal W}}{\beta}\eta T + \frac{2L_{\cal W}^{2}}{n\beta}T$ The authors of [2] show that the adversarial loss $f^*$ satisties $\eta$-approximately $\beta$-gradient Lipschitz with $\eta = 2\Gamma _{\cal X}\epsilon$ so that the generalization bound above gives their generalization bound for adversarial training. In their determination of the $\eta$ parameter, they have assumed that the standard loss $f$ satisfies certain Lipschitz and smoothness condition; this condition is effectively equivalent to our condition (7).

It is worth noting that the generaliztion bounds derived based on the approximate smoothness parameter $\eta$ contain a term unrelated to the sample size $n$ because of the independence of $\eta$ on $n$.

Regarding your questions:

• "How does the bound in [1,2] change when considering ${\rm tanh}_{\gamma}$-PGD?"

As we have shown above, the bound remains unchanged in [1,2] when considering ${\rm tanh}_{\gamma}$-PGD with different $\gamma$.

• "Have you tried larger $\gamma$ s? $\gamma=10^5$ seems to be very far from sign-PGD in Figure 2 (b). It would be interesting to see how does tanh-PGD behave when it’s close to sign-PGD."

The reviewer might have misread Figure 2b. In fact, in that figure when $\gamma = 10^5$, ${\rm tanh}_{\gamma}$ function closely approximates the sign function and $\gamma = 10^5$ is actually sufficiently large.

To illustrate, we have plotted the training trajectory of ${\rm tanh}_{\gamma}$-PGD AT with $\gamma=10^5$ and the trajectory of the sign-PGD AT in Figure 7 (a), Appendix E.1. (from line 1074). The results show that their trajectories overlap almost entirely.

Further, we have plotted the $\tanh_\gamma$ function with $\gamma=10^5$ and the sign function in Figure 7 (b), Appendix E.1, to show that they are indeed very close.

• "Can you construct an experiment where the dependence on $n$ is displayed? For example taking a smaller number of samples from the studied datasets in order to see how the generalization gap grows. A synthetic distribution could also be employed where more and more samples are drawn and the gap decreases to zero for finite $\gamma$."

Upon your request, we have performed AT experiments using various fraction of the training set from CIFAR-10 and SVHN. The generalization gaps are estimated and plotted in Figure 8 in Appendix E.1. It is clear that the generalization gaps reduce with the increase of training sample size $n$. Notably, in the limit when $n$ approaches infinity, the model is effectly trained on the entire data distribution, and the generalization gap must approach zero.

Also observed from the figure is the phenomenon that smaller $\gamma$ gives smaller generalization gap. This is consistent with our theoretical analysis.

Dear reviewer,

Thank you for raising your score! We have now included comparison of our work with [1, 2] in Appendix F. We also would like to elaborate this aspect in the main body of the paper. But at current stage, in order not to disturb line numbers for the ease of all reviewers, we will postpone this when we prepare next version of the paper.