Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Authors: Hancheng Min
Rene Vidal
Venue: ICML 2025 poster (2025)
Keywords: Orthonormal Gaussian Mixture
Robust classifier
Two-layer Network
Gradient Flow
Primary area: theory->optimization
TL;DR: We show GF on two-layer networks converges to robust classifiers for data from GMM with orthonormal cluster centers

Abstract: Deep learning-based classifiers are known to be vulnerable to adversarial attacks. Existing methods for defending against such attacks require adding a defense mechanism or modifying the learning procedure (e.g., by adding adversarial examples). 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. More specifically, this paper addresses the problem of finding a robust classifier for a binary classification problem in which the data comes from an isotropic mixture of Gaussians with orthonormal cluster centers. First, we characterize the largest $\ell_2$-attack any classifier can defend against while maintaining high accuracy, and show the existence of optimal robust classifiers achieving this maximum $\ell_2$-robustness. Next, we show that given data from the orthonormal Gaussian mixture model, gradient flow on a two-layer network with a polynomial ReLU activation and without adversarial examples provably finds an optimal robust classifier.

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Hancheng Min 12
René Vidal 123
Abstract
Large Language Models are also susceptible adversarial attacks (Chao et al., 2023; Shah et al., 2023), leading to undesired or harmful outputs, and the competition between adversaries and defenders continues (Robey et al., 2023; Ji et al., 2024). While such a competition allows us to design more robust networks, it will not end unless many funda- mental questions about adversarial robustness are answered.
Deep learning-based classifiers are known to be vulnerable to adversarial attacks. Existing meth- ods for defending against such attacks require adding a defense mechanism or modifying the learning procedure (e.g., by adding adversarial examples). This paper shows that for certain data distributions one can learn a provably robust clas- sifier using standard learning methods and without adding a defense mechanism. More specifically, this paper addresses the problem of finding a ro- bust classifier for a binary classification problem in which the data comes from an isotropic mix- ture of Gaussians with orthonormal cluster cen- ters. First, we characterize the largest fa-attack any classifier can defend against while maintain- ing high accuracy, and show the existence of op- timal robust classifiers achieving this maximum fz-robustness. Next, we show that given data from the orthonormal Gaussian mixture model, gradi- ent flow a two-layer network with a polynomial ReLU activation and without adversarial exam- ples provably finds an optimal robust classifier.
One question is, what is the maximum adversarial perturbu- tion neural network can tolerate? Many works on certified robustness (Cohen et al., 2019; Fazlyab et al., 2020; Zhang et al., 2018) aim to find certified radius such that a neural network can provably maintain a high prediction accuracy for adversarial attacks within that radius. However, their reported certified radii are often too small compared what can be achieved by practical defenses (Tramèr et al., 2018; Guo al., 2018; Gowal et al., 2020; Wu al., 2020). Yet, practical defenses come at the cost of computing adversarial examples, or sophisticated model designs, mostly without theoretical guarantees, except for the case of linear classi- fiers (Zou et al., 2021). This also gives rise to an intriguing question: possible to find a robust network by standard training methods without adversarial examples?
Note that this question might not always be well-defined. For example, Dobriban et al. (2023); Javanmard et al. (2020) prove that, for certain tasks, trade-offs between clean accu- racy and adversarial robustness are unavoidable, hence the notion of robust networks requires additional specifications on how much accuracy one would sacrifice for robustness. However, for tasks without such trade-off', a robust clas- sifier can be accurate clean data while maintaining substantial level of robustness against adversarial attacks. The existence of such a robust classifier is closely related to data geometry. For instance, Pal et al. (2023; 2024) show that if the data is localized, i.e., if the distribution of the data given the class concentrates in a set of small volume, then a robust classifier is guaranteed exist. Moreover, they show that a 2r separation (w.r.. some distance metrie) between the sets that contain each class-conditioned probability mass is sufficient for the existence of a robust classifier against attacks of radius r in the same distance metric. These results motivate us to explore the following question: Can standard training methods, without adversarial examples, provably find classifier for localized data that achieves maximum robustness while maintaining good clean accuracy?
1. Introduction
The vulnerability of neural networks to adversarial at- tacks (Szegedy et al., 2014), i.e., perturbations to their input that are typically human-imperceptible, has led to numerous efforts building defenses against these attacks (Shafahi et al., 2019; Papernot et al., 2016; Wong et al., 2019; Guo et al., 2018; Cohen et al., 2019; Levine & Feizi, 2020; Yang et al., 2020; Sulam et al., 2020; Kinfu & Vi- dal, 2022). These defenses have been counteracted by new adaptive attacks (Athalye et al., 2018: Carlini et al., 2019; Croce & Hein, 2020), leading to new defenses and so on.
'Center for Innovation in Data Engineering and Science (IDEAS) 'Department of Electrical and Systems Engineering 'Department of Radiology, University of Pennsylvania, Philadel- phia, U.S.A.. Correspondence to: Hancheng Min <hanch- min scas. upenn.cuuu.uu..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
Robust Acc. against & PGD Attack
1.0
PReLU (p=3)
ReLU
0.8
Bayes
(pn
Accuracy
0.6
Tanh
MLP
D
LogReg
0.4
0.2
A1
o D
P2
0.0
F2
0.0
0.2
0.4
0.6
0.8
1.0
1.2
Attack Radlus
Figure 2. Given mixture of Gaussian data with 12 positive clusters and 8 negative clusters (D 2000), gradient descent (SGD, small initialization) (bias-free, width-200) two-layer ReLU network (ReLU) fails to find a robust classifier. This issue persists after 1) increasing depth to (MLP): 2) (blindly) switching to another activation (Tanh);; or 3) using a linear classifier (LogReg). However, by choosing suitable activation (pReI.U, p = 3), GD can find nearly optimal robust classifier. Here, the plot emphasizes the im- portance of choosing an appropriate function class (activation). Additional experiments in Appendix B.2 highlight the importance of choosing proper network parameterization and initialization.
Figure 1. Illustration of two clusters in high-dimensions, each concentrated on (D- --ddinensional affine subspace such that the subspaces are separated by Euclidean distance of /2.
In this paper, we show that for certain localized data distri- butions, one can characterize the maximum robustness any classifier can achieve based on how class-conditional prob- ability masses are separated. We also show one can make suitable architectural designs that exploit the data geometry such that a nearly optimal robust classifier can be provably learned by standard training, such as gradient flow (GF).
Based on this observation, our first set of results are:
Theorem (Proposition I & 2, informal). No classifier can defend against an adversarial attack of radius 2 ever, one can construct nearly optimal robust classifier that can defend against attacks of radius arbitrarity close to va when D) sufficiently large. 2
V2 How-
In what follows, we explain each one of these contributions in more detail. Before that, we introduce our data model.
Our results show that data localization and separation are important properties in understanding the maximum achiev- able robustness for a classifier. Moreover, we will show that the classifier we construct is the Bayes optimal classifier w.r.t. the 0-1 loss, which operates as nearest-cluster rule: classifiers that exploit the multi-cluster data structure are naturally and optimally robust.
Orthonormal Gaussian Mixture Model. Consider a bal- anced mixture of K Gaussians in RR,, split into two classes;
Min, ( "ID),, M(IK),,,,,,,(KK, II//D) (Positive Class)
Mux,aa (Negative Class)
Learning optimal robust networks So far everything seems to be intuitive and straightforward given the fairly simple distributional assumption. However, issues arise when one does not know the data distribution a priori and seeks classifier by training neural network on sampled data via gradient descent (GD). As Figure 2 suggests, a trained ReLU network fails to find classifier with the same level of robustness the Bayes classifier (which indeed can defend against attack of radius v2 as our results suggest). This matter is first discussed by Frei al. (2023), where they show that any two-layer ReLU network trained by GD under data samples from orthonormal Gaussian mixture is non-robust against adversarial attacks of f2-radius θ ( where K is the total number of clusters. Later, Min & Vidal (2024) show that this issue is caused by the fact that ReLU network fails to learn, internally with its weight parameters. the multi-cluster structure of the data distribution, even the sampled data points are revealing such a structure, and a convergence analysis of GD in Li et al. (2025) theoreti-
where the cluster centers M1.' MK RR are othonormal, a denotes the intra-cluster variance, and the data dimen- sion D is sufficiently large. One can show that this mixture of Gaussian distribution satisfies data localization and sepa- ration properties similar to those studied in Pal et al. (2023), thus a robust classifier is guaranteed to exist.
Maximum fg-robustness. As illustrated in Figure 1 for the case of two clusters (one from the positive class and one from the negative class), the class-condin conditonnd probability masses concentrate around two (D- - 10-11--dime dimeenssioaa affine subspaces separated by a Euclidean distance of almost v2.
2
'To see this, start with the fact that the distribution A (1r, e² T) concentrates around sphere of radius o, then use the result stating that one can cover most masses of this high-dimensional sphere by any set S that is a Minkowski sum of ( -D)rrdius a (D- - -imieensia affine subspace that contains the Gaussian mean (one should think S heing the inflated version of the affine subspaces shown in Figure 1 with thickness (1)/DD)).
-radius ball and
2

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
cally supports this argument. Therefore, while the structural property of the data distribution allows one construct an optimal robust classifier, gradient descent algorithms neural networks may struggle to learn these key properties, leading to non-robust classifiers.
ple of random variables (X,Y, Z) on RD x (+1,-11x [K]
representing observed data, observed class label, and latent cluster membership, respectively, defined as follow:
Z ~ Unif([1,.... ,K, ,KK), x ~ N (uz, (I = - 12>K,, (1)
To address this issue, Min & Vidal (2024) propose to change the activation. More specifically, replacing the ReLU activa- tion with a polynomial ReLU activation (pReLU) with poly- nomial degree p hyperparameter (defined later in (5)). They empirically show that when p is large, the pReLU network can internally learn the data structure, leading to a more robust classifier. However, a rigorous analysis of convergence is not provided. Our second set of results is to develop a full convergence analysis for gradient flow on a two-layer PReLU network and show that:
-
where the p,,..... .K. called cluster centers, are a set of orthonormal vectors in RD, i... (Uks 14) = 1L=k- We denote the marginal distribution of the (X, Y) pair by Dx,y, and use (æ, y) to denote sample from Dx,y.
f--robust classifier for Dx,y- Our interest is to find a classifier that not only accurately predicts the label y given an observed data æ, but does so in a way that is robust to some additive adversarial attacks on æ. Specifically, we seek a classifier f: RD + such that given a sample (x, y) from Dx,y, with high probability, we have f(z) > O, which suggests that sign (f())) correctly predicts the label y, Moreover, we require that for some > 0, f is robust to additive adversarial attacks of b2-norm radius r, i.e., min [|] f( + rdjy > 0 with high probability over sample (ær y)- This suggests that sign (f + rd)) still makes a correct prediction on y even though æ has been corrupted by some attack rd. Ideally, we want a classifier that is robust to attack of radius r, with as large r as possible.
Theorem (Theorem 1 & Corollary 1, informal). When the intra-cluster variance a² is sufficientll small, gradient flow on pReLU networks (5) with p > 2 converges to a nearly optimal robust classifier.
Our result is based on prior works on gradient de- scent/flow with small initialization on two-layer ReLU net- works (Maennel al., 2018; Phuong & Lampert, 2021: Boursier et al., 2022; Kumar& & Haupt, 2024; Chistikov et al., 2023; Wang & Ma. 2023; Min et al., 2024) and we extend their convergence analyses to pReI.U networks. We show how the implicit bias (Vardi, 2023) of the gradient flow dynamics critically depends on a careful choice of ac- tivation function, allowing the network to learn accurately the underlying data structure, which, as we have discussed, is essential for finding robust classifier.
Maximum achievable fy-robustness. Inevitably, any clas- sifier fails to be robust if the adversary has too much power, i.c., the attack radius r exceeds some value. Indeed, for the data distribution Dx,y of our interest, no classifier can defend against attacks of radius x22 shown below:
Proposition 1. Let f : RD. + R be any Lebesgue measurable function such that the random variable mingalsi [f (x + d) y is also measurable. Given a sample (xc, y) ~ Dxxy, we have
Notation. We denote the inner product between vectors x and y by (z, y) = x y, and the cosine of the angle be- tween them as cos(2; y) = | T ). For an n matrix A, we let || and || denote the spectral and Frobenius norm of A, respectively. We define A as the indicator for a statement A: 1A- = 1 if A is true and 14- = O otherwise, and define [+ == max(-:0 We also let N (1,, )²) denote the normal distribution with mean μ and covariance matrix m² and Unif(S) denote the uniform distribution over a set S. Lastly, we let [M] denote the integer set [1,--- ,N3 and let SD-1 be the unit-sphere in RDD
Ty,
/ (xx
V2
1 1/
min K1, K2}
P min [dl]
50
>
(2)
2
K
We refer the readers to Appendix C. for the proof. We ex- plain Proposition I from a geometric perspective, expanding upon the discussion in the introduction: Consider data from a² two clusters N (Mi, Oh I) and andN(uus N( o² I) corresponding to different classes. As shown in Figure 1, when ambient dimension D is large, we expect that each cluster concen- trates around a D - 1 affine subspace that is orthogonal to the vector [4] - u2z Most importantly, the distance between these two affine subspaces is v2, suggesting that given any decision boundary that separates two affine subspaces, an adversary can perturb substantial portion of the probability mass of these clusters to cross the boundary with attack radius v/2 The same argument holds for K-clusters, where 2
2. Optimal Robust Classifiers for Orthonormal Gaussian Mixture
We start by studying the optimal robust classifiers for or- thonormal Gaussian Mixture.
Orthonormal Gaussian Mixture Model. We study a bal- anced mixture of K Gaussians, with K, of them belonging to the positive (+1) class and Kg == K K2 of them be- longing to the negative (-1) class. Formally, consider tu-
any pair of clusters is separated by a Euclidean distance
3

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
22. We also note that extending Proposition 1 to attacks in another metric amounts measuring this separation in that metric. Our second result shows the Bayes optimal classifier w.r.t. the 0-1 loss is also nearly optimally robust:
two-layer networks with gradient flow. Then show that with pReL.U activation, gradient flow provably finds classifier that is nearly optimal fg-robust.
Proposition 2. The Bayes optimal classifier w.r.t. the 0-1 loss is sign (x)), where
3.1. Preliminaries: training on two-layer networks for orthonormal Gaussian mixture
Kr exp
D
(a. (1)) Σ exp
)
K
(D(
(a.
PRRLU network. We consider two-layer pReLU net- work (Min & Vidal, 2024), which is defined as follows:
(x)
a²
a²
1=1
k== K1+1
( wgy) 2
Moreover, given a sample (a. v) ~ Dx,, we have, for any 2v2n² log
f(() (x; 1)=
1100 || (0:= (w,, 0,))=a) (5)
S VVS S 22,
Note that f(P) can be viewed generalized version of the ReLU network. When p 1, f()) is exactly two-layer ReLU network. When p > 1 and that is approximately unit-norm, the output of the hidden activation is approxi- mately equal to the one of the ReLU network multiplied by cos" (x, wy) (Min & Vidal, 2024), which discourages large angle separation between data x and neuron wy..
V2 11 d
min ||
+
y >
2
Dv²
2 - 2K exp
(3)
64a2
We refer the readers to Appendix C.2 for the proof. If we
pick V = (( +) in Proposition 2, then the result shows
f-lsoss function and balanced dataset. Given dataset (a;, y1 )=) define the loss function as L(0; {æa, y6 )==))) Σ f(y.. where f f(v) (zx;; 0). For classification problems, the typical choice for é is the exponential loss exp(-vý). or the logistic loss log(1 [1 + exp(-uö)). Most of our theoretical analysis works for these choices for f. However, using classification losses poses additional chal- lenges in analyzing the late phase of the training (details explained in later sections). Therefore, our theorem consid- ers the fz-loss: E(y, ù) a ~01 and the extension to classification losses is discussed in Appendix A.
that/ /" is robust against attacks of radius //2 - 0 (
with probability at least 1 OKK exp - (.:)) (1))))) over new sample from Dx,y. Therefore, f is nearly optimal 2² = (1), i.e., the ambient dimension is large robust when D or the intra-class variance is small.
Interpreting f as nearest-cluster rule. One can show that (please see Appendix C.2 for the derivation)
sign
max IskSKi
(xc, (Ax)
max
(1,, (Ax)
KitIsksK
O a²
As for the dataset, since Dx,y samples data with equal probability from each cluster, there are approximately equal number of samples from each cluster when we sample a large number of data. Therefore, instead of considering dataset directly sampled from Dx,y, we consider the following balanced dataset D {a y1 KN where
log K)).
(4)
D
When the error O K 83) is small, the Bayes classifier (xx) finds the closest cluster center to æ and outputs the label to that cluster, which is nearest-cluster rule. There- fore, by respecting the multi-cluster structure of Dx.y, f achieves the maximum fy-robustness.
2; N (MAN a² I/D) W/ lagk, 1 (k- 1)N + 1 i AN 1 kkk. K.
(6)
So far we have shown that a nearly optimal robust classi- fier for Dx,y can be easily constructed as a nearest-cluster rule. However, as we discussed in the introduction, gra- dient descent algorithms with sampled data often fail to find classifier with the same level of robustness. Next, we address the problem of finding nearly optimal robust classifier by gradient flow dynamics.
We call this dataset balanced because D has exactly N sam- ples from each cluster ((MA;,aTT/)) This assumption allows us to omit the additive perturbations in our analysis introduced by imbalanced per-cluster sample size.
Gradient flow with small and balanced initialization. Given the network parametrization O and the loss function L constructed from balanced dataset D, we consider training the network by the following gradient flow dynamics?:
3. Optimal Robust Classifiers Obtained via Gradient Flow
i - VoL(0 D), 0 = Oo.
In this section, we aim to find a nearly optimal Eg-robust classifier for Dx,y by vanilla gradient descent without ad- versarial training. We start by stating the problem of training
Note that we focus on PReLU network with p > 2. Therefore. the network f(P) differentiable everywhere w.r.t. 0 and so
4

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
We assume the initialization (() is e-small and balanced, formally defined as the following.
((p) 0) with small initialization finds a classifier that is close to F(P) up to constant scaling factor. Then they argue that such proximity to F(e) implies that the trained network has the same level of robustness as F(P), Our main results in Section 3.2.2 fully prove this conjecture with p > 2.
Assumption 1 (e-small and balanced initialization). The initialization 0 (0) {w, (0), 2y (0)) satisfies the follow- ing: there exists an initialization shape {w,o, 230 with winn S ||ww Wmax: j. for some W minu Wmaxx > 0
Remark 1. Min & Vidal (2024) also conjecture that GF on a ReLU network (p - 1) finds a classifier that is not robust against adversarial attacks of fz-radius O [J ). which is later proved by Li et al. (2025). As extensively discussed in both works, the main reason why a trained ReLU network is not robust is because of its inability to learn the multi-cluster structure DDxy y via GD/GE
and an initialization scale 0 such that
2 (0) = e0 20(0) = eUjo, |k0zoll - leyol, Vj.
(8)
Under a balanced initialization, we have [0)| (oy())), Vyj, and this balancedness holds throughout the GF trajectory (See Appendix E.1): [|)= = |u, (t)), Vj. The balancedness between w and By allows us to focus on the dynamics of w., which has been a common assumption in prior work of this type (Maennel et al., 2018; Boursier et al., 2022; Chistikov et al., 2023; Min et al., 2024). Readers may view this assumption as made out of convenience, but we think it is essential for tractable analysis, and at the same time, the theoretical results out of this assumption match the empirical results when no balancedness is enforced (Min et al., 2024). Moreover, this assumption allows for an ele- gant interpretation of the dynamics of wy (Maennel et al., 2018; Boursier Flammarion, 2024) as searching for some directions that maximize its alignment with the data.
Closeness to F(P) implies robustness. We first show that given any classifier f that is positively homogeneous of degree 1 w.r.t. x and is close to FP in terms of some distance measure, it is nearly optimal robust when the intra-class variance is small (We refer to Appendix D for the proof.).
Proposition 3. Let 2. Given classifier f that satiisies f((z) 7f(x)) Vo E RD, by >> O and dist(f, F(P) infaso sup lcf(()) - (x)) S v for some O < Then for a sample (x, v) ~ Dx,y, we have
/ P
[
V2
P
min [d||s]
f
x
d
y
20
2
show that sign(u,(t) (1g)(1 Vj. Vt 2 0 (Boursier et al., 2022). Roughly speaking, this means that (g)())(0)) determines the dynamical behavior of neuron wj under gradient flow: neurons with sign(u,
Given balanced initialization, one
DV 3
3 802
21 2K exp
4 exp
(10)
2K
= +1 tend to align its direction with one of the positive cluster centers, -1 tend to align with one of the negative cluster centers. For this reason,
Given this result, it remains to show that gradient flow finds network (-; (which is positively homogeneous of degree 1) that is close to F(r) in the distance measure de- fined above. We will first discuss an additional assumption required on the initialization, then state our main result.
Ps. k- = 1,.... K1, and those with sign(v;(0)
define the following neuron index sets: N4 == [j E [h] (gg())(0)) = +1} and V_ ====0 = {j e [h] sign(r, = -1].
3.2. NON-DEGENERATE INITIALIZATION SHAPE
3.2. Main results: PReLU (p > 2) provably finds (near)-optimal robust classifiers
To properly define non-degenerate initialization shape, we need to define radial Voronoi tessellation of RD- I \ {0} given tuple of unit-norm vectors {px hkek.
PReLU classifier and the conjecture. Min & Vidal (2024)
study the adversarial robustness of the following PReLU
Definition 1. Given set of unit-norm vectors {UA define the following
classifier (a particular case of f(P) (x; for a choice of 0):
K1
R₂ = (WERD- {0} [cos wil+ > (cos( (e((),))))+ w)) VI kk (Voronoi regions)
((0) = Σ o ((z, pk))
Σ o (((x))))) (9)
k=
and show that (()) with p > 2 is robust to adversarial attacks of fa radius arbitrarily close - when 2 is large.3 They conjecture that when p is large and the intra-cluster variance a² is small, the gradient flow on PReLU network
RD = ( (0) [cos( w)) = 0, Vk E K. (Void region)
From this definition, it is clear that Rr. h E K and R are disjoint subsets of PR- \ {0]. We are ready to define a non-degenerate initialization shape:
TTo provide our view on why F(P) is robust, we show in Ap- pendix D that it behaves like a nearest-cluster rule for large p.
5

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMS
Definition 2 (Non-degenerate initialization shape). Given set of unit-norm vectors {us keK let (R&) and R be their Voronoi and void regions, as per Definition 1. A set of initialization shape ywy is non-degenerate W.E. pe kee if there exist disjoint subsets (Ne)kex of N. such that N = (UKEK N and
111
R1
W10
R2
(Neurons must be within one of the regions)
wyo E RR,, Ak E NE: wyo E RR, yk E :
(Non-void regions must contain at least one neuron) N& + Y. EKK K.
112
W20
R o
Moreover, we let d(w,S) S) = 1- sup a cos(w, w. 8) and define non-degeneracy gap:
Non- degenegyyyy
A
d( (woo. o( RR)):
A = min min U No kek
KEK
Figure 3. Illustration of a non-degenerate initialization shape
min d( (1050.
(11)
{wio, W20 w.r.t two orthonormal vectors (21,
JEN
Whenever a vector to falls into one of the Rg, it means that: 1) the angle between w and the corresponding f4g is less than 3; and 2) compared to all other pus μe is the closest (in angle) to w. This suggests that neurons initialized within some R2 converge to the corresponding M* under GF, and those initialized within R" stay in RD. This is indeed the case, as we will see in Section 3.2.3.
3.2.2. CONVERGENCE OF PRELU (p > 2) ON ORTHONORMALL GAUSSIAN MIXTURE
Now we are ready to state our main theorem:
Theorem 1 (pReLU converges to optimal robust classifier for orthonormal Gaussian mixture). Let p > 2. Given 0 < 5 S 1 and a sufficiently small ağ assume the intra-cluster variance, the data dimension, and per-cluster sample size satisfy that a² S og. D 2 M(0 and ((05 S N S ö(exp(ar))) respectively. Suppose that the initialization ((0) is balanced, e-small (Assumption 1) with Ô (a 8K) ). and satisfies Assumption 2 with non non-degeneracy gap A = =(1). Then with probability at least 8, the GF dynamics (7) with a sampled balanced dataset D = {wx, Ms) ) starting from (0), has its solu-
The special case when a neuron is exactly initialized on the boundary of these Voronoi regions Ø( [Ker Rx) cannot be analyzed since if a neuron has equal angular distance to two a vectors, there is no way to determine which μ vector it converges to under GF with sampled data around these μ vectors. Similarly, if neuron is initialized at the bound- ary between some R& and R", then we can not determine whether it converges to Mux or it falls into the interior of R and stays there after that. Therefore we require an initializa- tion shape with a positive non-degeneracy gap. Moreover, every R4 must contain one neuron, ensuring the correspond- ing sl gets learned. This leads our assumption:
tion (t) satisifying that: for some t" Ö (log an
1 and
T = θ log d.) +5 (ap --mini--222) with ,t", [T,,,*** + 0, we have ((0(t))= (a Vt Et T and
Assumption 2. (The initialization has a non-degeneracy gap of at least A) 3A > O such that [woj)]eNN, is non- degenerate w.r.t. {ux JISKK, with a non-degeneracy gap of at least A, and {wjo]iEN_ is non-degenerate w.r.t. {px) (iikiisss with non-degeneracy gap of at least A.
(xx (x; 0(1))()))))))))))) F (x)) <ō(a)) (12)
sup sup rE[s" (e(==--)--0-111
K i, ô, Ô hide logarithmic factor log 3 and constant factors that depend on p (in the worst case, 2²). Theorem formally proves the conjecture in Min & Vidal (2024), showing that GF on PReLU networks finds a robust classifier for orthonor- mal Gaussian mixture. Notably, the smaller the intra-cluster variance og is, the closer the network f(r) (:;0) is to F(r), which is observed numerically in Min & Vidal (2024).
As one can see, this condition is stated per class: Positive (Negative) neurons must be initialized to be non-degenerate w.r.t. cluster centers from the positive (negative) class, and we have disjoint subsets [NaJiskske N2 of N4 (disjoint subsets { MKiKI _V of N_). As suggested in our previous discussion, we show that (See Section 3.2.3) under GF, all neurons in Na converge in angle to μax which is an essential part of our theoretical results. We also let N, := N2 U N contain indices of neurons that are initialized within the void region.
We organize the subsequent discussions as follows: First, we state several remarks on understanding our main result and comparing it with prior work; Then we conclude with technical discussions on its proof sketch in Section 3.2.3.
6

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Nearly optimal robust classifier via GF. The major impli- cation of Theorem is that one can find nearly optimal (2-robust classifier by GF without adversarial examples. When the intra-cluster variance a² is small, along the GF trajectory there exists a (-:) (1)) that is (ag) close to a nearly optimal f2-robust classifier F((), and such proximity to F(r) implies the same level of E2-robustness, as shown in Proposition 3. We can immediately conclude that f(r) is also nearly optimal f2-robust:
large initialization regime (Jacot al., 2018; Chizat et al., 2019; Lee et al.; Woodworth et al., 2020; Luo al., 2021; Min et al., 2021; Du et al., 2019; Arora et al., 2019b). Our analysis follows the line of work on two-layer ReLU net- works, as we will explain in Section 3.2.3 in detail, and improves upon it by considering a more complicated dataset. Specifically, the GF on two-layer ReLU networks has been studied for orthogonally separable data (Phuong & Lampert, 2021; Min et al., 2024; Chistikov et al., 2023), that is, data with the same (different) label has positive (negative) corre- lation, for mutually orthogonal data (Boursier et al., 2022), and for positively correlated data (but only with two data points) (Wang& & Ma, 2023). Our data assumption is clos- est to mutually orthogonal data (Boursier et al., 2022), but considers non-zero intra-cluster variance. In addition, we consider a pReLU activation function, whose inductive bias is significantly different than that of ReLU (We elaborate this point in Section 3.2.3).
Corollary 1 (Nearly optimal l fg-robustness), Given any (:;0((t) obtained at t E [t", TT" from Theorem 1, it can defend against adversarial attacks of radius v2 -0a5) ) with probability 1 - (x. ~ Dx.y, thus nearly optimal robrst for Dxy-
2
2)) over new sample
Comparison with prior work: robust classifier for or- thonormal Gaussian mixture. The problem of finding a robust classifier for data drawn from orthogonal cluster centers was initiated by Frei et al. (2023), who show the- oretically that any classifier obtained by gradient descent on a two-layer ReLU network is susceptible to an adver- sarial attack of fz-radius O ((R)) even though one can easily construct a ReLU network that is robust to attacks of radius O(1)*, Then Min & Vidal (2024) explain this non-robustness issue with ReLU networks from a neural alignment perspective (Maennel al., 2018; Boursier & Flammarion, 2024). They propose replace the ReLU net- work by the PReLU, f(r) (-; 0). conjecture that training the PReLU with samples from Dx,y leads to a classifier that is close to F()) when the intra-cluster variance a² is small, and provide empirical validation for their conjecture. Our work takes one step further to theoretically prove the con- vergence to F(r) under GF, and also show that the achieved fg-robustness is nearly optimal. Also, small initialization is critical for finding robust classifier: since our data is approximately low-dimensional, adversarial examples exist if the initialization scale is large (Melamed et al., 2024), which is verified by our numerical results in Appendix B.2.
Limitations of our current result. One of the weaknesses of Theorem I is that random initialization does not satisfy Assumption (Nonetheless, we experimentally verify in Appendix B.1 that GF/GD still converges to the robust clas- sifier from random initialization): Since the non-degeneracy gap is defined by inner products between neurons and cluster centers, one can show that under random initialization, the non-degeneracy gap is A= = O (DD with high probability, while the theorem requires a @(1) gap. We have discussed this issue when we define non non-degenerate initialization in Section 3.2.1: When neurons are initialized close to the boundary between one Voronoi region R2 and another R, (which is the case under random initialization), whether they align with μ4 or with μ will depend on the points actually sampled in the data set. In this regard, at the very initial stage of GF there is a "burn-in" phase during which neu- rons "choose" their target clusters depending on the samples. Once the neurons have moved away from the boundary of these Voronoi regions with gap A = O(1), we characterize the GF dynamics by Theorem 1. In Appendix A, we elabo- rate on why this "burn-in" phase is challenging to analyze and discuss several additional technical limitations.
Comparison with prior work: GF with small initializa- tion. Over the past year, gradient descent/flow with small initialization has been studied for both linear networks (Gu- nasekar et al., 2017: 2018; Arora et al., 2019a; Woodworth et al., 2020; Gidel et al., 2019; Jacot et al., 2021; Stöger & Soltanolkotabi, 2021; Jin et al., 2023; Xu et al., 2025) and nonlinear networks (Maennel et al., 2018; Phuong & Lampert, 2021; Boursier et al., 2022; Kumar& & Haupt, 2024; Chistikov et al., 2023; Wang & Ma, 2023; Min al., 2024: Tsoy & Konstantinov, 2024; Zhu et al., 2025), to understand the implicit bias of gradient descent algorithms towards structurally simple networks, as opposed to those in the
The goal of this paper is to understand the- oretically the problem of learning a robust classifier for orthonormal Gaussian mixture via GF. Thus, we focus on proving rigorous theorems and discussing the associated technical challenges. For the practical implications of this problem, we refer the reader to Min & Vidal (2024); Li et al. (2025), where they empirically validate that in some transfer learning settings, the training problem is related to learning robust classifiers for orthonormal Gaussian mixture. For- mally establishing these connections is an interesting future research direction.
Remark 2.
*Frei al. (2023) consider data from NV VVVDiu a2 II) thus their results should he rescaled by VD when applied to Dx.Y.
7

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMS
Alignment
dt Ckj 2 (1- (a²))
2 - (amiuufar))
Ckj == coS(PR, mty))
1 S ks S K.j E No.
Cej increases
Ckj 2 1 0
Time
Weight norms
dt
Σ
|uyll
Σ 1|ws:11
Ö (a²)
Σ
l|wsy
JEV
JENL
JENL
Ejex, ||wy| ? 1s K
Σ JEN,
Iu, 10ll'ss 1Pson O(e)
Σ JEA.
|wyl so(a?))
0
O (loga"))
o (log =
Aligmment Phase
Convergence Phase
Figure 4. Important quantities (alignment and weight norms) and their dynamics long GF trajectory
3.2.3. PROOF SKETCI
for some constant C > 0. Consider the case when a = and + 0, for j E Ni. the dynamics de cks 2 Cpck P- (1 - 2. characterize the nominal effect of cluster centers μu 1 S k K on neuron direction "i each wi cluster centers is either attracting or repelling T depend- ing whether their label matches the sign of V/j and the
For simplicity, we consider the case a² = og and use a² throughout this section. The discussion conditioned on good event (has at least ô probability) when samples are concentrated around their respective cluster centers.
Overall proof. Our proof in spirit is close to that of Boursier et al. (2022), with a two-phase analysis of the GF focus- ing on different quantities. Specifically, at the initial phase, called alignment phase, one studied the dynamics of the neuron direction wy
w; aggregate effect is pushing Tw; towards pas, the closest cluster center to w in angle at initialization. We call the k-th cluster the target cluster for w.y.
||زي||| through cosine angles between W and cluster center [4g, where one shows that, for all it and j E Ne. we have that Caj == cos (nt, wj) monotonically increases until it reaches - Ō(22). That is, as we men- tioned earlier, neurons initialized within Rg converge in angle to the corresponding Ma. Then in the second conver- gence phase, we show that all Ckj can probably stay above 1 1- 1-0(2²) until T** and in the meantime, the norm of the neurons (measured by EjEN, ||æ,,| for each k) monotoni- cally grows until it reaches 1 + Ö(a²) before t", Moreover, the norm of the neurons initialized in the void region stays small: EjEN, [|0, = ö(a?). These three conditions Ckj 2 1 202((2), - ESEM, || < Ō(a²) and EjeN. ||00||| = ō(a²) together imply the desired bound between f(1)) and F()), See Figure 4 for an illustration.
The rest of the terms are considered perturbations due to noisy samples around cluster centers and a non-zero initial- ization scale: The first Ô (o/vT + */VD) term is due to the noisy samples from (the target) k-th cluster. Since we have A ((1) non-degeneracy gap, wy has a positive inner product with every sampled data within the k-th cluster, then one can utilize concentration results to bound the effect of noise. The second Ô (a² + %(vD) term is due to the noisy samples from other non-target clusters. Unfortunately, we have no control over how many of them have positive inner products with Wy, thus a worse bound Ô (a²) is de- rived. Lastly, Ô (c) is due to an e-small weight norm. With = fi(a samples, D = (a==2 dimension, and small c, the dominant terms become Ô (a allowing us to prove:
Proposition 4 (Alignment in PReLU network). Given the same assumptions as in Theorem I and consider the same GF solution ((),, 1 2 0. There exist some 4 = O (log 2) and l2 = O (log 2) such that Vk and Vj E NNs cos (JAR, wy(()) 2 1 Ō(a²). Vt [t1,t2].
Alignment phase. (See Appendix F) The alignment phase is the time interval between 0 and some Ô (log !) time, where e is the initialization scale. During the alignment phase, the norms of the weights stays Ö(e) small, which follows a similar proof in Boursier et al. (2022); Min et al. (2024). The small norm the weights, together with the positive non- nen-degeyyyycy gap assumption, allows for the following characterization of the alignment for 1 < k < K,j E NE:
We explicitly state the result during the alignment phase in Proposition 4 highlight the difference between its described alignment for pReLU network (p 2) to that of Boursier et al. (2022) for ReLU networks, where neurons are aligned with class average μ4+ = Ei l and μ__ ΣK b4 instead of cluster centers.
d dt
ckj 2 Cpec (1 -gg)
-0
a +0 a²+ a +Ō(e), (13) VD)
Convergence phase. (See Appendix G) During the conver- gence phase, the weight norm grows and exceeds e-level, as
VD)
8

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMSs
suggested by the following dynamics:
Acknowledgments
|uy|11 = (1 1 Σ
[2,]1²]
Σ
|
The authors acknowledge the support of the NSF under grants 2031985 and 2212457, the Simons Foundation under grant 814201, and the ONR MURI Program under grant 503405-78051. H. Min acknowledges the support of the DDDI and the IDEAS at UPenn under the Al x Science Fellowship.
dt JEN
JEN
JENV
④
+ 0 (aP))
Σ
|emi1l (14)
JEN2
which holds when ckj 2 1- Ō Nk.j E Nu.
d di Ejev, |ww 12 = (1 (1-) - S ||, If) EjeN, |twyll (nominal dynamics) describes the weight growth if ckj
Impact Statement
In this theoretical paper, there is no potential societal con- sequence which we feel must be specifically highlighted here.
1, y E N& and a = O. Following nominal dynamics, EjEN, ||wy| converges to 1 for every k.
The rest of the terms are considered perturbations due to noisy samples around cluster centers and the fact that align- ment ckj are only close to 1. The first O (o/vT) is due to the noisy sample from the target k-th cluster. the second Ö (a²)
References
Arora, S., Cohen, N., Hu, W., and Luo, Y. Implicit regular- ization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019a.
term is from imperfect alignment Ckj 2 1 - Ô (a²), and the last ④ (a²) term is from the noisy sample from the non- target clusters (Notice that now wys are almost orthogonal to non-target clusters, thus the effect of non- non-target clusters is smaller). With N = 2))=2) samples, the dominant terms become Ō(a²). ), allowing us to show that EjEN, ||w,|| converges to = (a²2) within t" time.
Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R. On exact computation with an infinitely wide neural net. In Advances in Neural Information Pro- cessing Systems, pp. 8141-8150, 2019b.
Athalye, A., Carlini, N., and Wagner, D. Obfuscated gra- dients give a false sense of security: Circumventing de- fenses to adversarial examples. In International confer- ence on machine learning, pp. 274-283. PMLR, 2018.
The only missing piece is that this argument requires Ckj 2 1 1-ō(a²) j We but one no longer has (13) after Ô (log 2) when weight norm starts to grow to (11--eeel. Nonetheless, once the alignment Ckj is 1 Ô (a²). ), it is hard to drop below this level as it relies on the attraction from non-target clusters but they are now near orthogonal to the neurons. Indeed, during the convergence phase, we can dt Ckj 2- - (amin (nii()r4)) ). by which we show Ckj can stay at 1 Ô (a²) level until 7 time. Since 7* 2 tx for small a, our analysis of the weight norm growth is valid.
Boursier, E. and Flammarion, N. Early alignment in two- layer networks training is a two-edged sword. arXiv preprint arXiv:2401.10791, 2024.
show that d
Boursier, E., Pullaud- Vivien, I.,, and Flammarion, N. Gra- dient flow dynamics of shallow relu networks for square loss and orthogonal inputs. In Advances in Neural Infor- mation Processing Systems, volume 35, pp. 20105-201 18, 2022.
4. Conclusion
Carlini, N., Athalye, A., Papernot, N., Brendel, W., Rauber, J., Tsipras, D.,, Goodfellow, I., Madry, A., and Kurakin, A. On evaluating adversarial robustness. arXiv preprint NMMiv:/902.06700 2019.
In this paper, we investigated the problem of learning ro- bust classifiers for orthonormal GMMs. While constructing the optimal robust classifiers is straightforward if the dis- tribution is known, the challenge arises, however, when a neural network is trained by gradient- based optimization algorithms with sampled data. We showed how a careful choice of activation function provably addresses the non- robustness issue of the network trained via gradient flow, highlighting how the implicit bias of training algorithms can critically guide the network to learn accurately the data structure, thereby achieving maximum robustness against adversarial attacks. Future research includes addressing the limitations in the current convergence amalyses, generalizing the data assumptions to more realistic ones, for example, the union of subspaces.
Chao, P., Robey, A., Dobriban, E., Hassani, H., Pappas, G. J., and Wong, E. Jailbreaking black box large language mod- els in twenty queries. arXiv preprint arXiv:23 10.08419, 2023.
Chatterjee, S. Convergence of gradient descent for deep neural networks. arXiv preprint arXiv:2203. 16462, 2022.
Chistikov, D., Englert, M., and Lazic, R. Learning a neuron by a shallow reLU network: Dynamics and implicit bias for correlated inputs. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMS
Chizat, L., Oyallon, E., and Bach, F. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pp. 2937-2947, 2019.
International Conference on Learning Representations, 2018.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018.
Cohen, J., Rosenfeld, E., and Kolter, Z. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pp. 1310-1320. PMLR, 2019.
Jacot, A., Ged, F., Şimşek, B., Hongler, C., and Gabriel, F. Saddle-to-saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity. arXiv preprint arXiv:2106. 2021.
Croce, F. and Hein, M. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In ICML, 2020.
Dobriban, E., Hassani, H., Hong, D., and Robey, A. Prov- able tradeoffs in adversarially robust classification. IEEE Transactions on Information Theory, 69(12):7793-7822 2023. doi: 10.1109/TT:22022.3255444
Javanmard. A., Soltanolkotabi, M., and Hassani, H. Pre- cise tradeoffs in adversarial training for linear regression. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2034-2078, PMLR, 09-12 Jul 2020.
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over wwrrpaarametrrized neural networks. In International Conference on Learning Rep- resentations(ICLR) 2019, 2019.
Ji, J., Hou, B., Robey, A., Pappas, G. J., Hassani, H., Zhang, Y., Wong, E., and Chang, S. Defending large language models against jailbreak attacks via semantic smoothing. arXiv preprinl arXiv:24022 16192, 2024.
Fazlyab, M., Morari, M., and Pappas, G. J. Safety ver- ification and robustness analysis of neural networks via quadratic constraints and semidefinite programming. IEEE Transactions on Automatic Control, 67(1):1-15, 2020.
Jin, J., Li, Z., Lyu, K., Du, S. S., and Lee, J. D. Under- standing incremental learning of gradient descent: A fine- aeee-graied analysis of matrix sensing. In International Conference on Machine Learning, 2023.
Kinfu, K. A. and Vidal, R. Analysis and extensions of ad- versarial training for video classification. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3416-3425, 2022.
Frei, S., Vardi, G., Bartlett, P., and Srebro,
N. The double- edged sword implicit bias: Generalization vs. robust- ness in reLU networks. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
Kumar, A. and Haupt, J. Directional convergence near small initializations and saddles in wwo-homogeneous neural networks. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Gidel, G., Bach, F., and Lacoste-Julien, S. Implicit regu- larization of discrete gradient dynamics linear neural networks. Advances in Neural Information Processing Systems, volume 32, pp. 3202-3211, Curran Associates, Inc., 2019.
Lee, J., Xiao, I.., Schoenholz, S., Bahri, Y., Novak, R., Sohl- Dickstein, J., and Pennington, J. Wide neural networks of any depth evolve as linear models under gradient descent. NeurIPS.
Gowal, S.. Qin, C., Uesato, J., Mann, T., and Kohli, Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.03353, 2020.
Levine, A. and Feizi, S. (de) randomized smoothing for certifialle defense against patch attacks. Advances in Neural Information Processing Systems, 33:6465-6475. 2020.
Gunasekar, S., Woodworth, B., Bhojanapalli, S., Neyshabur, B., and Srebro, N. Implicit regularization in matrix fac- torization. In Proceedings of the 31t International Con- ference on Neural Information Processing Systems, pp- 6152-6160, 2017.
Li, B., Pan, Z., Lyu, K., and Li, J. Feature averaging: An im- plicit bias of gradient descent leading to non-robustness in neural networks. In The Thirleenth International Con- ference on Learning Representations, 2025.
Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. Im- plicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, volume 31, 2018.
Li, J., Nguyen, T. V., Hegde, C., and Wong, R. K. W. Im- plicit sparse regularization: The impact of depth and early stopping. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021.
Guo, C., Rana, M., Cisse, M., and van der Maaten, L. Coun- tering adversarial images using input transformations. In
10

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Li, Y., Ma, T., and Zhang, H. Algorithmic regularization in over-pan pere--armeteezee matrix sensing and neural networks with quadratic activations. In Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceed- ings of Machine Learning Research, pp. 2-47. PMLR, 06-09 Jul 2018.
Phuong, M. and Lampert, C. H. The inductive bias of relu networks on orthogonally separable data. In International Conference on Learning Representations, 2021.
Robey, A., Wong, E., Hassani, H., and Pappas, G. J. Smooth- Ilm: Defending large language models against jailbreak- ing attacks. arXiv preprint arXiv:2310. 11..0:2310000844..4 2023.
Luo, T., Xu, Z.-Q. J., Ma, Z., and Zhang, Y. Phase dia- gram for two-layer relu neural networks at aafinite-widit limit. Journal of Machine Learning Research, 22(71): 1-47, 2021.
Shafahi, A., Najibi, M., Ghiasi, M. A., Xu, Z., Dickerson, J., Studer, C.,, Davis, L. S., Taylor, G., and Goldstein, T. Adversarial training for free! Advances in Neural Information P Processing Systems, 32, 2019.
Maennel, H., Bousquet, O., and Gelly, S. Gradient de- scent quantizes relu network features. arXiv preprint arXiv:1803.08337, 2018.
Shah, R., Pour, S., Tagade, A., Casper, S., Rando, J., et al. Scalable and transferable black-box jailbreaks for lan- guage models via persona modulation. arXiv preprint arXiv:2311.03344 2023.
Melamed, O., Yehudai, G., and Vardi, G. Adversarial exam- ples exist in two-layer relu networks for low dimensional linear subspaces. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Stöger, D. and Soltanolkotabi, M. Small random initializa- tion is akin to spectral learning: Optimization and gen- eralization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information Processing Systems, 34, 2021.
Min, H. and Vidal, R. Can implicit bias imply adversarial robustness? In Proceedings of the 4/ International Con- ference Machine Learning, volume 235 of Proceed- ings of Machine Learning Research, pp. 35687-35718. PMLR, 21-27 Jul 2024.
Sulam, J., Muthukumar, R., and Arora, R. Adversarial robustness of supervised sparse coding. Advances in neural information processing systems, 2020.
Min, H., Tarmoun, S.. Vidal, R., and Mallada, E. On the ex- plicit role of initialization on the convergence and implicit bias of overparametrized linear networks. In Proceedings of the 38th International Conference on Machine Learn- ing, volume 139 of Proceedings of Machine Learning Research, pp. 7760-7766 PMLR, 18 24 Jul 2021.
Szegedy, C.,, Zaremba, W., Sutskever, Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, 2014.
Min, H., Mallada, E., and Vidal, R. Early neuron alignment in two-layer relu networks with small initialization. In International Conference on Learning Representations, pp. 1-8,5 2024.
Tramèr, F., Kurakin, A., Papernot, N., Goodfellow, I., Boneh, D., and McDaniel, Ensemble adversarial train- ing: Attacks and defenses. In International Conference on Learning Representations, 2018.
Moroshko, E., Woodworth, B. E., Gunasekar, S., Lee, D., Srebro, N., and Soudry, D. Implicit bias in deep linear classification: Initialization scale training accuracy. Advances in Neural Information Processing Systems, 33, 2020.
Tsoy, N. and Konstantinov, N. Simplicity bias of two-layer networks beyond linearly separable data. In Forty-first International Conference on Machine Learning. 2024.
Vardi, G. On the implicit bias in deep- algorithms. Communications of the ACM, 66(6):6699)) 93,,,999355- 2023.
Pal, A., Sulam, J., and Vidal, R. Adversarial examples might be avoidable: The role of data concentration in adversarial robustness. Teirth-seventh Conference on Neural Information Processing Systems, 2023.
Wang. M. and Ma, C. Understanding multi-phase opti- mization dynamics and rich nonlinear behaviors of reLU networks. In Thirth-seventh Conference Neurul Infor- mation Processing Systems, 2023.
Pal, A., Vidal, R., and Sulam, J. Certified robustness against sparse adversarial perturbations via data local- ization. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Wong, E., Rice, I.., and Kolter, J. 7.. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2019.
Papernot, N., McDaniel, P., Wu, X., Jha, S., and Swami, A. Distillation as a defense to adversarial perturbations against deep neural networks. 2016 IEEE symposium on security and privacy (SP), pp. 582-597. IEEE, 2016.
Woodworth, B., Gunasekar, S., Lee, J. D., Moroshko, E., Savarese, P., Golan, I., Soudry, D., and Srebro, N. Ker- nel and rich regimes overparametrized models. In

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
Conference Learning Theory, pp. 3635-3673. PMLR, 2020.
Wu, D., Xia, S.-T., and Wang. Y. Adversarial weight pertur- bation helps robust generalization. Advances neural information processing systems, 33:2958-2969, 2020.
Xu, Z., Min, H., MacDonald, L. E., Luo, J., Tarmoun, S., Mallada, E., and Vidal, R. Understanding the learning dy- namies of lora: A gradient flow perspective on low-rant adaptation in matrix factorization. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 1636-4644- PMLR, 03-05 May 2025.
Yang, G., Duan, T., Hu, J. E., Salman, H., Razenshteyn, I., and Li, J. Randomized smoothing of all shapes and sizes. In International Conference Machine Learning, pp. 10693-10705. PMLR, 2020.
Zhang, H., Weng, T.W.., Chen, P.-Y.. Hsich, C.-J, and Daniel, L. Efficient neural network robustness certifica- tion with general activation functions. Advances in neural information processing systems, 31, 2018.
Zhu, Z., Liu, and Cevher, V. How gradient descent bal- ances features: A dynamical analysis for two-layer neural networks. In International Conference Learning Rep- resentations, 2025.
Zou, D.,, Frei, S., and Gu, Q. Provable robustness of adver- sarial training for learning halfspaces with noise. In In- ternational Conference Machine Learning, pp. 13002- 13011. PMLR, 2021.
12

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMS
A. Technical limitations of current results
We discuss here several technical limitations of our current results and potential avenues to address them. These limitations are listed in an order that the most challenging ones are stated first.
Requirement the initialization. The initialization requires a non-degeneracy gap A = (1)) this assumption aims to alleviate the challenges to analyze the activation patterns (1)20)))) along the GF trajectory. The activation patterns critically determine the gradient due to the existence of ReI.U activations in the network. Generally, as set of binary states in the GF dynamics, their evolution is hard to track unless the underlying training data has some special property, for example, (Boursier et al., 2022) assumes mutually orthogonal data, in which case the activation patterns remain constant throughout GF, and (Phuong & Lampert, 2021; Min et al., 2024) assume orthogonally separable data, in which case the activation can only flip one direction ("0 + 1" or "1 - 0"") for each neuron. Due to relatively more complicated data assumptions and the polynomial ReLU activations, there is no good technique to track the activation as of the current analysis. Therefore, we pose the non-degeneracy gap A (11) assumption the initialization, under which each neuron activates all the data points from its target cluster and none of the others, and the activation patterns are fixed thereafter. Future research on careful analysis of the activation pattern evolution can relax this initialization assumption.
As we have discussed after Theorem I, this non-degeneracy gap A = (1) generally cannot be achieved by random with high probability. Given that D 5a(a= ²),
initialization: the cosines between neurons and cluster centers are O VD
the actually non-degeneracy gap of a random initialization is Ōaa). We have discussed this issue when we define non- degenerate initialization in Section 3.2.1: When neurons are initialized close to the boundary between a Voronoi region R2 and another region R2, whether they align with μ4 with l4t depends on the actually sampled points in the dataset. In this regard, when weights are randomly initialized, there is "burn-in" phase during which neurons "choose" their target clusters depending on the samples, then once they get away from the boundary of these Voronoi regions with A (()) gap, can characterize the GF dynamics afterward by Theorem 1.
Upper bound on N. Regarding our requirement ((g5²) S N S o(exp(a)2))
)), we have discussed the lower bound N 2 Marg" ?) in Section 3.2.3. In fact, one can remove this lower bound and get a final bound Ö ao
in Theorem 1. The VN
upper bound N S o(cxp(ap 2)) may seem puzzling. This issue originates from ReLU nonlinearity: a data point must activate neuron by having a positive inner product. Our analysis requires that a neuron w is activated by every data point from its target cluster, which is translated into two conditions: 1) @(1) non-degeneracy gap; and 2) vlog Na o(1). Here vlog Nav is essentially the radius of a ba-ball centered at cluster center that can contain all the sampled points from that cluster with high probability. Without these conditions, there will be outliers in sampled points, which must be handled with extra analysis. We believe this is possible because those outliers will be rare and thus may have a negligible effect on the dynamics.
Extension to classification losses. Our results for the alignment phase directly apply to classification losses: the loss E(y. 5) only affects the alignment dynamics through V ())== and this quantity is same (may up constant scaling) regardless of whether L is exponential, logistic, lz. However, the analysis of convergence phase critically depends on l: Recall that in Section 3.2.3 we show that the nominal weight norm dynamics are ; = (1 =)2, = EjENi || 1 for lg loss. For exponential loss, the nominal dynamics become غ exp(-2)) whose closed-form solution is not available. A better characterization of the solution to the nominal dynamics of the type á = exp( 22) in future research naturally leads to an extension of Theorem to classification losses.
The choice of
Analysis until finite time T Our focus is on the distance between f(r) (()) and F(P), thus we restrict the time interval [0, T when we have explicit control of all relevant quantities (alignment, weight norms, etc.). To show convergence towards a minimizer of the loss after 7 we believe applying the results in Chatterjee (2022) suffices, following the approach in Boursier et al. (2022).
13

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
B. Additional Experiments on Learning Robust Classifiers for Data from Orthonormal GMMs
B.1. Experiments on the role of non-degenerate initialization shape
In this section, we conduct experiments to show the difference between random initialization and non-degenerate ini- tialization, with the main purpose being to verify the statements our discussions Limitation of our current result and Requirement the initialization that training with random initialization, while satisfying our non-degeneracy assumption, still find the desired robust network.
Experiment settings. We consider two types of initialization shapes (The initialization scale is 10-"):
Random initialization: the initialization follows Assumption 1, with entries of initialization shape wyyo / 1, ... all i.i.d. samples from standard Gaussian. As we discussed, this does satisfy our Assumption in nigh-diimensioal scenarios.
Non-degenerate initialization: We nudge the above random initialization shape toward cluster centers increase its -on-eegeyyyycy gap. Specifically,, for every j. we let wjo +- w (1----01-0000 where μ is randomly uniformly selected from one of the cluster centers μ4z k = 1, K. The resulting new initialization shape has non-degeneracy gap of roughly ò, thus satisfying Assumption 2. We also adjust the [uy] accordingly so the initialization satisfies Assumption 1.
Alignment v.s. Iteration
Loss & Distance v.s. Iteration
1.0
1.0
Cosine Alignment
0.8
0.8
Distance
0.6
0.3
0.6
0.4
0.4
0.2
Distance
0.2
Loss
0.0
0.0
0
100
200
300
400
500
600
100
200
300
400
500
600
Iteration
Iteration
Figure 5. GD two-layer pReLU (p 3) with random, small initialization
Alignment v.s. Iteration
Loss & Distance v.s. Iteration
1.0
1.0
0.5
Cosine Alggnment
0.8
0.4
0.6
Distance
0.6
0.4
0.2
0.4
0.2
0.1
Distance
0.2
Loss
0.0
0.0
100
100
200
300
400
500
Iteration
Iteration
Figure 6. GD on two-layer pRe..U (p = 3) with non-degenerate (6 0.05), small initialization
After the initialization determined, we run GD with step size 0.2 on synthetic GMM dataset of size 5000 with 0.1, and keep track of the following:
D 1000, K1 5, Kg
Alignment:
The alignment measures we are interested in are max; cos(p4, wy). 1, ... h, and our Theorem I and its proof suggest that they converge to close to after sufficient training time. For clarity, we report their median (lines), the 1st and 3rd quantiles (shaded regions).
Loss: The mean square loss.
(x)). We estimate this quantity by randomly sampling large batches of x and running projected gradient ascent on this distance, similar to (Min & Vidal, 2024).
Distantance to F(P); The quantity supesso-1 (f(P) (f(e 0)
14

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Experimental results. We plot the results in Figures 5 and 6. First of all, Figure 6 shows the convergence of GD under non-degenerate initialization (in both the loss and the distance F(P)). Then the same convergence happens under random initialization. However, the alignment between neurons and cluster centers is slower for random initialization than with the nudged initialization with 8 = 0.05 non-degeneracy gap. This agrees with our discussions in Limitation of our current result and Requirement on the initialization: having some non-degeneracy gap skips a "burn-in" phase for the neurons' directional dynamics.
B.2. Experiments on the role of parametrization and initialization scale
In this section, we provide additional experiments to that in Figure 2, highlighting the importance of parametrization of function space, and the hyperparameters of training algorithm in determining whether one can succeed in obtaining robust classifier for data from orthonormal Gaussian mixture.
Robust Acc. against 2 PGD Attack
1.0
PReLU (p-3) large init
poly RelU (deg=3) w. large init
0.B
PReLU (p=3)
poly ReLU (deg=3)
Accuracy
0.6
Bayes
0.4
0.2
0.0
0.0
0.2
0.4
0.6
1.0 Attack Radius
0.8
1.2
1.4
1.6
1.8
Figure 7. Given balanced orthonormal Gaussian mixture data with 12 positive clusters and 8 negative clusters (D = 2000), gradient descent (SGD, small initialization) on (bias-free width-200) two-layer network with regular polynomial ReLU activation of degree 3 fails to find a robust classifier. Moreover, if one increases the variance of the random initialization, both regular polynomial ReLU network and pReLU network can not find robust classifier. All networks here trained for sufficient amount of epochs until they achieve perfect training accuracy on synthesis orthonormal Gaussian mixture dataset of size 20000.
Regular polynomial ReLU networks. In this experiment, we consider both the regular polynomial ReLU networks to PReLU networks. In particular, recall that the regular polynomial ReLU networks defined as:
g(x; 0) = Σ uo w)))
@Ø 0= (w,, 23 11))
(Two-layer Networks with Polynomial ReLU activation with degree p) We note its difference with PReLU networks: regular polynomial ReLU networks do not have a weight normalization at the first layer. Nonetheless, when p is fixed, it is easy to verify that the function/hypothhesi spaces induced by PReLU networks and regular polynomial ReL.U networks are the same: any function f())( (æ: 0) for some 0 = {wy, my } is equivalent to g(x: 8) with = (w), |w 1/-1
Regular polynomial ReLU networks v.s. PReLU. Although the induced function/hypothesii spaces are the same, GD on regular polynomial ReLU networks and pReL.U finds classifiers with different levels of robustness. As one can see in Figure 7, with a small initialization (all weight entries are randomly initialized as (V 1 x 10-4)), SGD on a PRcLU network successfully finds a classifier that as robust as the Bayes classifier. However, SGD on a regular polynomial ReLU network fails to find robust classifier. This suggests that the way the function/hypothesis spaces are parametrized is also important in determining the robustness of the networks trained by GD, different parametrization induces different implicit biases of GD in selecting the loss minimizer in the function space.
Effect of initialization scale. Finally, when one uses a large initialization scale, where all weight entries are randomly initialized as (0, 0.25), even the GD on a PReI.U network fails to find a robust classifier. This is not surprising as the initialization scale also controls the implicit bias of GD (Moroshko et al., 2020), and many works (Maennel et al., 2018; Stöger& & Soltanolkotabi, 2021; Li et al., 2018: 2021) have theoretically shown the advantage of using a small initialization scale in GD.
'The neurons with ||æ || = 0 should be eliminated from the parameters for this argument to hold.
15

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.Mss
C. Optimal Robust Classifier for orthonormal Gaussian mixture
In this section, we discuss the optimal robust classifier for orthonormal Gaussian mixture. We first show that any measurable classifier can not defend against an adversarial attack of &2 radius v leading to robust error of at least _in(Kr.Ka) Then we consider the Bayes optimal classifier (*(x) = arg maxy IP (Y 2 y/(²) and show that it is also optimally robust: it can defend against any adversarial attack of lg radius x o(1), as the dimension of the data D increases.
C.1. Maximum robustness against le adversarial attacks
need the following lemma (we provide proof after proving Proposition 1)
Lemma 1. For any n x m matrix, let a be the number of rows that contain at least one non-positive entry and b be the number of columns that contain at least one non-negative entry. Then a + b 2 min(n,m.
With Lemma 1, we are ready to prove Proposition 1.
Proposition 1 (Restated). Let RD IR be any Lebesgue measurable function such that the random variable [d|ls min
{ (x - dd) y is also measurable. Given sample (x, y) ~ Dx,,, we have
min
2 d
min K2)
IP
min [d]]
f
1
0
(C.1)
K
Proof. We start with the following:
22
K Σ
V2 d
P
min ||lls]
f
a
+
d
y
00
P
min
f
x +
y
S 0 = = k
p =k)
(C.2)
2
||d
2
A=
For k < K1.
V2 d
V2
P min |
f
x +
y
0
k.
=Pe
min ||d 1
Mk + +
2 d
S
2 Pe
min Ki+k<sk
1/ + 14
+ E
50)
2
The measurability of f ensures this lower bound exists. Similarly, we have for K1 + 1115 K
v2 d
V2
P
min ||d|
1 00
k
P
min |d|[
Mh + 6 +
2 d
5 0
+
2 Pe
min
+ E
0
ISTCK
2
Pr
max
PR +
20)
1<KK
2
Therefore,
2
P
min
f
x +
d
0
||d|
2
V2
min
d
5 =
P(= k)
2
1=1
V2
1
IP
min ||d|
f
x +
d
y
0
2 =
K
1
16

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MSs
/ {1x0
v2
+
Σ
P
min l|d
x
d
y
s 00
=k)==k]
ki)
2
KItISKSK
PE
min KitisigK
Mk +
E
50)
2
ISbSKi
E KI+ISASK
Pe
max ISISKi
f 11m in
+E)
2 20)
2
Σ ISKSKI
min KittSIsK
{
+
Ml
+ +E)
50 p(E)
2
E
/
1
max ISISK
f
+ kn +
2 0 p(E)
KI+ISKEK
/
Σ 1SkSKi
1
min Kitssik
pkk +
+ + 30
(C.3)
K
2
Σ
max 1SISK:
f
[A
} 2 0)
p(e),
(C.4)
2
Ki+IsASK
and if we define the K2 x K2 matrix
1bk + p1 +E
My(E): :-
(C.5)
and examine carefully enough, we notice that EiSEek 1 IERSKI, KI+ISIK
[f (uetu + +e)] S 0) is the number of rows of
(e) that contains at least one non-positive entry and EKI+ISKK" (maxisisk, [f ( + s)] 2 0) is the number of columns of (e) that contains at least one non-negative entry. By Lemma we have
V2 2
f mink K
P
min |||
1
5
0
(C.4)
Therefore
V2 d
min K1, min{Ki, K2}
P
min |d|ls]
x +
>
(C.6)
2
K
Proof of Lemma 1. We denote C* C"(n,, m) the minimum value of a over all possible choice x m matrices. It suffices show C* (n, m) 2 min(r (n, m) (The equality is obtained by an all-positive matrix when n S and all-negative matrix otherwise), and we prove it by induction.
For n = 1.m = 1, C* m) 1. This is trivial. We need to show that if (n, m) = min(r, m) holds for some n and m, then
(" + 1) min (n, 1):
and (* + 1) min(n + 1, m).
We shall prove these two cases:
Case 1. Cn m) 2 min(n, + C² m + 2 min(n, m + 1}
17

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Given n. matrix M and agumented matrix M' M v/. let a, b and a' 8 be the row/column counts of interest for M and M' respectively. Without loss of generality, suppose the first rows of M all contain least non-positive entry (and the rest do not, by definition of a). We know that b 2 min(n, m). and
T
a
1(e, 50,
6' ='= b+ (mmax v 2 0)
(C.7)
which is
d'+ = + Σ
1(; 0) + 1mmx U; 2 0). 1=+1
(C.8)
There are two scenarios:
When a = n,, we have Eis4t1 10; 0) + 1 (max, v; 2 20
2. When < we have Eis4t 1(;; - 0) + 1 (max; n; 2 0) 2 211
Therefore, find that
d' + b' 2 min(n b 1} 2 min(n, min(n, m] + +1} = min n 1,m+ + +1 min +1. (C.9)
This shows C (n, m + 1) 2 (n. m + 1}.
Case 2. Cn 1,m) 2 min 1, m] C* 1, m)
min 1.
M
let b and a', 6' be the row/column counts of our interest for M and M' respectively. Without loss of generality, we suppose the first columns of M all contain at least one non-negative entry (and the rest do not, by definition of t).. We know that a + b 2 min(n, (nn m). and
Given matrix M and agumented matrix M'
a' 1mmin vs 0),
bb=
1(u; 0),
(C.10)
b+1
which is
+'' = +a+ Σ
1(v; 2 0) - 11 1min v. S 50).
(C.11)
1=b+1
There are two scenarios:
When b = m, we have Σm Li=bil 1(0; 2 0) 1mii, 02 S <0) 2
2. When b < m, we have Em 10v; 2 0) 1mmi, S 0) 2 1.
Therefore, we find that
d' + b 2 min(a + m, + b b min(m, min(n, m} + +] = min n n + 1, 1] mn + 1,m.. (C.12)
This shows C* (n + 1, m) 2 min(n- + m,
C.2. Bayes Optimal Classifier w.r.t. 0-1 loss
We first show that the Bayes optimal classifier is approximately a nearest-cluster rule. We have the following derivation:
sign (x)) sign
Σ
k=
Ki
exp
D (x)
a²
Σ
kk=Ktt1
K
exp
D (x, pak)
a²
2
K
D (x, us) (a.
)
a²
K
D (z, pk)
= sign
log
Σ exp
log
Σ
exp
a²
D
az
k=Kit1
18

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
max (z, + (log K a² D)). KitTSksK
sign
max ISkER
(w.
where the second inequality is due to the fact that a² D> log(-) function is a non-decreasing function, and the third inequality is because LogSumExp((21,," .2k) }) function with temperature di uniformly approximate max; & with error O( log K /) As we discussed in the main paper, this is a nearest-cluster rule when a² a²/ D is small.
We next show that the Bayes optimal classifier is robust. Our proof will use Hoeffding's inequality for high high-dimensional Gaussian vectors
Lemma (Hoeffding inequality). For any unit vector μ E 5D-1, we have
Dta
P eewr(u, (1 (K, e) > t) s 2 exp
(C.13)
2a
And the concentration result of the norm of high-dimensional Gaussian vectors
Lemma 3. We have
(-
1
P (
(1E)) > 1) S cxp
(C.14)
8a.
Proposition 2 (Restated). The Bayes optimal classifier w.r.t the 0-1 loss is sign (x)), where
(x) = Σ exp
K₁
D
(2.)
Σ exp
D (x, pux) (2x,
a²
a²
1=1
k=
K1+1
Moreover, given sample (x. v) ~ Dx,,, we have, for any
2vZa loo
SVS V2
D
v2
v
P
min
a +
1/ >0
|d|ls]
2
Dv²
2 1 - 2K exp
(C.15)
64a²
Proof. Bayes optimal classifier for Dx,y The Bayes optimal classifier w.r.t. 0-1 loss is given by
f*(x) arg max P (Y = y X = x))
K
arg max
Σ
P(Y = y 12 x X= x)
EK (Z = k x = x) E k
P(Z = à x = x)
1, O.W.
Ki
K
sign
P x - Σ
k
(C.16)
k=
Bayes rule and a few derivations give:
( = x 1= k) = k)
P(Z = k
x=
Σ (X x 7 1) (7 =1)
(_Dlla-pe -Dla--aall
exp
2a
K 1 exp
D - D (-
20t
D[[|=|| - 2 MAN
31)
exp
exp
2a
(C.17)
DC [c0] 2
2
p
pM [12)
((a
1= exp
2a
1== exp
19

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
Combining (6.16) and (C.17), we have
K;
D
K
D (D(z)
)
f (a) = sign
Σ oxp
Σ
cxp
(C.18)
a²
a²
k=K1+1
Robustness of f". We now proceed to show that
f is robust near-optimally. Since
v2
min |
/
x +
d
1/
00
K
22
P
min
f 1 +
d
y
$ 2 ==
p(z k)
||d 1
k=1
suffices to show that 41 & k S
V2 v 2
CDv2
min |d|l<]
fr
d
y
S
0
k)
k
s
K
exp
16a²
(C.19)
When &e S K1, we have
V2
P
min
y
0 2 =
[
2
V2-
P.
min
fz
+
d
50
||
2
D
v2 - v
(d, (d. us) )
Pe
min
exp
+
(Kk
E)
||
a
2
D
v22 -
(d, mi) )
Σ
exp
a
(m) +
2
(d. mi) )) $o)
D
V2
Σ Ki+TSIsK
exp
(u) +
a²
2
D
-2-v v
Pe
min
exp
1 (1k: E) +
(d, ppx
||
a
2
(m,e) + V2-V (d. pi) )) so)
D
Σ exp
a²
Ki+IsIsK
D
V2 -2
Iss
min
exp
1 (uk 8) +
(d, uni
|
S1
a
2
(d. (iهم ) 0o
D
V2 12-w
Σ
(((,))+ e) +
exp
a²
2
Ki+IsisK
D
V2-N 12-2 v
(d, ps) ))
P
min
exp
1+ EM +
|d 1
2
2
K2exp
D
KMI,))+
V2 -v
max Kitlsick
Kdd, Kd.pwii) wلهس
z0)
Kitlsisk
2
V2-V (d, mr)
PP
min ||
1+ ( +
2
20

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
a²
V2-
log K2
max Ki+IsIsK
(HI,E)|
max
Ki, mill $0
D
2
K. kitssk
V2
v2
I Pe
min || -
+
(d. m1)
max
1(d, pi)l
2
2
Ki KitisikK
2
Kw, K(,,e) =0)=
log K₂ - 1 E)1
max kitIsisK
(C.20)
1)
Since
V2
V2-v
min S]
+ 2
(d. (1)))
max
pid pi)
2
Ki KitIsisK
min
1+
V2 V (k)
V2-v
V2
-v
Σ
Kid
<|
2
2
Ki+ISisK
V2 V 2
v2 v
min 2
(d, (dd, 12+) 12+
Σ
((d, mil?
min d
1
|d]
1
1
2
v2
/2¹
KI+ISISK
we finally have
a
(C.20) - Pe
log K2 KKKk
max Ki+IsIEK
Km (w(, e)1 =)0)
V22
D
V
KM,, E\]l s0))
$ Pe
max ISISK
2/2
s 2K exp (-
2xxxp Dv²
S KPs
[((),))| 2
(C.21)
4
64a
The proof for case K2 + is almost identical.
21

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
D. PReLU converges to optimal Ez-robust classifier, Part One: Convergence implies robustness
We first show that FP behaves like nearest-cluster rule, which is critical for it to robust. Notice that
K1 Σ
o² (x)) - E 1o=K++1 ("(( maii))
K
sign
(x)) sign
k=1
Ex of ((xe))s))) 3) (1e pk))
k= of ((ax, (e
Ki
sign
σ (a, m1)) o ((x, (22))
To (ar, 1k(+1))
o (xr, (kx+)))
sign(
)
((2,, pkx) })_
When gets larger, the || llp is closer to the || Ilx. Therefore, FP behaves more like a nearest-cluster rule for large p.
We next prove Proposition 3 here.
Proposition (Restated). Let p Given a classifier f that satisfies f(yx) -f((x)) Yx E RD, by > and dist(f, p(P))= infaso suppssp- lcf(x)) p(r) (x)) $ v/ for some V S we have
v2 P.
Then for a sample (x. y) D x
v2 Sv2
P
min |d|l
+
d
y
>0
2
Dv
3
21 -1-2K 22 exp
4ex
(D.I)
2K2
8a
Proof. First of all, since f((x) = (f()),, Va E RD.yy > and the same holds for F-))(), we suppose the infimum is attained c* 0, then
sup
f(x) - [()(( = sup
|
x
(()
||>|||
x
|
S
|<>||>>
(D.2)
=ERD
=ERD
where the last inequality uses dist(f, ((p)) S v. With (D.2), we have
V2-
min
2 +
d
1/
50
[d]]
2
V2
8
min
f
d
y 00
[[d]]
2
min
f
22
81/
d
11
F(v)
2 +
v2- 8
11 + F(6)
x
V2 - Su
d
11 50
[|
2
V2
8
V2- 8
x V2- - Sut d y
<P
min
(()
d
max
c* x +
d
y F(p)
50
[
2
||
2
2
8
17
17
min [d]]
F()
d
max
c(f(2) y F()) Fz)())))
0, ||ج|| 2
+ P ||0||
>
2
I C9
2
2
8
17
min [d]]
F())
d
max 559
c2f(z) - F(P) (z) 0 +P ||0|| >
2
V2
8
+P ||00|| > 17
min [d||s]]
F())
d
5 3v
2
2
22

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMMs
The second term P (||=]|2>
17
is easy bound, our focus is to show
v2
8
CDv2 K2a²
P
min dil
F(P)
d
y
S
3v
2 2(K + exp exp
(D.3)
2
which resembles the result in Min & Vidal (2024, Theorem 1), but one can not directly obtain (D.3) from this existing result. Nonetheless, we can partially follow Min & Vidal (2024, Theorem 1)'s proof and obtain (D.3) (with non-trivial new derivations), as shown below:
Since
V2 - 8v8
IP
min
F(e)
d
y/
S 32
||d|
<1
2
K
V22 - 81/ d
7
P
min
F(n)
y
S 3u z= P(== =k==) k),
|d||s1
suffices to show that VI
S k S
/ SuP
CD82
P
min |d
F(n)
x
dl 11
S = == k
s 2K( 2) exp
(~2(K2 1)
(D.4)
When & K2, we have
V2
SU
P
min
F(P)
x +
d
y
S 3v 2 =
||]]
2
V2 SUY d
Pe
min 11
F(P)
x +
11
S 3v
||
2
V2 8u
Pe
min [|d] $1
1 (px E) +
(d) mm6
2
Σ oF (wiie))
-2-8r/ -
(d, mi)
2
Σ OD (InIE) + Ki+IsIsK
V2 -vF
(d, mid
S 53v 3v
2
-
< Pe
min ||d
o² 1 (pi,,) 8) +
(d, 1m6
<1
2
Σ oº (IIIEE +
V2 -
8v
(d, (d.
3zv
(D.5)
2
Kit1sIsK
We define the event
V2 g
:: 1 E) +
(d. mx) 2 V, SD-1
(D.6)
2
Then, by Min & Vidal (2024, Lemma 2),
V2. - Sut
(D.5) Pe
min
1 ()
(d, mok)
||d] S
2
Σ oF (WIIe)
V2 - 8
(d, mi) )
< 3v
Ki+ISIKK
23

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMMs
+ e) + V2 SuT
S Pe
min |]
oe
(d, p4s)
2
(mI.eC+ V2 Su²
(d. mi) )
Σ T" KItISICK
$ $34 E + PP (PE)
(D.7)
2
Since under event &, have oF [1 (eeke E) + v2-8ré (d. usi ceed with
1+ (pRREE) xZ-Suu (d, mni )
we can pro-
88²
(D.7) = Pe
min [d|ss
1+ 1+ (M),E) +
(d. (4))
2
V2 Su
(d, mi) ) E3
E T"
(WINE)+
+ P(E))
2
KITTSISK
-2=8
Pe
min ||
1+ (pA. E)
(d. 14x)
2
1 (d, ui) 1) ) 33 1
v2 8u
Σ
(ImIE))+
< 3,0-
+ +P(EE)
2
KITISIKK
1 + (pRte) E) + V2- Sut
Pe
min ||d|||
11)
1/v
Σ
(1ui))) +
V2- - 8u
v2
(d. (d. mi\l
P
+ +3v
3,0 +P(
KItISISK
1/8
22 81
V2 -
Pe
min ||
1
(d, uk)
Σ Ki+ISISK
(dd Ip)
2
:= MM))))
1/8
Σ
(( 1)" + 3v
| <0,8
+ P
Ki+ISIsK
S Pe
M*(1)
Σ
(Mi,)) - (30) - 144 <0 + +P(E))
(D.8)
KITTSIER
From the proof of Min & Vidal (2024, Theorem 1), we have M²(P) = 4v2u., Therefore we have
(D.8) P.
Σ
( + Ken, e) > M²(v) (3v)
+ +(E))
Ki+ISISK
2 Pe
Σ
(MiE)) + ( ()),,)) (4V2 - 3/) Dt
+P
Ki+IeISK
2 Pe
Σ
(miE)) + [ > V2vi +P(E)
KitTSIsK
24

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMMs
V20Ł
2 Pe
max ISkSK
[14, E)
>
+
+P(E))
K
V2Vē
DV K²a²
2 kPp
((1,)))
+P(89) 22Ke8 exp
+ +P(89).
K
Therefore, we have
v2 - 8
Dvr (T2aa²
||00||2 > 2
3 2
P
min ||
f
d
0
s 2K exp
+ +P +P((E)+ +P
Finally, by
P P(E)) PP
[(mEe) 8)1
2
V2
P
[(AEE))) E)1
2 2
S 2xxp
2D
5
25a
2
||0||/
17 2
S
|||||
2 2
17
-1
1)
< <eexp
17
1
S
4exp
(-3
2
Sae
8a
The proof is finished, notice that the bad event | >> 17 is chosen arbitrarily, so one can derive more general results by letting the results depend on the choice of a bad event. But for our purpose, we do not need it.
2
25

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
E. PReLU converges to optimal l2-robust classifier, Part Two: Basic results on neuron dynamies and good events
In this and the following sections, let ((t)) Cyys, f(P) (t))) denote the loss on data point (æi,3k), and V Vgli denotes the derivation of & w.r.t its second argument, the network output. Moreover, we let Ckj = cos( w) (t)) denote the cosine angle between cluster center 14 and neuron wi. Note: For simplicity, we drop the time dependence in (t), (t), (t), ((t), (1), (ty(t) and write 0 U/ w) L, l, Ckj whenever it is clear that they come from the GF solution thus depend on time. Note: suffices to prove the case a = ao, we thus use a to both denote the intra-class variance and the og we use to control the order of all the relevant quantities in our proofs.
We also let I {i: (Is 1)N + 15 kN), the index set of data sampled from k-th cluster.
E.1. Results on neuron dynamics
Neuron dynamics: Under GF, we have
dt
d
w
N
1
Σ
KN
V
Vglin Fj
plo((2,, wx w0;))
||00 ||-1 2. - (p -1)
(2,, w2
|| [00 11t1 w0
1
Vils pllar, w3
1 p-1 ni (p - 1) Kooks wP
100 wz
N
and similarly,
d
(1 w;))
Vgles
dt U3
||20 ||0-1
i: (m
Balancedness: We compute
d dt
/d. dt
(w) w,)
Wi. wi
1
Σ
Vols 2y
pplaar w;))
[|w, ||2-1 (p- 1)
Kae, wr w |--1
N
i: w, >00
2
Σ
Vgls 2ig
(1x2, w3)l
N
||-
and
dt
d
0j
2
dt
d
11
2
Σ
V Voli Uy
[x wr))
|w0, ||-11
1:(20, w,) 30
Therefore, we have
d T wj - 0z) 00
di w
(E.1)
thus w (t) - (t)) = = (0) -)) (0), Vt, since we have a balanced initialization such that w (0) (0),y(0)
0² (0), Vj. Such balancedness holds for all time t. Using this balancedness o² |w,]1² 11 Vj [hi] write
dt w,
sign(v,(0) (0)
Σ
Jgle |/5
(p) ((((
W
x; (p - 1) ((0)) Wi
w
(E.2)
N
[
|ww1]]
where we use that (ign(u,(t)) (t)) = sign( (0)), which is another consequence of balancedness Boursier et al. (2022); Min et al. (2024). We will study the dynamics of w from now on, and one can write the time derivatives of the norm and direction of these neurons:
26

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
Neuron norm dynamics:
d
||
dt
d
2
w/
w
dt
-2
sign vg (0))
N
Vgls ||w0||
(((22) ar
|
wi ))
2t) - (p (12e) |
w0
))²
1
||00|||
sign (0)))
20
)
||wy|1 - (p - ((
w
)) |/w,|||
-
N
Volk ||w
p
|w0
= 2
sign(v; (0))
Σ
Voli ((az)
w
||,,
(E.3)
N
|wo||
Neuron angular dynamics:
d w
dt
||,|||
=(1- 1-- w,yn ;
1 d
||,
[w || dt mn
sign(u)(0))
Σ ( 20
Vgll I
w
1wyy 12
((((0
p
Zs
|2,
w
p-1
x;
(p
1)
((Z))
|
wy
||20
(ign(u)(0)
Volip ((2 Dit
Wj
w
wy
(E.4)
N
w
[w
||,,,
())),,,)) 20
Finally, from the directional dynamics
d wi
we obtain
de 1
d ckj
wi
|k: dt
|
sign (0)
Σ
Vgle p ((22;
Wi
p-1
(1es, 22s)
F1:
W.
Ckj
(E.5)
N
00,)00
and whenever lexil * 0, we have
d log lcxil dl
1 d
ckj dt Ckj
sign(v;(0))
Σ 2(
Vole p
wi
P-1
(pane ax))
Mi,
wi |
(F.6)
N
|00
Ckj
Our proof has the same structure as prior works (Boursier et al., 2022; Min al., 2024): We will study neuron's 's angular dynamics (E.5) at the early phase (alignment phase) of the GF training, and then study neuron's norm dynamics (E.3) at the later phase (convergence phase).
Lastly, in order to prove Lemma and Proposition 4 in the next subsection, we need the following:
We let {μк+1.'.. }D} an orthonormal basis for the subspace that is orthogonal to span (1, ... 4k }. and we can define Ckj cos(1 wy k K + +,.... D. Since (pi,... "M,,".",,1)) " forms an orthonormal basis for the ambient space RDD.
27

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
have
D
Σ
W
1.
(E.7)
k=1
Moreover, write the same time-derivatives di Skjz and (E.6), respectively.
log loxzl for Ckj = cos( wj); k K 1, D as in (E.5)
Lastly, the following inequality will be used frequently in our proof:
Σ
layll &
Σ
= (1-
(E.8)
IEIED
Note:
The sum operation Eiee implicitly assumes I S K. We will explicitly indicate the range of if it can take values between + and
E.2. Good Event
For a balanced dataset δ = {x;, Vilizt notice that æ; = #1 + E, for some e, E N (0. good event w.r.t. these e;s and show that they happen with high probability: Lemma 4. We define the event Egood when the following happens:
(0. $1). We define the following
1. ||&l|| S / 8log 16KN a, VI VIsiS KN:
2. ((uxee)) S v log SK2N
VD
3. |1ET e:ll S 2 Nv N, Y1 skks
4. Σiezy |ley12 < 8log 16K N, VI <
We have P (Egood) 2 1 5. Furthermore, for simplicity, we write
log KaN 1. ||s S C
5 a, sISiSKN
2. [ C
log K VD
VI KIISKKNIISKE
3. IiEE, eill < C Vog z aw
Y1 s
4. ΣiEZ |l < C
Coo
R 2 N, V1 kk
for some universal constant C 0.
Proof. We proof relavent probabilities one by one:
1. By Lemma 3, we have
(-
12
P ((|e,]] 2 < 4exp
(E.9)
8a.
2. By Lemma 2, we have
Dt2
P (1) 21 < 2 exp
(E.10)
2a
28

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
3. Apply Lemma 3 to the vector ΣiEz. Ci have
t²
Σ
E
2t t
S
4xxp
8NN2
(E.11)
I
4. Apply Lemma to the vector that is the concatenation all Es N₂ and notice that its norm is equal
EiEI, ||E hence
t²
P
Σ
||:
2 12)
4exp
(E.12)
(NNa²
VEIx
Therefore,
16KN
8
" 1A 1A
|e:l 2
8 log
8 a
S
4KN
8K2N
8
E1)
2log
,
VD
4K2N
16K
Σ E
log
avN
8
4K'
16K
(- 12
8
K K
Σ
||E:||
2
8 log
N
<
4cxp
*8Naa
8
4K'
The union bound shows that PP (Egood) $ 1 -
29

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMss
F. PReLU converges to optimal l2-robust classifier, Part Three: Alignment Phase
F.I. Auxiliary lemmas
We need the following lemmas (proofs provided Appendix H)
Lemma 5. Given an initialization shape that satisfies Assumption 2 with non-degeneracy gap A > 0, then for j E No. we have
(1-1)² -1) do.
Ck2(0) = cos (,) V (1- A)²
(F.1)
(0)
S (1 22D)" = Σ2, vl + with yt = yk and (0) > 0
(F2)
Lemma 6. Letp > Condition on good event good Given some S k S K and some N₂ and suppose the following
true some point on the GF trajectory:
1. Ckj 2 Å
2. cbj
lay
(1- 4
Then the following holds:
d di cuj 2 pck 12(1 czj) Ci log
K oa
C2 max ( 0(1),,
for some universal constant C1, C2 that depends p. If one further assume Ckj 2 3. then the lower bound can be improved as
K a² J (1- (1 - ck)) C log
p-1 Ckj 2 pc
C2 max ( (2,)
dt
Lemma 7. Let > Condition on good event Eguos- Given an initialization shape that satisfies Assumption 2 with non-degeneracy gap A > define
la = inf (: max (660 (x;; 0(t) min 12 Â1)
12-1 22 11
11
(F33
20+1
2k2++1
Then the following holds S tiai
(1)(1) (0) 2 A VI < k KkjKj,jNN
(F.4)
and
2 (t)
10 (0)
S ÅΑ and + k.j E No.
(F.5)
(1)
Lemma 8. Let p > 2. Condition good event Eyous, then with any balanced initialization scale e S 4/hW2 the solution to gradient flow dynamics satisfies
max I
If (1:; 0())) S 2eVTW2 max
Vt <
log 20+2KK 20-1
(F.6)
The following lemma will be used to bound the time each neuron spends until reaching a neighborhood some data
Pk.-
30

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
Lemma 9. Let 2. Given some C O, for some z(1), the following holds
22202' Vt E [0, x(0) = 20. 2(T) = 21
(F.7)
dt
for some 0 < 20 S 21 < 1. Then the travel time T for z(1) to go from 20 to 21 salifies:
T
(F.8)
(p - 2)
Lemma 10. Let p>>>>>>>> 2. Gäven some C> for some z(t), the following holds
d 0(1 C(1- 2), vt E [0, T1, z(0) = 20, 2(T) = Z1
(F99
for some 0 < 20 S 21 < 1. Then the travel time T for z(1) to from 2g to 21 salifiex:
1
T S C
log
(F.10)
1
The following lemma will be used to lower-bound the time each neuron stay around the neighborhood of some data ptp.
F.2 Proof of Proposition
Proposition (Restated). Given the same assumptions as Theorem I and consider the same GF solution Ot), t 0. There exist some O (log 1) and t2 O (log ?) such that vk and jj No. cos (M4s w, (t)) 2 O(a²). Vt [21
Proof of Proposition 4. Breakdown the proofs We let
K 4= inf (: min min (ay(1) 2 C'log a
(F.11)
JENz
8
We define
Ap-1 12 - -1))
min
2 2 /hW2 max
A 12(1 - 22A
22 Vhw2
pÂ "za²
8y WTW2
1
20
2 log Clog a
Vh
exp
-4K
(p - 2)p
p(20-1 -
2)
(F.12)
Our goal is to show that if the initialization scale S eo (Notice that our assumption O(a*k) can satisfies this inequality), then
1. ming minjea,, (1) grows above C' log o before
20 f (p- 2 x(2 2 22 log C log $
2. Any ckyl (t) staying above 1 - C' Colog Ka² during [t, t2), where to = अ log 20-ii/he)
The remaining proof is to show them one by one.
Upper bound on f When 1 1 k < j E N₁ implies that wyo E R4 and sign(r,) = 1. We shall primarily focus on this case as the proof is nearly identical for Ki + < k < K. We prove it by contradiction.
31

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMss
14 [1, we have
A A2-1-2(1- A1)
A2-1 - v24)
max (2t) 0)1 S min
(By Lemma 8 and (F.12))
(F.13)
20+1
2k2
and
p-2
(x)(1) 2 A1
1 D2 41 j.j EN
(By (F.13) and Lemma 7)
(F.14)
2
kj
Suppose /1 2 4, then J E N such that 199 = inf(t: cwg (1) 2 - o > 11 However, for 0 S / I 41 we have, by
Lemma 6, for this particular k,
Whenever Ckj 2 Åι,
d
K a ja 10-11 22(1 - cnj) - Ci log
2 peks" The
C2 max (p 0(1),,
(F.15)
Whenever ckj 2
1 5'
d p-1
1
K a C2 max (( (mm: (())
dt ckj pd
1
(1 cky)
O2 log 8
(F.16)
20-2
Notice that by Lemma 8 and (F.12), we have
max (x; p Aga?
(F.17)
These suffices to show that Ckj will reach Coa 2
in less than ( time.
For some choice of C' and sufficiently small a we have: Whenever, á S ckj S V
Ckj
2 pckj
- 2e ckj)
C1 log
a² - C2 max (HT) 0(t)
dt
k
K
pckj p-1 A2
1-
Ci log
a
C2 max | (()) (mrs 0())
4
K a C₂
pÂp Ága
pccj 1-1 ÅΑ
1-
V
C1 log
8
4
p-1
Ag
1-
p-
(F.18)
5
20
where we uses the fact that Cjj 2 Å the last inequality. Whenever, / cvj S Co²
2
p-1 (
K a² - C2 max f(() (mu: O())
Ckj 2 pckj
20-2 (1 (1-ca)) - C1 log 8
dt
K
2 2((20-1 - -2)(1 -41) - --1 log
g a² - C2
max of (1:: (t)l
k
K
- C³= p "2aa
2 2 2)(1 cx)) - - log
a
p - 22 ck:)
(F.19)
where uses the fact that ckj 1 C' 2/ a² in the last inequality. The right- hand sides of (F.18) and (F.19) is positive, which proves that ekj is monotonically increasing before reaching 1 C' log /8 a² Lastly,
32

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
1. by Lemma and (F.18), it takes at most
20 time for Ckj travel from Å to
(p-2)pA,á)
2. by Lemma 10 and (F.19), it takes at most
2
log log aa²
time for Ckj travel from y { to Colog f
p(20-1-2)
Therefore, have
+ in (ty(t) 2
a²
1
2 log 1 (p - 2p Ap-2 p(2p-1 -2) Colog a = ii,
20
(F.20)
2
which contradicts our initial assumption that ezy > 41 Hence 1 I h.
Maintaining C'log 5 a alignment until & We have shown that at some t I f, all Ckj have grown above C'oo a?
5
Now we show that any Cky (t) stays above C log 8
K a between [h, 12]. suffices to show that for any S 12,
Ckj dt
00.
(F.21)
Ok ex-=--Olo Clo $
Indeed, the inequality (F.16) is still valid before 12, i.e.
dt ckj 2 peks' 1-1
) (1 - (1-ck)) --ck)) - C1 log a² C2 max (
20-2 )
K
8
k
K
C2 - "oaa
p 2) ckj) Ci log
8 a
Therefore, for some choice of C' and sufficiently small
d
K a Ci log fa² C2 p 4
K
"za""
Ckj lay=1 - Clog log 402
2 2 -2)
- log x
2 0.
(F.22)
dt
Hence
K a² vt E [t1,t2).
min min (ty(t) - 1 8
(F:23)
k JENz
33

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
G. PReLU converges to optimal Eg-robust classifier, Part Four: Convergence Phase
G.I. Axuiliary Lemmas
We need the following lemmas (proofs provided in Appendix H):
Lemma 11. Let p > Condition on good event Egond- Suppose the following is true at some point on the GF trajectory:
K 2 Vk,j E No: 1. (t)(t) 2 1 2C, log
8
2. ΣjENi |0,1 11 2 C. log a² vk;
3. EjEN: ||, ||= ö(a?).
Then the following holds for every 1 S k S K, Ix.
K
f(P)
(0 0) < Σ
|w,
1 1+2 0
log
a²
+ +2KCa";
8
JEN
K2N a
f(P)
0)
Σ
| 1|2
1 1 ApC
log
-2KCa"
jEN
Lemma 12. Let > 2. Condition on good event Egood Suppose the following is true at some point the GF trajectory:
1. (ty(1) 2 1 - -C, log a² Vk,j E Na:
2. EjENs ||2,,1 $ 1 C. log K a², Vk;
3. EjEN. |,,]12= ō(a²).
Furthermore, suppose additionally that for some j Ne:
K K a² < cky(t) <1 C. log 1- log
8 a
Then the following holds for the same k,
d Ckj 2 CK
K2N
a minu(p.4)
dt
8
Lemma 13. Let p2 > Condition on good event Egood. Suppose the following true at some point on the GF trajectory:
1. (ty(t) 2 121-2,,,10 log ka², k,j E Nn:
2. EjeNi |/00 - 1 Ci log aa,, Vk;
3. ΣjEN, ||, ö(a?).
Then the following holds for every 1 s k S K.
d
K a²) Clog J
(I JEN₂
Σ JEN
||
22 1 Σ
| +
||00s1 11?
di
JEN,
and
d
Σ
||
?
221-
22 1
Σ
| 1 C Clog K a²
Σ
||e0
dt
JEN
jEN
JEN,
where C some universal constant such that C Cun
34

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Lemma 14. Consider the same ussumptions as in Proposition 4. Given the in Proposition 4, the following holds LA k K:
(t)sl+))1 exp (- 2pp+2 K
Σ
W miin.. e
(G.1)
p(p 2)
JEN,
Lemma 15. Given some <
4' for some zt)), the following holds
d
2 (1 2 A)2, =(0) 20; 2(T) 21:
(G.2)
dt
for some 0 < 20 S 1. and 20
21 <1 - A. Then the travel time T for z(t) to go from zo to 21 satisfies:
1
T TS2 log 1- 21 A
+ log
-
(G.3)
20
Lemma 16. Condition on good event Egood: we have
100,00010=00 o(a?), T
T
(G.4)
JEN.
Lemma 17. the neurons {w,}}=1 satisfies the following for some S 8 S 1 and v, > 0:
max maxjeN, (t)(t) 2 6;
. 1 1- --EEENs 1|0 s
Ejeve SiENe//u2yy12 S.
then suPxesD-1
(2x) 0) (())(()))))))))) K(1 (2 1)28 Ku
G.2. Proof of Theorem 1
Theorem 3 (Restated). Let p> 2. Given < and a sufficiently small a assume the intra-cluster variance, the data
dimension, and per-cluster sample size satisfy that a² < ozj D Mayzz) and M(ap)) N < ((exp(ap)) respectively. Suppose that the initialization (0) is balanced, e-small (Assumption 1) with
θ (a and satisfies Assumption 2 with non-degeneracy gap A (1)) Then with probability at least - 8, the GF dynamics (7) with sampled balanced dataset D = {xi V1
KN ==
starting from (()), has its solution O(f) satisifying that: for some t = Ô (log d.
and T = L) + Ω (oo an
min (p- 2)2) with [t", + O, we have ((e(t)) Ō(()), VtElt" TT", and
sup BE(t -
sup
(x:; (())(x)) sō(a)).
(G.5)
Proof. We have shown in Proposition 4, and Lemma 14 that:
1. Any (t) staying above 1 - C. log aa² during [t,, t2];
2. Σjen, (1))l2 exp (-m 2p"12K
W Wiine 2, for every 5 K.
We define
2p K
41 +2
log (C-
+ log
(G.6)
K a² Co log J
p(p 2)
pp-2
W
min e
O(1)
C
T
t2 e(lg +
K max(a-xxppppp 8
(G.7)
log
Since c = = ((. For sufficiently small a, we have Olog 2 = 1" < T ((a-min(2-p--2) Our goal is show that
35

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMss
1. Before 7", must have maxg maxJEN, (1)(() 1 2Ca log & a² and ΣjENa [|w, < 1 C log a
2. Before T for all k whenever EjENs [10,(()) reaches 1 - Cw log
K 8 a², it can not drop below C log K a²;
3. After t", for all k one must have ΣJENE |wy) ||² 2 - n0 log K a²
We also have EjEN, |wyl" 1 1 o(a²), then applying Lemma 17 gives the desired result. The statement that C(() - Ō(a²) due to the fact that y/ - f(0) (a,;; (()) = Ō(a²) during [t", TT).
First claim: The two inequalities hold before 12, thus it suffices to study
T3 = inf
K t 2 12 : max max (Ly(1) S - -2
8 az))
h JEN:
K 1+ C log a?
T1 == inf
t 2 12
w 21+
jEN
and show that min T3, Ta} 2 T We proof it by contradiction, suppose min Ts. Fa) S T", then it must be either Ta min(Ts, r4} S 7 or 74 = min (Ta: T4} < T
Consider the first case that r3 = mTa {4} < T then there exists some & and j E Ni and some Ty- 2 to such that
K
K a vl [a)-
- 2C log x
a² S cky (1) 1 Clogg x
(G.8)
K a² cky(Ts) = 20 log
K a²
CTy(T3 )= C Cogg
(G.9)
since (t) is continuous and has to travel from 1 - Cloo x
K a 1- 201-2Clog 2C' aa By Lemma 6, we have
d Ckj -CK log
K
a min(p,4) Vt E [T3-
dt
8
Then by the fundamental theorem of calculus, we have
K -Clog log a² cT)(TT) (ty(T3-)=
1
TB d
T3
KºN min(p.4}
Ckj 2
-CK log
dt
T3-
K min(p.4]
=-(73 T3
)CK log
(G.10)
Therefore, for some constant C >
C
(Ts T3-) >
max m2xx22pp-22 (T3 - -t2) log K
max (2-p.-)
(G.11)
log
KaN A
[f2, T3] has length at least T3 S T The case one is thus eliminated.
thus is an interval that contains [t2, T*) Contradicting our assumption that log K2N a (2 pp-2) 2}
Consider the second case that 74 min(T8. T4) < T", then by the continuity of ||yll we know that there exists some k such that EjeN, (T4))l + C.,, log K a² However, by Lemma 11, we have, at Ta.
d
Σ ||, JENL
2
Σ
||,,11
K +C'log a
( 1100)112 JENZ
de
JeNi
=1+ C.n. log 15 K22
36

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
K (C- Cm log g
Σ JEN&
< 0,
which indicates that Eee,, |wyl" 1| can not surpass + C. log a² after T4, violating the definition of 74, leading to contradiction. Therefore the second case is eliminated as well. We must have min T3, TA) 2 T The first claim is proved.
Second claim By Lemma 13 (it applies to any - T given the proof in our first step), we have
(I 11ass112 JENE
d
K Ce log
K x²) C Clog
Σ ||m01 JENx
5 Fa
dt
ESEN' [w,112=1-Ca log a
2 0.
Therefore, whenever Ejen, [t)l reaches 1 c, log o/ a it can not drop below C log $ $a? The second claim proved.
Third claim Lastly, just need an upper bound on the travel time for ΣjeN, I|w 1 C log K a?, for which we simply combine Lemma 13, 14,and to see the travel time upper bounded by 8
(t)ll to go from ΣjENE 1 (t1)ll to
2p p(p-2) 29
2 log (C- Cw log a²
+ log Wa
(G.12)
min c
Thus ΣjENe [0,((()12 must reach 1 Cw log a² by 1"
37

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
H. PReLU converges to optimal E2-robust classifier, Part Five: Proofs for auxiliary lemmas
Lemma (Restated), Given an initialization shape that satisfies Assumption 2 with non-degeneracy gap > 0, then for j E N₁. we have
Cky(0) (0) = cos(p2 20)( 2 (1 -1-AY A)2 -1) d..
(H.1)
(0) kj
S (1 22A 22, vA + k with yr yk and (ız(0) > 0
(H.2)
Proof. We prove both inequalities by contradiction.
First inequality Suppose 0 < (O) cos (1 w (0) = cos(p1: Wgo) < Å., then consider who
wyo
and
ck:(()) (0)
い w
Ckj (M4 w0,))
(H.3)
Notice that here (0) = cOS( unoo) a UUKE Rx), and
(Me, mojo) It is easy to verify that (m,,i) = 0, V1 S S K, thus i
d wjo, O U Ra) =1
sup
cos (w50. w) S 21 - cos(tūjo, 2))
(H.4)
KEK
wEB Usex Ra)
Since one can compute
(w w
1 (0)
cos( ub)
>1
(H.5)
j (i
11+222
+ (0)
where the last inequality is due to assumption that (k)(0) < Å₁. Combining (H.5)(H.5), we have
w 0 U Rv.) d
< A
(H.6)
KEK
which contradicts our assumption that the non non-degeneracy gap is at least A.
E (()
Second inequality Suppose there exists an I & such that y yk and
(1 V2A)==2 and (0) > 0, pick
22 ((0)
the that has the largest (1²(0, (0), then consider 00
Wgo ||
and
Cky (0) (0)
wio
(Mu mi)
(H.7)
It can be verified that ||قح||| 1, cos( w) cos( w) cry (1)(0)a and cos(Mm, w) cos w.o) S cos(pt, w)) Vm A k or I. All of the above together implies vo E (ØRx) n (ØRi) c a(Urek RR), and
d (uyo. o( U Ru)) =1 kEX:
sup meo (Utek Ra))
cos (w w) < 11- cos(2ū w)
(H.8)
One can compute
(w w)
(cks (0) ct (0))2
cos (0: w)
| [
2
(U) 2
(k) (0)
>
2
38

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
2
p-2 Oj (0)
2
1 (1 - D2) 2
2
11-A,
(H.9)
2
2(0) (1)
where the last inequality is due to our assumption that
> (1 22
Combining (H.4)(H.5), we have
d
jo, o ((UR)) Rx))
< A
(H.10)
kEK
which contradicts our assumption that the non-degeneracy gap is at least A.
Lemma 6 (Restated). Let p > 2. Condition on good event good Given some S k S K and some E No and suppose the following is true at some point on the CF trajectory:
1. Ckj 2 Åμ
2.
Lay Ckj
< (1-V2) (1-V2A),
Then the following holds:
d
K o C2 max If (p:: 0(t)),
dt Ckj 2 pekp'D2l (ck)) C1 log
for some universal constant C1, O2 that depends on p. If one further assume Ckj 2 v B. then the lower bound can be improved
d dt Ckj pcks
K (1-222) (1 (x)) Ci log a² C2 max ( (x;;; 0)
p-1
k Kı.j E N implies that N4 thus sign(w;) 1. We shall primarily focus on this case the proof is nearly identical for K1 + t
Proof. When S <
d dl
Ckj
Vgli P (( Ii
| )>>
p-1
Σ
wi
(HeR, x..)
W.
Ckj
||00,||
I
Σ
(ye- - (x)) 0))
(x:;;
ati ||w0sll >)
(un, (x;)
w
Cke
N
100
=
N
1
Σ
yi ((
Øis |w,,]]
w
(pary xi))
|100
w
Cks
( 0)
wi
(Me,, (.;)
w
|
|000
Ckj
k(
==1's (will treated later)
Wi )
Vi (ar,
N
|
Ckj
IEI, (am,,))0))))))000
(a)
39

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.Mss
Σ
E
(
W p-1
))
(ues xi) - Cs:
W0
Ckj
+Ti
(H.11)
(b)
We handle these terms differently:
(a)
N
Σ
Vi ((
|
Wi
(eass 201) -
|100]
W
Ckej
IE
p-1
N
Σ
p
MAN + Eir
||20,|1|
w
(peRy Max + Ei)
pan eis
1|200
w
iELx
N KEIx
1
Σ p
( [k [ Es:
||20|||
p-1
ckj
(pete Ei)
Ess
||
Ckj
N
1
Σ
p
[kx + Eú:
||0
wy
p-1
Es:
|e0
Wi
CRi
IEI
Wi
+ N
y/s
+
Eis
(#eVe Ei)
T
:m I2 be treated Inter)
))
p-1 ( 1 --cū
un
wn
p
Ckj +
Ei ||2
Ei
Ckj
+ +I2
(H.12)
N
|w0
With the Taylor expansion
p-1
2 (H.13)
Ckj
+
Egi
W |[05||
p-1 Ckj
+ (p
1)
Esi
+
Es
w [w]]]
||w]]
where Rg = (p- 1)p 2)(e and SL between O and
(e:
w |
comes from the Lagrange residual. Clearly
|R1l < 2 p. Combining (H., we have
(a)
(H.12)
pokj (1 - -x2)) + (-pek, + + 1)ck-2(1 (1- (c6)))
W
Eis
2
(-p(p 1)ckk + +pR1(1 - c21))
wi
+ N
Eir
||22||
1ET
2
N pCks Rr.
Σ
w
W
+ r2
[wy]
SEIx
2 p0g 1-1 (2))
N
Σ 9
28
||e;
2P-3 p
||e: 11 + +
HEIx
VEI
iEZ
2 pcd 1- (11 (2g)
2
Σ
2x
p
|
2p-3 3
||= 11 max ||Ei|| +
N
N
TE
TT
K
K
K2N 3 + +122.
2 p
22g) Cp2
log
V
-2P-1
pppc 0
log
g
a
- 3p3C
log 8
(H.14)
40

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMSs
We leave the bound as the last one for now and turn to the other term:
(b)
-
1
Σ
W
))
p-1
j
Vi P
Fi:
Ckj
N
b
Σ
N
P
Cij +
Ei:
|err]] ||
CRj
N
1
E
Y: P
Ctj +
||00
>) p-1
(HKs Ei)
1ytk (EI
(will treated Later)
EE LEfk 1EZ
|ass+ (
Ei
[,,,
w
P >>
Ckj + I'3
(H.15)
With the Taylor expansion
(1asl +
(Ei
||w, >> layl + playy1-
w
20 +
>
w (H.16)
Ei.
Es.
Eio
2
where Rg p(p- (1001)((o]+4e)) and &L between and
(Ex,
w, ww,1/
comes from the Lagrange residual. Clearly |Rl] s
2 20 2p. Combining (H., we have
(H.15)
)p +I3
Σ 1
play Pckj N
p(p 1)(eu/ 1)(ey)1-7ck))
w/ Es.
PRicks (EL Ets |wo ||
w
|w0|1 ||
N
LAk TET,
IE
Σ 1#
play PCkd
p(p - 1)(cy) 11aypp--ca cas
Eii
w
)
K2p 2p" C2 log
K a² +T:
N
|em
17th TET
Σ k
play
P.cki
p(p 100 Ois (Ieilly 1 ch + I mmll)
log x K2P-2
K -a² + +13,
lifk İEI
K2N
log K a² l3
2 Σ
play P'ckj Σ pllcs p- cky C0,011100 log
ov 1 - 20-2pp7- p33 -2
8
1
p(p - l)(c,)/-te css (E m2)
== r a be treated Inter)
C4g p-2
19g P-2
K2N log
K K2 -K2--2p C² log x + [T +
pcks
[ayp" 12
p
lerg
C
a 1
p 2 kjj
8
1yck
1*k
ckj
lcg p-2
KºN
K a² + IT + +T
-pcks
1-1
xxtt
Σ
12
Eplaslyy
log
8 a
E21
K2 x20-2p"' 2p"C0 log 3
lifh
p-2
lylk
City p
K2N
K
-pcks
p-1
maxx lifk
p-2
Σ |ag 12 pC V
log
a
1 22
layl
K2P- 2 p² log 5
+ l'3 +1'4
1*
lz
2 -pck
p-1
max lifh
Cig 1-2 2
1ay1 12 /C|/ K log
K2N
a
1 -
cjj
|ay12
- -K2-2233 log a + +T +1
K
6
1*
lsfk
41

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMS
2
kj
p-1
max lifk
c
p-2
(1
( (1- (1-DC) (1-pcc klog 8
pCy
K2N
a(1 -21)
K =22= log 8
a
+ r3 +
[
2
P p-1 2
kj
max Lifk
ctyl p--
(1 (Z2) - K2p
K -a² + +4 0 log 0² log
(H.17)
kj
Finally, combining (H.14)(H.17), we have
d
cty P-2
K a
K 8
KºN
ckj 2 pckj
p-1
1 - max
(1-6k) (gj C/ V
log
C2 log
a
C3 log
8 a
dt
D-2
6 VN
kj
| - [2
[Ta - [rall
2 kck
p-1
1 - max lyf
Ciyy
p-2
(1-4k)
C/ V log
K a
C2 log
g
K
C2 log
K 8
a
D-2
8 VN
kjj
|T - [T2l
|ral
[[a],
where the readers should be able to find universal constants C C22 Cj from the derivation. It remains to bound these [ = 1,... 4. Indeed, we can find the following bound:
1 Σ
( 0) p ((Z2 1Di
wj
Fl
N
|
Wi;
[m
Ckj
w1)20,0))00
< max (
(o0;; 0)
Σ |p|0>;110 (2|
(,(,,,,))00
S p2 max (f()) 0),,
02);
1 Σ y P ( (n=+ + Ei ||,,
p-1
W
[Tl
(me: Es)
K2N a
Σ
p||x;|
KH4, S <p20-1cy '0/ log
N
8 DD
TT
p
Wj
TTl =
Y: Cij +
Ei:
N
||,,
lif
K a
p||00110*
p2 1144,
S D2p 120-111/ ov log 8 VD
N
1EI2
Td
p(p 1)|ay| cx I( pk)
N
lifk TE
K2N a 5 vD
< N
ΣΣ
p² Kee si)i S Kp²C log
I
NET
With these norm bounds, we have
d
ckj
di
C-ylp-2
K a
K log 8 a²
pcks"
p-1
1
max lsk
p-2
(1 cZ2) -CV
log
8 VN
cjj
K 3
K2N
- Cr' Log
C/ max ((ا) (x;; 0)1 - -C'y
log
8
DD
42

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMSs
2
kj
D-1 kj
1
1
max 1
(t p-2 (ayl8~2 --2
(1 ckz) - C1 log
K a² C2 max ( (z,; 0)
Lastly, our bound is
When we only assumed ckj 2 Åi:
d
1 (1-
1-mma
layl p-2
K a² C2 max (x)) 0) [kck)) C1 log
dt ckj 2 peks
l
cki
8
K max ( (z.;
2 pckj 12 ckj)
C1 log 8
aa² x
2. When we further assume Ckj
5+ we have that Eiex cij = 1 ckj S 5. then max las S V Therefore
-cg
1 - max Ip
City 1-- D-2 kgj
mmxx/f lcts
P-2
1
1
2
(H.18)
Ckj
2P-2
which leads to
K (1 - (1-cuj) C1 log Ja (1- 2p-2
di ckj 2 pcks
O2 max If (x;;
Lemma (Restated). Let p > 2. Condition on good event Eyoud- Given an initialization shape that satisfies Assumption with non-degeneracy gap A 0, define
laa = inl {1: max ( (x,;; (z;;; 0()) > min { A 10-1 12 - (1) A '2 22
1}
(H.19)
20+1
2k2
Then the following holds S tiai
(t)(t) 2 (k2(0) 2 A V1 <K K.. No.
(H.20)
and
(2- (1)
12- (0)
< ÂΑ and VI + k,j No.
(H.21)
Proof. When S < K1.j Ng implies that E N thus sign(v,) 1. We shall primarily focus on this case as the proof is nearly identical for Ki +1 1 l K.
Overview of the proof: We will prove by contradiction, we let == inf 3kgj E No, s.t. (ty(t)
< Cky (0)) and
T2:= : inf t j E No. &el # k. s.t. (0)
( oky f by the continuity of every exy and every (t)(t) on the
[0]]
(1)
of (m))
of (0)
interval mI] and [0, r2] respectively, we know that (T)( = cxj (0) for some k,j j and
for some
(F2
ek, (0)
k, If min( ) > tia then there is nothing be proved, otherwise, there are two cases:
1. When min(71, lia we show that for the k.j such that (L)(n)) (0)
d
Ckj
2 0,
(H.22)
dt
which says (n + At) 2 (0)( for every sufficiently small At, contradicting the definition of TI-
43

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
2. When 72 (TI, S tia, we show that for the j, such that 1y (ma)l
10) (0)
(6)(7)
(0)
d
|all
log
00
(H.23)
dt
Ckj
t=t2
(e)(+++A0)) which says Oky (71+)))) S (0)(0) for every sufficiently small At (due to the monotonicity of log function), contradicting the definition of 72-
Time derivatives of log cosine angles We have shown in (E.6) that for every S I D, whenever atyl 0,
log |cy
dt
1
E
VoliP
((
W p-1
)
Dis
w
N
|w0|
(ne,, xei) Cj
Σ
V
Sgi
N
|2w|
w0 (
p
N
Σ
V Vgli p
(
|wo
2: )20
Case One: tI min(TI, T2).
This case is relatively easier as have already shown Lemma 6. For the k, j such that
Ckj A
d ckj
K a p2 max (f(m) (xx 0)1
2 pcks
Ao(1 - -ka)) - C₁ log
dt
8
t=n
by Lemma 6 (conditions satisified at t Ti and one should be able to get (*) using the intermediate results in the proof of Lemma 6). Then
d dl
K 2
2 P (1 ÂΙ) C₁ log
p2
max ( (x0,; 0))
Ckj
t==i
(T Stan)
K 8 a
2 p p-1 á (1 - -,) - C1 log
K a 2 0,
2 - 5 -Ā) - C1 log
for sufficiently small a.
14 (r2) 1c, 2
Case Two: 72 = minff1, T2). For the k. j. such that
have (although omit the notation, all the derivations are at 72, so that Cr can appear the denominator of fraction.)
(T)) (0)
d
lcisl
log
dt
Ckj
d
=
di
log |ayl
dt.
log Ckj
Vgli ((zz)) ( |
wi
(1 x3))
(He xi))
Cii
Ckei
difos )
N
1
Σ
(ys (x,)
(x;;; 0))
Zti
||,
w
p-1
Ct
(pak, I.)) Ckj
44

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
p-1
(pi (1))
(JRR, wi/
Σ
yi p
N
Clj
Ckj
p-1
(uur 2k.)
(HR,, 2t1)
(a:;; 0)
|
cij
Ckj
:
1
Σ
w
p-1
(ML M4 + Ex)
(pen M4 Ex) okj
N
1/4 p
P2 Eto
|/200
aj
w,)
1
20
(pi p4 + Ei)
(#eRss pi + Ei)
N
Y/
p4 + Ess
|20y1
ct
ckj
(EZ::(0,,,))20
Σ
Σ
yiP P (( pe
( Eii
wj
(mi Me + E.)
(uen pe + +Ei)
+Ti
||w5
Cij
Ckj
KK 127,:(20,00))000
1' tk
1
Σ
W
p-1
(Mi Ei)
y
Ckj +
Edi ||wy|
+
N
Ckj
Ci
Ckj
VET (,, )20
1
Σ
P
Ctj +
Eis |w
p-1
1
+
(m 8i)
(un;EE)
N
Ctj
Ctj
Ckj
iEI:(1;,15)20
Σ
Σ
w
(1i Ei)
(eens Es)
N
DiP
Cry +
Ei,
||mr||
Ctj
Ckj
+
IK t0))))0 1'fL,l' A/
1
Σ
wj
))
P
Ckj +
Ei: ||w,
N
Ckj
1
Σ
Yi p
Cij
Eir
w
>)
p-1
Ii + T2,
(H.24)
w
Cijy
We view T1, T2 "perturbation term" and will control their norms later. For the first two terms in (H.24), we have, respectively:
1
Σ
W
P
Ckj
+
E
N
CRj
P
W
p-1
1
Ckj +
Exi
N
Ck:
TE
p-1
Ess
P
p-2
N
kj
Cku
IET
p-1
Ess Tw
P
2-2
N
kj
Ck.j
IEI
p
2-2
1 (p 1)
Eti
Tw
w0
N
kj
Ckj
iEI
max; ||eil|
4K2N
< --pcp= p-2
+ p(p
2 pp p-2 + p(p
1)/8log 8log
(k)(
5
45

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
and similarly,
1
Σ
w
p-1
1
yi P
Ctj
Eis
N
[
Ctj
iEZr:(e,,,))>) ue )20
p-1
wy
Σ
1Mal |oy p--
1+
Es:
1|
(2T,:(2,,,0))20 20,)300
6in |0, w
$
P N
Σ
lasl
1 (p - 1)
C1j
(6I)((r,,,))20
2 playy p=2 + +p(p
4K2N 1)
151sK K K<lsD
8
0,
Therefore we have
d
log
ctjl Ckj
< -p(ck] 2-2 -lc1 1051p-211 (1-=)) + +2p(p 1) 8log 6
4K2N
[
F2
dt
4
S -p(ck
2 lcy 2) +
2p(p - 1)1/ 8 llog
[11
1T2
5
1 |e,1| P-2
4K2N
S ppokj
2p(p
1/ 8 log
a
T1
[22
ckj
p-2
4KKN
S 2-p + 2p(p
1)v
8log
- [Tal
T2].
remains to bound these [[1], [Ta]- Indeed, we can find the following bound (note that at T2. we have layl = (1)(1) and Ckj 2 Å
1
(x;;))
((12)
Dis
w
(uss xia)
N
|,,,
Cij
Ckj
1
(2(:( p
w
(pa,, ax))
Dii (ww))
N
Oay (1
v24
Ckj
ISKKN
Kp2p+1
(raStiu)
S max (xx;
S
pPå p- Az,
Å
22
W
(p))
(uR)Es)
T2
N
PiP
Ei,
|unyl]
Cij
Ckj
is(mn;
Σ
W
(m,, Ei)
(AAK: Bi)
<
N
p
Dis
||w,|l 11
Cky(1 22A
+
Ckj
ISISKN
Ky20+1
CKp2p+1
K2N
I max (M) inke
log
Á -22)
A V2A
8 VD
Finally, we arrived at
d
log
Ckj
t=
'I may take some time to recollect terms we omitted in (H.24) and regroup them into T2
46

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMSs
2 -pāp 2 Ω + +2p(p - 1 8log a + - +
4K2N
CKp2
K
a
log 8
A (1 V2A)
VD
1 -ー 2 + 2p(p 1) 8log S
4K
CKp2Pt1
K
a
a +
log
(H.25)
8
Á1 V2A)
8
VD
for sufficiently small a.
Lemma (Restated), Let p > Condition on good event Egood, then with any balanced initialization scale the solution to gradient flow dynamics satisfies
4yhW2
max (g(] (14R; (())) S 2eV/W2 max
VI S 20+2K
log /he
(H.26)
k
Proof. Let T == inf(t: max; (1(xx;;;10) > 2e m. then V/ S TT E [b]] we have
d
|wy1 2 -2
(1))(
Σ Voli (( 2i
w
|w,,| 12
di
N
|00|
w,)00
1
KN
(1z), w2
[w,) 12"
1 KN
V /g/////,////1/0111
N
2 KN
Σ
(1 + (f( ((t))Dll
N
20+1 KN
Σ (1 + 4ev hw2 max 1/w, 1|
N
< 2 [(1 + 4ev 7w2 w 1 1|
(H.27)
Let ry = it [t)](
2² 2- vh
and let jr == arg miny Tj. then Ty- miny Ty S T due to the fact that
(1w,, )2))²
[f(x000]=
Σ
2
ww 112 < 2 max
|w,
|1w, p-11
jE(h]
JElM]
JE(M]
which implies "Is(sx; 0(()) > 2 v Tw2 max
eWa 24 1/h
Then for t S Ty-, have
d
di mm--1 112 S 20+1 K(+4eV/WW (2ax)) 1|200- 112
(H.28)
By Growwwlll' inequality, we have Vt S Tj-
(t)l < exp 22 K(1 + 4e hhw2 (/Wh (0)])
(20t1K] K(1 + v Tw2 m )1) 62 01
exp
S exp
(20tIK( K(1 + / hw2 2 2
(20+1
Suppose Ty- I log 12--i/h (v ). then by the continuity of |/,,- (t)l we have
2eW2 max < 1|w-- (12=
)|² < exp (2 K(1 + 4ev devhn 4evhw2 m )Tx e² w2 max
2p-1
47

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
< exp
2 [(1 + 4EV hev
log
1
2 max
max
20+2
20-
Vhc
+ 4e kev
1
< exp
max
log
e22
2
2p-1
max
28 1he )
cW2
S exp
log
W
max
max
2D-1 1V
which leads to contradiction 2e S Therefore, must have T 2 T3- 2 2012K proof.
log
1
This finishes the
2" Vhe
Lemma 9 (Restated). Let p 2. Given some C' > 0, for some z(t), the following holds
d
dt dt=² == E [), x(0) = 20. x(T) = 21
(H.29)
for some 0 < 20 S 21 < 1. Then the travel time T for z(t) to from 2o to 21 satifies:
T
(H.30)
(p 2)C2 2-
Proof. We have
C2p-T dz 2 / di,
(H.31)
-0
thus
1
1
1
T 2)C
S
(H.32)
p-2
of-3
(p 20-2)
20
Lemma 10 (Restated). Let > 2. Given some C >> 0, if some z(t), the following holds
J." 0(- V (0, 73, =00) 20, 2(T) 21
(H.33)
for some 0 < 20 S 21 < 1. Then the travel time T for =t)) to go from 2o to 21 satifies:
T T 0
log 1
(H.34)
Proof. We have
1
d2 /"
T
dt.
(H.35)
C(1 2)
0
thus
1
1- 20
T <
log
< C
log
(H.36)
C
1
1-
Lemma 11 (Restated), Let p 2. Condition on good event Egood- Suppose the following is true at some point on the GF
trajectory:
1. (t)(t) 2 - 1-,,, log K Ka², Vk,j E No:
1 2. EjENi 12 Cw log Ko² aa, Vk;
3. EjEN, |,, [m, ö(a?).
48

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMS
Then the following holds for every 1 S k S K, Is
K2N
(( (xg; 0) - Σ
||wy11 112
| 1+ log
a²
+ 2KCa";
8
JEVe
1 11 1 ApC
K2N
f(P) (xg
0)
||w /|
log
a²
2KCa
5
JENL
Proof. Our proof ignores terms related to neurons in Nu as they only introduce a o(a²) perturbation.
f f(P)
(a;; ))
h
[ xii)
[1y 1|--1
==
((
||
W 1|20r
w
P
((
Σ ||0z11
W
Σ
23:
2z
JeVr
lif JEN
Σ
||0511
Ckj +
E:
Σ
| 11
C33 +
w
(H.37)
||w
|
JEV
JEM
Upper bound:
((0) (3::; 0)
(H.37)
K
m )13
S
||,,,12
(oks +
+
Σ Σ Te JEM
| ||asyPP00 18o00
(ss
+
||,,||
wi
E:
JEN₂
(a)
(6)
For the first term, we have
(a)
||m,|12 ||2
1 + ||::ll / 1 - 2g +1 (a)k:es)] ea)1 1)"
JENN
||
1+ ||=:|| V 2(1 -cxs) + 14 E,)
JeNL
P
K2N log 5 a² + CV log
K2N a
1 1+20 ||, ||
8 D
JENL
K a 8
| 2|
1+
log
JEN
for sufficiently small For the second term, we have
bb) 2 2 Σ
[ayl +
E/ |wy|
1#
< 2K
Ei) (p)m) (v2(1 cxj) + |1eilly 1 (11 ckj) + (mi 8x) 1)
(V1-ch + ||=:|l / 1 - Eg + (nr,,
1)
$ 2K
49

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
KºN - 2k Ca Caa CC
K a Cy ô VD
a²
S <2KCa.
(H.38)
Therefore
K
(( (x 0) 5
Σ
||m,11 1 2
log
a²
+ 2KC
(H.39)
8
JENL
Lower bound:
[(P] (3:;; (1p)( 0)
(H.37)
w (1 ))
|ayl1
Ckk
Σ JEN;
2w 1
cyj
|20,1 E,
w
JENr
(a)
S(1.38
For the first term, we have
- E.) )) P
(a)
|00 1|
[1-leelly 2g -ku
JeNL
Σ
||,0112
1 ||:il|
2(1 -cas) - 1(
JEN
K2N
K2N
Σ
||/p
- 20
log
CV log
5
5
JEN
K2N
Σ
||,l1²
1 1 4pC
log
a
8
JeN&
for sufficiently small a. Therefore
(()) (x;;0)
2 2
Σ ||,,|1
(1p(1-11
(1-40C1io log
4p01
K2N
o²
2K Co.
(H.40)
5
JEN₂
Lemma 12 (Restated). Let p > 2. Condition on good event Eyood Suppose the following is true at some point on the GF trajectory:
1. ct((1) 2 1 - 1-10 log Kaz, Vk,j E Nsi
2. EjeNi |/w/1 < Ci log //2 a², Vk:
3. EjEN. ||,, ō(a²).
Furthermore, suppose additionally that for some k. E Ne:
K 1 1- log Ja² s (ny(() 21- C. log 7 a:
K
Then the following holds for the same k,j.
d
KºN min
dt ckj 2 -CK log
50

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Proof. When < k K Ng implies that j E E thus sign(vy) proof is nearly identical for K1 + +lsksk. K.
1. We shall primarily focus this case as the
d
Ckj
dt
Volip (( Ti:
Σ
wj
(Jun x.)) - 27:s
N
|
||20g]
2: 22,
1
Σ
(ys - (I
(o);; 0)) p
w
p-1
(peRs x(a)
2
Ckj
N
|w0)
20
( 20,)30
1
1 -
| p
Zi.
(p), x.i)
1i
w
Ckj
N
[w
jENo
(a)
((
>)
p-1
|2,112
g(v) (20e; 0)
(Mis x.))
W
p
Ckj
N
(wyy)
1ET
JEN
(b)
Σ Σ
N
(yi- f(z) (x:;; ((z))
Twy|l
w
p-1
(HR: D.))
|[w]1
w
Ckj
(H.41)
We deal with these terms one by one:
Since ΣjeNs ||05112 < 1 + Ca², for (a), there are two cases:
1. When 1 - ESENs ||w 2 2 0, Follow the same derivations from (H.12) to (H.14), we have
(a)
Σ
||2
1 N
Σ p
((20 Eii
[w; ))
Wi
(pek: (x:)
2/
W
Cki
|ww
JENL
iEI,
K
K -28 -2-1 0 C log 8 - o(a2)
Σ ||
prkj (1 - -(t) - -pp log
VN
JENr
p(1 - Ca?jo-1 pl1-Ca?jo-1 Caa (Ca2- -Ga))) -Op² Σ ||,,
K
K
logg
-2 12 '22 0 log a a - o(a?)
/N
JENr
for some choice of C and sufficiently small a.
2. When -Ca² s 1 - ΣjEM, ||w0,1² 112 < O, we have
(a) 1- Σ
||,
1
Σ
p
((
Ts:
P-1
(us 2ii)
0i;
| || Wi
Ckj
N
JEAi
IEI
Σ JENr
||u 1|
N
Σ p ((Zz)
Dig
||00
wi
p-1
ch
(pek, 1+
Es:
Ckj
TEIx
Σ JEN
||w 1
p2--1 (1- ch + 2| (min Ei) + ||eill c2,
51

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
K2N a
2 CV log
(H.42)
Therefore, we always have
KºN
(a) 2 C log
8 a²
(H.43)
The second term (b) is easy: by Lemma 11, we know that Ejen. 11,,11 - f(r) (x;;:) a similar derivation as in (H.42), we have
=O(ylo log KºN a then by the
(b)
1 N
Σ i
Σ JEN
|10
f(z) (or;; 0)
(x);;)
p ((( a wwy
))
p-l
(HiRs mi)
Fi:
||20
w
cki
Σ
||0
( 0)
N
Σ p (
|
p-1
2xg + (eek E2) |+
(
Ed:
|e00
w
cks
JEN&
TE
K2N
2 Clog
α
(H.44)
For the last term, we have
(c)
1 Σ
Σ
(y:- p(0l (x;:))) p ( Zii
|20,11 ))
w
(p), 20,)
Dz.
W
Ckj
N
2
p ctj (e:
|u0,]| >>
w/
p-1
(uR. ei) + cssee +
(
w
N
Eii
|00g|
Cki
P (V1- - Eg. + +lsill 1- ctj) p-1 (muR Ei) + 11 Cn cks + ||3:ll 1 - ((2
GE IE4
K2N
2 C log
8 a.
Finally, we can conclude that
d
K2N
dt Ckj 2 CC log
8 o min[p,4)
(H.45)
Lemma 13 (Restated). Let p > 2. Condition on good event Eyood Suppose the following is true at some point on the GF trajectory:
1. (t)(t) 2 1- 1-220, log a k,j E Nai
2. EjEN, ||uu,112 1 + Cw log K aa,, Wk;
3. Ejev. 12, =
Then the following holds for every! 1 S S K.
d
K a²
(I JEN&
Σ
112
22 1- Σ
|uy 1 +
Clog
a²
||00
di
JENU
jEN.
and
J a² ) K |2 2an -C Clog
d
Σ
1|?
2 1 - Σ
2-
Σ JENz
||0001?
di
JENU
JEN.
where C some universal constant such that C < Can
52

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Proof. When S k S Ki.je E NN implies that j E N thus sign(wy) 1. We shall primarily focus this case as the proof is nearly identical for K1 +1 - k < K. We start with (E.3):
d
|1, 12
2 N
Σ
(yi (20) 0))
||w
df
||w,,
;(201,0,)100
(yi - f(P) (2);;; ((
Σ
2
N
|00,
(a)
(yi - ((P) [ 0)) (( (zi
))² P
Σ E
w
||w,
N
|w
For the first term, we have
(a)
1 N
Σ
(yi (xx) 0))
((
(wi
||mry]
VEIx: 20y1>0
1
Σ
(1 p(0)
(a:;;
0)) 0)) (( Fib |/w/l
N
iEI#
1 -
Σ ||
|000||
W
Σ
Σ
|w 12o"
(azz)
|00,
W
Ci
|003
JEN
JEAS
1
Σ
|,
((
Dig
|
wy
((
xi
||w,|||
Wi
|
||00
un
N
N
TE
JEN&
TET litk JEN
P |1n;11 ))
N
Σ
1 -
Σ
|,
Ckj +
ein
||m
wa
cuj
+
Ei:
+ r2.
JEN
We shall focus on the first term. With the Taylor expansion
Wj [wm]]]
))
wi
wi [
ckj
+
Eii
cg + prkk'
Ei:
+ Rr.
E::
(H.46)
|20.1
where R₁ = p(p- 1)(e)) and Çr. between 0 and (ei we
comes from the Lagrange residual. Clearly Ry
2F-2 2p-2p². Then we have
N
1
|w, 1|2
Ckj +
++(8)) Eis
||,,
))²
P)
Cks +
Ei
|wo]
W
))
TET
JENN
Σ
kj
JENL
pcks
2 Σ
||,,
Ckj
2p-1
1
Eii
W
N
|w,]
JENL
SET.
53

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
2p-2 RR - pk 22 Ru)
1 N
Σ
)
| +
wy (((e
(2)
Ei
||00||
i
Finally, we ready to derive the upper and lower bound. For lower bound,
|wyl1 ||
dt
2 ((a)
I1)
||w/|2
2
N
1
1 Σ
||0l11
Ckj
Es:
||00
Ckj +
Ei:
W
P
T
[T2l
||00,) 12
IEIx
JEN
22
Exi
|2
112c03
CIN N
Σ Eis
(ww)
w
C2
N
1
Σ
Es:
|wwyl
II
JEN
TE
(K 6is |100
1)
wj
-|ril |T1|
- |[21
||20z11
K a
K aa² -aa²= oaaa) - - [T2] ||wr112
22
kj
|0,11200
Cvlog
log
log log
6 VN
JEN
2
Caa
Σ
||,1112 - CV log
a
C2
K 8 - o(a2) -Iril - |T22| ||[2l
||w0
2
i VN
JEN
Co
K a
K a² o(a?) - [Tl - [22 ||,
22
1 p
Σ
||, -
c. log
- c2 log
2
8 VN
8
JEN
It remains to bound these
T1 [T2]. Indeed, we can find the following bound:
(( ((z2) |
F1
Σ
(Bi- - f(r) (x)::))
w
N
ht tEI =0
101 - f(P) (2;;; (( Zii
wj P
N
17E IET
2
w
Tii
||000
2
||203||
YEI,
2
Cii
Eii ||201]|
N
VEL
18fk
2
V1 1 + |leill / - ci. + (m)r
KCa,
N
VEI
lsck
||, 11220 (( 2i
ΣΣΣ
w
22
N
|w,]|
iEI 17 JEN;
54

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
))
Bi
w
PP
N
iEI
Therefore,
d z
K C log 8 aa²
|10,11
2 2
1
E
||w
||,,|l 11?
JEN.
since when a is sufficiently small, the dominant term is of order a² Similarly, for the upper bound, we can have
d
1zyl
dt
2 ((a)
+
K vN
K
$ 2
Σ
||wyl 11 11/c0p3 + C
log
+ C² log
ja a + +(aa) + +1ril+ + [T'2 ||w,11
kj
JEN,
2 2
1
Σ
||w0112 (1 1- Ca²
3p
-
-C log
K VN
c
+ o + + |100,11
K
JENr
Ca
K VN
K
2
1
Σ
||0, 1|
+4p
log
+ log
a o(a²) + + [Tal ||w,
2
8
JEN
K a² C C'log
2 1
Σ
||00,12 2|
||w,1 1?
8"
JEN
Lemma 14 (Restated). Consider the same assumptions in Proposition 4. Given the t1 in Proposition 4, the following holds v1 & k < K:
2p K
Σ [e, exp
W Wiin 2
(H.47)
p(p 2)
JEN,
Proof. The proof will be in two parts: first, we define, for each k
2
(By definition)
(()) = inf aux
t:
min JENz
Czj (t) 2
t1:
(H.48)
3
and show that
2pp+2K K
Σ JEN
|| w (1b) (t())) 1|2 2 exp
(0)12.
(H.49)
- 2) 22 p(p-2)
JENL
Then we show that ΣJEN, 1| (tz) is non-decreasing during [t()) tz]-
Lower bound at ((t)): We shall focus on the case 1 5 k S K1. In the proofs of Proposition 4, we have shown in (F.18) that
when & < (k) < E1, the following is true: Vj E 2/2
d dt Ckj > Aepetjt
(H.50)
By Lemma 9, we have
= inf { t: Cky
2 5
1
(k) Faux
2
(H.51)
3 p(p
A
55

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
Now we are ready to lower bound EjEN, 1/20, (8)) | In the same way we derived (H.27), we can also obtain: for S (1,
dt w 112 2 - K(1 + 4c nww max max) ||
-20 1
(H.52)
thus
d
|ayl1 2 -2 K
|2, 112
(H.53)
dt
JENN
JEN
Finally, by Gr onwall's inequality, we have
Σ JEN
(t
2 exp
(-pp+ Kct
Σ
[0)12
JEN
2pp+2
z exp
W c2
mine?
p(p 2)
Norm is non-decreasing afterward The techniques we will be using here is similar to those used in proving previous lemma, so we describe the argument briefly.
Suppose 1 S k - K, we have the norm dynamics
d dl
|wyll 1|
2
Σ
gbi
((
Tig
||20,
||a
N
|w
(i(00s,05))00
2
V1
w
"
|| 112
+
O(e)
N
|00
(0(00,,0,,)000
Recall how we handle the proof of Lemma
Dig
p
|| |/w/wll ))r)
203
||ı0,|1 [105|1++00 O(c)
N
|2w|1
F
bo TE
Ckj +
Wi
leyl +
(
W
>)
||0, 2 ((e)
|wy||
FEIA
b $EZI
Taylor expansion, refer in (H.46)
Taylor expansion, refer to (H.
(v/oe
K2N a
2
la
-((3)) +(()))))(().)
kj
When Ckj 2 2/ we have
K -
Elassh layl 2 E (1 -1- 0,
(H.54)
1yk
then for sufficiently small and e, have a ||w
1 > 0. Then during Lank < 41, have
d
| 20. 0.
(H.55)
dt
JEN
The proof is finished.
Lemma 18. 15[Restated] Given some 0 < A < 1. for some =(t), the following holds
d dt
2 (1 2 - A)2, z(0) zo. x(T) 21
(H.56)
56

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs
for some 0 < 20 2.2 and 2o S 1
A. Then the travel time T for z(1) to go from 2g to 21 satisfies:
1 -
T 2 2 log 21 A
+ log
(H.57)
20
Proof. We have
T
/ dl,
dz 2
(H.58)
A)z
.0
thus
1 T
A
1
1
log
+ log
22
log
+ log
(H.59)
A
21 A
20
1
21
A
20
Lemma 16 (Restated), Condition on good event Egood, we have
Σ JEN,
10) o(a2), 1. T
(H.60)
Proof. We deal with neurons with sign(u;) = +1, the other case has similar proof. If E No. it means wyo is initialized into the void region with (O)(0) < 0 and (t))(t) = ((). for 1 S k < K₁. Therefore, the inner product between (0)(0) and a data point x; from the k-th cluster always negative, and this holds continuously as long as (t)(t) < 0 and [ck)(t)] = (1).
We will show that
1. Until / S t", we still have (t) < 0 and [c))()) = @(1), thus none of the data in positive clusters activates wzj.
2. Then (t)(t) < 0 and (cs)(t) (t) = (1) suggests that, ΣjEN, ||wy|| has an at most O(a2) growth rate. And during [t", T"), with slightly different argument, ΣjEN, ||w, /12 still has at most (aa?) growth rate, thus continually stays at ō(a?).
The more formal proof requires proof by contradiction, with previous lemmas have proved, but the provided argument should easily be translated into proof by contradiction.
First step: Given a E No U and 1 S k S K1, we have during t S t",
Ckj
=
1
Σ
Vgli P ((02) ( ( )
(psk: xxa)
W
Cki
dt
N
(i(o,,,,))00
1
Σ
Σ
Vols P ((
Zi ||w
wi
(pec x
Et.
||0
w
Ckj
KITTSISK (EI)(E,,,,))0
-
N
Σ
Σ
Vols p
((2))
Zi:
||w
Wi
Ckj
+
VD
KI+ISIKK 1)))(
Since b is either < 0 (during alignment phase) or O(a²) (after norm growth). Then we always have d _ O(a2).
Therefore, Vt <
a000 2
+00
cRy( S Cky + (( + cx, 0 a²
(H.61)
thus, we still have (1)(1) and
57

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal G.MMs
Second step: During [0, (*), since none of the data in positive clusters activates wi,, have
di |
2 N
1
Σ
Vgli
( (zi
w
)) [
|
[wy]
1 --2 N
Σ
Σ
Vgli
((z))
[w, 112
|w
Ki+IsIsK K (2,,,,,,,
Since V Vele is either < 0 (during alignment phase) =r = O(a²) (after norm growth). We have
d de "/llwll'' 2|2 = O(a2) 11 112.
During [t", T*), we have Vgl; (a²²) for all (as the consequence of EjEm, ||w, =(a2) and Lemma 11),
Therefore still have d ||, /|2 (a²)) ||, Then we have 41 ST
d
Σ =0(p(((())((
Σ =00)
00)))
Σ [|))( S (0(2)= =((a))
(H.62)
dt JENL
JEN.
JEN.
Lemma (Restated). If the neurons {ur, satisfies the following for some S 8 S and v, Ç >
* max; maxjeNs (t)(t) 2 -5 8;
1 -1EEENN ||,0 su
EjeNe 1|20;12 S.
then supzeso-1 (xx) 0) f())(x)) < K(1 + () - -1)26 + Kv + C
Proof.
p(0)
(x; (x;
(H.63)
h
Gp ( x))
Σ
|wy p-1
1=1
((0))
Σ
sign(u;) [
|0
1=1
Σ sign( (5 11, ((
W, x
||00
10,0100000 (
| 2 ))
1,0 (1
= Σ
Σ
W
Σ
Σ
wj
x
IkkK JEAL
KI+ISKSR JENN
sign(u,) wy 1208
((
||
20
(H.64)
JEA'
For the first term, have Yo E GD-1
1|, 00 ((
|,,,1' 1)
Σ Σ ISASK, JEN,
w
Σ )
ISkgKi
58

---

Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMS
<
Σ
Σ JEN
|w,|130
|wy
((10e)]
w
aa + pMs;
20 1) ((ue, 2))
15k5 Ki
(HES; 2)) + 11 w
||00]1 [|1x]]]] uk) 1) ='(((ess x)))
5
Σ
Σ
||05 1103|/000
K
JENL
Σ
Σ JENx
|0m
1oP ((1x: 2²) + 2(1 - css)) - o² ((1),
Ks
Σ IskSKi
Σ
Iwy/
(0 + ckj)) Σ
110, 1P'0 ((ux)
JENL
JEAL
Σ
||2, (() x)) - of ((p2) x\)
ISkSK,
JENN
Σ (1+ 10p ((H)) x) + 2 - cki)) - ( xz)1 +
E
x));
Iskski
IskSKi
Σ (1+ 100 (1pk x) + + - ckj)) o ('H,e + K1v
1SKSKi
- (1 + (2P 1)25 + Kiv,
where the last inequality is due to the following derivation (notice that ReLU (=)) is non-decreasing in 2, and polynomial 2 is non-decreasing for 2 > 0)
10 ((1R) x²) + 1112((1c5)) okg) - -
("U( x))
=0 ((4, x)) + 2(1 cky)) (1LE, x))
$ (1 25)² - 1 S (2 1)25.
Similarly, for the second term, we have Vo e SD-1
Σ Elw,loo'
((100)11=) x 1)-
w
Σ
< + +2 1)28 + K2v.
JHHISKKKJENG
KitISksK
Lastly, for the third term, we have
w. :))
Σ slnn()))1l,)1P0'
((11a)1
S Σ
||m SC cC.
JEN=
JEN=
Therefore, for any æ E SD-1, we have
1|:0 ((1me)))
w xx) 1)
((0)(x;;) 0) - (())(x)) S
Σ ISASK, JENE
Σ
Σ )(((N)
ISASKi
Σ
Σ ||0n (< ||00,]|| (|Imo|ll=0///
W .x x))===
Σ d(((H,,)))
KitIskSKJENN
KitISkKK
((
||,,,|| x ))
Σ sign (ign(
w
JEN
<K(1 + =2 1)28 + Kv C.
59


Reviews:
[{"review_id": "RX2P2tgc4w", "reviewer": "Reviewer_KSsi", "summary": "This paper analyzes the gradient flow dynamics of training a pReLU neural network. It is shown for data coming from Gaussian mixture models with orthonormal cluster centers that, under some technical initialization conditions, the dynamics converge to a particular pReLU model that acts similar to a nearest-cluster rule, with a known (and high) level of robustness.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n**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.\n\n**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.\n\n**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).\n\n**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.\n\nWe also thank the reviewer for pointing out typos and notation issues in our manuscript. We will fix them in the revision. \n\nWe hope our rebuttal addresses your concerns. If you have additional questions/concerns, please feel free to post them during the discussion phase. \n\nReference: \n\nHopcroft, J. and Kannan, R. Computer Science Theory for the Information Age. \n\nChatterjee, S. Convergence of gradient descent for deep neural networks. arXiv preprint arXiv:2203.16462, 2022.", "claims_and_evidence": "The claims are all theoretical, and are well-supported by clear and rigorous mathematical analyses.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The mathematical analyses appear to be rigorous and correct.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "This paper is somewhat niche, with impacts primarily in the area of mathematical analysis of neural network training.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is extremely well-written. The content is highly technical, but the authors do a good job at shedding light on what the technical conditions mean intuitively (for instance, through geometric descriptions).\n\nThe problem setup is definitely impractical in terms of the assumptions being made, as the authors themselves have acknowledged. However, in my opinion, this does not necessarily detract from the contributions and possible impact of the paper; the paper's goal is to conduct a theoretical analysis of a gradient flow that is in general intractable to characterize for complicated data distributions and initialization schemes. So, appropriate assumptions are employed and clearly stated in order to reduce the analysis down to a tractable one, enabling the authors to attain their goal (and to prove a previously open conjecture). Such simplified analyses can still offer intuitive insights into what we may expect for gradient-based learning in the cases where some of the assumptions are relaxed. Furthermore, the analysis methods developed here may serve as the foundation for future work to analyze more complicated (and more practical) settings.\n\nThat said, I do have a few questions and concerns that I would like to see addressed. See below.", "other_comments_or_suggestions": "1. Line 98 and Figure 1: Why would those two Gaussian clusters concentrate on D-1 dimensional affine subspaces rather than on spheres?\n2. Line 119, Column 2: It seems odd to restrict your attack model to a sphere of radius $r$ rather than a ball of radius $r$, which is the more common method for modeling additive adversarial attacks. That is, why are you using $\\min_{\\|d\\| = 1}$ rather than $\\min_{\\|d\\|\\le 1}$? With your model, is it not possible to potentially find some large radius $r$ for which the model is robust, even though there may exists some smaller radius $r' < r$ at which an attack results in misclassification?\n3. The interpretation of the Bayes optimal classifier as a nearest cluster rule (with some error term) is very interesting.\n4. Notation in Proposition 3: By $x\\in S^{D-1}$, do you mean the $D-1$ dimensional unit sphere? If so, it would be good to explicitly define this notation for the reader.\n5. Notation: Typically set minus is denoted with a backslash (\"\\setminus\" in LaTeX), not a forward slash.\n6. Typo in Assumption 2: \"The initialization has s\"... there seems to be an extra floating letter \"s\".\n7. Overall, I find the geometric descriptions of the rather technical initialization conditions in Section 3.2.1 to be very nice, and enlightening.\n8. On the takeaway message of Theorem 1, and discussion \"Nearly optimal robust classifier via GF\": Does your analysis guarantee that GF will not suddenly diverge away from the robust baseline $F^{(p)}$ once the flow time increases beyond $T^*$? It seems to me like this might be a possible limitation. If this is the case, how would one know when to stop the gradient flow process to \"capture\" the right set of parameters giving maximal robustness?\n9. Your analysis in Theorem 1 seems to be saying that GF will result in $f^{(p)}$ approaching $F^{(p)}$, and then claiming robustness of $f^{(p)}$ from that of $F^{(p)}$. If $F^{(p)}$ is such a desirable baseline for robust prediction, why wouldn't one simply use $F^{(p)}$ for prediction in the first place? What is one gaining by learning $f^{(p)}$?\n10. Footnote 3: This footnote should be placed after the punctuation, to avoid looking like a mathematical \"cubed\" symbol.", "questions_for_authors": "See above \"Other Comments Or Suggestions.\"", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aeFJ0gMjlC", "reviewer": "Reviewer_MTUy", "summary": "This paper presents new theoretical findings regarding the feasibility of achieving robustness without adversarial training. Specifically, the paper focuses on a specific data model: a mixture of Gaussian distributions whose cluster centers (i.e., mean vectors of each Gaussian distribution) are orthonormal vectors. The paper first proves that $\\ell_2$-robustness cannot be achieved for a particular attack radius. However, for smaller attack radii, the adversary’s attack success probability can be lower-bounded for the Bayes optimal classifier, implying the robustness of the Bayes optimal classifier for the given data model. Then, the paper presents its theoretical achievement that, for the given data model, it is feasible to train a pReLU network without adversarial training with a proper assumption on the parameter initialization.\n\n## Update after rebuttal\nI appreciate the authors' rebuttal. However, I don't think that the rebuttal properly addressed my concern on paper organization and I can also see that I'm not the only reviewer who concerned about the paper writing as a major issue of the paper. I'll keep my initial rating of 2.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments and suggestions. Here are our responses to your questions and concerns:\n\n**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.\n\n**What message should one get from this paper?** As a theoretical paper, we believe our messages are clearly stated.\n- The paper title summarized our theoretical contributions;\n- 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\";\n- 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. \n\nBased 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.\n\n**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.\n\n**How our findings benefit the ML Community**: Our contributions are:\n- (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.\n- (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.\"\n- (Practical) We have expanded our remarks on the practical implications of our results in this rebuttal and will add them to the revised manuscript.\n\n**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).\n\nWe hope our rebuttal addresses your concerns regarding the organization of our paper. If you have additional questions/concerns, please post them during the discussion. \n\nReference:\n\nLi, 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.", "claims_and_evidence": "All the claims contain proofs in appendices.", "methods_and_evaluation_criteria": "This paper neither proposes a new method nor evaluates it.", "theoretical_claims": "I read most of the main body, including the proof sketch. The proof idea in the sketch makes sense.", "experimental_designs_or_analyses": "This paper presents purely theoretical findings and does not contain any experiments.", "relation_to_broader_scientific_literature": "This paper contains an interesting finding that adversarial robustness is achievable without adversarial training for a specific data model with some assumptions. However, the impact of the findings is unclear to me.", "essential_references_not_discussed": "The paper cited the needed references well.", "other_strengths_and_weaknesses": "### Strengths\n1. To the best of my knowledge, the presented theoretical results are novel.\n2. We still lack a theoretical understanding of adversarial training, and this paper adds some new findings to the theory.\n\n### Weaknesses\n1. The paper is not well-organized, which makes it harder to understand.\n2. The theoretical findings are interesting, and the paper contains many findings. However, the practical implications of those findings are unclear. In Remark 2, the paper referred to other papers to find such practical implications of the problem. (Even this should be discussed separately in a section discussing related works.) However, those papers do not explain the message the reader should get from **this paper**.", "other_comments_or_suggestions": "1. Please organize the paper's contents to have a better structure as an academic paper. For example, you can present the summary of the theoretical findings first, then a separate proof sketch section, and then another section containing additional content, such as a comparison to prior work and limitations. Also, please add a conclusion section that summarizes the paper's achievements.\n2. Please be more selective about what you present in the main body of the paper. For example, while Propositions 1 and 2 are interesting theoretical statements, I don’t think they have more significant value than the results in Section 3. Moving those Propositions to the Appendix and discussing the results in Section 3 more would be better.\n3. Be clear about the message the paper wants to deliver to the ML community. The paper proves some interesting theoretical statements, but the reason why the findings are significant is unclear.", "questions_for_authors": "1. Regarding the impact of this paper, Remark 2 refers to other papers about the practical implications of the problem setting. Please briefly explain the practical implications to me. (In my opinion, this should be explicitly written in the paper.)\n2. What do the paper's findings imply related to the practical value of the problem? Specifically, how can those findings benefit the ML community?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xwntg1JjNY", "reviewer": "Reviewer_hboM", "summary": "A common concern in the design of deep learning systems is their susceptibility to imperceptible noise. The authors approach this problem from the angle of finding the maximum adversarial perturbation tolerated by a neural network, without needing adversarial training. It is clarified that this often conditions on the data geometry, since the proof of a robust classifier depends on a sufficiently large margin between each class-conditional cluster in the desired classification space. The desire is to provably find a robust classifier while maintaining clean accuracy.  The submission proposes theoretical proof that on specific data models, the maximum robustness any classifier can achieve is based on the separation between the class-conditioned probability mass. Although the data distribution follows specific structural patterns that enable learning a robust classifier, the ability to learn the robust classifier by gradient descent is not viable unless using a polynomial ReLU (pReLU) proposed in prior work. Based on a balanced gaussian mixture model, the authors first show that a nearly optimal classifier can be constructed from nearest-cluster rules. Unfortunately, gradient descent must derive classification rules over the trajectory of optimizing weights, which makes learning the robust classifier more difficult. With bounded network parameter initialization, the main result tries to prove the conjecture provided in prior work, which states that gradient descent on a pReLU network with $p > 2$ eventually converges to an adversarially robust network in the radius close to $\\frac{\\sqrt{2}}{2}$. This is said to hold for an arbitrary classifier $f$ within a specific distance measure (proposition 3). The result assumes: a balanced data sampling of the GMM (Assumption 1), and given the definition of non-degeneracy gap using a union of Voronoi regions and void regions, there is a limit on where individual neuron weights may initialize given the weight's angle to nearby cluster centers (Assumption 2).\n\n## Post-rebuttal update\n\nThanks to the authors for a detailed response and new experiments, which will improve the next version. The main pain point remaining is the layout and organization of the main text, which is difficult to remedy in a single review cycle without a major revision, so I will keep my original score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments and suggestions. Here are our responses to your questions and concerns:\n\n**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.\n\n**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. \n\nWe describe these numerical experiments in detail: we consider, as per the reviewer's suggestion, two types of initialization:\n - *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.\n - *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.\n - The initialization scale is $\\epsilon=1e-7$\n\nWe 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:\n - *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.\n - *Loss*: The mean square loss.\n - *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.\n\nWe summarize the findings\n 1. GD converges and finds $F^{(p)}$ in both cases, thus verifies our Theorem 1;\n 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,\n \nfrom the following tables:\n\n|GD, random init.|||||||||\n|---|---|---|---|---|---|---|---|---|\n| Iterations| t=0| t=50 | t=100  | t=150 | t=200 | t=300 | t=400|t=500|\n| Alignment (mean)| 0.05 | 0.06 | 0.14  | 0.29 | 0.47 | 0.69 |0.80 | 0.80|\n| Alignment (1st quantile)|0.04| 0.06 | 0.04  | 0.04 | 0.05 | 0.14 |1.00 | 1.00|\n| Loss | 1.00| 1.00 | 1.00  | 1.00 | 1.00 | 9.99e-1 | 4.97e-1|1.30e-4|\n| Distance to $F^{(p)}$| 5.33e-1| 5.20e-1 | 5.25e-1  | 5.14e-1 | 5.21e-1 | 5.21e-1 | 5.05e-1|3.89e-5|\n\n|GD, non-degenergate init. $\\delta=0.05$|||||||||\n|---|---|---|---|---|---|---|---|---|\n| Iterations| t=0| t=50 | t=100  | t=150 | t=200 | t=300 | t=400|t=500|\n| Alignment (mean)| 0.07 | 0.12 | 0.34  | 0.58 | 0.77 | 0.92 |0.95 | 0.95|\n| Alignment (1st quantile)|0.05| 0.05 | 0.08  | 0.14 | 0.48 | 1.00 |1.00 | 1.00|\n| Loss | 1.00| 1.00 | 1.00  | 1.00 | 1.00 | 9.92e-1 | 1.94e-1|9.15e-5|\n| Distance to $F^{(p)}$| 5.33e-1| 5.20e-1 | 5.25e-1  | 5.14e-1 | 5.21e-1 | 5.18e-1 | 4.80e-1|1.57e-5|\n\nNote: 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.\n\nWe 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.", "claims_and_evidence": "- The main proof is structured similar to prior work studying GF dynamics - the GF problem is split into an alignment phase and a convergence phase. The alignment of neuron weights can be bounded given the assumptions on initialization and non-degeneracy. The convergence can be checked based on monotonic growth of the neuron norm in Voronoi regions and small bounded amount in void regions. The proof seems reasonable and an iterative step over prior work.", "methods_and_evaluation_criteria": "The authors provide some small experiments using synthetic data in Appendix B, although they mainly relate to comparison of regular polynomial ReLU and pReLU.", "theoretical_claims": "I did not see any major errors with the proofs.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "- The proposed theorems may have implications for prior work which offered conjectures on the convergence properties of pReLU-based 2-layer neural networks. \n- Future work may extend the results to different classification losses, since the current format assumes a specific loss (due to difficulty in characterizing neuron movement during training).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- The convergence proofs would be a useful extension for the conjectures proposed in prior work. \n- The submission mainly suffers from structural and organization issues. The main theorem is not presented until page 6. The introduction runs until page 3 and contains  information that is not necessarily needed for introducing the problem domain (e.g., defining GMM, informal versions of proofs). Most of section 2 could likely be moved to an appendix since it relates to the idealized Bayes classifier with cluster center rules. The main text ends abruptly, but should ideally devote more space to synthetic experiments to validate assumptions, closing remarks, and future work. \n- The main results are interesting but I was expecting to see some verification of assumptions (1 and 2) on small-scale synthetic data, e.g., demonstration of the effect from degenerate and non-degenerate initializations, or when initialization places neurons close to region borders. It would've been interesting to check the classifier training which obeys Assumption 1 but not Assumption 2 (non-degeneracy shape). It makes sense to need a specific placement of neuron weights relative to cluster centers for the convergence analysis, but it wasn't clear how necessary this is during practical implementation.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TqUcEwBddv", "reviewer": "Reviewer_AZei", "summary": "This paper investigates the problem of adversarial robustness in deep learning classifiers and provides a theoretical framework demonstrating that standard training methods, specifically gradient flow, can lead to a provably robust classifier under certain conditions. Unlike existing approaches that require adversarial training or explicit defense mechanisms, this work focuses on the natural robustness that emerges from the structure of the data.\n\nThis work focuses on a binary classification problem where data is drawn from an isotropic Gaussian mixture model with orthonormal cluster centers. The theoretical study first establish the limit of adversarial robustness by showing that no classifier can defend against an L2 attack of radius greater than $\\sqrt{2}/2$, while also proving the existence of an optimal classifier that achieves this bound. This classifier follows a nearest-cluster rule, assigning labels based on the closest cluster center in feature space.\n\nThe core result of the work is the proof that a two-layer neural network with a polynomial ReLU (pReLU) activation function, trained using gradient flow, can successfully learn this optimal robust classifier without requiring adversarial training. This stands in contrast to standard ReLU networks, which fail to achieve robustness due to their inability to internally learn the multi-cluster structure of the data. This work  further provides a rigorous convergence analysis demonstrating that gradient flow on pReLU networks can find a classifier that is not only highly accurate on clean data but also robust to adversarial perturbations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments and suggestions. Here are our responses to your questions:\n\n**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.\n\n**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.\n\n**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.\n\nWe hope our rebuttal addresses your questions. If you have additional questions/concerns, please feel free to post them during the discussion phase.", "claims_and_evidence": "The claims made in the submission are supported by a combination of theoretical proofs and empirical observations. The core theoretical contributions, particularly the characterization of the maximum achievable adversarial robustness and the proof that gradient flow on a two-layer network with a polynomial ReLU activation can learn a robust classifier, are well-supported by rigorous mathematical derivations. This work establishes upper bounds on robustness and demonstrate that their proposed classifier achieves these bounds, providing convincing justification through formal theorems and proofs.\n\nOne of the key strengths of the paper is its detailed convergence analysis, which demonstrates that gradient flow on a properly parameterized network finds a nearly optimal robust classifier under the assumed data distribution. This theoretical backing is essential in supporting the claim that standard training, without adversarial examples, can yield robustness in certain structured settings. The results align with prior works that study adversarial robustness in relation to data geometry.", "methods_and_evaluation_criteria": "The proposed method in this paper is aligned with the theoretical analysis. The primary methodological contribution is the demonstration that gradient flow on a two-layer neural network with a polynomial ReLU (pReLU) activation function can provably learn a robust classifier under the specified conditions. This is a novel and interesting result, particularly in showing that standard training methods can achieve adversarial robustness **without explicit adversarial training**. The evaluation criterion used to assess the robustness of the learned classifier—the maximum L2 perturbation it can withstand while maintaining high accuracy—is a reasonable and widely accepted metric in adversarial robustness research. The paper provides formal derivations to establish the theoretical upper bound on robustness and proves that the proposed  method can achieve this bound empirically, which is a strong result.", "theoretical_claims": "I checked the key theoretical proofs provided in the submission and found that the high-level arguments and overall structure of the proofs are sound. The authors develop their results with careful attention to the necessary assumptions, such as the non-degenerate parameter initialization and the scaling conditions required for the convergence analysis of the gradient flow on the pReLU network. Their derivations for the maximum L2-robustness and the subsequent convergence guarantees are presented with clarity and logical consistency. While I do not verify every technical detail down to the last inequality, the main steps and techniques—such as the use of concentration inequalities and the analysis of activation dynamics—appear to be correct and align with established methods in the literature. Overall, I think the proofs convincingly support the theoretical claims in the paper.", "experimental_designs_or_analyses": "I also checked the experiments presented in the paper.  The experiments primarily serve to illustrate key theoretical results rather than to provide a comprehensive empirical evaluation of the proposed approach. The authors use synthetic data generated from an Orthonormal Gaussian Mixture Model (GMM), which is a well-chosen setting to validate their theoretical analysis but does not necessarily reflect the complexities of real-world datasets.\n\nThe experimental design effectively demonstrates the failure of standard ReLU networks in learning robust classifiers and the corresponding success of pReLU networks under gradient flow. The figures provided show that specific activation functions play a crucial role in achieving robustness, which supports their claim that the architecture must be designed to exploit the structure of the data. However, the evaluation lacks a comparison with standard adversarial training techniques or alternative defense mechanisms, making it difficult to assess how well the proposed approach performs relative to existing state-of-the-art methods.\n\nOne major concern over the experiment design is the absence of evaluations on widely-used benchmark datasets such as CIFAR-10, MNIST, or ImageNet. While synthetic experiments are useful for validating the theoretical results, their practical significance remains unclear. The paper does not explore how well the proposed method generalizes to more complex, high-dimensional data distributions where the assumptions of the Orthonormal GMM may not hold. \n\nIn summary, I think the experimental design supports the theoretical findings within the specific scope of the problem but does not fully validate the broader applicability of the approach. A more extensive empirical evaluation, including real-world datasets and comparisons with adversarial training methods, would be necessary to establish its practical relevance.", "relation_to_broader_scientific_literature": "The main contribution in this paper is closely related to the study of adversarial robustness, neural network training dynamics, and implicit regularization in deep learning.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "The most significant weakness is the lack of empirical validation on real-world datasets. The theoretical results are developed within the framework of an Orthonormal Gaussian Mixture Model (GMM), which is a well-structured and mathematically convenient setting but does not necessarily reflect the complexity of natural datasets. Without experiments on standard benchmarks such as CIFAR-10, MNIST, or ImageNet, it remains unclear whether the proposed method would work effectively in practical scenarios where data distributions are more intricate and do not satisfy the strict assumptions of the orthonormal GMM.\n\nThe initialization requirements also present a potential weakness. The analysis relies on a non-degenerate initialization with a positive gap to ensure that neurons align correctly with the cluster structure of the data. However, this condition is not naturally satisfied by random initialization, meaning that additional interventions may be needed to ensure that gradient flow leads to a robust classifier. This assumption is acknowledged in the paper, but there is little discussion on how one might relax it or adapt standard training methods to meet these conditions in practice.\n\nAs well, the requirement that the data follows a high-dimensional mixture of orthonormal Gaussians is a strong assumption that may not hold in many real-world applications. This limits the generalizability of the results", "other_comments_or_suggestions": "I would suggest the authors conduct experiments on real-world datasets such as CIFAR-10, MNIST, or ImageNet, which may significantly enhance the paper’s practical relevance. In addition, this paper could also benefit from a comparative analysis with adversarial training methods, such as PGD adversarial training and randomized smoothing. Comparing with the robust training baseline can consolidate the adversarial robustness claim made in this work.\n\nThe paper shows that ReLU networks fail, yet pReLU networks succeeds in mitigating adversarial attacks. How about using other variants of ReLU, such as GELU, or leaky ReLU ? Could they yield similar robustness properties ?  \n\nI also suggest the authors discuss potential extensions beyond the Gaussian mixture model. The structured nature of the data model is useful for theoretical analysis, but adversarial robustness is often studied in much more complex, high-dimensional, and non-Gaussian settings. Exploring whether similar guarantees can be derived for broader classes of data distributions can make the findings more broadly applicable.", "questions_for_authors": "Please check the suggestions made.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: The paper proves that, with suitable choice of activation (pReLU), one can learn robust classifiers even with standard gradient descent. The analysis is under the framework of a Gaussian mixture model, and the dynamics for the pReLU activation is quite non-trivial. All reviewers agreed that the theoretical results are solid and interesting, while some reviewers raised concerns about the writing style. The authors are encouraged to include the simulation results in the revised version.
Decision: Accept (poster)