Gradient Flow Provably Learns Robust Classifiers for Data from Orthonormal Clusters

We thank the reviewer for the review and for acknowledging the strengths of our paper. We address your concerns below:

1. Is the data assumption reasonable: We have added a new experiment section addressing your concern about the practical relevance. We refer the reviewer to our revised Appendix A and our global response.

2. Bayes classifier v.s. $F^{(p)}$ classifier: We have shown Bayes classifier is nearly optimally robust and explained it by interpreting it as a nearest-cluster rule. When Min and Vidal, 2024 propose $F^{(p)}$ classifier, they did not state whether its $\sqrt{2}/2$ robustness is optimal or not. The reviewer's question of why $F^{(p)}$ classifier is also optimally robust is valid, and we have some explanation: the $F^{(p)}$ classifier is also approximately a nearest-cluster rule when $p$ is large. To see this, notice that $sign(F^{(p)})=sign(\sum_{k=1}^{K_1}\sigma^p(\left\langle x,\mu_k\right\rangle)- \sum_{k=K_1+1}^{K}\sigma^p(\left\langle x,\mu_k\right\rangle))$ $=sign((\sum_{k=1}^{K_1}\sigma^p(\left\langle x,\mu_k\right\rangle))^{\frac{1}{p}}-(\sum_{k=K_1+1}^{K}\sigma^p(\left\langle x,\mu_k\right\rangle))^{\frac{1}{p}})$ $\approx sign(\max_{1\leq k\leq K_1}(\sigma(\left\langle x,\mu_k\right\rangle)-\max_{K_1+1\leq k\leq K}(\sigma(\left\langle x,\mu_k\right\rangle))$ because the $p$-norm is getting closer to $\infty$-norm as $p$ increases.

We hope our response addresses your concerns. If you have additional questions/concerns, please feel free to post comments during the discussion phase.

References:

Min and Vidal, Can implicit bias imply adversarial robustness? ICML, 2024

We thank the reviewer for the review. We address your concerns below:

1. Orthonormal cluster data: We have added a new experiment section addressing your concern about practical relevance. We refer the reviewer to our revised Appendix A and our global response.

2. Notation in Theorem 1 and 2: Thank you. We have fixed the notion in Theorem 1 and 2.

3. What happens if one uses ReLU: First of all, we wrote footnote 1 only to justify the use of gradient flow: If we are to study ReLU networks, then we have to write equation (7) as the differential inclusion (and the reviewer is right that many analyses exist), which is unnecessary in our manuscript since our main results are about pReLU (p>2). Secondly, the results for ReLU (the case when p=1) have been shown in prior works, and we mentioned them in multiple sections (lines 97-107, and lines 384-395): Frei et al. 2023 showed that GF on two-layer ReLU networks provably converges to networks that are non-robust against adversarial attacks of radius $\mathcal{O}(1/\sqrt{K})$ and Min and Vidal, 2024 further explained this phenomenon.

4. upper bound on the amount of data: The upper bound on sample size $N$ is due to the current proof techniques used in this paper, and we have discussed this limitation in lines 517-527. We invite the reviewer to read lines 517-527; if they do not clarify, please feel free to ask further questions.

5. what $\theta(t)$ represents: Since this paper considers the gradient flow dynamics, the continuous-time limit of gradient descent when the step size is infinitesimal, $\theta(t)$ represents the solution to the ordinary differential equation in (7), and $t\in[0,\infty)$ denote the time. Nonetheless, there is some connection between the gradient flow solution $\theta(t)$ with the iterates from gradient descent with sufficiently small step size, for which we refer the reviewer to Elkabetz and Cohen, 2021.

6. robustness without adversarial training: This is the point we highlight in our manuscript: the correct choice of network architecture matters in determining the adversarial robustness of the trained network. For this mixture of Gaussian data, we show that, as long as the activation function is chosen carefully (pReLU, p>2), the gradient flow training without adversarial examples can find the optimal robust classifier; Notice that in our Figure 2., if the network is NOT chosen carefully, the trained network is not robust, reminiscent of what reviewer pointed out, "normal training makes the network non-robust".

We hope our response addresses your concerns. If you have additional questions/concerns, please feel free to post comments during the discussion phase.

References:

Min and Vidal, Can implicit bias imply adversarial robustness? ICML, 2024

Frei et al., The double-edged sword of implicit bias: Generalization vs. robustness in reLU networks. NeurIPS, 2023

Elkabetz and Cohen, Continuous vs. discrete optimization of deep neural networks. NeurIPS, 2021

We thank the reviewer for the review. We address your concerns below:

1. Non-degeneracy gap assumption: The reviewer is right that the non-degeneracy gap is very small under random initialization when dimension $D$ is large, which we also acknowledged in our remark Requirement on the initialization in lines 506-516 as one limitation of our current results. In that remark, we noted that the required non-degeneracy gap of $\Theta(1)$ generally cannot be achieved by random initialization. However, this does not imply that GF cannot converge to a robust classifier from random initialization. From a random initialization, the GF dynamics should be split into three phases ("burn-in" phase -> alignment phase -> convergence phase). The "burn-in" phase is the initial chaotic phase when each neuron moves towards the interior of one of the Voronoi regions (since each neuron is initialized close to the boundaries of these Voronoi regions, we have no control over which Voronoi region it "selects" as it highly depends on the sampled training data points). Once every neuron has reached the interior of one of the Voronoi regions with a non-degeneracy gap $\Theta(1)$, our results apply afterward. We hope the reviewer can see the challenges in analyzing this "burn-in" phase, which we plan to tackle in future research. We also note that special but practically viable initializations, such as initializing each neuron as one of the training data points, satisfy our non-degeneracy gap assumption, which might be a good alternative to random initialization.

2. Dependence on variance $\alpha^2$: In our response, we will first point out that the dependence on $\alpha$ is also empirically observed in Min and Vidal, 2024. Then, we will discuss our view on such dependence.

• In Figure 2(a) of Min and Vidal, 2024, they plot the distance between the trained network and $F^{(p)}$ against different choices of $\alpha$, and the distance increases as $\alpha$ increases. Therefore, empirical results have shown the dependence on $\alpha$, and our results agree with such observations.

• Why does the distance have to depend on $\alpha$? Our explanation is as follows: To make sure the trained network $f$ is close to $F^{(p)}$, one requires each neuron $w_j$ to be aligned with one of the cluster centers $\mu_k$, and any misalignment $\cos(w_j,\mu_k)$ will be reflected in the distance between $f$ and $F^{(p)}$. However, since the training data only contains noisy samples around cluster centers, the GF dynamics can only guide the neurons' directions within a neighborhood of the true cluster center, and the size of this neighborhood necessarily depends on the variance. Indeed, in our proof sketch for the alignment phase (line 445-476), we show that the misalignment $\cos(w_j,\mu_k)$ is $\mathcal{O}(\alpha^2)$, which eventually gets into our upper bound on the distance between $f$ and $F^{p}$.

3. Empirical validation: In Min and Vidal, 2024, the authors had the conjecture that pReLU networks converge to the robust classifier $F^{p}$ and offered empirical validations on synthetic data (mixture of Gaussian data) and on real image dataset (MNIST). We feel their numerical validations are sufficient to show the effectiveness of pReLU in finding robust classifiers. Thus, we focus on formally proving their conjecture with a detailed proof sketch and technical discussion. Nonetheless, to address the practical relevance of our theorems, we added numerical experiments to our revised manuscript; we invite the reviewer to check the new Appendix A and our global response.

We hope our response addresses your concerns. If you have additional questions/concerns, please feel free to post comments during the discussion phase.

References:

Min and Vidal, Can implicit bias imply adversarial robustness? ICML, 2024

We respectfully disagree reviewer's assessment of our manuscript:

1. Data assumption: Our data assumption is not restrictive when compared to other theoretical works using similar analyses. We have compared our data assumption in lines 397-409 to those in prior work that also studied the convergence of two-layer networks; ours is the least restrictive. Moreover, our theoretical results can characterize exactly what classifier the two-layer network learns via gradient flow, which cannot be done without some assumption, either on data or the network width. Having said this, we are working on relaxing these assumptions.

2. Relevance in real-world scenarios: We have added a new experiment section addressing your concern about practical relevance. We refer the reviewer to our revised Appendix A and our global response.

3. Why ReLU fails to be robust: The results for ReLU (the case when p=1) have been shown in prior works, and we mentioned them in multiple sections (lines 97-107 and lines 384-395): Frei et al. 2023 showed that GF on two-layer ReLU networks provably converges to networks that are non-robust against adversarial attacks of radius $\mathcal{O}(1/\sqrt{K})$ and Min and Vidal, 2024 further explained this phenomenon.

4. Accuracy-robustness tradeoff: We have clearly stated what is considered to be robust classifiers in our paper in lines 142-149: those that can defend against attacks of radius $r$ while maintaining a robust accuracy almost as high as the clean accuracy, which has no accuracy-robustness trade-off against attacks of radius smaller than $r$. Our contribution is to show that robust classifiers in such a strong sense exist for our orthonormal cluster model with $r\approx \frac{\sqrt{2}}{2}$ and can be found by the gradient flow. Moreover, our results still agree with the empirical observation that the accuracy-robustness tradeoff exists: the robust classifier we find can achieve high accuracy under any attack of radius smaller than $\sqrt{2}/2$, but has near zero accuracy under attacks of radius larger than $\sqrt{2}/2$, as shown in Figure 2. In order to achieve more robustness against an attack of radius larger than $\sqrt{2}/2$, one must trade off the clean accuracy, for example, by using a constant classifier that always outputs the majority class. The same thing can be said for real datasets: robust classifiers in our strong sense exist for some unknown $r^*$ that might be small, and in practice, the algorithm might be looking for robust networks against attacks of radius much larger than $r^*$, which necessarily has the accuracy-robustness tradeoff.

5. Obvious claims The reviewer is misinterpreting our theorems.

For example, we don't need a mathematical analysis to figure out the reason behind the fact that attacks with unlimited budget are not defendable

Our theorem 1 does not assume an unlimited budget. For our orthonormal clusters model, we are showing the critical attack budget $\sqrt{2}/2$: if the attack radius is smaller than this critical value, a robust classifier achieving high accuracy exists; and if the attack radius is larger, no classifier can achieve high accuracy.

Moreover, we don't need a reason to believe that robust classifier exists since every optimal Bayes classifier is accurate and robust by definition

We do not see why the Bayes classifier is robust by definition if its definition has nothing to do with adversarial attacks. Our theorem 2 shows that the Bayes classifier for our orthonormal clusters model is nearly optimally robust because it can maintain high robust accuracy under any attacks of radius smaller than the critical attack budget $\sqrt{2}/2$. We would like the reviewer to clarify why this is an obvious result that does not require proof.

We hope our response addresses your concerns. If you have additional questions/concerns, please feel free to post comments during the discussion phase.

References:

Min and Vidal, Can implicit bias imply adversarial robustness? ICML, 2024

Frei et al., The double-edged sword of implicit bias: Generalization vs. robustness in reLU networks. NeurIPS, 2023

Thank you for the response. I don't want to discourage the authors from pursuing this research, rather I think that the paper is asking the wrong questions. Even though the analysis is done rigorously, and the quality of the paper is very good, I'm afraid that answers to irrelevant questions are irrelevant.

• Data assumption:

My understanding of the analysis is that the paper is basically assuming that the training samples are sampled from a simplex, i.e. sampled from a Dirichlet distribution, and that the samples are separable, i.e. the parameters of the Dirichlet distribution are equal and less than one. The paper does not realize this simple characterization of data and spends a lot of energy in describing it through orthogonality, etc. Nevertheless, this does not change the fact that the assumption is not real or helpful. For example, it is completely useless for any domain that is a subset of $\mathbb{R}$ because it is not even possible to define a classification problem that respects this assumption in 1D; the simplex in this case is a point. Considering this fact, I cannot see what good an analysis with this assumption can do. Previous papers might be onto something here, but I don't think that this paper is furthering the discussion in a significant direction. I can imagine that relaxing/changing this assumption would be a step in the right direction.

• Relevance in real-world scenarios:

I think the new experiments are fine, however, the experiments should also contain the end-to-end robust accuracy as well before we can infer them as evidence for real-world relevance.

• Why ReLU fails to be robust:

From what I understand, $\sigma^p\in C^p$ in which $C^p$ is the set of $p-1$ times differentiable functions. For example, $\sigma$ is continuous but not differentiable, and $\sigma^2$ is both continuous and differentiable but not twice differentiable. Consequently, a network that is activated with pReLU is also in $C^p$. We know that $C^p\subset C^q$ for $q<p$, i.e. networks that are activated with ReLU are more expressive that those that are activated with pReLU with $p>1$. So, it makes a lot of sense, even a little obvious if I may, that GD performs better for pReLU when the target decision boundary can be represented with a $C^q$ function in which $q>p$; there are simply less hypotheses in the hypothesis space. This further shows why the assumptions on data distribution are very important on making the analysis relevant. My take is that the paper has set the learning problem up to succeed.

• Accuracy-robustness tradeoff:

I think you are assuming that a tradeoff between accuracy and robustness is only possible when training samples overlap. While there are such proposals in the literature[A], there are also counter arguments[B]. I think the safest bet for now is to say that the trade-off is due to nonexistence of a representation for the robust decision boundary in the hypothesis space. The analysis does not take into account this possibility which further exacerbates the issues with data assumption and the presented analysis that I have mentioned. The paper needs to make these issues explicit in the text.

• Obvious claims:

Our theorem 1 does not assume an unlimited budget.

The theorem gives an upper bound for the budget, so I am interpreting that it is rejecting the possibility of unlimited budget. The exact value of the bound is dependent on the data distribution and is irrelevant to the broader problem IMHO.

We do not see why the Bayes classifier is robust by definition if its definition has nothing to do with adversarial attacks.

AFAIK, the Bayes classifier is:

in which $D$ is the distribution of test samples. So, as long as we are choosing the right distribution, there is no need to mention any robustness condition. As an analogy, consider a human subject as the optimal Bayes classifier. If we find a perturbation for an image of a dog which changes the opinion of the human into believing that this is an image of a cat, then that image is indeed of a cat, i.e. the perturbation has moved the sample past the true decision boundary. What you are referring to I think is the application of attacks in adversarial training of the hypothesis which always limit the budget so that a human is never convinced that the label of the image has truly changed, e.g. the perturbation be imperceptible. As you can see, we are always training a classifier for which the corresponding optimal Bayes classifier exists in practice.

[A] D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry, “Robustness may be at odds with accuracy,” in International Conference on Learning Representations, 2019. [B] Y.-Y. Yang, C. Rashtchian, H. Zhang, R. R. Salakhutdinov, and K. Chaudhuri, “A closer look at accuracy vs. robustness,” in Advances in Neural Information Processing Systems, 2020

We find it unfair for the reviewer to criticize our work from a pure learning perspective for having a simple data model and disregard all our main contributions in optimization.

I understand your frustration, but my job is to be objective, not to be fair. If the main contribution of the paper is in optimization, then it should not have been filed under "learning theory" as the primary area. That is the main reason that the paper is being reviewed by someone like me. Having said that, since the paper's analysis is not taking into account the issues of hypothesis spaces and sample complexities of those spaces, from the perspective of "learning theory" it is not a strong analysis. In other words, as far as learning theory is concerned, I believe that the proposition of the paper regarding GD is true for every ERM learning rule out there and the specific analysis of gradient flow seems a little superfluous. Nevertheless, I might change my mind after discussing the contributions with other reviewers and AC in the discussion period. Hence, I will increase the score of the paper to 5 to show that I am willing to discuss.

The reviewer criticizes our data assumptions based on an incorrect understanding of our data assumptions. Specifically, the reviewer believes “training samples are sampled from a simplex, i.e. sampled from a Dirichlet distribution.” As we write in Line 56, “We consider a balanced mixture of K-Gaussians.”

Figure 1 of the paper explicitly shows the simplex, the dashed line connecting the centers of the Gaussians is exactly the simplex. More formally, the cluster centers in $\mathbb{R}^D$ could be stacked in a $D\times K$ matrix $M$ which has a QR decomposition $M=QR$ in which $R$ is a rectangular diagonal matrix with its diagonal entries being 1. As you can see, when $K\leq D$, the cluster centers fall on the corners of the $K-1$-simplex and when $K>D$ it is not possible to satisfy the orthogonality condition. Furthermore, since only support vectors are necessary to define the decision boundary, the training samples that are sampled from the simplex are sufficient for classification since they are the samples that fall closest to any other cluster center.

Simply put, this is where the state of the art is.

The SOTA argument is not effective when it comes to theoretical papers. For an experimental paper, it is acceptable to be similar to SOTA, but for a theoretical paper we either need a new theory or an improvement over SOTA. That is what I meant when I said that the paper is asking the wrong questions, this particular configuration of data is already analyzed and now we need to move beyond it. The particularities of this data assumption are not significant enough to be discussed further IMHO. For example, I consider dropping the orthogonality condition or the Normality condition on the distribution of clusters as significant.

we are very puzzled by the reviewer's comments.

In my comment I am referring to Theorem 2 of the paper. The text following the theorem reads:

Therefore, $f^∗$ is nearly optimal robust when $\frac{\alpha^2}{D}=o(1)$, i.e. the ambient dimension is large or the intra-class variance is small.

I find the conclusion of this theorem obvious. This problem would be alleviated if the paper draws a stronger connection between the theorems and the main goal of the paper.

We thank the reviewer for the response and willingness to reassess our manuscript. Since it is close to the end of the discussion phase, we will keep our response short as we have discussed our viewpoints in previous responses.

In other words, as far as learning theory is concerned, I believe that the proposition of the paper regarding GD is true for every ERM learning rule out there and the specific analysis of gradient flow seems a little superfluous.

The reviewer's comment about hypothesis space is interesting, but we think our additional experiment in the newest revision is at the odds of this conjecture. In this new experiment (Please see Appendix A.1), we run SGD on a pReLU network and on a regular polynomial ReLU network (they induce the same function space for the same $p$), and the results are (We invite the reviewer to check the details in our new revision):

• SGD on a regular polynomial ReLU network cannot find a robust classifier. Therefore, selecting the function space is important, but the way the function space is parametrized is also important.
• SGD on a pReLU network with a large initialization scale cannot find a robust classifier. Therefore, selecting the correct hyperparameter of the training algorithm is also important.

In summary, many important aspects of GD training affect the robustness of the trained network; our theoretical analysis, alongside many previous works on the implicit bias of GD, precisely shows why certain choices make sense, which is a non-trivial problem, as we can see in the experiment. We hope our new experiment can aid the reviewer's assessment of our manuscript.

(Note: We slightly edited our response to improve its clarity)