Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs
Authors: Dmitry Chistikov
Matthias Englert
Ranko Lazic
Venue: NeurIPS 2023 poster (2023)
Keywords: implicit bias
implicit regularization
training dynamics
ReLU networks
gradient flow
theoretical analysis
TL;DR: We perform a detailed analysis of dynamics, convergence, and implicit bias of gradient flow from a small initialisation, for learning a neuron by a one-hidden layer ReLU network, when the training points are correlated with the teacher.

Abstract: We prove that, for the fundamental regression task of learning a single neuron, training a one-hidden layer ReLU network of any width by gradient flow from a small initialisation converges to zero loss and is implicitly biased to minimise the rank of network parameters.  By assuming that the training points are correlated with the teacher neuron, we complement previous work that considered orthogonal datasets.  Our results are based on a detailed non-asymptotic analysis of the dynamics of each hidden neuron throughout the training.  We also show and characterise a surprising distinction in this setting between interpolator networks of minimal rank and those of minimal Euclidean norm.  Finally we perform a range of numerical experiments, which corroborate our theoretical findings.

Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs
Dmitry Chistikov" University of Warwick d. chisttikov@xarwic..ea ac uk
Matthias Englert* University of Warwick
m. englert@warwick.ett ac, uk
Ranko Lazié*
University of Warwick
I. 8 lazic@warwick. ac uk
Abstract
We prove that, for the fundamental regression task of learning a single neuron, training one-hidden layer ReL.U network of any width by gradient flow from small initialisation converges to zero loss and implicitly biased to minimise the rank of network parameters. By assuming that the training points correlated with the teacher neuron, we complement previous work that considered orthogonal datasets. Our results based on a detailed non-asymptotic analysis of the dynam- ics of each hidden neuron throughout the training. We also show and characterise a surprising distinction in this setting between interpolator networks of minimal rank and those of minimal Euclidean norm. Finally we perform range of numerical experiments, which corroborate our theoretical findings.
Introduction
One of the grand challenges for machine learning research is to understand how overparameterised neural networks are able to fit perfectly the training examples and simultancously to generalise well to unseen data [Zhang, Bengio, Hardt, Recht, and Vinyals, 2021]. The double-descent phe- nomenon [Belkin, Hsu, Ma, and Mandal, 2019], where increasing the neural network capacity beyond the interpolation threshold can eventually reduce the test loss much further than could be achieved around the underparameterised "sweet spot", is mystery from the standpoint of classical machine learning theory. This has been observed to happen even for training without explicit regularisers.
Implicit bias of gradient-based algorithms. A key hypothesis towards explaining the double- descent phenomenon is that the gradient- based algorithms that are used for training are implicitly biased (or implicitly regularised) [Neyshabur, Bhojanapalli, McAllester, and Srebro, 2017] to con- verge to solutions that addition to fitting the training examples have certain properties which cause them generalise well. It has attracted much attention in recent years from the research community, which has made substantial progress uncovering implicit biases of training algorithms in many important settings [Vardi, 2023]. For example, for classification tasks, and for homogeneous networks (which is a wide class that includes ReLU networks provided they contain neither biases at levels deeper than the first nor residual connections). Lyu and Li [2020] and Ji and Telgarsky [2020] established that gradient flow is biased towards maximising the classification margin in parameter space, in the sense that once the training loss gets sufficiently small, the direction of the parameters subsequently converges to Karush-Kuil
point of the margin maximisation problem.
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Insights gained in this foundational research direction have not only shed light on overparameterised generalisation, but have been applied to tackle other central problems, such as the susceptibility of networks trained by gradient- algorithms to adversarial examples [Vardi, Yehudai, and Shamir, 2022] and the possibility of extracting training data from network parameters [Haim, Vardi, Yehudai, Shamir, and Irani, 2022].
Regression tasks and initialisation scale. Showing the implicit bias for regression tasks, where the loss function is commonly mean square, has turned out to be more challenging than for classification tasks, where loss functions typically have exponential tails. A major difference is that, whereas most exponentin
of the results for classification do not depend on how the network parameters are initialised, the scale of the initialisation has been observed affect decisively the implicit bias of gradient-based algorithms for regression [Woodworth, Gunasekar, Lee, Moroshko, Savarese, Golan, Soudry, and Srebro, 2020]. When it is large so that the training follows the lazy regime, we tend to have fast convergence to global minimum of the loss, however without an implicit bias towards sparsity and with limited generalisation [Jacot, Ged, Simşck, Hongler, and Gabriel, 2021]. The focus, albeit the price of uncertain convergence and lengthier training, has therefore been on the rich regime where the initialisation scale small.
Considerable advances have been achieved for linear networks. For example, Azulay, Moroshko, Nacson, Woodworth, Srebro, Globerson, and Soudry [2021] and Yun, Krishnan, and Mobahi [2021] proved that gradient flow is biased to minimise the Euclidean norm of the predictor for one-hidden layer linear networks with infinitesimally small initialisation, and that the same holds also for deeper linear networks under an additional assumption on their initialisation. A related extensive line of work is on implicit bias of gradient-based algorithms for matrix factorisation and reconstruction. which has been fruitful test-bed for regression using multi-layer networks. For example, Gunasekar, Woodworth, Bhojanapalli, Neyshabur, and Srebro [2017] proved that, under a commutativity restric- tion and starting from a small initialisation, gradient flow is biased to minimise the nuclear norm of the solution matrix; they also conjectured that the restriction can be dropped, which after a number of subsequent works was refuted by Li, Luo, and Lyu [2021], leading to detailed analysis of both underparameterissed and overparameterised regimes by Jin, Li, Lyu, Du, and Lee [2023].
For non-linear networks, such as those with the popular ReLU activation, progress has been difficult. Indeed, Vardi and Shamir [2021] showed that precisely characterising the implicit bias via a non- trivial regularisation function is impossible already for single-neuron one-hidden layer ReLU networks, and Timor, Vardi, and Shamir [2023] showed that gradient flow is not biased towards low-rank parameter matrices for multiple-outpu ReLU networks already with one hidden layer and small training datasets.
ReLU networks and training dynamics. We suggest that, in order to further substantially our knowledge of convergence, implicit bias, and generalisation for regression tasks using non-linear networks, we need to understand more thoroughly the dynamics throughout the gradient- based training. This is because of the observed strong influence that initialisation has solutions, but is challenging due to the highly non-convex optimisation landscape. To this end, evidence and intuition were provided by Maennel, Bousquet, and Gelly [2018), Li al. [2021], and Jacot et al. [2021], who conjectured that, from sufficiently small initialisations, after an initial phase where the neurons get aligned to number of directions that depend only on the dataset, training causes the parameters to pass close to a sequence of saddle points, during which their rank increases gradually but stays low.
The first comprehensive analysis in this vein was accomplished by Boursier, Pillaud- Flammarion [2022], who focused on orthogonal datasets (which are therefore of cardinality less than or equal to the input dimension), and established that, for one- one-hidden layer ReLU networks, gradient flow from an infinitesimal initialisation converges to zero loss and is implicitly biased to minimise the Euclidean norm of the network parameters. They also showed that, per sign class of the training labels (positive or negative), minimising the Euclidean norm of the interpolator networks coincides with minimising their rank.
and
Our contributions. We tackle the main challenge posed by Boursier et al. [2022], namely handling datasets that are not orthogonal. A major obstacle to doing so is that, whereas the analysis of the training dynamics in the orthogonal case made extensive use of an almost complete separation between turning phase and a growth phase for all hidden neurons, non-orthogonal datasets cause

---

considerably more complex dynamics in which hidden neurons follow training trajectories that simultaneously evolve their directions and norms [Boursier et al., 2022, Appendix A].
To analyse this involved dynamics in a reasonably clean setting, we consider the training of one- hidden layer ReLU networks by gradient flow from small balanced initialisation on datasets that labelled by a teacher ReLU neuron with which all the training points are correlated. More precisely, we assume that the angles between the training points and the teacher neuron are less than и /4, which implies that all angles between training points are less than 7/2. The latter restriction has featured per label class in many works in the literature (such as by Phuong and Lampert [2021] and Wang and Pilanci [2022]), and the former is satisfied for example if the training points can be obtained by summing the teacher neuron e² with arbitrary vectors of length less than ||o* 1l/v2. All our other assumptions are very mild, either satisfied with probability exponentially close by any standard random initialisation, or excluding corner cases of Lebesgue measure zero.
Our contributions can be summarised as follows.
We provide a detailed non-asymptotic analysis of the dynamics of each hidden neuron throughout the training, and show that it applies whenever the initialisation scale À is below a precise bound which is polynomial in the network width m and exponential in the training dataset cardinality n. Moreover, our analysis applies for any input dimension d > 1, for any nt 2 d (otherwise exact learning of the teacher neuron may not be possible), for any m, and without assuming any specific random distribution for the initialisation. In particular, we demonstrate that the role of the overparameterisstion in this setting is to ensure that initially at least one hidden neuron with a positive last-layer weight has in its active half-space at least one training point.
We show that, during a first phase of the training, all active hidden neurons with a positive last-layer weight get aligned to single direction which is positively correlated with all training points, whereas all active hidden neurons with a negative last-layer weight get turned away from all training points so that they deactivate. In contrast to the orthogonal dataset case where the sets of training points that are in the active half-spaces of the neurons are essentially constant during the training. in correlated setting this first phase in general consists, for each neuron, of a different sequence of stages during which the cardinality of the set of training points in its active half-space gradually increases decreases, respectively.
We show that, during the rest of the training, the bundle of aligned hidden neurons with their last-layer weights, formed by the end of the first phase, grows and turns it travels from near the origin to near the teacher neuron, and does not separate. To establish the latter property, which is the most involved part of this work, we identify a set in predictor space that depends only on and the training dataset, and prove: first, that the trajectory of the bundle stays inside the set; and second, that this implies that the directional gradients of the individual neurons are such that the angles between them are non-increasing.
We prove that, after the training departs from the initial saddle, which takes time logarithmic in and linear in d, the gradient satisfies Polyak-Lojasiewicz inequality and consequently the loss converges to zero exponentially fast.
We prove that, although for any fixed À the angles in the bundle of active hidden neurons do not in general converge to zero as the training time tends infinity, if we let À tend to zero then the networks to which the training converges have limit: a network of rank 1, in which all non-zero hidden neurons are positive scalings of the teacher neuron and have positive last- weights. This establishes that gradient flow from an infinitesimal initialisation is implicitly biased to select interpolator networks of minimal rank. Note also that the limit network is identical in predictor space to the teacher neuron.
We show that, surprisingly, among all networks with zero loss, there may exist some whose Euclidean norm is smaller than that of any network of rank 1. Moreover, we prove that this is the case if and only if a certain condition on angles determined by the training dataset satisfied. This result might be seen as refuting the conjecture of Boursier et al. [2022, section 3.2] that the implicit bias to minimise Euclidean parameter norm holds beyond the orthogonal setting, and adding some weight to the hypothesis of Razin and Cohen [2020]. The counterexample networks in our proof have rank and make essential use of the ReLU non-linearity
We perform numerical experiments that indicate that the training dynamics and the implicit bias we theoretically established occur in practical settings in which some of our assumptions are relaxed. In particular, gradient flow is replaced by gradient descent with realistic learning rate,
3

---

the initialisation scales are small but not nearly small as in the theory, and the angles between the teacher neuron and the training points are distributed around ,7 /4.
We further discuss related work, prove all theoretical results, and provide additional material experiments, in the appendix.
Preliminaries
n). ||o|| for the Euclidean length of a vector v, V = e/|lo|| for the normalised vector, <0,,v') = arccos(w w') for the angle between and v', and
Notation. We write: [n]] for the set {I,...,
vn = (Ei= B.v, 31,..., Bn 2 0} for the cone generated by vectors u1...., Un-
One-hidden layer ReLU network. For an input a E RR, the output of the network is
ha(x) = - aww]aa)
where m is the width, the parameters 0 = (a, W) E Rd x Rdx consist of last-layer weights
= [a....... aml and hidden-layer weights W = [W]..... w w.l and (u) = max(u, 0} is the ReLU function.
Balanced initialisation.
For all j E [m] let
w = Az
of = sy == 9
where À > O is the initialisation scale, 2j E R. (0), and 8, E {+1)
A precise upper bound on À will be stated in Assumption 2.
We regard the initial unscaled hidden-layer weights 2j and last-layer signs 8j as given, without assuming any specific random distributions for them. For example, we might have that each zj consists of d independent centred Gaussians with variance 1 and each is uniform over (+1)-
dm
We consider only initialisations for which the layers are balanced, i.e. [a]] ||we|| for all j E [m]] Since more generally each difference (ag)²- ||uo² || constant throughout training [Du, Hu, and Lee, 2018, Theorem 2.1] and we focus on small initialisation scales that tend to zero, this restriction
(which is also present in Boursier et al. [2022]) is minor but simplifies our analysis.
Rd and the training dataset Neuron-labelled correlated inputs. The teacher neuron
((D;, C (IRd (0}) R are such that for all i we have
= o xx))
L(0", x.) 7/4.
In particular, since the angles between o* and the training points æ; are acute, each label y, positive.
To apply our results to network with biases in the hidden layer and to teacher neuron with bias, one can work in dimension d' and extend the training points
Mean square loss gradient flow. For the regression task of learning the teacher neuron by the one-hidden layer ReLU network, we use the standard mean square empirical loss
T((0)
1 2m Σe (yr hax)))))
Our theoretical analysis concentrates training by gradient flow, which from initialisation as above evolves the network parameters by descending along the gradient the loss by infinitesimal steps in continuous time [Li, Tai, and E, 2019]. Formally, we consider any parameter trajectory 0:: [0, xx) - Ih' x m that is absolutely continuous on every compact subinterval, and that satisfies the differential inclusion
dØ adt/dtt -8L( for almost all o0),
where ØL denotes the Clarke [1975] subdifferential of the loss function (which is locally Lipschitz).

---

We work with the Clarke subclifferential, which is a generalisation of the gradient, because the ReLU activation is not differentiable at which causes non cum-dffferentabbiity of the loss function [Bolte, Daniilidis, Ley, and Mazet, 2010]. Although it follows from our results that, in our setting. the derivative the ReI.U can be fixed as o (0) Appendix DJ, and the gradient flow trajectories are uniquely defined, that is not priori clear; hence we work with the unrestricted Clarke subdifferential of the ReLU, We also remark that, in other settings, o' (0) cannot be fixed in this way due to gradient flow subtrajectories that correspond to gradient descent taggaagg along a ReLU boundary (cf. e.g. Maennel et al. [2018, section 9.4]).
like in the orthogonal case [Boursier et al., 2022,
Basic observations. We establish the formulas for the derivatives of the last-layer weights and the hidden neurons; and that throughout the training, the signs of the last-layer weights do not change, and their absolute values track the norms of the corresponding hidden neurons. The latter property holds for all times i by continuity and enables us to focus the analysis on the hidden neurons.
Proposition 1. For all j E [m]] and almost all t E [0, 00) we have:
(i) day. w/ T 9 and dwy o² gز. where وو E her (2x1) (o x;) xi (ii) af sj [o 0.
The definition in part (i) of the vectors  that govern the dynamics a membership because the subdifferential of the ReLU at the set of all values between and 1, i... (0) = [0, 1].
3 Assumptions
To state our assumptions precisely, we introduce some additional notation. Let
(v) ii [n]] o aa > 0} lo(v) ii [n] v x; = =0 L(v) (i [n] < <
denote the sets of indices of training points that are, respectively, either inside or the boundary or outside of the non-negative half-space of vector v. Then let
J = ( E [m] L(2,) + 0 A 8j +1}
E [m]
4(z,) + 8, -13
be the sets of indices of hidden neurons that are initially active on at least one training point and whose last-layer signs are, respectively, positive or negative. Also let
X [.1,
Fr,
Y = = E
denote the matrix whose columns are all the training points, and the sum of all training points whose indices are in a set /, weighted by the corresponding labels and divided by n.
Moreover we define, for each j E J4 U J_, continuous trajectory at in Rd by
/ = sy syl1a)117
for all f (0)
Thus, starting from the unscaled initialisation æ, of the corresponding hidden neuron, a follows dynamics obtained from that of w in Proposition 1 (i) and (ii) by replacing the vector 9 by 7r (af)) which amounts to removing from 9 the network output terms and the activation boundary summands. These trajectories will be useful yardsticks in our analysis of the first phase of the training.
Assumption 1. (i) d > sp
Dn. Rd, and ||o*|| =
(ii) J 0, I0(2,)) = 0 for all j E [m]. and L(z (m)) > for all E J_
(iii) T..... In are distinct, the eigenvalues of Lxx" are distinct, and v² does not belong to span of fewer than d eigenvectors of 1 X
n
(iv) [[o(aa)] < for all j E U and all [0,
(v) For all E [m] and all 0 < T T', for all (T,T') we have (ww))= = Io Io(w?'') # and Io(w))) 4(w²") 0. then for all t > T we have w/ w
5

---

This assumption is very mild. Part (i) excludes the trivial univariate case without biases (for univariate inputs with biases one needs d 2), ensures that exact learning is possible, and fixes the length of the teacher neuron to streamline the presentation. Part (ii) assumes that, initially: at least one hidden neuron with positive last-layer weight has in its active half-space at least one training point, no training point is at a ReLU boundary, and no hidden neuron with negative last-layer weight is perfectly aligned with the Yin vector; this holds with probability at least - (3/4)" for
any continuous symmetric distribution of the unscaled hidden-neuron initialisations, e.g. 2j Ltd.
(O, 7m - Id). and the uniform distribution of the last-layer signs sj Lid, (( Parts (iii and (iv) exclude corner cases of Lebesgue measure zero; observe that X is positive-definite and that (iv) rules out a yardstick trajectory encountering two or more training points its half-space boundary at exactly the same time. Part (v) excludes some unrealistic gradient flows that might otherwise be possible due to the use of the subdifferential: it specifies that, whenever neuron deactivates (i.e. all training points exit its positive half-space), then it stays deactivated for the remainder of the training.
Before our next assumption, we define several further quantities. Let 1 > ... > d) > denote the eigenvalues of 1 xXX" and let U...... Ue denote the corresponding unit-length eigenvectors such that v" = Σ k= un for some "i vi....,, v2 > 0. Also, for each j E J J J_, let nı := -1_,, xy (z,)l be the number of training points that should enter into or exit from the non-negative half-space along the trajectory aj depending on whether the sign 8y is positive or negative (respectively), and let
12
3 Laa), ((((())) for all t oo) such that 4(aa)) + 0
be the evolving angle between a² and the vector governing its dynamics (if any). Then the existence of the times which the entries or the exits occur confirmed in the following.
Proposition 2. For all j E J+ U J- there exist unique enumeration i) ....... of I I (zz) and unique 0- 7. 7) < .... <..TTT such that for all E [nz]:
(i) L,, (a)) L, (z,) U U.... (8)....., 3or all t E (1) ,75);
(i) Lo(a)) 0 for all e (T/1) .T)) and to lo(a))) {if).
Finally we define two measurements of the unscaled initialisation and the training dataset, which are positive thanks to Assumption and which will simplify the presentation of our results.
mineetm] | ll. ming D. Te, minketa-ul(/m (d 1), Vnd.
minseldi 2 Vd, minsemmi ||, minjez. cos pf. minseJ_ Siiie___snnn/ 49: 8 min
E JUL A & [n,]
min Ø
E
A Ate IT 4- ,T) i [n]
minjeJ a² Etd.
A Ai i A (f (1
min of |je 4U ^ le [n,]]
A max(maxxetn]]]l))) maxje[m]]lz] 1}.
Assumption 2. 0 0<E and X > (m /80) 3/5
The quantity e introduced here has no effect on the network training, but a parameter of our analysis, so that varying it within the assumed range tightens some of the resulting bounds while loosening others. The assumed bound on the initialisation scale À is polynomial in the network width m and exponential in the dataset cardinality n. The latter is also the case in Boursier et al. [2022], where the bound was stated informally and without its dependence on parameters other than m and n.
First phase: alignment or deactivation
We show that, for each initially active hidden neuron, if its last- sign is positive then it turns to include in its active half-space all training points that were initially outside, whereas if its last-layer

---

sign is negative then it turns to remove from its active half-space all training points that were initially inside. Moreover, those training points cross the activation boundary in the same order as they cross the half-space boundary of the corresponding yardstick trajectory a². and at approximately the same times (ef. Proposition 2).
Lemma 3. For all; E J+ JJ_ there exist unique 0 -- -11 193()) <...
Ei such that for all & E [nz]]
(i) (uy(w))) 1, (2)) (t).... 13 for all E ,9111)))
and to (wx) {85};
(ii) Io(w)) = 0 for all t E
(iii) 1r - 1ン $ x (1+ 3,))
The preceding lemma is proved by establishing, for this first phase of the training, non-asymptotic upper bounds on the Euclidean norms of the hidden neurons and hence on the absolute values the network outputs, and inductively over the stage index f, on the distances between the unit-sphere normalisations of a and w/. Based on that analysis, we then obtain that each negative-sign hidden neuron does not grow from its initial length and deactivates by time To = max T/ + 1.
Lemma 4, For all j E J_ we have:
|| To || S X |
w/ w To for all L 2 To
We also obtain that, up to a later time Ti eln(1/A)/|]/ each positive-sign hidden neuron: grows but keeps its length below 2||z,| X²== continues align to the vector 7 up a cosine of least - X5, and maintains bounded by 1--3e the difference between the logarithm of its length divided by the initialisation scale and the logarithm of the corresponding yardstick vector length.
Lemma 5. For all j E J+ we have:
| || < 2||2,||
T
Jin 21-X
X
In [ala I1 In | S 3133
Second phase: growth and convergence
We next analyse the gradient flow subsequent to the deactivation of the negative-sign hidden neurons by time To and the alignment of the positive-sign ones up to time Ti, and establish that the loss converges zero at rate which is exponential and does not depend on the initialisation scale X.
Theorem 6. Under Assumptions and 2, there exists time T2 < (n(1/A)(4++)))) +)dd² f such that for all 2 we have T(()Tatt) < 0.5 A e--00.15
In particular, for = 1/4 and X = (mnn))942/0 3/C
(cf. Assumption 2), the first bound in
Theorem 6 becomes T2 < (In + n nlnn) d. 17 27 A /50
The proof of Theorem 6 is in large part geometric, with a key role played by a set S S1 U... in predictor space, whose constituent subsets are defined as
S:
UKRAK
2x A tr A
(V A V k. A E
1=1
ISkCE
eskck'd
where the individual constraints are follows (here To = oc so that e.g. 2n0
= 0):
V/ Dx: 1 <
T
Vi 1/
nh U/ VV
Te:
<
51
2
2np 1x 1/2
1
my.
E: 0 XX (v" - v) > 1//3
Vk <
1/k
2nk
Thus S is connected, open, and constrained by 3 to be within the ellipsoid T X (v" v) =0 which is centred at n¹ boundary surfaces.
2 with the remaining constraints slicing off further regions by straight or curved
7

---

In the most complex component of this work, we show that, for all t 2 Ti, the trajectory of the sum o' := Eje,, djwrj of the active hidden neurons weighted by the last layer stays inside S, and the cosines of the angles between the neurons remain above - 4x This involves proving that each face of the boundary of S is repelling for the training dynamics when approached from the inside; we remark that, although that is in general false for the entire boundary of the constraint E, it is in particular true for its remainder after the slicing off by the other constraints. We also show that all points in S are positively correlated with all training points, which together with the preceding facts implies that, during this second phase of the training. the network behaves approximately like a linear one-hidden layer one-neuron network. Then, as the cornerstone of the rest of the proof, show that, for all & T2, the gradient of the loss satisfies
Solyak-Eojasiewiez inequality 2nal Yoalll L(0"). Here T2 = inf(l 2 Ti ui/0 2 1/2] is a time by which the 5tn
Il >
network has departed from the initial saddle, more precisely when the first coordinate vf of the bundle vector o' with respect to the basis consisting of the eigenvectors of the matrix X X crosses the "
half-way threshold to the first coordinate 'f of the teacher neuron.
The interior of the ellipsoid in the constraint E actually consists of all vectors that have an acute angle with the derivative of the training dynamics in predictor space, and the "padding" of xe/3 is present because the derivative the bundle vector vf is "noisy" due to the latter being made up of the approximately aligned neurons. The remaining constraints delimit the subsets Si, ..... Sa of the set S, through which the bundle vector V, passes in that order, with each unique "handover" from St to S happening exactly when the corresponding coordinate v/ exceeds its target vs. The is needed to ensure the repelling for the training dynamics.
non- non-linearity of the constraints V ".
Implicit bias of gradient flow
Let us denote the set of all balanced networks by
+ = {(a, W) E R x add Vjj E [m]] |ayl = ||w,||}
and the subset in which all non-zero hidden neurons are positive scalings of v", have positive last-layer weights, and have lengths whose squares sum up to ||o*|| = 1, by
O.. = {aa W) E e
|
A Vj E [m]: wy 7 0
1 A aj 0))
Our main result establishes that, as the initialisation scale À tends to zero, the networks with zero loss to which the gradient flow converges tend to network in .,.. The explicit subscripts indicate the dependence on λ of the parameter vectors. The proof builds on the preceding results and involves a careful control of accumulations of approximation errors over lengthy time intervals.
Theorem 7. Under Assumptions and 2, L lim 0¹) 0 and lim lim 0', E O... to00
x t-000
7 Interpolators with minimum norm
To compare the set θ.. of balanced rank-1 interpolator networks with the set of all minimum-norm interpolator networks, in this section we focus on training datasets of cardinality d, we assume the network width is greater than 1 (otherwise the rank is necessarily 1), and we exclude the threshold case of Lebesgue measure zero where M defined below in terms of angles between the teacher neuron and vectors in any two cones generated by different generators of the dual of the cone of all training points.
The latter measurement of the training dataset is
Let [X Xal == X and
$ C [d]
M max cos <(p. 9) sin <(p, v*)
A 0 p cone Xx k E K} l $ K}
^ 0 + q E cone
Assumption 3. d, > and M + 0.
We obtain that, surprisingly, .,, equals the set of all interpolators with minimum Fuclidean norm M < 0, but otherwise they are disjoint.
8

---

Centred training dataset
Uncentred training dataset
max. angle b. active neurons
10a
10a
109
100
10 2
10
10
10-4
10-6 6
10-6
10a
10
10
10
10-6
10
10"
10a
109
10-2
10
10 10-6
10
256
d 1024
Dependence of the maximum angle between active hidden neurons on the initialisation scale X, for two generation schemes of the training dataset and range of input dimensions, at the end of the training, Both axes are logarithmic, and each point plotted shows the median over five trials.
Figure 1:
Theorem 8. Under Assumptions and 3:
(i) if M < 0 then Ou- is the of all global minimisers of |1012 subject L(0) 0: (ii) if M then no point O global minimiser of @|| subject to L(0)
For each of the two cases, provide family of example datasets in the appendix. We remark that sufficient condition for M < O to hold is that the inner product of any two distinct rows X of the inverse of the dataset matrix X is possiiiiee i.c. that the inverse of the Gram matrix of the dataset (in our setting this Gram matrix is positive) is a Z-matrix (cf. e.g. Fiedler and Pták [1962]). Also, the training points were orthogonal then all the cos <(p, q) terms in the definition of M would be zero and consequently we would have M < 0; this is consistent with the result that, per sign class of the training labels in the orthogonal setting, minimising the Buclidean norm of interpolators coincides with minimising their rank [Boursier et al., 2022, Appendix CJ.
8 Experiments
We consider two schemes for generating the training dataset, where Sd-1 the unit sphere in Rdd
We sample y from (Sd-1), then sample Ti...., Ea from ((u, ( where 1, and finally set v* = μu. This distribution has the property that, high dimensions, the angles between the teacher neuron 8" and the training points æ; concentrate around π /4. We exclude cases where some these angles exceed π 7/2.
Centred:
Uncentred: This the same, except that we use p = / 1, sample one extra point Zo. and finally set T.. Here the angles between v" and æ; also concentrate around π 7/4 in high dimensions, but the expected distance between v" and şe is vp.
For each of the two dataset schemes, we train one-hidden layer ReL.U network of width m 200 by gradient descent with learning rate 0.01, from balanced initialisation such that z; itd. N'O0, 2m Ia)
and 8j i.dd 14 (1).), and for range of initialisation scales À and input dimensions d.2
We present in Figure some results from considering initialisation scales = 42,4' 41 and input dimensions d 4, 16, 64, 256, 1024, where we train until the number of iterations
4- 1--2--4-1
4 4-1
We are making code to run the experiments available at htttp:://gite www./o/grrttmm/ahaallllllllaoole m/shallov.
ReLU dynamics.

---

Training loss
Test loss
10
10-7
10
10 10-17
10-15
10-27
10
10-22
22
10
10a
10*
106
10a
0
5
10
10 1
1.5
10? 2 107
A= 4
Figure 2: Evolution of the training loss, and of an outside distribution test loss, during training for an example centred training dataset in dimension 16 and width 200. The horizontal axes, logarithmic for the training loss and linear for the test loss, show iterations. The vertical axes are logarithmic.
reaches 2 107 or the loss drops below 10-9. The plots are in line with Theorem 7, showing how the maximum angle between active hidden neurons at the end of the training decreases with A.
Figure 2 on the left illustrates the exponentially fast convergence of the training loss (cf. Theorem 6), and on the right how the implicit bias can result in good generalisation. The test loss computed over an input distribution which is different from that of the training points, namely we sample 64 test inputs from NO, Ia). These plots are for initialisation scales 4-2 ...... 77.4"
Conclusion
We provided a detailed analysis of the dynamics of training shallow ReLU network by gradient flow from small initialisation for learning a single neuron which is correlated with the training points, establishing convergence to zero loss and implicit bias to rank minimisation in parameter space. We believe that in particular the geometric insights we obtained order to deal with the complexities of the multi-stage alignment of hidden neurons followed by the simultaneous evolution of their norms and directions, will be useful to community in the ongoing quest to understand implicit bias of gradient-based algorithms for regression tasks using non-linear networks.
major direction for future work is to bridge the gap between, on one hand, our assumption that the angles between the teacher neuron and the training points are less than π /44, and the other, the assumption of Boursier al. [2022] that the training points are orthogonal, while keeping a fine granularity of description. We expect this to be difficult because it seems to require handling bundles of approximately aligned neurons which may have changing sets of training points their active half-spaces and which may separate during the training. However, it should be straightforward to extend our results to orthogonally separable datasets and two teacher ReLU neurons, where each of the latter has arbitrary sign, labels one of the two classes of training points, and has angles less than 5 /4 with them; the gradient flow would then pass close to a second saddle point, where the labels of one of the classes have been nearly fitted but the hidden neurons that will fit the labels of the other class are still small. We report on related numerical experiments in the appendix.
We also obtained condition on the dataset that determines whether rank minimisation and Euclidean norm minimisation for interpolator networks coincide or are distinct. Although this dichotomy remains true if the т /4 correlation bound is relaxed to π 7/2, the implicit bias of gradient flow in that extended setting is an open question. Other directions for future work include considering multi-neuron teacher networks, student networks with more than one hidden layer, further non-linear activation functions, and gradient descent instead of gradient flow; also refining the bounds on the initialisation scale and the convergence time.
10

---

Acknowledgments and Disclosure of Funding
We acknowledge the Centre for Discrete Mathematics and Its Applications at the University of Warwick for partial support, and the Scientific Computing Research Technology Platform at the University of Warwick for providing the compute cluster on which the experiments presented in this paper run.
References
Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E. Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent. In ICML, pages 468-477, 2021.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and classical variinar trade-off. Proc. Natl. Acad. Sci., 116(32):55849-15588 2019. 1
Jérôme Bolte, Aris Daniilidis, Olivier Ley, and Laurent Mazet. Characterizations of Lojasiewicz inequalities:
subgradient flows, talweg, convexity. Trans. Amer. Math. Soc., 362(6):3319 33333333333333,,, 2010. 5
Etienne Boursier and Nicolas Flammarion. Penalising the biases in regularisation enforces sparsity. CoRR, abs/2303.01333 2023. Accepted to NeurlPS 2023.
Etienne Boursier, Loucas Pillaud- Vivien, and Nicolas Flammarion. Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs. In NeurfPS, 2022, 2,
9, 10
Frank H. Clarke. Generalized gradients and applications. Trans. Amer Math. Soc., 205:247-262, 1975. 4
Damek Davis, Dmitriy Drusvyatskiy, Sham M. Kakade, and Jason D. Lec. Stochastic Subgradient Method Converges on Tame Functions. Found. Comput. Math., 2091):119-154, 2020.
Simon S. Du, Wei Hu, and Jason D. Lee. Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced. In NeurlPS, pages 382-393, 2018. 4
Matthias Englert and Ranko Lazić. Adversarial Reprogramming Revisited. In NeurlPS, 2022.
Tolga Ergen and Mert Pilanci. Convex Geometry and Duality Oxer-parameterizeed Neural Networks. J. Mach.
Learn. Res,, 22(212))1 2021.
Mathieu Even, Scott Pesme, Suriya Gunasekar, Nicolas Flammarion. (S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability, CoRR, abs/2302.08982, 2023. Accepted to NeurlPS 2023.
Miroslav Fiedler and Vlastimil Pták. On matrices with non-positive off-diagonal elements and positive principal minors. Caechoslovak Mathematical Journal, 12(3):382-400, 1962.
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic Learning of a Single Neuron with Gradient Descent. In NewrlPS, 2020.
Spencer Frei, Gal Vardi, Peter L. Bartlett, and Nathan Srebro. Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization. In COLT, pages
2023a.
Spencer Frei, Vardi, Peter L. Bartlett, and Nathan Srebro. The Edggle-Fdged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks. CoRR, abs/2303.01455 2023b. Accepted to NeurIPS 2023.
Spencer Frei, Gal Vardi, Peter L.. Bartlett, Nathan Srehro, and Wei Hu. Implicit Bias in Leaky ReLUU Networks Trained on High- figh--Dimnsiioal Data. In ICLR, 2023c.
Suriya Gunasekar, Blake E. Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit Regularization in Matrix Factorization. In NeurIPS, pages 6151-6159, 2017. 2
Niv Haim. Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing Training Data From
Trained Neural Networks. In NeurIPS, 2022. 2
Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, and Franck Gabriel. toall-ttt-Sadlle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity. CoRR, 1ass/106611933. 2021. 2

---

Arnulf Jentzen and Adrian Riekert. Convergence analysis for gradient flows in the training of artificial neural networks with ReLU activation. Math. Anal. Appl., 11761) 2023.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In NewrlPS, 2020.
Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon S. Du, and Jason D. Lee. Understanding Incremental Learning of
Gradient Descent: A Fine-grained Analysis of Matrix Sensing. In JCML, pages 15200-15238, 2023. 2
Sangmin Lee, Byeongsu Sim, and Jong Chul Ye. Magnitude and Angle Dynamics in Training Single ReLU
Neurons. CoRR, abs/2209. 13394, 2022.
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms Mathematical Foundations, Mach. Learn. Res,, 20(40): 447 2019. 4
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning. In ICLR, 2021.
Kaifeng Lyu and Jian Li. Gradient Descent Maximizes the Margin Homogeneous Neural Networks. In ICLR, 2020.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang. and Sanjeev Arora. Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias. In NeurlPS, pages 12978-12991, 2021.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly, Gradient Deseent Quantizes ReLU Network Features. CoRR, abs/ Abs/1803308837, 2018. 5,5
Odelia Melamed, Gilad Yehudai, and Gal Vardi. Adversarial Examples Exist in Two-Layer ReLU Networks for Low Dimensional Data Manifolds. CoRR, abs/2303. 00783, 2023. Accepted to NeurlPS 2023.
Hancheng Min, René Vidal, and Enrique Mallada. Early Neuron Alignment in Two-layer ReLU Networks with Small Initialization. CoRR, abs/2307. 020223777181111 12851, 2023.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring Generalization in Deep Learning. In NeurlPS, pages 5947-5956, 2017.
Greg Ongie, Rehecca Willett, Daniel Soudry, and Nathan Srebro. A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case. In ICLR, 2020.
Scott Pesme and Nicolas Flammarion. Maddle-to-Saddle Dynamics in Diagonal Linear Networks. CoRR, abs/2334.00488. 2023. Accepted to NeurlPS 2023.
Mary Phuong and Christoph H. Lampert. The inductive bias of ReLU networks orthogonally separable data. In ICLR, 2021. 3
B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4) 1963.
Noam Razin and Nadav Cohen. Implicit Regularization in Deep Learning May Not Be Explainable by Norms. In NewrlPS, 2020.
Roei Sarussi, Alon Brutzkus, and Amir Globerson. Towards Understanding Learning in Neural Networks with Linear Teachers. In /CML, pages 9313-9322, 2021.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In COLT, pages 2667-2690, 2019.
Lawrence Stewart, Francis Bach, Quentin Berthet, and Jean- Sean-Philippe Vert. Regression as Classification: Influence of Task Formulation on Neural Network Features. In AISTATS, pages 11563 -1582, 2023.
Nadav Timor, Gal Vardi, and Ohad Shamir. Implicit Regularization Towards Rank Minimization in ReLU Networks. In ALT, pages 1429-1459, 2023. 2
Gal Vardi. On the Implicit Bias in beep-Lennnng Algorithms. Commun. ACM, 66(6):86 93, 2023.
Gal Vardi and Ohad Shamir. Implicit Regularization in ReLU Networks with the Square Loss. In COLT, pages 4224 4258, 2021. 2
Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning Single Neuron with Bias Using Gradient Descent. In NewrIPS, pages 28690-286778 28700, 2021.
12

---

Gal Vardi, Gilad Yehudai, and Ohad Shamir. Gradient Methods Provably Converge to Non-Robust Networks. In NeurIPS, 2022. 2
Mingze Wang and Chao Ma. Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networks. In NeurIPS, 2022.
Yifei Wang and Mert Pilanci. The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge Extreme Points of the Dual Convex Program. In ICLR, 2022. 3
Blake F. Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry. and Nathan Srebro. Kernel and Rich Regimes in Overparametrized Models. In COLT, pages 3635-3673, 2020.
Weihang Xu and Simon Du. Over- EverrParameetrrization Exponentially Slows Down Gradient Descent for Learning Single Neuron. COLT, pages 1155 1198, 2023.
Gilad Yehudai and Ohad Shamir. Learning Single Neuron with Gradient Methods. In COLT, pages 3756-3786. 2020.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view implicit hias in training linear neural networks. In ICLR, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun, ACM, 64(3):107-115, 2021.
13


Reviews:
[{"review_id": "LdkM7bWDr1", "reviewer": "Reviewer_6KPF", "summary": "Convergence and implicit bias of non-linear networks is an important open question in deep learning theory.  The paper studies these questions in the case of regression with ReLU networks with a single teacher neuron. It proves that at a vanishing initialization scale the student neurons align with the teacher (or gets deactivated). It also shows an interesting counter example such that the implicit bias as initialization tends to zero need not be a minimum norm interpolator. ", "questions": "a) It is mentioned in the contributions there exists a case where that the minimum norm interpolator is rank 2 instead of rank 1. Can the authors comment how the non-linearity plays a role here? Can the authors a simple example providing a more detailed illustration?", "limitations": "a) The experiments are conducted with synthetic data and only in the case of single teacher neuron. It would interesting some empirical evidence in the case of more than one teacher if the phenomenon characterized in the paper holds in more generality. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "a) Going beyond the orthogonal data, the paper proposes an interesting setting which helps analyse the case of correlated inputs. \n\nb) The geometric technique to study the convergence after the alignment phase is novel. \n\nc) The scenario proposed where the implicit bias as $\\lambda \\to 0$ is a rank minimizing one instead of a minimum norm interpolator is a very interesting contribution. ", "weaknesses": "a) The setting is simplified: there is only a single teacher neuron and all the labels are only positive. It directly that neurons (at least yardstick neurons) with negative last layer decreases in norm. The assumption that the inputs are correlated further ensures that they are deactivated. This makes the analysis easier.  \n\nb) The technical analysis follows the same strategy as Boursier et. al. Some aspects are easier as there is only one saddle to escape. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> b) The technical analysis follows the same strategy as Boursier et. al. Some aspects are easier as there is only one saddle to escape.\n\nWe think that the presence of the negative labels and the consequent second saddle in Boursier et al. did not introduce major difficulties in that work, i.e. that the main technical achievements in Boursier et al. lie elsewhere in that work.  Indeed, the proofs of the technical results that take care of the negative labels in Boursier et al. (Lemma 8 and Lemma 11) proceed mostly along the same lines as the proofs of the corresponding results about the positive labels (Lemma 7 and Lemma 10, respectively). \n\nWe remarked in the second paragraph of Appendix A that our results should be straightforward to extend to a setting with an orthogonally separable dataset labelled by two teacher neurons, which would allow both positive and negative labels, and result in a second saddle.  We chose not to develop that case in the paper because it would be a relatively shallow addition from a technical point of view.  Please see the bottom plot in the attached PDF for an experimental illustration. \n\nWe suggest that, in technical aspects (proofs), our correlated setting is considerably more difficult to analyse compared to the orthogonal setting of Boursier et al.  In particular, our handling of the second phase during which the active neurons simultaneously grow and turn involved a novel geometric technique. \n\n> a) It is mentioned in the contributions there exists a case where that the minimum norm interpolator is rank 2 instead of rank 1. Can the authors comment how the non-linearity plays a role here? Can the authors a simple example providing a more detailed illustration?\n\nA family of examples is provided in Example 36 (case $\\mathcal{M} > 0$) in Appendix H, for any dimension $d > 2$.  The core of the construction are three data points, e.g. $(16, 0, 0)$, $(16, -4, 1)$, $(16, 4, 1)$, and a teacher neuron, e.g. $(0.8, 0, 0.6)$, whose norm is $1$.  In this instance, the labels are therefore $12.8$, $13.4$, $13.4$, respectively.  However the same labels are produced by a sum of two ReLU neurons $(0.8, 0.05, 0.4)$ and $(0, -0.1, 0)$, whose sum of norms is approximately $0.896 + 0.1 = 0.996 < 1$.  In order for the second neuron to contribute to the label of just one data point out of three, non-linearity is essential.  Without it the sum of the two neurons would label the third data point by $13$ rather than $13.4$.  It is straightforward to obtain from this example a balanced one-hidden layer ReLU network with two neurons which thereby has smaller norm than any interpolator of rank $1$. \n\nIf you think it would be helpful, we are happy to include a short example along these lines in the main paper? \n\n> a) The experiments are conducted with synthetic data and only in the case of single teacher neuron. It would interesting some empirical evidence in the case of more than one teacher if the phenomenon characterized in the paper holds in more generality.\n\nLearning a multi-neuron ReLU teacher network is known to be challenging to analyse.  Already in a uni-variate setting with biases, it is easy to come up with example datasets of only a few data points for which during the training several bundles of neurons emerge that simultaneously change their norms and directions, and apparently interact significantly with each other.  Such an example was provided by Boursier et al. in their Figure 4 in Appendix A.1.  We believe that our work provides a substantial and important step towards understanding such phenomena in arbitrary dimension, where we focused on alignment of the neurons and their simultaneous growth and turning, leaving for future work significant interactions between multiple bundles of neurons. \n\nPlease see the middle two and the bottom plot in the attached PDF for some results from additional experiments with two teacher neurons.  For small scales of the noise used to generate the synthetic datasets (where the smallest scales are such that the angles between the data points and the corresponding teacher concentrate around $\\pi / 4$), the phenomena we identified theoretically still seem to hold, where the training passes near a second saddle point as we outlined in the second paragraph of Appendix A."}, {"review_id": "j2lM0rW9qU", "reviewer": "Reviewer_PDpC", "summary": "This paper studies how a two-layer ReLU network can fit a single neuron. The authors consider the case where all \ntraining points are correlated with the teacher neuron and show that gradient flow from small initialization can \nconverge to a zero-loss solution. \nThey divide the training into two stages. In the first stage, the neurons are small and will align with the teacher \nneuron or deactivate, depending on the sign of the output weight, and in the second stage, the aligned neurons will grow \nand fit the target function. \nIn addition, they show that as the initialization scale goes to $0$, gradient flow converges to a rank-$1$ solution. ", "questions": "* Is it possible to adapt your strategy to the Gaussian inputs case? This seems to be a more natural generalization to \n  the orthogonal input setting. \n* Could you intuitively explain the meaning of the conditions in the definition of $S_l$?", "limitations": "This is a theoretical work and I cannot see any potential negative societal impacts. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Overall, the presentation is clear, and the main text is relatively easy to follow (see the weakness part of the \n  review for some minor issues.) \n* The use of the yardsticks $\\omega_j$ is interesting.\n* The geometric argument for the second phase seems novel and may be of independent interest. \n* Theorem 8, which shows the set of balanced rank-1 interpolating networks and the set of minimum-norm interpolating \n  networks can be the same or disjoint, depending on a certain quantity, is surprising. ", "weaknesses": "* The presentation is overall clear, but the notations are cumbersome. \n  * For example, I don't think using $w$ and $\\omega$ simultaneously is a good idea, especially when they co-occur a lot \n    and represent two closely related objects. \n  * The detailed definitions of $\\delta$ and $S_l$ can be moved into the appendix, and define them informally in the \n    main text and maybe briefly explain how small can $\\delta$ be and the intuition behind $S_l$. \n* I personally don't like the $\\exp(-n)$ initialization scale, though I will accept it as it has been used in previous \n  works. I think it is somewhat cheating because, with it, you can make sure the norm of the neurons is sufficiently small \n  so that you can ignore them for any polynomially long time. \n* The setting is quite restricted and unrealistic as it requires the angle of all inputs and the teacher vector to be \n  smaller than $\\pi / 4$. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In the first stage, the neurons are small and will align with the teacher neuron or deactivate, [...]\n\nJust to clarify that the alignment in the first phase is with the vector $\\mathbf{\\gamma}\\_{[n]} = \\frac{1}{n} \\sum_{i = 1}^n y\\_i \\mathbf{x}\\_i$, whose direction is in general different from that of the teacher neuron.  (E.g. the teacher neuron might even be outside of the cone spanned by the data points.)  This is important because it means that, after the first phase, the aligned neurons may need to change direction significantly to fit the target function.  In Example 32 at the end of Appendix F, we show an example run in which the alignment with $\\mathbf{\\gamma}\\_{[n]}$ happens relatively early while the norm is relatively small, whereas alignment with the teacher neuron $\\mathbf{v}^*$ happens only towards the final convergence after the growth of the norm.\n\n> The presentation is overall clear, but the notations are cumbersome. [...]\n\nWe are happy to implement these suggestions.  The intention behind the $\\mathbf{w}$ and $\\mathbf{\\omega}$ notations was that their similar looks would remind the reader that they represent related objects, however thank you for pointing out that it may be confusing. \n\n> I personally don't like the $\\exp(-n)$ initialization scale, though I will accept it as it has been used in previous works. [...]\n\nThe exponential dependence of the initialisation scale on the dataset cardinality $n$ is indeed impractical when $n$ is not small.  However, we think it is worthwhile to analyse in detail even such small initialisation scales and to determine a bound under which the analysis holds, partly to provide a solid basis from which to investigate the border to another regime such as mean field or lazy.  It is encouraging that our numerical experiments paint a picture which broadly follows the patterns identified in our theoretical results even for initialisation scales that are significantly larger than our theoretical bound.  Relaxing that bound, and in particular seeking to reach polynomial dependence on $n$, is therefore an interesting direction for future work.  We expect one challenge will be that the first phase of the training will produce bundles of neurons that are not as tightly aligned as we can guarantee in this work. \n\n> The setting is quite restricted and unrealistic as it requires the angle of all inputs and the teacher vector to be smaller than $\\pi / 4$.\n\nPlease see our response to all the reviewers jointly. \n\n> Is it possible to adapt your strategy to the Gaussian inputs case? This seems to be a more natural generalization to the orthogonal input setting.\n\nWe expect that various parts of our submission could be adapted to the Gaussian inputs case, either for a population loss or for an empirical loss with a sufficiently large number of samples. \n\nXu and Du COLT 2023 considered learning a ReLU neuron by a ReLU network with Gaussian inputs, where only the hidden layer is trained and every last-layer weight is fixed to $1$.  Having a population loss over the Gaussian inputs makes some aspects of the training dynamics simpler than in our setting.  In particular, already the first phase aligns the neurons to the teacher. \n\nWe think it is worthwhile to consider finite datasets, especially in the context of seeking to determine the implicit bias of gradient-based algorithms for regression tasks, where a central question is what interpolants the training converges to in predictor space.  The results in this submission establish that, for any dimension $d > 1$ and in our correlated setting, $d$ linearly independent inputs (the algebraic minimum) suffice to learn the teacher neuron; and that the implicit bias is such that, as the initialisation scale tends to zero, exactly the teacher neuron is converged to and moreover with a network of rank $1$.  (In the orthogonal setting, the number of inputs is at most $d$.)  We suggest one of the main contributions of this work is a full account of the second phase of the training, which due to working with an empirical loss over a finite dataset (rather than a population loss over a spherically symmetric data distribution) may start with the bundle of neurons aligned to a direction which is far from that of the teacher. \n\n> Could you intuitively explain the meaning of the conditions in the definition of $\\mathcal{S}\\_\\ell$?\n\nThe entire set $\\mathcal S$ is open, bounded, and connected.  It is an invariant for the training dynamics in predictor space even when small noise is added to the derivative: namely, $\\mathcal{S}$ contains the trajectory of the bundle $\\mathbf{v}$ of neurons from the end of the alignment phase onwards, travelling from near the origin to near the teacher $\\mathbf{v}^*$, see e.g.  Example 30 (and Figure 3) in Appendix F. \n\nThe $\\Omega\\_k$, $\\Phi\\_\\ell$, and $\\Psi$ conditions control the dynamics: the ratios $\\nu\\_k / \\nu\\_k^*$ grow towards $1$ and then overshoot $1$, all sequentially one coordinate at a time: each component $\\mathcal{S}\\_\\ell$ basically contains the segment of the trajectory during which the $\\ell$th coordinate of the bundle grows towards its target, and the “handover” to $\\mathcal{S}\\_{\\ell + 1}$ (for $\\ell < d$) happens exactly at the point of the overshoot.  The coordinates, $\\nu\\_k$ and $\\nu\\_k^*$, are with respect to the basis consisting of the eigenvectors of $\\frac{1}{n} \\mathbf{X} \\mathbf{X}^\\top$. \n\nThe non-linearity of the $\\Psi\\_{k, k’}^\\uparrow$ constraint makes the boundary of the set $\\mathcal{S}$ repelling for the approximate training dynamics when approached from the inside. \n\nFinally, $\\Xi$ defines an ellipsoid of all vectors that have an acute angle with the derivative of the training dynamics in predictor space.  Moreover, $\\Xi$ adds a “padding” inside the boundary determined by the small quantity $\\lambda^{\\varepsilon / 3}$ to account for the approximate derivatives. \n\nIf you think it would be helpful, we shall add explanations along those lines to the paper."}, {"review_id": "zBd3sLY0t7", "reviewer": "Reviewer_ytEj", "summary": "The paper studies the problem of learning a single ReLU using a 2-layer ReLU network using gradient flow on both layers. The main assumption is that the data is correlated with the target neuron, while other milder assumptions are also used (e.g. specific initialization and spectral assumption on the data matrix). The main result is a two-phase convergence to a global minimum. Several experiments are also given.\n", "questions": "- What changes if we assume that the angle between the data samples and the target neurons is \\alpha, where \\alpha > \\pi/4?\n- What is the total convergence rate of gradient flow for learning a single neuron?\n- Is it possible to extend the result to gradient flow? or possibly SGD?\n- Is there an explicit condition on the dataset that can be given so that the set of interpolators also minimizes the norm of the predictor  \n", "limitations": "The authors do address adequately to the limitations of the paper, although I think it is important to elaborate more on the main assumption about the dataset.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The main convergence result is novel AFAIK, and shows an interesting convergence dynamic, where in the first phase the learned weights either align with the target neuron or deactivate, and in the second phase converge to a global minimum. \n- The connection between the global minima of the problem and the minimal norm solution in Section 7 is interesting and brings forward the question of whether minimizing the empirical loss results in a minimal norm solution, which was studied in previous works too (e.g. Vardi et al 2022).\n- The experimental part shows empirically the behavior of the angles between the learned weights and the target neuron.\n", "weaknesses": "- The assumption that the data is correlated with the target neuron is pretty strong. The motivation for taking an angle of at most \\pi/4 between each data point and the target neuron is also not clear. What changes if the angle is larger\\smaller? I think the authors should elaborate more on this assumptions, and what breaks if it is not assumed. To compare, other papers about studying a single neuron usually consider a data distribution spread in all directions (e.g. Frei et al. 2020, Yehudai & Shamir 2020).\n- The presentation of the main result is not clear. I think there should be a single Theorem stating the convergence result, with an explicit convergence rate. Currently, there is no single result just a lemma for each phase, and it is difficult to parse the main out-take of the paper. In such a paper, I think the convergence rate of the entire procedure is crucial to fully understand the quality of the result.\n- The paper is very technical, and in my opinion, doesn’t provide enough intuition to understand the quantities that are used. For example, the definition of \\delta in line 238. Can’t \\delta be zero or at least exponentially small (if the angle between two data points is very close to \\pi/2).\n- The result in Section 7 is interesting but not quite clear. What does the quantity M represents? What can we say about the dataset itself so that either option (i) or (ii) of Theorem 8 is applied?\n- I think that claiming that the implicit bias for the problem studied here is to minimize the norm is a bit misleading. As I understand it, all the learned weights either align with the target neuron or deactivate, this means that the solution converges to a specific form of rank-1 matrix (where each row is either v^* or 0). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> [...] where in the first phase the learned weights either align with the target neuron or deactivate, [...]\n\nPlease see the first item in our response to reviewer PDpC.\n\n> The assumption that the data is correlated with the target neuron is pretty strong. The motivation for taking an angle of at most $\\pi/4$ between each data point and the target neuron is also not clear. What changes if the angle is larger\\smaller? I think the authors should elaborate more on this assumptions, and what breaks if it is not assumed. [...]\n\nPlease see our response to all the reviewers jointly.\n\n> The presentation of the main result is not clear. I think there should be a single Theorem stating the convergence result, with an explicit convergence rate. Currently, there is no single result just a lemma for each phase, and it is difficult to parse the main out-take of the paper. [...]\n\n> What is the total convergence rate of gradient flow for learning a single neuron?\n\nFrom Lemma 6, in the final stage of the training, the mean square empirical loss converges to zero at an exponential rate $L(\\mathbf{\\theta}^{T\\_2+t}) = \\exp(-\\Omega(t\\delta^4/\\Delta^2))$, which is $\\exp(-\\Omega(t))$ for fixed $\\delta$ and $\\Delta$.\n\nThe time $T\\_2$ to reach the final stage by Assumption 2 satisfies $T_2 = O((\\ln m+n^2) d \\Delta^4/(\\delta^8\\ln\\delta))$, which is $O((\\ln m+n^2)d)$ for fixed $\\delta$ and $\\Delta$.  This reflects the lengthy escape from the saddle at the origin due to the small initialisation scale.  (After submission, we succeeded in reducing the $n^2$ term here to $n\\ln n$.)\n\nWe are happy to make these bounds clearer in the paper.\n\n> The paper is very technical, and in my opinion, doesn’t provide enough intuition to understand the quantities that are used. For example, the definition of $\\delta$ in line 238. Can’t $\\delta$ be zero or at least exponentially small (if the angle between two data points is very close to $\\pi/2$).\n\nIn our results, the dataset and the unscaled initialisation are given rather than sampled from particular distributions.  This generality comes at the price of having the explicit parameters $\\delta$ and $\\Delta$, which otherwise typically would be replaced by lower and upper bounds (respectively) on measurements of the dataset and the unscaled initialisation that hold with high probabilities.\n\nThat $\\delta$ is positive follows from Assumption 1, however indeed it may be arbitrarily small since in our worst-case approach the dataset is given by an adversary.\n\nWe remark that e.g. Boursier et al. regarded quantities like our $\\delta$ and $\\Delta$ as constants (see their Appendix B.2).\n\n> The result in Section 7 is interesting but not quite clear. What does the quantity $\\mathcal{M}$ represents? What can we say about the dataset itself so that either option (i) or (ii) of Theorem 8 is applied?\n\n> Is there an explicit condition on the dataset that can be given so that the set of interpolators also minimizes the norm of the predictor\n\nAt present we do not have an alternative characterisation of the dichotomy shown in Theorem 8.\n\nThe following is a sufficient condition for option (i) to apply, i.e. for the set of rank-1 interpolators to also minimise the norm: the inverse of the Gram matrix of the dataset (in our setting this Gram matrix is positive) is a Z-matrix, i.e. the inner product of any two distinct rows of the inverse of the dataset matrix $\\mathbf X$ is non-positive.\n\nAs we point out in Remark 37 (ii) in Appendix H, option (i) of Theorem 8 also always holds in dimension $d=2$.\n\nThat option (ii) may occur is related to (in fact, it implies) the known fact that, for $d>2$, it is not the case that the inverse of every non-singular symmetric non-negative $d \\times d$ matrix is a Z-matrix (see e.g. Markham “Nonnegative matrices whose inverses are M-matrices\" Proc. Am. Math. Soc. 36 (2), 326-330, 1972).  However, additional work was involved to construct our family of examples in Example 36 (case $\\mathcal M>0$) in Appendix H.\n\n> I think that claiming that the implicit bias for the problem studied here is to minimize the norm is a bit misleading. As I understand it, all the learned weights either align with the target neuron or deactivate, this means that the solution converges to a specific form of rank-1 matrix (where each row is either $\\mathbf{v}^*$ or 0).\n\nIn the definition of $\\Theta\\_{\\mathbf{v}^*}$ in Section 6, the normalised non-zero hidden neurons equal $\\mathbf{v}^*$. Thus Theorem 7 asserts that, as the initialisation scale decreases to zero, the training converges to a rank-1 matrix in which each row is either a positive scalar multiple of $\\mathbf{v}^*$ or $0$. However, the scalars can be quite different, i.e. the hidden neurons in the rank-1 network might have quite different norms (that depend on the initialisation).\n\nWe agree that the norm is not necessarily minimised; indeed Theorem 8 (ii) captures the scenario where it is not.\n\n> Is it possible to extend the result to gradient flow? or possibly SGD?\n\nThank you for this suggestion. We believe an extension to gradient descent would be possible, by proving an upper bound on the learning rate such that essentially the same behaviour occurs as with gradient flow (as in e.g. Cheridito et al. “A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions” J. Complex. 72, 101646, 2022). At the moment we prefer to leave this to future work, so as not to distract readers from our main goal: analysis of the training dynamics and characterisation of the implicit bias of learning a non-trivial regression task using a non-linear network in a theoretically challenging setting.\n\nAn intriguing related question is to what extent the phenomena described in this and other works that assume a small initialisation are consistent with training by gradient descent (possibly stochastic) that uses adaptive learning rates to speed up departures from near saddle points."}, {"review_id": "eM7QksFDxK", "reviewer": "Reviewer_JZbY", "summary": "The authors analyze the dynamics and implicit bias of gradient flow with the square loss when learning a single ReLU neuron using a one-hidden-layer ReLU network. They assume that the training data are correlated with the teacher neuron (the angles are smaller than $\\pi/4$), and that gradient flow starts from a small and balanced initialization. They give a non-asymptotic convergence analysis. In the limit where the initialization scale tends to zero, the resulting network has rank $1$. Namely, all non-zero neurons point in the direction of the teacher neuron. On the other hand, the resulting network might not have minimal Euclidean norm. Thus, there is an implicit bias for rank minimization but not for norm minimization.", "questions": "See the “weaknesses” section.", "limitations": "The authors discussed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Understanding convergence and implicit bias in overparameterized networks is an important question, that has attracted much interest in recent years. The paper gives a detailed analysis of the trajectory and implicit bias. The analysis is under strong assumptions (single-neuron teacher, correlated training data, small and balanced initialization, etc.), but these assumptions are present also in existing results, and the analysis of gradient flow is challenging even under such assumptions. Finally, the paper is well-written.", "weaknesses": "In Assumption 1: \n- Item (iv): why is it a measure-zero event?\n- Items (iv) and (v): I think that the assumptions should specify properties of the training data and the training algorithm. Then, the properties of the trajectory should be shown using these assumptions. Can you specify items (iv) and (v) as assumptions on the data+algorithm?\n\nOther than that, I don’t have major concerns. An obvious limitation is the strong assumptions, and specifically the assumption on the correlated training data, but as I already mentioned, I think that it is reasonable here.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In Assumption 1:\n> - Item (iv): why is it a measure-zero event? \n> - Items (iv) and (v): I think that the assumptions should specify properties of the training data and the training algorithm. Then, the properties of the trajectory should be shown using these assumptions. Can you specify items (iv) and (v) as assumptions on the data+algorithm?\n\nRegarding item (iv), a single yardstick trajectory at any time $t$ follows a direction $\\mathbf{\\gamma}\\_S$ for some $S \\subseteq [n]$.  The set $S$ changes at most $n$ times, namely at the crossing of $\\bigcup\\_{i \\in [n]} H\\_i$, where $H\\_i$ is the set of vectors orthogonal to the training point $\\mathbf{x}\\_i$.  Consider a set of targets $H\\_i \\cap H\\_k$, of dimension $d-2$.  It can be reached by a straight-line trajectory from a convex polyhedron $P$ of dimension at most $d-1$.  Thus, the previous change of direction occurs at a vector from $P \\cap \\bigcup_{i \\in [n]} H\\_i$, which is a polyhedron of dimension at most $d-2$ as well.  Thus, in order for a vector to reach $\\bigcup_{i < k} H\\_i \\cap H\\_k$ by a yardstick trajectory, it must belong to a finite union of affine subspaces of dimension $d-1$.  Therefore, if each $\\mathbf{z}\\_j$ at the initialisation is sampled from any absolutely continuous distribution on $\\mathbb{R}^d$, the probability that Assumption 1 (iv) is violated is $0$.\n\nRegarding item (v), we would say it is an assumption about the gradient flow, and it has featured in the literature, e.g. in Eberle et al. “Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation” ERA 31(5): 2519-2554, 2023, where on page 2535 it is paraphrased as “the set of all degenerate neurons of the GF solution at time $t \\in [0, \\infty)$ is non-decreasing in the time variable” (in fact, our Assumption 1 (v) is slightly weaker than that).  The trajectories of the gradient flow that this assumption excludes cannot arise as limits of paths of gradient descent with any fixed value for the derivative of $\\sigma$ (the non-linear ReLU function) at zero: if that value is $0$, then any deactivated neuron cannot activate subsequently even if there are data points exactly on its ReLU boundary; and if that value is greater than $0$, then in our setting the deactivation of any neuron would necessarily involve removing all data points from its ReLU boundary.  Thus arguably these impractical trajectories might a priori exist only due to a quirk of the theoretical setup of the gradient flow.\n\nWe are happy to expand on these points in the main paper, and we shall provide in the appendix a more detailed proof of the measure zero for item (iv)."}]

Author rebuttal:
We thank all the reviewers for their positive and encouraging reviews, and for comments and questions, which will help us improve the submission. 

We attach a PDF with plots from a few additional experiments, and refer to it in our responses to some of the reviewers. 

In what follows we elaborate on the $\pi / 4$ condition on the angles between the data points and the teacher neuron, which reviewers PDpC and ytEj commented on and asked about, and which may be of interest also to the other reviewers. 

* Theoretically, whilst the $\pi/4$ condition is strong, it enables us to focus on datasets that are not orthogonal, thus taking on the main challenge posed by Boursier et al. NeurIPS 2022. Notice, e.g., that orthogonal datasets in $\mathbb R^d$ may have at most $d$ data points, whereas in our work the number of data points is unbounded.

* A key place where we rely on the $\pi/4$ condition is to show that, during the second phase of the training, all neurons that form the aligned bundle are active on all (and thus the same set) of data points (see Proposition 26 in Appendix F).  The $\pi / 4$ condition also implies that the angle between any two data points is less than $\pi / 2$, which streamlines the first phase and ensures that it produces only one bundle of aligned neurons.  We remark that, in dimension $2$ (which covers the uni-variate setting with biases), the $\pi / 4$ restriction with the teacher neuron can in fact be replaced by this weaker $\pi / 2$ restriction between data points. 

* Please also see the top four figures in the attached PDF for some results of additional experiments that explore the effects of increasing the scale of the noise used to generate the synthetic datasets so that quickly most of the data points exceed the $\pi / 4$ angle with the corresponding teacher neuron.  The growing maximum angles between neurons at the end of the training indicate that we no longer have a single (or one per teacher neuron) aligned bundle of neurons forming and sticking together for the rest of the training.

We believe this submission paves the way for future work to generalise both the strictly orthogonal datasets of Boursier et al. and the correlated datasets with the $\pi / 4$ bound considered here.

We are happy to add remarks such as above to the paper.  We shall make clear all the places in the proofs where we use the $\pi / 4$ condition, and we shall report on the additional experiments in the appendix.

Meta-review: The authors consider the dynamics of two-layer relu networks trained by gradient flow on inputs such that the labels are given by a single neuron which is correlated with all training points.  The reviewers were unanimous in voicing support for acceptance, albeit most of the reviewers were somewhat unenthusiastic in their support.  The reviewers valued the importance of understanding the implicit bias of gradient flow and the difficulty in trajectory analyses even in the simplified setting considered by the authors; one reviewer was impressed by some of the arguments used.  The primary concern brought forward by reviewers was the clarity of the writing and organization of the paper, with secondary concerns concerning the strength of the assumptions.  On the whole, I think the contributions are significant and I recommend acceptance.

I would recommend that the authors revise the main section in accordance with reviewer ytEj's suggestions.  I would also confirm that the camera ready and supplemental version have the same citation list, I noticed some odd differences in these.
Decision: Accept (poster)