Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data 
Authors: Spencer Frei
Gal Vardi
Peter Bartlett
Nathan Srebro
Wei Hu
Venue: ICLR 2023 notable top 25% (2023)
Keywords: implicit bias
gradient descent
gradient flow
neural networks

Abstract: The implicit biases of gradient-based optimization algorithms are conjectured to be a major factor in the success of modern deep learning.  In this work, we investigate the implicit bias of gradient flow and gradient descent in two-layer fully-connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal, a common property of high-dimensional data.  For gradient flow, we leverage recent work on the implicit bias for homogeneous neural networks to show that asymptotically, gradient flow produces a neural network with rank at most two.  Moreover, this network is an $\ell_2$-max-margin solution (in parameter space), and has a linear decision boundary that corresponds to an approximate-max-margin linear predictor.  For gradient descent, provided the random initialization variance is small enough, we show that a single step of gradient descent suffices to drastically reduce the rank of the network, and that the rank remains small throughout training.  We provide experiments which suggest that a small initialization scale is important for finding low-rank neural networks with gradient descent. 

Published as a conference paper at ICLR 2023
IMPLICIT BIAS IN LEAKY RELU NETWORKS TRAINED ON HIGH-DIMENSIONAL DATA
Spencer Frei'
Gal Vardi*
UC Berkeley
TTI Chicago and Hebrew University galvardi@ttic.ed.
frei@berkeley.edn
Peter L. Bartlett UC Berkeley and Google peterOberkeley.c edu
Nathan Srebro TTI Chicago
Wei Hu
University of Michigan vvhê edu
nati@ttic.edu
ABSTRACT
The implicit biases of gradient- optimization algorithms are conjectured be major factor in the success of modern deep learning. In this work, we inves- tigate the implicit bias of gradient flow and gradient descent in two-layer fully- connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal,, a common property of high-dimensional data. For gradi- ent flow, leverage recent work on the implicit bias for homogeneous neural networks to show that asymptotically, gradient flow produces a neural network with rank most two. Moreover, this network is fa-max-margin solution (in parameter space), and has linear decision boundary that corresponds to an peroximate-mmx-mmreee
linear predictor. For gradient descent, provided the ran- dom initialization variance is small enough, we show that a single step of gradient descent suffices to drastically reduce the rank of the network, and that the rank remains small throughout training. We provide experiments which suggest that a small initialization scale is important finding low-rank neural networks with gradient descent.
INTRODUCTION
Neural networks trained by gradient descent appear to generalize well in many settings, even when trained without explicit regularization. It is thus understood that the usage of gradient-bart based op- timization imposes an implicit bias towards particular solutions which enjoy favorable properties. The nature of this implicit regularization effect- and its dependence on the structure of the training data, the architecture of the network, and the particular gradient- optimization algorithm- thus central object of study in the theory of deep learning.
In this work, we examine the implicit bias gradient descent when the training data such that the pairwise correlations [,), between distinct samples x,, 2j Rd are much smaller than the squared Euclidean norms of each sample: that is, the samples are nearly-orthogonal. As we shall show, this property is often satisfied when the training data sampled i.i.d. from d-dimensional distribution and d is significantly larger than the number of samples n. We will thus refer to such training data with the descriptors "high-dimensional" and 'nearly-orthogonal interchangeably.
We consider fully-connected two-layer networks with m neurons where the first layer weights are trained and the second layer weights are fixed at their random initialization. If we denote the first- layer weights by W E Rimxd, with rows w E Rd then the network output is given by,
f(;; = aw,((
j 1, are fixed. We consider the implicit bias in two different settings: gradient flow, which corresponds to gradient descent where the step-size tends to zero, and standard gradient descent.
where aj E RR
"Equal contribution.

---

Published as a conference paper at ICLR 2023
For gradient flow, consider the standard leaky ReLU activation. 6(2) max(yz, 2). Our starting point in this setting is recent work by Lyu & Li ( Ji & Telgarsky (2020) that show that, provided the network interpolates the training data at some time, gradient flow on homogeneous networks, such as two-layer leaky ReI.U networks, converges (in direction) to a network that satisfies the
(KKT)) conditions for the margin-maximization problem,
min 1/2 [ W
S.t. Vi E [m], y6 (x4; W) 2 1.
Leveraging this, we show that the asymptotic limit of gradient flow produces a matrix W which is global optimum of the above problem, and has rank at most 2. Moreover, note that our assumption on the high-dimenssonnllty of the data implies that it is linearly separable. Our leaky W
ReLU network (-; W') is non-linear, but we show that gradient flow converges in direction such that the decision boundary is linear, namely, there exists 2 E IRd such that for all æ we have sign(f W)) = sign(= T=) 2). This linear predictor may not be an fg-max-margin linear predictor, but it maximizes the margin approximately (see details in Theorem 3.2)
For gradient descent, we consider smoothed approximation to the leaky ReLU activation, and consider training that starts from random initialization with small initialization variance. Our result for gradient flow on the standard leaky ReLU activation suggests that gradient descent with small- enough step size should eventually produce network for which W(() has small rank. However, the asymptotic characterization of trained neural networks in terms of KKT points of margin- maximization problem relies heavily upon the infinite-time limit. This leaves open what happens in finite time. Towards this end, we consider the stable rank of the weight matrix W(O) found by gradient descent at time t. defined as [|
I| |lP 11// the square of the ratio of the Frobenius
norm the spectral norm of W(t), We show that after the first step of gradient descent, the stable rank of the weight matrix W(( reduces from something that is of order min(m, d) to that which is at most an absolute constant, independent of m, d, or the number of samples. Further, throughout the training trajectory the stable rank of the network is never larger than some absolute constant.
We conclude by verifying our results with experiments. We first confirm our theoretical predictions for binary classification problems with high-dimensional data. We then consider the stable rank of two-layer networks trained by SGD for the CIFAR1O dataset, which is not high-dimensional. We notice that the scale of the initialization plays crucial role in the stable rank of the weights found by gradient descent: with default TensorFlow initialization, the stable rank of a network with m = 512 neurons never falls below 74, while with a smaller initialization variance, the stable rank quickly drops to 3.25, and only begins to increase above 10 when the network begins to overfit.
RELATED WORK
Implicit bias in neural networks. The literature on the implicit bias in neural networks has rapidly expanded in recent years, and cannot be reasonably surveyed here (see Vardi (2022) for a survey). In what follows, we discuss results which apply to two-layer ReLU or leaky ReLU net-
works in classification settings.
By Lyu & Li (2019) and Ji & Telgarsky 22200), homogeneous neural networks (and specifically two-layer leaky ReLU networks, which are the focus of this paper) trained with exponentially-taiien classification losses converge in direction to a KKT point of the maximum maximum-margin problem. Our analysis of the implicit bias relies on this result. We note that the aforementioned KKT point may not be a global optimum (see discussion in Section 3).
Lyu et al. (02T)) studied the implicit bias in two-layer leaky ReLU networks trained on linearly separable and symmetric data, and showed that gradient flow converges to linear classifier which maximizes the lg margin. Note that our work we do not assume that the data is symmetric, but we assume that it is nearly orthogonal. Also, in our case we show that gradient flow might converge to a linear classifier that does not maximize the & margin. /aarusii et al. (202T) studied gradient flow two-layer leaky ReLU networks, where the training data is lincarly separable. They showed convergence to a linear classifier based on an assumption called Neural Agreement Regime (NAR): starting from some time point, all positive neurons (i.e., neurons with positive outgoing weight) agree on the classification of the training data, and similarly for the negative neurons. However, it is unclear when this assumption holds a priori.
Chizat & Bach (020)) studied the dynamics of gradient flow on infinite-wide width homogeneous two- layer networks with exponentially-taiie losses, and showed bias towards margin maximization w.r.t.
2

---

Published as a conference paper at ICLR 2023
certain function norm known as the variation norm. Phuong & Lampert (020) studied the implicit bias in two-layer ReLU networks trained on orthogonally separable data (i.e., where for every pair of labeled examples (z,, 3t), (z), Mj) we have x 2; > 0 if y = Yj and x; 2 S 0 otherwise). Safran et al. (2022) proved implicit bias towards minimizing the number of linear regions in univariate two-layer ReL.U networks. Implicit bias in neural networks trained with nearly-orthogonal data was previously studied in Vardi et al. (2022). Their assumptions on the training data are similar to ours, but they consider ReLU networks and prove bias towards non-robust networks. Their results do not have any clear implications for our setting.
Implicit bias towards rank minimization was also studied in several other papers. Di Telgarsky (2018) (020) showed that in linear networks of output dimension 1, gradient flow with exponentially- tailed losses converges to networks where the weight matrix of every layer is of rank 1. [Timor et al.
2022)) showed that the bias towards margin maximization in homogeneous ReLU networks may
induce a certain bias towards rank minimization in the weight matrices of sufficiently deep ReLU networks. Finally, implicit bias towards rank minimization was also studied in regression settings.
See, e.g., Arora et al. (2019;; Razin & Cohen (2020); et al. (2020); Timor et al. (2022): ) Ergen &
Pilanci 202 2020)..
Training dynamics of neural networks for linearly separable training data. A series of works
have explored the training dynamics of gradient descent when the data is linearly separable (such
as is the case when the input dimension is larger than the number of samples, as we consider here). Brutzkus et al.] (2017) showed that in two-layer leaky ReLU networks. SGD on the hinge loss for linearly separable data converges to zero loss. |Fri et al. (02T) showed that even when a constant fraction of the training labels are corrupted by an adversary, in two-layer leaky ReLU networks, SGD on the logistic loss produces neural networks that have generalization error close to the label noise rate. As we mentioned above, both Lyu et al. (202T) and (arussi et al. (2021) considered two- layer leaky ReL.U networks trained by gradient-based methods on linearly separable datasets. [Wang] jet al.] (2019) and Yang et al. (202T) considered the dynamics of variants of GD/SGD algorithms on the hinge loss for ReLU networks for linearly separable distributions.
Another line of work has explored the dynamics of neural network training when the data is sampled i..dd from a distribution which is not linearly separable but the training data is linearly separable due to the number of samples being smaller than the input dimension. Cao et al. 2022) studied two-layer convolutional networks trained signal-to-noise ratio can result in harmful overfitting, while a high signal-to-noise ratio allows for good generalization performance. [Shen et al. (2022) considered a similar image-patel signal model and studied how data augmentation can improve generalization performance of two-layer convolu- tional networks. Frei et al. (2022a) showed that two-layer fully connected networks trained on high- dimensional mixture model data can exhibit a 'benign overfitting' phenomenon. Frei et al. (2022b) studied the feature- feature-learning process for two-layer ReLU networks trained on noisy 2-xor clustered data and showed that early-stopped networks can generalize well even in high-dimensional settings. Boursier et al.. (2022) studied the dynamics of gradient flow on the squared loss for two-layer ReLU networks with orthogonal inputs.
image-patei data model and showed how low
2 PRELIMINARIES
Notation. For a vector x we denote by ||ж||| the Euclidean norm. For a matrix W we denote
by || the Frobenius norm, and by ||W]| the spectral norm. We denote by 1 the indicator function, for example 1[t 2 5] equals 1 if 2 5 and ( otherwise. We denote sign 2) = 1 for > 0 and sign(z) = -1 otherwise. For an integer d 2 1 we denote [d] = (1....,dl d). We denote by N(J, 0²) the Gaussian distribution. We denote the maximum of two real numbers a, as V b, and their minimum as a b. We denote by log the logarithm with base e. We use the standard O(-) and ((-) notation to only hide universal constant factors, and use Ō() and f(() to hide logrrtogaii factors in the argument.
Neural networks. In this work we consider 2 neural networks, where the second layer is fixed and only the first layer is trained. Thus, neural network with parameters W is defined as f(x; W) = Σm a, z),
where x E ddd is an input, W E Rm second layer are oj E (+1/ 1mmmmm for j E [m]. and & R - IR is activation function. We focus on
dd is a weight matrix with rows wi ...., wT the weights in the
3

---

Published as a conference paper at ICLR 2023
the leaky ReLU activation function, defined by 6(2) max for some constant 7 (0, 1), and on a smooth approximation of leaky ReLU (defined later).
Gradient descent and gradient flow. Let S = {(r,, (())) S I x {+1} be a binary- classification training dataset. Let [(;; W) IRd - R be a neural network parameterized by W. For loss function é IR + IR the empirical loss of f(; W) the dataset $ is
L(W) = -/- Σm fay; WW)
We focus on the exponential loss E(q) = e and the logistic loss E(g) = log(1 + t
In gradient descent, we initialize [W( i.idd
N(O, for some Winit 2 O, and in each iteration
update
= = - -w
where a > is fixed step size.
Gradient flow captures the behavior of gradient descent with an infinitesimally small step size. The trajectory (1) of gradient flow defined such that starting from an initial point W W()), the dy- namics of W (t) obeys the differential equation dW = V (t).. When L(W) is non- de
differentiable, the dynamics gradient flow obeys the differential equation dW(t) E - (t)()), dt where 0 denotes the Clarke subdifferential, which is generalization of the derivative for non- differentiable functions (see Appendix A for a formal definition).
ASYMPTOTIC ANALYSIS OF THE IMPLICIT BIAS
In this section, we study the implicit bias of gradient flow in the limit / + co. Our results build on theorem by Lyu & Li (2019) and Ji & Telgarsky (020)) which considers the implicit bias in homogencous neural networks. Let f(r; () be a neural network parameterized by 0, where we view f as a vector. The network f homogeneous if there exists > such that for every > and x. we have f(x; (30) = 3 (a:; f). We say that trajectory ((t) of gradient flow converges in direction TØ-T Their theorem can stated as follows.
0 if lim;
8(t)
[0(E]
Theorem 3.1 (Paraphrased from Lyu & Li 2019;; Ji & Telgarsky (2020)). Let f be homogeneous ReLU or leaky ReLU neural network parameterized by 8. Consider minimizing either the exponen- tial or the logistic loss over binary classification dataset (x;, y1) } using gradient flow. Assume
that there exists time to such that [(((t)) < log(2) Then, gradient flow converges in direction to first order stationary point (KKT point) of the following maximum-margin problem in parameter space:
min 1/2 1101
s.r. Vi [n] yrf(2,;; 21.
Moreover, ī(((t)) 0 and [0()t]l + as + 0o.
We focus here on depth-2 leaky ReLU networks where the trained parameters the weight matrix W E Rmxd of the first layer. Such networks are homogeneous (with L = 1), and hence the above theorem guarantees that if there exists time to such that L(W (to)) < log(2), then gradient flow converges in direction to a KKT point of the problem
min 3/2 ||]]
S.t. Vie [n] f W) 2
Note that in leaky ReLU networks Problem (T) is non-smooth. Hence, the KKT conditions defined using the Clarke subdifferential. See Appendix A for more details the KKT conditions. The theorem implies that even though there might be many possible directions W that classify
the dataset correctly, gradient flow converges only to directions that are KKT points of Problem (T. We note that such KKT point is not necessarily a global/local optimum (cf. Vardi al. (2021); Lyu et al. (202T)). Thus, under the theorem's 's assumptions, gradient flow may not converge to an optimum of Problem (T), but it is guaranteed to converge KKT point.
4

---

Published as a conference paper at ICLR 2023
We state our main result for this section. For convenience, will use different notations for positive neurons (i.e., where a, = 1/ m/) and negative neurons (i.e., where = -1/ m/) Namely,
f(a:W) = E
ajol x) دزو vm d() دزو J vm d(u]a)
Note that m11 m2.. We assume that mi, m2 1.
Theorem 3.2. Let (i)) S Ra x { be a training dataset, and let Rmax == max; |
Ryin = min; ||:|||| and R Rmox/ Rmin-
We denote I = [n], I == {i E yi 1] and
I- EiEl = -1). Assume that
R 2 3r 3 R2 max (2 xz)1=
143
Let f be the leaky Rel.U network from (2) and let W be a KKT point of Problem 7 Then, the following hold:
1. y W) = for all i T.
2. = Uma == and =... Uyz == Hence, rank(W) 2
3. v 1 EiEl, ArT;
mm Eiel_ Ara and u = v Eiel_ ArT; Jim EvEL ArT
where d 2R 2
for every i E I. Furthermore, for all E I we have you x2 >
0 and you rg < 0.
4. W is a global optimum of Problem
7 Moreover, this global optimum is unique.
5. u, u is the global optimum of the following convex problem:
min 0
m1
||0|
m2
|1/1
(3)
2
m2
m2 u
Vi El4
U
2
Vm
Vm
Vi EI_
Vm
M2
ut T
-1
vm
m1
U 2 1.
6. Let z = MLL u.u. u. For every x. E Rd we have sign (f(x; W)) = sign(z Tx). Thus, the Vm Jm"
network [(;; has linear decision boundary.
7. The vector may not be la-max-margin linear predictor, but it maximizes the margin approximately in the following sense. For all E I we have y:z Et 2 1, and || I
K+7 ||="|| where ===-
2
min/my mm)] and =² == argmin; || s.I. y:ā xi 2 for all
max
i I.
Note that by the above theorem, the KKT points possess very strong properties: the weight matrix is of rank at most 2, there margin maximization in parameter space, in function space the predictor has linear decision boundary, there may not be margin maximization in predictor space, but the predictor maximizes the margin approximately within factor of * Note that
(i.e., m, = m2) and 7 is roughly 1, then we get margin maximization also in predictor space. We remark that variants of items 2, 5 and 6 were shown in Sarussi et al. (202T) under a different assumption called Neural Agreement Regime (as we discussed in the related work section)
The proof of Theorem 3.2 is given in Appendix B We now briefly discuss the proof idea. Since W satisfies the KKT conditions of Problem (1), then there are A1,...,AA ', such that for every j E [m] we have
w = Eier A w, (uif(as: = a, EiEr A.yro,.. Ti
where ,y,,, is subgradient of o at u. o;. Also have A; for all i, and X Off faz W) * 1. We prove strictly positive upper and lower bounds for each of the X, 's. Since the X, ' are strictly
In fact, the main challenge in proof is to show that a property similar to their assumption holds in every KKT point in setting.
5

---

Published as a conference paper at ICLR 2023
positive, the KKT conditions show that the margin constraints are satisfied with equalities, i..., part of the theorem. By leveraging these bounds on the A 's we also derive the remaining parts of the theorem.
The main assumption in Theorem 3.2 is that R 2 3y R2n max47) Tz)]- words, this means the squared norms of samples much larger than the pairwise correlations between different samples, i.e. the training data are nearly orthogonal. Lemma 3.3 below implies that if the inputs s; are drawn from a well-conditioned Gaussian distribution (e.g.. ((,, Ia)), then it suffices to require
). i.e., d 2 & (n²) if y 12(1). Lemma 3.3 holds more generally for class of subgaussian distributions (see, c.g,, Hu et al. (2020) Claim 3. 3.1)). D), and we state the result for Gaussians here for simplicity.
( V n
Lemma 3.3. Suppose that F1,-..,, In are drawn i...d from a d-dimensional Gaussian distribution N(O, E). where Tr[x]] d and |_||| 0(1). Suppose S <d0(1), Then, with probability at least
1 - n 10 we have |a,11 = + (V log n for all i, and Rer,,,) d
d = =(( logn) ) for all i i+ j-
The proof of Lemma 3.3 is provided in Appendix C We thus see that for data sampled i.i.d. from well-conditioned Gaussian, near-orthogonaliity of training data holds when the training data is sufficiently high-dimensional, i.e. the dimension is much larger than the number of samples.
By Theorem 3.2 the data points are nearly orthogonal then every KKT point of Problem (T) satisfies items 1-7 there. It leaves open the question of whether gradient flow converges to a KKT point. By Theorem 3.I, in order to prove convergence to KKT point, it suffices to show that there exists time to where (tu)) <
log(2) In the following theorem we show that such to exists, regardless of the initialization of gradient flow (the theorem holds both for the logistic and the exponential losses).
Theorem 3.4. Consider gradient flow the network from (2) assumption from Theorem 3.2 Then, there exists a finite time to such that for all 2 to we have (t) < log(2)/n.
w.r.t. a dataset that satisfies the
We prove the theorem in Appendix D Combining Theorems 3.1 3.2 and 3.4 we get the following:
Corollary 3.5. Consider gradient flow on the network from w.r.t dataset that satisfies the assumption from Theorem 3.2) Then, gradient flow converges to zero loss, and converges in direction to weight matrix W that satisfies items 1-7 from Theorem 3.2
NON-ASYMPTOTH ANALYSIS OF THE IMPLICIT BIAS
In this section, we study the implicit bias of gradient descent with fixed step size following random initialization (refer to Section 2 for the definition of gradient descent). Our results in this section are for the logistic loss {(2)
log(1 + exp(-2)) but could be extended to the exponential loss
as well. We shall assume the activation function ø satisfies x(0) = 0 and is twice differentiable
and there exist constants y E (0, 1), H > such that < y S 6'(z) < 1, and (0" I H. We shall refer to functions satisfying the above properties as 7-leaky, H H-smooth. Note that such functions are not necessarily homogeneous. Examples of such functions are any smoothed approximation to the leaky ReI.U that is zero at the origin. One such example is: 6(2) = 72 +
(1 7) log (1(1 + exp(z))). which is 7-leaky and 1/1-smooth (see Figure in the appendix for side-by-side plot of this activation with the standard leaky ReLU).
We next introduce the definition of stable rank (Rudelson & Vershynin 2007 Definition 4.1. The stable rank of matrix W R.mad is StableRank W) |W] [W]2
The stable rank is in many ways analogous to the classical rank of matrix but is considerably more well-behaved. For instance, consider the diagonal matrix W E 12dx with diagonal entries equal to 1 except for the first entry which is equal to E 2 0. As s - O, the classical rank of the matrix equal to d until exactly equals 0, while on the other hand the stable rank smoothly decreases from to d 1. For another example, suppose again W E dxd is diagonal with Wi,1 = 1 and W., cxp(-d) for 2 2. The classical rank of this matrix is exactly equal d, while the stable rank of this matrix is 1 + o1(.)
With the above conditions in hand, we can state our main theorem for this section.

---

Published as a conference paper at ICLR 2023
Theorem 4.2. Suppose that Φ is a 7y-eeayy H-smooth activation. For training data {(z,, V4) y:) Fim1 C Rd x {+1), let Raax max; || and Rynin min; ||a||, and suppose R = Rmmx/ Rmin is at most an absolute constant. Denote by Cr = 10R²/72 10. Assume the training data satisfies,
R 2 57 B max (x,,,)))- (f
There exist absolute constants C1, C2 > (independent of m. d, and n) such that the following holds. For any d E (0,1), if the step-size satisfies S (5n R²C max(1, H))- and Winit S <ry² Rmin (72RC /ndo//ddooo log( (4m,/8) then with probability at least 1 1-8 over the random initialization of gradient descent, the trained network satisfies:
1. The empirical risk under the logistic loss satisfies L(W(0) S v Cini/ for b 1.
2. The l2 norm of each neuron grows to infinity: for all j. [10] |lu 00. cc.
3. The stable rank of the weights bounded: sup (tta S C2.
We now make a few remarks the above theorem. We note that the assumption the training data is the same as in Theorem 3.2 up to constants (treating 7 as a constant), and is satisfied in many settings when d >> n²² (see Lemma 3.3).
For the first part of the theorem, we show that despite the non-convexity of the underlying optimiza- tion problem. gradient descent can efficiently minimize the training error, driving the empirical risk to zero.
For the second part of the theorem, note that since the empirical risk under the logistic loss driven to zero and the logistic loss is decreasing and satisfies {(z) > 0 for all 2, it is necessarily the case (Otherwise, ((W(()) would be bounded from below by a constant.) This leaves open the question of whether only a few neurons in the network responsible for the growth of the magnitude of the spectral norm, and part (2) of the theorem resolves this question.
that the spectral norm of the first layer weights [ [|2
The third part of the theorem is perhaps the most interesting one. In Theorem 3.2 we showed that for the standard leaky ReLU activation trained on nearly-orthogonal data with gradient flow, the asymptotic true rank of the network is most 2. By contrast, Theorem 4.2 shows that the stable rank of neural networks with 7-leaky, H-smooth activations trained by gradient descent have constant stable rank after the first step of gradient descent and the rank remains bounded by constant throughout the trajectory. Note that at initialization, by standard concentration bounds for random matrices (see, e.g., Vershynin (2010)) the stable rank satisfies StableRank(N (W)(a)) s ((md/ty/ttaii vm++v))) [m Ad), that Theorem 4.2 implies that gradient descent drastically reduces the rank of the matrix after just one step.
The details for the proof of Theorem 4.2 are provided in Appendix E. but we provide some of the main ideas for the proofs of part and 3 of the theorem here. For the first part, note that training data satisfying the assumptions in the theorem are linearly separable with a large margin (take, for instance, the vector 2im1 i= (:R.). We use this to establish a proxy Lojaaia-o (PL) inequality (Frei & Gu 2021) that takes the form |VĪ(((() 2 c.(W())) for some c 0, where G(W(e)) is the empirical risk under the sigmoid loss -f((2) = 1/(1 + cxp(2)). Because consider smoothed leaky ReLU activations, we can use smoothness based analysis of gradient descent to show [[ - which implies G(W(t)) + 0 by the proxy PL inequality. We then translate guarantees for G(W()) into guarantees for ((W()) by comparing the sigmoid and logistic losses.
For the third part of the theorem, we need to establish two things: (i) an upper bound for the Frobenius norm, and (ii) lower bound for the spectral norm. A loose approach for bounding the Frobenius norm via an application of the triangle inequality (over time steps) results in a stable rank bound that grows with the number of samples. To develop tighter upper bound, we first establish a structural condition we refer to as a loss ratio bound (see Lemma E.4). In the gradient descent updates, each sample is weighted by a quantity that scales with -I' (fff(x; W(O)) e (0, 1). We show that these - ll losses grow at approximately the same rate for each sample throughout training.
7

---

Published as a conference paper at ICLR 2023
Relative Rank Dimensionn in
Relativ Rank Inibalizztion Saale
veletive to intiellcsion
1.00
rank relatvee to intlabbation
1.00
0.75
GD ttpps
0.75
GD Steps
1
0.50
0.50
10
300
0.25
300
0.25
53060
0.00
0.00
3e403
1e404
3e404
1e405
0.01
0.10
1.00 10.00
dimension
initaaization scale (mulliple tensorflow default)
Figure 1: Relative reduction in the stable rank of two-layer nets trained by gradient descent for Gaussian mixture model data (ef. (4)). The rank reduction happens more quickly as the dimension grows (left; initialization scale 50x smaller than default TensorFlow, a = 0.01) and as the initial- ization scale decreases (right; d = 10 0.16).
and that this allows for a tighter upper bound for the Frobenius norm. Loss ratio bounds were key to the generalization analysis of two previous works on benign overfitting (Chatterji & Long 2021: Frei al. 2022a) and may be of independent interest. In Proposition E.10 provide a general approach for proving loss ratio bounds that can hold for more general settings than the ones we consider in this work (i.e., data which are not high-dimensional, and networks with non-leaky activations). The lower bound on the spectral norm follows by identifying a single direction jr :===) ==>= y: that is strongly correlated with every neuron's weight wy. in the sense that /Itf"" II, ( is relatively large for each j E [m]] Since every neuron is strongly correlated with this direction, this allows for good lower bound on the spectral norm.
IMPLICATIONS OF THE IMPLICIT BIAS AND EMPIRICAL OBSERVATIONS
The results in the preceding sections show remarkable simplicity bias of gradient- based optimiza- tion when training two-layer networks with leaky activations on sufficiently high-dimensional data. For gradient flow, regardless of the initialization, the learned network has a linear decision bound- ary, even when the labels y some nonlinear function of the input features and when the network has the capacity to approximate any continuous function. With our analysis of gradient descent, showed that the bias towards producing low-complexity networks (as measured by the stable rank of the network) is something that occurs quickly following random initialization, provided the initialization scale is small enough.
In some distributional settings, this bias towards rather simple classifiers may be beneficial, while in others it may be harmful. To where it may be beneficial, consider Gaussian mixture model dis- tribution P. parameterized by a mean vector fa E Red, where samples (xr, y) ~ P have a distribution as follows:
Uniform((+1)), I/y ~ yu ~~ N(O, La).
(4)
The linear classifier x + sign((uu x)) performs optimally for this distribution, and so the implicit bias of gradient descent towards low-rank classifiers (and of gradient flow towards linear decision boundaries) for high-dimensional data could in principle be helpful for allowing neural networks trained on such data to generalize well for this distribution. Indeed, as shown by Chatterji Long 2201)) since || s + || while (Iz, x,حح x ||a|| + vd for + j. provided |||||| ((d)) and d >> n- Vn² for 3 E 1/2), the assumptions in Theorem 4.2 hold. Thus, gradient descent on two-layer networks with 7-leaky, H-smooth activations, the empirical risk is driven to zero and the stable rank of the network is constant after the first step of gradient descent. In this setting, [Feii jet al.) (2022a) recently showed that such networks have small generalization error. This shows that the implicit bias towards classifiers with constant rank be beneficial in distributional settings where linear classifiers can perform well.
On the other hand, the same implicit bias can be harmful if the training data come from distribution that does not align with this bias. Consider the noisy 2-xor distribution Dxor in 2 3 dimensions defined by
2 2 { where norms, & ~ N(O, I,), and = sign( test error Dxor- Moreover, provided ||m]] (d))) for 3 < 1/2 by the same reasoning in the
Uniform( (#/11
). where #1, A2 orthogonal with identical
(P2, x ). Then every linear classifier achieves 50%
8

---

Published as a conference paper at ICLR 2023
defsuit Int.
small Int.
1.000
-0755
stablerank
0.50
train, acc
300
-.25
0- 20401 1e403 Ie405
0.00
Ie-03 3e403
1e405
step
Figure 2: Stable rank of SGD-trained two-layer ReI.U networks on CIFAR-10. Compared to the default TensorFlow initialization (left), smaller initialization (right) results a smaller stable rank, and this effect is especially pronounced before the very late stages of training, Remarkably, the train (blue) and test (black) accuracy behavior is essentially the same.
preceding paragraph the assumptions needed for Theorem 3.2 are satisfied provided d >>>>> 20 Vn In this setting, regardless of the initialization, by Theorem [.2] the limit of gradient flow produces neural network which has a linear decision boundary and thus achieves 50% test error. In the appendix (see Fig. 6) we verify this with experiments.
Thus, the implicit bias can be beneficial in some settings and harmful in others. Theorem and Lemma 3.3 suggest that the relationship between the input dimension and the number of samples, as well the initialization variance, networks. In Figure [ we examine these factors for two-layer nets trained on a Gaussian mixture model distribution (see Appendix for experimental details). We see that the bias towards rank reduction increases as the dimension increases and the initialization scale decreases, as suggested by our theory. Moreover, appears that the initialization scale more influential for determining the rank reduction than training gradient descent for longer. In Appendix F we provide more detailed empirical investigations into this phenomenon.
influence how quickly gradient descent finds low-rank
In Figure we investigate whether or not the initialization scale's effect on the rank reduction of gradient descent occurs in settings not covered by our theory, namely two-layer ReLU networks with bias terms trained by SGD on CIFAR-10. We consider two different initialization schemes: (1) Glorot uniform, the default TensorFlow initialization scheme with standard deviation of order 1/vm + d, and (2) uniform initialization scheme with 50x smaller standard deviation than that of the Glorot uniform initialization. In the default initialization scheme, it appears that a reduction in the rank of the network only comes in the late stages of training, and the smallest stable rank achieved by the network within 106 steps is 74.0. On the other hand, with the smaller initialization scheme, the rank reduction comes rapidly, and the smallest stable rank achieved by the network is 3.25. It is also interesting to note that in the small initialization setting, after gradient descent rapidly produces low-rank weights, the rank of the trained network begins to increase only when the gap between the train and test accuracy begin to diverge.
CONCLUSION
In this work, we characterized the implicit bias common gradient-based optimization algorithms for two-layer leaky ReLU networks when trained on high-dimensional datasets. For both gradient flow and gradient descent, we proved convergence to near-zero training loss and that there is an implicit bias towards low-rank networks. For gradient flow, we showed number of additional implicit biases: the weights are (unique) global maxima of the associated margin maximization problem, and the decision boundary of the learned network linear. For gradient descent, we provided experimental evidence which suggests that small initialization variance is important for gradient descent's s ability to quickly produce low-rank networks.
There are many natural directions to pursue following this work. One question is whether or not similar implicit bias towards low-rank weights in fully connected networks exists for networks with different activation functions or for data which is not nearly orthogonal. Our proofs relied heavily upon the oethoorthygynality of the data, and the 'leaky' behavior of the leaky ReLU, namely that there is some y > 0 such that d'(2) 2 y for all 2 R. We conjecture that some of the properties showed Theorem 3.2 (c.g., a linear decision boundary) may not hold for non-leaky activations, like the ReL.U, without the near-orthogonality assumption.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We thank Matus Telgarsky for helpful discussions. This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing as part of the Deep Learning Theory Summer Cluster. SF, GV, PB, and NS acknowledge the support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards MAS-2231883 and #8 14639.
REFERENCES
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances Neural Information Processing Systems, pp. 7413-7424, 2019.
Etienne Boursier, Loucas Pillaud- Vivien, and Nicolas Flammarion. Gradient flow dynamics of shal- low relu networks for square loss and orthogonal inputs. Preprint, vrXiv:2206.009333 2022.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd lears over- parameterized networks that provably generalize on linearly separable data. arXiv preprint arXiv: 10174, 2017.
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer con- volutional neural networks. Preprint, arXiv:2202.066 065266, 2022.
Niladri S. Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129)) 2021.
Lenaic Chizat and Francis Bach. Implicit bias gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04488 2020.
Francis H Clarke, Yuri Ledyaev, Ronald Stern, and Peter Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008.
Joydeep Dutta, Kalyanmoy Deh, Rupesh Tulshyan, and Ramnik Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, 56(4): 1460))19399999 2013.
Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. In International Conference on Artificial Intelligence and Statistics, pp. 4024-4033. PMLR, 2020.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference on Machine Learning, pp. 3004-3014, PMLR, 2021.
Spencer Frei and Quanquan Gu. Proxy convexity: A unified framework for the analysis of neural networks trained by gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Spencer Frei, Yuan Cao, and Quanquan Gu. Provable generalization of SGD-trained neural networks of any width in the presence of adversarial label noise. In International Conference Machine Learning (ICML), 2021.
Spencer Frei, Niladri S. Chatterji, and Peter L. Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory (COLT), 2022a.
Spencer Frei, Niladri S. Chatterji, and Peter L. Bartlett. Random feature amplification: Feature learning and generalization in neural networks. Preprint, arXiv:2202.2202.07666 2022b.
Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplicity of the early- time learning dynamics of neural networks. Advances in Neural Information Processing Systems, 33:17116-17128. 2020.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: 088..000.3 2018
10

---

Published as a conference paper at ICLR 2023
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006.06655) 2020.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):1302-1335 2000.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning, arXiv preprint arXiv:20/2.09839, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 1X06:1906055800 2019.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 1111278--19991 2021.
Mary Phuong and Christoph H Lampert. The inductive bias of relu networks on orthogonally sepa- rable data. International Conference on Learning Representations, 2020.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. arXiv preprint (xXx::005500636 2020.
Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through geo- metric functional analysis. Journal of the ACM (JACM), 54(4):21-es, 2007.
Mark Rudelson and Roman Vershynin. -angon-wright inequality and sub sobb-gaussian concentration. Electronic Communications Probability, 18:1-9, 2013.
Itay Safran, Gal Vardi, and Jason D Lee. On the effective number of linear regions in shallow univari- ate relu networks: Convergence guarantees and implicit bias. arXiv preprint arXiv:2205.09072, 2022.
Roei Sarussi, Alon Brutzkus, and Amir Globerson. Towards understanding learning in neural net- works with linear teachers. In International Conference Machine Learning, pp. 9313-9322. PMLR, 2021.
Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipulation: story of desert cows and grass cows. In International Conference on Machine Learning (ICML), 2022.
Nadav Timor, Gal Vardi, and Ohad Shamir. Implicit regularization towards rank minimization in relu networks. arXiv preprint arXiv:2201. 2022.
Gal Vardi. On the implicit bias in deep-lcarning algorithms. arXiv preprint arXiv:2208. 12591, 2022.
Gal Vardi, Ohad Shamir, and Nathan Srebro. On margin maximization in linear and relu networks. arXiv preprint arXiv:2 10.00732, 2021.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. Gradient methods provably converge to non-robust networks. arXiv preprint arXi::2202.04344 2022.
Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. arXiv preprint, 10Xiv:1011.3022 2010.
Gang Wang, Georgios B. Giannakis, and Jie Chen. Learning ReLU networks on linearly separable data: Algorithm, optimality, and generalization. IEEE Transactions on Signal Processing, 67(9): 2357-2370, 2019.
Qiuling Yang. Alireza Sadeghi, Gang Wang, and Jian Sun. Learning two-layer relu networks is nearly as easy as learning linear classifiers on separable data. IEEE Transactions on Signal Pro- cessing, 69:4416 4427, 2021.
11

---

Published as a conference paper at ICLR 2023
CONTENTS
Introduction
Preliminaries
Asymptotic Analysis of the Implicit Bias
4
Non-Asymptotic Analysis of the Implicit Bias
5
Implications of the Implicit Bias and Empirical Observations
Conclusion
Preliminaries the Clarke Subdifferential and the KKT Conditions
12
B
Proof of Theorem
13
Proof of Lemma 3.3
21
Proof of Theorem 3.4
22
Proof of Theorem
24
Concentration for random initial ization
24
Smoothness of network output and loss
25
Loss ratio bound
25
Upper bound for the Frobenius norm
35
E.5
Lower bound for the spectral norm
37
E,6
Proxy PL inequality
39
Proof of Theorem 4.2
40
Experiment Details
42
Binary cluster data
42
CIFARTO
A PRELIMINARIES ON THE CLARKE SUBDIFFERENTIAL AND THE KKT CONDITIONS
Below review the definition of the KKT conditions for non-smooth optimization problems (cf.
Lyu Li 2019 Dutta et al. (2013)).
Let Rd R be locally Lipschitz function. The Clarke subdifferential (Clarke et al. 2008
x E Rd is the convex set
8 f()()) conv lim fxx) lim n; x, f is differentiable at x; ++000
(1-000
f is continuously differentiable at then 0 f(x) = (Vf(z). For the Clarke subdifferential the chain rule holds as an inclusion rather than equation. That is, for locally Lipschitz functions
12

---

Published as a conference paper at ICLR 2023
2n 2
R - IR and f R - R, have
( o (x) C conv Σ osly a E (1.,)(()).........) hs E =02(00)
Consider the following optimization problem
min f(x s.t. Vn E [N] (n( 00,
(5)
where f. 9.91...... . In Rd + R are locally Lipschitz functions. We say that x E R is a feasible point of Problem (5) point if there exists .p....,,, 2 0 such that
if x satisfies gn (2) for all [N.. We say that a feasible point is KKT
1. 0 E D f(x) + EnEiN An (z));
2. For all n E [M] we have (x) 0.
B PROOF OF THEOREM 3.2
We start with some notations. We denote p maxişi (zy, Thus, our assumption can be written as < 73 R Re Since W satisfies the KKT conditions of Problem (1), then there are A1,..., An such that for every j [ma] we have
R
V/ = Σ N. (uff(x;;W))
Exerodan vm RET
(6)
IET
where o',,,, is a subgradient of á at 12 xv. i... if vJ > then H.,y = 1, if of x, < 0 then Ki,,, 7 and otherwise K',,, is some value in (7, 1]. Also we have x, 0 for all i, and X 0 if yif( W) 1. Likewise, for [mg] we have
A., W))
Σ I(-wii)hh.,
"j
Vm RE1
VEI
where d,,,, is defined similarly de,,, The proof of the theorem follows from the following lemmas.
Lemma B.1. For all E we have Eje(m,) d:th.o, + EjE(mo) Aethin < A < 2R for all i T.
3m 2 R2
Furthermore,
Proof. Let & = max,el (Eye Ago + EjE(ma) )p and suppose that 2
3m Let
2 R
r argmax (Eeeim)) 2 + Ese(ma) Aqo
Since & 2
3m 2y
> 0 then A, > 0, and
hence by the KKT conditions we must have yr (xx; W) We consider cases:
13

---

Published as a conference paper at ICLR 2023
Case 1: Assume that r I_. Using (6) and
we have
(zr W)=
E
o(u x4)
Σ
olu xr)
je[mil
JE[ma)
(|m
Σ je[ml]
Agyly 1. fi ttr
E
Σ
\x0 yo Vo)
mm
vm
9ET
jElmal
Σ δ jE(ma]
1 Vm
Ar
Fe 2r D'
T
1
Σ
Xada Rig 2r
Vm gET(()
Σ
(r +
Σ
vm
sE[ma]
ge\((r
Σ Φ jE[ml]
Xr
R2 +
Σ
NoWoy Fig 2
Vml
Vm (ET((r)
Σ Φ
dr
R² N
Σ qEr((r)
(p 11-yy) Fig Fr
vm
mm
je/mal
Since the derivative of is lower bounded by y know Φ(21) 6(22) 2 7(21 22) for all
21, 72 E R. Using this and the definition of g, the above is at most
Σ
Σ gEN(r)
Naya 25 2
)
vm
1 y
y.
R2
m
je [m)]
Σ
Σ
Ay yu
+
Vm ? Ar
1
R2
je(mal
(ET((r)
RR min
Σ
Σ
Agygyh a Tr
Σ
V
JE[mg]
vm
ge/\(r)
jE|mal
vm (Er((r)
78 R2
Σ
Σ
XaVg n.n, o0 N
Σ
Σ
(a(-ya)
V m
min
m
mm
/E(ma]
(E))(r)
JE(mal QET((r)
Using
|x] xrl S for q # r, the above most
mm
R
min
+
v
Σ
Σ
vm jE[mal gE/
Σ
Σ
5e[mil
geZ
1 min
R2
p
Σ
Ayo G 9:
+
Ayo qun
m
m
qEr((r)
jEmmll
jE(mal
<
75 min
E2
+
p
|7|
max GEl
Xyo
+
mm
Vm
JEmmll
JE(ma]
3
R2
p
ng
g
(y RT
np)
Vm
vm
Vm
14

---

Published as a conference paper at ICLR 2023
By our assumption n, can bound the above expression by
3
R
R
E
7
R
min
min
vm
p
3
P
Vm
3
R2
& ERe
Y
?
vm
3
2
m
3
3m
R
2y
2 min
mm
3
m
Thus, obtain f(r;; W) -1 in contradiction to yr (zr; W) = 1.
Case Assume that r E L+. A similar calculation to the one given in case (which we do
repeat for conciseness) implies that [0, () > 1, in contradiction y- W) 1. concludes the proof of & < 2-y
3m
Finally, since & <
3m Ry
and the derivative of & is lower bounded by 7, then for all i E / we have
3m 2 R2 min
Σ
Σ
Xr md,r,
fE(mi]
jE[ma]
and hence \
Ry mm
Lemma B.2. For all i E I we have Eje(m)) Xeth. + Eje(ma) Aech > A 212 for
m
Furthermore,
TR
Proof. Suppose that there i E such that E Eje(ms) A:oh., + E Eje(ma) Aioh.ng
S
m
Using (6)
28
and 7 we have
m & [Vmf(eRW]l
Σ
ouu xx)
Σ
plu} xx)
1 Σ
10 xzs +
Σ
|uJaz xz
JE(mll
fE(mz)
JE(mLl
3E /E(mal
Σ
NaWhyhnn xrj Jac
Σ
Na ) 2ey 062
Vm
Vm
jE(ml]
GEl
jE 3E(ma)
gET
[Merroh 2 xT
Σ
Σ
m
jE(mi]
Σ
[
Σ
2e) 2 mrdr
jE(mal
(
15

---

Published as a conference paper at ICLR 2023
Using [2 z4l I p for q # and 2 24
S R the above is at most
Aedi F +
E ren())
Σ
R +
Σ
mm
m
jE(mas]
jE(ma)
nEN(()
Xedy
Ry
X
Ryas
Σ
Σ
g
mm
VmI
je(mal
je mm(ma]
PET((1)
jE(mi]
jE(m²]
R max
+
Σ
Ag
X
v m
m
/E/mll
jE[ma]
gEA((*)
jE(mal
R2 max
m
P
max |1|
Σ
Ag
+
vm
2R max
gEt
jElmJ]
JE[mal
Combining the above with our assumption n, get
max gET
Σ
Ag
g.05
+
A
g,
2np
m
2p
172
7 12
3p
R2
R
max
2
3m
jE[ma]
jE[ma]
in contradiction Lemma B.1 concludes the proof of Σje(m Xool + EjE(mal Aeok.
m
2R
Finally, since Eje(m)) Aed + jmma A.0% by 1, then for all we have
and the derivative of is upper bounded
21
m
Aooh.y + Σ
rookin S mms.
2R2
max
JE[mJ]
jE(ma)
and hence X; >
2
Lemma B.3. For all i I have (z W)
Proof. By Lemma B.2 we have x; 0 for all i E I, and hence by the KKT conditions must have yif(x; W) =1.
Lemma B.4. We have
Um
Σ
Σ
Asa
mm
Vm
iel+
EEL_
and
Umm
Σ
Aat
m
TE!
SET.
Moreover, for all i E I we have: you xi
> 0 for every j E [mi]] and you. xs < 0 for every
j E [m2].
Proof. Fix j E [m]]. (6 for all i I4 we have
AyHay' 9. 2.
yEl
Σ
2 Li +
mm
1,0y
Vm
ger((()
A i,
R2
1
Σ
Agoy
V m
Vm
QEI
16

---

Published as a conference paper at ICLR 2023
By Lemma B.1 and Lemma B.2 and using o Syy,, E 17, 1] for all g I, the above is larger than
Vm 2 2
7 R
vm
24 R
3
p
2/mR
7R2
vm
7
3
R
min
p
R
R
min
2 2 R
3
P
RR
0.
2
2/mReaa
Thus, 2/ 24 > O, which implies dayy Similarly, for all i I_ we have
1/ xi
1 vm gEl
E
xet
E
vm
gETVE
Ao
A
R min
Σ
VETVE)
By Lemma B.1 and Lemma B.2 and using d2,,, E [7,, 1] for all q I, the above is smaller than
RRe min
7a
R2
R2
3
Vm 2R y R
m n
27 22
min
Ps 2/mR
vm
3
min
R2
min
2y² R2
min
712
7122
0.
2
2 R2
Thus, 0/ 24 O, which implies d',,, =
Using again we conclude that
Dj
m VE!
Vm sEl+
Σ
mm
Σ
Apti
IE7
Since the above expression holds for all j E [mi] then we have 01 Umi
By similar arguments (which do not repeat for conciseness) also get
Ummz
A5T:
Σ
AaT
m
RE
ET
and youeer vi < 0 for all E and E [m2)].
By the above lemma, we may denote v 2
Umg and
Umz. and denote
ma
m2 u.
Vm
Vm
Lemma B.S. The pair v, unique global optimum of the Problem
Proof. First, remark that variant of the this lemma appears in Sarussi al. (021). They proved the claim under an assumption called Neural Agreement Regime (NAR), and Lemma B.4 limlics that this assumption holds in our setting.
Note that the objective in Problem is strictly convex and the constraints are affine. Hence, its KKT conditions are sufficient for global optimality, and the global optimum is unique. It remains to show that v, satisfy the KKT conditions.
Firstly, note that v, satisfy the constraints. Indeed, by Lemma B.4 for every i I+ have v. x; > 0 and u' x; < O. Combining it with Lemma B.3 we get
mi
m2 olu T x.)
mi m
m2
= f(1;; W)
0(v xx)
(8)
mm
17

---

Published as a conference paper at ICLR 2023
Similarly, for every i I- have 2 x; < 0 and u x4 15>>0 0. Together with Lemma B.3 we get
-1 -1 s(;; ());
m1 mm
60 xz)
vm
m2
(bu x3))
vm
m1
2i
v m
7122
(9)
Next, we need to show that there are Mly...
2 such that
ma
Σ SEL+
Mi
m1
Ui +
Σ
Ui
(i(-7
mi
ri)
m
Vm
IEL_
m2
Σ
Ma pa(-7
m2
v;)) +
m2 .ET_
Σ
14
R4 m
Vm
1E
By setting 14 X; for all i E I, Lemma B.4 implies that the above equations hold.
Finally, we need to show that μ4 = for all i E where the corresponding constraint holds with a strict inequality. However, by (8) and (
all constraints hold with an equality.
Lemma B.6. The weight matrix W is a unique global optimum of Problem
Proof. Let W be weight matrix that satisfies the KKT conditions of Problem ().. and let U1...., Umg ui,...y Umg be the corresponding positive and negative weight vectors. We first show that W = W, i.e. there is unique KKT point for Problem D Indeed, by Lemma B 4 for every such W we have ig = = Lmm := Ü and ύj i, are a unique global optimum of Problem (3). Since by Lemma [B.5] the vectors U, v are also unique global optimum of Problem B then we must have
Um == ü, and by Lemma B.5 the vectors
and û.
Now, let W be global optimum of Problem I By Lyu Li (2019), the KKT conditions of this problem are necessary for optimality, and hence they are satisfied by W*. Therefore, we have W W. Thus, W a unique global optimum.
Lemma B.7. For every x E R.d we have sign (f(:; W)) sign(2Tx))
Proof. First, We remark that variant of the this lemma appears in Sarussi al. (2021) They proved the claim under an assumption called Neural Agreement Regime (NAR), and Lemma B. 4 4implies that this assumption holds in our setting.
Let o E Rdd, Consider the following cases:
Case 1: If uT 2 0 and u Tu 2 0 then ((;
122
2 ZTx, and thus ma u x vm
/mm
sign (f; W)) si x). (x).
Case If TTx x 2 and u Tr < then f(x; W)
m.
Jr.
me vm
yuu TT.Tx x
and TT
vm
mi Vm
T
m2
0.
vm
Case 3: If v x < 0 and u then f(z;
my
yo
u
0 and 2Tx
vm
vmm
mi
m2 u² 0. vm
V
Case 4: If TTTa x < and TT x < then f(x:W)
my Vmm
m2 vm
yu T = 72 x, and thus
sign (z; W)) s2 z).
Lemma B.S. The vector z may not be an ma-max-margin linear predictor.
Proof. We give example of setting that satisfies the theorem's 's assumptions, but the correspond- ing vector 2 is not an ma-max-margin linear predictor. Let ς = 1/2 and suppose that mi = m == m'. Let = (-1, 0, T)TTO.T.T T 42 = (e, vI == and æ 0, 0, T) where e > 0 is sufficiently small such that the theorem's 's assumption holds. Namely, since we need n S 3 p Thi
12 I² and we have
Rmin = Ru and = c, then e should satisfy 3 < 8.3r- We also let y1 = - 1/2 = -ys = 1. Let W be a KKT point of Problem [1) w.r.t. the dataset (zx.8:) 1= and let U1, Umi, U1 Um be the corresponding weight vectors. By Lemma B.4 and Lemma B.5 we have
... Umm
18

---

Published as a conference paper at ICLR 2023
and W1 Lemma B.2
Umz where v, solution of Problem
33. Moreover, by Lemma B.4 and
we have
1
(Agag + A303 - -11111) =
+ A323
2 \121
(10)
/2m
72m
u
(AII1 71222 - >A333)
1
A1
1
A222
(11)
22
22m
where X O for all Since 21, 22, By are linearly independent, then given v, u there is a unique choice of λ1 A2, Ag that satisfy the above equations.
Since v, u satisfy the KKT conditions Problem 3). we can find )1, A2, A as follows. Let
μ1, M2: M3 2 be such that the KKT conditions of Problem hold. From the stationarity dition we have
m
m'
m' 714
m' u
p2
22m D2
+
22m
v 22m
m
m
m' a 141
22m 11
71222
D2
7/133
v 2m' E3
/2m
Since T1, 32 Fy are linearly independent, combining the above with (10) and (TT) implies μ4
A > 0 for all i. Therefore, all constraints in Problem 33 must hold with an equality. Namely, we have
v 2m
T
1 T
5"¹
1
1
2 \1221 ]] I
1
A
A2
A232
+ A3333
v 2m
2
2
2
5
A2222 - A313
- \1 .1 A2(-E) - 2s -2.00)
/2m'
1
/2m
4
5
A1 + )xe))
22m'
4
22m
1
11
=u
F2
m!
2
1
1
1
1
1
)333 )( 42
A232 + A3333
A1
\a
A2
2'
2
2
2
1
5.
(5
A2ar2
21101
T2
A2
0
A1(-e))
22m'
2m
4
1
X2 A1c
/2m'
and
v 22m
1 T
22m' (5 X2 + 23233 11
1 5
1
13
As
m'
2
/2m
4
Solving the above equations, get \1 >22 1 and Ag 8.
19

---

Published as a conference paper at ICLR 2023
Thus, KKT point of Problem
must satisfy (10) and
11
with the above X'ss s. Now, consider
m'
m'
m
2
u
(o
u)
V2m
22m'
2m
m'
Σ
7 Σ
Σ iET
A,2; +7 Σ
22m
2m'
iEl1
IET
iET1
1+7 Y
Σ
Σ
Xi2ii
2
IEL+
iEl-
3
8
8
32
+
33
31
4
4c +
5
5
4c + 5
6
22
+
23
20
4e
+
5
5
4e + 5
We need show that does not satisfy the KKT conditions of the problem
| s.l. ViE (1, yE H; 2 3,
(12)
for any margin 3 > 0. A KKT point 2 of the above problem must satisfy ă = -X + X2z2 + Xgra. where X 2 for all i, and X; 0 if y x4 * B. Since is linear combination of the three independent vectors 21, 23 where the coefficients are non-zero, then if 2 is a KKT point of Problem (2) we must have X * for all which implies y1z I, 8 for all i. Therefore, order conclude that is not KKT point, it suffices show that x2 + z 2Tx3.. x3.
We have
6
6
65
6(c + 1)
2 x2 =
12
33
21
12 =
+0+ +
4e
+
5
4e
+
4e
+ 5
4e + 5
4e +
and
6
6
T
6
2 x3
4e +
I2
+
5
23
4e 5
Using the above equations, it is easy to verify that 2 x2 + x 2z for all c O.
TTx,
where 2" argming ||]|] Lemma B.9. For all E 7 we have yızT 2 and ||||| xt7 | S.1. y: x4 2 1 for all i E I.
Proof. By Lemma B.4 for E 1 we have o x; TTx;
and TT x4 < 0. Hence
1 f(;;; W)
m1
x.))
m2
olu Tuu) x;))
vm
vm
m2
I₁
yuu
Vm
Vm
< mi
122
u
24 = 2 24
mm
m
Likewise, by Lemma B.4 for all i E T_ we have v. TT,; < O and u TTx;
x; > 0. Hence
-1 2 [(y W)
mi
06 (xs))
(l" T x2) vm
11
my
m2 u Tr
yu
0;
Vm
mm
mi
m2
u
x; z Nr
m
m
Thus, remains obtain upper bound for |||||-
20

---

Published as a conference paper at ICLR 2023
Assume w.l.o.g. that mi 2 m2 (the proof for the case my S mg similar). Thus, A
/
mm Let mj
2" E I2d such that (x(=))aa x4 2 1 for all i E I. Let
0- = v
+
vm
m2
K K+T
Note that v", u² satisfy the constraints in Problem
(3). Indeed, for i E I_ we have
m2 (u*) xx 7 vm
m1
(o*) I,, = <<{=))=x;
(=*) Fi
1
+
=1
vm
18 K+
K K+7
kt?
K + 7
For E 1+ we have
mi (v") (u') 32
m2 (1") (u*)T==
(z*) 02
<(=²)* T
K
1 1 7AS
+
+
2 1
x+
K
K +
K
where the last inequality is since 0 S (1 x) (1 7) 1 no
7.
By Lemma the pair v, is a global optimum of Problem Hence
mi ||0||² m2 ||ull2 z m ||"01 1|
m2 ||="|1 1|?
1
||
m² (x + 7)2 1|="11
m
R2
m1 mf
(I 7)2
m2
m ||="|]
x²
(x + 72)2
17
m ||?
2
(k + 7)²
mi
Therefore, we have
< m² || + m1m2 ||u1|2 < m ||=*11
| + ||
2
(x + 7)2
Hence,
1')
4 1| (n + 7)2
||=||
72
2
< 2
M1
1
+
m2
41
[lm101] + (122 <
mm
which implies ||=|||
S
2||="| k+7
as required.
C PROOF OF LEMMA 3.3
Proof of Lemma 3.3
According the distribution assumption in the lemma, we can write Z;
/.1/2 where T4 N(O, Ta) By Hanson-Wright inequality (Rudelson & Vershynin, 2013 Theo- rem 2.1), we have for any t 2 0.
(-1 (-0(1 8²
(1(11191))
Pr
///2 2,
x
/ >t] 2cep
i.e.,
| - Vdl > < 2 exp (exp(-00 (-))
Pr
Let /. = C.Vlog n for a sufficiently large constant C > 0. Taking a union bound over all i E [m]. we have that with probability at least n 20 | 0 n) for all i E [n] simultancously.
The proof below holds more generally when 3; has independent subgaussian entries.
21

---

Published as a conference paper at ICLR 2023
For i + j, we have (21, N(O. 2] Σx,). Hence apply standard tail bound obtain
t
Pr Pr[1(zn, my) - exp
2x, Exg
Because we have known that 2. Ex, = 011 11²) = O(d + log n.) = (d) with probability at least 1 - n 20 we have
Pr (21, 24y1 t S 20 + exp (-0 (0((2)
Then we can take Vld for sufficiently large constant and apply a union bound over all i, j. which gives (1x +g)1 Olydlogn for all i + with probability at least
1-n² (n 20 + (exp(-S((C2 (og 1)g) 2 1 n 15
This completes the proof.
D PROOF OF THEOREM 3.4
we need to show that for some to > 0, [()())) < log for to- To do so, we will first show proxy PL inequality (Frei & Gu (021), and then use this to argue that the loss must eventually be smaller than log 2/n.
To prove Theorem 3.4
We begin by showing that the vector πi := Σn ii= yetz correctly classifies the training data with positive margin. To see this, note that for any [n).
ye yk
||
Σ (yr yL.Kk)
2 min || 2l - max (Tx, 25)1
73
1
min ||,
3
(41)
2
min |
(13)
3
Inequality (i) uses the theorem's assumption that 3n max [x,, للحه s y3. Inequality (id) uses that 7 I 1. To show how large of margin f gets on the training data, we bound its norm. We have,
n
y1
Kay, 2zح1
||~;:|1 11? + Σ Kare, K2 s#1
|| (2 max Kors, m3>1 i$
3 ||a;||
min ||=
2n max ||
Denoting Rmin = min; || Rmax
max; ||:l|| and
Remxx / Rmins substituting the above
display into (13) we get for any & E [m).
2/3R2
V2lmin
(14)
2n R2 mux.
3n
22

---

Published as a conference paper at ICLR 2023
Let us now define the matrix Z Rmxd with rows,
2j : | dj-
Since a3 1/m for each j, have | 1, and moreover we have for any k E [n] and
W E Rmxd
(
Uk V (M)
2) = Σ
2 (mug, mkl)
==1
v 2 Rmmin
8' (((10,,zk))
3R RR n m
3R/n
where the first inequality uses (14) and the last inequality uses that ('(2) y. If E is the logistic or exponential loss and we define
10 Σ glu (axs W())),
((2) (2), G(W(t))
72
then since g(=) > 0 the above allows for the following proxy-PL inequality, [V](W())lle> > ((((()))--)
[ (V) ((t), z)
Rmin (()(
(15)
3R/n
By the chain rule, the above implies
d
= = -11
dt
/2 a(W()))
S
3R/a
Let us now calculate how long until we reach the point where ((W < log 2/(3). Define
T inf ((W()) < log 2/(3n)]
Then for any < T we have
dt ((W())) 5 (
V2..minn log 2
3R 3n
Integrating, we see that
I(W())) S ((W(O)) 2R 2mnn ?2 log2(2))
8
Since (()(()) 2 O, this means that т
R2 R2 R2 12)) S
At time we know that GTW < log 2/(3n) and thus Va, W (7)) > 0 for each i. For
both the logistic loss and the exponential loss satisfy ((2) 1 2 -f' and so for either loss, we have
((W(T)) 1 (yrrf(a;
Σ
((u.((aa((T)) 2θ(W(F)) - log 1=1
n 1=1
Since ((W(t)) is decreasing, we thus have for all times t 2 T, we have ((W(t) s [(W(T)) < 1nn(2)nn.
23

---

Published as a conference paper at ICLR 2023
E PROOF OF THEOREM 4.2
In this section, we provide a proof of Theorem 4.2 An overview of our proof is as follows.
1. In Section
we provide basic concentration arguments about the random initialization.
2. In Section E.2
we show that the neural network output and the logistic loss objective func-
tion are smooth as a function of the parameters.
3. In Section 3 we prove a structural result on how gradient descent weights the samples throughout the training trajectory. In particular, we show that throughout gradient descent, the sigmoid losses (v: W(O) grow at approximately the same rate for all samples.
4. In Section we leverage the above structural result to provide a tighter upper bound on
[W( Fr than is possible with a na've application of the triangle inequality.
5. In Section E.5 we provide a lower bound for [|
6. In Section E.6 we show that proxy- PL inequality is satisfied.
7. We conclude the proof of Theorem 4.2 in Section E.7 by putting together the preceding items to bound the stable rank StableRank
[ 1/./ /| [|ž and to show that
[(W(9) + O.
Let us denote by CR == 10R2//2 + 10, where R Rmax/ Rmin and Rmax = max; ||.ي||| Rmin = min; ||>s||- For given probability threshold 8 (0, 1), we make the following assumptions moving forward:
(A1) Step-size a S 2-2 R5mR2m RCC max H))
where & H-smooth and y-leaky.
(A2) Initialization variance satisfies wint S an² Rmin
mnd lo (ogg(4/4mm//))
We shall also use the following notation refer to the sigmoid losses that appear throughout the analysis of gradient descent training for the logistic loss,
g(2) - (2)) I exp(2))
G(W) = Σ (vlif(e; 9.²h : g(yff(;;
12
(16)
E.1 CONCENTRATION FOR RANDOM INITIALIZATION
The following lemma characterizes the f2-norm of each neuron at intialization. It also characterizes how large the projection of each neuron along the direction ği = Σ y:ar be initialization. We shall see in Lemma In the proof of Theorem 4.2 we will argue that by taking a single step of gradient descent with sufficiently large step-size and small initialization variance, the gradient descent update dominates the behavior of each neuron at initialization, so that after one step the ju direction becomes dominant for each neuron. This will form the basis of showing that ((!)) has small stable rank for 1 1.
E.13 that gradient descent forces the weights to align with this direction.
Lemma E.1. With probability at least 1 1 over the random initialization, the following holds. First, we have the following upper bounds for the spectral norm and per-neuron norms at initialization,
|| ||2
Cowiiit
(vm Vdl. and for all j [m], |/ (0) 1|2 I Jw dlwgg/mm//////mm
Second, if we denote by ja E Rdd be the vector E yrtt:/ Ei MaDi then we have
(w0) (0) p < 2wimt v log(4m/0)))))
Proof. For the first part of the lemma, note that for fixed j E [m], there are i.i.d. ~ N(O, such that
d
d
w 10 12
(w (0)) (w = w Σ
2 ~ Whit (d).
24

---

Published as a conference paper at ICLR 2023
By concentration of the x² distribution (Laurent & Massart
2000 Lemma 1), for any t 0,
P
Iwy 12 d 2v + 21
exp(-t).
In particular, if we let log(4m/0), we have that with probability at least - 8/4, for all E [m],
I 10 whit (d + 2/ dllo(44m8)) log(4m/0)) S
For the second part, note that { (i) N(O, w We therefore have ((
(0) mi) 2 t) S
2 eexp(-E (tt2/2wf Choosing t Wintt v log( (mm/0m we see that with probability at least 1 - 6/2, for all J. ((w,) (0) (i)l S 2winit v Alog (1mg(4m/)). Taking a union bound over both events completes the proof.
E.2 SMOOTHNESS OF NETWORK OUTPUT AND LOSS
In this sub-section, we show that the network output and the logistic loss satisfy number of smooth- ness properties, owing the fact that & is H-smooth (i.e., o" exists and (0"(2)] H).
Lemma E.2. For H H-smooth activation & and any W, V Rexd and x E R
H |
If( - f(;;) (V (z (2; W Vy
I
Vll.
2/m
Proof. This was shown in Frei et al. (202a Lemma 4.5).
We next show that the empirical risk is smooth, in the sense that the gradient norm is bounded by the loss itself and that the gradients are Lipschitz.
Lemma E.3. For an H-smooth, 1-Lipschitz activation o and any W, E Rmxdd if [|aaal| S Rmmxx for all i,
VVL(W)ll S G(W) & ((W) A1,
Ryax
where G(W) is defined in (16) Additionally,
[VL(W)- vi(V)ll < R (1+
11 vm
|W
Vl12-
Proof. This follows by Frei et al. (2022a] Lemma 4.6). The only difference is that in that paper, the authors use || < Cip (in their work, x; IRP) to go from equations (5) and (6) to equation (7), while we instead use that ||,;] < 122
E.3 LOss RATIO BOUND
In this section, we prove key structural result which we will refer to as 'loss ratio bound'. Lemma E.4. Let d be a 7-leaky, H-smooth activation. Define R = max,,; ||xel// [la, lb and let us denote CR 10R2 + 10. Suppose that for all E [m], we have,
| 2 5- 5- -2 max xx))
keft
Then under Assumptions (A] and (A2) we have with probubility least 1 8.
(v: W()) E' (y) W())
sup 120
max (Jj[M)
CR.
This lemma shows that regardless of the relationship between æ and the ratio of the sigmoid
losses fx( W()))), where -f((z) = 1/(1 + exp(2)), grows at essentially the same rate for all examples.
25

---

Published as a conference paper at ICLR 2023
Our proof largely follows that used by Frei et al. (2022a), who showed a loss ratio bound for gra- dient descent-trained two-layer networks with y-leaky, -mothh activations when the data comes from mixture of isotropic log-concave distributions. We generalize their proof technique to commodate general training data for which the samples are nearly orthogonal
the sense that | > maxkşti (x),, Additionally, we provide more general proof technique that illus- trates how a loss ratio bound could hold for activations ø for which o' (z) is not bounded from below by an absolute constant (like the ReLU), well as for training data which are not necessarily nearly- orthogonal. We begin by describing two conditions which form the basis of this more general proof technique. The first condition concerns orthogoaaatyy of the gradients of the network, rather than the samples as in the assumption for Theorem 4.2
Condition E.5 NNea--othoggnalityy of gradients). We say that near-orthogonality of gradients holds at time if. for a some absolute constant C" > for any E [n].
(x;; w( C'n max (V] W(t),, (s(sk; W( kft
Note that for linear classifiers-ice. m = 1 with o(z) = -ca--ttttooo of gradients is equivalent to near-orthogonality samples, since in this setting fxx; W) Ij. It is clear that this is more general condition than near-orthogonality of samples.
The next condition we call gradient persistence, which roughly states that the gradients of the net- work with respect to sample has large norm whenever that sample has large norm.
Condition E.6 (Gradient persistence). We say that gradient persistence holds at time L if there is constant c such that for all i E [n],
WV 2 c|1ar112
Gradient persistence essentially states that there is no possibility of a 'vanishing gradient' problem.
Next, show that Lipschitz activation functions that also 'leaky' in the sense that ('(2) > > everywhere, allow for both gradient persistence and, when the samples are nearly-orthogona oranogothoyn of gradients.
Fact E.7. Suppose is such that (=)) for all for some absolute constant 7 >> Suppose that for some C > fo all E [n] we have.
| On max Ka,, ax)). kn1
Then for all times t 2 0, the gradients orthoonor (Condition E.5 with C" C22 and gradient persistence (Condition E.6y holds for = 7?.
Proof. For any samples i, k E [n] and any W E Raxd
(VI(2;; [T] VJ W)) (I,,
a.) ((w,) xx))
Since ('(x) [y; 1] for all 2, we therefore see that gradient persistence holds with 22:
1 Σ o (1w3, 2 11
[V/ W = || 1
j-1
Similarly, we see that the gradients are nearly-orthogonal, since
(8) Cn max 1ffh
(61)
Ca W), (zys W)) <
(r, zx)l
< VIV W)ll.
<>
igk
where (i) uses that & is I-Lipschitz and (ii) uses the assumption on the near-orthogonality of the samples.
26

---

Published as a conference paper at ICLR 2023
We can now begin to prove Lemma E.4 We remind the reader of the notation for the sigmoid loss,
===)== 1 expx(())
g (1,
We follow the same proof technique of Frei et al. (2022a), whereby in order to control the ratio of the sigmoid losses we show instead that the ratio of the exponential losses is small and that this suffices for showing the sigmoid losses is small. As we mention above, we generalize their analysis to emphasize that near-orthogonality of gradients and gradient persistence suffice for showing the loss ratio does not grow significantly.
Lemma E.8. Denote R: = Rmax/ Rmin where Rmmax max, |a,|| and Rm min; ||,,|] and les be an arbitrary I-Lipschitz and H -mmoohh activation. Suppose that near-orthogonality of gradients (Condition E.5 holds for some C² and gradient persistence (Condition E.6 hold at time for some с > 0. Provided S [5 Rmac n10R? /cc 10]] and C' 2 25R / + 25, then for any i.j [n] we have,
exp y4 (az W((+1))
(zf W(()))
exp
exp
yj fz W(++l]))
exp
fzf( W()))
gg Rc min
(t)
R22
9i
X exp
(
n
aK RRR22 max
G(W(())
X exp
(10R2/c 10)n
Proof. It suffices consider i and 2. For notational simplicity denote
A (xp(-)1 ( exp( exp(-y2//(0) (2) W(())
We now calculate the exponential loss ratio between two samples at time + in terms of the exponential loss ratio at time
Recall the notation 9," == (y W()),, and introduce the notation
V [ (())).
27

---

Published as a conference paper at ICLR 2023
We can calculate,
exp( V1 (01: w(++)))
Ac+1
exp(
U/ (12) W(++1)))
vifi (w()) aa10-avi(ww) -VV
exp
y2f2 (W()) - )
exp
vi (aa; (00M + Dn (v (
( exp
H HR max a²
exp
12. (122; ((0) + y2a (4 v[(W((0))
m
exp
(()) V[(W(()))
(4)
exp
V1a
HR
A
vi(w()))
exp
12a
exp
(w)
H H
A,
exp
Σ k=
m
exp
A. exp
X exp
Ih
(y2
V
9k (11
(1)
1 (1)
k
H max
X exp
[i((10))1
(17)
m
(ii) uses the definition of Ar. We now proceed in a manner similar Frei al. (2022a) bound each of the three terms in the product separately. For the first term, since gradient persistence (Condition E.6) holds at time t, we have for any i E [m].
Inequality ( uses Lemma
while
2 c||=,11 2 cR
On the other hand, since @ is 1-Lipschitz we also have
F
||=:||
Σ (lwlw 2.))) S ||=:112 < 12
Putting the preceding two displays together, we get
cR2 mnn
<
13 < R2
(18)
Therefore, have
(t)
(t)
exp (-m a n
(0
1
- 92 1
(1) I1:))
92
9
11
I
|2
exp
71
92
(
S exp
92 a
(1)
gi
(1)
cR2
122
(
exp
92
(t)
acR2
min
g
(4)
R2
(19)
n
Inequality (i) uses (18) and the equality uses the definition R Rmax/ Rmin- term in (17)
This bounds the first
For the second term, we the fact that the gradients are nearly orthogonal at time t (Condition E.5 and the lemma's 's assumption on C' to get for any + k.
(0) 2 C'n n max
(25R²/ /cc + 25)n max KV
( J.
(20)
k
28

---

Published as a conference paper at ICLR 2023
This allows for us bound.
Σ
exp
Uk
9
ya
π
2
(6)
KV
(1)
(0)
exp
9k
11
1#1
2
exp
Σ
9k
|V
(1)
Σ
9
(e)
1
|V 1
n1
(25R cc 25)n
(25R2/c 25)n
1xl
k
exp
a
9k
R
max
a
RR
(25R2 /c 25)m
(25
c 25)m
k
kef2
S exp
2a max
C(WW(o)
(21)
(25R2/c + 25)n
Inequality (i) uses the triangle inequality. Inequality (ii) uses (20)
The inequality (iid) uses (18)
Finally, for the third term of (17) have
H R
H max a² vm
G(w(o))
exp
exp
m
(ii)
aR max
-((V()))
exp
(22)
2(25 c 25)m
Inequality (i) uses Lemma
E.3 while (it)
the lemma's assumption that is smaller than into (17) we get
[5HR2 max n200R2 // 10)] Putting (19) (21)
and (22)
A-1 S Ar exp
92
(2)
acR2
min
(t)
R²
(1)
7
92
c
2a R2
max
G(W())
exp
(25 /cc 25)n
R2
G((W(()
exp
2(25R22/c c/c 25)n
A exp
92
(+)
acRk
min
9 (t)
R²
exp
5a R22 2ux
G(W(()))
(23)
2(25 c 25)n
This completes the proof.
(t) /9/ is large, then for small-enough step-size, Lemma E.8 shows that if the sigmoid loss ratio g; the exponential loss ratio will contract at the following interation. This motivates understanding how the exponential loss ratios relate to the sigmoid loss ratios. We recall the following fact, shown in Frei et al. (2022a) Fact A.2).
Fact E.9. For any 21, 22 E R,
((21)
< max 2,2 exp( -21) expl (app--z)) Ez)
g(z2)
and if 21, > 0, then we also have
exp( - 21
2 g((1)
exp(
=2
g(22)
This fact demonstrates that if we can ensure that the inputs to the losses is positive, then we can essentially treat the sigmoid and exponential losses interchangeably. Thus, if the network is able
29

---

Published as a conference paper at ICLR 2023
to interpolate the training data given time t, can swap the sigmoid loss ratio appearing in Lemma EE8 with the exponential loss, and argue that the exponential loss is too large at a given iteration, it will contract the following one. This allows for the exponential losses to be bounded throughout gradient descent. We formalize this in the following lemma.
Proposition E.10. Denote I == Rmax/ Rmin where Rmax - max; ||=:||| and Rmin = min; || Let be an arbitrary I-Lipschitz and H -mmoohh activation. Suppose that,
Gradient persistence (Condition E.6 holds at time for some c > 0, and
Near-orthogondity of gradients (Condition
E.5 holds at time for some > / /ct
25,
For some p 5R2 /e+ an exponential loss ratio bound holds at time I with,
exp y-ffff W()))
max
(J exp ( Uzf ((()))))))) S.
The network interpolates the training data at time L: ys (14;; W(O) > f all i.
Then, provided the learning rate satisfies [5 (1 /c100////++)]]] we have an exponential loss ratio bound at time + as well,
exp yo (24; W W
max 1. exp
リソ fzzz W(++1) P.
Proof. As in the proof of Lemma the first sample to the exponential loss for the second sample is bounded by p. Let again denote
E.8 it suffices to prove that the ratio of the exponential loss for
A, exp(-yi (x= W())
W(r))
and recall the notation 9; we have,
(+)
l' (y: (a;;; ((;;)(())) and ((("
vf(=: By Lemma E.8
A+t1 S A, exp
92
(1) acR2
min
(
gi
R22 ))
exp
(10R3/c+ C(w(o))
RR2 max
(24)
(0)
92
We now consider two cases.
Case 1: g1 /9/2) < p. Continuing from
(t)
(24)
we have,
(
92
(t)
aR
min
Ri2
a.22 max
G(W())
A441
A. exp
exp
(10R2/C= 10)n
n
(0) R2
R2 (W(()))
92
A exp
a
7
(10R2/ /c 10)n
(6)
< 1.2.,
(68)
$ 2.4
(tv) 2
< 2.4 5
Above, incquality (t) follows since 90 /999" > 0. The equality uses that R = Rmax/ Rmin- Inequality
(ii) uses that 9; (t) < 1, the lemma's assumption the step-size, S [5H R2 n n110R2 /c + 10)]- and that exp(0.1) < 1.2. The incquality (žii uses the proposition's assumption that the network interpolates the training data at time f, that the ratio of exponential losses is at most twice the ratio the sigmoid losses by Fact E.9 The final inequality (iv) follows by the case assumption that (0) (1)
gi / < pp.
30

---

Published as a conference paper at ICLR 2023
Case 2: 91 /92) p...
Continuing from (24)
we have,
A4+1
92
acR
min
91
92
[t)
(8)
R
C
exp
(10RF/cc 10)m
a max
G(W(())
(0)
S A₁ exp
92 RcR
11
min
5
R²
exp
(10R2/e
Q:R max
10)n
G(W(())
A₂ exp
92 acR R2
min
50
2
R
exp
(10R² /c + 10)m
a mmx
92
(1)
1
93
(t)
i=1
92
(6))
S A. exp
92 aCR
min
(5"
2 Ra
eep
a R
-2p)
(1)
(10R2/c 10)n
exp exp
92
acR
min
2 0
R²
R²
5R² 5R2/c /R2//+5' :))
1
(162) Ar S.
Inequality (i) uses the Case assumption that 91 /92 > P.p. Inequality (ii) uses the proposition's assumption that the exponential loss ratio at time / is at most p. so that the sigmoid loss ratio is at most 2p by Fact (note that the sigmoid loss ratio is at least 2p/5 > 2 by the case assumption and p 5). The equality uses that R = Rmax/ Rmin. The final inequality (iii) follows as we can write
(2)
(t)
R2
R
1
2
5R / (/++1)=
R²
5
C
C
5R
c
==
3(R² (1R3/c+1))
2
R
2
0
5
2
> 0.
The first incquality above uses that [=(1+z)) < for x > 0, and the final inequality follows by the assumption that p 2 loss ratio decreases at the following iteration.
5R /c. This proves (iit) above, so that in Case 2, the exponential
In summary, the preceding proposition demonstrates that loss ratio bound can hold for general Lipschitz and smooth activations provided the following four conditions hold for some time to:
(1) an exponential loss ratio bound holds at time to;
(2) cearrorrhogoonaliyy of the gradients holds for all times t 2 to:
gradient persistence holds at all times t 2 lo: and
(4) the network interpolates the training data for all times 2 to-
This is because the proposition guarantees that once you interpolate the training data, if the gradients are pearly-orthogonal and gradient persistence holds, the maximum ratio of the exponential losses does not become any larger than the maximum ratio at time lo- Note that the above proof outline does not rely upon the training data being nearly orthogonal, nor that the activations are 'leaky', and thus may be applicable to more general settings than the ones we consider in this work.
On the other hand, when the training data is nearly-orthogonal and the activations are 7-leaky and H-smooth activations, Fact shows that (2) and (3) above hold for all times t 2 0. Thus, to show a loss ratio bound in this setting, the main task is to show items (1) and (4) above. Towards this end, present the final auxiliary lemma that will be used in the proof of Lemma E.4 A similar lemma appeared in Frei et al. (2022a) Lemma A.3), and our proof is only a small modification of their proof. For completeness, we provide its proof in detail here.
31

---

Published as a conference paper at ICLR 2023
Lemma E.11. Let 6 be 7--eakyy H-smooth activation. Then the following hold with probability at least å over the random initialization.
(a) An exponential loss ratio bound holds at initialization:
max (xp W S exp(2).
4, exp(-0;
(b) If there is an absolute constant CR > 1 such that at time we have maxi, (9: /9/ (0) I Cp and for all k E [n] we have
| 27 20
max 17t
Ka,, mx>|
then for a S (2H122 R n), we have
a7 R ((W()).
for all k E [nd].
(elf(zziW(ttt f(zsi w(0)]
40nmm
(c) Ifror all E [n]] we have || 2 8y-2 and (A2) at time = 1 and for all samples k E [nl], we have yo (Tv;; W(O)) >> O.
2n max444 (0,, zn), then under Assumptions (Al
Proof. We shall prove each part of the lemma in sequence.
Part (a). Since di is 1-Lipschitz and ((0) O, Cauchy-Schwand implies
If(:; W)]
Σ ( -
Σ
(w) x)2 ||
j=1
Applying this bound to the network output for each sample at initialization, we get
(i) V5a R2
(ii))
[f(2 (()) < ||]|a]) S V5wint v log(m// Rmax
Bma
(25)
72n
50
Inequality (i) uses Lemma E.1 while inequality (ti) and (iii) follow by Assumptions (A2) and (AI)
(A2)
respectively. We therefore have.
exp( ppp--11 yi. (0;;; (())))
max I exp( (ol--vjf(e Vj (xz; W()))) - exp(2).
(26)
Part (b). Let &s [n]. Let us re-introduce the notation V v we know
fx W(t).. By Lemma E.2
H RR max a2 2/m m
Vxx w((+1) ((x: f(xx; W(())]
V (1)
Vi(W(())
9
By definition,
(0 (o Iz)
1
o'
(ww)) 22)))' (11,)) xx)))
(27)
m
E(79,1]
32

---

Published as a conference paper at ICLR 2023
We can thus calculate,
yis (z W W(++))
f(xx: W(0))
H HR on G(W())
V
9
m/m
H R on
9 1 n
Σ 9 ( (
(0))
G(W(t))
2/m
1
(
H R 2/m
an
G(wrlo))
96
max 9j
izk
(e)
9
| |/
max,
(V
HR om
max
G(wll))
2/m
9k
where Inequality (i) uses Lemma E.3
Continuing get that
y& [f w((+)) f(xx; W(
IV@
Rd on
212
(t)
|
C² Σ
G(W(())
9k
2/m
IV
HR an G(wrtt) 2/m
CR Σ
Kor,
HR am ((Wlo)) 2/m
(2)
"" 7
9k
IV
(4)
1
H HR 2/m
G(W(()))
9k
2
71
IV3
( R2
H H an G(W(())
G(W(())-
11
20
2/m
(0))
222 G(W(1))
40
Inequality (1) uses the lemma's assumption that , /9/" S C²p- Inequality (it) uses that
is 7-leaky and i-Liischitz (see eq. (27)). Inequality (idi) uses that the assumption that the samples oehroylorlhogonal,
||a > 2- -
R max [a,, 2 27 "C's if
(0r, ax))
Inequality (iv) uses the definition Rmin = min; ||x;|| Inequality (v) again uses the lemma's 's as- sumption of sigmoid loss ratio bound, so that
(t)
(1) G(W()).
9k
9 C
C
The final inequality (vi) follows since the step-size This completes part (b) this lemma.
72 /2HC R2 R2 is small enough.
Part (c). Note that by (25) If( (()) S 1/50. Since is monotone this implics the sigmoid
losses at initialization satisfy 93 so
(0)
E [11 + exp(0.02)) (1 + exp( C [0.49, 0.51] and
G(w(o)) z 100
49
and
max 6,
g (0)
51
(28)
0)
49
9
33

---

Published as a conference paper at ICLR 2023
Thus, the assumption that || 2 8y 2n max (21, and Assumption (A1) apply part (b) of this lemma as follows,
allow for to
yk. (ax: w())
( W(l)) - (xx: W(() + fx W(()
yv (axi W yv. (Ira; W()) - W(
1 an R2
(((11))-- V5winit v md log 4m Rmax
4n 51/49
(() 3 R
-/5mmi v mi log(4m/0)) Rmax
16n
2
16v Srwnin h Ren / md log 4m//)) R
16n
(6i2)
32n
The first term inequality (i) uses the lower bound provided part (b) of this lemma as well as (28)
while the second term uses the upper bound on (fr W( in (25) Inequality (fi) uses (28)
Inequality (tii) uses Assumption (A2) so that Winit I ar² Rminn (72RC / mmd log( 4m (6))
and that 1 5 < 36.
We now have all of the pieces necessary to prove Lemma E.4
Proof of Lemma E.4 In order to show that the ratio of the g(-) losses is bounded, it suffices show that the ratio of exponential losses exp(-(-)) is bounded, since by Fact E.9 W(O))
Aau W(9)) hJ=l... Ily (1y; W(O))
max
max 2,2
ij= exp(- (0, W(())
(29)
We will prove the lemma by first showing exponential loss ratio holds time t 0 and f 1, and then use an inductive argument based on Proposition E. with p == 5R² /y8 + 5 = Cn-
By part (a) of Lemma E.11 the exponential loss ratio at time loss ratio holds at time f == 1, first note that by assumption, we have that the samples satisfy,
is most exp(2). To the
||a.|| 5y -2 =n max (rs, mx3i = 2 22 (25R 25)n max ( (x)), legfi
(30)
Because is y-leaky, H-smooth activation, by Fact E.7 this implies that gradient persistence (Condition E.6 holds with c = 72 and ncar-orthogonality of gradients (Condition E.5) holds for all times &. with C" > 2(25 R2 + 25). By Assumption (A1) at time f = 0, so that we have for any i,J.
therefore apply Lemma E.g
exp
yyf((y (((()) $ exp(2) exp
ye fx, W()))
g
(0) ack2
min
9
R2
exp
9 (0)
72
RRR2 mmxx
G(W(O))
exp
(10R2) / + 10)m
R² R2 a
R2
I exp(2) exp
exp
max
n2
(10R2 /n2 + 10)n
(a exp
R2
R2
exp(2)
+
(10R2 //22 10)n
cxp(2.1) 9.
Inequality (i) uses that g. < 1, while inequality (di) uses that the step-size is sufficiently small a - 1/20 max by Assumption (Al) Therefore, the exponential loss ratio at times = 0 and t most 5 //2 5.
34

---

Published as a conference paper at ICLR 2023
Now suppose by induction that times 1, ..... the exponential loss ratio most 5R² + and consider t 1+ 1. (The cases t = and = 1 were just proved above.) By the induction hypothesis
and (29) the sigmoid loss ratio from times 0,... .,....t is at most 10 /n² 2 + 10. By Assumption (AI) the step-size satisfies
a f 15n R (10R" + 10) max(1, H)) H)
R R'n]-1
Further, the samples satisfy (30) so that
||>م|| 27 (10R2 + 10)n max (Tt, xbmi = 2---2-20 CRR max (2 rR)l: 1yk
Thus all parts of Lemma E.11 hold with Cj CR = 10R2 + 10. By part (b) of that lemma, the unnormalized margin for each sample increased for every time .....,t:
for all r I....,t, yxlf( w((+))) f(xx: w()) > 0.
(31)
Since the network interpolates the training data time 1 by part (c) of Lemma E.11 this implies
for all r = I,...,t, yu f w(r)) > 0.
Finally, since the learning satisfies a 25 C² max(1, H)] all of the conditions necessary to apply Proposition E. hold. This proposition shows that the exponential loss ratio at time + 1 most 5R2 /12 5. This completes the induction so that the exponential loss ratio is at most 5R² //2 + 5 throughout gradient descent, which by (29) implies that the sigmoid loss ratio most 10 //? + 10.
E.4 UPPER BOUND FOR THE FROBENIUS NORM
In this section we prove upper bound for the Frobenius norm of the first-layer weights (recall that StableRank W> = || W 1 [ The proof a modification of Frei et al. (2022a Lemma 4. 10) to accommodate more general data. Note that the lemma is strict improvement over the triangle inequality, as we are able to reduce the growth term by factor of 1/ //v.. The proof crucially relies upon the loss ratio bound proved in Lemma
Lemma E.12. Let Rmin- min; || Rmaxx max; || R Rima: Rini-- and denote CR 10R2 + 10 as the upper bound on the sigmoid loss ratio from Lemma E.4 Suppose that for all i [n] the training data satisfy,
|
5y
Cggn max (14, kef
Then under Assumptions (Al and (22)
with probability at least 1 - for any anyt2 2 1,
n
t-1
|| < || +
G(w(e)))
Vn ==0
Proof. We prove upper bound on the & norm of each neuron and then use this to derive an upper bound on the Frobenius norn of the first layer weight matrix. First note that the lemma's assumptions guarantee that Lemma E.4 holds. Next, by the triangle inequality, we have
( =
(0) w
+
V [((()))
$11w50011
10 IV,
(32)
35

---

Published as a conference paper at ICLR 2023
We now consider the squared gradient norm with respect to the j-th neuron: || , [1
1
9i
(5)
Ye V 5
(1;;
W
n2
i=1
Σ
gi ) 2
Wof(ow
+ Σ
9i gh uey (V)(E Ves( (folms:
n²
AgttE(n)
Σ ( 2
Vyf(a,
V f W(o)), s ( M 9s 9k
n²
[m]
( 2
('(ww))
(0) x.)) 11=111
9i 9k ((uu)] (1) .x)) ((1ff [x))
(s) (s)
A
g (a))
2
||a:112 +
(a) (3) K sk>il
Di 9k
A [n]
)
||:;|| +
(x) Kirs m2a1
A Di
ag (m1
(0(())
1|x;112 + On Σ
( +
n
1=1
Right
(iv)
n 20² 2
gi (3) 2 ||=:1|
Above, inequality (i) uses that V [ W) = aa )r. Inequality (ii) uses that ø is 1- Lipschitz. Inequality (ii) uses the loss ratio bound in Lemma E.4 and inequality (iv) uses the lemma's 's assumption about the near-orthogonality of the samples. We can thus continue,
1(W( <
2a²
Σ
(1)))) ||0;|1
n 2
20 203 Rems
max (s)
Σg'
9k
n²
1=1
Ra
max
9k
(5)
G((V(a))
n
(6) 2a R2
On
(G(W()))?
(33)
The final inequality uses the loss ratio bound so that we have
max; 9
CR
max K
9
i=1
Finally, taking square roots of (33) and applying this bound on the norm in Inequality (32) above we conclude that
||u50|| < 10 + V2Cula, la, Rman a
Σ G(w()))
Vn
establishing our claim for the upper bound on [lug))] |I For the bound on the Frobenius norm, we have analogue of (32)
1 < |
v L[((()))
+ 0
36

---

Published as a conference paper at ICLR 2023
and simply that a} 1/m and
[V( Σ
1 |V,
E.5 LOWER BOUND FOR THE SPECTRAL NORM
We next show that the spectral norm is large. The proof follows by showing that after the first step of gradient descent, every neuron is highly correlated with the vector çi -i=1 Ye
Lemma E.13. Let Rmaxx max; || Rmin min; ||x and R Rmax/ Rmin- Let Cn
10R2--2 + 10. Suppose that for all E [n]] the training data satisfy.
| 1 2 5- ²CCn max (xi, ket
Then, under Assumptions (AT) and (A2) have with probability at least 1 we have the following lower bound for the spectral norm of the weights for any t 2
|| 2
or Rmin
Σ ((W()).
L-
4/2RV ==0
Proof. We shall show that every neuron is highly correlated with the vector p == Ex= yi By definition,
(10) (1+1) - 10j m
aa;
Ji
(t)
xi))
yits Σ
ad
9i (w(w xz))
|1:11 Σ
Positive neurons.
If aj > O, then we have,
alaj
(10) (++1)
w/) p
9 (1(1))) .x4))
|
Σ
(aras
A
ala5
Ø' ((w) (1) xx)))
/// ||0:,1?
N/ IV aa
R2
min
0'
('((w)) (9) xx)))
2n
ar/ay1 G(W(t)).
2
Inequality (i) uses the lemma's assumption that ||x; > maxky4 (1,, mb).. Inequality (ii) uses that & is 7-leaky and g; (t) > 0. Telescoping, we get
(w])
(1) - 3 3
R2
min Σ G(w(o)) = a7 min
Σ G(w(+)).
(34)
2 2/m
==0
==0
We now show that we can ignore the (w) ( term by taking a large relative to Wint- By the calculation in (25) know that (x;; W()) < for each and thus
G(W()))= = Σ
+ exp(-vif(xa W())) 2 1/4.
(35)
i=1
37

---

Published as a conference paper at ICLR 2023
On the other hand, by Lemma E.1 know that
(w))
(0) ( 2wimit Iaail v log (4m/))
By the lemma's assumption that | 1|? > n maxxşi [ mkl), we have
|
|
+ n max kp
(ax, xza)
2nllaax
(36)
kockpta
Substituting this inequality into the previous display, we get
Ku, | S 4 v log(4m/6).
(0)
(37)
We thus have
ar R ((W(O))
( ary R
2 2/m m
8/m
min v n log(4m/6)
(aa)
(0) p.
(38)
where (i) uses (35) (i)) uses Assumption (A2) and that CR > so that,
a 2 64winit CR R Rmax/ (iiin) V nm log (4m/5) 64wimit? - CC R2/ Rmin) nm log(4m//) 4m/6),
and (iii) uses (37)
Continuing from (34) we get
(1o/)) ( 2 (w
(t)
w p3) - 1100 (0) p
w.
(0)
a7
|a R
[-1
((w())) - Kww (2)
2
an a7/ay/
R22
min
G(w())).
(39)
where the last inequality uses (38)
Negative neurons.
The argument in this case is essentially identical. If aj 0, then
(wu(tt)) - wi .)) < ala,
d' ((1 xz1) ||0,1|2 1-a12-I(ann Exs aR\i
1=1
(4)
ar [a,
R min
(4)
Φ' ((110)
(((()))))))))) ,xi))
9T
2n
(682)
anyaa R2
min
G(()())))
2
where the inequalities (i) and (ii) follow using an identical logic to the positive neuron case. We therefore have for negative neurons,
07122
[-1
( W/ ..)
min 2/m
C(ww)
(40)
An identical argument used for the positive neurons to derive (39) shows a similar bound for (m0g) (t)
38

---

Published as a conference paper at ICLR 2023
To see the claim about the spectral norm, first note that since Rmin 0, Kuw m1i] * O. We thus calculate,
and hence
(1) 2
|
12
|W
p 1
m
-171
(10))) m2)
(t)
j=1
R2
C(wioo))
2
|7 2
min
/=1
==0
ary R
-|111-2
min
G(Wr())
(6)
ony R min
G(wlo))
4v 2 v
Inequality (i) uses (34) and (40) and inequality (it) uses the upper bound for || given in (36)
This completes the proof.
E.6 PROXY PI. INEQUALITY
Our final task for the proof of Theorem 4.2 is to show that ?(W(0) -> O. We do so by establishing a variant of the Definition 1.2).
(PL. iequallty called a proxy PL inequality (Frei Gu 2021
Lemma E.14. Let Rmax =
max; ||=:||, Rmin = min; ||aall. and R == Rmax/ Rmin- Let On 10R + 10. Suppose the training data satisfy, for all E [n].
||=;|| 2 5y CRR max (xi, kii
For ryleaky activation, the following proxy- PL inequality holds for any t 2 0:
vi(ww))]
2 7 Rmina
2/2R/n G(W(O).
Proof. By definition, for any matrix V E R. with ||V|| S we have
x VD > (vî()) -V) g y (Vf(,; V).
Let ū = - Mar; and define the matrix V having rows agp\ [|]]] Then, || -/ o² 1, and we have for each j.
Vs (Vf(a,
o' d'(w,, 21) pt p/1
8 ((WW (())
||0,|12 +
Σ
(M ylokk
| m
k
m
1 2 ((10,
( _110011
R2 min
m
8' ((W,,,)))
2 m
(mi)
RR
2 |
39

---

Published as a conference paper at ICLR 2023
Inequality (1) uses the lemma's assumption that |2,,11 2 > maxx4i (T,, mz)|_ Inequality (ii) uses
that ||:;|| 1 2 Rmin and inequality (iii) uses that (')=) 7.
We therefore have,
IVL(W()
(V
(V (V
R G(W())
2 7
7 Rin
G(W(D)=
C(W(1)) 2/2RVn
~Riii
2 2v2Rmmm
where the final inequality uses the calculation (36)
E.7 PROOF OF THEOREM
We are now in position to provide the proof of Theorem 4.2 re-state the theorem below.
For the reader's convenience, we
Theorem 4.2. Suppose that & is a 7-leaky, H-smooohh activation. For training data {1Ii Mc) ))) C Rd x {11}. let Rmax max; ||ara] and Ramin min; ||æra], and suppose R = Rmox/ Rmin is at most an absolute constant. Denote by Cr = 10R2 + 10. Assume the training data satisfies,
R2 2 5- 3 Cn max Kr,,,,)). 6$
There exist absolute constants C1, C2 > 1 (independent of m. d, and n) such that the following holds. For any 8 (0,1), if the step-size satisfies a S (5n CR H)) and
Winit. S an,? Rmin (T2RC / log (4m/8))= -1, then with probability least 1 8 over the random initialization of gradient descent, the trained network satisfies:
1. The empirical risk under the logistic loss satisfies L(W(0) S v CinjRanat 1 1.
2. The l2 norm of each neuron grows infinity: for all j. |10 00.
3. The stable rank of the weights is bounded: sup121 [StableRank(W((0)} < C2.
Proof. We prove the theorem in parts.
Empirical risk driven to zero. This is simple consequence of the proxy-PL inequality given
in Lemma E.14 since é is smooth; a small modification of the proof Frei et al. (2022a) Lemma
4.12) suffices. In particular, since by Lemma E.3 the loss T.ww)) has R2 (1 + H m ipsschitz gradients, we have
[(w(++1) s f(W())) a (
||
+ R max(1, H/ m |V(((())) 1|
Applying the proxy-PL inequality of Lemma E.14 and using that a < 12 max (1, H/ mm) we thus have
7 R2
min G(w < |V(((()) [((wle+)) i(wlo)) [[(](t)))(((w(())]]
8
Telescoping the above, we get
Σ Gww 2l(W(!))
8nR
min G( KT
aT
72 R2 min
We know from the proof of Lemma sample for all times. Since g monotone, this implies G(W(t) is decreasing and hence G(W(9)2, which implies
(see 31) that the unnormalized margin increases for each
((W(T-1))= = min G(w())
min k<T
R2 of
40

---

Published as a conference paper at ICLR 2023
Since f(2) (g(2) for and we know that the network interpolates the training data for all
times 1, we know that L(W(t)) (G(W((0) for 1, so that for T Σ
(w (R)
L(W(T-1)) < (G((W(T-1) s 2
722h R aT
Norms driven to infinity. for each j.
We showed in Lemma
E.13 (see (39)
and (36) that for each 2 1 and
alaj
12 min
1 (0)
10 (w)) ///lT//1
G(w()).
4v 22
It therefore suffices to show that E. ((W(s)) exists some > 0 such that Σ (s) & B for all t. By Lemma E.12 this implies that for all t, [[ | S ||
Suppose this is not the case, that there
2-2//RR Rmax
a/13. /n3. In particular, ||V is bounded independently
of l. But this contradicts the fact that ((W(O) + and & > everywhere, and thus [/w, E.1 G(W(+)) 0o.
( || z
Stable rank is constant. By definition,
| |2
StableRank(W1l))
[
We consider two cases.
Case 1: || > 2| 2/ In this instance, by Lemma E.12 ties,
we have the chain of inequali-
V2C It Max Ok
2| <
| < | +
G(w(s)).
Vn
a=0
In particular, we have
220
R Rmax a
|
G(W(+)).
Vn
s=0
We can thus use Lemma 13 and Lemma E.12 12 spectral norm:
bound the ratio of the Frobenius norm to the
IF [W0 2|
[W(0) |E + v R
Ex G(W())
v
Rr
L- G(W())
4/
2v WC Runa E G((r())
vn
cc Run
E G(W(o))
4v/28/m
160 R2a-1
(41)
Case 2: | |F < 2 W ||.
Again using Lemma E.13 we have
|
2|( F
[ 11
Puin
Σi= G(W())
v Vowinit /md looggmmmm)))
an Rai G(W(O))
4/2R
(8) 4v 5wimtt v md log (4m/))
4v2RV
= 166 RR Vna -l "iit mm
(668)
7//n 16C 16
(42)
41

---

Published as a conference paper at ICLR 2023
8
-4
Figure 3: The 0.1-leaky, --smooth leaky activation d(z) = 0.12 +11++00 0.9 0.9 log (5 exp(22) (left) and the standard leaky ReLU 6(2) = max(0.12, 2) (right).
Inequality
i uses
Lemma
Inequality (ii) uses that G(W 1/4 by
calculation (35)
The final
inequality (ite) uses Assumption (A2) that Winit S
a Ramia (72 (72RC nny mollo(( (mm/g))m/))))- Thus, (42) rank,
yields the following upper bound for the stable
StableRank( S C6 16 160 10) C*.
F EXPERIMENT DETAILS
We describe below the two experimental settings we consider.
F.1 BINARY CLUSTER DATA
In Figure [ consider the binary cluster distribution described in (4) We consider neural network with m = 512 neurons with activation o(2) = 7/2 + (1 7) log ( + exp(2))) for
y 0.1, which a 0.1-leaky, 1/4-smooth leaky ReLU activation (see Figure 3}. We fix n 100 samples with mean separation ||д||| = d0 with each entry of identical and positive. We introduce label noise by making 15% of the labels each cluster share the opposing cluster label (i.e.. samples from cluster
+u1 have label +1 with probability 0.85 and -1 with probability 0.15). Concurrent with the set-up in Section 4 we do not use biases and we keep the second layer fixed at the values #1/ with exactly half of the second-layer weights positive and the other half negative. For the figure on the left, the initialization is standard normal distribution with standard deviation that is 50x smaller than the TensorFlow default initialization, that is, Winit 1/50 W where wnit /2/(m + d). For the figure on the right, we fix d 10 and vary the initialization standard deviation for different multiples of wiit so that the variance between (10-2wTTF )2 and (10"w )2 For the experiment on the effect of dimension, we use fixed learning rate of 0.01, while for the experiment on the effect of the initialization scale we use learning rate of a = 0.16. In Figure [ we show the stable rank the first-layer weights scaled by the initial stable rank of the (0))). The line shows the average over independent random initializations with eтror bars (barely visible) corresponding to plus or minus one standard deviation.
network (i.c.. we plot StableRank( (Sab)///eleaaak
In Figure 4 we provide additional empirical observations on how the learning rate can affect the initialization scale's influence on the stable rank of the trained network as we showed in Figure []] We fix d = 10 and otherwise use the same setup for Figure | described in the previous paragraph. When the learning rate is the smaller value = 0.01, training for longer can reduce the (stable) rank of the network, while for the larger learning rate of 0.32 most of the rank reduction occurs in the first step of gradient descent.
In Figure 5 we examine the training accuracy, test accuracy, and stable rank of networks trained on the binary cluster distribution described above. Here we fix d = 10 and a = 0.01 and otherwise use the same setup described in the first paragraph. We again consider two settings of the initialization scale: either a standard deviation of TF or 1/50 x wnit. We again see that the stable rank decreases much more rapidly when using small initialization. Note that in both settings we observe benign
TF
42

---

Published as a conference paper at ICLR 2023
Relative Rank Intialization Scale
Relative Rank Iniializatin Scale
1.00
1.00
rank relative to intilliation
rank relattive Entiaatzation
0.75-
0.75
Steps
1
1
0.50
0.50
10
300
300
0.25
53060
0.25
53060
0.00
0.00
0.01
0.10
1.00
10.0 00
0.1
1.0
10.0
iniialization scale (mulliple tensorflow default
iniliaizztion scale (mulliple tensonflow default)
(a) Learning rate 0.01
(b) Learning rate 0.32
Figure 4: With larger learning rates, most of the rank reduction occurs in the first step of gradient descent. With smaller learning rates, training for longer can reduce the rank most initialization scales.
default ini.
small init.
-1.00
300-
rank
0.75
200
0.50
stablerank
train, acc
100-
0.25
val_ acc
0
0.00
1e+01
1e+03
1e+05
1e+01
1e403
1e:05
step
Figure 5: For the nigh-dimensional binary cluster data (cf. (4)) we see that using small initializa- tion scale leads to a rapid decrease in the stable rank of the network. A similar phenomenon occurs with CIFAR-10 10 (see Figure 2}.
overfitting phenomenon as the training accuracy 100% and the test accuracy is eventually the (optimal) 85%.
Finally, in Figure 6 we examine the training and test error of two-layer leaky ReLU networks trained by gradient descent with learning rate 0.01 for the 2-XOR distribution described in 3ection(3(win) n = 80). We fix the number neurons to m = 512. Theorem 3.2 suggests that the leaky parameter 7 and are large enough relative the number of samples, then the network will achieve a linear decision boundary. For the 2-XOR distribution, every classifier with a linear decision boundary achieves 50% test accuracy. We see that as y and d increase, the test accuracy is indeed close to 50%, but for small 7 and d the network achieves better performance and thus learns nonlinear decision boundary.
F.2 CIFAR10
We the standard 10-class CIFARI0 dataset with pixel values normalized be between and (dividing each pixel value by 255). We consider a standard two-layer network with 512 neurons with ReLU activations with biases and with second-layer weights trained. We train for T 10 steps with SGD with batch size 128 and learning rate of = 0.01. Figure 2 shows the average over 5 independent random initializations with shaded area corresponding plus or minus one standard deviation.
For the second-laye initialization we use the standard TensorFlow Dense layer initialization, which uses Glorot Uniform with standard deviation /2/(m + 10) (since the network has outputs). For the first-layer initialization, we consider two different initialization schemes.
We use the standard Dense layer initialization in TensorFlow Keras. In this case the "Glorot Uniform' initialization has standard deviation T. (2/(m + d).
Default initialization.
43

---

Published as a conference paper at ICLR 2023
Leaky ReLU Networks on XOR Data
leaky: 0.001
leaky: 0.01
leaky: 0.1
leaky: 0.2
1.0
0.8
4000 12
0.5
accuracy
0.5
metric
train acc
1.0
val acc
0.8
0000S
0.6
1e+01 1e403
1e405
1e401
1e403
1e405
1e401
1e+03
1e405
1e401
1e403
1e405
step
Figure 6: As y and d increase, leaky ReLU networks trained by gradient descent fail to generalize well for the XOR distribution, as predicted by Theorem 3.2
Small initialization. use Whntt wiit/ /50.
44


Reviews:
[{"review_id": "ojqZL57v0e", "reviewer": "Reviewer_ewuA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is concerned with the implicit bias of gradient flow and gradient descent in two-layer fully connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal. For gradient flow, this paper leverages the implicit bias for homogeneous neural networks to show that gradient flow produces a neural network with rank at most two. For gradient descent, this paper shows that a single step of gradient descent suffices to sufficiently reduce the rank of the network and the rank remains small throughout training. Finally, several experiments are provided to verify the effectiveness of the proposed method.\n", "summary_of_the_review": "This paper is concerned with the implicit bias of gradient flow and gradient descent in two-layer fully connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal. I believe the paper shalle be improved in providing a detailed comparison of related works on assumptions on the data, activation functions, global/local optimality, and other interesting findings. Overall, the contribution of the present paper is below the bar for ICLR.\n------------------------------------------------------\nI have looked at the the authors' replies as well as the comments of other reviewers. I agree that the paper contributes new ideas and technical proofs for understanding training of leaky ReLU networks. I have updated my score. It would be good to see all the corrections in the revision. \n", "strength_and_weaknesses": "Strengths: the paper characterizes the implicit bias of common gradient-based optimization algorithms for two-layer leaky ReLU networks trained on high-dimensional datasets. It presents that small initialization variance is important for gradient descent’s ability to quickly produce low-rank networks.\nWeaknesses: The clear and precise definition of \"high-dimensional data\" is missing. What exactly are \"high-dimensional data\"? I understand random data in high-dimensions are almost always nearly orthogonal to each other. Please be more careful when stating the 'near-orthogonality' of data dealt with in the paper. Can we quantify the required \"near-orthogonality\" of data? Furthermore, the idea, analysis, and technical tools used in this paper are mainly adapted from the literature, in e.g., Lyu & Li (2019), Ji & Telgarsky (2020), Lyu et al. (2021). Third, I am not sure whether this so-called \"implict bias\" pertains to the network itself intrinsically, since if some of the assumptions on the data/gradient flow algorithms would make the \"implict bias\" not hold. Some existing works on two-layer ReLU or leaky ReLU learning are missing and closely related. See e.g., the landscaple and local/global optimality of (Leaky) ReLU networks in Laurent, et al, The multilinear structure of ReLU networks, in ICML, 2018; Laurent, et al, Deep linear networks with arbitrary loss: All local minima are global, in ICML, 2018; as well as the global optimality of SGD on training ReLU networks and the rank-2 solutions of regularized relu training in e.g., Wang, et al. Learning relu networks on linearly separable data: Algorithm, optimality, and generalization. IEEE TSP, 2019, and Yang, et al. Learning two-layer relu networks is nearly as easy as learning linear classifiers on separable data. IEEE TSP, 2021.  Ergen & Pilanci, (2020, June). Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. In International Conference on Artificial Intelligence and Statistics. PMLR. Last, can the results generalzie to three-layer or deep ReLU networks of practical interest? Or please at least discuss its implications for training deep relu networks.\n\nComments:\ni) This paper investigates the implicit bias of gradient flow and gradient descent in two-layer fully-connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal. However, the paper still focuses on two-layer neural networks and also only the leaky ReLU activations. More comparison of the work in context shall be included, as well as its practical hints for ReLU networks and deeper networks.\nii) On Page 1, \"We consider fully-connected two-layer networks with m neurons where the first layer weights are trained and the second layer weights are fixed at their random initialization.\" Although fixing the second-layer weights does seem to harm the representation of the 2-layer network, which is indeed used in most existing works, this (considerably) makes the learning problem much easier. Nonconvex optimization often comes from the symmetry or rotation, if one fixes the second-layer and breaks the symmetry/or elliminates the scaling issue. It would be much more meaningful to study the landscape and learning behaviour of the two-layer networks.\niii) Could you please list the pros and cons of your offline method compared with the online method in Lyu & Li (2019) and Ji & Telgarsky (2020)? In addition, could you explain how does different choices affect the result?\niv) In the experiments, this paper verifies the theoretical results in two-layer ReLU networks with bias terms trained by SGD only on CIFAR-10. More datasets and tests shall be conducted for validation.\nv) There are some mistakes in grammar and sentences, such as \"...and consider training that starts from a...\" and \"...when the labels y are some nonlinear function of t...\" These indistinct expressions abate the readability of this paper.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jSaasMzGc3", "reviewer": "Reviewer_MUCK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the implicit bias of gradient flow/descent on a two-layer leaky-ReLU network. Specifically, assuming the data points are nearly orthogonal, Theorem 3.2 gives an accurate characterization of the KKT point of the margin maximization problem: all data points are support vectors, the first layer is of rank 2, and a closed-form solution is given. In Theorem 3.4, it is further shown that gradient flow converges to this solution. Section 4 focuses on gradient descent, and shows that with nearly orthogonal data and smoothed leaky-ReLU activation, the stable rank of the network is bounded by a universal constant. Empirical supports are also provided.", "summary_of_the_review": "This paper gives interesting results on the implicit bias of gradient descent with nearly-orthogonal data and leaky-ReLU activation. I recommend for acceptance.", "strength_and_weaknesses": "This paper provides interesting and accurate characterizations of the implicit bias of gradient flow/descent with nearly-orthogonal data and leaky-ReLU activation. Specifically, although the network can be highly over-parameterized, this paper shows that the classical or stable rank stays small. One weakness is that the near orthogonality condition is a little restrictive, as it implies linear separability. Lemma 3.3 shows that it holds with Gaussian inputs, but it requires $d\\ge n^2$, which does not hold in practice. Can you discuss how this assumption is used in your proof, and why linear separability is not enough?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QIuvTc_iyT", "reviewer": "Reviewer_BzfX", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers learning high dimensional linearly separable data with a one-hidden layer network with Leaky ReLU activations. The high dimensional data assumption entails that the norm of the data points is significantly larger than the pairwise correlation between different points. The assumption holds for random high dimensional data such as a Gaussian distribution. It is shown that a network where the first layer is trained with gradient flow has the following properties: (1) It converges to a zero training error solution (2) The solution has rank at most 2. (3) The solution has a linear decision boundary (4) It converges to a certain max margin solution which is not necessarily the max margin linear separator. Results for gradient descent are also presented where a bound on the stable rank is proved.", "summary_of_the_review": "Strong and novel theoretical results in a challenging setting and very well written. Highly recommend for acceptance.", "strength_and_weaknesses": "Strengths:\n1. Strong theoretical results in a challenging setup.\n2. New theoretical techniques that might be useful in other settings.\n3. Very well written.\n4. Novel empirical findings.\n\n\nWeaknesses:\n\nNothing major. \nTwo minor weaknesses:\n1. The fact that “high dimensional data” is used throughout can be a bit of an over statement. For example, consider classifying MNIST digits, e.g., 0 digit vs. 1 digit. This problem is high dimensional, while I guess that the assumption in the paper is not satisfied. For example, there can be two data points of a 0 digit that have a large pairwise correlation. Maybe “random high dimensional data” is more accurate.\n2. There are only a few experiments. There are many interesting experiments that can be included. For example, the theoretical finding on D_XOR is very interesting because usually networks solve the XOR problem. I guess that this is because of the high noise and low norm of the cluster centers. In any case, it would be interesting to see that the network indeed fails on this data empirically and converges to a linear classifier.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3r_PXooaTj", "reviewer": "Reviewer_kRaJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors studied the implicit bias of gradient flow and gradient descent for two-layer leaky-ReLU networks with nearly orthogonal data. It is shown that gradient flow will asymptotically converge to a network with rank at most 2 and linear decision boundary. Such a network is also approximately a max-margin linear predictor. For gradient descent, it is shown that with small enough initialization, a single step could reduce the rank of weight matrix to constant and the rank of weight matrix will remain constant throughout training. Experiments are also provided to support the theoretical results.", "summary_of_the_review": "In summary, this work studied the implicit bias of two-layer leaky ReLU network with nearly orthogonal data. It shows that the convergence point has a low (stable) rank weight matrix and a linear decision boundary. The results seem to be new and interesting. Therefore, I’m currently leaning towards accept.", "strength_and_weaknesses": "Strength:\n- The paper is well-written and easy to follow.\n- Understand the implicit bias of neural networks is an important problem and current paper provides an answer in the two-layer leaky-ReLU network with nearly orthogonal data setting.\n- The results are clearly stated with proof ideas discussed in the main text and full proofs in the appendix.\n- I found the section 5 that discusses the implication of the result quite interesting: it not only discusses the benefits of such implicit bias, but also gives examples where such implicit bias is harmful.\n\nWeaknesses:\n- As mentioned in the conclusion section by authors, the results heavily rely on leaky ReLU and cannot be applied to ReLU. Such leaky parameter $\\gamma$ also has impact on the convergence point, such as point 7 in Theorem 3.2. It is unclear how to generalize the results to other activations and non-nearly-orthogonal data.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%