Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs

Thank you for the valuable comments and suggestions. Here are our responses to your questions:

Experiments on real datasets: As we stated in Remark 2 (and we will expand it as per reviewer MTUy's suggestion), we focus on developing theoretical results in this paper, and the related experiments on real datasets (MNIST, CIFAR) have been presented in prior works. Nonetheless, we will add experiments on synthetic data that validate our Theorems (See our rebuttal "Experiments: degenerate v.s. non-degenerate initialization" to the reviewer hboM). Lastly, the comparison with adversarial training suggested by the reviewer is an interesting future research topic.

Other choices of activation functions: If one uses GELU or Leaky-ReLU, the trained network has a similar level of robustness to those (ReLU, linear, Tanh) that are non-robust. We are happy to add their corresponding plot to Figure 2.

Beyond Guassian models: We will add a concluding remark discussing future work. The future work will be along the lines of extending the current analysis to more complex data models, for example, union of low-dimensional subspaces.

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

Thank you for the valuable comments and suggestions. Here are our responses to your questions and concerns:

Structure of this paper: We have shared our view on the current structure of our paper in our rebuttal "Organization/presentation of this paper" to reviewer MTUy, and we will make revisions to our manuscript to further improve its presentation and clarity. Regarding your specific suggestions, we will add numerical experiments to the manuscript (please see below) and a concluding remark discussing future work. The future work will be along the lines of extending the current analysis to more complex data models, for example, union of low-dimensional subspaces, and possibly extending to the transfer learning setting (Please see our rebuttal "Practical implication of our results" to reviewer MTUy) for end-to-end robustness certificates, when provided some properties of the feature extractor.

Experiments: degenerate v.s. non-degenerate initialization: Great suggestions. We have conducted numerical experiments on synthetic GMM data to illustrate how this (non)degeneracy of the initialization affects the convergence of GD. These experiments validate our Theorem 1, and also show that GD still converges under random initialization (which does not satisfy our Assumption 2) except with a slightly slower alignment between neurons and cluster centers, which agrees with our discussion in our remark "Limitation of our current result." We will add these experiments to the revised manuscript.

We describe these numerical experiments in detail: we consider, as per the reviewer's suggestion, two types of initialization:

• Random initialization: the initialization follows Assumption 1, with entries of initialization shape $w_{j0},j=1,\cdots,h$ all i.i.d. samples from standard Gaussian. As we discussed, this does not satisfy our Assumption 2 in high-dimension scenarios.
• Non-degenerate initialization: We nudge the above random initialization shape toward cluster centers to increase its non-degeneracy gap. Specifically, for every $j$, we let $w_{j0}\leftarrow w_{j0}+\delta \cdot(\mu-w_{j0})$, where $\mu$ is randomly uniformly selected from one of the cluster centers $\mu_k,k=1,\cdots,K$. The resulting new initialization shape has a non-degeneracy gap of roughly $\delta$, thus satisfying Assumption 2. We also adjust the $|v_j|$ accordingly so the initialization satisfies Assumption 1.
• The initialization scale is $\epsilon=1e-7$

We run GD with step size $0.2$ on a synthetic GMM dataset of size $n=5000$ with $D=1000, K_1=5, K_2=5,\alpha=0.1$, and keep track the following:

• Alignment: The alignment measures we are interested in are $\max_k\cos(\mu_k,w_j), j=1,\cdots,h$, and our Theorem 1 and its proof suggests that they converge to close to 1 after sufficient training time. For clarity, we report their mean value and the 1st quantile.
• Loss: The mean square loss.
• Distantance to $F^{(p)}$: The quantity $\sup_{x\in S^{D-1}}|f^{(p)}(x;\theta)-F^{(p)}(x)|$. We estimate this quantity by randomly sampling large batches of $x$ and running projected gradient ascent on this distance.

We summarize the findings

1. GD converges and finds $F^{(p)}$ in both cases, thus verifies our Theorem 1;
2. The alignment between neurons and cluster centers is slower for random initialization than with the nudged initialization with $\delta=0.05$ non-degeneracy gap. This agrees with our discussion in "Limitation of our current result": having some non-degeneracy gap skips a "burn-in" phase for the neurons' directional dynamics,

from the following tables:

Note: 1) for the alignment, $1.00$ is a rounded value; 2) by the end of the training, "GD, random initialization" has a lower mean alignment because it has more neurons in the void regions that do not receive GD update during training.

We hope our rebuttal addresses your concerns regarding the organization of our paper. If you have additional questions/concerns, please feel free to post them during the discussion phase.

Thank you for the valuable comments and suggestions. Here are our responses to your questions and concerns:

Organization/presentation of this paper: Although this is a concern raised by two reviewers (MTUy and hboM), we do not think there is any major issue with the organization of our manuscript. In fact, Reviewer KSsi finds the paper "extremely well-written". It is our view that the disagreement comes from the fact that in the main sections after the introduction, we put more emphasis on the interpretation of our assumptions and results (and Reviewer KSsi thinks they are "interesting", "very nice, and enlightening"), and relatively less emphasis on certain aspects (message to the ML community, practical implications). We thank reviewers MTUy and hboM for pointing out those issues. We address them in the rebuttal, and they can be easily incorporated into our current manuscript.

What message should one get from this paper? As a theoretical paper, we believe our messages are clearly stated.

• The paper title summarized our theoretical contributions;
• Our message appeared in the abstract: "This paper shows that for certain data distributions, one can learn a provably robust classifier using standard learning methods and without adding a defense mechanism";
• We outlined our messages in the introduction section in detail: (0) We aim to answer whether standard training methods can find a robust classifier without adversarial examples. We show that for GMM data, (1) data concentration ensures the existence of robust classifiers, and class separation determines the maximum achievable robustness; However, (2) GD on shallow networks can not find a robust classifier unless the activation is carefully chosen, and we show the GF probably finds a robust classifier with appropriate choices; (3) These results highlight that finding robust classifier by standard training is possible but requires a joint understanding of the data structure and the training dynamics of GD algorithms.

Based on the reviewers' comments, we feel their concern arises because, after the introduction, the main body of the paper emphasizes the technical presentation of our results. To resolve this issue, we will remark on how our results reflect these messages in the main sections.

Practical implication of our results We will expand Remark 2 to address the practical implications of our results. We explain them here: In the case of transfer learning, one is given a pretrained feature extractor and aims to train a shallow network classifier. Our theorem provides guidance in obtaining robust shallow network classifiers with standard training for tasks with coarse labels. By tasks with coarse labels, we mean that each class includes many sub-classes, but the label only reveals the class membership. For example, when classifying images of cats and dogs, the dog (cat) class may include different breeds. Notably, many feature extractors, like CLIP, are trained on a massive dataset that contains subclass information and thus can "distinguish" subclasses. That is, the extracted feature from different subclasses has nearly an orthogonal GMM structure (verified for CLIP embeddings of CIFAR in Li et al. 2024). Therefore, classifying these extracted features only with coarse class labels is close to the learning problem we entertained in this paper, and our theorem sheds light on how to train the shallow network with appropriate activation for robustly classifying these features. We note that here, we are addressing the robustness of the classifier against perturbations in the extracted feature; how robust the end-to-end model is also depends on the property of the feature extractor.

How our findings benefit the ML Community: Our contributions are:

• (High-level) We show that for certain data distributions, one can learn a provably robust classifier using standard learning methods and without adding a defense mechanism.
• (Theoretical/Technical) Our main theorem introduces the analysis of GF on shallow networks with new activation functions, and reviewer KSsi thinks "the analysis methods developed here may serve as the foundation for future work to analyze more complicated (and more practical) settings."
• (Practical) We have expanded our remarks on the practical implications of our results in this rebuttal and will add them to the revised manuscript.

Other additions: We will add a conclusion section based on the responses above. Moreover, we will add numerical experiments to validate our theoretical results and remarks on future work (Please see our rebuttal to reviewer hboM).

We hope our rebuttal addresses your concerns regarding the organization of our paper. If you have additional questions/concerns, please post them during the discussion.

Reference:

Li, B., Pan, Z., Lyu, K., and Li, J. Feature averaging: An implicit bias of gradient descent leading to non-robustness in neural networks. arXiv preprint arXiv:2410.10322, 2024.

Thank you for the valuable comments and suggestions, and for the encouraging words acknowledging the strengths of our manuscript. Here are our responses to your questions and concerns:

Concentration of Gaussians: The claim that a Gaussian $\mathcal{N}(\mu,\frac{\alpha^2}{D}I)$ concentrates around a $(D-1)$-dimensional affine subspace is derived from the fact that (1) as the reviewer pointed out, it concentrates around a sphere, and at the same time, (2) one can cover most masses of this high-dimensional sphere by any set $S$ as long as $S$ is a Minkowski sum of a $\mathcal{O}(1/\sqrt{D})$-radius ball and a $(D-1)$-dimensional affine subspace that contains the Gaussian mean $\mu$ (one should think $S$ being the inflated version of the $(D-1)$-dimensional affine subspace with thickness $\mathcal{O}(1/\sqrt{D})$); This geometric property of high-dimensional sphere is discussed in the section 2.2 of the book from (Hopcroft and Kannan). Therefore, most masses of this Gaussian $\mathcal{N}(\mu,\frac{\alpha^2}{D}I)$ is within $\mathcal{O}(1/\sqrt{D})$ eculidean distance to the chosen affine subspace, from which we say in line 101, "the class-conditioned probability masses concentrate around two (D−1)-dimensional affine subspaces". We hope this clarifies and are happy to add this explanation to the revised manuscript.

Attack radius: The $\|d\|=1$ in line 119 is a typo. Thank you for pointing it out. We have $\|d\|\leq 1$ in all other places.

Stop time in Theorem 1: This is a technical limitation of our analysis. In Appendix A, line 592, we acknowledged this limitation in the remark "Analysis until finite time $T^*$", and we referred to some previous work on local convergence of GF, for example (Chatterjee, 2022), which can potentially be utilized to show that the weights stay around the neighborhood around where they are at time $T^*$ for the rest of the GF because the loss is already close to its global minimum (thus no sudden divergence).

Why not use $F^{(p)}$ directly: Our aim is to theoretically understand how a neural network can learn a robust classifier by standard training. Although $F^{(p)}$ can be easily constructed, it is unknown whether a network can learn $F^{(p)}$, and our theorem highlights that provable learning $F^{(p)}$ with networks requires some specifical choice of activations.

We also thank the reviewer for pointing out typos and notation issues in our manuscript. We will fix them in the revision.

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

Reference:

Hopcroft, J. and Kannan, R. Computer Science Theory for the Information Age.

Chatterjee, S. Convergence of gradient descent for deep neural networks. arXiv preprint arXiv:2203.16462, 2022.