Directional Convergence, Benign Overfitting of Gradient Descent in leaky ReLU two-layer Neural Networks
Authors: Ichiro Hashimoto
Venue: ICLR 2026 Poster (2026)
Keywords: Benign overfitting
Implicit bias
neural networks
classification
Primary area: learning theory

Abstract: In this paper, we provide sufficient conditions of benign overfitting of fixed width leaky ReLU two-layer neural network classifiers trained on mixture data via gradient descent. Our results are derived by establishing directional convergence of the network parameters and classification error bound of the convergent direction. Our classification error bound also lead to the discovery of a newly identified phase transition. Previously, directional convergence in (leaky) ReLU neural networks was established only for gradient flow. Due to the lack of directional convergence, previous results on benign overfitting were limited to those trained on nearly orthogonal data. All of our results hold on mixture data, which is a broader data setting than the nearly orthogonal data setting in prior work. We demonstrate our findings by showing that benign overfitting occurs with high probability in a much wider range of scenarios than previously known. Our results also allow us to characterize cases when benign overfitting provably fails even if directional convergence occurs. Our work thus provides a more complete picture of benign overfitting in leaky ReLU two-layer neural networks.

DIRECTIONAL CONVERGENCE, BENIGN OVERFITTING OF GRADIENT DESCENT IN LEAKY RELU TWO-LAYER NEURAL NETWORKS
Ichiro Hashimoto
Department of Statistical Sciences
University of Toronto
Toronto, ON M5G IZ5
ichi ro. ha sh m utoronto.ca ca
ABSTRACT
In this paper, provide sufficient conditions of benign overfitting of fixed width Ieaky ReLU two-layer neural network classifiers trained on mixture data via gradi- ent descent. Our results are derived by establishing directional convergence of the network parameters and classification error bound the convergent direction. Our classification error bound also lead to the discovery of newly identified phase transition. Previously, directional convergence in (leaky) ReLU neural networks established only for gradient flow. Due the lack of directional convergence, previous results on benign overfitting were limited to those trained on nearly orthog- onal data. All of our results hold on mixture data, which is broader data setting than the nearly orthogonal data setting in prior work. We demonstrate our findings by showing that benign overfitting occurs with high probability in a much wider range of scenarios than previously known. Our results also allow us to characterize cases when benign overfitting provably fails even if directional convergence occurs. Our work thus provides more complete picture of benign overfitting in leaky ReLU two-layer neural networks.
INTRODUCTION
The practical success of deep learning has revealed surprising theoretical phenomena. One such phenomenon, which has inspired intense theoretical research, is benign overfitting, where over- parametrized neural network models can achieve arbitrarily small test errors while perfectly interpo- lating training data-ewe even in the presence of label noise (Zhang et al. (2017); Belkin et al. (2019)). Benign overfitting has attracted broad attention since it seems to conflict with the classical statistical understanding that there should be trade-off between fitting the training data and generalization the test data. This led to intense theoretical research which has revealed that benign overfitting also occurs in several classical statistical models, such as linear regression (Bartlett et al. (2020), Muthukumar et al. (2020), Mei and Montanari (2022), Hastie al. (2022)), ridge regression (Tsigler and Bartlett (2024)), binary linear classification (Chatterji and Long (2021); Wang and Thrampoulidis (2022): Cao al. (2021); Hashimoto et al. (2025)), and kernel- estimators (Liang and Rakhlin (2020), Liang et al. (2020)), to name a few. However, our understanding of the phenomenon for neural networks remains limited.
It is widely believed that the implicit bias, which results from implicit regularization of gradient based optimization, is the key to understand generalization performance in the over-parametrized regime. In fact, for binary linear classification. it is known that lincar classifiers trained under gradient descent with loss function with tight exponential tail, e.g. the exponential loss and logistic loss, converge in direction the maximum margin classifier (Soudry et al. (2018)). Benign overfitting in binary linear classification has been studied thoroughly by analyzing the convergent direction (Wang and Thrampoulidis (2022); Cao al. (2021); Hashimoto et al. (2025)).
In this work, we investigate benign overfitting in two-layer leaky ReLU neural networks with fixed width for binary classification whose network parameters are trained mixture data by gradient

---

descent with exponential loss. We show that benign overfitting occurs in much wider scenarios than previously known.
Our results are derived by establishing directional convergence of the network parameters with precise characterization of the convergent direction and by obtaining a classification error bound of that direction. Due to the difficulty in establishing directional convergence of gradient descent for ReLU type networks, prior work for leaky ReLU networks were limited to either gradient flow (Frei et al. (2023a)), smoothed approximation of leaky ReLU (Frei al. (2022)), or nearly orthogonal data regime (Xu and Gu (2023)), i.e. the predictors (#:; Jemm i p.... C R satisfy ||a:||| >
mäxiyt ( az)).
The precise characterization of convergent direction not only allows to prove benign overfitting beyond nearly orthogonal data regime but also leads to a novel lower bound of the classification error in the case of Gaussian mixture. The lower bound shows our bound is tight and allows us to characterize cases when benign overfitting provably fails even if directional convergence occurs.
Moreover, sufficient conditions of directional convergence and classification error bound are obtained in a deterministic manner, which allows us to show that benign overfitting occurs with high probability on polynomially tailed mixture models while the prior results are limited to uab-Gaussian mixture.
2 RELATED WORK
Benign overfitting in neural networks for binary classification. As noted earlier, benign overfit- ting in neural networks remains poorly understood. In fact, very few theoretical results are established beyond the so called neural tangent kernel (NTK) regime. Cao et al. (2022) studied benign overfitting for two-layer convolutional neural networks with polynomial ReLU activation (ReLU', - > 2). Their results were strengthened by Kou et al. (2023a) by relaxing the polynomial ReLU assumption. Both Cao et al. (2022) and Kou et al. (2023a) are not applicable to our setting since our work considers fully connected neural networks.
More closely related work is Frei et al. (2022), which studied benign overfitting in smoothed leaky ReLU two-layer neural networks on mixture data. Their work was extended by Xu and Gu (2023) to non-smooth leaky ReLU like activation. While Xu and Gu (2023)'s work is not limited to (leaky) ReL.U, their work is limited to the nearly orthogonal data regime and only holds for isotropic mixture with bounded log-Sobolev constant, which is stronger assumption than sub-Gaussian mixture. Our work establishes benign overfitting beyond the nearly orthogonal data regime and can be applied to a wider class of mixtures than the prior work such as polynomially tailed mixture. Moreover, we also establish a novel lower bound of the classification error in the case of Gaussian mixture, which shows tightness of our result and helps characterize cases when benign overfitting provably fails. Even with gradient flow, benign overfitting in leaky ReLU neural networks is limited to nearly orthogonal data setting and Gaussinn mixture model (Frei et al. (2023a)).
Lastly, our result is shown for fixed width two-layer neural networks, which relaxes Xu and Gu (2023) who required m to grow as n. and thus is also beyond the NTK regime or the lazy training regime (Jacot et al. (2018) 8); Arora et al. (2019)).
Implicit bias in neural networks for binary classification. Here, we focus on works on leaky ReLU homogeneous neural networks which are closely related to ours. We refer readers to Vardi (2022) for a comprehensive survey on implicit bias in neural networks.
Most prior work on the implicit bias of (leaky) ReLU neural networks for binary classification has considered gradient flow. For gradient flow, Lyu and Li (2020) showed that any limit point of the network parameter of homogeneous neural networks trained with exponential type loss is a KKT point of a constrained optimization problem and that margin maximization occurs. and Telgarsky (2020) further established directional convergence of the parameter of homogeneous neural networks trained with the exponential type loss. Taking advantage of the directional convergence of gradient flow, Lyu et al. (2021); Bui Thi Mai and Lampert (2021); Sarussi et al. (2021); Frei et al. (2023b); Min et al. (2024) obtained detailed characterizations of the convergent direction of the parameters of (leaky) ReLU two-layer neural networks under further assumptions the training data.
In contrast to gradient flow, directional convergence of network parameters for ReLU type neural net- works was not proven for gradient descent with exponential type loss, even under strong assumptions.
2

---

As result, only weaker forms of implicit bias have been obtained for gradient descent. Lyu and Li (2020) showed that margin maximization also occurs for the network parameters of a homogeneous network trained by gradient descent, but their assumptions include smoothness of the network, and hence rule out (leaky) ReLU networks. Frei et al. (2023b) showed that the stable rank of network parameters stays bounded by constant for two-layer neural networks, but their result is limited to the smoothed approximation of leaky ReLU, Kou et al. (2023b) proved similar results for (leaky) ReLU two-layer neural networks assuming that the number of positive and negative neurons are equal. Moreover, Frei et al. (2023b); Kou et al. (2023b) are limited to the rather specialized scenario of nearly orthogonal data regime. Cai et al. (2025) showed directional convergence of gradient descent, but their result is not applicable to ReLU type neural networks since their result requires networks to be twice differentiable with respect to the parameters. Schechtman and Schreuder (2025) extended Lyu and Li (2020) by removing twice differentiability but their result does not guarantee directional convergence and assumes that training is already in the late-stage.
To the best of our knowledge, our work is the first to show directional convergence of gradient descent ReLU type neural networks with precise characterization of the convergent direction.
We also note that Karhadkar et al. (2024) studied benign overfitting in leaky ReLU networks using hinge loss instead exponential type loss.
A concise summary of related prior work is given in Table 1.
Table 1: Summary of Existing Studies of leaky ReL.U two-layer neural networks
Directional Convergence
Benign Overfitting
Nearly Orthogonal Data
Other regime
Nearly Orthogonal Data
Other regime
Gradient Flow Gradient Descent
and Telgarsky (2020)
Frei et al. (2023a)
NA
N
Frei et al. (2022)**,
NA
Xu and Gu (2023)
Cai et al. (2025) showed directional convergence assuming twice differentiability Frei et al. (2022) studied smoothed approximation of leaky ReLU instead.
PRELIMINARIES
We consider two-layer neural networks
f(x; W)
Σ 1=1
(a (a,,))))))
(1)
where x E RR, wy E RR, W = (wi, w Wm) E TR ag = vm
and & is leaky ReIUU
activation, i.e. (xx) max (w) for 7 E (0, 1). Letting ((x) if
0 and ((x) = 7 if
we may conveniently write (xx) = ((x)..
Letting J (1.2.....m)) m). J+ (j J : aj )m), and J_ J+, can rewrite the
network (1) as
f(x:W)= W) = Σ JEJI
1
o((x, wy)) - Σ ((x
Vm
vm
JEJ
We consider the exponential loss ((u) exp(-u) and define the empirical loss of the dataset {( w)her, where / := (1,2...., n by
n
n
L(W) Σ (ynf(x;
Σ exp(-ytf(2; W)).
We train the first layer weights w, by gradient descent initialized at (0)), i.c.
w((+1) W(O a V ((W(()))) t= 0, 1,1 .....
3

---

where > 0 is a fixed constant and we assumee d0)) is any number in h, 1]. The second layer weights 2j are fixed throughout the training. Fixing the second layer weights a, E [#1/ym] and only optimizing the first layer weights w is standard in the existing literature, see e.g. Arora et al. (2019); Cao et al. (2022); Frei et al. (2022); Xu and Gu (2023); Kou et al. (2023b). We do not consider random initialization of W(O) since only the magnitude of W plays a role in our analysis.
Assume that we observe i.i.d. copies { 9:) from a mixture distribution on R x {+1} which is defined follows
(M) The observations consist of n i.i.d copies (æ;, yi), i=) 1,..., , of the pair (æ, y). Here for
random variable y E { {-1, satisfying P(y = 1) = P(y -1) 1/2, random vector
z E R" independent of y, and a deterministic μ R", we have
x
y/ + 2.
The sub-Gaussian norm of a random variable X, say ||X| || 12 is defined | inf > 0 : E exp((2 X² /8) S 2}.
The sub-Gaussian norm of a random vector X E IRP is denoted by || 1l and defined as |0 == sup (1(v, X llvz.
X
As special case of the model (M), we consider sub-Gaussian mixture model (sG) and polynomially tailed mixture model (PM):
(sG) Suppose in model (M) = E.g, where & E R2 has independent entries & that have mean zero, unit variance, and satisfy [1,) S for all j = 1..... for L < 00,
(PM) Suppose in model (M) = = E. where & E Rº has independent entries E, that have mean zero, unit variance, and satisfy BIE, I for all j = 1.....p for E (2, 4] and K < co.
The mixture model (sG) have been studied for linear classifiers by Chatterji and Long (2021); Wang and Thrampoulidis (2022); Hashimoto et al. (2025) and for two-layer neural networks with Σ I by Frei et al. (2022); Xu and Gu (2023). The model (PM) has been studied for linear classifiers by Hashimoto et al. (2025).
We denote by || and ||A|| the spectral norm and the Frobenius norm of a matrix A, respectively.
For W E R=xm, we say benign overfitting occurs if the network (:; W) classifies the training data perfectly (interpolation) while arbitrarily small test error is achieved for sufficiently large n.
4 DIRECTIONAL CONVERGENCE OF GRADIENT DESCENT
We start from our main result on directional convergence of gradient descent in leaky ReLU two- layer neural networks trained on mixture data. Our result provides precise characterization of the convergent direction, which is a key for our analysis on benign overfitting. The key to prove directional convergence is neuron activation. We say that j-th neuron o({, ((;)) is activated if ajyi (I:; wx)) > 0 holds for any E 1, which can be equivalently written as 0z3i (a:, wy) > 0 for any E I.
In the following, we let Rmaz (x) == max, || and Rmin (z) := min, || and define an event that capture deterministic conditions the training data need to satisfy for the directional convergence:
E(O1, 02) max K6 iffk
|
=a S 0, and max 1( ( Tnt 8 |
(4)
for some 0,, O2 E [0, 1] (take 0 = 0 if μ = 0 or R Rmaz (z) = 0 and take 02 = 0 if I 0 or Rman (z) = 0). Event E allows us to control ||>;|| and (a,, ax),i + in terms of
[|al|], Rmin(2) (z), Rmaan (=), 01, and 02.
In addition, we denote by = max, ||rr the size of initialization. It is also convenient to let R2 (z)] to keep the assumptions of our main result concise.
= / mm/ 02)
We present sufficient conditions of directional convergence for the following two cases:
4

---

Case 1: This is the when (y y1. 2 0 is guaranteed for any i k. In this case, make the following assumptions:
Assumption 4.1 (Positive Correlation).
||||| 2 20 |||| Baar (z) + O2 R2 Rmmaa (z).
Assumption 4.2 (Small Initialization).
pexp(p)
r(1 - 02) (2))(2))
Assumption 4.3 (Small Step Size).
a[n]|u11 Rmaz (2) <1
The intuition behind these assumptions is follows: It can be shown that Assumption 4.1 ensures (y;e,, 3)xxa) 2 for any + k. Assumption 4.2 ensures the step size sufficiently larger than initialization that neuron activation occurs immediately after one step of (2). Assumption 4.3
ensures the step size is small enough for directional convergence to hold.
Case 2: This is when (VI y, k + i could be negative. The assumptions we make are:
Assumption 4.4 (Near Orthogonality).
202 |||| Rmma (2) + 02 R2 Rmmo (z) 817(1 - 02) R2
for some en E [0, 1).
n exx((2p)
Assumption 4.5 (Small Initialization).
pcxp(p)
for some 62 E (0, 1].
E2 R2 Riin (2)
Assumption 4.6 (Weak Signal).
n|||||2 S Eg R (z) for some Eg E (0,
Assumption 4.7 (Small Step Size).
6a R2 (2) exp(p) < 1.
Assumption 4.4 and 4.6 allow to carefully control (yx y, Small E1 ensure that the training data are nearly orthogonal. By taking μ = O, this case includes the nearly orthogonal data regime studied in the prior work (Frei et al. (2023b); Kou et al. (2023b)). The other assumptions analogous to Case 1.
We now ready state main result directional convergence, which not only establishes directional convergence but also provides detailed characterization of the convergent direction:
Theorem 4.8 (Directional Convergence on Mixture Data). Suppose event holds under one of the following conditions:
(i) Assumptions 4.1, 4.2 and 4.3 with 02
(ii) Assumption 4.4, 4.5, 4.6, and 4.7 with E + 82 +3 Cwee S i 1,3, and 02 S where C.,, := 24 2Aexp(1)y R2 (z) ? (z).
Then, the gradient descent iterate (2) keeps all the neurons activated for t 2 satisfies L(W(t))- = ( and converges in direction.

---

Furthermore, the convergent direction {ıt}}ee, can also be given by 0 + for J+ and き = w
for w- E J_, which is the unique solution to the following optimization problem:
Minimize
|J+1|
|/0+1l + 1-11||=111
J+
J|-_1
S.T.
w+)
(zt, w
2 1, E Lt:
m
vm
(5)
|J-| (1:, w0
(1 (.) 2 1,
vm
vm
Lastly, the resulting network f(; W) has the linear decision boundary defined by i = v
14+
w4
|J_] w. i.e sigu([(æ W)) sign( (ar, mi) for any R.. Vm
We note that condition (i) goes beyond nearly orthogonal data regime studied in the existing literature since there is no upper bound to the magnitude of the signal μ., while condition (ii) contains the nearly orthogonal data regime studied in Frei et al. (2023b); Kou et al. (2023b). As discussed in Introduction, directional convergence of gradient descent in ReLU type neural networks was not established in the existing literature even under nearly orthogonal data regime. In addition, the characterizations of the convergent direction in Theorem 4.8 were obtained only for gradient flow trained on nearly orthogonal data by Frei al. (2023b).
We also note that the optimization problem (5) has a unique solution since the objective function is strictly convex.
We show in Section that these deterministic conditions on training data can be achieved with high probability under sufficient ver-ppaaametrization not only by (sG) but also by (PM).
The proof of Theorem 4.8 is given in Appendix B.
CLASSIFICATION ERROR OF THE CONVERGENT DIRECTION
In this section, we discuss the classification performance of the convergent direction W.
Near orthogonality z;'s 's to each other and to la is again the key to obtain the closed form expression
and to establish an error bound. Letting Z (z1, ................................ =n)) .,)) E "xx,, n4 = Ki I ys 1H, and n_ = n n.,, the near orthogonality condition is characterized by the parameters from the following events which are defined for R 2 0, 0, &2 2 0, and 63 [0, 1]:
Es R) {l|Zz* T R1, s $ R)
(6)
E2 R) [11Zμ|| S & R]
(7)
Eg(Ea) = (In+ - = S $
(8)
Event Ei captures near orthogonality of 2;'s to each other and uniformity of their norms, and event Fe captures near orthogonality of z;'s to μ.. Although we could use the same parameters as in the analysis of directional convergence, these events Ei, Es makes the analysis of W simpler.
With É == max(ãi, Vπε2), q+ |J+1/m, q- = 1/mm and 9- = min(q+ + .4- + 7+ we can now present our main result on the classification performance of W:
Theorem 5.1 (Classification Error Bounds). Suppose event N 1= E.g holds with é & 9/ E3 S
further assume one of the following condition holds for a constant C C(7,44):
(i) Cnllul| < R. CE S n 3, and Ca2 < v
(ii) 9, > 7. n 2 CR. C n 1
Then, there exists constants c, N which depend on 7.9+ such that 2 N implies
P (( (vf W) < <0
exp
- |= xellaall
+
for model (sG),
<||E||
for model (PM).

---

If z= NN(, then we have instead
c 1 Mmin
(~ vi | + R
re||
W) <0) Sienn
{
n2 relleel
Ti 1i|||a| +
where k(t) PC1 2 t) and Bmin is the smallest eigenvalue of E and Braz
=||=||
This is a concise version for the purpose of presentation. A detailed version of the theorem and the proof are given in Theorem C.13, Appendix C.
Theorem 5. shows that there is a phase transition between the weak signal regime, i.e. n n|| S R and the strong signal regime, i.e. re|lel| Z R. The weak signal regime corresponds to the nearly orthogonal data regime studied in prior work under specific distributional settings (Frei et al. (2022); Xu and Gu (2023)). The lower bound in the case of Gaussian mixture implies that the phase transition is indeed a feature of the model. Previously, this type of phase transition was not shown even with gradient flow. Moreover, it was only known occur for binary linear classification (Cao al. (2021); Wang and Thrampoulidis (2022); Hashimoto et al. (2025)).
Moreover, the assumptions of Theorem 5.1 given in deterministic manner. We confirm in the next section that these assumptions are satisfied with high probability under model (sG) and (PM), and conjecture that they can also be verified in other settings.
Lastly, we note that the condition dy > y in (iii) is necessary to ensure the equivalence of v and the minimum norm least square estimator. We can even prove that the equivalence fails if q, < y which can be viewed as another form of the phase transition in the behavior of the convergent direction. Additional details are provided in Appendix C.
BENIGN OVERFITTING ON MIXTURE MODELS
We here demonstrate that the results of Theorem 4.8 and 5.1 hold with high probability in model (sG) and (PM) under sufficient over- veer-praaettization. For (sG) we make the following assumptions: Assumption 6.1. One of the following conditions holds for constant C
(a) n 122, C. a, St) o S 0.1yav
tx)
||||| 2 C'I
tr(E) 2 C max
n mlllal n
/ rr n
|ل||| n 1E
|e
and further suppose one of the following:
(i) |||||2 2 C max
/n pll.
/ni| m |=]|]
(ii Ir(E)= > C max
n | p11. n 2 |||| n² |z]|
N| 2+tr(E)
(b) 97 > 7. n 2 C, S 2.4m 1 S
0.2
| |
pall2 ||
tr())= N C max n |||||||l | 2.
|
/T||_i| F, nn|lill
Vn. V (x(2) n
||||| 2 C max
pll, V F x1,,,111111
We note that condition (a) above corresponds to the weak signal regime and (b) to the strong signal regime in Theorem 5.1. We are now ready to present our main classification error bound on (sG); Theorem 6.2. Consider model (sG). Let 8 E (0, 4)- Suppose Assumption 6. 6.1 holds for a sufficiently large constant C which depends only on 5, 9+- Then, we have with probably at least 36: the gradient descent iterate (2) keeps all the neurons activated for 2 1, satisfies L(W()) = (t))), converges in direction, and the convergent direction W attains
na 2|||
P (u W) < 0) S exp (-
|
nn | +rr(
7

---

where e is a constant which depends only on ry and 4+-
If x ~ NN, E), then we have instead
S ) < <0) s n cDnds (
n| pa]l |n||a|| + tr(E)
$
n ne|l |l tr(E))
c 3 min
We note that W perfectly classifies the training data since the training loss C(t) is driven to zero by gradient descent. Thus, Theorem 6.2 implies that benign overfitting occurs if nl|æe|| > ||]]tt[E)) under (a) or || > |Σح| under (b) is satisfied. For Gaussian mixture model, we see that benign overfitting provably fails even though directional convergence occurs if ni||a]] X (mintr(E)) under (a) or || S Bmin under (b).
We note that Theorem 6.2 under Assumption 6.1 (a) (i) and (b) are novel regimes which were not identified in the existing literature (Frei et al. (2022); Xu and Gu (2023)). Only the result under Assumption 6.1 (a) (ii) with Σ Ip was previously studied. A more detailed comparison with the prior work is given in Appendix A.
The Bayes eπror rate is given by x(I| (/11 if ~ (O, E) and Σ is intvertible (Section 1.2.1, Wainwright (2019)). Therefore, our bounds in the case of isotropic Gaussian mixture is tight up to constant factor in is in the strong signal regime, i.e. the implicit bias of gradient descent leads to the Bayes optimal.
We also note that Karhadkar et al. (2024) studied implicit bias and benign overfitting in leaky ReLU networks in a somewhat different setting. Since their work studied hinge loss instead of exponential type loss and label-flipping noise is added, it is difficult to directly compare their result with ours. Nevertheless, their distributional setting can be viewed as a special case of ours. In fact, their distributional setting (ignoring the label-flipping noise) is essentially Gaussian mixture with ||ا||| R 1 and tr(E) 1, which falls into the strong signal regime in our work.
Moreover, Theorem 4.8 and 5.1 allow us to extend the above result to heavier tailed model (PM). This significant distributional relaxation from the existing results which assumed = is sub- Gaussian and strongly log-concave (Frei et al. (2022)) or z has bounded log-Sobolev constant (Xu and Gu (2023)). For brevity, we only present a result for Σ. Ip:
Theorem 6.3. Consider model (PM) with Σ Ip- Then, benign overfitting occurs with the convergent direction W with high probability if either one of the following holds:
(i) ||a||| Z / and max (n 2112 n
+++1 S S min
(ii) |||||| Σ vn and
max(n ||م 3 nar |10l|| SF- |a1|| - } S p S min { mellual?
Lell
(iil) max(n || 1|, n n n +22 S < n||
Detailed versions of the theorems and the proofs are given Appendix D.
7 PROOF SKETCH
In this section, we provide the proof sketch of our main theorems. The key to establish the classi- fication error bound in Theorem 5.1 is the precise characterization of the convergent direction in Theorem 4.8. The precise characterization allows us to obtain both upper and lower bounds of the
key quantity (s0.1e) in classification error bounds (98), which results in the novel lower bound in the case of Gaussian mixture. We also note that the conditions in Theorem 4.8 and 5.1 are given in a deterministic manner. The separation of deterministic and distributional arguments allows us to substantially relax distributional assumptions made in prior work. In fact, Theorem 6.2 and 6.3 are proved by showing that all the conditions in Theorem 4.8 and 1 are achieved with high probability under (sG) and (PM) with sufficient overparametrization.
||
8

---

Proof sketch of Theorem 4.8 As noted in Section the key to show directional convergence of the gradient descent is activation of neurons.
The next lemma shows that if all the neurons stay activated after step of gradient descent (2), directional convergence occurs towards the maximum margin vector v vec(W)) in transformed sample space, i... W is the solution the following optimization problem:
Minimize
||w || S.t. (yrā,, w) 2 1 for all i I, where w wWc,
where a! = - 2, 2.2...... (T,m) E R Rlmp with æa, =aj(a,y)) Letting maaz (X) be the
maximum singular value of X IRuxpp whose rows consist of at 's, we have
Lemma 7.1. Suppose all the neurons are activated for t 2 T and (a) <2. Then, the gradient descent iterate (2) satisfies ((W())- = O(t=)) and W converges in the direction characterized by Theorem 4.8.
The proof is done by reducing the argument to that of binary linear classification, i.e. classifiers of the form ğ = sgn( (x, w)). fact, all the neurons are activated for all (æx, v:), = 1,... n at step t, then we have
fa W(O) (y. (())
where (n) = ve)(W())). Therefore, if all the neurons stay activated after 2 T, gradient descent iterate (2) becomes that of linear classifier in transformed space, and the directional convergence follows from Theorem 3, Soudry et al. (2018).
To establish sufficient conditions for the neuron activation, observe that, for any i,j, have
0j (y: w (t+1) (t)
<((0,) (1)) ||2 |1? exp( y (()
(10)
C( w (1) (NC yeur) exp( - yu yu (aes; W()))]
Angh
The only source of negativity in (10) are (ya (,) i i
k. We note that event E implies
Kusare yx - |||1| S 20 |a]|| Rmaz (z) + R (2), Vi v # k.
(11)
So. by keeping 20 Ral (z) + 02 Re small (Assumption 4.1 and 4.4), the update (10) should stay positive. Then, it should suffice to make all the neurons activated at step be done by taking initialization sufficiently smaller than the step size (Assumption 4.2 and 4.5).
which can
Proof sketch of Theorem 5.1. establish the desired classification error bound. This is done by
The detailed characterizations of the convergent direction given
by Theorem 4.8 allows obtaining closed form expression of i vec(W), which é X (XXXT) where y (yI...., ) )..........) T R.. To establish i X T (XX y. is necessary to understand the behavior of y (XXT)-1 Letting X can write
(x) 22 ,....,,. ) E Raxp and recalling ã., = (H((H;,)) we
X (a) BiX B2X
Om Bm X),
(12)
where By E IRax is the diagonal matrix whose diagonal entry (By B2)x = ((a,8k). Then we have
XxT = Σ B, Bj.
(13)
JEJ
Notice that Bj's are the same among j J and j E J_, respectively. So. we can write B, B,.j E J and B_ = Bj,j E J_ With a² = I we have
|J+
J_
X B+ +
B X B_.
(14)
m

---

The analysis of (XXXT)= will be done through X || Ty(Z T puy + 2 uy RT, under sufficient orthogonality of z,'s to each other and to l (events Fj, Fiz).
The rest of the argument is split into the strong signal regime and the weak signal regime. The latter easier since we have X z RIn, which further implies XXT ~ R(q+ B + 9- B²), which is diagonal matrix. The strong signal case is more difficult to analyze, and relies characterization of the eigenvectors of [|++ B+yy B+ + Byyy B-) R(g+ B4 + + B2).
careful
DISCUSSION
In this paper, we have established sufficient conditions of benign overfitting of gradient descent in leaky ReLU two-layer neural networks. Here we discuss directions for future research other than the obvious direction of extending to deep neural networks:
Not only showing directional convergence in more generality but also obtaining detailed characteri- zation of the convergent direction remains an important open question. Even for two-layer neural networks we studied, our setting is rather restricted considering more general result obtained by and Telgarsky (2020) for gradient flow.
In this study, we did not introduce noise to the label y as was done in some prior work on binary classification (Chatterji and Long (2021); Wang and Thrampoulidis (2022); Frei et al. (2022); Xu and Gu (2023); Hashimoto et al. (2025)). We conjecture that introducing noise will not change the result for the weak signal regime since in this regime the signal μr is negligible. However, the situation is likely to change substantially in the strong signal regime with noisy data as was observed in Hashimoto et al. (2025) for binary linear classification.
ACKNOWLEDGMENTS
We thank Stanislav Volgushev and Piotr Zwiemnik for helpful discussions and guidance. The author is further grateful to the anonymous reviewers and the area chair of ICLR for constructive feedback that improved the manuscript. We would also like to thank Xingyu Xu for helpful discussions regarding the work Xu and Gu (2023).
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-graine analysis of optimization and generalization for overparameterrzed two-layer neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th Internutional Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 322-332. PMLR, 09-15 Jun 2019. URL https: httpp/ppecceeeeppeeeeepeecc..cst mlr. www.s/vvee.... v97/arrraal..... html.
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 1 117(48) 2020. doi: 10.1073/pnas.1907377 1907378117. URL https:/ wwww www.wppaaaccoo wwtpp/aa..ooo/////aaaee.a.ee abs 1073 10.3////p 1907378117.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical barianee trade-off. Proceedings of the National Academy of Sciences,
2019. doi: 10. 10.1003/pnas. 190307010 16. URL https: /www. pnas. org doi abs/ab. 1073/ / pnas. 1ataass...00 1903070116.
Phuong Bui Thi Mai and Christoph Lampert. The inductive bias of ReLU networks orthogonally separable data. In 9th International Conference on Learning Representations, 2021.
Yuhang Cai, Kangjie Zhou, Jingfeng Wu. Song Mei, Michael Lindsey, and Peter L. Bartlett. Implicit bias of gradient descent for non-homogeneous deep networks, 2025. URL https: //arxiv. brg/abbs2502. 6075.
10

---

Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over-paran perrpaaameterized max- imum margin classification on sub-gaussian mixtures. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 8407-8418. Curran Associates, Inc., 2021. URL https: htttps:/prrceed::: http://oooedddeeeeeeeeoeee ngs neurips cttpsccccppppepeeeeeee wt..ffleeppapr/2221111 Papetr.ppppp........
Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in Mohamed, A. Agar-
two-layer convolutional neural networks. In S. Koyejo, wal, D. Belgrave, K. Cho. and A. Oh. editors. Advances in Neural Informa- tion Processing Systems, volume 35, pages 25237-25250. Curran Associates, Inc., 2022. URL https::/proceeddiiiiee http://rroediiin..eiiiie.ooooooe neurips wwt..ips...pppppr.eeeeoc..e.. wtt.pppsssepppeerfeeeleeee/eeese pappprrfflles__eeeeeepprrrreeeee patpp///222////////////p
pdff.
Niladri S. Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129): 2021. URL
http:/ //jrr org/ papers 222 974 html.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2668-2703, PMLR, 02-05 Jul 2022. URL https:/
hatps://proceediin pwwppedinggg....oooo mlr press vv11vv11111 / 122 .tml..
Spencer Frei, Gal Vardi, Peter Bartlett, and Nathan Srebro. Benign overfitting in linear classifiers and leaky relu networks from kkt conditions for margin maximization. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 3173-331 3173-3228. PMLR, 12-15 Jul 2023a. URL bttps://ppent http:::s//poccedinggsss mlr www.sppesssspeem vi 95/ frei23a. html.
Spencer Frei, Gal Vardi, Peter L. Bartlett, Nathan Srebro, and Wei Hu. Implicit bias in leaky relu networks trained on nigh-dimensionas data. 2023b. 11th International Conference on Learning Representations, ICLR 2023 Conference date: 01-05-2023 Through 05-05-2023.
Ichiro Hashimoto, Stanislav Volgushev, and Piotr Zwiemikk. Universality of benign overfitting in binary linear classification, 2025. URL
org. abwaaaass..... 10538.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statisticcs, 50(2):999 986, 2022. doi: 10.1214/21-ao22111 URL https: www.o.orrg////oooo /10 10. //11 1214/21-acs2113. acs2133.
Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors in high dimensions. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceed- ings of Machine Learning Research, pages 91-99. PMLR, 13-15 Apr 2021. URL https: //proceedings... mll. press pre.:sssss........p.e.p..ee.reee v1 v100vv3/shss 30/hau2aa html.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and general- ization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31, Cur- ran Associates, Inc., 2018. URL http:: http::/::////ccceoeoe//e.m neurips cc/paper_files Paper. pdÉ.
paper/2018/E5 httpa///cee.eeeeeeeeeeeeeeeeeaaa
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17176-17186. Curran Asso- neuriss.rrrppp... cc ccppeerrr.p..ee.eeppeeeeeeeeee.e files/paper.
ciates, Inc., 2020. URL 22 42 2020/ /ile//ee//// ww7.66622afaff55ooc
Kedar Karhadkar, Erin George, Michael Murray, Guido Mont ufar, and Deanna Needell. Benign overfitting in leaky relu networks with moderate input dimension. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information
11

---

Processing Systems, volume 37, pages 36634-36663 Curran Associates, Inc., 2024. doi: 10.52202/ 079017-1155. URL
ctpppss..cc///ooooooooooopeoooo/ ccppaper.pppppppppepppeeeeepeeee /iles/paper/ pdf.
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting in two-layer ReLU convolutional neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardtt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17655-17659 PMLR, 23-29 Jul 2023a. URL https: 0202/kouls 3a html.
htt.ttsss//proceeee /pwp///edddeeee pepooeedingg.... ngs. ml press/
Yiwen Kou, Zixiang Chen, and Quanquan Gu. Implicit bias of gradient descent for two- layer relu and leaky relu networks on nearly-orthogonal data. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine, editors, Advances in Neural In- formation Processing Systems, volume 36, pages 30167-30221. Curran Associates, Inc., 2023b. URL https::/pproceedinnngg meereeddiiiinnnneeeeeeee.....e neurips wwwerrips.ccppappe wwtppccccpppppeeeeeeeeeeeeeeeeee wtw.felles/pppe/2222222 file/
pdf. pdf.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression generalize. The Annals of Statistics, 48(3):1329-1341) 1347, June 2020. doi: 10. 10.1214/19-aos 1849. URL https:
//doi, .rrgorgg//// 10. 1211/1911A01111
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum- interpolants and restricted lower isometry of kernels. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2683-2711. PMLR, 09-12 Jul 2020. URL https:/ :
proceedings mww.m.r......m www..mmes.........mmmm...m..m..e www.ppresssvvl.. 2at55/1aang0000 html.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020. URL htttt::://pppeeeeeee
net foet/fooe forum? LddSJeeLgBKE
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent two- layer nets: Margin maximization and simplicity bias. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural In- formation Processing Systems, volume 34, pages 12978-12991. Curran Associates, Inc., http://///coceceen....mo htttp:://rroocee 2021. URL https:
wwwuuripssccpppppee wiwes//appe///2211 file//c351dee da 5b5e8a 9eaaaaaaaaaa262222------e
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
doi: 10. 10.1002/epa.2200. URL https: doi. wrtg/...//................ 1002/
22008.
Hancheng Min, Enrique Mallada, and Rene Vidal. Early neuron alignment in two-layer reLU networks with small initialization. In The Twelfth International Conference on Learning Representations, 2024. URL https:://// /ttp////peeeeeeeeee/eeeeeee net/ forummiiiiioo di bP zdVrRu.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless inter- polation of noisy data regression. IEEE Journal on Selected Areas in Information Theory, (1):67-83,, 2020. doi: 10. 10.1100//AA/TT222002280 JSAIT. 2020 2984716.
URL https: /ttp:ooooo.....11//o////1 1109/
Roei Sarussi, Alon Brutzkus, and Amir Globerson. Towards understanding learning in neural networks with linear teachers. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9211--322,, PMLR, 18-24 Jul 2021. URL https: http//pptce.ecccpppeeep.poss.sse mlr. press/v153 / russi2 22a html.
Sholom Schechtman and Nicolas Schreuder. The late-stage training dynamics of (stochastic) sub- gradient descent on homogeneous neural networks, 2025. URL https: sectpa://araae /tt///xivv///////////./////aalla http://awx...aaaaaa///// 2502. 05668.
12

---

Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1-57, 2018.
Alexander Tsigler and Peter L. Bartlett Benign overfitting in ridge regression. Journal of Machine Learning Research, 24(1):123, 2024. ISSN 1532-4435.
Gal Vardi. On the implicit bias in deep-learning algorithms, 2022. URL URLhttss:/arxx..ooo abs/2208. 12591.
Roman Vershynin. Biggh-DDmessonall Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2018. doi: 00.1017/9781102211557
Martin J. Wainwright. Bigh-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi:
10.1017/9781 108627771,
Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization. SIAM Journal on Mathematics of Data Science, 4(1):260-283) 2022. doi: 10.1 10.113721M1411521. URL https::/doi.org:
237/21M141512.
Xingyu Xu and Yuantao Gu. Benign overfitting of non-smooth neural networks beyond lazy training. In Francisco Ruiz, Jennifer Dy, and Jan- van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 11094-11117, PMLR, 25-27 Apr 2023. URL https: //proceedings..o mlr press / v206 xu23k.223k2.... html.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017, URL https: http///pnnneeeeeeeeeeeeeee wwwpenrwwewwwweeeeeeeeeeeeeeeeee ftt.:eeeoooommmmmmyy88malll
13

---

A COMPARISON WITH THE EXISTING RESULTS
In this section, provide more detailed comparison of our main results with the existing results (Frei et al. (2022); Xu and Gu (2023)), Since Frei et al. (2022) only considers smoothed approximation of leaky ReLU, our comparison mostly with Xu and Gu (2023).
Since only isotropic nau-Gausiian mixture was studied in the existing literature, we present here sufficient conditions of benign overfitting derived from Theorem 6.2 in the of Σ Ip for the purpose of direct comparison:
Corollary A.1. Consider model (sG) with Σ = Ip. Then, for sufficiently large benign overfitting occurs with the convergent direction W with high probability if eithher one of the following holds:
(i) ||ll| 2 v and n n||lall? Sps
WIll
(ii) ||ll| 2 v and n |||| SP S minlrlllal?? I
(ii) m|ll Sp < l./l
We first note that conditions (i) and (ii) are newly identified regimes on which benign overfitting occurs. and only condition (iii) is directly comparable the results studied in the prior work (Frei et al. (2022); Xu and Gu (2023)). As shown in Theorem 6.3, we have further extended the result in the case of (PM).
Data Regime: Our work considers both weak and strong signal regimes and identified the surprising phase transition in classification error occurring at nı|mu| tr(E). Frei al. (2022); Xu and Gu (2023) only studied nearly orthogonal data regime, which corresponds to the weak signal regime in this paper, and thus did not identify the phase transition. Even the weak signal regime, condition (i) in Corollary A.1 was not studied.
Our results significantly relax distributional conditions in prior work by extending to anisotropic polynomially tailed mixture (PM). Both Frei et al. (2022); Xu and Gu (2023) considered mixtures even stronger than (sG). Specifically, Frei et al. (2022) assumed z is not only aub-Gaussian but also strongly log-concave. Xu and Gu (2023) assumed z has bounded log- Sobolev constant, which is also stronger than just assuming z is sub-Gaussian. Moreover, both work only considered isotropic mixture.
Distributional setting:
Comparing condition (iii) with that of Xu and Gu (2023), we have a better upper bound on (Xu and Gu (2023) requires p plog(mp) & n// (t). We allow the width m be arbitrary while Xu and Gu (2023) requires m 2 log n. We note that Xu and Gu (2023)'s 's result holds for non-smooth leaky ReLU like activation, which is slightly stronger than theirs which requires p Z (nax(1])44]1 n² n).
limited (leaky) ReLU, We also note that our lower bound on p
B PROOF OF DIRECTIONAL CONVERGENCE
B. PROOF OF LEMMA 7.1
Lemma B.1. Consider (M). If all the neurons are activated at step t, i.e. 0)(u0) y,rr)) > holds for all i E I and j E J, then
w (1+1)
20 :0/ =a
exp( exp((yyf(a;;) /o
iel
14

---

Proof. By (2), we have
wj w ((+1) 30 = - Σ exp(-y%/(a;; w (- Vi: Σ (and }
W=W())
Σ exp(-1h/ // ( W W Vay (b (w) xii) (, w
Σ exp(-yif(z W a
where the last equality is due to the assumption azy: (w))) az) > 0 which implies sgn((w))) xzi)) sgn(a,w:).
sgn((n)(,,,;))
Remark. Lemma B.1 implies that the gradient descent update same within j E J4 and j E J-, respectively.
Lemma B.2. Suppose W = (wi..... wm) has w, w if E J and w, w ifj E J_. Then, fæ: W) has the linear decision boundary defined by w = sign((æ, w)
[441 //m w |J_| vm
w.. i.e. sign(f(>; W))
Proof. We consider several cases separately:
Case (x, w+) 2 0 and (x, w-) 2 0: we have
|++
[J-]
f(x; W)
(x,, w+)
(xx, w-) (cx, w0
vm
Vm
Case (x. w+) 2 0 and (xx, w- ) < 0: we have
f(x; W) |++| m
7|J_| (xx, w-) 2
[++]
|J_|
w+)
(x, w+)
(x, w-) (xx, 2 0.
vm
mm
vm
Case (x,, w+) < and (xx, w- 2 0: we have
|J
7|J+|
|-_| vm
(x, T (x. w+)
(x, w-)
>
(x, w+)
(x, w-) f(z: W)
v
/m
Case (x) < and (æe, w- ) < O: we have
f(x:W) => (1++ ((/r) (x, w+)
|--|
(xx, w-) 7(x, w)
Vm
Therefore, have confirmed sign( W)) sign((æ, 1)) holds for all the cases above.
Proof of Lemma 7.1. By the assumption that all the neurons stay activated after 2 T, the directional convergence follows from Corollary 8 of Soudry et al. (2018).
For completeness and to show the remaining claims, we provide the complete proof of the directional convergence here.
15

---

First note that ago((a (an, w )) assumption that all the neurons are activated after T. Then, we have for 2 T,
az((azyi)a;;; w (0)) holds for all E I,j J,1 2 T by the
(a W())
Σ ",,
Σ (an (
Σ Iasslaayiiuann 50
(u. w
(y, w (
where the fourth equality follows from the definition of ã; and w(() = vec(W())).
With this, the gradient descent updates in Lemma B.1 can be rewritten as
(t-1) 3 = Σ exp (-(y, w()))) a,((a,8))..
Therefore, have
w (1+ ((()) a Σ exp((= (())))))
(15)
VEl
which can be viewed as the gradient descent iterates of binary linear classifier of the dataset { wi)ker C. RmP x {+1}.
Therefore, gradient descent iterates ( converges in direction if the dataset {(ē;, 2/ Jver is linearly separable and a sufficiently small due to Theorem 3 of Soudry et al. (2018). We now provide additional details verifying that this result is applicable in setting.
is easy to see linear separability of {(T,, wheer by expanding the following inner product 50)
W, w (+)) = Σ
(waa;((a; w = -E ((azV:)a, (yea,, wn/")
(16)
JEJ
jEJ
Now it is clear that the inner product is positive by the assumption that all the neurons are activated at time 2 T.
em In addition, a -+ -- is I-Lipschitz on (0, co) and (16) implies that (y; w())) stays in this region. Therefore, Theorem 3 of Soudry et al. (2018) can be used with 3 ==
Since (ā,, ve) is linearly separable and satisfies ao maz (X) < 2, lim4 (| from Lemma of Soudry et (2018), ((W(()) O(t-²) follows from Theorem of Soudry et al. (2018), and the directional convergence follows from Theorem 3 of Soudry et al. (2018), respectively,
follows
Now we turn to the characterization of the convergent direction. First, we show that not only [| but also [(o]]] diverges infinity for all j J. To this, note that by Lemma B.1, we have for t 2 T
(1) w
(T) w
Σ
Σ exp( g u. ((((): ((a,g)),,u
(17)
Since [1) is diverging to infinity, we must have |1m000) (1)) diverging to infinity for some j. and hence Σ(=} exp(-y: (m,;; W(+))) co
for some i. Denote such as i..
Again by Lemma B. we have for any j.
(w w ()) w
T))
Σ
Σ exp(-M y f w(n))) (1a))))),(aaa,,,. (T))))
(18)
[-1
2 a Σ
exp( hep(-y.. ys. (x;, ((1))) xi, Di,, w0 (T)) + 00,
16

---

where the inequality is due the assumption that all the neurons are activated at 2 T and the divergence is due E exp( exp(-yi. yi, ( W())) and the fact that all neurons activated at time T, implying (Bi, 24 ) * O. Since this holds for any j. we must have ||w/| diverging to infinity for all j J.
By Theorem 3 of Soudry et al. (2018), the convergent direction is equal to that of the solution to the following optimization problem:
Minimize
||a|| s.t.
(y:e,, w) 2 2,
(19)
which is equivalently written
Minimize
Σ JEJ
1u
1
s.t.
[amnC(amm 2 Vi
(20)
jEJ
Recalling that the gradient descent updates same within j J+ and j J-, respectively, and that || (II diverges to infinity for all j J. the direction that w converges to must the same for all j J and the same for all j E J_ Thus the solution to the optimization problem (20) must have w, = + for all j E J+ and w, = w for all j E J_. With this, (20) can be further rewritten as the desired optimization problem (5).
Finally, the claim about the linear decision boundary follows from Lemma B.2
Before proceeding to the subsequent subsections where we prove Theorem 4.8, we introduce some ancillary results:
We first note that event E implies (11) and the following inequality:
- (1a4)) + Rm (z)) S ||:=::11 < (1 - 02) {1ll21 + Rmaz (=)}, Vi.
(21)
We also note that the definition of implies max (s( W( <
(22)
By (11) and (21), obtain the following lemma, which is going be useful establish sufficient conditions for ad maz (X) < 2: Lemma B.3.
P (X) $ (1 02) 1 + R (2)} + (n - 1) [|| + (202]l Rmax + 01 R2 (z)}
Proof. Note that
(āi, Tx) =
Σ ((1 a0))
- ((ayn))((,naa)) 100, mk)1
(23)
m
< (a, mx)..
where the last inequality is due 72 < ((a,vi) 1.
With this, (11), and (21), for any E Sm we have
| 0112
Σ
3 +
(2, Fx)
< (1 + (11411 R2 (z)) Σ 2i
+ +[1mu||+ (20z|1aa|| Pimaz (z) + 01 R2
Re (2)}]
i,K:ighk
S (1 +1+ 02) (2)4411112 R2 (z)}
+ (n 1) ||| + (20211ea|| (mlaz))mmmx() + 0, 122 122 (z)}1
17

---

where in the last inequality we used Σ KeageR [1b04] 1, which follows from the Cauchy-
Schwartz inequality.
B.2 PROOF OF THEOREM 4.8 UNDER CONDITION (1)
Lemma B.4. Suppose event F. holds with ||]] 2 202 | Rmar (2) + 01 Rmma()) and Assump-
tion 4.2. Then, all the neurons stay activated for 1.
Proof of Lemma B.4. Under || 2 > 202|| Rmar ( (z) + 02 Ri (z), the gradient descent updates (10) stays positive. Therefore, it enough to confirm all the neurons are activated at
Again by (10), (21), (22), || 2 20 pa|| Rmaz (z) + 02 (mma(()) (z),
(i )
an(1 82) 12)(11m11 + (m)n(=)}}
(24)
mmp max | - Vma max |< an - 12)(1111122 + Rmin(()) exp(-pl - pl >
Proof of Theorem 4.8 under condition (i). By Lemma B.4, all the neurons stay activated after 2 1. By Assumption 4.3, it suffices to show on (8) < 211|| Rma (z)) to ensure ao mam (iaax()) 2.
By Lemma B.3 and ||a]|2 202 |||a|| Rimnn (2) + 01 R2 R2aa (z) we have
maa (8) < (1+ 02) (1lua1 12 (2)) + 2(n 1)
s 2(1pe] 2 + Rman (2)) 2(n 1)11
(25)
2(n 10 Rymax (z)).
Therefore, the directional convergence follows by Lemma 7.1.
B.3 PROOF THEOREM 4.8 UNDER CONDITION (1)
First, it is useful recognize the following inequality which follows from (10), (11), and (21):
7(1 - 02)1111111 + Ri (z) exp( eexp(=21/ -25 W())))
Σ C((202, ) 20 |u||| (2) O2 R2 exp(pxx.. f W(O)))
kzleffi
< a, (Br00, w ((+1) - -w0()) (t))
(26)
(1 + 02) uel2 +
(()))
(1llul2 + 20 Rmmax (z) + 02 Ri (2)) exp(-2k. f W())
We start from establishing neuron activation at 1. Lemma B.5. Suppose event E,, Assumption 4.4 and 4.5 with E + E2 < 1. Then, we have for any i.
aj (yKyao; w (2)) 0,
and hence all the neurons activated at 1. 1.
18

---

Proof. By (22), (26), and the assumptions, we have
az ay(ui w, ) 2 m (afn(l 82)RRmm (z) exp(-p)
1
exp(--pp)))
-n(202 Araan (z) 02 H (z)3 exp(o)] P]
1
2 [1 E1)ar(1 82) 82) (z) exp( -p) p) p]
2 (1 E 62) 82 Renin (z) exp(-p) > 0.
m
Thus, all the neurons are activated at t if 1 5 < 1. Lemma B.6. Suppose event E, Assumption 4.4, 4.5, 4.6, and 4.7 with @1 + + E3 < 1. Then we have
max (f (2);; Kei exp( [ W()))) I exp(11 and aax (8) <2
Proof.
By (22), (26), and the assumptions, we have
aj 1, (2)) S
m a (1 (m)(1111ml1 + Rmae (z)) exp(p)
1
+ +n ||| (mma((2) + O1 Rmann (2)) exp(p) } + o)
0 (1 02) E3) R)) (z) + E Rmanl (z) exp(p) + pl
(1 02) + E1 = E3) R) exp(p)
m
(z) exp(p)
1
m
where the second inequality is due to Assumption 4.4 and 4.6, the third is due to Assumption 4.5, the fourth is due to E + E2 < 1, and the last inequality is due to Assumption 4.7.
Therefore, with Lemma B.5, we have 0 < ye faz; W()) s 1, and hence
exp(-y: f:f ( W())) max Kei
exp(-Ux ff f( [xx W()) < max exp(exx( (()) S exp(1).
k
We now show aoz max (8) 2. By Lemma B.3, we have
ao² man
(X)
s {1 (n) R (2)) + +1++111110 R2) Raa (z)}
<a + 22) + E3) Rman(2)
< 4a R2 (z) 22
where the first inequality due to Assumption 4.4, the second inequality is due to Assumption 4.6, and the last line due E + E3 and Assumption 4.7.
Finally, we prove that all the neurons stay activated after 2
Lemma B.7. Suppose event E, Assumption 4.4, 4.5, 4.6, and 4.7 with e + te + < 1, Cues < 1 = 1,3, and 0g S 3. Then we have for any i.j
ay (,, w (1) 0
and
max exp( uyp(-yif(a,; W(!)))
kgli exp(- f (xx; W(O)) < Cy.
(27)
19

---

Proof. We prove both claims simultaneously by induction. By Lemma B.5 and B.6, both claims hold at step t = 1. Suppose both claims hold for _ 1.
We first show the first claim also holds for t + 1. By (26), Assumption 4.4, and the induction hypothesis, we have
ag (yrer, w) (+4)) :
exp( (00 W()))
m
(mn Cw - 02) Rmain()) (2)} x 7(1 - B2) -02)
(28)
71 CwEI)(1 B2)aR (z) exp( yr (2;; W(()))
m
1
yaR (z) exp(-Ui f (x;; W())) 0.
4m
where the last line is due to Cwei S 2 and 02 S 3.2 Therefore, all the neurons are active at step / + 1. Next, we prove (27). By (26), the assumptions, and the induction hypothesis, have
aj (2 j ((+1) ) exp(
-yis(:; exp(pxy:f ))
(1 02) [ (2) + Cwey Ri (2) CWE (1 02) Rina
(29)
1 [ 1 E3 + Cwes + Cwei } (1 + 02)a Ras (2) expp exp( Vi f W(0))
6a ( exp((xx (x;());;()))
where the first inequality is due to Assumption 4.4 and 4.6, the last is due to the assumptions on éc.
Since all the neurons are activated both and i have ay (zi;, w.j u ((+))))) a,vid((;; w/ ))- = ((a,y))a, (yari, w ((+1) (1)))
With this, (28) and (29), we have
22 a R Rin (2) exp(-yxppee V W())
S vn w(++1) (x W(()
(30)
S 6a Ra (z) exp(- uuf((;; W())).
Now we fix & ls and let A, = exp(-y. (( (30), we have
By induction hypothesis, we have A, S Cw. By
expl W(,))
A4+1 S A exp
al mii (z) exp( v. (x: w(())
2a (z) exp( nb (xx; w(t)))
(31)
72 RR R exp( y (xx w())) {Ar
24 Rana (2)
A exp
(32)
x2 R2
24 24 then A < A, immediately follows from (32).
If A, >
A, < 24 (2))
(z)
(z)* then (31) and the fact that all neurons are activated at time t, yielding
Va; W(t) for all i, implies
24R2
man (z)
A
2 R2
(z)
exp
6a Ra (x)
24 R4 yaar
(z)
exp(1) S Ow.
7 R12
(z)
20

---

where the last line holds from Assumption 4.7. This concludes the induction argument proving the desired claims.
Proof of Theorem 4.8 under condition (ii). The conclusion Lemma B.6, B.7, and Lemma 7.1.
now follows immediately
from
C PROOF OF THEOREM 5.1
The proof of Theorem 5.1 is done by first establishing the equivalence of the maximum margin vector and the minimum norm least square estimatorice. v = X (XXT yy, and carefully analyzing the behavior.
To prove v X ( yy we rely on the "proliferation of support vector" phenomenon due to Lemma 1, Hsu al. (2021).
Lemma C.1. y "eyT(XX (- yie,
ffr all then
i X (XXX))
Proof. By Lemma 1, Hsu et al. (2021), the assumption implies all (æ,, v.), i = 1, ....... support
vectors. Under this condition, the optimization problem defining is equivalent to
arg min ||/] subject (w, y(ā.)
and is also equivalent to the optimization problem defining the least square estimator.
As noted in Section 7, the analysis is done by establishing X || B+yy B+ q B yy B-) + R(q+ B², + q²)
Lemma C.2. evevnt En n Fez holds, then the following inequality holds
||XX (1lw)]yy vy +RI,) ER,
where & max n.
Proof.
Noting event Es implies T1 < Es R and X = || + + +Z 3
ZZ we have
(11m112yy)) -(1m)) yy |Xx - 1xxT-(1lall
RIm)
(1 T|I |(Zx)) 11 + 12Z -Raa
R + R+ R ER.
With (14), this establishes X ||||| "i| B+ yy B+ 9- B yy B-) R(g+ B + q- B²)
It is convenient to introduce B 9+ B², B² where B R=x is a diagonal matrix with
v V + ifie 4
Big
V q- + if I..
Lemma C.3. If event Es n Ez holds, then we have
B X B Al < E R
where
A:= ||||| PB (q+ B_ yy B+ + - 9- B yy B-) + RI
To obtain approximation of from Lemma C.3, we need the following ancillary lemma: Lemma C.4. U - VII < sL and V > LLn for some L > 0 and [0, 1). then
||U v-1 < 2
21

---

Proof. Since V = LIn for L > 0, V is invertible and |V~ ||| 1 L-
Then we have
1| 1- | VII s.
Letting S = In - -n
-V-1, we have ||S|| v 8 - 2- So, U is invertible and
[1v-~ 1n1l - ||| + |||| + 5 8
- 2s.
Combining with |V~ < 1,-1, we conclude
| - V S - I, 22I
Now we are ready to obtain the following approximation of (XXT)-1 which our remaining arguments heavily relies on: Lemma C.5. Ifevent E₁ n Es holds with ε s 22 then have
24, _
-B 1 v
R
Proof. Note that the additional assumption implies ēg," S 1.2 Then, the desired conclusion follows
from Lemma C.3 and C.4 by taking U = 1----XX B = A, s = εq,"" and L = R.
By Lemma C.I and C.5, the rest of our arguments is reduced to the analysis of (B-1y) T. A-1, Here, we present technical results regarding this quantity which are used frequently later.
Lemma C.6. Let y = 1, 1_, where (1-), = Lf e 4 and (1-), = 0 if E 1_ and (1-); = 1 if 1- and (1-); = 0 if E L. We have the following equalities:
1. if = -,,9- = O,
y) T A-1 -R- {(1-
n||la|1
n4 + + +
1+
12 12||pa|1 1 7 R
(33)
7-- n p
n 0||1=112
14 + 7 n
1
T
12 + R
2. 18 0, 1,
(B- (T'yyT== A -R- {(----
n m2|1pa12 2
I- + n
1
n n2|lu|122 +
n
(34)
n||||||2
7- r''n+ n4 + +
1 1
1
n n||lu|12 + R
71
3. if 9+9 #
(B- -1
=td(2t + +72 + (q- + --
V a+ + 22 1--4p-9--00
- (1)+-1)n1111 + (g- + +
(35)
V-- + 7 (1++ + + - 7)m+ + (a+ + >² R 1-
where
d(g+ + --- + )
(36)
(1 - 7- - |||||* + (a+ + + + 22aatl1 +++++34 RRRR.
n.
22

---

Proof. Let A -E= u be the singular value decomposition of A with $1 82 Sn. We split in cases.
We first consider the case either 9+ 9- 0, i.c. either
|+ or [J_] = O. Then we have B B+
q- and = B_ if q+ = 0, and hence A = 1
yy + Rl,, either way. Then, we have Thus,
$1 n 2 R. 81 R, i 2, and can take u2 vn.
A- |1]1 + R
y y
+ R
u
v vT
22
y (12 |el? 2 + RJR V
n pe||pa|1
R
n
(37)
VT R v vn
1=1
RR-
In
12 n1|la|12
y
Case q+ = 1, = 0: In this case, we have = B+ as noted earlier. Since y = 1+ 1_ and
B y = 1, - 7 1_.. we have that
B v) A-
n| 1e|l
(BT'y- y
R
BT 2 y
n/| ni||aa| +
n
n4 + 7 In 1
=R-
11| + R
n g|||a|l2
+ y n n4
n 14 2 R
72
Case 9+ = 0, 1: In this case, we have B = B_ as noted earlier. Since y = 1+ 1- and
B '1 1_, we have that
(B v) "TAT" TA-1
T
n n0|la|12
(B- y. y)
R
B 1
12 n0||10|1 12 + R
n
{
72
|1|1
7-1n n + n
R
1+
n
|||
2 + R
re||ka|12 ?
ni
y'1 + n
7 n
T 1-
|A 2 + R
Case 9-9- * 0: this case, we have the span of {B-1Byy, B B_y) equal to the span of {ui, Uz), and s; R for i 2 3.
To determine Σ 1,2 u. it is convenient to use isomorphism between the span of {B 18-'Byy. B B_Byy y and 2 by 1 /n4ei and 1_ + en_ez. Under this isomorphism. we have
B B- Va+ + 7
1,
7
4
vn+
El
n/n-
62.
Vq- + 7
V + 729
Vq- +
7
(38)
1
7/4
VI-
B-1 B y
-1
V + 72a -22
Vat + 2z
Va- + 2
V 72
Thus, E i is regarded as a 2 x 2 matrix
7/447-11
n+ || +
V(+ + (29-)(9- + z
(39)
7v44 ||
n |||1 R
V(g+ + +r2g (g- + 77
23

---

Thus, Ex=12 87 uu is regarded
7 7y |
-1
n |1|1 + R
(9+ +-779-11 )(8 + 7²
7y ||112
n || R
(a+ + 1²q-)(B ++)
(40)
n 1--+n-111 1|
n |110|122 +
V(++ + 7-2---120009 14 + 72
dd
Y /v441-1 pAll
n4 |||l + R
V(++ + 7-2g0)(0 + +72
where
7 n nー || (a+ + 9 (g- + -²2++
d
[n+1|u|12 + [R](n-11111 R3
Since B B-1y 6
vTT E1 Vo++>²9-
v Ve-trag
E2 and B- 1 u, for all i2 3, we have
(B y) TA-1
|| 2 + R
n |e|2
1+
4+ 7-
Va+ + 7 -2 (9- + 72
1|
7m Rel1
1
V9- + 7
V + 32 (a+ + +
(41)
=(d(a+ + 9 +
VV+ 2- {19- + +22 -2nn-111111 + (g- R+)
Va- + ( + 7 7)m+111112 (4+ + +r²g))R]1
Before proceeding the next lemma, we note that the following inequality holds under Es:
2 n²
n²
4 n4
(42)
The next lemma establishes useful bounds on d.
Lemma C.7. We have
d(g+ + 7 +73 < 72+ 5(1 5(1 7232
(nllual2 R))
a+
(43)
547 (nllua]² + R)
s 4
If additionally Eg(E3) holds for some Eg [0, 1). then we also have
(1 11-2)((1 - 22) (nelleal2 + R)² (8)2+20 2R?
d(q+ + + + 224))
(44)
8
Proof. We first note that
4- 2 (q+ (q- 72 = (1 + + ) +
2 +222
======22 72 2- (1- (45)
With (45) and also noting that n+n <
2
4 it is easy (43) follows from (36).
24

---

By (36), (45), and (42), we have
d(q+ + +
+
2 (1 [1 72)2
9+0- (ml1za|13)² + (-2 + (1 -01))2)2444 -+ R2
(1 E1 -2
9+9- (1a))aa11)² + R²² + 7
(1 E1) - 72)2
4+9- (1|| + +R)² + 7
where the last inequality is due a² b2 (a+b)² 2
Now we are ready to establish sufficient conditions of u X(XXX)-1y
Lemma C.8. Suppose event N==1,2,3 E, holds with ε < % and further assume one of the following conditions holds:
(i) q- = 0., n||lul < ,मक R. and VNē S z
d
(ii) q+ #0, re|lel22 < XR, and Vnš S 5(++)) for some S gr
2y(1-7}'
1 (ii) 4, > 7, n||lul2 2 XR, and VNE S C(v.9-,3,, A) milul for some X > O, where
E3, == (1- E1-E -7)
5(1 +
Then, we have
④ = X(XXT)-''
Proof. By Lemma C.I, it suffices to show y (X'XT)- > 0 for all i.
By Lemma C.5, we have
y T y:e:
=BB 3) T B(X BB-1 y;e; y;e
2(B-yy) v) TA A B yie: - BI B 2Eg, R
(46)
BB (B-'y) T A 1 y:e. - 2B - -IERR
9/:
n4
+
n_
a+ 729
q- 22
BB { (B 2) TA A 1 y.c.
24, 3/ vn
where the last inequality follows from the definition of 9, and n, + The rest of the argument is split in cases.
Case g+ =1 0: By (33), we have
(B_ ") T A
B- y:e:
R 1
2|l n+
n
if I+, if I.
(47)
~||
R-1
1 +R
Therefore, by the definition of Es. (46) and (47), we have (XXT)
1 y
|| (1++ - )) - 33
R nl + R
ifi T+, ifie..
(48)
7 R
7 n
n|| (1+x (11-Es) 27 -3 n5
25

---

Case 9+ =0,9- 1: By (34), have
(B_ y) T A B=1B_'yye y;e:
r R- (7-1 ni uel 2nn tm
(49)
plll +1
12
R- |||
u|l
nt +
if
R2
Therefore, by the definition of Es, (46) and (49), we have
y (XXT) ) y:e; 1 (
?| (1+ (11-5s) - 27-3/188
if E 4+
(50)
R
?| +
(1+7 (1())))
24 -3 NE
if I..
Therefore, for both the cases above, it suffices have
|e] 12
(1+>~))(1 53)
1
and 27 2 VTs
R
2'
2
which follows from the condition (i).
Case a+ * 0: By (41) and (46), we have for i E 1
y (XX ) yie:
2. Bij [elle+ + 1 -
(51)
x x V a+ + 72 { (9- + 7- - ---n-nn11u + + + +
29 3/2 3/2R R Vnēl
and for i E 1_
y ([88T)-1u 'ye yee,
> BB²²1 [dll+ + + + + (24+)}-1
(52)
x { (Vo- + 72 (1+ + + - 7)m 11112 + (a+ + )-
29 3/2 3/2R Vnē
Under regime (ii), (43) implies
54h d(g+ + +)99))
(1 R)²
(53)
4
By 4- > 72, we have
(q- + 9 7/11111112 (g- + +
9, R 7(1 7)n || 2
2 4 R 7(1 - 7)
(54)
> 4 R,
2
where the last inequality is due the assumption on A.
Similarly, we have
(a+ + +---- - p1 + (g+ + 9-9-))
l. R.
(55)
2
26

---

Therefore, for i 4,, (51), (53), and (54) imply
29
y (XXXT)- yse,
> "ye,
B R-
207
Vně
2 0,
(56)
5 + A)2
where the last inequality is due to the assumption on v'ě. The same conclusion analogously holds for E I- as well by (52), (53), and (54).
Under regime (iii), by (43), we have that
50g d(g+ + +7 Ma- + ++)++) S 4
(1 + 1= + (mlleal13
(57)
With (51) and (57), we have for E I+
y (XX yie;
qi [q, 7) E3) [||
> 1
54 (1 (1l1))211111))))) 24, VVER"
(58)
-[B 12 (1) Es) n// 12
+ 6(1+1-1) 2//né
R 2 0.
Similarly, the same lower bound holds for i I_ from (52).
Remark. By similar argument we can show under (iii), an upper bound of the similar form as (58) for i I+ whose dominant term is (q- + 729, p|11 Similarly, for I_, we have
upper bound whose dominant term is (q+ + 7-9- [ |||l? If we have < y, exactly one of q- + 7 Y and q+ + --2-- - 7 becomes negative and the other stays positive. Suppose Q- 4- - 7 < O, then we have y ) < 0 for all 4. when |||l sufficiently larger than R, which means the equivalence of v X (XXXT)- y provably fails in such case. The same applies with the case q+ + 7-9- Y < 0.
With v
T (XXX)) ) ) y. by defining
X B+ ((XT))
w+
Vm
X B+ (at B4 B4XX B + + B-) y.
mm
(59)
X B_ B
Vm
- B_ (xx T B4 B
V
we have v = w j E J and wZ = w if E J_.
By Lemma B.2, the network f(: W) has the linear decision boundary defined by
J+1 mm
w
J
(60)
By (59) and (60). we have
1 = TT (g- B_ + B-) (XX y.
This implies
|| 12 y (XXXT)
(1- + + B_) X T + ly,
(61)
(w. 11) yy (XXT (g+ + +-BB
= = (XXXT)--1 (g+ + B-) (11xaal2y) Zp).
(62)
27

---

We need to obtain bounds of || and (ı, pi), respectively, in order to later establish classification error bound of w.
To obtain bounds of || the following inequality is useful.
Lemma C.9. Suppose that the conclusions of Lemma C.2, C.5, and C.8 hold. Then, we have
|||2|| (1] + RK2) S <ERK2,
and
20 -
(10 -11113// I
4r E2l( TA |R + - V
3
where
K1 = { (XXX -1 B 2
{B v) BBXBB(XXXT)) B By + + B-) and
(63)
K2 (0+ + 9 B- (-
= I1+ + B-) B B(X B. B
(64)
Proof. Letting v- = (a+ B+ + q- B-) (XXT)) we have ||00||2 = w XXTo. Then, by (61) and the conclusion of Lemma C.2, we have
||| 2 (1|x|1 (v, (v, v)² 2 R||u|??) = 2|
The first desired inequality now follows by noting (v, y)² = Ki and ||aa|² K2.
To show the second desired inequality, we note that (62) implies
(1) (4) = ||ll1 VKi + (B- "T T B B- + B-H
(65)
+ +B T B(X A-1 B (q+ B + +
By Lemma C.5 and (65), we have
() - 11111112 K2
s [[ T ||| 111 + q- 9-B--IllZZl
20,
+ B
111yy1
|B B+ + BB
R
29 E. VNē2
S 4 E2 B v) T 1
where the second inequality follows from the definition of & B-11|| S gx - # and 1|g B4 + q- B 1.
Lemma C.10. Suppose that all the assumptions of Lemma C.8 hold with Eg S }/2 in (ii) and (iii).
Then there exists constant & which depends only on 7 and q+ such that
|
S é
n
2
Furthermore, there exist constants é and N which only depends on 7, q+ (and under (ii) and (ii))
such that 2 N implies
2 2
n
14
R
28

---

Proof. By Lemma C.9, the proof is reduced to bounding K, i 1,2.
By Lemma C.5, we have
(B ((XB(XXXT y
BB (q+ + Q-B-)y - - +
2
|1 |BByyllbb B+ ---B-)y1
20. &
9+ + 79-
9- 79+
Vg + 7--- 1+ V + +
1+
V u+ + +72g
V q- + -2
20. E R
(a+ + )2
(q- + 79+)2
2+ + 72
144 +
9- + 72 n-
g+ 7 14. +
9- + 72 11-
207 E
n2
R
V
47
20, 2ně
R
(66)
Similarly, we have
(1 B+ + q- QBB-)B-- B(XXT)- -B B. B-
11( B+ +q-B-)B- A-1, B-
207 E
11 B4 + -Q-BB)B-B |
R
2q E
9+ +79-
9- + 79+
n
R
max
1/+ + +-2
9- 7
V /
207 18 1
72
VT
47
24 2 VNÉ
R
(67)
We split in cases.
Regime (i): We first note that nil ne||u|12 < 1+(149755 R S 7Rt implies
R- S (1 + ( + R) R)
(68)
We first consider the case when 7+ 1, 0. By (33), have
(B 3)
TATTAA11 A B (q+ + q B-B
= =BT y) A y)
(1-
n ||||
n4. + 7 + n
R
n+
r2| 14
12 + R
n
n ne||ua?? 2
n4 + y n
(69)
+x-1 7
n
nu Te||pa|1
2 + R
n2. + 7 -
nm
R
<(1 + 7)r 2
7
n1|la|12 R
where the last line is due (68).
29

---

We also have
(B-1y) ( BA B+ + -q-B-)u
2R-1 { (1-
1211u11 | (++E))(1+ (3)(1+>)))
n|| + R
2
n
2
(1
Eg) + 7-11
--- x-2
n2 22|
R
2
n
(70)
2R-1 { (1-2)
1
n4 + +
n
2
212(1 + ))} n 1
where the first inequality is due to És. the second inequality is due to the assumption n||æ||/ <
T R. and the last inequality is due to 7 (0, 1).
Analogously, we have the same results for q+ = 0, 9- =1
With these, (66) with (68), and noting that 9, = 72 when 9+9- = 0, we have under the regime (i)
2
p1 + R)2 S
2(1 + +77 -
8(1 +
2(1 +7)
(n |1|2 + R)2
(71)
n²
S Ki S (1+7)² (x-2 + 27 - )
2
(1 2 + R)2
for sufficiently large n. Similarly, (33) implies
(q+ +9-B-)B -A- B y|
||A BB.'vll ylll
1 {11
n||ke||2 n4 + +y- 2
R-1
n4
(72)
n2 |e|| 2 + R
2
+y 2 (7-1
T1m + +
n
n||l||? 2 + R
n
and so under the regime (i), we have
2(1 - 7) 11 + R S Ik B+ + +--BBBBB A B--yll $ (1 + +
n
n2
+ R
(73)
With (67), we have
3 8(1
2
2(1 + -/--11))) n 2(1+>)
1
(1 + R)2
R²2
(74)
K₂ < 71+ -2 27 =)) 2
(1 12 + RT²
for sufficiently large n.
Thus, by Lemma C.9, (71), and (74), we have
{
{ 3 8(1 + (1(1+))) 7) (1 (1+7)) 7) (7 -2 22 =2)² n 10l1pa11 + R
| S (1 (1 + 7) (7 2 + 27 -8) 2
n |1 + R
30

---

with the left hand side being positive for sufficiently large
Case 9+9- * 0: By (35), have
(B-'y) A A (g+ + q- q-BB-
=fd(a+ +- 9-- +
(a+ 29-) ( + +22 ||11 + (q- + R+)
(75)
(a- 7 + 7) ||ll (a+ -2 (-)-)13 )18
Thus, we have with Lemma C.7
(B 1 A B (a+ B+ + B- ly S {d(q+ + + )a- + )) (n(+))ln(((lllll R)
n
(76)
$ (1 (1- 21 2-) - 1
Similarly, (35) implies
|1(+ B+ +q-B-)B- A
[d(a+ + + +
(a+ 7-- {(g- + +-²9 - 7) 1112 + (q- )+ n
(77)
+ 4q- + x9+) 2 (2 +229- - 7)m+11m11 + (9- + -/-++299-)FF )
Thus, we have with Lemma C.7
[1 B+ + BB)-BB)BB A-1 B B-yyll {d(l+ + -3 / R22)
Vn
$
[1 - Eg) - 72 9 n n11 1 2 R
(78)
We now consider regime (ii) and (iii) separately.
Regime (ii): By (66) and (76), we have
K1 <
8
+ 2(1 + 2) 28 28
2
n
(79)
[1 (3)
2
(n [n| + R)²
Similarly, (67) and (78) imply
8
2
K₂ S (1 [1) -2222-9-
+ 2)
(80)
(nll + R)
(54) and (75) imply
TT-1 (g+ + B-)B
2(((a+ + + + +,29+)} -1 Rn
2
(81)
2(d(at + 7 + +
nnnllll1 Rt)
2(1 +
By Lemma C.7, (66), (81), and the assumption on غ, we have for sufficiently large n
K, >
29, 2(1 + ))g,
2 n
9,
n²
(82)
5(1+
nn 1 + R)
5(1 + X)
(nll + RR)
31

---

Similarly, (54) and (77) imply
I1( B+ +q-BB)B- A- B B-yy y|
2
zld(e+ + + (q- + +)(
97 1
2
R
(83)
97
=(d(a+ +1 (9- + +)/g+))
VnR
2
S
Zdd(e+ + + - (9- + }+
Vr(nalulll= + R).
2(1 + X)
By Lemma C.7, (67), (83), and the assumption on ē, we have for sufficiently large n
K2 2
20-
2(1 2)g, 2
9r
}² n²
(84)
5(1 + X)
(n 12 + RJ2
5(1
X) +
(Filleal2 R)2
By Lemma C.9, (79), (80), (82), and (84), we have
{ 5(1+
4-
2)
}
2
8 (1 - E3) - 92)
+ 2q,
28
2
n n2|1a|1
+ R
(85)
l (1+
8
22
n
(1
(1-
12
R'
where the left hand side is positive for sufficiently large n due to the assumption on é.
Regime (iii): By 10|1ea112 2 AR, Vnš S Ö.
R
C S x. (66), and (76), we have
8
(1 1 n
n||la|12
2
n
K1 5
+ +20
(1 - E])( 72 22
R
(nillaal2 + R2)
(86)
8
+ +20 22
1
2
n²
(1 - =1 72
vn
(1l1lee12 + R.2²
Similarly, n nl|/u|2 2 2 XR, v v < Ô alll
S &. (67), and (78) imply
+ (1 r2 r2||ke|1
n
K2
(1 - E1) 22999
R
(nll + R)²
(87)
8
x
1
+ -
+20 20
(1 51 - 22)2400-
vn
(nelbe| 2 + R2)²
By (42) and (75), we have
B v) - B- (q+ + q-B
1 Es
2(d(2+ +
+ )} 11 '9, -7)
n(n+ + +n>lll11
2
(88)
2(d(g+ + 9 (4- + 72 (1 E3) (97 - 7) n² n211
2
By Lemma C.7, (66), and (88), we have for sufficiently large
2(1 Eg)( 7) n2² ||
(1
n2 nellul12)
K1
247²
5 (n |0| 2 R22
R
R
2(1 Ez)( 77
2c 22- -
+
2
n²
20
(89)
5(1 + 11)
Vni
(nllea|12 + R2)2
(1 -E)) - -7) 1²
n²
5(1 + 111)
(n]
| + R)
32

---

Similarly, (42) and (77) imply
|1( + q- 9-B--B-- A-1 B B-y y1l
2 2dd(1+ + -0- + +))4 "( - n (n+ + n 1=|
(1
[g)
(90)
2(d(0+ + +7 9-) + )) 9, - -71
n: pel
4
(1 Eg)
[dd(++ + 7- (a- + ++)++)) (1, - 7)
n1 |el1
2
By Lemma C.7, (66), and (90), we have for sufficiently large
2(1 Eg) -7)
n 1ell2
(1+
K₂ 2
247
5 (m 14|
2 + R)2
R
n 14
R
2(1 - 5g) -7) Vn
20
+1
Vn
29
5(1 + n|| n1|m|12 R)
vn
n | 2 R.
(91)
2(1 - (g) -7)
20 -= +
n
5(1 1-
vn
[n|lua R))
(1 (17 -7)
11
5(1+1-1)
(n |1 + R)
By Lemma C.9, (79). (80), (89), and (91), we have
(1 (1-Eg) Eg) - 7) ?
8
+2 20
+247²0
1
+
2
+ -(1+1-1)
(1-
- (g)
7222444
||
(92)
8
20 x
+
| (1+
+ 224
(1
71
vn
2
R'
where the left hand side is positive for sufficiently large n.
We now turn to obtain bounds of (w, p))
Lemma C.11. Suppose that all the assumptions of Lemma C.8 hold with E3 S 1 in regime (ii) and
(ii)) Further suppose ε2 < D va uell" in (i) and (ii), where ò is a constant which depends only on t
R
q+ (and X under regime (ii)). Then, there exist constants 02 ē22 N which depend only 7 94 (and
under regime (ii) and (iii) such that n 2 N imply
71
1
7I p||
(10,
11)
S
02
2
+
R
1 2 + R
Proof. By Lemma C.6 and C.7, we have
7 vn
ff 0,
R
( A-11
(93)
8q7
Vn
if ff44- + 0.
(1 72
9
n 1 + R
The remaining argument is split in cases.
Regime (i):
33

---

We first note (71) and nl| 1 RR imply
n 1
n| nl1pel1
S (1++)) (7- + 27 88)
(94)
64 + 7)3
R
R
Furthermore, Lemma C.9 and (93) imply
7
20 2
(w, 14) - -1111111
Ki
Vnē2 +
6. v V
3
3
7
47
+ 20
28
V VnE2
3
(95)
y 2 + 27
-g
V /,Ê2
+ 2
-
n2 | 2
D
R
where the last line is due to the assumption on $2. By (94) and (95), suffices to choose π so that
y= 2 +2 48
D
<
3
8(1 + 7)33
Then, we have
1 n |1 2
n ne/1
<
S (i, p!)
64(1 + 7)3
n n1111 2
+ R
64(1
733
R
2 7-2
2 + 27 15+ +
1
n! pell
S (1 (1+ 7) { {--2+ +2 +
1
n2 p0l1
8(1+))3
R
8(1 + 7)3
n |2 + R
Regime (ii): We note that under regime (ii), we have ||ll//KK the other hand, Lemma C.9 and (93) imply
-|| - by (79) and (82). On
8
VTR
20 2
(1 14) - / Ki
<
82
3 E
3(1 (1
22
11
2 + R
8
EgR
n2
n2||pe|12
20
3(1 (1)
22
Vnll 11 12 n2
2 + R
3
(96)
80
11 11/111|1 12
20
n ne|lu|
+ +
3(1 ())
2) n2 n1|11|11 73
+ R
3
n
n||la|
2 + R
8
24
n||pa|2
n
D
3(1 - (1) 7 P
9
3
n
m
2 + R
Therefore, choosing an appropriate D suffices to establish the desired bounds. Specifically, under regime (ii), we have by (82)
4- ni r1|lza|12
|| K1 2
5(1
+ 2) r2
| + R
and hence it suffices choose D that
8
2q
D <
3(1 - 311-2)(11 - p/
3
10(1 + X)
34

---

Regime (iii): Similarly, we note that under regime (iii), we have // and (89), On the other hand, Lemma C.9 and (93) imply
n - by (86)
18 p1) ||1| K
8
Vn.
29,"
82
E. /nÊz
3(1 (3)
92)
R
3
R
ni
p
29
E
V T82
3(1 - (1)
7+0 ve n
112
+ R
3
8
ER
n
p
20
2
E²
(97)
3(1 (1)
2 n/ n/
|
2
R
3
112
20 2
n [0||
-1- 11|11112
+
80
+ --
3(1 - ()
+ R
3
14 12 + R
8
--
24 2
5(1
+ ー-
r2|1
3(1 - (1) - 72) 9+
3
n
10 R
By (86), (89), and (97), have the desired bound for sufficiently large
Lemma C.12. Consider model (M). If w E IR such that (w, μ1) > O, Then, we have
P((w, yæ) - 0) I exp { -c
2
(w,, p.)
[/
where c is a universal constant and || is the sub-Gaute Gaussian norm of z.
If z E with NO, Ip): then we further have
(w. p2)
(w. p1)
(wv, p2)
( ||/||
< (PW (x,))x) < 0) =
Bmmd
(98)
||00||
where kctt) = IP(5 2 t) and Bmin is the smallest eigenvalue of and Bmax = ||:||.
Proof.
Since y = f + yz. we have
P((w, y s 0) (V 2) (ww, ((w,,)) 14))
P((w, z) 5 -ww, (w,,)) 11)) + - IP( (w, x) S ((w, 14)
2
P(kw x) (w. 14)).
Then the desired conclusion follows from the basic property sub-Gaussian distributions (see Proposition 2.5.2, Vershynin (2018)).
The second result follows since (w, z) (w, ) (Ww E) NN(0, w Ew) if AO 2).
Theorem C.13 (Detailed version of Theorem 5.1). Suppose event 0 E, holds with one of the following conditions:
(i) 9- 0, 1l1 < T R. and Vπē < 2²
(ii) 9+9- # 0, 22|lp||2 < 2 R. n < 20
and E3 S 2.
(iil) 9. y. nl|lel2 カ
R, ES 1/2 and Vnē (0(0))))
R
|
35

---

Further suppose &2 S δ vall (i) and (ū), where D is a constant which depends only on 7 9+-
Then, there exist constants e and N, which depend on ry and 9t, such that n. 2 N imply
ne re||
P (u W) 0) exp
"T (m 12 RJ
If x E with E ~ (O, 1p). then we have instead
1- min
relleal12 $
c comid (
ni|la|l 3 } (nlllali + R
12|||a||2 + R
where k(t) = EP( 2 t) and 8min the smallest eigenvalue 2f 2 and Bmax = ||ا|||
Proof.
Since we assume VNē z 1 in all the regimes, have 2/2 for sufficiently large n.
have By Lemma C.10 and C.11 with (>(1-7)'
n pa
22 n 1 |
é
n R
δ1
14
2
R
Then, the desired conclusion holds from Lemma C.12.
D PROOF OF THEOREM 6.2 AND THEOREM 6.3
First we establish connection between events E(O1, 02) and Ei R), E2(22: R).
Lemma D.1. Suppose (E R) n E2(E2, R) hold with ε S 2. then event E(I,, 02) holds with
ê1 and 02 = 2 |||
82 R
0 = 2
Proof. By Ei R), we have ||| - R
<
E1 R and (zz, zn)l S f R for any i + k. Then, we
3
have
2;
2k
EL
R
|
(1
)
< 2
where the last line follows from the assumption é S 2- Similarly, by (,,,,, R) n Es(E2, R), we have
K
Zi 1
)
E R
ε2 R 2||
||
||||||
V(1 5 H
where the last inequality is due to é S 1
D.1 PROOF OR THEOREM 6.2
For model (sG), we have
Lemma D.2 (Lemma $4.1, $4.2, Hashimoto et al. (2025)). Consider model (sG). There exist universal constants C i = 1, such that for any 8 E (0, } event E, O Eg holds with probability at least 1 - 26, where
=trEE),
ε = C₁ max { n log (+)
E| log (#) ||||| /tr(Z)
82 = Coynlon (1)
36

---

Lemma D.3. There exists universal constant C3 such that have with probability least 1 6
n4 n_| S C3y n log(
Proof. By independence y, and y/ E {+1}, Hoeffding's inequality implies that
Σ yo S C31 log(t)
holds with probability at least - 6, where C3 universal constant.
The desired result follows by noting that >, = nt n.
log( with probability at least 5.
Corollary D.4. Event Eg holds with E3 == C3
With these, we can rewrite assumptions of our main theorems, namely Theorem 4.8 and C.13, using parameters defining the model (sG).
From Theorem 4.8, we have the following result on (sG).
Theorem D.5. Consider model (sG). Suppose
| pel
tr(E) 2 max 201 v n logg( 20 log (o1 CB
(99)
||
and further suppose one of the following conditions:
(i) | 2 2.18 max {Ci [CI log( Cim Cog )1
C2 / nog( pll
a < [1.2 + tr(E)) and a s 0.2 tur()
m
67.2c
(ii) tr(E)= 2 n n||
722
453e
tr(2)
max {CI / (oggg))))()11) Ion C2 log( wll).
73
a s (8tr and o s 0.1 xx(
Then, we have with probability at least - 28, the gradient descent iterate (2) keeps all the neurons activated for t 2 1, satisfies L(W()) = O(1-2) and converges in the direction given in Theorem 4.8.
Proof. By Lemma D.1, D.2, and the assumption (99), all conclusions of Lemma and D.2 hold with probability at least 1 25 with
R = tr()),
C max
Vn (loo(()))2))))) log(
||>>|
0
< 4
2
2tr(E)
C2 C2 log (og(() Mall
E2 R
02
2 ||
2 (/r((E))lm)
2
Then, have 0.91 / (r((E)) Rmin( Rmar < 1.09 /I(E))
37

---

From these, have
202|| |1| Rmaz (2) + 01 Rmaa(
< 11099C /nn log( +))l=* wlll
(100)
+ +0.6C1 max (/llog())122) p log log (1)
22.18 max (Ci y ( Conlog C2y n log( ) E pll)-
We first show the desired conclusions under condition (i).
First, is immediate from (100) to see || 2 282 (2 (z) holds under condition (i).
Furthermore, condition (i) also implies that Assumption 4.3 is satisfied since
a<nlllul12 (z)) 1.220 (m]] tr(E)) s 1.
We note that exp(p) < 1.26 holds under condition (i) since
3 2
P S oV
< 1.35a V m 11 (r())
< 0.27
tr())}
0.27
< 1.2 S 0.225.
where the first incquality follows from the definition of p and 0g s and Rmax (z) < 1.2 tE(). the remaining inequalities follow from condition (i).
Noting exp(p) 1.26 and p s 0.277a + tr(E)), }, also see that Assumption 4.2 is satisfied since
pexp(p) < 1.266
s 1.26 0.27 1| tr(E)}
1.26 0.27
7a p|l2 + R2 (z)}
0.8
< 7(1 02)a 1| (z))
Since the assumptions of (i) of Theorem 4.8 are satisfied, the desired conclusions hold with probability least 1 26 under condition (i).
Next we show the desired conclusions under condition (ii). To see this, first note that ě S 1/2 implies
that n2...
<
1+ 1-
So, we have C.,, in Theorem 4.8 with C..
168e 3x
So. by setting
Runs (x)
E
3636 i 1,3, C s < is ensured. Moreover, by setting Eq 1.2 81 82 + 53 < 1 ensured.
3
We note that exp(p) holds under condition (ii) since
S 1.35a / tr(E)
< (.3500/m(1000055()((())
1.360 / mtr(E)
1.36 0.1yatr(E)
1.36 0.1
< 0.017 < log( (0).
8
38

---

By noting 0.136)aat((2) and exp(p)
10 condition (ii) implies that Assumption 4.5 is satisfied
since
pexp(p)
_ 10 0.136yatr(E)
$ 10 0.136 0.8 a Riin
$ R (z)
S 6 O2)aRemmnn Rimin
Similarly, by noting exp(p)
<
10 g condition (ii) also implies that Assumption 4.7 is satisfied since
Ra (2) exp(p) < 7.2 9 Rinn
Satr(E) 1.
By (100), condition (ii) implies that Assumption 4.4 satisfied since
202 Rmaz (z) + 02 0. (z)
28 max lo + )l Ci (ong())) O2y log( (2t m
3/ (tr(E
453en
5n2
1/2 0.8ytr(2)
336e
(100/))2
c1 02 R (z)
71 (2p)
Since all the assumptions of (ii) of Theorem 4.8 are satisfied, the desired conclusions hold with with probability at least 26 under condition (ii).
Application of Theorem C.13 on the model (sG) is given below:
Theorem D.6. Consider model (sG). Suppose n 2 max { (4C3 log(t)) and one of the following holds:
(i) 9+g- = 0, 11|uu12 < T+(1+)//2
(r(E) 2 4, - nm log(t) max C/Ell, mlog())) CevTil/ j and
| D (2 uu|| log(H).
(i) g+g- + 0. 0llee122 S 9 2-(-)(1(2) LTC).
tr(E)) > 20 2 log( () max ([|E||,,,||EE) (log(f))
( C2vn well and and
|11123 2 - 3 p211 1og(3),
(ii)) t nllpa|1
2 2
27 tr(E).
2v10 10
tr(2)= 2
1e
ne|le|| (log( (10)(4))1/4
ln /1
max
C.lEll
39

---

Then, we have with probability at least 1 36
72 p (11S 2 2 + tr())}
((n.))(ff W) < 0) S exp
where c is a constant which depends only on and q+-
Proof. By Lemma D.2 and Corollary D.4, event 2 E. holds with probability at least - 36
with
R tr(E),
E C₁ max V /log (1) r. (t) |231| /tr(Z)
E = C2 n nog (+) (lllz((ll)())))
log(#))
E3 Cap
n
Note that the assumption
4C3 l)g( implies Es 3
Then, the desired conclusion follows by simply rewriting assumptions of Theorem C.13.
We now see that Theorem 6.2 follow from Theorem D.5 and D.6 by ensuring both assumptions are satisfied. Specifically, Theorem D.5 under condition (i) and Theorem D.6 under condition (i) and (ii) imply Theorem 6.2 under (a)-(i). Similarly, Theorem D.5 under condition (ii) and Theorem D.6 under condition (i) and (ii) imply Theorem 6.2 under condition (a)-(ii). Lastly, Theorem D.5 under condition (i) and Theorem D.6 under condition (iii) imply Theorem 6.2 under condition (b).
D.2 PROOF OF THROREM 6.3
For model (PM), we have instead of Lemma D.2
Lemma D.7 (Lemma S3.4, S3.5, Hashimoto et al. (2025)). Consider model (PM). There exist constant Crr, K) such that for any 8 (0, 1), event E, n Ea holds with probability least 1 - 28, where
R = tr{))
|
ε C(r, KY8 max pn=p²-b ",n"
tr(E)
82
tr(E)
Similar arguments using D.7 instead of D.2 allows us to establish results analogous to Theorem D.5 and D.6.
Theorem D.S. Consider model (PM). Let ô E (0, 4) Suppose, for sufficiently large constant C which depends on 6, 7/s 7,94,;7 T,
[ pell
tr tr(E) 2 C max
n'p"
2
[ P. [[ n
(101)
and further suppose one of the following conditions:
(i) 2 2 C' max
(n 2 - |E : || vnl Σ E3
a < [1 lr (r()))]] and a < 0.270
+ur(E)
(ii) tr(E) C Caxx nnl 1| 2, n ++ p
Σ F.
|1
< (Str(E))- and o < 0.17ay
m
40

---

Then, we have with probability at least 28, the gradient descent iterate (2) keeps all the neurons activated for 2 1, satisfies ((W())) = Ot ), and converges in the direction given Theorem 4.8.
Proof. The theorem follows from Theorem 4.8, Lemma D.I, and Lemma D.7 by repeating the same argument from the proof of Theorem D.5 by replacing Lemma D.2 with Lemma D.7.
Similarly, we obtain a result analogous to Theorem D.6.
Theorem D.9. Consider model (PM). Let 8 E (0, 3). Suppose n 2 max {4Cg log( N(7,4+) and one of the following holds for sufficiently large constant C. which depends on 6, 7, 2+, r, K:
(i) tr(E) 2 C Caaafnnllll :n 2 [Ele,, + |Elle, n 1/ >|>
and
|| 2 C/
(ii) 9- > 7 n 11l 2 27(1
2- tr (E). and
tr(E) z |l max n 8p- |
[
Then, we have with probability at least 35
n2 ne||u||1 (- tr(E)}
(a;;; W) < 0) S exp
where is a constant which depends only on y and q+-
Proof. The theorem follows from Theorem C.13, Lemma D.1, Lemma D.7, and Lemma D.4 by repeat- ing the same argument from the proof Theorem D.6 by replacing Lemma D.2 with Lemma D.7. C
Putting these together with Σ Ip. we obtain Theorem 6.3. Specifically, Theorem 6.3 under condition (i) follows from Theorem D.8 under (i) and Theorem D.9 under (i), Theorem 6.3 under condition (ii) follows from Theorem D.8 under (i) and Theorem D.9 under (ii), and Theorem 6.3 under condition (iii) follows from Theorem D.8 under (ii) and Theorem D.9 under (i).
41


Reviews:
[{"review_id": "TcyGT1oqAh", "reviewer": "Reviewer_4YXg", "summary": "The authors consider a natural simplified model of a two layer network with leaky ReLU activations.  The first-layer weights are trainable, and the second layer weights are simply fixed and set to $\\pm 1$ up to rescaling.  The authors use an exponential loss function. This is all a fairly standard model for this type of analysis. The goal is to solve a classification problem, where the two classes are centered at $\\pm \\mu$ and iid noise either with subgaussian or polynomial tails is added to each data point.\n\nThe first main contribution of the paper is to work out the convergent direction of the network weights.  Notably, this convergent direction is worked out explicitly under deterministic conditions, and is presented as the solution to a simple optimization problem, which has appeared in prior work under stronger conditions.  This allows the paper to separate the deterministic and probabilistic components of the analysis.  Then in Theorem 5.1 they turn to understanding the classification error under a random data-generation model.  Interestingly, this work gives both an upper and a lower bound on the probability of misclassification, so the authors are able to observe a phase transition between the weak versus strong signal regime, with the latter being associated with higher levels of misclassification.  The authors apply their result to random data models (with subgaussian and polynomial tails) in the overparameterized regime and thereby give new results on the benign overfitting phenomenon.  The main improvements are that the data need not be nearly orthogonal, and that they can handle leaky ReLU activations.", "questions": "What is the difficulty in move from gradient flow results to gradient descent?  Can gradient flow results not be converted to gradient descent results just by taking the step size small enough? Or is the interest in getting specific bounds on the step size?\n\n“We confirm in the next section that these assumptions are satisfied with high probability under model (sG) and (PM), and conjecture that they can also be verified in other settings.”\nWhat settings are conjectured to work?\n\nThe two-sided bounds e.g. in Theorem 6.2 are given for Gaussian z.  Are these bounds expected to hold more generally?\n\n— Minor —\n\nAssumption 6.1 (a) – latex compilation issue\nBeginning of section 3.  $|a_j| = \\pm \\frac{1}{\\sqrt{m}}$ – shouldn’t have the absolute values", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper seems technically sound and gives legitimate improvements over prior work.\n\nThe first improvement is that the analysis holds beyond the nearly orthogonal setting, which is necessary for understanding the types of data that occur in practice, particularly when the means of the two classes are far apart.  They also understand the convergent direction of the weights in a data-dependent way, which may make these results easier to apply as a black box in other settings.  In addition to obtaining an upper bound on the probability of misclassification, they also obtain a lower bound.  This allows for a precise characterization of when overfitting occurs, which appears to be an improvement over prior work.\n\nThe observation of a phase transition between the weak and strong signal regime is also interesting, and gives an explanation as to way previous work required an orthogonality assumption.  This seems to be a substantially novel result compared to prior work.", "weaknesses": "Some of the actual results are perhaps a bit incrememental.  For example the convergent direction is precisely that of Frei et al. as should be expected. On the other hand, relaxing the orthogonality assumption seems like a nice direction, as previous work in the area was unable to do this.\n\nThe actual model is fairly weak compared to modern DL models, and so may be limited in terms of understanding why benign overfitting occurs in practice.  Benign overfitting in two-layer networks is an established research direction though, and think this would be broadly interesting to that community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "3GcEriUqPc", "reviewer": "Reviewer_SjjM", "summary": "This work studies 2 layer (1-hidden layer) leaky relu nets. The authors give result on the limiting behavior of gradient descent and generalization bound.", "questions": "How is w_bar on Line 268 related to the mu from eqn (3)?\n\nLine 257: does a neuron being \"activated\" means the same thing for leaky-relu as it does for the standard relu? the term is a bit confusing since leaky-relu doesn't have a \"dead spot\".\n\nLine 259 says \"the convergent direction [...] can also be given by ...\". Is the convergent direction unique, or is the direction defined in eqn (5) just one possible convergent direction?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Main result on convergence of the parameters also gives the geometry of the decision boundary (which is linear).\n\nGoes beyond the nearly orthogonal setting that many previous work assumes.\n\nIs well-written.", "weaknesses": "The term \"benign overfitting\" is used throughout and in theorem 6.3, but I could not find the mathematical definition of the term. \n\nIs interpolation implied by result on Line 258? \n\nAlso would be helpful to explicitly to write down the Bayes error rate (perhaps it's obvious and I just missed it, but I can't figure it out while reading).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "QMZfXLB6Fv", "reviewer": "Reviewer_RXkj", "summary": "The paper studies two-layer leaky ReLU networks trained by gradient descent in the context of binary classification using an exponentially tailed loss. It establishes two main theoretical results. First, it proves that gradient descent, with a fixed step size, exhibits convergence in direction for the network weights, approaching the max-margin classifier. Second, it characterizes the generalization behavior of such networks under a mixtures data model with mean $\\mu$ and covariance $\\Sigma$. The analysis identifies a phase transition between benign and harmful overfitting,\n$\nn \\|\\mu\\|^4 \\gg \\|\\Sigma\\| \\,Tr(\\Sigma).\n$\nThe results apply to data distributions that may be correlated and heavy-tailed (need finite fourth moments), they don't require the common assumptions of isotropy or sub-Gaussian tails.", "questions": "- On convergence in direction: for what range of step sizes do we get convergence versus oscillation / divergence? At the moment Theorem 4.8 seems to say for sufficiently small step-size we get convergence, I am wondering if you have any insight into when this convergence breaks down?\n\n- Can you sketch the convergence proof idea out perhaps? I am imagining that you try to fix the activation pattern eventually, allowing you to treat the network as a piecewise linear model? How do you control switching between activations regions and the contraction in angle?\n\n- Have you thought about the non linearly separable setting? In this setting I think perhaps a finite solution would exist and as a result the analysis of convergence in direction would no longer be relevant but one could still think about a soft margin bias say.\n\n- I think this work has some similarities (particularly in regard to relaxing the orthogonality conditions on the data) with \"Benign overfitting in leaky relu networks with moderate input dimension\", by Karhadkar et al, a link to which is given below,\nhttps://proceedings.neurips.cc/paper_files/paper/2024/hash/4054556fcaa934b0bf76da52cf4f92cb-Abstract-Conference.html. Would you possibly comment? I think this and maybe some of the references therein might be worth considering adding to your prior work section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The two key technical contributions of this paper seem to me to be as follows.\n- convergence in direction for gradient descent, not just gradient flow. Although this might feel intuitive this is not I would imagine easy to prove,  you need to show some uniform control on the angle between successive gradients which is complicated by the fact that the gradient angle can jump around discontinuously due to the non-smoothness of leaky-ReLU.\n- identifies benign versus harmful overfitting regimes without isotropic / nearly orthogonal data: in many former works this was a requirement for proving benign overfitting as it allows one to treat network activations of different points almost independently, thereby simplifying the dynamics greatly. It is worth noting that another work tackles this issue in a slightly different setting (hinge loss rather than exponential tailed), see questions below.\n- the paper extends benign-overfitting and directional-convergence results to heavy-tailed mixtures.", "weaknesses": "The main weaknesses of the paper I think are as follows\n- Scope / relevance of the setup, namely shallow leaky-relu network, only training the inner layer weights, data which is linearly separable / drawn from a relatively simple distribution. Analysis even in this setting is pretty challenging though so I do not think this is a major issue.\n- A flip side of one of the paper's strengths is that it does not provide finite-sample or high-probability generalization guarantees. The absence of sub-Gaussian or independence assumptions I think precludes standard concentration arguments, so the results provided are weaker in the sense that they hold asymptotically and in expectation. In short, compared to prior results, while the theory applies to broader data distributions, it does not yield as explicit rates or probability bounds. This really is more of a trade-off though than a weakness.\n- I think some relevant work has been missed in the literature review, see questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "vembIHRvs7", "reviewer": "Reviewer_i5vN", "summary": "This work proves directional convergence of two-layer neural networks with leaky ReLU activation trained on the linearly separable data without label flipping via gradient descent. The data distribution are either mixture sub-Gaussian or mixture of polynomially tailed distribution.", "questions": "What's your definition of benign overfitting? Why there exists benign overfitting if all labels are correct/unflipped?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The derivation is very solid and the error bounds look correct. The writing is clear and easy to follow.", "weaknesses": "1. The studied data distribution is restricted to two linearly separable mixture models.\n\n2. Previous work on benign overfitting need $d >> n$ or near-orthogonality because of the existence of the flipped labels. It's intuitive and very expected that near-orthogonality is no longer needed if there is no flipped labels.\n\n3. Theorem 4.8 states the convergent direction is the solution of an optimization problem (5), but does not solve (5).\n\n4. In your Assumption 6.1 (a), in the special case where $\\Sigma = I_d$, it reduces to $d \\geq C \\max (n \\|\\mu\\|^2, n^2)$, which is the same as Assumption (CL2) in [1], why you do not have near-orthogonality under such assumption?\n\n5. typos: The latex does not compile correctly at Assumption 6.1 (a)\n\n[1] Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": {}}]

Author rebuttal:

Decision: Accept (Poster)