Stability and Generalization of Adversarial Training for Shallow Neural Networks with Smooth Activation

W1: Regarding $m\geq \eta^2 T^2$

Reviewer has a correct understanding of why stability holds, i.e., the change of the weights when doing GD is very small compared to the number of neurons. We utilize the weakly convex robust loss (see Lemma 4.1) as well as $m\geq O(\eta^2 T^2)$ to establish stability.(see Theoorem 4.3)

Note that training neural networks (i.e., implementing the ERM rule) is known to be computationally hard, even for a two layer network with only three hidden nodes. This has been known since the early 90s. Recent results in deep learning theory focus on two-layer neural networks that are greatly overparameterized ($m$ is large) and involve a certain scale of initialization. Under these settings, we can bound the training error of GD after T iterations by $1/\sqrt{T}$. This is the state-of-the-art results in computational theory of deep learning.

Now, the important point we want to make here is that the key to the analysis is ensuring that the weights of the trained network do not change by much from initialization. One can then show that training neural networks is similar to dynamics of kernel methods. This is the dominant framework for computational learning theoretical guarantees for training neural networks and is aptly called the “lazy regime” or the “neural tangent kernel” (NTK) setting.

The early works that laid the foundations for this theory are [r1, r2, r3].

W2: Regarding $\alpha_1(\eta,T)<1$

Yes, for that result of ours to make sense we do need $\alpha_1(\eta,T) < 1$. However, we can also give a result that is of the same form as the expression in equation (4) of [r4] and get a factor of $C\alpha_1(\eta,T)\cdot (1+\alpha_1(\eta,T))$ instead of $C\frac{\alpha_1(\eta,T)}{1-\alpha_1(\eta,T)}$. In that case we don’t need $\alpha_1(\eta,T) < 1$.

W3: Regarding $\frac{1}{1-\alpha_1}<1.1$

It is possible that the reviewer did not realize $\eta=O(\frac{1}{\sqrt{T}})$.

In order to get $\frac{1}{1-\alpha_1}<1.1$, we need $\alpha_1$ to be a small positive real number, and equivalently, $\eta\sqrt{T}$, $\frac{\eta T}{n}$ and $\sqrt{\beta_1\eta T}$ are small positive real numbers (through the definition of $\alpha_1$). Note that we have selected $\eta=c_0\frac{1}{\sqrt{T}}$ in Corollary 3.3, plugging in $\eta$, we equivalently require $c_0$, $c_0\frac{\sqrt{T}}{n}$ and $c_0\beta_1\sqrt{T}$ to be small positive real numbers. In Corollary 3.3, we assumed $T\leq O(n^2)$ and $T\leq O(1/\beta_1^2)$, so we can choose $c_0$ to be a proper (small) positive constant so that the three inequalities hold.

W4: Regarding line 509

The definition of the generalization gap is the test loss minus the training loss \epsilon_{gen}=L_{rob}(W_t)-$$\hat{L}_{rob}(W_t;S)

so we can get line 509 by subtracting $E_{S\sim\mathcal{D}^{n}}\hat{L}_{rob}(W_t;S)$ on both sides of Eq (4), so the left hand side will have the generalization gap.

Q1: Given $\epsilon>0$, how should we set the parameters of the problem to get generalization error and robust accuracy smaller than $\epsilon$?

The relationship is a bit involved since our bounds are post-hoc and not a-priori. In other words, our bound is instance specific, and depends on the given training data and the output of the algorithm. This is in stark contrast to bounds that are based on uniform convergence and hold simultaneously for all hypotheses in the class – there you can ask how many samples or iterations you need to ensure suboptimality. However, note that uniform convergence bounds can be overly pessimistic/vacuous. Anyhow, even though there is not a simple answer, below we try to give an intuitive understanding.

Let’s say you want to bound the expected robust test loss by $(1+\epsilon)$ times the expected training loss (see Lemma 4.2 relating the two quantities). Then, To ensure $\frac{1}{1-C_x\cdot \alpha_1}\leq 1+\epsilon$, we need $\alpha_1\leq\frac{\epsilon}{C_x(1+\epsilon)}=O(\epsilon)$. We can give two possible ways of setting the different parameters to ensure that $\alpha_1 = O(\epsilon)$.

Recall that $\alpha_1=O(\eta\sqrt{T}+\frac{\eta T}{n}+\sqrt{\beta_1\eta T})$.

Set $\beta_1 = O(\epsilon^2)$, $n=\Theta(1/\epsilon)$, $T=\Theta(1/\epsilon^2)$, $\eta=O(\frac{1}{T})$,

or set $\beta_1 = O(\epsilon^3)$, $n=\Theta(1/\epsilon^2)$, $T=\Theta(1/\epsilon^4)$, $\eta=O(\frac{\epsilon}{\sqrt{T}})$.

Check that $\eta\sqrt{T}=O(\epsilon)$, $\frac{\eta T}{n}=O(\epsilon)$ and $\sqrt{\beta_1\eta T}=O(\epsilon)$.

Q2: What happens when m is chosen independently of T

We can choose $m \geq \Theta(n^2)$, and then set $\eta T\leq O(n)$. Note though that it seems superfluous as there could be other regimes that could still give us the condition we need. This is why prior works (e.g., [r4, r5]) also state the assumption as we do.

This also makes sense as our generalization bounds are based on algorithmic stability which depends on parameters $\eta$ and $T$. If we were using tools from uniform convergence, then m would naturally depend on the sample size and input dimension d.

[r1] Du, Simon S., et al. "Gradient descent provably optimizes over-parameterized neural networks." arXiv preprint arXiv:1810.02054 (2018).

[r2] Arora, Sanjeev, et al. "Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks." International Conference on Machine Learning. PMLR, 2019.

[r3] Ji, Ziwei, et al. "Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks." arXiv preprint arXiv:1909.12292 (2019).

[r4] Richards, Dominic, et al. "Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel." Advances in neural information processing systems 34 (2021): 8609-8621.

[r5] Lei, Yunwen, et al. "Stability and generalization analysis of gradient methods for shallow neural networks." Advances in Neural Information Processing Systems 35 (2022): 38557-38570.

I thank the authors for their response.

Other reviewers (including myself) found it strange that the overparameterization depends on the learning rate and number of iterations. However, after reading the author's response I agree that this dependence is indeed the right one for stability analysis of generalization bounds, contrary to uniform convergence analysis.

To conclude, my questions are answered, and I will raise my score to 7. I think the authors should add in the final version several clarifications that were raised from the reviewer's question. I also think it would strengthen the paper to include the proof for \alpha_1 > 1.

W1: The bounds are in expectation and not high probability bounds.

We can give high probability bounds based on [r1], which relates high probability generalization bounds with algorithmic stability, but they are looser than the bounds in expectation. We had those originally in the paper but chose to remove them as they are not very informative.

W2: A large width is required for the bounds to hold.

Training neural networks (i.e., implementing the ERM rule) is known to be computationally hard, even for a two layer network with only three hidden nodes. This has been known since the 90s. Recent results in deep learning theory focus on the setting where networks are greatly overparameterized. Indeed, all results giving computational guarantees for learning deep neural networks assume that the networks are overparameterized. So, it is not surprising that we need a similar condition in the adversarially robust setting. The assumption on width, $m\geq \eta^2 T^2$, has also appeared in related prior works [r2] and [r3].

Also, note that the way we present the results, we can also rewrite the condition above as $\eta T \leq O(\sqrt{m})$ and interpret it as early stopping .

W3: The $\beta_1$ parameter is set in the worst-case, and as a result for practical attack algorithms is likely to be high. In fact, if $\beta_1>0$ is constant, then it appears Corollary 3.3 is vacuous.

[TLDR] $\beta_1$ is not a constant, it is a parameter you can choose. You can make it arbitrarily small by adding more computation. Large $\beta_1$ means that the quality of simulated adversarial attacks is poor, so indeed our bounds suggest that the robust generalization will not be good. This is what should be expected, it is not a weakness of our result.

Recall that adversarial training involves finding an adversarial perturbation of every training example in the training set. Can we solve this optimization problem exactly? If so, then $\beta_1$ is equal to zero. Most works in theory of robust learning assume that. We argue that in practice that is not true. So, we allow for approximate optimization for finding an adversarial example during training. We introduce a parameter $\beta_1$ that is bound on the suboptimality of an adversarial example. Note that this is a design parameter that a practitioner can choose. If you choose a large $\beta_1$, the training is easier but the resulting model is not good. So, of course, one should choose a small $\beta_1$. This involves a computational cost that most previous papers ignore. The only paper that carefully shows how many iterations are needed to find a $\beta_1$ suboptimal attack is that of Mianjy and Arora (2023) – they show that we need $1/\beta_1^2$ iterations of PGD attack to find a $\beta_1$ suboptimal attack.

[Mianjy and Arora, 2023] “Robustness Guarantees for Adversarially Trained Neural Networks,” NeurIPS 2023.

Q1: How realistic is the assumption that there exists a robust network in the vicinity of the initialization?

[TLDR] Existence of a network that generalizes well in the vicinity of a certain way of initialization is a high dimensional phenomenon that is central to the NTK setting, a dominant framework for computational learning theory of deep neural networks. Nonetheless, our results also yield guarantees that do not depend on the distance from initialization.

Most computational learning results for deep neural networks assume overparametrization and a certain initialization that ensures that the weights of the trained network do not change by much from initialization. Yet, these trained networks in the so-called lazy regime or the NTK setting, are guaranteed to generalize. So, assuming the existence of a network that generalizes well in the vicinity of initialization (chosen at the right scale) is a high dimensional phenomenon. We argue that if the conditions of our theorems are met (i.e., we consider over-parametrized settings), then such an assumption is not unrealistic. It is same as saying “how realistic is it that a unit ball has almost no volume and all of its mass is concentrated near the boundary.” Well it happens in high dimensions.

While we give a bound on robust generalization in terms of distance from initialization, it does not mean that it is a necessary and the only condition for robust generalization. In fact, we can also give a robust generalization bound that does not depend on the distance from initialization. This follows using Theorem 3.1 and Lemma 4.2.

Q2: Should I be thinking of $\beta_1$ as a constant? If so, how should Corollary 3.3 be interpreted?

No, $\beta_1$ should not be treated as constant, it is a design parameter you can choose. Please see a detailed discussion above.

[r1] Feldman, Vitaly, and Jan Vondrak. "High probability generalization bounds for uniformly stable algorithms with nearly optimal rate." Conference on Learning Theory. PMLR, 2019.

[r2] Richards, Dominic, and Ilja Kuzborskij. "Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel." Advances in neural information processing systems 34 (2021): 8609-8621.

[r3] Lei, Yunwen, Rong Jin, and Yiming Ying. "Stability and generalization analysis of gradient methods for shallow neural networks." Advances in Neural Information Processing Systems 35 (2022): 38557-38570.

W1: The model studied in this work is a special neural network. By fixing the weights of last layer, it has only one layer of trainable parameters, it is unclear if the results shown in this special neural network can be generalized to regular neural netowrk.

It is known since the early 90s that training neural networks is computationally hard, even for two layer networks with three hidden neurons. Modern theory of deep learning avoids those hardness results by considering (a) overparameterized two layer-networks, (b) a certain small-scale randomized initialization, and (c) freezing the top layer and training only the bottom layer. Under this setting, we can bound the training error of GD after T iterations by $1/\sqrt{T}$. This is the state-of-the-art results in computational theory of deep learning. Yes, it may be too specialized and not close to practice, but this is all we have currently. So, even in the standard setting, it remains unclear if these results can be generalized to “regular” networks.

W2: The authors claim that they use a over-parameterized neural network, while they explian "over-parameterized" as $m\geq O(\eta T)$. It is confused that $m$ depends on $\eta$ and $T$ but not depends on the number and dimention of inputs.

We state $m$ in terms of $T$ and the learning rate \eta as our generalization bounds are based on algorithmic stability which depends on those algorithmic parameters. Similar assumptions have also appeared in related prior works [r1] and [r2]. If we were using tools from uniform convergence, then m would naturally depend on the sample size and input dimension $d$. Note that we could still write the condition $m \geq O(\eta^2 T^2)$ as $m \geq \Theta(n^2)$ and $\eta T = O(n)$, but that would seem superfluous as there could be other regimes that could still give us the condition we need.

[r1] Richards, Dominic, and Ilja Kuzborskij. "Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel." Advances in neural information processing systems 34 (2021): 8609-8621.

[r2] Lei, Yunwen, Rong Jin, and Yiming Ying. "Stability and generalization analysis of gradient methods for shallow neural networks." Advances in Neural Information Processing Systems 35 (2022): 38557-38570.

W3: In section 4, the bound shown in theoretical results depend on $m$ with a same order. I check the proof of this work, and find that these bounds depend on $m$ since the weights of last layer is initilized from $\\{\frac{1}{\sqrt{m}},-\frac{1}{\sqrt{m}}\\}$, which means that the bounds depends on the initilization of weights of last layer. If the last layer is initilized from other parameters, especially, initilized from $\\{{\sqrt{m}},-{\sqrt{m}}\\}$, does the reult still hold for over-parameterized neural network?

No. The scale of the initialization is important. As we state above, this is the case with the dominant framework for a computational theory of deep learning even in the standard setting. Such initialization has also appeared in prior works, e.g., [r3, r4, r5]. In particular, we need the initialization to be at that scale for our Lemma 4.1 to hold.

[r3] Du, Simon S., et al. "Gradient descent provably optimizes over-parameterized neural networks." arXiv preprint arXiv:1810.02054 (2018).

[r4] Arora, Sanjeev, et al. "Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks." International Conference on Machine Learning. PMLR, 2019.

[r5] Ji, Ziwei, and Matus Telgarsky. "Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks." arXiv preprint arXiv:1909.12292 (2019).

W4: The main techniques used in proofs depend on the weakly convex property of function, and uniform stability of algorithm. It is suggested to show the formal definition of weakly convex function.

We will include a formal definition of weakly convex functions.

Q1: Is this possible to generalize the results from special neural network to regular neural network with mild assumptions like the Theorem 4.7 in [1]?

We are not sure what is reference [1], but see our response above regarding the state-of-affairs with computational learning theoretic results for training neural networks.

W1: Detached from practice?

Our is a theoretical result and theory always lags practice and rarely matches the practice perfectly. Having said that, we would like to remind the reviewer that it is known since the early 90s that training neural networks is computationally hard, even for two layer networks with three hidden neurons. Modern theory of deep learning avoids those hardness results by considering (a) overparameterized two layer-networks, (b) a certain small-scale randomized initialization, and (c) freezing the top layer and training only the bottom layer. Under this setting, we can bound the training error of GD after T iterations by $1/\sqrt{T}$. This is the state-of-the-art results in computational theory of deep learning. It is indeed too specialized and not close to practice, but this is all we have currently.

W2: Feasibility of adversarial training with the smoothed loss.

Yes, it is very feasible and practical and has shown to be successful in prior work. [Xiao 2024] discuss at length the feasibility of adversarial training with smoothed loss and present extensive empirical results.

[Xiao 2024] "Uniformly Stable Algorithms for Adversarial Training and Beyond." arXiv preprint arXiv:2405.01817 (2024).

W3: How to think about $\beta_1$?

We should not think of $\beta_1$ as a constant. It is a parameter that you as an algorithm designer can choose. You can make it arbitrarily small by adding more computation. Large $\beta_1$ means that the quality of simulated adversarial attacks is poor, so indeed our bounds suggest that the robust generalization will not be good. This is what should be expected, it is not a weakness of our result. We further expand on our comment above. Recall that adversarial training involves finding an adversarial perturbation of every training example in the training set. Can we solve this optimization problem exactly? If so, then $\beta_1$ is equal to zero. Most works in theory of robust learning assume that. We argue that in practice that is not true. So, we allow for approximate optimization for finding an adversarial example during training. We introduce a parameter $\beta_1$ that is bound on the suboptimality of an adversarial example. Note that this is a design parameter that a practitioner can choose. If you choose a large beta, the training is easier but the resulting model is not good. So, of course, one should choose a small beta. This involves a computational cost that most previous papers ignore. The only paper that carefully shows how many iterations are needed to find a $\beta_1$ suboptimal attack is that of Mianjy and Arora (2023) – they show that we need $1/\beta_1^2$ iterations of PGD attack to find a $\beta_1$ suboptimal attack.

[Mianjy and Arora 2023] “Robustness Guarantees for Adversarially Trained Neural Networks,” NeurIPS 2023.

Q1: Lines 9 and 10 in the abstract: If I understand correctly, there should be something added along the lines of “provided there exists a robust network around the initialization.”

While we give a bound on robust generalization in terms of distance from initialization, it does not mean that it is a necessary and the only condition for robust generalization. In fact, we can also give a robust generalization bound that does not depend on the distance from initialization. This follows using Theorem 3.1 and Lemma 4.2.

Q2: Lines 193-194, “This view is also consistent with several empirical studies.”: can you please elaborate on this?

Early stopping is a standard approach for algorithmic regularization. It has been shown to prevent overfitting in many settings, see for example [r1, r2, r3]. Here, we show that it is able to mitigate robust overfitting as well.

[r1] ​​Caruana, Rich, Steve Lawrence, and C. Giles. "Overfitting in neural nets: Backpropagation, conjugate gradient, and early stopping." Advances in neural information processing systems 13 (2000).

[r2] Rice, Leslie, Eric Wong, and Zico Kolter. "Overfitting in adversarially robust deep learning." International conference on machine learning. PMLR, 2020.

[r3] Pang, Tianyu, et al. "Bag of tricks for adversarial training." arXiv preprint arXiv:2010.00467 (2020).

Q3: Theorem 3.2, for the result on the generalization gap you should explicitly state the loss function, right? (since eq. (3) is defined with respect to a generic function $f$).

Yes. We will state the loss function explicitly.