Stability and Generalization in Free Adversarial Training

We thank Reviewer wev8 for his/her time and constructive feedback and suggestions. Below is our response to the questions and comments in the review.

1- Tightness of the generalization bound

Re: The reviewer is right that the generalization bound in Theorems 2 and 4 could be pessimistic in the sense that we only assume bounded Lipschitz and smoothness coefficients of the learning objective function. We would like to clarify that we did not make a definite theoretical statement on the generalization comparison of vanilla and free adversarial training, since our stability-based generalization bounds only suggest a lower expected generalization gap for free AT in comparison to vanilla AT. As pointed out by the reviewer, a generalization lower-bound would shed light on the tightness of the bounds in Theorems 2, 4. However, to the best of our knowledge, the question of a non-trivial lower-bound on the expected generalization gap (the quantity bounded in the stability-based approach) is still an open problem for both nonconvex-concave and nonconvex-nonconcave min-max learning problems.

To investigate the discussed implications of our theoretical bounds, we performed numerical experiments on standard datasets and neural net architectures, which is similar to other theoretical works on the generalization of adversarial learning algorithms. The results of the numerical experiments are consistent with our hypothesis on the comparison of generalization error between vanilla and free AT algorithms.

2- Postponing the numerical results on transferability to the Appendix

Re: As recommended by the reviewer, we deferred the numerical results on the attack transferability to the Appendix, and used the space to present the numerical results on the role of the size of training set $n$, which was suggested by the reviewer.

3- Line styles in Figure 1 for train and test qunatities

Re: We thank the reviewer for pointing out the identical line styles in Figure 1. We have changed the line style for test accuracy in the revision.

4- Empirical comparison between free and vanilla AT with different dataset size $n$ values

Re: Following the reviewer’s suggestion, we performed numerical experiments by randomly sampling a subset of size $n \in \lbrace 10000, 20000, 30000, 40000, 50000\rbrace$ from CIFAR-10 and CIFAR-100 training sets, and trained ResNet18 neural nets using those training sets. The numerical results of our comparison of the generalization gaps between free and vanilla AT are presented in Figure 4 and Appendix B.3 of the revised submission. The results indicate that the generalization gap of free AT is decreasing considerably faster than vanilla AT with dataset size $n$. We thank the reviewer for the great suggestion.

5- “Do the theoretical results also apply to the $L_{\infty}$ case?”

Re: Our theoretical analysis concerns only the $L_2$-norm bounded perturbations. As a Hilbert-space norm induced by an inner product, the $L_2$-based projection reduces to a standard normalization of the input vector which preserves the vector’s direction. This property allows us to leverage the theory of linear dynamical systems to track the changes following the two different datasets $S,S’$ and bound the stability degree of AT algorithms. On the other hand, the $L_\infty$-norm would lead to a sign-based projection that can completely alter the direction of an input vector. Therefore, a similar stability analysis of the $L_\infty$-based AT would lead to a highly non-linear dynamical system which would be difficult to analyze using existing control and optimization theory frameworks.

6- "Has there been any work that empirically estimates the Lipschitz and smoothness constants in Assumptions 1 and 2?"

Re: To the best of our knowledge, computing the exact Lipschitz and smoothness coefficients of overparameterized neural networks is a computationally challenging problem. The related works [3,4] used SDP relaxation to compute the Lipschitz constant of neural networks, but the computational cost of a SDP-based method would be unaffordable for overparameterized neural networks such as standard ResNets. Another line of work [5] attempted to bound the Lipschitz constants and smoothness by using standard matrix-based norm for the neural net’s weight matrices; however, these upper-bounds could be significantly loose in application to standard neural net architectures and image datasets.

7- Relaxation of smoothness and Lipschitzness assumptions

Re: We note that our stability-based generalization results will hold if the bounded gradient and Hessian norm assumptions hold only for every input vector within an $\epsilon$-distance from the support set of the underlying distribution of random vector $X$. We have clarified this point in the revised text.

8- "What is Free-4 in Table 2 and some of the figures?"

Re: We added footnote 1 for clarity. Throughout our work, ‘‘Free-$m$’’ means the free AT algorithm with $m$ free steps, and following from [8] and [9], we use ‘‘Free’’ without specification to denote Free-4 by default.

9- Relationship between $\mathbb{E}[|| w(S) - w(S’) ||]$ and $\mathcal{E}_{gen}$

Re: We agree with the reviewer that a higher stability degree does not necessarily imply a lower generalization gap. Our generalization analysis follows the standard analysis for stochastic gradient-based optimization algorithms (please see the discussion in [7] for more details), and, as the reviewer pointed out, can be pessimistic for a general nonconvex-nonconcave minimax problem. Similar to other theoretical works on generalization of deep learning models, our bounds only suggest a hypothesis for the generalization comparison, which we attempt to validate using numerical experiments.

10- Extension of the analysis to other AT algorithms

Re: We thank the reviewer for the constructive feedback. In Appendix B.6 of our revision, we have performed numerical experiments on a similar ”free” variant of the TRADES algorithm [6] (which we call Free-TRADES). Following our theoretical discussion, the simultaneous optimization updates in Free-TRADES could help lower the generalization gap. Our numerical results indicate that Free-TRADES can also reduce the generalization error. The theoretical analysis of the generalization behavior of Free-TRADES is an interesting direction for future exploration.

[1] Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 2021.

[2] Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training. Advances in Neural Information Processing Systems, 2022b.

[3] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 2019.

[4] Zhouxing Shi, Yihan Wang, Huan Zhang, J Zico Kolter, and Cho-Jui Hsieh. Efficiently computing local lipschitz constants of neural networks via bound propagation. Advances in Neural Information Processing Systems, 2022.

[5] Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Rethinking lipschitz neural networks and certified robustness: A boolean function perspective. Advances in Neural Information Processing Systems, 2022.

[6] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, 2015.

[7] Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv:1509.01240, 2015.

[8] Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free, Advances in Neural Information Processing Systems, 2019.

[9] Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. International Conference on Machine Learning, 2020.

We thank Reviewer T7Bj for his/her time and feedback. Below is our response to the questions and comments in the review.

1- Technical contributions of the work

Re: Free AT is a widely used variant of adversarial training, mainly due to its higher speed in application to large-scale learning problems. While the free AT method has been extensively used in many applications, the existing theory literature on adversarial training methods has not focused on the specific properties of free AT algorithm. In our work, we focus on the generalization analysis of models learned by free AT, which, to the best of our knowledge, has not been studied in previous works.

Regarding the reviewer’s comment on our work’s technical contribution, we note that our generalization guarantee for free AT (Theorem 4) does not follow from any existing stability-based generalization bound for min-max learning frameworks. Specifically, our generalization analysis accounts for the following properties of the free AT method, which have not been considered in the related works:

1- Re-initialization of the max variable (adversarial perturbations) after the completion of optimization steps for every batch of training data
2- Utilizing the normalized gradient (instead of vanilla gradient) for the gradient ascent step of solving the maximization sub-problem
3- Using mini-batch stochastic optimization for updating min and max variables at every iteration

The generalization analysis under the above conditions and the comparison of generalization performance between vanilla vs. free adversarial training are our work’s main technical contributions, which we believe are novel results that do not follow from any existing bound in the literature.

2- The assumption on bounded gradient norm $\Vert\nabla_\delta h(w,\delta;x,y)\Vert$ in Theorem 4

Re: We note that the bounded-gradient-norm assumption is only needed for the points within an $\varepsilon$-distance from the training samples. Based on this comment, we numerically evaluated the gradient norm in the application of free-AT to CIFAR-10 and CIFAR-100 datasets, indicating that the minimum gradient norm on training data is constantly lower-bounded by $\mathcal{O}(10^{-3})$ in those experiments. We refer the reviewer to Figure 11 in the revised Appendix B.5 for the statistics of the gradient norm evaluation in the experiments.

3- The objective that the free AT method aims to optimize

Re: The free AT algorithm has been originally proposed in [3] to solve the standard min-max formulation of adversarial training problems. The reviewer’s question points to an interesting research direction on the effects of the optimization steps in free AT on the target min-max optimization problem. While this problem sounds an interesting direction to explore on free AT, we think our stability-based generalization analysis is orthogonal to this research direction.

Please note that our main objective is to compare the generalization error of free vs. vanilla AT methods, and to perform a fair comparison we should use the same generalization error metric for both these AT algorithms. According to the standards in the adversarial learning literature, we chose this generalization metric to be the difference between the worst-case training and test error under norm-bounded perturbations. Therefore, to ensure a fair comparison between free and vanilla adversarial training, we have to use the same generalization metric for the analysis of free AT. Any different selection of the generalization metric for free AT would have led to an unfair comparison of the generalization error between the two methods.

[1] Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 2021.

[2] Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training. Advances in Neural Information Processing Systems, 2022.

[3] Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free, Advances in Neural Information Processing Systems, 2019.

We thank Reviewer ge9g for his/her time and feedback. Below is our response to the questions and comments in the review.

1- “What is the definition of $\Delta$?”

Re: As we stated at the beginning of Section 3.1, $\Delta$ is the set of all possible perturbations, which is usually an $L_2$-norm or $L_\infty$-norm bounded ball of some radius $\varepsilon$.

2- “What is the definition of randomized algorithm $A(\cdot)$? What is the definition of $\mathbb{E}_A$? Given $S$, $w=A(S)$ is a random variable or constant?”

Re: As we stated in Section 3, $A$ is a potentially randomized algorithm that takes a dataset $S$ as input and outputs model parameter $w=A(S)$. Since the randomness of $A$ may come from random initialization or random batch selection, $\mathbb{E}_A$ is taking the expectation over such randomness, and $w=A(S)$ will therefore be a random vector.

3- “What's the definition of $S’$ here?”

Re: Following our statement in Definition 1, $S’$ is any dataset that has the same size as $S$ and differs from $S$ in at most one example.

4- “What is the definition of "$A$ is $\epsilon$-uniformly stable"?”

Re: Please refer to Definition 1 for the formal definition of “$\epsilon$-uniformly stable”, which follows from references [1,2].

5- “Unclear definition in Theorem 1?”

Re: We wish the reviewer could be more specific about his/her observed unclarities in Theorem 1. We will be happy to answer any follow-up question on this point.

6- “Where does the randomness of $A_{Vanilla}(S)$ come from?”

Re: In our analysis, both $A_{Vanilla}$ and $A_{Free}$ are stochastic optimization algorithms and the training dataset is also random. So the randomness of $A$ could come from both random initialization and random batch selection.

7- Insights from the theoretical and empirical results.

Re: Free AT is a widely used variant of adversarial training methods due to its higher speed in training the neural net classifier. While the free AT method has been extensively used in several applications, the existing theoretical analysis of adversarial training have not focused on the properties of free AT algorithm. In our work, we focus on the generalization analysis of models learned by the free AT approach, which, to the best of our knowledge, has not been studied in the literature. We show that due to the simultaneous updating nature of free AT, it has significantly better generalization performance compared to vanilla AT in theoretical analysis, and the numerical results are consistent with the theory. Please see our response to the first comment of Reviewer T7Bj for more information about our technical contributions.

[1] Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 2021.

[2] Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training. Advances in Neural Information Processing Systems.

We thank Reviewer iGFe for his/her time and constructive feedback. Below is our response to the questions and comments in the review.

1- Practical implications of the theoretical generalization bounds

Re: In the revised version, we have added a remark after Theorem 4 to discuss the implications of the theoretical bound on Free AT. We note that Theorem 4 suggests how the stepsize parameters for the max and min variables affect the generalization gap of free AT, where by reducing the number of maximization steps $m$ and step size $\alpha_\delta$ one can achieve a lower generalization error.

2- The relationship between generalization gap and training error

Re: We agree with the reviewer that if we continue training the neural networks by applying free AT for more epochs, the training error might further decrease and the generalization gap might be larger. This phenomenon is essentially consistent with the stability analysis – our stability-based generalization bounds consider the number of iterations $T$ as a parameter and grow sublinearly with $T$. To make a fair comparison between free and vanilla AT from the stability perspective, we use the same number of training iterations in our experiments, and we observe a lower generalization gap and sometimes 2%-5% improvement on the robust test accuracy by free AT. Please note that the dependence of the generalization gap on the iteration number $T$ is consistent with the numerical findings of the references (e.g. the discussion in [1]).

3- Improved adversarial training/regularization methods based on the generalization analysis

Re: The simultaneous nature of min-max updates of free AT can be extended to other established robust training methods such as TRADES [2]. Based on this comment, we have performed numerical experiments on the application of a similarly defined ‘‘free’’ version of TRADES (which we call Free-TRADES). The results of our numerical experiments are presented in the revised Appendix B.6. The numerical results indicate that Free-TRADES can similarly gain a better generalization performance using the simultaneous min and max optimization steps. The theoretical analysis of the proposed Free–TRADES will be an interesting future direction to our work, which we have discussed in the revised conclusion section.

[1] Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, 2020.

[2] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, 2019.