Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU Networks on Nearly-orthogonal Data
Authors: Yiwen Kou
Zixiang Chen
Quanquan Gu
Venue: NeurIPS 2023 poster (2023)
Keywords: ReLU Neural Networks
Implicit Bias
Deep Learning Theory

Abstract: The implicit bias towards solutions with favorable properties is believed to be a key reason why neural networks trained by gradient-based optimization can generalize well. While the implicit bias of gradient flow has been widely studied for homogeneous neural networks (including ReLU and leaky ReLU networks), the implicit bias of gradient descent is currently only understood for smooth neural networks. Therefore, implicit bias in non-smooth neural networks trained by gradient descent remains an open question. In this paper, we aim to answer this question by studying the implicit bias of gradient descent for training two-layer fully connected (leaky) ReLU neural networks. We showed that when the training data are nearly-orthogonal, for leaky ReLU activation function, gradient descent will find a network with a stable rank that converges to $1$, whereas for ReLU activation function, gradient descent will find a neural network with a stable rank that is upper bounded by a constant. Additionally, we show that gradient descent will find a neural network such that all the training data points have the same normalized margin asymptotically. Experiments on both synthetic and real data backup our theoretical findings.

Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU Networks on Nearly-orthogonal Data
Yiwen Kou'
Zixiang Chen" Quanquan Gu
Department of Computer Science
University of California, Los Angeles
Los Angeles, CA 90095
Berankou,chenzxee qgu>ecs. ucla. edu
Abstract
The implicit bias towards solutions with favorable properties is believed to be key reason why neural networks trained by gradient-based optimization can generalize well. While the implicit bias of gradient flow has been widely studied for homogeneous neural networks (including ReLU and Icaky ReLU networks), the implicit bias of gradient descent is currently only understood for smooth neural networks. Therefore, implicit bias in non-smooth neural networks trained by gradient descent remains an open question. In this paper, we aim to answer this question by studying the implicit bias of gradient descent for training two-layer fully connected (leaky) ReLU neural networks. We showed that when the training data are ortroyl for leaky ReLU activation function, gradient descent will find a network with stable rank that converges to whereas for ReLU activation function, gradient descent will find neural network with stable rank that is upper bounded by constant. Additionally, we show that gradient descent will find a neural network such that all the training data points have the same normalized margin asymptotically. Experiments on both synthetic and real data backup our theoretical findings.
Introduction
Neural networks have achieved remarkable success in variety of applications, such image and speech recognition, natural language processing, and many others. Recent studies have revealed that the effectiveness neural networks attributed to their implicit bias towards particular solutions which enjoy favorable properties. Understanding how this bias is affected by factors such as network architecture, optimization algorithms and data used for training, has become an active research area in the field of deep learning theory.
The literature on the implicit bias in neural networks has expanded rapidly in recent years (Vardi 2022), with numerous studies shedding light on the implicit bias of gradient flow (GF) with wide range of neural network architecture, including deep linear networks (Ji and Telgarsky 2018 2020
Gunasckar et al. 2018), homogencous networks (Lyu and Li, 2019) Vardi et al. 2022a and more specific cases (Chizat and Bach 2020 Lyu et al. [202]] Frei et al. 2022b] Safrann et al. 2022). The implicit bias of gradient descent (GD), on the other hand, is better understood for linear predictors
(Soudry et al. 2018) and smoothed neural networks (Lyu and Li 2019 Frei et al. 2022b). Therefore, an open question still remains:
What is the implicit bias of leaky ReLU and ReLU networks trained by gradient descent?
this paper, we will answer this question by investigating gradient descent for both two-layer leaky ReLU and ReLU neural networks specific training data, where (x;) In are nearly-orthogonal
"Equal contribution
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

(Frei et al. 2022b), i.e., |xx112 2 Cn max (x,, xx)] with constant C. Our main results are summarized as follows:
For two-layer leaky ReL.U networks trained by GD, we demonstrate that the neuron activation pattern reaches stable state beyond a specific time threshold and provide rigorous proof of the convergence of the stable rank of the weight matrix to I, matching the results of et al. (022bb regarding gradient flow.
For two-layer ReLU networks trained by GD, we proved that the stable rank of weight matrix can be upper bounded by a constant. Moreover, we present an illustrative example using completely orthogonal training data, showing that the stable rank of the weight matrix converges to a value approximately equal to 2. To the best of our knowledge, this is the first implicit bias result for two-layer ReLU networks trained by gradient descent beyond the Karush-Kuhn Kuhn--uukerr (KKT) point.
For both ReLU and leaky ReLU networks, we show that weight norm increases at the rate of ([lg((t) and the training loss converges to zero at the rate of (tt=)), where is the number of gradient descent iterations. This improves upon the O(t rate proved in Frei et al. (2022b) for the case of two-layer smoothed leaky ReLU network trained by gradient descent and aligns with the results by Lyu and Li] (2019) for smooth homogeneous networks. Additionally, we prove that gradient descent will find neural network such that all the training data points have the same normalized margin asymptotically.
2 Related Work
Implicit bias in neural networks. Recent years have witnessed significant progress on implicit bias in neural networks trained by gradient flow (GF). Lyu and Li (2019) and Ji and Telgarsky (2020)
demonstrated that homogeneous neural networks trained with exponentially-talled classification losses
converge in direction to the KKT point of a maximum-margin problem. Lyu et al. (202T) studied the implicit bias in two-layer leaky ReLU networks trained on linearly separable and symmetric data, showing that GF converges to linear classifier maximizing the l2 margin. (Fri et al. (2022b) showed that two-layer leaky ReLU networks trained by GF on nearly-orthogonal data produce a f2-max-marghe solution with a linear decision boundary and rank at most two. Other works studying the implicit bias of classification using GF in nonlinear two-layer networks include Chizat and
Bach (2020); |Phuong and I Lampert (202T): [aauusi et al. (202T); (Safran et al. (2022); Vardi et al. 2022a b): Timor et al. (2023). Although implicit bias in neural networks trained by GF has been extensively studied, research on implicit bias in networks trained by gradient descent (GD) remains limited. Lyu and Li (2019) examined smoothed homogeneous neural network trained by GD with exponentially-tailed losses and proved a convergence to KKT points of a max-margin problem. Frei ct al. 2022b) studied two-layer smoothed leaky ReLU trained by GD and revealed the implicit bias towards low-rank networks. Other works studying implicit bias towards rank minimization include Ji
and galssrk 2018
2020); Timor et al. (2023): Arora et al. (201)); Razin and Cohen (2020):
ct al. 2021). Lastly, Vardi (2022) provided comprehensive literature survey on implicit bias.
Benign overfitting and double descent in neural networks. A parallel line of research aims to
understand the benign overfitting phenomenon (Bartlett et al. 2020) of neural networks by considering a variety of models, For example, Alleen and Li (2020): Jelassi and Li (2022); Shen al. (2022) ;
Cao et al. (2022) Kou et al. (2023) studied the generalization performance of two-layer convolutional networks on patch- based data models. Several other papers studied high- -ing--iimnsionall mixture models
(Chatterji and Long, 2021 Wang and Thrampoulidis 2022; Cao et al. 2021; Frei et al. 2022a). Another thread of work Belkin et al. (2020); Hastie al. (2022); Wu and Xu (2020); Mei and
Montanari (2019): Liao et al. (2020) focuses on understanding the double descent phenomenon first empirically observed by Belkin et al. (2019).
3 Preliminaries
In this section, introduce the notation, fully connected neural networks, the gradient descent-based training algorithm, and data-coorrelated decomposition technique.
Notation. We use lower case letters, lower case bold face letters, and upper case bold face letters to denote scalars, vectors, and matrices respectively. For vector v ",,,), T, we denote by

---

||vl22 [Ej=1 29) its le norm. For a matrix A E Rmxx we use || to denote its Frobenius norm and || ll its spectral norm. We use sign(z) as the function that when 2 0 and otherwise. For vector v R we use [v], E R to denote the i-th component of the vector. For two sequence {ax} and {bx J. we denote a = ((bb) if ay. I C/ for some absolute constant C, denote ag = (b(bx) if by = O(ax). and denote Oę = (bb)) if ag = (bx)) and ag = l(bb)). We also denote ag ((bb.) if lim /a./bal O.
Two-layer fully connected neural newtork. We consider two-layer neural network described as follows: its first layer consists of m positive neurons and negative neurons; its second layer parameters are fixed as +1/m and -1 -1/m respectively for positive and negative neurons. Then the network can be written as f(W, x) (++(W+1: +1, x)
F-1(W -1, -1,x), x), where the partial network function of positive and negative neurons, i.e., F +1, F- -1, are defined as:
(W
Σ (w..).
(3.1)
for j E {=1}. Here, (z) represents the activation function. For RELU, a(z) max =), and for leaky ReLU, (z) = max{72, =}. where E (0, W E Ixxd is the collection of model weights associated with F,. and Wi.r E Rd denotes the weight vector for the r-th neuron in W,, We W denote the collection of all model weights.
Gradient Descent. Given training data set S ((x,, vi)} S Rd x [+1), instead of consid- ering the gradient flow (GF) that is commonly studied in prior work on the implicit bias, we use gradient descent (GD) to optimize the empirical loss on the training data
n n Σ E(w f(W.x))).
Ls(W)
where ((z) = log(1 [1 + exp(-=)) is the logistic loss, and S = {(x, y:) y/) 1 is the training data set. The gradient descent update rule of each neuron in the two-layer neural network can be written as
(1+1) 3 w 17 V (s(())
(C)
(e) o' ((W j.r x:)) juix;
(3.2)
for all j E {+1] and r E [m], where introduce shorthand notation e l'v f(W()) x,)] and assume the derivative of the ReLU activation function at 0 is o'(0) = without loss of generality. Here 77 > is the learning rate. We initialize the gradient descent by Gaussian initialization, where all the entries of W(O) are sampled from i..dd Gaussian distributions (N0 az) with of being the variance.
Main Results
In this section, we present our main theoretical results. For the training data set S = {x,, W))L S Rdd {11,, let Rmin = min; |x; ||: Rima = max; ||x:]l2. p = maxiş4 (xx, X+)|, and suppose R = Rmax/ Rmin is most an absolute constant. For simplicity, we only consider the dependency on I when characterizing the convergence rates of the weight matrix related quantities and the training loss, omitting the dependency on other parameters such as m, n, do. Rmin: Rmaxx-
Theorem 4.1 (Leaky ReLU Networks). For two-layer neural network defined in 3.1 with leaky ReLU activation (z) = (1x,( E (0, 1). Assume the training data satisfy R22 > ARp for some sufficiently large constant C. For any ö E (0, 1), if the learning rate 7 < (CR2 (RRa///Rm)) and the initialization scale do (CRRmax / [og(mm//))
then with probability at least 1 - 5 over the random initialization of gradient descent, the trained network satisfies:
The & norm of each neuron increases to infinity at a logarithmic rate: || | ll2 = (log(tt) for all
j {+1} and r [m].
3

---

Throughout the gradient descent trajectory, the stable rank of the weights w for all E (+1) satisfies
lim W
1
10000
with a convergence rate of (LL log(t)).
Gradient descent will find ( such that all the training data points possess the same normalized
margin asymptotically:
lim +0
y (ff((Wo/
II x,) yke 3xf((W(0) // xx) = 0, Vi, & E [n].
If we assume that (+)) converges in direction, i.e., the limit of W / by W, then there exists scaling factor > 0 such that a W satisfies the Karush- Kuhn-Tucker (KKT) conditions for the following max-man max-margin problem:
|| exists, denoted
min W
W
S.t.
W:((W xx) 2 Vi E [n].
(4.1)
The empirical loss converges to zero at the following rate: Ls ( = O(t
Remark 4.2. In Theorem 4.1 show that when using the leaky ReLU activation function nearly orthogonal training data, gradient descent asymptotically finds a network with a stable rank of W equal 1. Additionally, we demonstrate that gradient descent will find network by which all the training data points share the same normalized margin asymptotically. Moreover, if we assume the weight matrix converges in direction, then its limit will satisfy the KKT conditions of the max- mar-mn problem 44.I). Furthermore, we analyze the rate weight norm increase and the convergence rate of the stable rank for gradient descent, both of which exhibit logarithmic dependency in L.
Theorem 4.3 (ReLU Networks). For two-layer neural network defined in (3.1) with ReLU activation (2) = max (0, 2). Assume the training data satisfy R 2 C mp for some sufficiently large constant C. For any 8 E (0. 1), if the neural network width m 2 C'log(n/8), learning rate and initialization scale op S (C / /logommm mn (8)) then with probability at least 1 - over the random initialization of gradient descent, the trained network satisfies:
n &
The Frobenious norm and the spectral norm of weight matrix increase to infinity at a logarithmic
rate: || (t) IF O(log(t)) and l|w(() (t) ll2 (log(tt) for all {+1}.
Throughout the gradient descent trajectory, the stable rank of the weights w for all E (+1) satisfies,
lim [ / W 12 Sc
8-+00
where is an absolute constant.
Gradient descent will find (4)) such that all the training data points possess the same normalized margin asymptotically:
lim 2
yif (1)(
// p. x;) -y--y vw /// xx)
0, Vi E [n].
The empirical loss converges to zero at the following rate: Ls Ls((())) = tt
Remark 4.4. For ReLU networks, we provide an example in the appendix concerning fully orthogo- training data and prove that the activation pattern during training depends solely on the initial activation state. Specifically, when training two-layer ReLU network with gradient descent using such data, the stable rank of the network's 's weight matrix W, converges to approximately 2. It worth noting that this stable rank value is higher than the stable rank achieved by leaky ReLU networks, which
Comparison with previous work. One notable related work is Lyu et al. (001)) which also investigates the implicit bias two-layer leaky ReLU networks. The main distinction between our work and Lyu al. (2021) is the optimization method employed. We utilize gradient descent, whereas they utilize gradient flow. Additionally, assumption is that the training data is orthoylollhogonal,

---

while they assume the training data is symmetric. Our findings are more closely related to the work by(Fre Frei et al. (2022b), which investigates both gradient flow and gradient decent. In both our study and Frei et al. (2022b), we examine two-layer neural networks with leaky ReLU activations. However, they focus on networks trained via gradient flow, while we investigate networks trained using gradient descent. For the gradient descent approach. Frei et al.] (2022b) provide a constant stable rank upper bound for smoothed leaky ReLU. contrast, we prove that the stable rank of leaky ReLU networks converges to 1, aligning with the implicit bias of gradient flow proved in Frei et al. (0022)). Furthermore, they presented an Ott-1/2 convergence rate for the empirical loss, whereas our convergence rate is ( Another related work is Lyu and Li (2019). which studied smooth homogeneous networks trained by gradient descent. Our results the rate of weight norm increase and the convergence rate of training loss match those in Lyu and Li (2019). despite the fact that we study non non-smooth homogeneous networks. It is worth noting that Lyu and Li (2019): Lyu et al. (202I); Frei et al. (2022b) demonstrated that neural networks trained by gradient flow converge to Karush-Kuhn- Tucker (KKT) point of the max-margin problem. We do not have such a result unless we assume the directional convergence of the weight matrix.
Overview of Proof Techniques
In this section, we discuss the key techniques invent in our proofs analyze the implicit bias of ReLU and leaky ReLU networks.
5.1 Refined Analysis of Decomposition Coefficient
Signal-noise decomposition, technique initially introduced by Cao et al. (2022). is used analyze the learning dynamics of two-layer convolutional networks. This method decomposes the convolutional filters into a linear combination of initial filters, signal vectors, and noise vectors, converting the neural network learning into dynamical system of coefficients derived from the decomposition. In this work, we extend the signal-noise decomposition to data-correlated decomposition to facilitate the analysis of the training dynamic for two-layer fully connected neural networks.
Definition 5.1 (Data-correlated Decomposition). Let w for j E (+1), r E [m] be the weights of
first-layer neurons at the /-th iteration of gradient descent. There exist unique coefficients (10) such that
12
w (()
j.r 5.r
w!!)
(0)
Pirx
(C) 1x=l1=2xx0 x,
(5.1)
By defining // == Pjant (p 2 0), (1)
(t)
= Paan 1 1 S <0), 5..1 can be further written as Eirr
(t)
(t)
n
w! (1) j.r w (0)
Pira |x|1|2 2
(
(()) Jan
||x 10ll2 x,-
(5.2)
j.r
As an extension of the signal-noise decomposition first proposed in Cao et al. (0022) for analyzing two-layer convolutional networks, data-correlated decomposition defined in Definition 5.1 can be
used to analyze two-layer fully-connected network, where the normalization factors x, 2
-2
are
introduced to ensure that Pjic R (.....)) This is also inspired by previous works by Lyu and Li (2019); Frei al. (2022b), which demonstrate that W converges
KKT point of the max-margin problem. This implies that w j.r j.r" ||2 can be expressed as a linear combination of the training
(ce) (3])) /[l
data (=, with the coefficient X; corresponding to jj.raa in our analysis. This technique does not rely on the strictly increasing and smoothness properties of the activation function and will serve as (()) the foundation for our analysis. Let us first investigate the update rule of the coefficient Pj.. jirs"
Lemma 5.2. The coefficients Plr S defined in Definition 5.1 satisfy the following iterative equations:
(0) p/ 2in, = 0,
(5.3)
5

---

Pirs -jjrs
(++1)
p(t). o' d'(( (.r.,.))))) x()) ||x:| (y: j),
(5.4)
nm
0 (+t))
(())
T e(0) d' ([ x()) | 1 =-),
(5.5)
5nd j.r,
nmm
for all r E [m], j E {=1} and E [n].
To study implicit bias, the first main challenge is to generalize the decomposition coefficient analysis to infinite time. The signal- noise decomposition used in Cao et al. : Kou et al. (2023) requires early stopping with threshold 7 to facilitate their analysis. They only provided upper bounds of
4 [l"g(T") for (1)) Pa.nai -j...
(See Proposition 5.3 in Cao al.
(2022) Proposition 5.2 in Kou et al.
(2023) ) and then carried out a two-stage analysis. To obtain upper bounds for Pj.r,a L they
used upper bound for (0(00 and directly plugged it into (.4) and (5.5 demonstrate that p
and lo would not exceed 4 log(T"). which is a fixed value related to the early stopping threshold.
Therefore, dealing with infinite time requires new techniques. To overcome this difficulty, we propose a refined analysis of decomposition coefficients which generalizes Cao et al. (022)'s 's technique. We
first give the following key lemma.
Lemma 5.3. For non-negative real number sequence { satisfying
C1 exp(-xx) S Øt+1 2t S C2 -x)),
(5.6)
it holds that
log(cxp(-zo) + +1 -t) S 24 I log (c(ppp(-xx) + C2 cxp((C)
(5.7)
We can establish the relationship between (5.4. (.5) and inequality (5.6) if we are able to express
(1) and 1p!0 To achieve this, we can first approximate e(t) using (0)) using coefficients Pj.rs
the margin vi((W(), xz) and then approximate (, x:) using the coefficients p The approximation is given as follows:
: (1) = (expl( yi (W((((()) x;))) = O ((epp (F-
-mi x:) - Feee (W()) x:))):
(5.8)
F x.)
(1) Pins Rminp
(5.9)
From (5.9. one can see that we need to decouple p!0) from (0) 1 + i). In order to accomplish
this, we also prove the following lemma, which demonstrates that the ratio between Σm l
and Em= 1p ((' * i) will maintain a constant order throughout the training process. Here, we present the lemma for leaky ReLU networks.
Lemma 5.4 (leaky ReLU automatic balance). For two-layer leaky ReLU network defined in (3.I) for any t 2 0, we have Σm j.ral ey² m
Emmle Ppr.. for any j E (+1) and i, E [n]. where
a constant.
By Lemma 5.4 we can approximate the neural network output using 5.9p. This approximation (t)
expresses the output F, (W)))) x;) as a sum of the coefficients Pj.ra
FJ
+ ey² R min
pm
Σ Pars
(5.10)
By combining (5.4)
5..5
5.8 and 5.10)). we obtain the following relationship:
= e 1 m1lxx111)) - nm
-1
Cr RR- mm
(1+1)
(c)
Joral
cxp
m
m
r=1
This relationship aligns with the form of (56).. if we set 2, can directly apply Lemma 5.3 to gain insights into the logarithmic rate of increase for the average
1 R min r=1 1p....l Thus, we

---

magnitudes of the coefficients 1 Σr= 10 which in turn implies that 1| Olog () and
[[((]]] = (logg t). the case of ReLU networks, we have the following lemma that provides
automatic balance:
Lemma 5.5 (ReLU automatic balance). For two-layer ReLU network defined in (3.1. there exists constant such that for any & 2 0, we have lp 2 clpg. for any j E {+1}, r E 5. := {r E
[m]]: (w x3) 2 0}, r' E [m]] and i, E [n]].
The automatic balance lemma guarantees that the magnitudes of coefficients related the neurons of class yt, which are activated by x, during initialization, dominate those of other classes. With the help of Lemma 5.5 we can get the following approximation for the margin y (W(((())) (W))));))
1 cR 2 min pn
Fy. (W(()) W xx) F-y. v. (W yc x:)
Σ
(1)
(5.11)
m71
TES!
By combining (5.4), 5.5
5.8 and (5.11, we obtain the following relationship:
1
c on min
exp
Painn
rES
rES())
rES
which precisely matches the form of (5.6) by setting 24
Lief
2 pr
Σ Eres(0) Paenne Therefore,
can directly apply Lemma 5.3 and obtain the logarithmic increasing rate of I P for r E s!") Consequently, this implies that [w0 (logt)).
5.2 Analysis of Activation Pattern
One notable previous work (Frei et al. 2022b) provided a constant upper bound for the stable rank of two-layer smoothed leaky ReLU networks trained by gradient descent their Theorem 4.2. To achieve a better stable rank bound, we characterize the activation pattern of leaky ReLU network neurons after a certain threshold time T in the following lemma.
Lemma 5.6 (leaky ReL.U activation pattern). Let T = -Cn nm nmmpm22 R For two-layer leaky ReLU 3. for any 2 T, it holds that sign( (ogu((ww) (((()) J,r x:)) = jy: for any j {+1} and
network defined
r E [m].
Lemma 5.6 indicates that the activation pattern will not change after time T. Given Lemma 5.6 can get o' ((w j,rt x;)) y for j * ys and o' d'(w (t) jar x,)) for j = yt- Plugging this into 5..
and (55 can give the following useful lemma.
Lemma 5.7. Let ''' be defined in Lemma 5.6 For t > T, it holds that
(T) P r.. PoLir ; = Por.r Pyr ,0 ((0) vi...6
(t)
- p. = (0)) L - ((T)
P Paini P (p (p- virt - 3/7
(t)
for any i [n]] and r' [m]]
This lemma reveals that beyond a certain time threshold T, the increase in Pj.r.s is consistent across neurons within the same positive or negative class. However, for neurons belonging to the oppose
class, this increment in Pj.r. is scaled by a factor equivalent to the slope of the leaky ReL.U function
(1)
jir 12(rr # r') can be upper bounded by From this and (.I). D. we can demonstrate that ||w j.r
constant, leading to the following inequalities:
| 1 S mlmmm//////// w 10 113 mC, [| mC2, |W 1B 2 m|[w f013 // mC4-
Considering that || - = (log ,) the stable rank of w( naturally converges to a value of 1. For ReLU networks, we can partially characterize the activation pattern illustrated the following lemma.
7

---

Lemma 5.8. (ReLU activation pattern) For two-layer ReLU networks defined in (3.1 for any i E [n]]
we have s
S s(++1) for any 2 0, where s!d) = fr [m] (Warr, x;) 2 0}.
Lemma 5.8 suggests that once the neuron of class ys is activated by x,, it will remain activated throughout the training process. Leveraging such an activation pattern, we can establish a lower bound for | [| as (llog(t)). Together with the trivial upper bound for | ||e of order Ollog(t),, it provides constant upper bound for the stable rank of ReLU network weight.
5.3 Analysis of Margin and Training Loss
Notably, Lyu and Li (2119) established in their Theorem 4.4 that any limit point of smooth homoge- neous neural networks /(W, x) trained by gradient descent is along the direction of KKT point for the max-margin problem (4.1 Additionally, Lyu and Li (2019) provided precise bounds on the training loss and weight norm for smooth homogeneous neural networks in their Theorem 4.3 as follows:
ls((W())) = @ (((1og)))-217) 2/T)
|W O(log 1)2/2),
where L is the order of the homogeneous network satisfying the property =e x) for all e 0, W. and x. is worth noting that the two-layer (leaky) ReLU neural network analyzed in this paper l 1-homogencous but not smooth. In Section 5.1] we have already demonstrated that | |[W(' convergence rate of ((--1) for the loss and establish the same normalized margin for all the training data points asymptotically. These results align with those presented by Lyu and Li (2019) regarding smooth homogeneous networks.
e (log t), and in this subsection, we will discuss the proof technique employed to show a
By the nearly orthogonal property, we can bound the increment of margin as follows:
7
(
||x S y. v.f(W(++)) x.) - y.f xx)
3n
||x ll
(5.12)
5mm
Given (.8)
and 5.12).
we can apply Lemma 5.3 and obtain
y. f.f(((()) .x)) - log
nm)) < C3,
(5.13)
where C3 is constant. Utilizing 5.13 and the inequality 2? 2 log(1 2) for 2 0, can derive:
Lg (s(W(9) <
exp (.(( x,))
im1
<
exp [-logt log(n///>/////// 12/mm) +C3) = O(t-l)
1=1
Ls (s(W())
exp (.'() xx)) exp (- 2y. (W((1) x,)) = 2(t
n
To demonstrate that all the training data points attain the same normalized margin as f goes to infinity, we first observe that (2.12) provides the following bounds for the increment of margin difference:
yk. yk.( (W(1)) xx) - y: y: (W((+1) x:)
yk ((W()) xx) - (1() xx.) (xxx)) 3n
. -
. 11,00-- ||2c/12.
" 5mm
(5.14)
nm
Now, we consider cases:
the ratio 1/12())))))))))) is relatively large, then yu (WW()) xx) v. (W((() x:) will not increase.
If the ratio (, 1/1((()) is relatively small, then yb vx/(WW) xx) ya (w xx) will also be
relatively small. In fact, it can be bounded by constant due to the fact that (11))) be approximated by ofplyf(W(l xx) vf((() By 5.14). we can show that
8

---

0211
Lody
Leaky Siae
Leats Pur.
8.02
8.435
30-
30 20
30
20
59
Figure 1: Stable ranks and training loss for different leaky ReLU slopes y across multiple runs. A slope of corresponds linear activation, while slope of 0 corresponds to ReLU activation. Each line represents the mean stable rank or training loss for given leaky ReLU slope, while the shaded regions indicate the variability of the values (#:3 times the standard deviation) across the 5 runs.
yk Maf(((++)) xx) y f (W((+))) x;) can also be bounded by a constant, provided that the learning rate 1) sufficiently small.
(1) and yis (f (x)())))))>>>>>)))) yv (WV)) x.) can be bounded by constants. This result is formally stated in the following lemma.
By combining both cases, we can conclude that both 1/14%
Lemma 5.9. For two-layer neural networks defined in 3.1 with (leaky) ReLU activation, the following bounds hold for any t 0:
(w)( x2) (w x+) S Ci.
/6 S C2,,
(5.15)
for any k [r]], where C1, C2 positive constants.
By Lemma 5.9. which shows that the difference between the margins of any two data points can be bounded by constant, and taking into account that || O(log t), we can deduce the following result:
lim y (W (1) //| [I,x.) - fw (W00) (()) F, xx) = 0, Vi, k E [n]] -0
This demonstrates that gradient descent will asymptotically find a neural network in which all the training data points achieve the same normalized margin.
6 Experiments
In this section, we present simulations of both synthetic and real data to back our theoretical analysis in the previous section.
Synthetic-data experiments. Here generate synthetic mixture of Gaussian data follows:
Let μ E d be a fixed vector vector representing the signal contained in each data point. Each data point (x, y) with predictor x E Rdd and label E { is generated from distribution D, which we specify as follows:
1. The label y is generated Rademacher random variable, i.c. Ply 1] Ply = - 1/2.
2. A noise vector & is generated from the Gaussian distribution (O00, da And x is assigned as + where f4 is fixed feature vector.
Specifically, we training data size n 10, d 784 and train the NN with gradient descent using learning rate 0.1 for 50 epochs. We set fe to be feature randomly drawn from (O, 10 10-41a) We then generate the noise vector & from the Gaussian distribution A (00 oz1) with fixed standard deviation o, 1. We train the FNN model defined in Section 3 with ReLU (or leaky-Rell activation function and width
100. As larger leaky ReLU slopes and have a smaller value when epoch + co.
infer from Figure the stable rank will decrease faster for
Real-data experiments on MNIST dataset. Here we train a two-layer foed-forward neural network defined in Section 3 with ReLU (or leaky-ReLU) functions. The number of widths is

---

Differont Vor
Test for Varfances
Cortamn Miliggt Vontanii 2091 Weigin vesaanca
422
26
Magght Varance Se46 Meight Varence 0.00
Figure 2: Stable ranks and test errors for different weight variances across multiple runs (ReLU Activation Function). Each line represents the mean stable rank or test accuracy for given weight variance, while the shaded regions indicate the variability of the values (#3 times the standard deviation) across the 5 runs.
Rarvis Different Var
Test git Varlances
249
Welght inrranca
Winggt Vovtamn rest
08
309
Maght Varance Se-d
Varance 0.005
Varance 0.00
Cosch
Figure 3: Stable ranks and test errors for different weight variances across multiple runs (leaky-ReLU Activation Function with slope 0.1). Each line represents the mean stable rank or test accuracy for given weight variance, while the shaded regions indicate the variability of the values (#:3 times the standard deviation) across the runs
set as m 1000. We use the Gaussian initialization and consider different weight variance Oo {0.00001, 0.00005, 0.0001, 0.0005, 0.001}. We train the NN with stochastic gradient de- scent with batch size 64 and learning rate 0.1 for 10 epochs. As we can infer from Figures 2 and the stable rank of ReLU or Ieaky ReLU networks will largely depend on the initialization and the training time. When initialization sufficiently small, the stable rank will quickly decrease small value compared to its initialization values.
Conclusion and Future Work
This paper employs data-correlated decomposition technique to examine the implicit bias of two- layer ReLU and Leaky ReLU networks trained using gradient descent. By analyzing the training dynamics, we provide precise characterizations of the weight matrix stable rank limits for both ReLU and Leaky ReLU cases, demonstrating that both scenarios will yield a network with low stable rank. Additionally, present an analysis for the convergence rate of the loss function. An important future work is to investigate the directional convergence of the weight matrix in neural networks trained via gradient descent, which is essential to prove the convergence to a KKT point of the max max-margin problem. Furthermore, it is important to extend our analysis fully understand the neuron activation patterns in ReLU networks. Specifically, we will explore whether certain neurons will switch their activation patterns by an infinite number of times throughout the training or if the activation patterns stabilize after certain number of gradient descent iterations.
A Acknowledgements
We thank the anonymous reviewers and area chair for their helpful comments. YK, ZC. and QG are supported in part by the National Science Foundation CAREER Award 1906 169 and IIS-2008981, and the Sloan Research Fellowship. The views and conclusions contained in this paper those of the authors and should not be interpreted as representing any funding agencies.
10

---

References
ALLEN-ZHU, Z. and LI, Y. (2020). Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXi::2012.09816.
ARORA, S., COIIEN, N., HU, W. and LUO, Y. (2019). Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems 32.
BARTLETT, L., LONG, M., LUGOSI, G. and TSIGLER, A. (2020). Benign overfitting in linear regression. Proceedings of the National Academy of Sciences.
BELKIN, M., HSU, D., MA, S. and MANDAL, S. (2019). Reconciling modern machine leaaningg practice and the classical bias- trade-off. Proceedings of the National Academy of Sciences 116 15849-15854.
BELKIN, M., Hsu, D. and Xu, J. (2020). Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science 1167-1180.
CAO, Y., CHEN, Z., BELKIN, M. and Gu, Q. (2022). Benign overfitting in two-layer convolutional neural networks. arXiv preprint arXiv:2202.06522.
CAO, Y., GU, Q. and BELKIN, M. (2021). Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures. Advances in Neural Information Processing Systems 34.
CHATTERII, N. S. and LONG, M. (2021). Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research 22 129-1.
CHIZAT, L. and BACH, F. (2020). Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory. PMLR.
FREI. S., CHATTERJI, N. S. and BARTLETT, P. (2022a). Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory. PMLR.
FREI, S., VARDI, G., BARTLETT, P. L., SREBRO, N. and Hu, W. (2022b). Implicit bias in leaky relu networks trained on high-dimensional data. arXiv preprint arXiv:2210.07082.
GUNASEKAR, S., LEE, J. D., SOUDRY, D. and SREBRO, N. (2018), Implicit bias of gradient descent linear convolutional networks. In Advances in Neural Information Processing Systems.
HASTIE, T., MONTANARI, A., ROSSET, S. and TIBSHIRANI, R. J. (2022). Surprises in high-
dimensional ridgeless least squares interpolation. The Annals of Statistics 50 949-986.
JELASSI, S. and LI, Y. (2022). Towards understanding how momentum improves generalization in deep learning. In International Conference on Machine Learning. PMLR.
J1, Z. and TELGARSKY, M. (2018). Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv:1810.02032.
JI, Z. and TELGGARKY, M. (2020). Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems 33 17176-17186.
KOU, Y., CHEN, Z., CHEN, Y. and Gu, Q. (2023). Benign overfitting for two-layer relu networks. arXiv preprint arXiv:2003.04155
LI, Z., Znov, Z. and GRETTON, A. (2021). Towards an understanding of benign overfitting in neural networks. arXiv preprint arXiv:2106.03212.
LIAO, Z., COUILLET, R. and MAHONEY, M. (2020). A random matrix analysis of random fourier features: beyond the gaussian kernel, precise phase transition, and the corresponding double descent. In 34th Conference Neural Information Processing Systems (NeurIPS 2020).

---

LYU, K. and LI, J. (2019). Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 1906.0589.
LYU, K., LI, Z., WANG, R. and ARORA, S. (2021). Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems 34 12978- 12991.
MEI, S. and MONTANARI, A. (2019). The generalization error random features regression: Precise asymptotics and double descent curve. arXiv preprint
PHUONG, and LAMPERT, C. (2021). The inductive bias of relu networks on orthogonally separable data, In International Conference Learning Representations.
RAZIN, N. and COHEN, (2020). Implicit regularization deep learning may not be explainable by norms, Advances in neural information processing systems 33 21174-21187.
SAFRAN, I, VARDI, G. and LEE, D. (2022). On the effective number of linear regions in shallow univariate relu networks: Convergence guarantees and implicit bias. arXiv preprini arXiv:2205.0907..
SARUSSI, R., BRUTZKUS, A. and GLOBERSON, A. (2021). Towards understanding learning in neural networks with linear teachers. In International Conference on Machine Learning. PMLR.
SHEN, R., BUBECK, S. and GUNASEKAR, S. (2022). Data augmentation feature manipulation: story of desert cows and grass cows. arXiv preprint arXiv:2203.01572.
SOUDRY, D., HOFFER, E.,, NACSON, M. S., GUNASEKAR, S. and SREBRO, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research 19 2822-2878.
TIMOR, N., VARDI, G. and SHAMIR, O. (2023), Implicit regularization towards rank minimization in relu networks. In International Conference on Algorithmic Learning Theory. PMLR.
VARDI, G. (2022). On the implicit bias in deep-learning algorithms. arXiv preprint arXiv:2208. /259/
VARDI, G., SHAMIR, O. and SREBRO, N. (2022a). On margin maximization in linear and relu networks. Advances in Neural Information Processing Systems 35 37024-37036
VARDI, G., YEHUDAI, G. and SHAMIR, O. (20226). Gradient methods provably converge to non-robust networks. arXiv preprint arXiv:2202.04347.
VERSHYNIN, R. (2018). Digg--Dimesiooal Probability: An Introduction with Applications in Data Science. Cambridge Series Statistical and Probabilistic Mathematics, Cambridge University Press.
WANG, and THRAMPOULIDIS. C. (2022). Binary classification gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization. SIAM Journal on Mathematics of Data Science 4 260-284.
WU, D. and XU, J. (2020). On the optimal weighted l regularization in overparameterizee linear regression. Advances in Newral Information Processing Systems 33.
12

---

A Additional Experiments
In this section, we conduct additional experiments on the nearly orthogonal and MINIST datasets.
A.1 Additional Experiment on Nearly Orthogonal Dataset
In this subsection, we conduct additional experiments on nearly orthogonal dataset for long epochs
to support our main Theorems 4.1 and 4.3
Sobie Kanks for Liferrr Lebey Skgun
Soale Raria- Prr Laaky Rella Stopes (Sers logy
Figure 4: (Left) Stable ranks for different leaky ReLU slopes y across multiple runs. A slope of 1 corresponds to linear activation, while slope of 0 corresponds to ReLU activation. Each line represents the mean stable rank for a given leaky ReLU slope, while the shaded regions indicate the variability of the values (#3 times the standard deviation) across the 20 runs. The red dashed line indicates stable rank of (Right) The difference between stable rank and from the left figure is visualized on a semilog y-axis.
Stbbie Parks For Dfffereet Leaky Rel. Stopes
Statre Rorks for Diforent Leaty Netu Skipes there key. bect
Bust
becl's apain 2.5
Excch
Figure 5: fully orthogonal data: (Left) Stable ranks for different leaky ReLU slopes Y across multiple runs. A slope of 1 corresponds to linear activation, while a slope of 0 corresponds to ReLU activation. Each line represents the mean stable rank for given leaky ReLU slope, while the shaded regions indicate the variability of the values (#3 times the standard deviation) across the 20 runs. The red dashed line indicates stable rank of 1. (Right) The difference between stable rank and 1 from the left figure is visualized on a semilog y-axis.
Figure 4 Under the same setting of the synthetic data introduced in Section 6, we train the NN with full batch gradient descent with a learning rate 0.1 for 1000 epochs. We set μ to be a feature randomly drawn from (O, 10 10-"Ig). We then generate the noise vector & from the Gaussian distribution (O da. with fixed standard deviation op = 1. We train the FNN model defined in Section 3 with ReLU (or leaky-ReLU) activation function and width m = 100. As we can see from when
Figure 4 the stable rank for the leaky ReLU network with large slopes 7 will converge epoch + co. In comparison, the stable rank for the ReLU network will not converge to 1.
Figure To further illustrate the behavior of the ReLU network, we generate the synthetic training data with fully orthogonal imput. Each data point (x, y) with input x E Rd and label E { {-1, 1} is generated from distribution D, which we specify as follows:
1. The label y is generated as a Rademacher random variable, i.e., Ply = 1]= = Ply = - 1| = 1/2.
2. Input x is randomly generated from the basis {ei, e2...... ..)).
Specifically, we set training data size n = 20, = 40 and train the NN with full batch gradient descent with a learning rate 0.1 for 1000 epochs. We train the FNN model defined in Section 3 with ReLU (or (eaky-ReLU) activation function and width m 10000. As we can observe from Figure 5
13

---

the stable rank for the leaky ReLU network with large slopes will converge to when epoch + co. In comparison, the stable rank for the large-width ReLU network will not converge to 1 but to 2.
A.2 Additional Experiment on MINIST
Our focus is the training of two-layer feed-forward neural network, as discussed in Section 3 utilizing either ReL.U or leaky-ReI.U activation functions. We examine different widths, specifically choosing from (10, 50, 100, 500, 1000].
The network initialization process follows a Gaussian distribution, with variance of og 0.00001. Training is executed using stochastic gradient descent, batch size of 64, and learning rate of 0.1, for a total of 10 epochs. As discerned from Figures 6 and 7 the stable rank of networks utilizing either ReLU or leaky ReLU is weakly influenced by the width. For an exceedingly small width such as 10, the weight matrix is low rank with a correspondingly small stable rank. However, this also results in low test accuracy the network cannot effectively learn all necessary features. As the width increases, the test accuracy and final stable rank will increase. However, for sufficiently large widths, an increase in width no longer corresponds to stable rank or test accuracy increases. Stable Rovis Difer Weight sances
Texi Accuracy for billeron Weglt Varfances
Finden dec
Pridten
152
0
Edair
1ibe-- 51
Eader a. +553
bpac
Figure Stable ranks and test errors for different width across multiple runs (ReLU Activation Function), Each line represents the mean stable rank or test error for given weight variance, while the shaded regions indicate the variability of the values (+3 times the standard deviation) across the runs.
Stacle Rarves Different Variaccee
Tea: Different We Verienee.
Ficden sie 110
hicdenile 1.00
Ficean
02-
riber c.0 -13 Hidr
Fider 3300
Caoch
Figure 7: Stable ranks and test errors for different width across multiple runs (leaky-ReLU Activation Function). Each line represents the mean stable rank error for given weight variance, while the shaded regions indicate the variability of the values (+3 times the standard deviation) across the 5 runs.
B Preliminary Lemmas
In this section, we present some pivotal lemmas that illustrate some important properties of the data and neural network parameters at their random initialization and provide the update rule of coefficients from data-correlated decomposition.
Now turning to network initialization. the following lemma studies the inner product between (0) randomly initialized neural network neuron w W (j E {+1} and (m]) and the training data. The calculations characterize how the neural network at initialization randomly captures the information in training data.
14

---

Lemma B.1. Suppose that d = (llog(mm/8)), = (l(oo)(/))). Then with probability at least 1 1-6, 6,
ofd/2 S 1w s. // (0)
(w j.r xx) - 2og (log(8mn/0)) ByRuuax
for all r [m] E {=1} and E [n].
Proof of Lemma B.1 First of all, the initial weights wi -N(0, aoT) By Bernstein's inequality, with probability at least 64mm) we have
|| 0 odd O vdlog(8m/o))
Therefore, if we set appropriately d = (mlog(m (0))) we have with probability at least - 6/2, for all j E [+13 and r E [m].
d/2
S 30/d/2.
Under definition, we have ||x:|22 & Rmax for all E [n]. It clear that for each j. {w j.r 14) is Gaussian random variable with mean zero and variance of x: Therefore, by Gaussian tail bound and union bound, with probability at least 6/2,
(0) [w j.r:x)) S /2 /2log (log(8mn/6)) RaRaax.
Next, we denote 5:0) as {r E [m] (w x.) 0}. We give a lower bound of | in the following two lemmas.
Lemma B.2. Suppose that 8 > 0 and m 2 50 50llg(2n/ (2n/o). Then with probability at least - 6,
0.4m S 5 < 0.6m, Vi E [n].
Sur x²) > 0] and P((w p..,, xx) > 0) = 1/2, then by Hoeffding's inequality, with probability at least 8/n, we have
Proof of Lemma B.2 Note that | Σm= [[( ((
|
(2n/2))8)
m
2m
Therefore, as long as m 2 50 50log(2n/d)) by applying union bound, with probability at least we have
0.4m < (s(00)
0.6m, Vi [n]]
Now give the update rule of coefficients from data-correlated decomposition. We will begin by analyzing the coefficients in the fata-correlated decomposition in Definition 5.1 The following lemma presents an iterative expression for the coefficients.
Lemma B.3, (Restatement of Lemma 5.2 The coefficients Pyr. p(0) defined in Definition 5.1
satisfy the following iterative equations:
p 2
(0) 0.
((+1) = =Pj.r.
17
(()
d'((w'( (1)
(1,x))))) ||x; 1 = j),
j.r
nm
(1+1) = (1) T
(1) of o'lo'w())) jare xx)) ||x ( -j),
2 nm
for all r [m], E {+1} and i [n].
15

---

Proof of Lemma B.3 First, we iterate the gradient descent update rule 3.2 t times and get
(1+1)
(0)
(1)) o o'((W), ((W)))))))) xi)) juxx.
==0
i=1
According to the definition of Pir,i have
(0)
(0) Jin'
|xx||22 X,.
Jor
i=1
Therefore, we have the unique representation
Pinn = "
d'((W jirt xi)) 1|x:112 -86-
nm ==0
Now with the notation (0)
Pj.r. = Pirri 1 j,rq 2 0), (00) = P 1 1 S 0) and the fact
((())) < we get
Pj
7)
((w Jor x,)) ||x:112 1 = j).
(B.1)
==0
(1)
(()) o' d'((w)
for x,)) ||x;1 ( = -))
(B.2)
nu
8=0
Writing out the iterative versions of B.I and
B.2 completes the proof.
C Coefficient Analysis of Leaky ReLU
In this section, we establish series of results on the data-correlated decomposition for two-layer leaky ReLU network defined as
f(W() (1) x) = F+1 (W +1, - FW -)
m
1 m
o a((w! (t)
+l.: x))
Σ
o(w ((w") (lr:
(C.1)
m r=1
(x) = max (72, > E (0,
The results in Section C D and G are based on Lemma B. which hold with high probability. Denote
by Eprelim the event that Lemma B.1 in Section holds (for a given
P(εpretim) > 1 8).
For simplicity and clarity, we state all the results in Section C D
on Eprelim.
Denote B max j.r x;)),. Ruax max ||x||22 Rmin = min,e(m] ||x:||2, p
(0)
maxiya [xx;, xx)l and suppose R = Rmax/Rmin is at most an absolute constant. Here we list the exact conditions for 77, To, Rmin, Ruax, P required by the proofs in this section.
a S (C(RRmax V Tog(mn/6)) -1
(C.2)
(C 1) S (CR2 R //m)
(C.3)
R2. 2 Cr -A R2mp.
(C.4)
where C a large enough constant. By Lemma B.1 we can upper bound 3 by 2og 12mm/0) Tn Rmaxx Then, by (C.2) and (C.4) is straightforward to verify the following inequality:
B s m,
(C.5)
? R np S C,
(C.6)
?
4 2 R2np <
min
(C.7)
16

---

where e is a sufficiently small constant.
Suppose the conditions listed in CC22 and
C.4 hold, claim that for any 2 0 the following
property holds.
Lemma C.1. Under the same conditions Theorem 4.1 for any 2 0, we have that
Σ g 2
Σ p=l
VJ.J [=1]. Vi, e [m].
(C.8)
where Cj is constant.
To prove Lemma C.I
we divide it into two lemmas, each addressing a specific case: 0 s Ti
(Lemma C.2) when the logit |0!00 @(1) and > Ti (Lemma C.3) when the logit (,(") is smaller than constant order. Here, Ti = C'm R max: and C" is constant. For each case, we apply different techniques to establish the proof.
Lemma C.2 (0 Ti). Under the same conditions Theorem 4.1 for any 0 2 Ti C'n--InmR R where C' is constant, we have that
l 2 Vi.j E [=1), Vr, [m], Vi, [r].
(C.9)
where is constant.
Proof of Lemmna C.2 In this lemma, we first show that CC.8) where C" = (11) is a constant. Recall from Lemma B.3 that
hold for t S Ti nmm
(t) o ((w j.r x,)) ||x; 11/ = j),
Pj..i = Pj.r.
2 = L +
(t) d'((w j.r x(a) ||I; 1 = -j),
(1)
we can get
(t) P- n, (()) 0,
(C.10)
Veir,i
and
plttt) p1())
77
-11x; S p000
R
Pu....
(C.11)
nm
nm
(t4)) virr S <1p(t) + num
7 ||x: S (1)
1
(C.12)
Ne.r.al
marr
1um
Therefore, we have maxj. j.r.át (0(1) 3.r3. =0(1) for any S Ti and hence
max, (F+1 +1, x1), F-) (w(() x)) ((1) for any s Ti. Thus there exists a positive constant
č such that (e((0) 2 e for any t < Ti. And it follows for any j {=1), r E [m]] E [n] that
2
(t)
77
|0 |x,1 1
हा nm
| 0A stST
nm
Typ
Rym
1
||x;|
VOSISTi
(C.13)
mm
mm
On the other hand, by (C.10). C.II and
C.12 we have for any j' E {+1), [m], i' e [n] that
R2
vo Ti.
(C.14)
nm
Dividing CC14)) by CC.13) we can get for any j.3 E ((+)),r, i,). e [n] that
Rr min
(0)
2
R2
which indicates that the first bullet holds for time t < Ti long C2 ER2 2m2
17

---

Lemma C.3 (t 2 Tj). Let Ti be defined in Lemma C.2
Under the same conditions as Theorem 4.1
for any t 2 Ti. we have that
Σ Pianal C37 Σ
10 Pynhbii
(+1). e [n],
(C.15)
where C3 = (1) constant. Moreover, we also have the following increasing rate estimation of Ip 10 -p.rrdl::
1 2 r- Prine S ci log 1 allx,l13aae21
1 E 10 1p S 5.5 15511-1 1:4--110p log 1 mmllx 13050
1 - Prirr 2 c log [+ 2nl1x, Bage Cr 1330
.
(1 1 nlx Beae (1++1) nn
1 E 10 (t)
1 2 Co 7 log
1).
where ca. c, C9 are constants.
Proof of Lemma C,3
We prove this lemma by induction. By Lemma C.2 we know that CC.5 holds
for time Tj as long as 63 S 62 Suppose that there exists > Ti such that (C.55) holds for all
time 0 st 1. We aim to prove that they also hold for = f. For any 0 t have
Fg. (W Mi x2)
af (w(()) Birro x,))
(t)
Beiry xi)
m
Σ
(w/(o)
Wii x3)
Σ
P Pourr 1 1xxx (xx, xx)
(C.16)
Pourrs
Σ
Ruzal
BB
(t)
(t)
R R
3
m
Z
1
R
2
pm
m
P
8
m
where the first inequality is by (2)) 2 2: the second equality is by 5. : the third inequality is by triangle inequality and the definition of 8.p. Rmsni the fourth inequality is by the induction 1, we also have the following upper bound of
hypothesis (C.15). Besides, for any 0 <
18

---

( (W Mi x.):
y. (W x.) =
(w
Bi. x:))
r=1
(0)
Mist: Xi) + Σ Periee ||< frsmeellxee11 |xx (xxr, xx.)
0
m
+
Σ
P
R R + B
m
(C.17)
Σ
IpW.r.s AminP + 1
Puera +
Night
(t)
R R + B
P yurr
1
R 2
minn pm
Pannn + 3
m
where the first inequality is by triangle inequality and the definition of B. p. Rminn the second inequality is by the induction hypothesis (C.15). On the other hand, for any 0 < t S t, we can give following upper and lower bounds for F-v. Fw wy xs) by applying similar arguments like (C.16) and (C.17):
m
F-ys (W(1)
x;)
2
7
Σ
Wirr Xi)
-
172
7
p
(t)
Σ 8+1
1
p. R 3).
(t)
171
71 + 7 --
2 0g
R m pr)
m
(t)
Boird 33,,
(C.18)
m
and
m
F-y. (W
xx)
p P
Σ
R
Rmmia +B
m
m
o ( ( minnd
+
Σ
1p (0
-uiin (mmlaa)) + 0(3)
P'yli
Σ
(t)
mir + 3
N'yli
7(1
min pr)
2
-aar + B,
(C.19)
m
where the second inequality is by a property of leaky ReLU function that a(a + b) (aa) (b), Va, b E IR.
19

---

Next, we can bound |0 for 10r0s11--1
1
(Wi)) (1t) 1 exp 31 yi x1) - F F- 21 "16"" x,}}
(W x,1]
$ -exp(- (W!l)) xi) + Fー (W -bi x
$ exp
1
C3 R R pn
m
Panin +
(t)
7(1 3
R min pn)
m
p Puiin
(1)
2/3
m
m
(C.20)
where the second inequality is by (C.16) and C.19). And
1 1 + exp (W (1) Mi x.)
F-w. (W x4)
1 1+ exx
14y- R Rmin pm
-x=1 Mirna
(t)
211+y-22
R RR pm]
- P + (1+ + 1)
(
m
m
exp 2
1
1 + c R Rmia pn
R 7 + 223 Puinn
(1)
2 pr)
--uur (7 + 1)8
(t)
m
m
(C.21)
where the first inequality is by (C17)) and (C.88) the last inequality is by 1/(1 exp(z)) 2
exp(-2)/2if = O. By (C.20). we can get for Ststt 1 that
10,00 S exp
{
7
- C3 min Pi
1
R
m
Purra 2,3
(0)
(C.22)
m
10,01 S exp
711 (11---30 -
3 -1
c3 min pm)
R
M..rA + +28
(C.23)
m
By C.21 and Pp.. 3 10 -p-r 5 5--
we can get for 0 S <1ST-1 1
2(1 411 -,,0--1110
R min pn)
m
10 2 exp
P
(1)
+7+ =11
(C.24)
m
12,00
(1 + +1 + -cg
C3
R
2 Rmin pn)
(0) -ttrr (7 (1)))
exp
22(1 + 7 6/g n pm)
m pr)
2
2 exp
-irr, (7 + 1)8 118
(C.25)
ym
By 5.4 5.5 and o' E [7, 1), we have for 0 S S --
that
Porr S P +
(1)
71
(0(00
||x:1|2.
mmm
(e+1) 2 P Bcr.s + 7m
|0(0 ||x
mm
(C.26)
(+(+))) < 10 -iorre
( +
17 10 - ||x: 12
nmm
lp (1+2)
2 1p (1)
+
10.00 ||x,
1-
nm
20

---

By plugging C..2
C.24
C.23
and C.25
into
CC26 we have for 0 stst
-1 that
(1+1)
m
Mirra
(4)
e
exp
7 Cg
R Rinu p
m
Purini
(e)
(C.27)
==1
((+1)
(1)
n/|x/|1 1
7(1
3 C3
R Ri pn)
exp
7
m
(C.28)
Σ
(++1)
? 11 (x+1). 1)88
2(1 +
2 Cg
R
min pm
Σ
(2)
exp
Puurss
2n
1=1
r=1
(C.29)
11+1) P-iind
(1
exp
2(1 + 7 2 Cgg
R R-2
min pm)
p
Uo mal
2n
7/m
(C.30)
By applying Lemma H.I to (C.27) and taking
It 7
Cg
R
min
pn
m
(c)
P
m
we can get for 0 < 1 That
1 n||x, 111x,11ace22
/l|xx [llxs }.1)
Σ
Virg S c4 log
exp
mm
nm
(C.31)
n7|1x,11 1|24c
I C 1 log
1
t
where 64 := 1=1-1
C3
R
min pn and the last inequality by 7) S (CIRaax//mmm and is
sufficiently large constant.
By applying Lemma H.T (C.28) and taking
7(1
3 03
R
min
pl)
Σ p mana
m
we can get for 0 < t
that
m
1 7 120
mm/x,,
1223 }.1)
m sa
(1)
5 log
exp
nm
nm
(C.32)
(1+ mmllx 22
< c5 1 log 1+
1).
where cs :
c5 R 1
pn and the last inequality by 1 (Cm) and C is
sufficiently large constant. By applying Lemma H.2
C.29 and taking
2( + 7
03
R
mini Pr)
pr))
we can get
1
ye.r.i 2 (2c6) 1 log (1 1 mm /xx 12ae (r+
1).
(C.33)
1=1
where cg 1 + 7- 2 -R R-2 pn.
21

---

By applying Lemma H.2 to (C.30) and taking
2(1 + 7 C3
R Rmin pm
m
1p mamel
It =
mm
can get
1 m
1+ n||x; Beae ( :.)
Merril 2 (200) log
(C.34)
m
nm
where Ce 1 +
2cg
R R pn.
In order to apply Lemma
H.4 (requiring > a), we loosen the bounds in
C
C.33
and
C.34 as follows:
TR
M max Cre
(
Birri S cq x log
1
(C.35)
m
mm
7 1
R2 max 23
-vr c4 - log
10
(C.36)
m
nm
1
R
min C6e
C (r+1)g
Pasir (206) log
1
1
0A
(C.37)
m
R Cbe (x+1)8
w..rll 2 (2c6) 1+
y log
4A 50
(C.38)
where C.35 by Bernoulli's inequality that 1+y- S (1+x)7 for every real number 0 S r S
and x 1; CC.7) is by Bernoulli's inequality that + 2 (1 x²) for every real number
0 S r 1
1 and x 2 11. 1. If R C6e
060--6e---5 (1+1)88 2 7 25020 we have
22((0)) c4
(C.39)
If R2
min Cbe (x+1)3 (c+t11++))) < 7R R2 R 20 by Lemma H.4
we have
minf m Σ Denni m Er=1 (0(
- P Poory -r=1 10 --ve max
m
(2)
log (1+ + nR² can- (141)88
t)
2 272(2c6)
nm
log (1 + Tn c0e2d nm log (1 + n/2 1oe-11
Ti)
2 (2c6)) -tea
nm
log (1 + inRaaaa cpe22
Ti
mm
log(1 + R-2 2 206 (1+1)88")
2 (2(6)
log(1 + 703028(") (")
as long as Therefore, we can get for 0 < 5655 7tht
m
m
Σ 1 2 2
03
l0 ml Vj.j" (+1), Vi, e [m],
(C.40)
C3 S (2c6)) - min {1, log(1 R- R2-2cpe- (1+118 (1-2)1-(1++1) log(1 + 20 C²)
22

---

This condition holds under the following conditions:
R Rmind pm -
c,,0 2
2: - 2'
log (1 + R R22 (
c3 min 1,
log(1 + 72200")
This implies that induction hypothesis
(C. 15 holds for = T.
Lemma C.4 (Implication of Lemma for time t, then we have that
C. Under the same condition as Theorem 4.1 if (C. hold
where 6j is the same constant as defined in Lemma
Proof of Lemma
C.4
By o'
[n, 1J. (5.4) and 5.5 we have
10g 2 | + 27
|
Vj E (+1}, Vr e [m], Vi [x].
num
lo & (9) +
2_ 11x Vj E [+1), Vr e [m], Vi [m].
nm
Thus, we have
me x 12
1
(4)
|,vj (+1) Vr e [m]. Vi e [m].
nm
n||x 2
10gtral S
Iijj [+1] Vr e [m], Vie [n].
Therefore, 10 2 y108)
for any j.j' E (+1),
[m] and i E [n], and hence
m
m 1 ?
(4)
(C.41)
Σ Pfsel 2 my mylpp9
Plugging (C.41 back into (C.8) completes the proof.
Lemma C.5. Let Tj be defined in Lemma C.2 Every neuron will never change its activation pattern after time Tı, i.e.
(1) sign((w! j.r x.)) sign( (w (Ti)
xx)),
for any t 2 Ti.j E {+1) and r E [m]. Moreover, it holds that
sign( (w j.m xx)) = ju::
(C.42)
for any 12 T, {+1) and E [m].
Proof of Lemma C.5 For j = yı and > O. we have ((()_ J.r.i
0. and so
(w)) j.r. xz) = (w x;) +
| 1121 (xx,x:)
= -w Jor x.) + p
(0)
+ Σ 1 (x,,x))
8'
> Pj.r.
Σ
(0)
1 3
23

---

2 Pjrrt - (-)
(1)
Pr.r, R pn
(1-7 - R pn) Pjar 3,
(1)
where the first inequality is by triangle inequality; the second inequality by Ip - 2. from Lemma and Lemma C.4
By C.I3). we have for 2 Ti that
Cy R Ti = C'oy R
Por.r
(C.43)
nm
Therefore, by C.5
C.6 and C.43
we know that
(1
1i (minpp)) Py..r Vr im]] E [m].
and thus sign( (w)) j.rt x,)) = 1 for any r E [m], E [m].] = yt-
For * y/ and any 2 0, we have 7/ O, and
n
(w S. xx) = (w [ x)) Σ
(0)
Pirn 11xx/1122 (x)))x)))
Σ
Pirrge | 11 (x)
(1)
(1)
Σ 10
R + 3
- S Lir. ? 0/ J.r,
(t) R-2 Rumip pn
= (1 7 - Rm pn) (1) B,
Dir.
where the first inequality by triangle inequality; the second inequality by le S
7 lo(t) Mura from Lemma C.1 and Lemma C.4
By C.13 we have
Ry Ti C² R
(C.44)
Tum C.6 and C..44, we know that
Therefore, by CC5
7 Ac, ci RmLumm) ( -arr 8,V i [n],
and thus sign (w (t)
x,)) -1 for j Vs. which completes the proof.
D Stable Rank of Leaky ReLU Network
In this section, we consider the properties of stable rank of the weight matrix Wi() found by gradient descent time t, defined as |/ (( the spectral norm of (t), Given Lemma C.5 we have following coefficient update rule for > Ti where Tj is defined in Lemma C.2
[[2. the square of the ratio of the Frobenius norm to
p(0+1)) Puin +
-1,00 ||x: 12.
(D.1)
( (0))
79
10 ||x;112.
(D.2)
nm
where
+ exp(F,, (w(t) x.) F-9. (w(
- x,)
Based on [D. and D.2 we first introduce the following helpful lemmas.
24

---

Lemma D.1. Let 7i be defined in Lemma
C.3 For any r,r' E [m], i E [n] and f - Ti,
I Burrs Werr' al S C", 1e - e L-unr' S C²
(4)
(D.3)
Proof of Lemma D.I By C.144. we can get
17 R TI C²,
P x
for f. & Tj. Notice that
(2!1) 7/() yerri P S max (1 1o01 aorr lolt)
-iiri Mert', max - wi lo(t)
(()))
Be
which completes the proof.
Lemma D.2. Let be defined in Lemma
C.3 For any r, r [m]. i [n] and 2 Tı,
Pyuri Poir'' C" le!0 Wirt
(t)
(1) e S C²
Proof of Lemma
D.2 By D.I and (D2).. we can get for any [m]. i E [n]] and 2 that
P P = Puint
(0(0 ||x 12.
TUT
(())
((T))
(t)
xx 11.
TIT
(1) Since Par.r, Por.rr, possess the same increment and p(() have
((()
-nnn - P- possess the same increment,
100) Porr 7(221) (TT)
Puc.r
(())
Uu.rii ((0) -...r (((
(2))
Notice that
max (1)
Birra Poleet .ll (T))
(T:)
((T))
E max max(1 (T))
6 purtc (T(T))
mi S SC
which completes the proof.
Lemma D.3. Let Ti be defined in Lemma C33 For 2 Tú, it holds that
(Ti) (1)
(Ti)
h.r P Pg.nt P P P
(())
V.r. p (T)
v.rk ((1)
(T))
Mirr P P = (lp(t)
(Ti)
(T))
11/7%
for any i [m]] and r E [m].
Proof of Lemma D.3 By Lemma about the activation pattern after time Ti, we can get
(1+1)
(t)
+
-0,000 ||x: 12
(D.4)
(+++))
(1)
79
1
(t)
||x;122.
(D.5)
Wiin nm
for 2 T,. Recursively using D.4 and D.5) 1. Ti times, we can get
n n1|xx 11
(t)
(Ti)
P
Porer
mm T
25

---

? x
12
1-
nm
This indicates that for different r E [m]] p
P Puerr and
(1L)
p Po..r
par are the same, whereas
(21)
P (t) (TT)) [p( and Puir'' Par.'' are the same, which completes the proof.
Now we are ready to prove the second bullet of Theorem 4.1
Lemma D.4. Throughout the gradient descent trajectory, the stable rank of the weights W, satisfies,
W
lim t-00
e
W w
with decreasing rate of
Proof of Lemma
D.4 By Definition 5.1 we have
w +
Σ
(0) Pins
||x;112" Xx
== v.
We first show that || 2 = +log
| (2)
11
(1)
||x:1122 2x11= xx
Pini
Σ (0gora) .||xil1z + Σ
Sirell jonee (ns 11: 2 (xi, xx)
Σ
Rm
S (e)
j.rp R
1=1
R R (1 R22 R - (
2 log (og((()) (t)),
where the second last inequality is by triangle inequality; the last inequality by 10 -
y- --1 lp j. from Lemma C.1 and Lemma C.4
By the definition of (1) we have
n
n
[lv f.r
(1) J.r
12
(t)
||X
12
1 x; Σ
(0) Pirei
||x;|| 1- .x;
Pinn
1=1
2
Σ
(p (()))) -1|x:112
(0)
Xi
2
Σ (0 Jrrs
,3,,,)) 32 111xille +
Σ
(2)
10
X
jir.
X
1=1
< (C') muin + n2 R
< 2
where the first inequality is by Lemma D.I and Lemma D.2
26

---

Now, we are ready to estimate the stable rank of W( On the one hand, for | 1|. we have
|
12
|
2
Σ lI
30
(0) 1
Iw (0)
|| 12 + 2( jrr v
Σ
|1 --lll))) + 2/ ll + 11v (11l11))
ml
2111 + 2 Σ
|1 3.r S + -| || //ill
1 +
[t 3.r v + 2| w0 5.r (111)))
S <ml S mC ||
(8) Aill ||2 + mC2.
where the first inequality is by triangle inequality and Cauchy inequality: the last inequality is by Lemma D.I. Lemma D.2 and taking
C = 3(o3voo C¹ (aRRiin)
C2 = 2(ooVd+ C² VnRRmnn
On the other hand, for | 113. we have
W 20 = max
IW
(0)
x
+
2
XESU-1
(0)
x1 + / x, v/(ix)
max
max
(0)
10 x)² + Σ (0)
(0) x)
(v
J.m. x)
X-84-1
(2)
J.P
(0)
11e
J.1
Iw
10
mlll/
11 2 Σ
(v9) v/.
v11
(e)
+ Σ
(1)
(t)
2
| 11
for
5.1
j,1
(
|
- Σ
// 3or
10/111 Σ
//
00 (2l (191 + 11 - -. (2)
((t)
ml| mmll 1111
Σ 2110 v1912 + (11) 11v
12 + || I1all
10 10 (1ll)
-
ml|ly mC 12 112 mC4
where the first incquality is by taking x 3 /l fills the second inequality is by Cauchy incquality; the third inequality by breaking v j.r down into 111 + (t) vfl and then expanding the
27

---

first term as well as applying triangle inequality to the last term; the fourth inequality is by Cauchy inequality; the last inequality is by Lemma D.I Lemma D.2 and taking
C3 1.50g vd + 3C' VnR min
C4 = 1. + 3C 0o v V min-
By leverage the upper bound of |W| (1) |
11 as well as the lower bound of [ (t) [12
we can get
W 0 12
| M + C1 II 31 l2 C2
W lB
Milll - Call 3.1 1l2 C4
Since |/ 1 /
W
(
| 1ill
Ollog () and Ci C2N C3, C4 are constants, it follow that
F =1,
lim
1
and
1 / 112
(CI + +alll (C2 C4)
-
1 Ca 1, C₁
Ci C3
6(C" VnR min o ovvd)
VRR min + 0o vd
O + aoy d/n Rmax
VnRmuax log(1)
log(()
which completes the proof.
E Coefficient Analysis of ReLU
In this section, we discuss the stable rank of two-layer ReLU neural network, which is defined as
S(W,x x) (Wi(W (W
1 m Σ ((W,,r:)))
(E.I)
(W j.
where (2) max(0, 2} is ReLU activation function.
These results are based on the conclusions in Section which hold with high probability. Denote by E Epeelim the event that all the results in Section hold (for given 8, see P( (e union bound). For simplicity and clarity, we state all the results in this and the following sections conditional on & prelim'
25 by
Denote B maxij. [1( j.r xi)1). Rmaxx maxiejm] ||x:||2, Rmin min ||x:|22 p max (xx, xx)l and suppose R Rmax/ Rmax/RRmia at most absolute constant. Here we list the exact conditions for 17, Go, Ruiin Rmax, P required by the proofs in this section:
σo < (CBmax / log(mn/6)) -1
(E.2)
n < (C
(E.3)
R2 2 CRRmp,
(E.4)
28

---

where C' is a large enough constant. By Lemma B.1 we can upper bound 3 by 2 (1og(1mmm0)) Boxxax- Then, by (C.2) and (C.4), it is straightforward to verify the following inequality:
c,
(E.5)
2 Rmin' np S C, R R² C,
(E.6)
2
(E.7)
where e is sufficiently small constant.
We first introduce the following lemma which characterizes the increasing rate of coefficients Pj.,,
(0)
Lemma E.1.
For two-layer ReLU neural network defined in E..1 under the same condition as
Theorem 4.3 the decomposition coefficients (4) satisfy following properties:
Puiro 2 c1 for any 5 r' E [m]] j {=1} and i, [n]]
(t) Pirits 2 02 log
(1 2155 |||x; 13 -8
+) for any S (0) and i [n]]
2nm
(e) Pyur, I 03 log (1 + 5t) nmd
||xx; 10
1) for any r E 5 and i E [n].
where c1 C22 C3 constants. And the following activation pattern is also observed: s.0) C 5 where 5 == frr E [m] (w wi.n x,) 2 0}, i.e., the on-diagonal neuron activated at initialization will remain activated throughout the training.
Proof of Lemma E.1 We first show that the first bullet and 5.0) C 5 hold for t S Ti = Cnj nmmR=² where = (1) is a constant. Now we prove this by induction. When the two hypotheses hold naturally. Suppose that there exists time < Ti such that the two hypotheses hold for all time & i 1. We aim to prove they also hold for & = f. Recall from Lemma B.3 that
Pir.
(++1)
-jjr nm
(t) o' d'((w j.r xx))
| 1/
11/ j),
((41) D mm
lg
(t) d d'((w (( xxi) ||x 12 1 -j),
we can get
R2
Par. $ Pfrr nm
(++1)
(1)
"
||x,12 2 < P....
(t)
(E.8)
nm
( S (0(t) 1
+ nm
1)
||x; 2 S 2
(t)
R
(E.9)
nm
Therefore, max (p) j.r.i (0(()
= ((1) for any t
Ti and hence
max +1r xx), F_
x:)] 0(1) for any S Tí. Thus there exists a posi-
tive constant such that 10 2 e for any < Ti By induction hypothesis, we have s( C s
for all 0 < t t 7 1 and hence d'(w wor x,)) = for all 0 < t < Z 1. And follows that for
s(0)
(((-1)
(1)
+
7
1 ||x: P P....
en
1 0A 5O
nmn
nm
enp
on R2 R2.nn
Parori
||x; 2
>
(E.
On the other hand, by
E.8 and
E.9
we have
R nm
(
j <
12
(E.11)
nm
nu
29

---

Dividing
(0.1 by EE.I
we can get
P Purri
eRain
Vr E Si .j (+1), E [n],
(E.
Ip j.rta
(t)
R max
which indicates that the first bullet holds for time 8 as long as c1 S (cR min)/ /R For 5 we have
(w-()
Xe)r
=(w(o) Merr
xx) + Σ
mane |xx1122 (xx)
n
- (w beir: xi) + Poirr
Puliee |xx 112 (xx, Xi)
Pzz
2 Pu.rr
Veirys
|
R2
Raxxx
2 P Pir
Σ
cR2 P Puirt Rmin
minn
2 (1
R
pn)
Puiin 20,
clt.
min
where the second inequality is by (E.12). This implies that 5,00) C 5 holds for time 1 T, which
completes the induction. By then, we have already proved that the first bullet and 5:0) C s hold for S Ti = C1j nm R
Next, we will prove by induction that the three bullets as well as S. S 5 hold for any time t 2 0. The second and third bullets are obvious t O as all the coefficients are zero. Suppose there exists i such that the three bullets as well as 5/0) C s(()) hold for all time 0 < t < 7- - 1. We aim to prove that they also hold for t E. We first prove that the second and third bullets hold for t = f. To prove this, we first provide more precise upper and lower bounds for (e(0) For lower bound, we have
1490
1 exp {Fy, (WW) Mi x.) F-v. (W()) -yg+ xx))
F-
1 + exp { (Fy, (wlh ii {
(E.13)
1 +expp( th E Eregfo (w),,,, x,)
and
(w)
yeirs x,) =
Σ
(ww
Bears x;) + +Pgans +
Σ (2)
Pout.e |xxx -xx,
(ES(t)
rEs(()
Σ
Σ
Σ
(0(0)
p RRma P + +|s((0)-1
Possrit
res(()
rESSO Mii
|S!00
Porryy R pn + +15/"01-1
c1
rES(1)
rESS
(s(
|s(())
Σ
Perrr pm p + 15/5)/18
|
ciss(0)
(
TES(")
< c( + R 2
min pn/c1)
Σ
p(1))
Pui + 11500 B,
(E.
rES (0)
30

---

where the first inequality is by triangle inequality; the second inequality is by the first induction
hypothesis that (1)
(8) Parnn 2 ci cilpy.r.. for E 5!!) and 0
S S i 1 and hence I S
(t) Drestor P P the third inequality is by
17
|
(( (9)
M x1)) |x:
7 TUT
Σ
1 ||%|
Tmm
TJ
16(00) ||:
P
Tum
and hence Paurt S P Vr E , 5t0 . E o for < t F- 1; the last inequality is
by (s < m S clss and d' can be taken as 2.5 by Lemma B.2 By plugging (.14)) back into
1
we can get
10,01
pn/cs)
18:01 33 Erest0) Purrr
+ exp
Eres!os pur +B}
(E.
1 + exp
1
c(1 + R
pn/c1)
Σ
p(0)) Pastt 88.00 10 vO
2 exp
m
rES(")
For upper bound of (((0)),, we first bound F,, (W/)) (1)
xx) F vo
xx) F
(W(t)
follows:
y/
Fg, (W()) (L) Vi
xx)
F-u. ue (W(t).
Σ
Polin Σ
Σ
pere 1 -1500-18/8
(c)
8
1 (t)
m
m
TES
|
(1)
Σ
p
R
Σ
Puin, R min pn - 28
c1m|s
(
c1 [
(0)
rES()
rES
rES(()
P
(t)
2
Be PminPo pn 2,3
R 2
(E)())
(ES
Σ
i Parnt
2e R
P 2/3
m
cim
(0)
(ES(")
1 2e
R
min pc/c
2
(0) Poirt 2,3
m
(E)
where the first inequality is by
Fy. (t())
x;)
1
Σ
(w((t)
Beirs xx)
m
(t)(()
1
(w(()
Beir: x;) + Po + Σ
Emmerer ||xxx1112 (xxr, xx)
m
r()(()
Pif
1
Σ
Σ
10
-
- 15(29.8)
Pyria
m
TES(O)
rES(")
31

---

and
(w (1)
1i.0 xj) = =( -y, x;) + Σ p
-nr |x 2 1x.1122. (xx,, xx)
(0)
= =(w -y. x;) + (1)
(0)
Mnwwllxx |x=1122 (xx, xi)
Pzz
3B+ +
10 (t)
Wirrye R
r'
and hence
m
x,) F-y (W 24
o(ww
o
(t)
Werr x,)
3 +
Σ
10
-inn Rmin)):
(E.16)
m
Pti
the second inequality is by the first induction hypothesis that Poi.r 2 ci p P veitss
cilp (t)
Mara and hence r csls
Eres(")
p!t) Phrri
(t -horr
Eresfor Pasirs
cs
for r E (!0) and 0 st 1; the third incquality is by / S m; the fourth inequality is by d' S Therefore.
12101
1 Vi x;) - F- (W()
1 + exp
(Fu (W(!) (t)
-w: x;)} xxi}
Fy. (W (t) x;) + F-y. (w!)) -vc xt)}
S exp
1 2c 2 minpp pn/c1
Paniri 2 04 s0
(1)
S exp
m
rES
By the induction hypothesis, know that ( C ((() for all 0 < 8 and hence d'(ww
(0) x,)) = 1 for all r E s(o) and 0 stst- 1. By E.155 and (6. it follows that
for all 0 < 1tttt1
Σ (1+1)
Σ
ns |||;;
1Be
d(1 + R mm/e))
R
Σ
(1)
exp
2nm
m
rES(!)
rES(O)
res
(E.
Σ
Σ
(1)
y|5 ||,,
1Bg
1
2c R pn
pn/c1
(t)
Puint
exp
nm
m
TE)
TES
(E.18)
By applying Lemma H.2 (E.17) and taking xz c'(1 222 pn/e/)
E 21ES Pui.i we can get
log [+ c'(1 + pm /nl////nl/s/ m |||x v00
Σ
P 2
m
d((1 + pm
2nm2
(ES(
(E.
32

---

By applying Lemma H.1 to (E.18) and taking 2t 1-2c' R pn/c1 Σ 2e P we can get for
any 0 S.E t S i that
m
log (1+ (1 - 2d R min pm
/ )ml St x; 11ze2s
Puiri S
1 2c' Rumnn pn/a
nm2
rES
2c R
min pn/ / )n| 11,
113e
exp
nm²
log (1+ 2(1 - 2e min S
(0)
|| 11
2c' R min pn pn/c
nm?
(E.20)
where the last inequality is by S (CR / C is a large enough constant and hence
2c' R Rinin pm/c)) (/ ||x 1 /nm²² I log 2. Since s/0) C s for all 0 si-1 and
hence d'((w)) 2e xx)) for all r E ( and 0 < S t 1, we have
Point nm |T 11
Accordingly, it holds that
P yu.r P p Vr,r' E E c(0) , 10
Applying this to (E.19) and E. we can get
m
(2) [5 (0) log 1+ c(1 + R min pn //
1e 1) 1|
Peiri
c1 + R R pm/
2nm
1+ c(1+ R-2
pn/e Rm/ppp/
m
||xx
1 .t) .80
2
log
c PmiuDn/a
2nm2
m
1 2(1 - 2e R
pn/c:))me S
(0) 1|x; 13e28 t)
Puint <
log
(1 2c' R min pm [5
nm2
d'
2(1 2c' R-2 pm /cn /ea)aa))lll )nl
|| 11 1)
$ (1 2c R pn/c2)
log
1+
YO 5OSESi,
nm?
(E.21)
By taking
C3 (1 2e' R Rmpppp/ C2 c((1 + pm/a))
the above inequalities indicates that the second and third bullets hold time t T. For the first. bullet, it is only necessary to consider the situation where 2 Tj
In order to
apply Lemma H.4 (requirin b > a), we loosen the bounds in (E.21) as follows:
Pu.T. 2 c2 log
(2)
+
0A 40
(E.22)
5nm
6n) Max 28
(1) p S c3 log
1)
1
(F.23)
5nm
where we use 0.4m < |5 < 0.6m.
33

---

By applying Lemma H.4 to (2.22) and
E.23
we can get for any i, E [m], r E 5/00 r' E $ and
Ti sts i that
P (t)
log 1 +
R c
1
02
5mm
P P
Bry c28 5mm
log [
+
R 200
log
1
+
Ti
C3 log
1
By mmax 625
T2
brm
log
+ 0.2Ce- Renin
C3 log
[ 11+ 2.2 R2
Notice that s C S for all 0 --Lss and hence o' o'(w (6)
xx)) = 1 for all r E 5 and
ostst 1, we have
[()) 1 o d'((w /. xx1)) -1) ||x:|]
mm
[()) x 12::
Aj {+1),r" E [m], E [m],
(1)
1 | 1
Vr $ i'' [n].
TET
and hence 10 vl rs for 0 SiSk T. Therefore, long
(9)
(t)
log 0.20e 9 R2
log + 1.2C 28 R2 max
the first bullet hold for time = L. This condition holds as long as
è' 2.5,
2c c 1 k pm S 0.5 =
C2 2 0.37, c3 5,
log (1 + 0.2Ce- R2
C: log (1 + 2.2Ce29 R
Finally, we verify that 5:0) C { For e ((o), we have
(w
= (w (0)
Miir: x;) + Σ
Minee |xx01122 (xxs, xi)
p=1
= (ww viir:
(0)
x,) + P
Beree |x, 11 (xx, xi)
Pize
10
(Raza C12 1p12 yurror
2 P Pu.ra
Rm2.pn/c) (1)
pu 2 0,
34

---

0 where the second inequality is by ge S Punns/.. This implies that 5 C s
holds for time
t= I, which completes the induction.
Next, we show that _e-) Lrree will be much smaller than I as the training goes on.
Lemma E.2. There exists time T2 and constant e such that for any time 2 T2
le S eR mu mara
where [m],r' E (0) and i, 1' [n] satisfying -y- yer
Proof of Lemma E.2 First, we will prove by induction that for r E [m], r' E 5 and i, e [n] satisfying -Y yr holds that
1 Disr S 8 + 1 R p pl
(E.24)
This result holds naturally when t = 0 since all the coefficients are zero. Suppose that there exists time such that the induction hypothesis (E.24) holds for all time / S We aim to prove that (E.24) also holds for 1 L. In the following analysis, (T-1)
cases will be considered: (--1) | 3p and Le s B + Exsp lo 1 |x pp.
Luanel > 3 + EKpr Poirs /alell/xell
For if 1p (7-1) > B + E Repe (8-1) |1111/1122 Pp, then by the decomposition
5.1 we have
(w (
,xx) = (w x,,) + 20 +
Σ
Pur.iil X xxxll
(xL. xy)
yur
( + + Σ
x
1a O.
kes
and hence
L (-1) Lv.r,,"'
1)
((-11) o' d'(ww (T-1) xx))) 1xxr1 aa-
nm
Therefore, by induction hypothesis
E.24 at time
= 1, we have
@ ( S B + 1 + R 2 pnl
p.. l/c - 3 + 1+ R Rm pr Porr d/c1.
f-1)
For if 1p ( S B Exjg
Rep 1 1 ||| |//2 2p, by the first bullet in Lemma E.1 we have
S B
Σ
( X 12 p/a1 s 3 + Pourr R mm/ea
(E.25)
and thus
(0)
-
( 111 . ((w((=)) xx,) ||xxx
Vi.r.j
1un1
(T-1)
R)
Tum
B +
R R pn/c1,
where the last inequality is by E.25 and 1) I (CRmax/nm)) with sufficiently large constant C. This demonstrates that inequality (E.24) holds for l = T, thereby completing the induction process. By Lemma R.1 we know that there exists time T" such that
1 W.r. .l 2 e: + 1) /min/
for any time 2 T". Taking Ta = T and c = 2/c1, we have
lo(t) p
S B +1+1 1 + pm2 Py. al/cs < 2R pm) yort a//2 = cRR_2 p/
35

---

which completes the proof.
Given Lemma E.2 the following corollary can be directly obtained.
Corollary E.3. There exists time T3 and constant such that for any time 2 Σ3
10 g S mn pl, Vr mm),r's s i, e [m] with ys yv
F Stable Rank of ReLU Network
In this section, we consider the properties of stable rank of the weight matrix ( found by gradient
descent at time I, defined as | ||2/ // Given Lemma E.1 we have following coefficient update rule for any t 2 0, i E [r] and r E 5/0
(1+1) (1) 7.
-1,600 ||x:
Pe.ra
P Puina nm
(F.I)
where
+ (f.. (W
(t) Mi
x,)
F-
Ni x,)
Now we are ready to prove the first bullet of Theorem 4.3
Lemma E1. For two-layer ReLU neural network defined in E.
under the same condition as
Theorem 4.3 the stable rank of w satisfies the following property:
| 10 |
lim sup t
S
C,
where C = ((1) is a constant.
Proof of Lemma
F.
By decomposition
5.1 have
xi
(0)
(8)
||x:l12" 2- x,
[
(e)
Xxn =
Pana
Xn.
and
1 2
(t)
Xx
((())
(()))
Pj222
x x1
Pj.2.
Xx
1
-2
x1
(t) P ||
p/.m,22/x1 x|12 2
p ||> 11
Let T)) be the i-th column of A,, It follows that
|W/00
1 w/
Tx AT)
Tr Σ ai(1) T Xi (2xx xxTa((()) a()))
1m1
Tr
(t) T xxxx (t
n
(xi, xx) (t) T aa)
36

---

|2=112 Tr(a:(1) a.(()) (()((()))))))))))))))))))))))))) + Σ
(x,, xvr) (r((a(()) Tay (1)
max
Tr(as(()Ta,(())) + p
ac())) Tr(a)())a:(())
Tr(a:(1)
and
m
(at))) = Σ (t),)) = Σ ( || |2|x2211 112 < Σ
(
Pjrrzl) 2 RRmin < CmR 4 (log(t))?,
r=1
m
m
(0 (t)(a, az (t)) (a)t))/a Σ
Panaa jor S ||x 1 x|, 11 S CmR (log(t)
Accordingly, we have
|w// w w 17
S C Rm (log(t))² + C'mn p (log(t))
CmmBt max Rmin (1 + Rm (log((()))
S C' mn max Rmmin (log(t))²
On the other hand, we will give an lower bound for (W()) w (0) 1|2.
| w 1
max 1(
yyl2 )
yES'L1
1(w
(1) X
(XX
1 12
[XX 1n112
A 2
X
XX 1-11n11
We first provide a lower bound for Note that
Σ
A,1,
Ei j.mm |x 111
we need to bound
E p/r
11 r E [m]. By Corollary E.3 there exists time T such that for
any 2 T, Lytr.al I cR Pnpp Mirr.s Vi E s( and Vi' E [m] with ya = --k- Therefore, we have
for t 2 T that
ΣΣ 2 1x
Σ
1 + Σ
Sind |xxllz?
J.na
r=
iE9
iES_,
(()
|
Disre
1E8,
iES
2
Σ
+
Σ
R-2 2
max
KES
IES-, r=1
m m|s3p
cR-2 pm
2
Σ
Σ
yyrrd R
Murra R-2
|S
|s(00)
KES, rES(
SES,
r
m m|S_p
cR
cR.4 R2 R on
2
Σ
Σ
yeste R
min
Σ
Σ
Porrr R
| minies;
(((U)
VES; rES!
iES, rES()
37

---

R R
(t) Par
(F22)
sES; rES!
where the second inequality is by Corollary
E.3 and hence
10_0)
S &cRmiippp Pmpp (t)
ye w Vr, E [m], Vi, [x],
cR pr
(p(t)
(0) Porrre Vr E [m], Vi, 1' E [m],
Westit
|5
rES
cR pm
l
Pinno Vr [m]], vi [n],
|S
|
iES
rESp")
the last inequality is by
ml |||5- cR RmnxpMM
| 1
I è' c'cR-i R max pn
| miness, |
[S]]
2
Then, have for t 2 T that
172
72
2
A 1,121
Pind |x P/mm
R max
(1)
Pirss
2/m
iES, rES
R 2
SS (5
R e
log (1 +
1)
2/m
2c'mm
2V CR mn log(t)
where the second inequality is is by
F.2 ; the third inequality is by the second bullet of Lemma E.I
For |X
(Xxxxx=== 1,1122 21,, we have
X (XX
1n1/2 (X(XXX)-XXXXXXXX
(IXXX)X)-
1
Ammin XXX
By the Gershgorin circle theorem, we know that Amiu XX lies within at least one of the Gershgorin discs D(XX )a, R.), [ni] where D(XX )as, R.) is closed disc centered at (XXT) ")x
||x+11 with radius R² = Engh [Xx
)ep )xpl = Ev (xx, Xx)). Assume Amin (XX] lies within
D(XX )is R.), then we get following lower bound for Amin (XX
Amin (XXT)= 2
|
(xx,xx)) 2 R np (1 R np) R 2 R /2.
Therefore, we have
2 22n
X 1xx))-'1nle
1nll2 5 Vemin (Amin(XXT)
Rmin
38

---

Accordingly,
|
(0)
A l
CR mn log(t) C" R RemaxRain Rmiin vmn log(t).
X
XX
)
111122
/2n/ Riin
Therefore, we have for 2 T that
W (t) w (0)
C'mn max R (log(1))
C'R C R
min (log (log(t))2 S
11
mn2 R
which completes the proof.
Next, we will provide an example of training data satisfying the condition Theorem 4.3 and prove that the stable rank of w trained by gradient descent using such data will converge to 2 + o(1). We first provide the following lemma about the increasing rate of coefficients Pj...
(t)
Lemma F22 If training data "I,'' are mutually orthogonal, the activation pattern after time = Cn Pmaa/nm is determined by the activation pattern at initialization, i.e.,
Berry x.) 2 0,
Bi.ro x1) 0,
(0)
He.ro x.) < 0,
(t)
W
Birry xi) < 0,
(0)
(c) (4)
-Bii x:) < 0, (t)
[w (0)
-Birr x;) 2 0,
B..ry xx) < 0, (w())
W (0)
Berr x,) < 0,
for any time 2 T. Besides, Pjrra satisfy the following properties:
p()) Pou.r 0, Vt 0,
if (w (1)
J.r x:) <
(1)
P...T = Purirss: Vt 2 T lim (1)
(T)
if (w (1)
Mur xx) 2
t Porri log m
if (w x:) 2
x,) x,,x < O, we first prove by induction that Proof of Lemma F2 Part For if (w /.
(0)
(0 Pj..t 0, (w x.) (w j.r x:)
< 0, A4 2 0.
(F.3
The result obvious at 0 as all the coefficients are zero. Suppose that there exists such that holds for all time 0 S
We aim prove that FB also holds for t f. Recall that by
5.4
(.5)) and with (F.) at time f 1, we have
p Pira
(i . o'(( (f11 x:)) ||x: 11 1(y: 5) = -,rr, 0,
nu 7
( (i-1)
(1-1) LG- d' d'l j.r xx)) ||x 1 -j) ((ā-1) 0.
j. g.
nm
j.rri
By 5.1 and the orthogonality of training data, we can get
(w x.)
Pinn
1 1 | 2 (x), = (wj.,.,,) x,) + Pj.r. ((w xx) < 0.
2=1
Therefore,
F3 holds at time i, which completes the induction.
For (w j.r x 2 and = ys. we will next prove by induction that
p 0, ( x.) (w x., > 0, Yt
0.
(F.4)
39

---

The result is natural at = 0. Suppose that there exists & such that (F.4) hold for all time 0 s By (5.4) and (F.4) at time 1. we have
(-1)
7
1
||x:122 2
S.r. 2 0
(-1)
nm
and hence the orthogonality of training data, we can get
J.r xx) = (w (0) f.. x,) Pj.r. (w x,) 2 0.
Therefore. F.4 hold at time f, which completes the induction.
For if (w) j.r
0 and j = - ys. we first show that under the same condition as Theorem 4.3
holds that
(T) iis
-w (0) j.rt Xz).
Since T= Cn Rmin/ / we have maxj.r, Ulp jo = O(1 for t S T. Therefore, we know that
(W()) F+1(W
x:), F-F(W-WW) -1: x;)
O(1). Thus there exists a positive constant such that - -,(() 2
for all i E [m]. Here we use the method of proof by contradiction. Assume ( 2 - (w 10)
j,r x,).
Since p!2)) S j..t for 0 S t T which can be seen from 5.5 we have (!() 2 -(w jor x;) for j,n
(0)
all & < T. Then, we can get
j.r: x;) (w
j.r: xx) Pjr.s 2 AA T.
(0)
Therefore, by the non-negativeness of (w j.r x.) and 5.5 ) we can get
on cn|xx 12
(0(+1)1 = 10
n
|0
||x,||
2 e
nm
1m
and hence
onl 1i 1BT
l Sirs
cC'||x;
min 2 oC' 2 3,
which is contradiction. Therefore,
(T) - (w for x,). By 5.5 we have (1) S (T))
Lind Ejr,
(w). J.r xx) for t 2 T. Therefore.
(0) jin x.) (w/ (0) xz) Pjjrs < 0, Yt 2 T.
Plugging this into (.5 gives us
((+1)) 1)
(t)
77
(000 o d'((w)) j.r, x,)) ||x = 0/0 Vt T.
(2)
Jir
nu
This completes the proof of the first half of the lemma about the activation pattern well the first (t)
two properties of Pj.r.a"
Part Now we will show that
lim 10000
/ logt = m
(F.)
if (w!2 (0) Wor. xx) 2 0. By the activation pattern, we can get
p(0)
17.
-16.00
||< 1
Vt 0, for (w (1)
W1. xx) > 0,
nm
((0) 0,
VA 2 0. for (w (1)
Wr.3: xx) < 0,
(F.6)
(()) (T)
(!)) -
V 2 0, for (w -:..d: xx) 2 0,
-birri
Burra O,
V 0, for (w W..d x;) < 0.
40

---

Given this activation pattern, we can get for t 2 0 that
m
m
Fg. (W Vi xx) - F F-
x4
((w
(0)
xx,)
Σ
σ o(w (1)
24
Mirr
m ==1
Nirr x:)
m
rES(
[(w
Wirry x.) + (1))
+
m
TES(
Σ
(() UU.Tr + 3
rES(")
and
m
m
Fg. (W M/
x.) F 21 (W(!)
x,)
((w
(t)
Darr x;))
a (1)
-vir:x;)) x:))
Virr
m
m
(w
Bi.T x3) -
rES(()
[(
Derry x.) + +.
m
(E
(t)
23. Ui.r,
rEg(0)
Therefore, we can get following upper and lower bounds for |/(10)1
10 S
exp
Σ
yuri + +23 .t 2 0,
rES!0)
16,001 2
1
Σ
p(1)
Wirss - 8 -)) 20
exp
2
m
reg(1)
And it follows that
Σ
(+1)
Σ
P
1/1x,112020
1
exp
Σ
2 0,
m
m
am
m
rES(U)
rES(O)
rES(U)
711x:112=
(1+1)
exp
Σ
Pointi
44 2 0.
m
m
2nm
m
rES(O)
rES(")
res(O)
By leveraging Lemma
H.1 well Lemma H.2 and taking
Σ
(t)
rEg
can get
1
(1
n||x; 28
/ 13020 ) s log 1+
(1+ 2 2n/1xx 113e tt
Σ
P S log
[1
exp
m (E
nm
nm
nm
41

---

n|/x; 12=-
Σ
P 2 log 1+
t)
m
2mm
rESt
Therefore, have
lim
1
Σ
110 P logt 1.
m
rES!"
Since T
Pa for any + E 1
we have
lim (1) / logt = m/\5(/) t00
which completes the proof.
Lemma E.3. For two-layer ReLU neural network defined in (E.I). there exists mutually orthogonal data X1, "n X such that stable rank of w will converge to 2 + o(1).
Proof of Lemma F3
By 5.1). have
jrr
w
jr
+
(1) Pins'
||x:|12
Given the definition of (t) j.m we have the following representation of and ((
j.r
x1
j.r
(1)
[P
||x11122
||xx|1221
:
Xn1
-1xxa112?
(t)
||x,
112
X1
(()
Pj.m,1
(2)
||x||| 11
P.m.n
||x,
Xn.
Assume an even number and X1. Xn/2 are with label +1 while X(n Xn are with
label -1. And take X.. X, as e1, e. Given Lemma F2 such selection of training data, we have
w
w
(0)
(t)
and
(t)) +1
lim
(A/x(1/2)) (amxx//)))m0m(//P22) Omx(n/2i] [In Onx(d-n)) (A/2()/)); (mx(d-(n/2))
log E
(!))
lim
(0mx(n/2)) B (m/2))
[n O Oxx(d=n))
(0mx(n/2), Bmx(n/2), O (n)(dn)))
1-000
log L
W(O)
Amx((/2)
mxx2x/)
0 (d-nn))
lim
logt
Omx (n/2)
B
Bmx(n/2)
0 (n
where
[[(w (0) +1,1x x1) 2 0]
[[( (0)
+1,1 Xn/2) 20
m/|s(0)
Am/22/
-diag
[((w +1.m x1) 2 0)
[[ f xn/2) 2 0
m/
(((0)
n/2
Cmx(n/2)
42

---

(0) I[(w -1. (1/2))11 2
1 1[(w
11,1
1,1 1,11 Xn. 2 0]
(0)
m/15 (n/2)+11
(a/2)
.diag
11 X
[( -,m Xn,
m/|s%
Dmx(a/2)
Then, we can get the stable rank limits as follows:
(
1
A
lim 100
A
+1
11
B
lir
80000
|W 1
B
| + |B
lim
2-000
[
(max 2, [B
Since x 0 Xn ex we can get
2 0j. j.r xx) 2 0 = 1[[w 9 |
Therefore, the entries of matrix C and matrix D can be regarded as i..d. random variables taking 0 or with equal probability. For || and | F. we have
n/2
|
1[ + 2 0] (m/lss
112
B
Σ
(0) 1, 2 0] (m/15/!012
(x12=(1/2)+)
By Lemma B.2 have with probability at least 8 that 0.4m S | S 0.6m. By Hoeffding's
inequality, we have with probability at least 1 - 25 that
a/2
n/2 m 1o/(2/5)
|
m
E i=1
m
(m/ls/00
(m/1s!0 =
625mm (2g(2/0)
2
2
32
B F
(m/
m log(2/0)
(m/1s( 1
625mm (2/0)
2
2
32
(n/2))+
Next, estimate || 2 and |B Let A À A and B B + E Assume G be the
m x (n/2) matrix with all entries equal to 1 1/2. Then,
m/ :
m/ (n/2)+1
[[A] G diag
E[ G diag
m/15
m/|s (
And the entries of matrix A and matrix B are independent, mean zero, sub-gaussian random variables. By Lemma H.3 we have with probability at least 8 that
C (Vm vn+ Vlog(/00),
| 1A|2 S
2
C (Vm vn + Vlo(2/8)),
B 122 - 2
43

---

where C' is constant. Let 1g denote the row vector with k entries equal to 1. Then for E[A] and B we have
|||||]|2 =
max xEST
[Gdiag(a)x[aa
max - 1 m 1 diag(a)x||2
x 2
Vm 2
max
1g diag x
XES
m 2
a aTx x
max
xES 1 -1
/mllaal2
and By triangle inequality, we have
/milbble
|B
C
|| 2 |C||2
|
> (vmllall2)
(Vm + vn vlog(2/8)).
C
|||| < [| A 2 - (v m 2
(Vm + vn + vlo((2/0)
BBl 2 |C
B 2 2 (v m b112)/2
(Vm + vT+ llg(2/8))
2
|B|| < |C||2 + B S (v m b22
(Vm vna + vlog(2/8))
2
Notice that ||a|l3
(n)
and |bb13 = (n), then with probability least 1 -25, have
A
m||al///2 + v 625mm log(/6))33
A
(vmll
12/2 - (mm vn (log(2/0))
A
2
m m|la||3/2
/25
= - 2
A
(Vmlle
2/2 aaal|aal///2
- (v vn vlog(2/8)))
B
m m|bb|//2+ + 625mm 12g(2/))
= =
B
|b|l/22 ς ( v vog(2/8)
B
ml|b|//2 - / (025mnlog(22)))1
(Vmlib bl12/2 C ( + v (log(202) = - o(1)
This leads
W
| 2
F
lim
= 2
100
|W 19
A
2
B
lim 81000
2 2 o(1)
B
For (t), we have the following lower bound
A
B
m a
1b12)/2
625mm log (2/0)/8
F
(max {1 A 2.
B 2
( m max ||||
[1b12]// (V + vn + [og((//)))
|a| + |
(2 o(1)) (max
|a 12. (bll))
44

---

16
z -(1)
where the third inequality is by (5/3) s ||al| S (5/2) and (5/3) - |b||2 1 (5/2) Vn due to 0.4m
-
|
I 0.6m. And
|
F
B
m |6
625mm l2g(2/))/8
max
A
B 22)
(vm max ( ||a||2. |b (v + vn + v (lg(2/6))
| 1 + |16|
(2+ (2+)
(max |a 2, [bb12))
+9+0 o(1),
where the third inequality is by (5/3) S ||l|| S (5/2) and (5/3) 1 |b6|2 & (5/2) due to 0.4m $ | S 0.6m. Therefore,
RE
A
F
B F
lim
E [16/9 -1), o(1]]
W
(max
A
B 2)
G Margin Results and Loss Convergence
In this section, we prove the convergence rate of training loss as well as the increasing rate of margin for both two-layer ReLU and leaky ReLU networks defined as
f(wi), x) F+1 (w()
FW x)
F-1
+1
1 m
(t) o wl.:
x))
o(ww l,r: x)),
(G.1)
(ReLU, leaky ReLU].
We first prove the following auxiliary lemma.
Lemma G.1. For both two-layer leaky ReLU and ReLU neural networks defined in following properties hold for any / 2
G. the
v.((WO) x;) 2 - e for any E [n] where is positive constant.
vi((W() xx) - yu.f(WWW xx) S C₁ for any i, E [n] where C₁ is a constant.
10 < C2 for any i, [n] where C22 is constant.
s C s((+1) for any E [n]. where s(() = {r E [m] (wo)rr x;) 2 0}.
Proof of Lemma
G.I We prove this lemma by induction. When t = 0, since
bu b.f(((()) (0) xx)]
Σ jun (W 10) x:)
1 m
Σ jy
a
(w
j.m x;))
(0)
m
o
(0) j.r
xx)))
m
$
Jor x;ب1
28,
45

---

the first bullet holds as long as c 2 23. We also have
(0) xs) S l xx)1 + (w (0), .xx]] S 43, y: y: x.) yn (W()
which verifies the second bullet at time t 0 as long as G1 N 4,3. This leads
1 + (W
(10) 1 + exp(v.
- 2 + exp(ya xx)) - ,.((((())
< 2(1 + exp(Ci))
C2.
as long as C2 2 2(1 + exp(Ci)). For any r E s(O), we have
(w h.r: xx) = (w (0)
x
(1)
fh. x(i)
Xy 9xx))
1
(w (0)
x,)
17
|
12
77
1 d' (o xzi) (M
1
(0)
x,)
+ n
10, (0)0
|
"
14 1 x,ح|
mm
7177
M
(0) 20
where the second equality is by (w (0)
yor, x.) 2 O; the first inequality is by triangle inequality; the second inequality is by 1 1/1, S C2 and the condition that 122 2 Cnp. C is a sufficiently large constant. This verifies the fourth bullet time 1 O.
Now suppose there exists time F > 0 such that these four hypotheses hold for any 0 S E. We aim to prove that these conditions also hold for t = T 1. We first prove that y: / (W((+1), x;) Z
(.(( x.). We have
v:f(W x.) (W (8), xx:)
Σ nn [3 (F((W( (+1)) x.) - (. xx,))
Eus 1
[o((w , xx)) - (( (
(++1)
j.r x;)))
m
(E+1)
xx)) - o ((
j.rt x,))
Σ
yr
for
(-n Vwy., I.s. (.s( x,)
m
(w j.r x,) - (w jor x,)
(1-1)
m
(7+1)
xx)) ((w(((
Σ
yi
for
17
E 1. - -.o((1 j.r xx²) juixe, xs)
m
xi) - (w jim x,)
nm
jrr
xx)) a
17
j.r x()) ||x:11
(++1)
xx) (w j. x
(f11) xx1) 0
n
(0 σ d((( (wm.P.x))))) xx)) (wixe, vex)).
(++1) x;) (w j.r: xi)
nu
46

---

By the fourth induction hypothesis at time = E, we have s(a+1) [ - and hence
a( o( (w1) xx)) - ((
(w ((+1)) .xi) - (w)
j.r xx))
jirt xs)
jr (++)
1,
(G.2)
(w jr x.) (w) j.m x,)
(w) (wfrt") (ftt))))
.x,) - (w) jint x,)
for j = y and r E $ For E Ieaky, ReLU], a is non-decreasing and 1-Lipschitz continuous, which gives
I a( (++1)
jrr xx1) a((w J.rt xx))
S 1.
(G.3)
(w (2+1)
xii - (w (2)
j.r xi)
j.r
Then, we have
m
Vi W.((W) xi) - (W ( xi) x,) 2 nm? 2
||x
71
(xxr, x,)
num
rEs(1)
2mm²
2
rES()
[x,
2nm
"
(0)
||x 2
5mm
where the first inequality is by
G.2
G.3
o' E [0, 1] and triangle inequality; the second inequality
is by 11(1 S C2. (s
1
0.4m and the condition that R 2 Cnp, C is
sufficiently large constant. And
y: (W((1) x;) y: v.f(W()) xx)
14,0
||x:122
1
(10 1 (xx,x)x))
nm2
nmm 2
rES(!)
< 31
|x: 2
2nm
2
3n 1400
11x:112.
nm
where the first inequality is by G.3 1
a' E [0, 1] and triangle inequality; the second inequality is by 2 Cnp, C is sufficiently
S C22 1s > ( 0.4m and the condition that R2
large constant. Now, we obtain
w.((W(+11) x.) 2 W.f(W()) xx) +
||x:
(G.4)
5 37
(.(())+))) x.) S v.f (W()
xx)) +
| 112
(G.5)
nu
which implies that y / /W(((+)) (++) x;) 2 ya (W(0)
x,) 2 -c.
This verifies the first bullet at time
t= t= 1. By subtracting (G.5) from
G.4). we have
yu g (W(+1)) xx) y.f (W (++1) x,)
$ s (xx) - y. v.f(
xx: 0xxx) +
3q e |xxx 12
" 5mm
-1 -||x
nm
47

---

11 1112 2 15A2 then 3y 16 || 11 1 5um -1.100 ||x; 11 and hence
nm
yk ( xx) yaf ( (+1)) xi) S wif((W() xx.) - y.f(( xi) S Ct.
If 1112 < 15R² then by Lemma H.5
ykf yxf(W xx.) v.f(w x,) - 1/114)1)1111(0))) < log(60
and hence
ya. IW xx) vi((W(t))) x1) S yw xx.) -y:[(W x:) +
31
1660 ||x
nm
S log((00 +1.
Combining the two cases, we have
yz u (F+1), xx) xxx)
y:f(( x.) S C1,
as long as C1 2 max m43, (og((R2))) + 1}, which verifies the fourth bullet at time = + 1. By
Lemma H.S this leads
((+1)
1 exp(yu
xx:)
((+1)
1 + exp(y W ((()),,,,,)
k
< 2(1 + exp(yx/ (+1))) xx) - Vz (W+(( x:))
< 2(1 + exp(Ci))
$ C2
as long as C2 2 2(1 + exp(Cii) For any r E S (F+1)
we have
n
(w (t2)+)) 21.t xx) = (w (w(
(F+1)
x;)
7
o d'((w bur
(E+)E xi)) (ye wix))
=(w(E+))
(E+2) ||x;112
nm
(E+1)
((w
(w(+t))
(E+1) xx,)) X vixi)
nm
(F+1)
x,)
7
1 (E+1)) ||x;11
(((2)) |(x,,,)))
Y377
x,) 2 O,
where the second equality is by (w (++1)
(Win x,) 2 0: the first inequality is by triangle inequality;
the second inequality is by |& (11g S C2 and the condition that R2 Riin Crep, C is sufficiently large constant. This verifies the fourth bullet at time i T 1.
Notice that [| | = Olog t) and considering the fact that the difference between any two margins can be bounded by a constant, the difference between any two margins can be bounded by a constant, can derive the following lemma, which demonstrates that the normalized margin of all the training data points will converge to the same value.
Lemma G.2. For both two-layer ReLU and leaky ReLU neural networks, gradient descent will asymptotically find a neural network such that all the training data points possess the same normalized margin, i.c.,
W
W( |
lim 8-000
Wf
x.)
xx) = 0,
|
for any i, k [rs].
48

---

By Lemma G. we can establish the subsequent lemma regarding the logarithmic rate of increase in margin. This lemma will be beneficial in demonstrating the convergence rate of the training loss in subsequent proofs.
Lemma G.3. There exists time T - nm) such that the following increasing rate of margin W.((W)) x;) holds:
M.f(W() .x.) logt (og(n|/x:1//mm))) S SC',
(11x: nm t)
(1lIxilé
C4
10t S Css
1)
nm
for any i E [n] and / T, where C3, Ca, C3 constants.
Proof of Lemma G.3
To prove this, we want to leverage Lemma H.l and Lemma H.2 To achieve this, we need approximate |,,50 by y:f(W()) x:). We have
1
S exp ( (- v.f(WW. yi x:)).
(G.6)
+ exp (yif(W bi xx))
and
exp (- (:
2i x,))
(G.7)
+ exp (yis (W)) (1)
x:))
I+ c
by yef( x cc Plugging the upper and lower bounds of |((00) into G.4 and
G.5 we
obtain
3n/ xi
vi((W(+11) xx) - () ,x,,
xx))
cxp ( 1.ffff((W]) /
x,));
(G.8)
nm
/|x 13
vf((W(+1) xx) - ()((((() xx:)) 5(1 e
cxp
yi (-n 91 x;))
(G.9)
mm
By taking o, = w.((() x.) - MWW() x.) and applying Lemma H.l to G.8
we can get
371|x, X
1
37l X
12
(if(W(0)) x:) S yi (W x;) + log (1+ CW:S(W x.)
exp
x.)
As long as t 2 3011x.113
(l xz) nm exp
3111x;113
O RR- nm). we have
exz/(wlo)
6n/|x;111
31p 33)[|x;11
(i((W(() x3) svf(W()) xx) log
exp
(W)) )m) 1)
eVL( x5 xm
(111x=112
37/1x; x2xx1
logg 1 log
+ +ogg
Tim
(W))
/111x
< <logt + log
+ log +1 1,
num
where the last inequality is by (V) xx)) s 23 and n S (C C a sufficiently large constant. By taking v, = / (W xi) - vi(((0)) (0) x.) and applying Lemma H.2 to G.9
we can get
n n
We (F(( xxs 2 vif (.()) +log
5(1 + e Dew: f(W x t)
1 | ||
2 v. v.f(W(o) xx) + log
551 + ex f( (Wo) mm
= loggt + log
log (5(1 + E)))
nm
49

---

Since
use it to derive an c24 @ x.)mm
3r/ 1
eli.(w(o)) xx: nm
623
exp
3 17
R min nm,
37/|xx 11:
3/7|xx:1
Taking
22
T
R nu min
C3 max { log 6 + 1, log (5(1 + {)))
3
completes the proof of the first equation. By plugging the margin upper bound into (.66), we can get
Σ exp ( - y:f(W vi x;))
I cxp
log - (oggnn/x1////mmm + C2)
[n||x; 1
exp(Ccs
nm
By plugging the margin lower bound into G.7
we can get
2 + e
exp ( y.f( (t) xx)) yi
2 + e
exp ( -lo t - (l13///11l/mmm) C2s)
( ("mm -t) -1
2 co (1 (1 + ea)
nm
Therefore, taking C4 1/e (1 + cd) and Cs exp(C) (3a) completes the proof.
Now we give the following lemma about the convergence rate of training loss.
Lemma G.4. For both two-layer ReLU and leaky ReLU networks defined in G. have the following convergence rate of training loss
Ls(w())) = O( ((()))
Proof. Having obtained lower bound for the margin in Lemma G.3 upper bound for the loss function as follows:
Ls (s())))
e(ys ((,s(W(),,))
12
log (1 + exp (W),((((),x))
exp ( 1.J([ x:))
< Σ exp ( log - log(n) ( ///1//111///mm nm)) + Cz)
(n|xxa113 113 t)
n Σ exp(Cs))
nm
= O(
where the first inequality is by log(1 + 2) S 2; the second inequality is by Lemma G.3
Having obtained an upper bound for the margin in Lemma G.3 we can now use it to derive a lower bound for the loss function as follows:
Ls Ls(W!))=
1
(w.s(W(), x:))
50

---

log (1 + exp ( (- -iJ(W()) (x))))
cxp ( ( y:f((W()) x.)) - cxp ( (- 22y: (-2y: xx))
71 1=1
exp (-log - log(nl l/l////l//mmm - C3)
71
exp ( -2(logt
t + Log(nll>: - C3))
1
( 1) - exp(2(s)
(n|Xx: 7177
))²²
-2
71
mum
((((
where the first inequality is by log(1 + 2) 2 22/2 for 2 2 0: the second inequality is by
Lemma G.3 This completes the proof.
In addition to the aforementioned lemmas, in the case of leaky ReLU, assuming convergence in direction, we can demonstrate that the directional limit corresponds to Karush-Kuu Kee--Kuuhnn--eee Tucker (KKT) point of the max-margin problem. This result is presented in the following lemma.
Lemma G.5. For two-layer leaky ReLU network defined G.I
assume that W(1) converges in
direction, i.c. the limit of w(t) /// exists. Denote lim /| [| as W. There exists scaling factor 0 such that a W satisfies Krmns-KKhhnTTuckee (KKT) conditions of the following max-margin problem:
1 min w 2
W
s.t.
Vif(W, xx) 2 1, Vi [m].
(G.10)
Proof. We need to prove that there exists AI,... An such that for every j E {+1} and r e [m] we have
Σ Ar Vw, (vi((W,x,)) = Σ Aayiy o (dWWjrr (w)) x,.
(G.11)
By 5.1. we know that
lim
jr
t0000
W
n
lim
jr
||x:1122 1x X;
100
( |
(4)
Pj.ra
lim
||x:|122 x;
t-000
[W
lim
Pinn
||x:1l2² X..
where the second equality is by | || = O(log t) and the last equality is by the existence of lim, (tt) / || as well as the uniqueness of data-correlated decomposition. By Lemma D.3
and | Ollg t), we can obtain that
Para
lim 1000
(G.12)
+00
|
51

---

for any j { r, r,r E [m], i E [n]. and
(4)
Pa.
P
lim 1-00
|W --y-
lim 10000
(G.13)
[W
for any j f {+1], i, i' [n] with j = yi. = -y and r,r' E [m]. Define
S = (i E [m] = 5}. X4 = lim
t-:00
|
By (.122, i E [2)
we know X is well defined and X₁ 0. And by G.13 we know that for any [m].
lim
P-
-->-
W
Then, we have
lim
[
||x:
-2
2
F
t=1
lim
|x1112" 2
X,
lim
Pj..i
||xx1122 X,
t-+00
[WO |F
iES
X
X 2 X;
||x
11
X;.
iE
iES-s
By Lemma C.5
it holds for any 2 Ti that
((ww!! (t)
Jir: xx)) 1,
Vje [#1}, ie Sj,
((w!!) (1) x;)) = 7,
e ie E
This leads
o' o'((W,,r:: 1,
Vj {#1), is., Vj iel. S_g.
o' d'( y,r: xx)) = 7,
Thus, get
Σ X1 ( (W...... xx)) 1xxi1222 xx,x
Σ
X o' x:)) ||x 1222
Wir
iES,
SES
Σ Xyij o' ((Wir, x:)) |1x: X;.
Taking X; X1 completes the proof of G.I.). On the other hand, by Lemma G.2 and the assumption of the existence of w(() /| |. we can get
wff(W xx) v.f(W,
for any k [n]]. Taking 1W,.f(,xx,) have
,,(aW, =
for any i [n], which completes the proof.
H Auxiliary Lemmas
Lemma H.1. Let {x, 1 be an negatige sequence satisfying the following inequality:
I++1 Iz C F 0
52

---

then we have
It S log + Ce..et.
Proof of Lemma H.1
Given the inequality I++1 2i S e for all t 2 0, we want to prove that
vr S log
+ Ce T) for T 2 We start by manipulating the inequality as follows:
Ei+1 21 1 C =
1++1 21 v C -++1+0
(using 2++1 instead of xz))
2++ [+++1 x4) S Ce
(multiplying both sides by e"t+1).
Summing the inequality from t 0 to t = T 1, we get:
Σ -t (a++1 x1) S Ce T. t=
Since e" is a monotone increasing function, we can approximate the above sum with integral:
| d Ce.. .T
Evaluating the integral, we get:
T 50 < Ce. T.
Rearranging the inequality, we get:
eT < Cec.0e.. TT
Taking the natural logarithm of both sides, we get:
S log(e + Ce T).
Therefore, we have shown that < log(c + Ce T), as required.
Lemma H.2. Let {xx [ be an sequence satisfying the following inequality:
T++1 Iz C e V2
then we have
34 z log( t0 + C Ctt).
Proof of Lemma H.2 Given the inequality I++1 x, 2 e for all t 2 0, we want to prove that
JT 2 log(e + T) for T 0. We start by manipulating the inequality as follows:
Ø141 - xt 2 mt
*d (#++1 xx) C
(multiplying both sides by e²*).
Summing the inequality from I = t / = T 1, we get:
(I++1 21) 2 T.
t=0
Since e is a monotone increasing function, we can approximate the above sum with integral:
e T.T
80
Evaluating the integral, we get:
FT 20 2 C.
53

---

Rearranging the inequality, we get:
e 2 c00 + C.
Taking the natural logarithm of both sides, we get:
2T 2 log(e"0 + C T.).
Therefore, we have shown that 2 log T0 C T), as required.
Lemma H.3 (Theorem 4.4.5 in Vershynin (2018) ) Let be an m x n random matrix whose entries di are independent, mean zero, sub-gausssan random variables. Then for any t > 0 we have
||||| CK(ym + vn 17+01
with probability least - 2 exxe Here K maxij |asilloa where || ll is the sub-gaussian norm.
Lemma H.4. For t 2 2 0, we have
log(1 + al) log(1 + bt)
log(1 + as) log(1 bs)
ifb 0.
Proof of Lemma H.4 Let ft) log(1 + at) log(1 + bt), and we want to prove that f' > 0 for all t >> 0. To find the derivative of f(t), we use the quotient rule:
(t()) (log(1 + 6t)) d (log(1 [ at)) (log(1 + at)) 4 (log + bt))
(log [1 bt))
(log(1 + b()) T4at (log(1 - att)
(log(1 + bt))²
a(1 bt) log(1 bt) b(1 at) log(1 + at)
(1 + a1 (1 + (log(1 + bt))
Next, we define the function g(() (t 1) log(1 bl) - (1 log(1 al), and aim show that g' (1) > 0 for all <>> 0. We start by computing the derivative of g()):
g((() log(1 + bt) log(1 + at).
Since and 0, we have 1 1+ bt > + at, which implies that log(1 + bt) > log(1 + at). Therefore, have (t) for all t > 0. Note that 90)
then have g(t) > 0 for all >> 0. Therefore, we have a(1 + bt) log(1 + bt) 6(1 + at) log(1 + at) > 0 for all > 0, which in turn implies that f'(t) > 0 for all > 0. Thus, we have shown that f(t) is increasing for >> 0 and hence f(t) f(s), which completes the proof.
Lemma H.5. Let g(=) = (=)) = 1/(1 + exp(=))) then we have that
((22)
< 2(1 + exp((z =2)), Vzi, 22 E I,
g 5221)
and
((22)
1
2 exp(21 - 22), V2a E R, 22 2 1.
9(21)
Proof of Lemma H.5
We first prove the first inequality. For if 21 I 0, we have
g(22) + exp(21)
< + exp(2y)
S 2.
(
+ (2)
54

---

For if 21 > O, we have
( + exp(21)
2exp(z1) exp(22)
1
2cxp(22 - 22).
(21) + exp(22)
Thus, for any 21 E R, we have
( (
2 + 2 2exp(21 22).
Now we prove the second inequality. We have
g(22) 1 exp(21) exp(- 22) + exp(21 -22) 22) exp(21 22) 1
exp(1) +1 2 exp(21 22),
g(21) 1 + exp(22) exp(-22) 22) +1
which completes the proof.
55


Reviews:
[{"review_id": "yut2OZprrT", "reviewer": "Reviewer_c8EH", "summary": "This study analyzes two-layer ReLU and leaky ReLU networks trained by gradient descent in a classification problem. It is shown that when training data is mutually nearly-orthogonal, by taking an initialization scale and a learning rate sufficiently small, a leaky ReLU network converges to a parameter with stable rank 1. They also show that a ReLU network converges to a parameter with a bounded stable rank, and it will equal 2 when the input is completely orthogonal. A similar analysis has already been provided by Frei et al. 2022 (with gradient flow and Leaky ReLU), this work takes another approach apart from the KKT condition, and a possibly faster convergence rate is obtained.", "questions": "- The authors conduct numerical experiments and observe the stable rank of trained networks, but I'm wondering about it precisely reflects the theoretical result. That is, whether the stable rank of the leaky ReLU network with large $\\gamma$ converges to 1 or not, and the stable rank of the ReLU network could converge to 2 by using fully-orthogonal training data.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Frei et al. (2022) have already shown a certain result on this topic, but it requires several non-practical modifications of the algorithm \n(such as considering gradient flow or smoothed leaky ReLU).\nThis study overcomes this shortcoming with a novel approach and obtains further results (extension for the ReLU activation and gradient descent without smoothing), which has an important novelty.\n", "weaknesses": "- The near-orthogonality assumption $R_{\\min}^2\\ge CR^2\\gamma^{-4}np$ seems to be strong (while Frei et al. (2022) also impose the same condition, but I realize that they assume high-dimensional settings).\n\n- It will be more interesting if the authors can characterize the direction to which the weight matrix converges. \n\n- The authors refer to the works on benign overfitting in the related work section, but the connection of this study to them needs to be made clearer. Does this study focus on high-dimensional settings? Or is the double descent curve provably obtained by this study?\n\n- Some terms are used without definition, such as $W_{y_i}^{(t)}$ in (5.8) and $w_{y_i,r}^{(0}$ in Lemma 5.5, and so on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and valuable comments! We address your comments and questions as follows.\n\n----\n\n**Q1**. The near-orthogonality assumption seems to be strong.\n\n**A1**. We have based our work on the assumption of nearly-orthogonal data following Vardi et al., (2022) and Frei et al., (2022). This assumption becomes milder in the high-dimensional setting. We will add more discussion about that in the revision. Although we are not aware of any weaker assumption to be used here, we will pursue it as an important future direction. \n\n----\n\n**Q2**. It will be more interesting if the authors can characterize the direction to which the weight matrix converges.\n\n**A2**. Thank you for your suggestion. There exist several challenges that need to be addressed to establish the directional convergence of the weight matrix. Firstly, in the context of leaky ReLU, even though we can demonstrate that neurons within the same class align with a common direction, we haven't yet devised a method to prove the convergence of $\\rho_{j,r,i}^{(t)}/\\\\|W_j\\\\|_{F}^{2}$. In the case of ReLU, prior to delving into directional convergence, we need to comprehend the activation pattern of all neurons. Regrettably, in the ReLU scenario, we can only characterize a portion of the activation pattern. As the training progresses, unlike the leaky ReLU case, instances might arise where neurons belonging to class $y_i$ remain deactivated by $\\mathbf{x}_i$, and neurons of class $-y_i$ are consistently activated by $\\mathbf{x}_i$ or even alternate their activation states infinitely. Consequently, establishing directional convergence proves to be intricate at present. We plan to delve further into these intricacies in the future.\n\n----\n\n**Q3**. Does this study focus on high-dimensional settings? Or is the double descent curve probably obtained by this study?\n\n**A3**. Yes, both our paper and the papers studying the benign overfitting phenomenon focus on high-dimensional settings. We both need to prove that the training loss will converge to zero for the non-convex loss. However, implicit bias is a property of the learning algorithm on the training data, while benign overfitting/double descent is a property of the learning algorithm on both training and test data. Since we don’t make any assumption on the test data distribution, we are not able to prove double descent or benign overfitting in our study.\n\n----\n\n**Q4**. Some terms are used without definition.\n\n**A4**. In line 95, $W_j$ is defined as the collection of model weights associated with $F_j (j\\in{\\pm 1})$. Additionally, $W_{y_i}$ signifies the collection of model weights belonging to class $y_i$, whereas $W_{y_i}^{(t)}$ pertains to the collection of model weights of class $y_i$ obtained via gradient descent at iteration $t$. Proceeding to line 96, the term $w_{j,r}$ is clarified as the weight vector corresponding to the r-th neuron in $W_j$, and $w_{y_i,r}^{(t)}$ denotes the weight vector corresponding to the r-th neuron within $W_{y_i}$ obtained by gradient descent at iteration t.\n\n----\n\n**Q5**. Wonder whether experiments reflect the theoretical result. That is, whether the stable rank of the leaky ReLU network with large $\\gamma$ converges to $1$ or not, and the stable rank of the ReLU network could converge to $2$ by using fully-orthogonal training data.\n\n**A5**. Thank you for your suggestion! We have conducted additional experiments to validate our theoretical results for long epochs (1000). The stable rank for the leaky ReLU network with large slopes will converge to $1$. In comparison, the stable rank for the ReLU network will not converge to $1$. \n\nWe also conduct the experiments on the fully-orthogonal training data and find that the stable rank for the large-width ReLU network will converge to $2$ instead of $1$.  The detailed proof for the behavior of a large-width ReLU network on the fully-orthogonal training data can be found in Appendix Lemma F.3 from Line 796 to 828.\n\nThese additional experiments can be found in the uploaded PDF."}, {"review_id": "cLxiYEH77f", "reviewer": "Reviewer_4Kvz", "summary": "This paper studies training two-layer leaky-ReLU/ReLU networks with gradient descent. The authors show that for approximately orthogonal data, GD converges and the weight matrices in the leaky-ReLU network have a stable rank of one asymptotically under GD, while those in the ReLU network can have a stable rank larger than one.", "questions": "See \"Weakness\"", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The convergence analysis of GD on two-layer neural networks seems novel\n2. The characterization of the stable rank of the weight matrices is interesting", "weaknesses": "1. There is little discussion on the upper bound $c$ in Theorem 4.3. How large it can be? How does it depend on the training data?\n2. For leaky-ReLU, the theorem only says it has a stable-rank one, meaning $W_j$ is approximately rank-one, is there a characterization of the left and right dominant singular vectors?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback! Here's our response to your comments and questions.\n\n----\n\n**Q1**. There is little discussion on the upper bound c in Theorem 4.3. How large it can be? How does it depend on the training data?\n\n**A1**. The upper bound c in Theorem 4.3 can be considered an absolute constant. The relationship between c and the training data is determined solely by two quantities: $np/R_{min}^{2}$ and $R=R_{max}/R_{min}$. However, we make the assumption that both of these quantities can be bounded above by a constant. As a result, the upper bound c can also be treated as a constant. And the exact form of upper bound $c$ is given by $CR^6(1-R_{min}^{-2}np)$ where $C$ represents an absolute constant unrelated to the training data. The terms $R$, $R_{max}$, $R_{min}$ and $p$ are defined in lines 108, 109, 110.\n\n----\n\n**Q2**. Is there a characterization of the left and right dominant singular vectors?\n\n**A2**. The convergence direction of network parameters as singular vectors of a tensor has been examined in linear neural networks trained via gradient flow, as described in [1]. However, for non-linear and non-smooth neural networks trained using gradient descent, the directional convergence of the weight matrix remains an unresolved issue. As we have not yet demonstrated the convergence of the weight matrix, we are currently unable to characterize the dominant left and right singular vectors. We will comment on this point as a limitation of our method in the final version.\n\n[1] Yun et al. \"A unifying view on implicit bias in training linear neural networks.\" arXiv preprint arXiv:2010.02501 (2020)."}, {"review_id": "TetupNa58i", "reviewer": "Reviewer_BcDb", "summary": "The paper investigates implicit bias, especially in terms of the stable rank of the weight matrix (which is the square of the ratio between the Frobenius and spectral norms), of gradient descent on the logistic loss for binary classification tasks and two-layer neural networks, where the first layer is trained and the second layer is fixed, the activation function is either ReLU or Leaky ReLU, and the training data are nearly orthogonal.  The main results are that, provided the learning rate and the initialisation scale are sufficiently small, as the number of training steps tends to infinity, the stable rank tends to 1 in the Leaky ReLU case, and is bounded by a constant in the ReLU case.  The authors also prove upper bounds on the convergence rate of the empirical loss, and tight bounds on the convergence rate of the norms of individual neurons in the Leaky ReLU case.  The theoretical results are supplemented by experiments on synthetic data generated by adding Gaussian noise, and on MNIST.", "questions": "What can you say about what happens if the second layer is trained as well, or if the network is deeper?", "limitations": "Training only the first layer significantly simplifies the dynamics.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper tackles one of the greatest current challenges in the theory of learning, namely understanding the implicit bias of gradient-based algorithms and its consequences for generalisation.  In contrast to most related works, it considers gradient descent rather than gradient flow, and is thus more readily applicable to practical settings.  The activation functions that it focuses on, namely ReLU and Leaky ReLU, are among the most popular.  The theoretical results are proved in detail in the extensive appendix, and sufficient details as well as the code for the experiments are provided.", "weaknesses": "The paper is a follow-up to \"Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data\" by Frei, Vardi, Bartlett, Srebro, and Hu (ICLR 2023), and shares most of the assumptions with the gradient descent part of that work, with the important difference that in the present paper the activation functions are ReLU and Leaky ReLU rather than a smooth variant of Leaky ReLU as in that work.  It is not very clear to me what difficulties exactly needed to be overcome to step up from that previous work to this paper, or in other words to what extent and in what ways the present paper is not a straightforward increment.  Another aspect that is similarly unclear to me is how essentially different are the ReLU and Leaky ReLU cases.  The theorems and proofs for them are presented in the main and in the appendix mostly separately, yet seem to follow similar patterns, so it would be good to clarify where the main underlying differences are.  A minor comment is that there is a typo saying that the signal-noise decomposition technique is introduced in the Preliminaries.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable comments and feedback! We address your comments and questions below.\n\n----\n\n**Q1**. It is not very clear to me what difficulties exactly needed to be overcome to step up from that previous work to this paper.\n\n**A1**. The technique employed in this paper differs significantly from that used in [1]. The argument presented in [1] (similar to the approach in [2]) heavily relies on the smoothness assumption of both the activation function and the neural network. They utilize this assumption to approximate $f(W^{(t+1)},x)=f(W^{(t)}-\\eta\\nabla L(W^{(t)}),x)$ by $f(W^{(t)},x)-\\eta\\langle\\nabla f(W^{(t)},x),\\nabla L(W^{(t)})\\rangle$ to establish the balance of loss ratio for different training examples, which lays the foundation for proving their Theorem 4.2.\n\nIn sharp contrast, our paper adopts a significantly different technique, which transforms the analysis of $W^{(t)}$ into the dynamic and increasing pattern of decomposition coefficients $\\rho_{j,r,i}^{(t)}$. We then use these coefficients to approximate $f(W^{(t)},x)$ and prove our theory. This approach allows us to get rid of the smoothness assumption, making it suitable for analyzing Leaky ReLU/ReLU (rather than their smoothed version) networks.\n\n[1] Frei et al. \"Implicit bias in leaky relu networks trained on high-dimensional data.\" arXiv preprint arXiv:2210.07082 (2022).\n\n[2] Frei et al. \"Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data.\" Conference on Learning Theory. PMLR, 2022.\n\n----\n\n**Q2**. How essentially different are the ReLU and Leaky ReLU cases.\n\n**A2**. For the case of leaky ReLU activation functions, we can accurately describe the activation behavior once a certain threshold of training time has been reached. To elaborate further, this behavior entails that beyond that specific time point, all neurons of class $y_i$ can be activated by the input $x_i$, while none of the neurons of class $-y_i$ can be activated by $x_i$. This observed pattern forms a pivotal basis for establishing the stable rank of the weight matrix. This is due to the fact that, given this pattern, the increments in $\\rho_{j,r,i}^{(t)}$ are consistent across different values of $r$, assuming a fixed pairing of $j$ and $i$. \n\nHowever, for the ReLU case, such a property does not hold. It is rather challenging to comprehensively characterize the activation pattern, as there might be instances where neurons of class $y_i$ are never activated by input $x_i$. Additionally, the activation pattern of neurons belonging to class $-y_i$ with respect to input $x_i$ could be consistently activated, or even flip infinitely throughout the training process. Consequently, the increments in $\\rho_{j,r,i}^{(t)}$ might exhibit inconsistencies across different $r$ values, assuming a fixed pairing of $j$ and $i$. This leads us to only be able to establish a constant upper limit for the stable rank of the weight matrix. As a result, the arguments for both leaky ReLU and ReLU, presented in both the main paper and the appendix, are treated separately. \n\n----\n\n**Q3**. A minor comment is that there is a typo saying that the signal-noise decomposition technique is introduced in the Preliminaries.\n\n**A3**. We’re sorry for the typo. We will remove the “ signal-noise decomposition technique” here.\n\n----\n\n**Q4**. What can you say about what happens if the second layer is trained as well, or if the network is deeper?\n\n**A4**. Our proof begins with decomposing the weight by the direction of the data input, and demonstrating the coefficients satisfy an ‘automatic balanced’ property. When working with deep neural networks, or two-layer networks with the second layer being trained, we need to first decompose the weight by the direction of the layer inputs. For example, we can decompose the weight of the first layer by the direction of the data inputs, but for subsequent layers, like the second layer, we must decompose the weights with respect to the direction of the second layer inputs (i.e., the data representation after the first layer). We can then prove that the coefficients remain auto-balanced. However, a significant challenge arises when the direction of the data representation changes during training. To address this challenge, we need to prove that the direction of the representation will converge, which requires more involved analysis. We will explore this direction in the future."}, {"review_id": "DcMC45TYFl", "reviewer": "Reviewer_6oj7", "summary": "The paper studies convergence and implicit bias in two-layer (leaky) ReLU networks trained with gradient descent. They focus on the case where the initialization scale and the step size of GD are sufficiently small, and the training data are nearly orthogonal. They show two main results: \n-  For leaky ReLU networks, they prove convergence to stable-rank 1 of the weight matrices (they consider the matrix of the positive neurons and the matrix of the negative neurons separately), and also give a convergence rate analysis; \n-  For ReLU networks they bound the stable ranks by a constant, which in some special cases can be roughly 2. They analyze the convergence rate also here.\n", "questions": "See the “weaknesses” section.", "limitations": "The authors discussed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think that it is a nice paper. The near-orthgonality assumption is quite strong, but I believe that it is a natural assumption, and that understanding the behavior of GD in this setting is helpful. For this reason, this assumption appears (either explicitly or implicitly) in several works in recent years.\n\nThis work extends the results from Frei et al. 2022b in several ways: \n- Frei et al. 2022b showed convergence to rank 1 of the matrices when using gradient flow and constant stable rank when using GD, and here it is extended to stable rank 1 using GD; \n- Frei et al. 2022b showed convergence to a constant stable rank when using GD with smooth leaky ReLU activation, and here it is extendedto leaky ReLU and to ReLU; \n- The convergence rate here is tighter than Frei et al. 2022b.\n\nI think that the question considered in the paper is interesting and the contribution is significant and non-trivial. Also, the paper is well-written.   ", "weaknesses": "I don’t see major weaknesses. Below I discuss some comments/questions that I have.\n\n- In the introduction the authors argue that “This finding suggests that ReLU networks possess superior learning ability compared to leaky ReLU networks”. I don’t see how this claim follows from the results. This sentence appears after mentioning the example where the stable rank becomes approximately 2 in ReLU networks, but this occurs also in leaky ReLU networks for this example. \n- Related to the above comment: Relating low stable rank to learning ability is not a trivial argument. While the exact rank can be used for bounding the complexity of the hypothesis class, this is not true in general for the stable rank. So I don’t see a direct argument that gives learning guarantees by only using the stable rank. (Still, I think that the stable rank is a natural notion and hence studying it is of interest).\n- The experiments on MNIST are conceptually similar to the experiments on CIFAR from Frei et al. 2022b. Please explain what is the contribution of this experiment compared to this prior work.\n- Typos:\n    - In Lemma 5.4 (line 215): should be $i,i’ \\in [n]$ instead of $r,r’ \\in [m]$.\n    - Line 286: “RelU”\n    - Line 759 (in Lemma F.2): \n        - In the first property should be $\\rho_{j,r,i}$\n        - The second property should be without the \\bar{}\n        - All conditions should consiter $w^{(0)}$ rather than $w^{(t)}$\n    - Last equation in page 42: should be $0_{m \\times(d-n)}$. Also in the equation before that.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and thoughtful comments! Below are our answers to your comments and questions.\n\n----\n\n**Q1**. In the introduction, the authors argue that “This finding suggests that ReLU networks possess superior learning ability compared to leaky ReLU networks”. This sentence appears after mentioning the example where the stable rank becomes approximately 2 in ReLU networks, but this occurs also in leaky ReLU networks for this example.\n\n**A1**. In the context of leaky ReLU networks, we prove that the stable rank of the weight matrix converges to 1 (rather than 2) when the data are nearly orthogonal. For ReLU networks, we provide an example concerning fully orthogonal data and prove that the stable rank of the weight matrix trained using such data converges to a value approximately equal to 2. Since the stable rank achieved by ReLU networks is larger than the stable rank achieved by leaky ReLU networks,  this suggests that ReLU networks possess superior learning ability than leaky ReLU.\n\n----\n\n**Q2**.  Relating low stable rank to learning ability is not a trivial argument. While the exact rank can be used for bounding the complexity of the hypothesis class, this is not true in general for the stable rank.\n\n**A2**. Thank you for raising this point. We agree that, in general, using stable rank to characterize the complexity of the hypothesis class needs a more careful argument. Yet in our results, the stable rank of leaky ReLU network is asymptotically 1, which means the exact rank equals to 1, and the stable rank of ReLU network is approximately 2 for learning completely orthogonal data, which means the rank is strictly greater than 1. So our argument about the learning ability of leaky ReLU vs ReLU still holds through the lens of exact rank.\n\n----\n\n**Q3**. Explain what is the contribution of this experiment compared to Frei et al. 2022b.\n\n**A3**. While our experiments on MNIST bear conceptual similarities to those of Frei et al. 2022b on CIFAR10, they offer additional insights:\n\n- We conducted our validation on the MNIST dataset, in addition to Frei et al.'s choice of CIFAR10. This allowed us to test the robustness of our findings across different datasets.\n\n- We presented visualizations of stable rank changes for both leaky ReLU and ReLU under various weight variances. In contrast, Frei et al. 2022b only visualized ReLU.\n\n- We provide additional experiments in Appendix I (Figures 4 and 5) to show how the stable rank of networks for both ReLU and leaky ReLU is influenced by network width. Our findings indicate that, for networks of adequate width, further increase in network width does not correlate with stable rank increments. Therefore, the stable rank emerges as an inherent characteristic of a specific learning problem, which is invariant in the network width.\n\nIn essence, our work not only supplements but also broadens the experimental scope initiated by Frei et al. 2022b, delivering a more comprehensive understanding of stable ranks across various settings. \n\n----\n\n**Q4**. Typos.\n\n**A4**. Thank you for pointing them out! We will fix them in the revision. \n"}]

Author rebuttal:
We want to thank all the reviewers for their positive and valuable feedback. In the uploaded pdf, we include additional empirical results to address reviewer c8EH’s concern. We have conducted experiments for long epochs (1000). We find that the stable rank for the leaky ReLU network with large slopes will converge to $1$. In comparison, the stable rank for the ReLU network will not converge to $1$.  We also conduct the experiments on the fully-orthogonal training data and find that the stable rank for the large-width ReLU network will converge to $2$ instead of $1$. The additional empirical findings strongly support our main Theorems 4.1 and 4.3. 

Meta-review: This paper studies the low-rank implicit bias of GD in two-layer ReLU and leaky ReLU networks in near-orthogonal data settings, strengthening a previous paper by Frei et al. The reviewers unanimously agree that this is a good paper, and therefore I recommend accepting it.

I suggest changing to a less broad title, such as including "low-rank" and "near-orthogonal."
Decision: Accept (poster)