Robustness Guarantees for Adversarial Training on Non-Separable Data

We thank the reviewer for pointing our the related references and will incorporate them into the final manuscript.

[W1]

High dimensional settings, wherein $d \gg n$, are common in applications of machine learning; e.g., bioinformatics, computer vision applications involving video/multimedia data, natural language processing, etc. The requirement that $n$ is larger than a constant, i.e., $n > C \log(1/\delta)$ is also very mild. Furthermore, we note that while we limit ourselves to these settings in order to build a theory, in application we may see that our results extend beyond this setting. Also, this paves a path for future work to explore which assumptions are necessary and which are not.

[W2]

We report MNIST in the Appendix due to space limitations. We can switch them if the reviewer prefers that.

[Q1]

In Section 3.1, $C$ depends on various problem parameters including $\gamma, H, c_1,c_2,\zeta$ and $\kappa$.

[Q2]

Yes, this empirical result is in line with our theorem. Higher dimension leads to a lower robust accuracy as per our result, since larger $d$ leads to a larger upper bound on the robust test error.

[Q3] Yes we can simply use $\| \cdot \|$.

[W1, W2]

Regarding technical difficulty and contribution.

Adding the adversarial perturbations requires certain ingenuity for the proofs to go through; they are not straightforward as you can check details from the Appendix. We here point out the contributions

1. We fix mistakes in the proofs In prior work of Frei et al. (2022) and Xu and Gu (2023). Please see discussion in Appendix Section B.1 first paragraph for details on technical improvements over Frei et al. (2022), and Prop. B.12-Lemma B.15 for a more rigorous concentration argument over Xu and Gu (2023).
2. The proof of our convergence guarantee also differs from the original -- our Lemma B.11 has a different proof strategy than Lemma 14 in Frei et al. (2022). Following the previous work to give a result in an adversarial setting leads to a vacuous bound. Please see the beginning of Section 4.2.
3. We establish a robust test error lower bound and explore its relationship with the upper bound, suggesting an almost tight bound under certain conditions. These are interesting findings not present in previous literature.

Regarding the perturbation size.

We disagree with the reviewer's comment that ``intensity $\alpha$ needs to take a very small value". For smooth activation function, the perturbation size can be as large as $\alpha=O(\|\mu\|)$ when $d=\Theta(n\|\mu\|^2)$.

Regarding high dimensionality data in robust setting.

Most ML problems are high dimensional. The ML community has increasingly been interested in theoretically understanding high-dimensional data under robust learning framework; see Shafahi et al. (2019), Mahloujifar et al. (2019), Richardson and Yair (2021), for example.

[W4]

Regarding overfitting discussion.

Nowhere in our discussion do we claim to explain the robust overfitting phenomenon observed in Rice et al. (2020). We simply remark that our results are not in conflict with their findings -- that remark is in no way trying to explain any phenomenon.

Reference:

[1] Frei et al. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, 2022.

[2] Xu and Gu. Benign overfitting of non-smooth neural networks beyond lazy training. International Conference on Artificial Intelligence and Statistics, 2023.

[3] Shafahi et al. "Are adversarial examples inevitable?." In Seventh International Conference on Learning Representations, 2019.

[4] Mahloujifar et al. "The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure."Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.

[5] Richardson and Yair. "A bayes-optimal view on adversarial examples."The Journal of Machine Learning Research 22.1 (2021): 10076-10103.

[6] Rice et al. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, PMLR, 2020.

[7] Wang et al. "Adversarial robustness is at odds with lazy training."Advances in Neural Information Processing Systems, 2022.

Dear Authors,

Thank you for the response. I still have some concerns about this paper:

1: Regarding the perturbation size:

In my understanding, $2\times \mu$ actually describes the separation distance between the 'centers' of two different classes. Therefore, for Section 3.1, the assumption $\alpha \leq 0.99 \mu$ does not represent a very large perturbation size. And, in Section 3.2, $\mu$ is large, and $\alpha \leq C$ represents a very small perturbation size.

2: Regarding any width networks:

Based on assumptions B.3 and B.7, when the network width tends to infinity, both the number of data n and data dimensions d should also tend to infinity for Theorem 3.3 to hold. That is to say, for fixed n and d, Theorem 3.3 does not hold for any width.

3: Regarding "lazy training":

I cannot agree with the author's response: "Our work shows that adversarial training actually returns networks that are outside the lazy regime (see Proposition 3.5) and are guaranteed to generalize adversarially robustly."

The relationship between the training regime of neural networks and their initialization has been studied [1]. A non-lazy training regime is not induced by adversarial training; without adversarial training, neural network training is non-lazy when the network initialization is sufficiently small, some papers with similar settings also demonstrated similar non-lazy training results without using AT [2]. In fact, there have been experiments indicating that adversarial training becomes 'lazy' earlier than standard training in a lazy training regime [3].

4: Regarding my raised question:

I think the authors did not provide a satisfactory answer. Directly setting $\alpha = 0$ (in training but remaining in robust loss) in the Thm 3.1 and Thm 3.3 would result in the degradation of the results to simple gradient descent. And, the bounds for Theorems 3.1 and 3.3 in this paper are optimal at $\alpha = 0$ (Because the $\alpha$ in robust loss only affects the last $\alpha$ that appears in the Thm 3.1). This implies that under the settings of this paper, a good robust loss can be attained using gradient descent without adversarial training (and potentially even better than adversarial training). This seems contradictory to the motivation of this paper.

Thank you,

Reviewer GnZf

Reference:

[1] Tao Luo, et al. Phase diagram for two-layer relu neural networks at infinite-width limit. JMLR, 2021.

[2] Spencer Frei, et al. Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data. COLT 2022.

[3] Nikolaos Tsilivis, et al. What Can the Neural Tangent Kernel Tell Us About Adversarial Robustness? NeurIPS 2022.

Thank you for the discussion.

Regarding the perturbation size and networks of any width:

Below we discuss smooth activation function and non-smooth activation function separately. Please remember that the analysis for non-smooth activation function is more challenging.

For smooth activation functions:

1. The best achievable condition is $\alpha \leq 0.99||\mu||$; $\alpha > ||\mu||$ results in a robust test error of at least $0.5$ (refer to Theorem 3.4). This is not surprising because even for linearly separable data, if the margin is $\mu$ and class conditionals (i.e., $p(x|y)$) are supported on (marginal) hyper-planes, i.e., at a distance of $\mu$ from each other, then a perturbation of more than $\mu$ will result in error of $0.5.$

2. We do not require any assumptions on width for this part.

For non-smooth activation functions:

1. First of, we do discuss in paper how we can relax this assumption also to $\alpha\leq 0.99\|\mu\|$ if we select a data-dependent initialization. See Remark 4.4 and Remark B.16. But, note that in literature, we are most concerned about settings where the adversarial perturbations are so small, that they are nearly imperceptible. This is why we consider $\alpha\leq \sqrt{n/d}||\mu||$ (or $\alpha\leq$ constant) which is reasonable in high-dimensional setting. Again, existing literature, e.g., [1,2,3], focuses on understanding the robustness guarantees with perturbation of size $O(||x||/\sqrt{d})$.

2. We note that what we mean when we say that ``our results hold for networks of any width'' is that we do not require any strong assumptions (e.g., extreme overparametrization) on the network. This is standard usage to characterize results of this type and very typical in nearly all papers in theory of deep learning. We only require very mild assumptions on width, specifically $\Omega(\log(n/\delta)) \leq m \leq O(\exp(n)\delta)$. These requirements are also found in [4].

[1] Bartlett et al. "Adversarial examples in multi-layer random relu networks."Advances in Neural Information Processing Systems 34 (2021): 9241-9252.

[2] Montanari and Wu. "Adversarial examples in random neural networks with general activations." Mathematical Statistics and Learning 6.1 (2023): 143-200.

[3] Wang et al. "Adversarial robustness is at odds with lazy training."Advances in Neural Information Processing Systems, 2022.

[4] Xu and Gu. Benign overfitting of non-smooth neural networks beyond lazy training. International Conference on Artificial Intelligence and Statistics, 2023.

Regarding "lazy training":

Nowhere in our paper or in our response, do we claim that a non-lazy regime is ONLY induced by adversarial training. All we are saying is that our analysis shows that for the setting we consider, adversarial training returns networks that are outside the lazy regime and, therefore, our results are not in contradiction with previous results that suggest that lazy regime is at odds with robustness. We feel that our comment was twisted badly here for the sake of a baseless argument. In any case, our result does not contradict with [1], and we are happy to include [1] in our related work discussion.

[1] Tao Luo, et al. Phase diagram for two-layer relu neural networks at infinite-width limit. JMLR, 2021.

Regarding the question.

If $\alpha=0$, the L.H.S. of the bound is no longer robust loss.

Regardless, we agree that there exist a similar form (albeit with different constants in the bound) of robust generalization guarantees for neural network trained non-adversarially with gradient descent. We want to point out that this observation doesn't contradict the motivation of our work. We would like to emphasize again that our results serve as the first step towards understanding the adversarial trained neural network without linearly separable assumption and beyond lazy training regime.

Dear Reviewer GnZf:

1. Regarding $\alpha=0$: your claim was blatantly wrong. It was not ambiguous. You have since changed the question to something that has nothing to do with the paper. We have already said that GD would also have similar robustness guarantees. So, entertaining your question further makes no sense but to engage in this meaningless back-and-forth, which has no constructive outcome. We are not being evasive here. You are not willing to see the reason.

2. Regarding Lemma 4.3: What we have said before about Lemma 4.3 is that it is possible to give an analogue of it for GD but with different constants. This is exactly what you say here. What is it about what we said that is not true? You seem to be in an alternate reality where you repeatedly think we are saying something we are not.

3. Regarding lazy training. For the nth time, the prior work shows that networks trained in a lazy regime are not robust. We show that adversarial training in our setting yields networks that are outside the lazy regime. Nowhere in the paper or our response, even the ones you copied here, say anything you claim we say. Again, you are twisting the reality to suit your needs. Nobody is being misled by these statements. You are simply not willing to listen to reason.

4. Regarding reference [2]. Benign overfitting in a lazy regime has nothing to do with adversarial training or robustness. You are trying to make connections that are tangential at best and definitely outside the scope of the paper.

5. Regarding our data distribution being linearly separable, you are flat-out wrong again here. Not only can our class conditionals, i.e., p(x|y), overlap, but we also have non-zero probability $\beta > 0$ of flipping the labels.

6. Regarding the width. Again, as we said before, for smooth activation functions, we make NO assumption on width. For non-smooth activation functions, we do make a mild assumption on width $m$ of the network; we assume that $\Omega(\log(n/\delta)) < m < O(\exp(n) \delta)$. We argue that this essentially means that our results hold for networks of any width. This is standard usage in literature as many theoretical results require the networks to be sufficiently over-parametrized. You have an issue with our phrasing that our "results hold for a network of any width’’— this is such a minutia; is it really such a big deal?

7. We have already addressed the issue of novel technical contributions, including making the reviewer aware that Lemma 4.1 and Lemma 4.11 in the prior work of Spencer Frei et al. are broken. We provide alternate arguments to give guarantees, and they are sound and rigorous.

Thanks for clarifying your stand. None of the reasons you list above are central to the results or technical contributions we make in the paper. You are focusing on minutiae like "Does this result really hold for a network of any width?’’ or ``is this a comment on training in a lazy regime more generally?’’ Even if these were genuine concerns, none of this can be a basis for rejection. None of your comments justify the low rating.

Best, Authors

Dear Authors,

Firstly, I'd like to clarify my previous responses.

1. $\alpha$:

I have corrected the possible ambiguities in my previous responses. I think I was clear in my previous response regarding the origin of $\alpha$ in the results. The author seems to be evading this issue.

2. Lemma 4.3:

The proof of the lemma relies on Lemma 4.9 in [1], differing only by constants. Moreover, Lemma 4.9 in [1] itself is a non-adversarial version of this setting. So the author’s previous statement about Lemma 4.3 is actually not true.

3. Lazy training:

My concern lies in this excerpt: "Furthermore, the convergence and generalization guarantees for overparametrized networks in the lazy regime or the Neural Tangent Kernel (NTK) regime (which is the dominant framework in theoretical deep learning), do not extend to the adversarial setting. The work of Wang et al. (2022) shows that networks trained in this regime are not robust. Our work shows that adversarial training actually returns networks that are outside the lazy regime (see Proposition 3.5) and are guaranteed to generalize adversarially robustly."

And this recent response: "Our work shows that adversarial training actually returns networks that are outside the lazy regime (see Proposition 3.5) and are guaranteed to generalize adversarially robustly.’’

Both statements attempt to establish a connection between adversarial training and the non-lazy regime but overlook the crucial influence of initialization in the lazy/non-lazy regime. This might mislead readers. In fact, under the settings of this paper, whether adversarial training is used or not, it will fall into the non-lazy regime. However, this is more of a formulation issue than a core concern of the paper.

4. Relation between [2] and this paper:

Both this paper and Section 3 in [2] primarily draw from [1] for their data distributions. The difference lies in initialization, resulting in different training regimes. Their proof strategies are similar (follow [1]). The authors attempt to refute Assumption 6 in [2]. But Assumption 6 applies only to Section 4 in [2]. It does not affect any of the results in Section 3 in [2].

5: "The perturbation size":

The author reiterated the results from the paper: for this issue, smooth activations need perturbations smaller than the distance from the data center to the boundary, while non-smooth activations need perturbations significantly smaller than this distance. I believe further discussion on whether these values are large or small is meaningless. In fact, the data distribution in this paper is considered 'linearly separable' in many references [3][4].

6: "The width of the network":

The author's response stated, "We do not require any strong assumptions (e.g., extreme over parametrization) on the network," which significantly differs from the original statement: "Our results hold for networks of any width."

7: "The technical difficulty and contribution":

I previously raised the issue: "even neglecting almost all adversarial directions and directly using random perturbations," and the author seems not to have responded to this.

As a reviewer, I aimed to discuss and enhance the paper with the author. However, the author's responses seem to diverge from this, so I feel further discussion would be futile. Given the author's evasiveness regarding some crucial issues, I will maintain my score.

Reviewer GnZf

Reference:

[1] Spencer Frei, et al. Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data. COLT 2022.

[2] Zhenyu Zhu, et al. Benign Overfitting in Deep Neural Networks under Lazy Training. ICML, 2023.

[3] Zhiwei Xu, et al. Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data. arXiv:2310.02541.

[4] Xuran Meng, et al. Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data. arXiv:2310.01975.

In Section 3.1, the additional assumption approximates the homogeneous property, which is used for proving the convergence guarantee. This almost homogeneous property is not very important, because it is only used to prove the bound on training error (not test error). From this assumption we showed that if the smooth loss function is close to ReLU or leaky ReLU, we can have a small training error.

Another example of almost homogeneous function:

$

\phi(x)= \begin{cases} x &x \leq 1,\newline \sqrt{2x-1} &x>1. \end{cases}

$

We are not assuming $c_1=c_2=0$ for ReLU. The approximate homogeneous property holds trivially for ReLU.