Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs
Authors: Etienne Boursier
Loucas Pillaud-Vivien
Nicolas Flammarion
Venue: NeurIPS 2022 Accept (2022)
Keywords: implicit bias
two-layer neural networks
gradient flow
gradient descent
global convergence
ReLU networks
variation norm
non-convex optimisation

Abstract: The training of neural networks by gradient descent methods is a cornerstone of the deep learning revolution. Yet, despite some recent progress, a complete theory explaining its success is still missing. This article presents, for orthogonal input vectors, a precise description of the gradient flow dynamics of training one-hidden layer ReLU neural networks for the mean squared error at small initialisation. In this setting, despite non-convexity, we show that the gradient flow converges to zero loss and characterise its implicit bias towards minimum variation norm. Furthermore, some interesting phenomena are highlighted: a quantitative description of the initial alignment phenomenon and a proof that the process follows a specific saddle to saddle dynamics.

Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs
Etienne Boursier TML, EPFL, Switzerland etienne. etienne. boureierrepfll.cc
Loucas Pillaud-
TML. EPFL, Switzerland loucas woucas.pillaud www.llandddivviieeeee.l..dddd
Nicolas Flammarion
TML. EPFL, Switzerland
ni colooool...oo.oo. aalolass.. ttt.aa..lmmaaaaaa www.maaiiiiinnepr.......
Abstract
The training of neural networks by gradient descent methods is a cornerstone of the deep learning revolution. Yet, despite some recent progress, complete theory explaining its success still missing. This article presents, orthogonal input vectors, precise description of gradient flow dynamics of training one-hidden layer ReLU neural networks for the mean squared error at small initialisation. In this setting, despite non-convexity, we show that the gradient flow converges to zero loss and characterise its implicit bias towards minimum variation norm. Furthermore, quantitative description of the initial alignment phenomenon and proof that the process follows a specific saddle to saddle dynamics.
interesting phenomena highlighted:
Introduction
Artificial neural networks are nowadays trained successfully to solve large variety of learning tasks. However, large number of fundamental questions surround their impressive success, Among them, the convergence to global minima of their non-convex training dynamics and their ability generalise well despite fitting perfectly the dataset have challenged traditional machine learning belief. While complete theory is still lacking, machine learning community has recently come up with key steps that allow to tame the complexity of the problem: proving the convergence of gradient flow to zero loss [Mei ct al. 2018 Chizat and Bach 20088) [Sirignano and Spiliopoulas] 20200) Rotskoff and Vanden- Vanden-Eiinden 2022 investigating the algorithmic selection of specilic global minimum often referred the amplicit bias of an algorithm [Neyshabur et al., 2014 Zhang
[02T]; while
paying attention the importance of the initialisation [Woodworth
2020 Chizat et al. 2019
analyse precisely these three points for regression problems. This done in specific setting: for orthogonal inputs, we provide a complete charactcrisation of the gradient flows dynamics of training one- me-hhidenn layer ReLU neural networks with the square loss at small initialisation. We show that this non-convex optimisation dynamics captures most of the complexity mentioned above and thus could be first step towards analysing more general setups.
The aim of this article
Global convergence of training loss for neural networks. Showing convergence of the gradient flow to a global minimum is an open and important question. Beyond the lazy regime (sec next paragraph), only few results were proven in the regression setting. The most promising route might be the link with Wassertein gradient flows for infinite neural networks. In that case, global convergence happens under mild conditions (Chizat and Bach [0188] Wojtowytsch 2020 Other works focus on local convergence [Zhou et al. [221] Safran al.] 2021]. or general criteria that eventually fail to encompass practical setups [Chatterjee] 2022 Chen et al. 2022 These latter works
36th Conference Neural Information Processing Systems (NeurIPS 2022).

---

rest Sallaak-ojasiewiiz inequalities that in fact cannot be satisfied through the whole process if the dynamics travels near saddle points [Liu et all 2022]. as empirically observed [Dauphin et al., 2014]. On the contrary, the present paper proves global convergence without resorting to large overparamelerisation dealing carefully with saddles.
Feature learning and small initialisation. The scale of initialisation plays an essential role in the behavior of the training dynamics. Indced, an important example that, large initialisation, known as the lazy regime [Chizat et al. 2019), the neurons move relatively slightly implying that the dynamics is nearly convex and described by an effective kernel method with respect to the
Neural Tangent Kernel [Jacot et al. 2018 Allen- ct al. 2019 Arora et al. 2019). Instead, we are interested in another regime where the mittalisation scale is small. This regime is known to be
richer it performs feature learning (Yang and Hu, [021] but is also more challenging analyse as
follows a truly non-convex dynamics (see details Section 4).
Implicit bias of gradient methods training. There are many global minima to the mean squared error, i.e. ReLU neural networks that perfectly interpolate the dataset. An important question is to understand which one is selected by the gradient flow for given initialisation [Neyshabur et al. 2014]. For linear neural networks, this question has been answered thoroughly [Arora et al. 2019 Yun et al. 2021 Min et al., [2021] with a discussion on the role of initialisation [Woodworth et al, 2020] and noise Pesse et al. 2021]. J. For non-linear activations such as ReLU, no clear implicit bias criteria have been ever exhibited for the square loss besides a conjecture of a quantisation effect (Maennel et all 2018]. Finally, note that in the classification setting, the favorable behavior of iterates going infimity simplifies the analysis prove implicit biases such as: max-margin for the Eg norm in case of linear models (Soudry et al. [2018] Ji and Telgarsky 2019b), alignment of inner layers for linear neural networks []i and Telgarsky] [2019a] and max- max-margin for the variation norm induced by neural networks Kurková and Sanguineti 2001] in the case of one- one-hidden layer neural networks (yy and Li 2019, Chizat and Bach [2200]
Beyond the convergence results, the implicit bias characterisation anticipates the generalisation properties of the returned estimate discussed in Section
Dynamics of training for neural network. In the regression case, the starting point governs where the flow converges. This observation suggests that a complete analysis of the trajectory may be required when one wants to understand the implicit hias in this case. Such descriptions have been undertaken by Maennel et al. [2018). who deseribe the initial alignment phase small initialisation,
and et al. [2cott Jacot al. [202T] who conjecture that the dynamics travels from saddle saddle.
These papers provide intuitive content that we prove rigorously in the orthogonal setup.
Finally, closest to our work are the following results on the classification of orthogonally separable data [Phuong and Lampert 2020 Wang and Pilanci [021] and lincarly separable, symmetric data [Lyu et 2201]. The classification setup provides easter tools to analyse the problem: indeed, after the initial alignment phase, the network has already perfectly classified the data points in these settings. From there. is known that the training loss converges to zero and that the parameters direction is biased towards KKT points of the max-margin problem [Lyu and T.j 2019 Di and Tel Telgarsky. 2020) Such tools cannot be applied after the alignment phase for regression, and we resort to a refined analysis of the trajectory to show both global convergence and implicit bias. On the other hand, Lyu
al. [202]] require precise description of the dynamics to ensure convergence towards specific KKT points of the max-margin problem. Yet, the analysis of the dynamics is simplified by their symmetry assumption: the trajectory does not go through intermediate saddles and all the labels are simultaneously fitted. On the contrary, the dynamics we describe travels near an intermediate saddle point which separates two distinct fitting phases. This behaviour largely complicates the analysis, besides being more representative of the saddle to saddle dynamics observed in general settings.
1.1 Main contributions
We make the following contributions.
We prove the convergence of the gradient flow towards global minimum of the non-convex training loss for small enough initialisation and finite width.
We characterise the global optimum retrieved for infinitesimal initialisation as a minimum f
norm interpolator, which implies a minimum variation norm in terms of prediction function.
As important as the convergence result, the dynamics portrayed in Section X quantitatively detail its different phases (alignment and fitting) and show it follows a saddle to saddle dynamics.
2

---

1.2 Notations
We denote by LA the function equal to 1 if A is truc and otherwisc. ((S) is the uniform distribution over the set S and (N, 2)) a Gaussian
mean f and covariance We denote Vaha(a) the gradient of ++ (2)) fixed x. For any n E N", |n] denotes the tuple integers between and n. The scalar product between æ, y E R4 is denoted by (z, v) and the Euclidean norm is denoted by || and called 2g S denotes the sphere of R for the Euclidean norm. ((0,r) r)) is the Euclidean ball of center and radius r. All the detailed proofs of the claimed results are deferred to the Appendix.
2 Setup and preliminaries
2.1 One-hidden layer neural network and training loss
Model. Let us fix integer E N' as well input data (I1,-- .ag....,,,,, 2x) (R")" and outputs (y1...., yo) E R". We are interested the minimisation of the mean squared error:
L(Ø)=
2n Σ (ho(xe) ve) where ho(z) Σ ((
(I)
is a one-hidden layer neural network of width m defined with parameters (a, W) E Rd x Rmxd. The vector R stands for the weights of the last layer and W [w] ... wm]] E Rdxm where each wy E H represents a hidden neuron. To encompass the effect of the bias, an additional component can be added to the inputs IT 4- [xT without changing results. Finally, the activation function a the ReLU: (z) == max (0,2).
We introduce here the main assumptions the data inputs.
Assumption The input points form an orthonormal family, i.e. Vk, k E [n]] (It, mar) = 1 A
The data are assumed to be normalized only for convenience-the the real limitation being that they are pairwise orthogonal. This assumption is exhaustively discussed in Section 3.2
Assumption 2. For all l E [v]]. Ms * and Σnpp Mi * Ex 2
This assumption on the data output mild, c.g. has zero Lebesgue measure, and only permits to exclude degenerate situations.
Gradient flow. As the limiting dynamics of the (stochastic) gradient descent with infinitesimal
step-sizes Li et al. 2019), we study the following gradient flow
d#
VL(O))
T Σ (xx) - y6) (Tx)::(x))
dt
initialised 0 = (a Wo). Since the ReLU is not differentiable O. the dynamics should be defined as subgradient inclusion flow [Bolte et 2010 However, we show Appendix the only ReLU subgradient that guarantees the existence of a global solution o' (a) 1. Hence, we stick with this choice throughout the paper. Another important difficulty of this non did-ffrrenntiaiiitty is that Cauchy- -ipschhtz theorem does not apply and uniqueness is not ensured. There have been attempts to define the solution of this Ordinary Diffential Equation (ODE) unequivocally (Eberle et al. 2021 well ways circumvent this difficulty by resorting smooth activations additional data assumptions [Wojtowytschi 20200, Chizat and Bach 2020). Yet, we do not follow this line and demonstrate our results for all the gradient flows satisfying Equation (2)
2.2 Preliminary properties and initialisation
Let us derive here some preliminary properties of the gradient flows. If we rewrite explicitly the dynamics of Equation each layer separately, we have straightforwardly that for all E [m].
da di (Dg'
duf 1
w/)
and
DTy d'.
(3)
dt
3

---

where Dj - Ei= =00,0 (1x) Ms. ir is vector of R This vector solely depends
on H through the prediction function hg and on the neuron j through activation vector A(w ):
where, for vector w Rd. A(w) := (1 (w.m)))s ..... L (a (am.a a.)
[0. From Equation
we deduce the following balancedness property [Arora et al. 20191.
Lemma 1. For all t 2 0 and all j E [rm]. (a])² -11
(a))² ||ul1 Assume furthermore that
for all j [m]] the initialisation balanced and non-zero: |a]) = || > 0. Then la):
||u3|||
and letting sigu(a") E [1.-1)",
mm for all i we have that a} sy]|uff]]
Importantly, by Lemma 1 the study of Equation 3 reduces to the hidden layer W solely. We consider the following balanced initialisation:
w Agj where gj Lid. (O
80 (a., W with
(4)
d = ==5s,,lue s where Sj Ltd. u(1-1,1)).
As already stated, we are interested in the regime where the initialisation scale À > 0 is small. We also introduce the following sets of neurons that are crucial in the fitting process
S_,1 : [j [m]] sy +1 and for all & such that yu > 0, (wf.. -m) 0).
(5)
S = [m] Sy = =1 and for all l such that yn < 0, (w... ma) 2 0}
(6)
Assumption 3. The sets St and S . are both non-empty.
Assumption 3 states that there are some neurons two given cones at initialisation. holds with probability when the support of initialisation covers all directions and the width m of the network goes to infinity. This is thus weaker condition than the omni- mmii-irecctonality of neurons at initialisation [Wojtowytsch] 20200. which is instrumental to show convergence the mean field regime (Chizat and Bach, 2018). On the other hand, it is stronger than the alignment condition of Abbe et al. [2022]. which is known to be necessary for weak learning but might not lead the implicit bias described in the next section.
3 Convergence and implicit bias characterisation
3.1 Main result
Thcorem [| below states our main result on the convergence and implicit bias of one-hidden layer ReLU networks for regression tasks with orthogonal data.
Theorem 1. Under Assumptions 1 there exists X >> depending only the data and the width such that, if X S X", the gradient flow initialised according to Equation (4) converges almost surely to some 8% of zero training loss, i.e. L(B = 0. Furthermore, there exists 8 such that
lim lim 0¹ = 0" argmin |101|.
A-0 10
L(0)-0
The significance of this result is thoroughly discussed in Section 3.2 Note that quantitative and non -on-syymtootic version of Theorem [ both in time and X, is stated in Lemma 12 (Appendix B Roughly, it states that the dynamics has already nearly converged after time of order In(A) and then that convergence happens exponential speed. Note also that the neural network need not be overparametrised for the result to hold: the only sufficient and necessary requirement on the width m stems from Assumption 3
Sketch of proof. The proof of Theorem restss on a precise description of the training dynamics, which is divided into four different phases. We here only sketch it at a very high level and more thorough deseription, with quantitative intermediate lemmas, is given in Section 4
During the first phase, hidden neurons align to few representative directions, while remaining close to O in norm. In particular, all hidden neurons in S1.1 (resp. S .,) align with some key vector 1) (resp. -D_ defined in Section 4.1 During the second phase. the neurons aligned with D+ grow in norm, while staying aligned with D.,, until fitting all the positive labels of the dataset (up to some error scaling with A). Meanwhile, all the other ncurons stay idle. Then similarly, the neurons aligned

---

with -D- grow in norm during the third phase, until nearly litting all the negative labels. Meanwhile, these neurons remain aligned with -D_ and all other neurons remain idle. The precise description of these three phases is obtained by analysing the solutions of the limit ODEs when À = O. The approximation errors that occur from dealing with non-zero À are then carefully handled via Grönwall comparison arguments. Due to the large time scales (of order - In())), the error can propagate on such large time spans. Handling these error terms is the main challenge of our proof and remains intricate despite the orthogonality assumption.
After these three phases (which last time In(A)/|| D-ID) the parameters vector is close to some minimal fo-norm interpolator. From there show, exploiting local Polyak Dolyak-Lojaiiwiie condition, that the dynamics converges exponential speed to global minimum close this interpolator.
3.2 Discussion
Even if the orthogonal setting consider is quite restrictive, it carries several characteristics that may be generic, either because they have been observed empirically, shown in related contexts simply conjectured. We discuss these important points below.
Convergence to zero loss. Theorem [ states that the gradient flow converges to zero loss. Such result is simple to show when the loss satisfies Polyak-Lojasiewicc (PL) inequality [Bolte et al., 2007]: || ? 2 cL for O. However, here, the dynamics travels near saddles, this inqquality is not verified through all the process. Cireumventing this global argument, it yet possible formulate refined analysis and show convergence the dynamics arrives a region where a local Pl. stands with a large enough constant. This refined analysis, inspired by the recent work of Chatterjee [2022 allows to characterise properly the last phase of the dynamics. We helieve that this approach may help in showing convergence in other non-convex gradient flow/descent.
On the implicit bias. Additionally. Theorem D states that the gradient flow at infinitesimally small initialisation selects global minimisers with the smallest & parameter norm. To our knowledge, this is the first characterisation of the implicit bias for regression with non-linear neural networks. Although it might not hold for some degenerate situations [Vardi and Shamir, 2021| we believe it to be truc beyond the orthogonal casc.
This regularisation is implicit, meaning that this effect does not result from any explicit regularisation (e.g. weight decay) performed during training [Shevchenko et al. 2021 Parhi and Nowak [022]
This is only consequence of the inner structure of the gradient flow and the scale of initialisation.
Furthermore, the implicit bias in parameter space can be translated in function space. Indeed, if we introduce formally the space of (infinite) neural networks, i.c. functions written as f(x)
[ [a((, 2)) (d)((). where is signed finite measure S2-1- Then, can define the variation Rorm. [[ Fi as the infimum of [n|] (Sa-1) 1) over such representations [Kurková and Sanguineti] 2001
Bach 2017 We have the following link between the two formulations
min 2 100033 = min Il. Lif)-
(8)
(())
with slight abuse of notation when defining ((f). Note that the result in terms of the f2- of the parameters strictly stronger than that of the Fi -norm of the function (Neyshabur al. 2014).
Following Equation (]. note the striking parallel between the inductive bias of infinitesimally small initialisation for regression and that of the classification problem with the logistic loss as max- margin problem with respect the Fi-norm [Chizat and Bach] 2220)_ As already observed in the linear case [Woodworth al. 20200. contrast with classification, infinitesimally small initialisation is instrumental in regression to be biased towards small Fi Form functions. The role of initialisation is illustrated empirically in Appendix[A [A]
Finally, let us stress that we did not address the question what functions solve Equation X nor the question of the generalisation implied by such a bias. Related works on the first point come from functional description of norms related to Fi [Savarese et al., 2019 Ongic et al. 2019 Debarre et al. 2022). For the generalisation properties of small Fi norm functions, we refer to Kurková and Sanguineti 2001), J. [Bach [2017]. Importantly, we recall that the question of how well low Ji noom functions generalise depends hcavily on the priori we have on the ground -ouundttuuthhh [Petrimi et al. 2022
Note that the argument is certainly not new, but the cited article has the benefit of clearly presenting it.
5

---

The initial aligmment phenomenon. An important characteristics of the loss landscape is that the origin a saddle point. Hence, as the dynamics is initialised at small scale X. the radial movement is slow and neurons move out of the saddle after time scale - In A. Mcanwhile, the tangential movement of the neurons rules the dynamics and aligns their directions towards specific vectors. This has been first explained by |Maennll ct al. (2018) and referred as the quantisation phenomenon, because neural networks weights collapse small finite number of directions. We emphasise that this phase happens generically when initialisation is near the origin and that this part of our analysis can be
directly extended to the general (i.e. non- non-orthognal) case. Phuong and Lampert (2020). [yu et al. [02T] analysed a similar early alignment for classification with specitic data structures.
The saddle to saddle dynamics. When initialising the dynamics of a gradient flow near a saddle point of the loss, it is expected (but hard to prove generically) that the dynamics will altemntte slow movements near saddles and rapid junctions between them. Such hehavior has been conjectured for linear neural networks [Li et al.] 2020, Pacot et al. [202]] initialised near the origin. We precisely prove that such a phenomenon occurs: after initialisation, the dynamics visits one strict saddle. See Section 4 Fact T for more details.
Limitations and possible relaxations. As its main limitation, Theorem [ assumes orthogonal data points z4. The orthogonality assumption disentangles the analysis as the different phases, where either the neurons align towards some direction or grow in norm, are well separated in that case, More precisely, the neurons do not change in direction once they have a non-zero norm in the case of orthogonal data. This separation between alignment and norm growth does not hold in the general case, observed empirically in Appendix [A] Extending our result more general data thus remains major challenge and requires additional theoretical tools. Nonetheless, dimension, our analysis can casily be extended to nearly orthogonal data where [ S 6, with order A. If however is much larger than the initialisation scale, the dynamics is drastically different and becomes as hard as the general case to analyse. In Appendix [A] we observe similar dynamics for high dimensional data, where the loss converges towards O. goes through an intermediate saddle point and the final solution is close to 2 neurons network.
can be the case in high
A minor assumption is the balanced initialisation, i.c. [|u:) = la]]. If instead we initialise a² as a Gaussian scaling with X, the initialisation would be nearly balanced for small A. This assumption is thus mostly used for simplicity and our analysis can he extended to unbalanced initialisations.
It is unclear whether our analysis can be extended to any homogeneous activation function. The train- ing trajectory might indeed not be biased towards minimal fn-nomm for leaky ReLU activations [Lyu et al. 202T] Theorem 6.2]. Contrary to some beliefs. it suggests that the l2 implicit bias phenomenon does not occur for any homogencous activation function, but might instead be specific to the ReLU.
The overparameterisation regime. Assumption 3 states a deterministic condition to guarantee convergence towards a minimal norm interpolator. This condition is not only sufficient, but also necessary for implicit bias towards minimal E2 norm. For isotropic initialisations, the width needs to be exponential in the number of data points for Assumption
hold with high probability.
With smaller (e.g. polynomial in n) number of neurons, Assumption 3 Jdoes not hold anymore. In that case, the training loss should still converge to 0, but the fn-nrrm of the parameters will not be minimal. More precisely, the estimated function will have more than two kinks. However, an adapted analysis might still show some sparsity in the number kinks (and thus a weak bias) of the final solution. The training trajectory would then go through multiple saddle points (one saddle per kink).
Scale of initialisation. The exact value of X is omitted for exposition's 's clarity. Roughly, it can be inferred from the analysis that X scales as 9(1) @(x)) Interestingly, the //m term is reminiscent of V
the mean field regime, which is known to induce implicit bias [Chizat and Bach 2020, Lyu et al,, 202T] On the other hand, the exponential dependency in 7 is common in the implicit bias literature (Woodworhh et al., [2020]. For larger values of À (but still in the mean field regime), the parameters empirically seem to also converge towards minimal norm interpolator. The analysis yet becomes more intricate and we do not observe any separation between Phase 2 and Phase 3, i.c. there is intermediate saddle in the trajectory.

---

4 Fine dynamics description: alignments and saddles
This section describes thoroughly the training dynamics of the gradient flow. It presents and discusses quantitative lemmas on the state of the neural network the end of each different phase. In particular, mathematical formulations of the early alignment and saddle to saddle phenomena are provided.
Additional notations
First, we need to introduce additional notations for this section. We define vectors D4 and D_ that are the two directions towards which the neurons align
D
Σ k go
and
D_
VK- Alunc0
Σ
We also need to define c == [m ||x]] I1/A and r == || Assumption 2 implies that # 1, and by symmetry we can assume r > 1 without any loss of generality. We additionally fix constants A., > 0, small enough and depending only on the dataset and the width
Spherical coordinates. As radial and tangential movements are almost decoupled during the dynamics, is natural to introduce the spherical coordinates of the neurons: for all [m] denote "y eft Wj. where 22- = In |æyll e and W, w2 w E Sa-1- these adapted coordinates, the system of ODEs reduces to:
dø dt sD, w()) and
dw dt
= (DS) - -(DG".)W)
(9)
4.2 Training dynamies
This section precisely describes the phases of the dynamics, summarised in Figure
Internediate soddle (Pact
Early alignment
Fitting positive labels
Fitting negative labels
Final convergence
(Temma
2
(Lemma
(I (Lemma
(Lemma
1-
[2
Figure Timeline of training dynamics.
Neuron alignment phase. During the first phase, all the neurons remain small in norm, while moving tangentially (i.c. in directions). The neurons align according to several key directions: an initial clustering of neurons" directions happens in this early phase, observed by Maennel et al. 2018). As the neurons have small norm, hot Rs for this phase and Equation (9) approximates
dw/
sj (D} (D). wf)w()
(10)
This ODE corresponds the descent/ascent gradient flow (depending on the sign of sy) on the sphere with objective (D), wy). All neurons end up minimizing or maximizing their scalar product with D which only depends on the activation of wj. As a consequence, neurons with similar activations align towards the same vector, leading some quantisation of the neurons' directions. This alignment happens relatively short time, so that the neurons cannot largely grow in norm. Lemma below quantifies this effect neurons in S and S which are crucial to the training dynamics. Since all other neurons remain small in norm during the whole process, we do not focus on their direction.
Lemma 2 (First phase). For S X2, we have the following inequalities for t -eln(A),
TD-1
neurons S+,1 aligned with D+:
Vj E S-,1, (w/t D+) D
(ii) neurons S-,1 are aligned with D=:
Vj VjE
-D- 2X-) ID-I|
(ii) all neurons have small norm: Vj E [m], || || S 2cA rr..

---

Fitting positive labels. During the second phase, the norm of the neurons in S+,1 (which are aligned with D+) grows until fitting all positive labels. Meanwhile, all the other neurons do not move significantly. The key approximate ODE of this phase is given for a (t) == =jes,, ||a]] by
du+(1) dt
2|11-11 (1
(+(()
r1I 11-1|1,111 u4 (t).
This equation implies that u+ (t). the sum of the squared norms of neurons in S.... eventually Mcanwhile, it needs to be shown that these
converges to D+I| within a time- (in(A)/ neurons remain aligned with Dj and that the other neurons remain small in norm. This fine control is technical and relies on the orthogonality assumption. If data were not orthogonal, neurons could illustrated by Figure 4d in Appendix A
indeed realign while growing in describes the state of the network the end of the second phase.
Lemma 3 below
Lemma 3 (Second phase). If X", then for some time 12 S [D.]
1433 In(A):
(i) neurons in S1,1 are aligned with D
Vj. (w, (2) 2 |P XE,
(ti) neurons in S+.1 have large norm:
EyesEn || = n|] D+I A3,
(iil) other neurons have small norm: Vj E [m]]] \ S4,11 |u/2| s 20X5.
These three points directly imply that the loss is of order X on the positive labels at time l2.
Saddle to saddle dynamics. As explained above, the positive labels are almost fitted by the action of the neurons belonging to S1,1 at the end of the second phase, whereas the other neurons still have infinitesimally small norm. At this point, the dynamics has reached the vicinity of a strict saddle point and requires long time escape it. The analysis actually leads to the following fact: Fact 1. There exists a (strict) soddle point Os & of I, such that if X 1 A
1+ |D+I|
1- DD-11 In(A)
Vt
In(A),
we have 18 - As S A5
The training trajectory thus starts at the saddle point and passes through a second non-trivial saddle point at the end of the second phase. This lemma illustrates the phenomenon of saddle to saddle dynamics discussed in Section a.2 conjectured for linear models by Li et al. [2020] Jacot et al. [202T]. This intermediate saddle point is escaped when the norms of the neurons in S_, have sigmificanlly grown (i.e. become non-zero), which happens during third phase described below.
Fitting negative labels. The norm of the neurons in S-,1 (which are aligned with -D_) grows until fitting all negative labels during the third phase. Meanwhile, all other neurons not move significantly. The additional difficulty in the analysis of this phase compared to the second one is that of controlling the possible movements of neurons in S,, Their norm is indeed large during the whole phase, but they do not change consequently, because the positive labels are nearly perfectly fitted.
Lemma 4 (Third phase). If X S X", then for some time t3 S - 1++3re In(A):
||D-11
(i) neurons S .1 are aligned with- DD: Vj 1. (w/ -D_) 2 | -
(ii) neurons in S-, have large norm: Escs_, || 4 1= D x
(iii) neurons in St.1 did not move since phase 2: Vj E St.1, |uu
(iv) other neurons have small norm: Vj E [m]] \ ($_1
|util| - 3ct=.
Thanks to the orthogonality assumption, the set of minimal f2-norm interpolators can be exactly described by Proposition in Appendix [ The minimal interpolators are actually equivalent to neural network of width 2: the first hidden neuron collinear with D; and the second one is
collinear with is A -looe to an interpolator d" of minimal formorm, that does not depend on A (see Lemma 12). It remains to show that the training trajectory converges to a point close to this interpolator at infinity.
L.emma E then ensures at the end of the third phase that the parameter vector
Convergence phase. To show this final convergence, we use local PL condition given by Lemma 5 Lemma 5 (Local Pl. condition). For > S X", we have the following lower bound on the PL. constont
inf Be B(0" 2 one where ② is the set of parameters verifying the balancedness property.
|D-II
L(

---

this implies that the training trajectory converges to an interpolator and stays the aforementioned ball. It thus converges exponentially at rate |D_ || to a point close to minimal norm interpolator, and the distance to this point goes to 0 when À goes to O, hence implying Theorem !] This exponential rate is only asymptotical: the dynamics still require large time (n/) [D- to escape the two first saddles.
Adapting arguments from the recent work by Chatterjee 2022].
Remark 1 (Local PL in the ReLU case), Note that, strictly speaking, Theorem 1.1 of Chatterrjee (2022) cannot be applied directly to our setup because (i) the infinum is taken on the intersection of ball and the set @ of balanced weights, (ii) the ReLU and hence the loss are not C2 required. We thank Spencer Frei for bringing us this point after the paper acceptance. Yet, the reformulation of Chatterjee (2022) in our case is straightforward and does not provide any more insight. To avoid confusion, we decide to omit the proof here and postpone its writing in an independent note for later. This will also be the occasion to put emphasis on the fact that, in some cases, such result can be applied in the ReLU case without much difficulty.
5
Experiments
This section confirms empirically the dynamics described in Section 4 on an orthogonal toy ample. The code and animated versions of the figures are available in biggttuu..... com/ eboursier/ @Fdynamicel. Additional experiments can be found in Appendix [A] they illustrate the necessity of small initialisation for implicit bias and present similar experiments on non-orthogonal toy data. For the latter. we observe some similar training phenomena, but major differences appearing in the dynamics highlight the difficulty of dealing with non-orthogonality.
We consider the following two-point dataset: 21, yh = (-0.5, 1), -1 and 22, 1/2 = (2, 1). It corresponds to unidimensional data with second 1 coordinate for the bias term. We choose unidimensional data for simpler visualisation. However, it restricts the number of observations to n = to maintain orthogonality. Also, the inputs' norms are not here, but we recall that our analysis is not specific to this case. The width the neural network is m = 60. We choose a balanced initialisation at scale A 10-6 m. We then run gradient descent with a step size 10-3 to approximate the gradient flow trajectory.
Figure 2 shows the training dynamics on this example. In particular, the state of the network is shown at different steps. In Figure 2aj all the neurons are close to at initialisation. Figure 2b]shows the end of the first phase. where the neurons are aligned towards two key directions. After the second phase, shown in Figure 2c all the neurons aligned with D+, have grown in norm and the positive label is perfectly fitted. Similarly at the end of third phase in Figure 2d all neurons aligned with D_ have grown in norm and the negative label fitted.
At the end of training. the loss is 0 and the estimated function is simple. In particular, it only has two kinks, which illustrates the sparsity induced by the implicit bias. Also, the final estimated function might be sounter-intuitive
Previous works on implicit bias indeed conjectured that the learned estimator is linear if the data can be linearly fitted Kalimeris et al. 2019 Lyu et al. 202T). However, the learned function in Figure 2d has a smaller F norm than the lincar interpolator.
Figure shows the evolution of the loss during train- ing. The saddle to saddle dynamics is well observed here: the parameters vector starts from the sad- dle point at initialisation and needs 5000 iterations to leave this first saddle. A second saddle is then encountered at the end of the second phase and the trajectory only leaves this saddle around iteration 11000. once the norm the neurons in S_,1 start being significant during the third phase. All these different experiments confirm Theorem [ and the precise dynamics described in Section 4 Moreover, such training phenomena not specific the thogonal data case, as observed in Appendix A
10-
0.4
0.-
7501 0.0
2501
1960
1250
Iterations
Figure 3: Evolution of the training loss.

---

Ru
-0.
(a) Initialisation (Iteration
(b) first phase (Iteration 4000)
88
88
802
802
64
10
-2-
-0.4
(c) End of second phase (Teration 8000)
(d) End of third phase (Treratinn 15000)
Figure 2: State of training different stages. The green dots correspond the data, while the green line is the estimated function he. Fach blue star represents neuron wy. its z-axis value given w/ Wi.1. which coincides with the position the kink its associated ReLU; y-axis value is given by sy ||,, which we recall the associated value of the output layer.
6 Conclusion and perspectives
We have shown that the training of non-linear neural networks on orthogonal data presents a rich dynamics with a small and onnidirectional intialisation. Convergence holds generically despite truly non-convex landscape and the limit enjoys an implicit bias minimum & parameter norm. Obviously, removing the orthogonal assumption on the inputs, while keeping fine level of description major, but difficult, perspective for future work. Another key point better understand the good generalisation of neural networks analyse properties of functions solving the minimum variation norm prohlem stated in Equation (8)
10

---

References
Emmanuel Abbe, Elisabetta Comnccciaa, Jan Hazla, and Christopher Marquis. An initial alignment between neural network and target is needed for gradient descent to learn In International Conference on Machine Learning, pages 33-52. PMLR, 2022.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019.
Sanjeev Arora, Simon Du Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
David Bertoin, Jérôme Bolte, Sébastien Gerchinovitz, and Edouard Pauwels. Numerical influence of ReLu (0) on backpropagation. Advances in Neural Information Processing Systems. 34, 2021.
Alberto Bictti and Julien Mairal. On the inductive bias of neural tangent kernels. Advances in Neural Information Processing Systems, 32, 2019.
Jérôme Bolte, Aris Danillidis, and Adrian Lewis. The Lojasiewicz inequality nonsmooth subana- lytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4): 1223, 2007.
Jérôme Bolte, Aris Daniilidis, Olivier Ley, and Laurent Mazet. Characterizations of Eojasicwiez inequalities: subgradient flows. talweg, convexity. Transactions of the American Mathematical Society, 362(6):3319 331-33333, 2010.
Sourav Chatterjee. Convergence of gradient descent for deep neural networks. arXiv preprint arXiv:2203. 2022.
Zhengdao Chen, Eric Handen-Eijnden, and Joan Bruna. On feature learning in neural networks with glohal convergence guarantees. arXiv preprint arXiv:2204. 10782, 2022.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances neural information processing systems, 31, 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two- wo-layer neural networks trained with the logistic loss. In Conference Learning Theory, pages 1305 1338. PMLR, 2020.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in diffcrentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem high-dimensional non-convex optimization. Advances in neural information processing syxtems, 27, 2014.
Thomas Debarre, Quentin Denoyelle, Michael Unser, and Julien Fageot. Sparsest piecewise-linear regression of one- dineennnaio data. Journal of Computational and Applied Mathematics, 406: 114044, 2022.
Simon Eberle, Arnuff Jentzen, Adrian Rickert, and Georg S Weiss. Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation. arXiv preprint arXiv:2 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Arthur Jacot, François Ged, Franck Gabriel, Berfin Şimşek, and Clément Hongler. Saddle-to-saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity. arXiv preprint arXiv: 106. 15933, 2021.
11

---

Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019a.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data, In Conference on Learning Theory. pages 1772-1798. PMLR. 2019b.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 33:17176-17186 2020.
Dimitris Kalimeris, Gal Kaplun, Prectum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in neural information processing systems, 32, 2019.
Vera Kurková and Marcello Sanguineti. Bounds on rates of variable-hasis and neural- approximation. JEEE Transactions on Information Theory, 47(6):2659 2665, 2001.
Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. The Journal of Machine Learning Research, 20 (1):1474-1)) 1520, 2019.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. In International Conference on Learning Representations, 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin, Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference Learning Representations, 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, 34, 2021.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient descent quantizes ReLu network features. arXiv preprint arXiv:1803.08367 2018
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Acudemy of Sciences, 1 115633)-7766--7777,, 2018.
Hancheng Min, Salma Tarmoun, Rene Vidal, and Enrique Mallada. On the explicit role initializa- tion on the convergence and implicit bias of overparametrized lincar networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7760-7768. PMLR, 18-24 Jul 2021.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint 1rXiv:1412.666 2014.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width ReLu nets: The multivariate case. arXiv preprint arXiv: arXiv: 1910.01655, 2019.
Rahul Parhi and Robert D Nowak. What kinds functions deep neural networks learn? Insights from variational spline theory. SIAM Journal on Mathematics of Data Science, 4(2):464 2022.
Scott Pesme, Loucas Pillaud-Viviee and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: A provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34, 2021.
Lconardo Petrini, Francesco Cagnetta, Eric Vanden-Eijnden, and Matthicu Wyart. Learning sparse features can lead to overfitting in neural networks. arXiv preprint arXiv:2206. 12314, 2022.
Mary Phuong and Christoph H Lampert. The inductive bias of ReLU networks orthogonally separable data, In International Conference on Learning Representations, 2020.
12

---

Grant Rotskoff and Eric Vanden-Eijnden. Trainability and accuracy of artificial neural networks: An interacting particle system approach. Communications on Pure and Applied Mathematics, 75(9): 1889-1935, 2022, doi: https://doi.org 1ttp//0..0///paa22202
Itay M Safran, Gilad Ychudai, and Ohad Shamir. The effects of mild over parammttttttiiiooonn the optimization landscape of shallow ReLU neural networks. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3889-3934, PMLR, 15-19 Aug 2021.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srehro. How do infinite width bounded norm networks look in function space? In Conference Learning Theory, pages 2667-2690. PMLR, 2019.
Alexander Shevchenko, Vyacheslav Kungurtsev, and Marco Mondelli, Mcan-field analysis of piecewise linear solutions for wide ReLu networks. arXiv preprint arXiv:21 1.02278, 2021.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. SIAM Journal on Applied Mathematics, 80(2):725-75 752, 2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasckar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Gal Vardi and Ohad Shamir. Implicit regularization in ReLu networks with the square loss. In Conference on Learning Theory, pages 4224 4258. PMLR, 2021.
Yifci Wang and Mert Pilanci. The convex geometry of backpropagation: Neural network gradient flows converge to extreme points of the dual convex program. arXiv preprint 2rXiv:2/1000644 2021.
Stephan Wojtowytsch. On convergence of gradient descent training for two-layer ReLu-networks in the mean field regime. arXiv preprint arXiv:2005. 13530, 2020.
Blake 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 Conference on Learning Theory, pages 3635-3673. PMLR, 2020.
Greg Yang and Edward J Hu. Tensor programs iv: Feature learning in infinite-widtt neural networks. In International Conference Machine Learning, pages 11727-11737. PMLR, 2021.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. unifying view on implicit hias in training linear neural networks. In International Conference on Learning Representations, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):077-155. 2021.
Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over-parameterized two-layer neural network. In Conference Learning Theory, pages 4577-4632. PMLR, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] Not
concerned
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report emror bars (e.g.. with respect the random seed after running experi- multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] We stipulate here that the hasic but non-trivial experiments were made a standard laptop.
4. If you are using existing assets (e.g.. code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was oblained from people whose data you'l using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "zI6NhVPUTXb", "reviewer": "Reviewer_bKcM", "summary": "This paper inscribes in the direction of providing quantitative understanding on the dynamics and implicit bias of gradient-based optimisation. The authors focus on regression problems in architectures with one-hidden-layer of finite width, ReLU activations and mean-squared error loss. The inputs are fixed and assumed to be pairwise orthogonal. The results are non-asymptotic, holding for any input dimension and training set size.\nThe contribution is threefold. First, they show global convergence of gradient flow to zero training loss if initialised at sufficiently small norm.  Second, they show an implicit bias of gradient flow towards minimum $\\ell_2-$norm interpolator again when starting from sufficiently small initialisation norm. Third, they characterise four different training phases traversed by the dynamics: (i) initial alignment of the neurons along one of two key directions while keeping a small norm, (ii) positively-aligned neurons grow in norm until fitting the positive labels, while the other do not move, (iii) the same for negatively aligned neurons until fitting negative labels, (iv) final convergence. The orthogonality assumption on the inputs is crucial to allow this separation between alignment and norm-growth phases. The authors also show that a saddle-to-saddle dynamics takes place, starting close to the saddle point at the origin and getting trapped for a long time close to a saddle point between phases (ii) and (iii). \nThe theoretical results are confirmed on a toy dataset of 2 unidimensional data points with a bias.\n\n", "questions": "I would be interested if the authors could discuss the following points:\n\na - What are the main limitations of extending the present analysis to the finite-step-size case and multi-pass stochastic gradient descent?\n\nb - What are the main limitations of extending the present analysis to generic losses other than the square one?\n\nIn [1], the authors discuss the necessity of an initial alignment with the target function for gradient descent to converge to a solution. Could you comment on how to reconcile the findings in [1] with the result of this paper that GD dynamics can align with the relevant directions? It seems to me that the main discrepancy is again related to the pairwise orthogonality assumption that limits the training set size, which prevents to reconcile the present setting with the dynamics of population loss. Could the authors comment more on this point?\n\n\nReference:\n\n[1] Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, Christopher Marquis Proceedings of the 39th International Conference on Machine Learning, PMLR 162:33-52, 2022.", "limitations": "The main limitations of the work regard the restrictiveness of the assumptions to pairwise orthogonal data and fixed dataset, which prevents from obtaining an understanding of the generalisation properties of the GD algorithm.\nThe main weakness in my opinion is the experimental setup, which could be improved in the ways I have described above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I find that the paper is well written. The motivations behind the analysis are relevant and clearly stated in the introduction.\nTo the best of my knowledge, the analysis of the implicit bias of gradient descent on finite-width one-hidden-layer ReLU networks is novel. Interestingly, the analysis is non asymptotic in the input dimension, dataset size and time.\n\nThe assumption of a fixed dataset seems to me a significant limitation towards understanding the generalisation properties in relation to the statistics of the data. It would be interesting if the authors could discuss more about the difficulty of averaging over some given data distribution. The pairwise orthogonality assumption on the inputs is also a significant limitation in terms of the learning ability of the network, given that the number of samples is limited to the input dimensionality.\n\nI also find that the experimental validation of the results is a bit poor and it would be interesting to see the paper findings confirmed on higher dimensional datasets. In particular, it would be interesting to test whether the observed training phenomena still hold true on non-orthogonal but more realistic datasets.\n\nFinally, the manuscript is not completely clear to me in a couple of points:\n\n- The paragraph “Feature learning and small initialisation” (lines 38-45) seems to suggest that the large initialisation case is not interesting since it leads to the lazy training regime. However, it is not clear and should be clarified whether the analysis presented in this paper has been already derived for the precise setting under consideration at large initialisation norm.\n- At line 110, the authors write that their gradient flow description holds for the infinitesimal step-size limit of \"(stochastic) gradient descent\" implying that as the step size vanishes there is no distinction between SGD and GD. If the authors want to keep this comment they should justify it providing a reference or an explanation in support of this claim.\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nxvAvhS3y92", "reviewer": "Reviewer_4xwj", "summary": "The paper studies gradient flow dynamics of shallow ReLU networks for regression with square loss. Authors consider a setting of orthogonal inputs in the regime of vanishingly small initialization. In this setting, they provide a characterization of stages of gradient flow on square loss (see Fig. 1), which allows them to draw a few qualitative results about training dynamics: convergence to nearly min-norm interpolator, justification of initial alignment phenomenon and “saddle-to-saddle” behavior of dynamics. Notably, the analysis does not exploit overparameterization and a main technical assumption (A3) (except the data orthogonality) on existence of neurons for which input and last layer weight agree on sign with the label is a mild one (or at least weaker than the one considered previously in related to zero-loss convergence papers).", "questions": "I suggest that authors add a few missing relevant references accompanied by discussion:\n- “A type of generalization error induced by initialization in deep neural networks” by Yaoyu Zhang et al., 2020 - shows convergence to the closest to init interpolator for lazy training regime (which in some cases might result in selecting the min-norm one)\n- There are a few references on generalization capabilities of “min-norm” interpolators (although mostly for linear models), e.g. “Tight bounds for minimum l1-norm interpolation of noisy data” by Guillaume Wang et al., 2022, which would be helpful to add for completeness in corresponding discussion.\n- “Gradient dynamics of shallow univariate ReLU networks” by Williams et al., 2019 - shows implicit bias in case of univariate regression depending on the init scale.\n\nAuthors should be a bit more explicit about stating that the result holds for a particular sequence (lambda->0) and that at any non-zero lambda dynamics approach but not exactly min-norm, and that the selected min-norm solution might not be unique, and that there is no description (as far as I understood) of a particular min-norm solution selected (e.g. if it is the closest to init?) . Although some of these points can be inferred from statements alone, I would suggest enhancing them for a broader audience.\n", "limitations": "Authors thoroughly discuss the limitations of the proposed approach.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Precise characterization of training dynamics under “non-lazy” regime: more specifically, timeline of dynamics ( covered by Lemmas 2-5 )\n- Analysis does not require over-parameterization\n- A theoretically justified “saddle-to-saddle” behavior conjectured in few related works\n- A few interesting supplementary results, e.g., that only for a particular choice of subgradient the dynamics are well-defined.\n\nWeaknesses:\n- Orthogonality assumption on data (which ultimately allows for such precise characterization of dynamics). This is the main weak point of the paper, as it is hard to understand where current technique will be of any insight in general (although, authors do a fair job of elaborating on it in the corresponding section)\n- A few results in the related literature worth discussing are missing\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kMi-AjmZH1", "reviewer": "Reviewer_7CA5", "summary": "This paper provides a detailed and quantitative characterization of the gradient flow dynamics of a one-hidden-layer ReLU network on orthogonal data. The results require some additional assumptions: square loss function, regression task, balanced and small initialization, and the width is large enough. Under these assumptions, the authors showed that the gradient flow process can be divided into 4 phases and characterized each phase precisely. The implications of the characterizations of this training process include: training loss will converge to zero, the weights will converge towards some minimum $\\ell_2$-norm solution, and the training trajectory will encounter a non-zero strict saddle point. The authors also did experiments to validate their theoretical results.", "questions": "- As mentioned in the \"weaknesses\" section above, it might be better if the authors could give more theoretical intuitions or empirical observations/evidence about neural network training dynamics in more general settings. It could also be better if the authors could provide quantitative requirements and more discussions about the initialization and width of the network.\n\n- Are there more implications for neural network training in practical settings that could be provided by the results in this paper? It would be very interesting if these results could provide guidance on training neural networks in real-world applications, and currently this connection seems a little weak.", "limitations": "This paper is mostly theoretical and focuses on very fundamental problems in neural network optimization, and I do not see any immediate negative societal impact of this work. The authors also adequately addressed the limitations of this paper in Section 3.2.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- This paper studies an important problem in this field, i.e., the training dynamics of neural networks. This work characterized the training dynamics in detail in a simplified setting (gradient flow of regression task with one-hidden-layer wide ReLU network, orthogonal input, square loss, and small and balanced initialization), and this dynamics has several indications which align with previous works' conjectures or empirical observations, including global convergence, implicit bias towards minimum $\\ell_2$-norm solution, and saddle to saddle dynamics.\n\n- This paper is well-written and well-structured, making it easy to read. The notations are well-defined, and the intuitions behind the lemmas and the implications of the theoretical results are discussed in detail. Besides, the authors provided figures (especially Figure 1) to illustrate the training process, which could help with the readers' understanding of the theoretical results.\n\n- The authors did experiments on synthetic orthogonal data to validate their theoretical results. They also did experiments for non-orthogonal cases, which provided intuitions about the similarities and differences between orthogonal and non-orthogonal settings.\n\n- The theoretical proofs in this paper appear to be correct, and the related works are adequately cited. Besides, the experimental settings are provided in detail, making them easily reproducible.\n\nWeaknesses:\n\n- The input orthogonality requirement might be a bit strong, and it limits the number of training data to be no more than the input dimension. Although the authors did some experiments on non-orthogonal inputs, the training dynamics of neural networks still seem a bit unclear and hard to characterize. It might be better if the authors could provide more intuitions/observations in more general cases.\n\n- The requirements for $\\lambda^*$ and the width of the network are not explicitly stated and discussed in the main text, which might make it hard to understand the results quantitatively. It could be better if the authors could move the upper bound of $\\lambda^*$ to the main text, and discuss more about the network width requirement. For instance, if the weights are initialized i.i.d. from the unit sphere, we might need exponentially (in the number of training data) many neurons to ensure that Assumption 3 is true with high probability.\n\nTypos:\n\n- In Figure 1, the end of Early Alignment phase should be $-\\frac{\\epsilon\\ln(\\lambda)}{||D_-||}$ instead of $-\\frac{\\epsilon\\ln(\\lambda)}{||D_+||}$ according to Lemma 2.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dOiW_UjaKQw", "reviewer": "Reviewer_XLXc", "summary": "This paper studies gradient flow dynamics for two-layer ReLU network with square loss and orthogonal inputs. In particular, authors showed that using small initialization gradient flow will converge to the minimum variation norm interpolator. The theoretical analysis consists of complete training dynamics analysis and highlights an interesting saddle to saddle dynamic. Experiment results are also provided to support the theoretical results.", "questions": "I would appreciate if the following questions could be answered:\n\n1. I was wondering if the Assumption 3 can be weakened in some settings so that the required width of neural network can only be polynomial in relevant parameters.\n\n2. I was wondering the exact requirement on \\lambda^*, which I did not find in Lemma 12 (line 149)\n", "limitations": "The limitations of the work are clearly discussed. This is a theoretical work thus I don’t see any potential negative social impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\n1. This work considered the regression setting with small initialization and orthogonal inputs and showed that gradient flow is biased towards minimum variation norm. This result is different from previous implicit bias results and gives understanding of implicit regularization under new settings.\n\nQuality\n1. The quality of this paper is overall good. The results and limitations are clearly discussed. Proof sketch of the main result is provided. Proofs of the theoretical results are included in the appendix.\n\nClarity\n1. The paper is overall well-written and easy-to-follow.\n\nSignificance\n1. Understanding implicit regularization of gradient flow/gradient descent is an important and active research problem towards understanding overparametrized neural networks.\n2. Analyzing the whole training dynamics and showing its convergence to a minimum norm interpolator is not an easy work, even in such simplified setting. It is great for authors to prove such a result.\n3. The condition on width of neural networks seems need to be exponential in number of training samples to satisfy Assumption 3, when using the gaussian random initialization. It would be better if authors could make it clear when discussing Assumption 3.\n4. The condition on the scale of the initialization also seems need to be exponentially small. I would not view this as a major limitation, since using an exponentially small initialization is common in the implicit bias literature.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept