Convergence of the Gradient Flow for Shallow ReLU Networks on Weakly Interacting Data
Authors: Léo Dana
Loucas Pillaud-Vivien
Francis Bach
Venue: NeurIPS 2025 poster ()
Keywords: Shallow Neural Networks
Gradient Flow
High-dimension
Convergence rate
Primary area: optimization
TL;DR: We analyse the convergence of one-hidden-layer ReLU networks trained by gradient flow on n data points, when the input lies in very high dimension.

Abstract: We analyse the convergence of one-hidden-layer ReLU networks trained by gradient flow on $n$ data points. Our main contribution leverages the high dimensionality of the ambient space, which implies low correlation of the input samples, to demonstrate that a network with width of order $\log(n)$ neurons suffices for global convergence with high probability. Our analysis uses a Polyak–Łojasiewicz viewpoint along the gradient-flow trajectory, which provides an exponential rate of convergence of $\frac{1}{n}$. When the data are exactly orthogonal, we give further refined characterizations of the convergence speed, proving its asymptotic behavior lies between the orders $\frac{1}{n}$ and $\frac{1}{\sqrt{n}}$, and exhibiting a phase-transition phenomenon in the convergence rate, during which it evolves from the lower bound to the upper, and in a relative time of order $\frac{1}{\log(n)}$.

Convergence of Shallow ReLU Networks on Weakly Interacting Data
Léo Dana
Loucas Pillaud-Vivien
Francis Bach i Sierra, INRIA Paris
Sierra, INRIA Paris
CERMICS, Ecole Nationale des Ponts et Chaussées
Champs-sur-Mand
Abstract
We analyse the convergence of ane-iiden-llaee ReLU networks trained by gra- dient flow on n data points, Our main contribution leverages the high dimension- ality of the ambient space, which implies low correlation of the input samples, demonstrate that network with width of order log(n) neurons suffices for global convergence with high probability. Our analysis uses Dolyyk--Ljjsiewvine view- point along the gradient-flow trajectory, which provides an exponential rate of convergence _. When the data are exactly orthogonal, we give further refined characterizations of the convergence speed, proving its asymptotic behavior lies Vn. and exhibiting phase-transition phenomenon the convergence rate, during which it evolves from the lower bound to the upper, and in relative time of order log(n))
between the orders : and -
Introduction
Understanding the properties of models used machine learning is crucial for providing guaran- tees to downstream users. Of particular importance, the convergence of the training process under gradient methods stands as one of the first issues to address in order to comprehend them. If, on one hand, such question for linear models and convex optimization problems [Bottou et al., 2018, Bach, 2024] are well understood, this not the case for neural networks, which are the most used models in large-scale machine learning. This paper focuses providing quantitative convergence guarantees for a hidden-dddeerr neural network.
Theoretically, such global convergence analysis of neural networks has seen two main achievements in the past years: (i) the identification of the lazy regime, due to a particular initialization, where convergence is always guaranteed at the cost of being essentially a linear model [Jacot et al., 2018, 8, Arora et al., 2019, Chizat et al., 2019], and (ii) the proof that with infinite amount of hidden units two-layer neural network converges towards the global minimizer of the loss [Mei et al., 2018, Chizat and Bach, 2018, Rotskoff and Vanden- Bijjdenn, 2018], However, neural networks are trained in practice outside of these regimes, as neural networks are known to perform feature learning, and experimentally reach global minimum with large but finite number of neurons. Quantifying in which regimes neural networks converge to global minimum of their loss is still important open question.
We identify regime-marked marked by low-correlated inputs-whert the training dynamics of shallow neural networks via gradient flow can be rigorously understood. Unlike prior analyses that hinged on finely tuned initialization scales [Chizat et al., 2019, Boursier et al., 2022], an infinite number of neurons [Jacot et al., 2018, Chizat and Bach, 2018], or the unrealistic orthogonality of data [Boursier
"leo. dana@inria.fr
'loucas. Llu.aa..pilauudvviiiie..... p.i.laudd-iiieedenp...ft Iranncis. Prancis.bachhinria...
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

ct al., 2022, Frei et al., 2023], our setting arises naturally in high dimensions, notably when the input dimension d exceeds n². Beyond existence of convergence, we seek to quantify it: how fast does the system lock onto a global minimizer? What governs this speed? Our work provides sharp answers.
We summarize our contributions in the analysis of the learning dynamics of one-hidden-layer ReLU network on a finite number of data n via gradient flow.
Our main contribution is that the gradient flow training of shallow neural networks, with square error, on low correlated input, converges globally, i.e. converges to a neural network that interpolates exactly the data. We show that this occurs with high probability for high dimensional whitened input data as soon as d 2 n². Furthermore, this convergence occurs for any initialization scale and whenever the neural network has more that log(n) neurons. We also show that the loss converges to zero exponentially fast with rate at least of order n
Then, when the inputs orthogonal, we refine analysis in order characterize the Moreover, we conjecture that this speed is always of the highest order 1 with high probability and verify empirically this claim.
range of possible asymptotic speeds, which we find to be at most of order 1
Finally, for orthonormal inputs and a special initialization of the network, we highlight a phase transition in the convergence rate during the system's evolution, and compute the associated cut-off time and transition period.
Problem Setup
Notations. We use ||o|| to denote the euclidean norm of vector v, (-I-) its scalar product, and [|M]] for the operator norm associated with of a matrix M. Moreover, let ū [[]]
Loss function. Let (z,, 1))m (Rd R)" be sample of input vectors and real outputs. Let d E NN be the dimension of the vector space and n E N* the number of data points. In order to learn the regression problem of mapping æ; to yı. we use one-hidden-layer ReLU neural networks, which we write:
ho(r) = 1 Σ (
j-1
where p N" is the number of units, (xx) max 00, 2) for E R is the rectified linear unit (ReLU), and the parameters are gathered in 0 (a,, wy wi)lsisp E (R x Rdyp, To simplify the ReLU notation, we define ((wyl=;; [x;)) = (w; [x;)+ and 1 [w> = L When mentioning neurons of the network, we refer to (wyl=:)+ while second layer neurons refer to dj. Neurons can be activated if (wylaa)+ > 0, and are correctly activated if moreover a,yA > 0. Upon this prediction class and data, we analyse the regression loss with square error,
1 Σ (1: h²
I(O) = 2n
(2)
As soon as d 2 (zz)i=1on can form free family, in which case the set of minima of L, which consists of all interpolators, is non-empty. We note r; V/ hy (2;) the residual of the loss.
Gradient flow. In order to understand simplified version of the optimization dynamics of this neural network, we study the continuous time limit of gradient descent. We initialize θr=0 = 0 and follow for all t 2 0 the ordinary differential equation
d
0, = -V_, dt
(3)
where we choose a particular element the sub-differential of the ReLU d'(x) = 1. for any E R. This choice is motivated by both prior empirical work from Bertoin et al. [2021] and theoretical work from Boursier et [2022, Proposition 2] and Jentzen and Riekert [2023]. Because ReLU is not differentiable O, we don't 't have unique valid trajectory satisfying the gradient flow

---

equation. We thus chose among all the trajectories the only one for which deactivated neurons cannot reactivate themselves alone (more in Appendix C.2). We also decided to accelerate the dynamics by a factor p as only this scaling gives a consistent mean field limit for the gradient flow when the number of neurons tends to infinity (see Definition 2.2 by Chizat and Bach [2018)).
Weight invariance. The I- I-homogeneity of the ReLU provides a continuous symmetry in the func- tion 0 + he and hence the loss This feature is known to lead automatically to invariants in the gradient flow as explained generally by Marcotte et al. [2024]. The following lemma is not new (Wojtowytsch, 2020, p. I.1 and shows that, from this invariance, deduce that the two layers have balanced contributions throughout the dynamics.
Lemma 1. For all j E [l, for all t 2 O, - [| la,(0) 1100-11wp (0))) and thus, if ([aa(0)) (0) 2 [10) then (t) maintains its sign and la (t) 2 (t)(-)
Initialization. Throughout the paper, we initialize the network's 's weights wy and a; from a joint distribution where both marginals are non-zero, centered, rotational iaaanall-ivrrintt,. are sub-Gaussian, and we take the norms a and wy independent of d, n. Each pair of neuron is sampled independently from the other pairs. Moreover, we need an assumption of asymmetry of the norm at initialization.
Assumption (Asymmetric norm at initialization). We assume that the weights of the network at initialization satisfy for all j E [1.p], |a,(0)| [0)]l
Articles by Boursier and Flammarion [2024a,b] already used this assumption to study two-layer neural networks in order to use the property described in Lemma 1.
Data. We define the data matrix X = (..,,..,2 nn,) E Rdxn, Denote C₁ = min; ||//|| and Cy = min; |usl: in what follows, we suppose that CF > 0 and C, > 0, i.c., the input and output data are bounded away from the origin. Similarly, we also let C max; ||æي|| and C max; [8al- We note Ciyy" refer to the set of these constants. Finally, introduce the following hypothesis the low correlation between the inputs.
Assumption (Low correlated inputs). We assume that the data satisfy
(2 C
||xTX Dxll
(4)
2/n C
where Dx denotes the diagonal matrix with coefficients ||xx/|
The term || Dxll ll is control on the magnitude of the correlations ((x,, As an extreme case, when it equals zero, the inputs are orthogonal. This assumption is purely deterministic this stage. Later, we show that this weak interaction between the inputs highly likely to occur for random whitened vectors in high dimensions (see Corollary 1).
Dimensions. Throughout the paper, even if the results provided are all non-asymptotic in nature, the reader can picture that the numbers n. p, d (respectively data, neurons and dimension) are all large. Moreover, they verify the following constraint: n is less than and p can be thought of the order log(n), meaning only "low" number of neurons is required.
2.1 Related works
Convergence of neural networks. Neural networks are known to converge under specific data, parameter, or initialization hypotheses, among which: the neural tangent kernel regime studied by Jacot al. [2018], Arora al. [2019], Du al. [2019], Allen-Zhu al. [2019], that has been shown to correspond in fact to a lazy regime where there is no feature learning because of the initialization scale. Another field of study the mean-field regime, where feature learning can happen but where the optimization has been shown to converge only in the infinite width case [Mei al., 2018 Chizat and Bach, 2018, 8, Rotskoff and Vanden Vanden-Eijnden, 2018]. Note that it is also possible to produce generic counter examples, where convergence does not occur [Boursier and Flammarion,
'Indeed, the subspace built from all parameters 0, ( 7)00))1s5pp when varies in (RI),, maps the same network, i.e., fe. ho
3

---

2024b]. Beyond these, there have been attempts to generalize convergence results under local PL (or local curvature) conditions shown by Chatterjee [2022], Liu et al. [2022], Zhou et al. [2021], but they remain unsatisfactory to explain the good general behavior of neural networks due to the constraint it imposes the initialization. Convergence theorems similar in spirit to Theorem 1 can be found in an article by Chen et al. [2022]. The main difference relies on two features: only the inner weights which is the regime of interest of the present article. Finally, it is worth mentioning other works on neural networks dynamics, e-g., the study of the implicit bias either for regression [Boursier al., 2022] or classification [Lyu and Li, 2020, Ji and Telgarsky, 2020], or sample complexity to learn functions in specific context [Glasgow, 2023].
trained and their result necessitates large value of outer weights when is large,
properties. Dating back from the early sixties, Polyak derived a sufficient criterion for smooth gradient descent to converge to global minimizer [Polyak, 1964]. This corresponds to the later-called Polyak-Lojasiewicz (PL) constant μ of function f Rd R4 that can be defined as the best exponential rate of convergence of gradient flow over all initializations,
or equivalently to the following minimum ratio = min [(=)(1 This has found many applications in non-convex optimization, as is the case for neural network optimization, and is very popular for optimization in the space measures [Gentil, 2020]. Other notions of PL conditions have emerged in the literature to characterize local convergence, by bounding the PL constant over a ball y² r))
f(x)
[[=](= [Chatterjee, 2022, Liu et al., 2022] and comparing it to f(z)
mingg
f()). We use a notion of PL which is local and trajectory- to prove lower bounds valid on each trajectory.
3 Convergence in high dimension
In this first section, our goal is to understand when the gradient flow converges toward global minimizer of the loss. Note that the parametrization of the prediction function hg by a neural network often implies the non-convexity of the objective L and prevents any direct application convex tools in order to ensure global convergence. Generally speaking, even if gradient flows expected to converge to critical points of the parameter space [Lee et al., 2016], such that V L(0) = O, they might become stuck in local minimizers that do not interpolate the data.
3.1 Local PL-curvature
Convexity not the only tool that provides global convergence: as known in the optimization com-
munity, showing that ||V[() is uniformly lower bounded suffices. As mentioned in Section 2.1, this is known as the Polyak-Lojasiewins condition [Polyak, 1964]. Taking a dynamical perspective on this, we define a trajectory wise notion of this "curvature" condition which we name the local-PL curvature of the system, and define for all /. 0,
(tt) = P (O)111
di ((0))
(5)
L(G,)
L(O:)
with the second equality being property of the gradient flow. Intuitively, this coefficient describes the curvature in parameter space that 0: "sees" at time t Z 0. The following lemma is classical and shows how it can be used to prove the global convergence of the system, well as quantification on the rate.
Lemma 2. Let (m(t)) == 7 Sh u(u)du the time average of the local-PL curvature, which we name the average-PL. curvature. We have L(O.) L(((0))e (m(())
Hence, if the total average-PL curvature (1oc) == lim (u(t)) is strictly positive, we can deduce an upper bound on the loss and convergence to 0 at the exponential speed (Hoo). This shows that the average-PL. curvature is actually the instantaneous exponential decay rate of the loss, and thus controls the speed at which the system converges.
3.2 Global convergence of neural networks for weakly correlated inputs
We are ready to state the main theorem of the paper on the minimization of the loss.

---

Theorem 1. Let > p 2 log (mm) (1 1+ (Ca.
) where Ca.w depends only on the
joint law of w, and suppose Assumption 1. We fix the data (Ti, U:)isisn and suppose it satisfies Assumption 2. Then with probability at least 1 - e over the initialization of the network, the loss
converges to with (poc) 2 C. where we define C- (07) have the lower bound
C.. Moreover, for any 2 we
C1
C min 1
rt(() yi
(())
(6)
Note that, at best, the number of neurons required in Theorem is logarithmic. This finiteness stands in contrast with the infinite number required in the mean-field regime, and the polynomial dependency typical of the neural tangent kernel (NTK) regime [Jacot et al., 2018, Allen-Zhu et al,, 2019]. In the orthogonal case, the ReLU makes the log(n) dependency necessary and sufficient, as shown in Lemma 5, as the residual r, goes to zero if and only if a neuron gets initialized as azy; > 0 and (wy) (ma) > 0 for each i.
Assumption 2 crucial for this proof: it means that the examples are insufficiently correlated with each other for the weights to collapse onto a single direction. As proved by Boursier and Flam- marion [2024a, Theorem 1], the direction ," = arg ming- (w.a] L(0) will attract all neurons if is accessible from anywhere on the initialization landscape This phenomenon known as early align- ment and first described by Maennel al. [2018], will prevent interpolation if examples are highly correlated [Boursier and Flammarion, 2024a, Theorem 2]. The fact that our result holds for any initialization scale shows that near orthogonal inputs prevent accessibility to i and make the early alignment phenomenon benign, as found by Boursier et al. [2022], Frei et al. [2023].
Note finally that norm-asy aoym-msyymettii initialization (Assumption 1) is sufficient for global conver- gence with high probability, but may not be necessary. That said, we present in Appendix C. a detailed example of low probability interpolation failure when the assumption is not satisfied.
Convergence in high dimension. In this paragraph we assume that the data (x,, y:)imim are gen- erated i.i.d. from some distribution Px,., We first show that, with high probability, Assumption is almost always valid if the dimension is larger than the square root of the number of data points. Additionally, we assume that the law aati-concentrates at the origin. These two features are gathered in the following lemma.
Lemma 3. Let (I Sinssnn be generated i..dd. from a probability distribution Px, which has compact support on RR IR", and such that the marginal Px has zero-mean, and satisfies FamPx [xx"] = à Ja- There exists C >> O depending only on the constants C+ and the initial- ization weights, such that, if d 2 C (1² + +n nlog (E)), then, with probability 1 E, Assumption 2 is satisfied.
The hypothesis in the previous lemma is satisfied by standard distributions like Gaussians N(0, Aaa for the inputs. The following corollary restates Theorem 1 for data that are generically distributed as in Lemma 3, and when the dimension is large enough.
Corollary 1. Let > 0. Suppose Assumption 1 and that (xi, Wi)isinn are i.i.d. gener- ated from a probability distribution satisfying the same properties as in Lemma 3. There ex- ists a constant C > 0 depending only the constants Oz,5 such that, if the network has
p log (61)
(1+(Caro
(Ca,ue+))
C+t (+2)2)
neurons in dimension d 2 C (n² n log (t)) with Ca. de-
pending only on the join law of w, then, with probability at least 1 - = over the initialization of the network and the data generation, the loss converges to 0 at exponential speed of rate at least T of
Beyond the digh-dimensionality of the inputs, Corollary 1 does not require any initialization speci- ficity (small or large), and the number of neurons required to converge can be as low as log(n). Hence, let put emphasis on the fact that the global nice structure of the loss landscape comes from the high-dimensionality: this does not come from a specific region in which the network is
'This accessibility condition is in fact the absence of saddle point for some function of normed neurons. which imply that neurons rotate from any anywhere the sphere w".
5

---

initialized as in the NTK (or lazy) regime [Chatterjee, 2022], nor rely on the infinite number of neurons [Wojtowytsch, 2020].
Remark that, under the near-otthogonality assumption, in the large limit, the largest amount of data that "fits" in the vector space is only d, and corresponds to perturbation of the canonical basis. On average, Corollary finally states that the average number of data points for which we can show convergence of the order vd. Trying to push back this limit up to order d an important question for future research and seems to ask for other techniques. Experiments underlying this question are presented in Section 5 (Figure 3).
3.3 Sketch of Proof
The proof of convergence relies on three key points: (i) the loss strictly decreases as long as each example is activated by at least neuron, (ii) for a data point, if there exists neuron which is activated at initialization, then at least one neuron remains activated throughout the dynamics, (iii) At initialization, condition (ii) is satisfied with large probability. Let us detail shortly how each item articulates with one another.
(i). First, Lemma 7, stated and proved in Appendix, shows that, by computing the derivatives of the loss, we get a lower bound on the curvature
(tt) 2 -1X"x - Dxll) min
Σ 3=1
lay 1211111111
To prove the strict positivity, one needs to show that ||X xxx is small enough, and that for each data there exists j such that Jay 12, is strictly positive. Thanks to the initialization of the weights, layl2 2 (0) I|w, (0) > O, and Assumption 2, Z (C |X Dx ||. Thus, have convergence if at any time, for any data input, one neuron remains active, i.e., formally, for all 2 O, and all i E [[ there exists E [[, such that (wy (w){());;++ O. Hence, the loss decreases as long as one neuron remains active per data input. We see next how to show this crucial property.
(ii.. Let us fix the data index E [1,n]. n]. and y/ > without loss of generality. Let us define J arg maxayy>>0 (wy( (f)[2;) the index of the largest correctly initialized neuron. Since oj cannot change sign thanks to Assumption 1, (wyz (t)) is continuous, and has derivative over each constant segment of jr- The strict positivity of this neuron an invariant of the dynamics: 2 Ví. the derivative of the neuron shows it increases. and if r, < Yi. the residual has decreased, which implies that the (w,; (t)) strictly positive. Thus, if neuron is correctly initialized for the data point i, a neuron stays active throughout the dynamics. This invariant however requires large but constant number of neurons.
(iii). Finally, Lemma 5 shows P(vv, 3j. (w, (0) > ONayy > 0) (2)² that for 4log("). the network is well initialized with probability at least -E.
which implies
4 Orthogonal Data
In this section, we go deeper on the study of the gradient flow, assuming that the input data are perfectly orthogonal, or cquivalently that ||X Dx 0. Since most of the intuition for the convergence is drawn from the orthogonal case, it offers stronger results which we detail. In partic- ular, we are able closely understand the local-PI. curvature (μ(());2a evolution and asymptotic behaviour.
4.1 Asymptotic PI. curvature
Theorem 1 has shown that the local-PI. curvature is lower bounded by term of order 1. allowing us show an exponential convergence rate of this order. The following proposition shows that in the orthogonal case the curvature can also be upper bounded.

---

10g
222
W22
322
22 011
Figure I: Example of group initialization with P.. = 3 neurons, kn - 2 examples per neurons, for total examples. Group initialization allows treat each group independently from the other, an thus to solve the problem for a 1-neuron network.
Proposition 1. Let E > O. Given orthogonal inputs, and a constant A > such that for all j E [[, la,(0) [0)]( > A, there exists C 0 depending only the constants C+.-, A, and on the law of a, w, such that for d z Clog(p) log(np) log (2)², with probability 1 on the initialization of the network, we have upper- upper-bound bound on the local-PI. curvature for all t 2 On,
rx(t)
C
p(t) S C max
y1
n
This upper bound uses two properties that are characteristic the orthogonal case. First, once a neuron is inactive on some data input, then, it can never re-activate again. The second property is that for an initialization scale independent on n, there is a phase during which correctly initialized neurons increase while the others decrease to O. This extinction phase, proved in Lemma 8, is short in comparison to the time needed to fit the residuals, and leaves the system decoupled between positive and negative outputs 1/--
In the limit where n goes to infinity, Proposition shows that the network does not learn since the local-PL. is O. This is artifact of the orthogonality of the inputs: the interaction between inputs should accelerate the dynamics. However, although all quantities have well defined limits as + +oo, the limits cannot be understood as gradient descent in an infinite dimensional space".
Proposition 1 is in fact valid for p fixed, and an initialization of the weights for which every data is correctly initialized by neuron. In that case, Proposition 1 shows that the asymptotic curvature cannot be larger than the order 1. While the local-PL curvature is between the order 1 and 1 the v
Vx next proposition shows that any intermediate order , for E [ 1), can be reached asymptotically, with strictly positive probability, using a particular initialization of the network.
Group initialization. In the following, we use Pa. denote the number of neurons, and partition the n data points in pv groups of cardinality kn (note that pn = n2). We re-index the examples per group as by (x: w/) (11+()11), 11)---)),, ). for all E [1, k,]] and j E [
P,, Moreover, we use special initialization of the network such that for j.g E [1. P.]. E [1, k.].
(wyla²) > 0 if =g and 0j sy 31ر1ااز1+
(wyl [ if f #
i.e., wy is correctly activated the group j only. An example of group initialization is visible Figure 1.
Proposition 2. Suppose the group initialization described above, with orthonormal inputs, and the signs of all outputs of the group j are equal to 8 Suppose moreover that the initialization is symmet-
ric, i.e. (a)(0) = [/w,(O]],, We fix k = n 2 la) with a E [ 1]. Then, for 2 Cn - log (Cn), the local-PL curvature satisfies
K₁ <
K₂ na
(10)
л
One would like to write the loss as an expectation over the data point, yet it is impossible as there is no uniform distribution on N.

---

where C' max (2d,))) K1 = 20² min, 2+ my w0 [i]l)
[0)
and K₂ = 40
Proposition 2 states that any asymptotic value (p2o) K K2j can be achieved with strictly posi- tive probability using group initialization. But of what order is the most likely limit of the curvature for standard initialization? The experiment Section 5.2 suggest that, with high probability, the
yn-
asymptotic curvature is always of the order vn
Conjecture 1. Let > O. There exist C₁ C2 depending only on the data and the initialization, such that for 2 C1 log(2) and for orthogonal examples, with probability at least E over the initialization of the network, have convergence of the loss to 0 and
C2
(Ho))
(11)
Vn
4.2 Phase transition in the PI. curvature
In the previous section, emphasized the asymptotic order of the local-PL. curvature with respect to n and hypothesized that it is of the order - in most cases. In this section, we are interested in the evolution of the local-PL curvature during the dynamics. Lemma below computes the local-PL curvature initialization in the large regime, and shows that initially it is of order +.
Lemma 4. At initialization, the local-PL. curvature ((0) is a random variable which satisfy (D(np(0)- - 3o) - N (0,7)), and with Ba, depending only on the data and the distributions of the network's 's neurons.
The constant 3o strictly positive as soon the limit network does directly equal the labels, which is natural to assume since they are unknown priori. Thus the exponential rate of decrease of the loss in the early times of the dynamics is of order n. Importantly, Proposition 2 with a single group has an asymptotic speed of order Vn" meaning that the local-PI. curvature transitions between
n and 1. If Conjecture is true, then this phenomenon happens with high probability during the dynamics.
yn'
Let us study this phenomenon through the example of Proposition 2, with fixed number of neurons p. In this case, the following theorem shows that there are exactly p phase transitions of the loss, which each corresponds to a data group being fitted. To be precise, let us define Lox limm +oo Ln (1), with (t) L(O(t x (..)). ln An log(np), and p fixed (ki, - 9 We prove that Loo is constant by parts with at most p parts.
Theorem 2. Suppose the same data hypothesis and initialization as Proposition 2. We define ||D]112= -i=,(rr) for each cluster, and suppose its limit [| (12 finite. Then, the function Too is constant by parts with at most p parts, and the transitions happen at each time i Moreover, for all E =J0, 1[. there exist times t (E) satisfying
I1
L' - E. - E) mmp and 12 =) ()((s) ~n
1 log (Cr (12)
In
2111791 log(n)
where Lt is the part of the loss corresponding to the group j. and C (8) depends on and the initializations and data of the group j.
The theorem shows that each transition of T., occurs in the time frame which decreases log(n)* Note that these transitions subtle: one needs extremely large dimensions in order to differentiate two close transitions as shown on Figure 2. The phase transitions of the loss are in fact associated with transitions of ||,,||² 12 from constant order to order vn, and by Lemma with transitions on the local-PL. from order 1 to order
n
VT
5 Experiments
In this Section, we aim to perform deeper experimental investigations on the system, which we could not do formally. Precisely, we want to answer two questions:

---

Rescaled loss trajectory in dimension 1.7 1018
Ln())
(t)
(t(
Loss
0
||P;1
|PiIl
Normalized time
Figure 2: Simulation of the loss trajectory of network with neurons and group initialization, each activated separately on half the data points. Ln is the rescaled loss for n examples, and L is its limit n goes infinity. We can see two phase transitions in the very high-dimensional regime.
1. What is the probability that the loss reaches 0 for n data points in dimension d, under the distributional hypotheses of Lemma 3 Sub--Gassian zero-mean and whitened data)? What is the maximum n for fixed d such that global convergence holds with high probability
2. In the orthogonal case, is the asymptotic exponential convergence rate of order 1 (on average over the initialization) stated in Conjecture I?
Vn
The data and weights distribution which have been used for the experiments below be found in Appendix B, and the code is available on GitHub.
5.1 Probability of Convergence
This section aims to test the limit in which Corollary holds when the number of data points crease. Intuitively, as the number of examples grows, the neural network becomes less and less overparametrized, and hence is expected to fail to globally converge. Knowing if and when this occurs with high probability important for us to understand how much our current threshold Cvd be improved. We thus plot the probability of convergence, well as the loss at convergence to obtain additional information when the probability is zero. We train 500 one-layer neural networks with the normalization presented in Section 2, dimension d 100, ranging from 2500 to 3500, and Pa = C' log(n) neurons. Additional details on the training procedure can be found in Appendix B.
Figure shows that for S 2900, the probability of convergence is very likely, for 2 3100 the probability is almost zero, and in between, there is sharp transition. This sharp transition is visible for any value at some point N (d,p), p), which we name the convergence threshold. By measuring C(p)d, with
the point for different values of d and p, we see that the threshold scales like (d.,p) C(p)) which is sub-linear (see Figure 5 in Appendix B). In particular, for n I Cdp, there exists a network that interpolates the data, meaning that the convergence threshold is not threshold for the existence of a global minimum. The threshold's 's scaling is linear in which implies that proving convergence for Cd data in dimension seems feasible.
5.2 Empirical asymptotic local-PL curvature
In this section we test Conjecture 1, and to do we measure ju()) during the dynamics, and mostly the end of the dynamies, since we know by Lemma 4 that near 0 the local-PI. curvature of order To provide the strongest evidence for the conjecture, we measured the order of the local-

---

Likelihood of global convergence dimension 100.
1.0
Transition at 3000
Percentage of remaining loss
0.6%
L(t - s)
Z(t= 0)
Probability to reach
0.8
Probability
0.5%
0.4%
0.6
0.2%
0.2
0.1%
0.0
0%
2600
2800
3000
3200
3400
2600
2800
3000
3200
3400
Dataset size
Dataset size
Figure Left: Probability that a network trained on n data converges loss. We observe transition 3000, from likely to unlikely convergence. Right: Loss at convergence normalized by the loss at initialization. For n 2 3000, the loss increases to 0.6%, which is equivalent to fitting all but one example.
PL. curvature in three ways: by directly measuring the local-PI. (u(o)) = log Libre-1)
at the T.(t.)) and finally by
L(xx)
last epoch fo0. by measuring the average-PL curvature (Moo) = 1 log mesuring the lower and upper bounds on the local-PL given Lemma
L(0)
1 as n increases. To Following Conjecture 1, all approximations should likely be decreasing Vn show this, plot the log-log graph of each measure above. We train 500 networks in dimension 2000, with n ranging from 1000 to 2000, and p., = Co)g(n). All resulting plots appear linear in the log-log scale, with slope close - (see Figure in Appendix B), meaning that the scalings indeed in C. This empirically confirms conjecture that the local-PL. curvature has order yx"
asymptotically.
6 Conclusion
We have studied the convergence of the gradient flow on one-hidden-layer ReLU networks with finite datasets. Our analysis leverages local Polyak-Lojasiewicz viewpoint the gradient-flow dynamics, revealing that for large dimension d in the order of n² data points, we can guarantee global convergence with high probability using only log(n) neurons. The specificity of the system relies on the low-correlation between the input data due to the high dimension. Moreover, in the orthogonal setting the loss's exponential rate of convergence is least of order and at most of order - which is also the average asymptotic order as experimentally verified. For a special initialization of the network, phase transition in this rate occurs during the dynamics.
Future Directions. We are most enthusiastic about proving the convergence of the networks for linear threshold d > Cn, which should require new proof techniques, as well as quantifying the impact of large amounts of neurons the system, which has been overlooked in study. Future work should also consider using a teacher-network to generate the outputs, in order to link the probability or interpolation with the complexity, in terms of neurons, of the teacher.
Acknowledgements
This work has received support from the French government, managed by the National Research Agency, under the France 2030 program with the reference PSAI" (ANR-23-IACI- 0008).
10

---

References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International conference on machine learning, pages 242-252, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op-
timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332, 2019.
Francis Bach. Learning Theory from First Principles. MIT Press, 2024.
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:468-477 2021.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Etienne Boursier and Nicolas Flammarion. Early alignment in two-layer networks training two-edged sword. arXiv preprint 1rXiv:2401.1079) 2024a.
Etienne Boursier and Nicolas Flammarion. Simplicity bias and optimization threshold in two-layer relu networks. arXiv preprint urXivv2410.02348, 2024b.
Etienne Boursier, Loucas Fillaud-Vivien, and Nicolas Flammarion. Gradient flow dynamics of shallow Relu networks for square loss and orthogonal inputs. Advances in Neural Information Processing Systems, 35:20105-200 18, 2022.
Sourav Chatterjee. Convergence of gradient descent for deep neural networks. arXiv preprint arXiv:2203.16462 2022.
Zhengdao Chen, Eric Vanden-Eijnden, and Joan Bruna. On feature learning in neural networks with global convergence guarantees. International Conference on Learning Representations, 2022.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in Neural Information Processing Systems, 31, 2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. International Conference on Learning Representations, 2019.
Spencer Frei, Gal Vardi, Peter Bartlett, Nathan Srebro, and Wei Hu. Implicit bias in leaky reL. networks trained on high-dimension data. The Eleventh International Conference on Learning Representations, 2023.
Ivan Gentil. L'entropic, de Clausius aux inégalités fonctionnelles. HAL preprint hal-02464182, 2020.
Margalit Glasgow. Sgd finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the xor problem. arXiv preprint arXiv:2309.15111, 2023.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl: Convergence and gen- eralization in neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Arnulf Jentzen and Adrian Riekert. Convergence analysis for gradient flows in the training of arti- ficial neural networks with Relu activation. Journal of Mathematical Analysis and Applications, 5 11760),12600, 2023.

---

Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 33:17176-17186, 2020.
Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference learning theory, pages 1246-1257, 2016.
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, 59:85-116, 16, 2022.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. International Conference on Learning Representations, 2020.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient descent quantizes Relu network features. arXiv preprint
2018.
Sibylle Marcotte, Rémi Gribonval, and Gabriel Peyré. Abide by the law and follow the flow: Con- servation laws for gradient flows. Advances in Neural Information Processing Systems, 36, 2024.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33), 2018.
B. T. Polyak. Gradient methods for solving equations and inequalities. USSR Computational Mathematics and Mathematical Physics, 4(6):17-32, 1964.
Grant Rotskoff and Eric Vanden-Eijnden. Parameters interacting particles: long time convergence and asymptotic error scaling of neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rXiv: 101.1.001,0 2010.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Stephan Wojtowytsch. On the convergence of gradient descent training for two-layer Relu-networks in the mean field regime. arXiv preprint arXiv:2005.13532 2020.
Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly wer-parameterized two- layer neural network. In Conference Learning Theory, pages 4577-4632, 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have shown with a theorem and experiments the convergence of the neural network setting we considered.
Guidelines:
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations is not a true deep neural network, discretization has to be carried out, and weaker assumption on the data could be made said in the conclusion.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Simply refer to the appendix and theorems statements.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In the experiment section, every thing is stated reproduce them.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: See link.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ys]]
Justification: Yes, in the link to the code and the details of the experimental section.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer:
[No]
Justification: We should add the error bars add some statistical precision Figure 2.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
13

---

Justification: Theoretical paper, time is very short to produce the experiments. Yet, justifi- cation can be found in Appendix B.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //turr///euuip///eee hwtpp//bll.c/tticcccueeeeee//eee
Answer: [Yes]
Justification: Theoretical paper.
Guidelines:
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Theoretical study.
Guidelines:
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Theoretical study.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Theoretical study.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: Theoretical study.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Theoretical study.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Theoretical study.
16. Declaration of LLM usage
14

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Theoretical study.
15

---

simple combination ORGANIZATION OF THE APPENDIX
The appendices of this article are structured as follows. Appendix contains the proofs of each of the 10 statements of the paper in an entitled subsection, with additional lemmas included in the relevant subsections. Only Corollary doesn't have a complete proof as of Lemma 3 and Theorem 1. Appendix B contains additional details on the experiments that were performed in Section as well as graphs for scaling laws, Finally, Appendix contains general discussions about the possibility to provably learn 2d inputs in dimension d, and the possible collapse of the second-layer weights.
A Proofs
Let note few equations that we will references for the proofs below. First, the two equations from the gradient descent (3) are the following.
d
aj
2 _
w
(13)
dt
d
1 = XP,R
(my
(14)
dt
In matrix notation, R(t) is the column vector of the residuals, X is the data matrix, and Pj is the diagonal matrix with diagonal elements 4i, = (wylar)) A second important derivative of the system is then the residuals.
d dt
(10(2z) taj (wyla)))
( d dt
ri
)=1
1,,00 T w X +a, XPP, XP,R
np /=1
(15)
d
+ Pj xP, Po,
dl
mip
MR
with M a time dependent symmetric matrix. Finally, taking the product with R in equation (15), we obtain an equation on the local-PI. curvature.
dl L(1) - R2 (())(())))))))))))))))))))))))))
d
2
(16)
m(t) = (()))))(())(())
where we recall that R =
R [[]
A.1 Theorem
Lemma 5 shows that number of neurons of order log(n) is both necessary and sufficient obtain the event I, which corresponds to an initialization of the network which guarantees convergence.
Lemma 5. Suppose ys + O, and let I be the event: for all i, there exists j such that, (w)(0)) and uj (0)m > 0. For all E > 0,
ipp 2 l))((2), then PZZ) 2 1,
ifp S 3log(") 2, then P(I) < E,
and thus, PTZ) 1 implies [3 log( () 2, 4 Alog(2)) []
16

---

Proof. of Lemma Let us note (w)(0))z;) Was and A, a, (0)y; random variables which are symmetric. A, are independent with all variables, while W are independent with all variables Aj and W Wg. with q #
P(Z) P(v. Ej. (w,(0) oNam 0)
=P > 00A0>00A0000
=1 =1-P
UN W SOU A₂ 50
2 1 nP (0 Wi, SO 50
(17)
nPP (W., SOU A₁ 50)
n(1 P (Wi,. > 00 > 0))
n (1 P (Wij P) > 0))
Replacing the expression with p = 4 log(? ) 2 -
log ( 2
log( Tog 3
we find that the probability
larger than 1 - E. Now for the other bound,
P(Z) ((vi 3i, (wy (0)1zz) > Onag > 0)
WeS > On >0
SP
nu W >0
3
= PP
U Wis >0
(18)
(1 P (W1,1 > 0)P)"
(1 2 p-n
E 3l0g(2))
< 1 4
< (1-4 m
< 1 -
where we use (1- x) <
x < 1 I valid on a E [0,1]. 1].
Lemma 6. Let O, and p 2 log (2) max ((latul3)+ (llle)))) ) ,1a(( (oo[w|)++ll +) c.
for any vector > O a constant, and || l the sub-exponential norm. We have the following bound on the loss at initialization.
PP (L((0) < 2(C 2 2
(19)
17

---

Proof. of Lemma 6
First, let upper bound the loss at é 0.
1 n
L(O0) = 2n im1
r
2
1 n
p as sulyllos)+
Σ j=1
yi
(20)
2n
1
aj (wy (w))1z1) 11 Σ j=1
2
Since a, w are sub-Gaussian random variables, the product is a centered sub-exponential random variable. Now, using Theorem 2.9.1 from Vershynin (2018), get the following bound
1 P j=1
1 p
P
S
K
2 1 P
ag (wyl())) K
(21)
-op min
[1atusler) 13 "1latyy1e))+ll)
x²
2 1 2e
log # op
log +) op
where e is an absolute constant. Taking K = ||a(wy) (2))++1)++>+ max
we get that
the sum bounded with probability least 1 E. Now using the inequality on p in the statement and that w as a distribution invariant by rotation, we obtain K s Oit, and thus
L(00) S 2(
(22)
Lemma 7. For any set of parameters 0 (ay, w. (), f=1:p the following bounds on the local-PL. curvature hold.
2 (C+) )2 max Σ (1az12 +111,111)) mMt) <
1
n
j=1
(23)
m(1) 2 2 ((C))² 1| Dxll) min
lay 11
where we recall that Dx denotes the diagonal matrix with coefficients ||x:||
Proof. of Lemma 7
We start from equation (16), which shows that the local-PL. curvature lies between the largest and smallest eigen values of the symmetric matrix M (t).
F w XP,R) + P11
ntt)
(24)
n
By the triangular inequality, we have on the local-PI. curvature.
< (m
XP, R7 < 11 which gets us bounds
2
2
|a ||1
< p(t) <
[||w + |a
(25)
TPP
Top
j=1
We transform the term
|XP,R112 to make || X
Dx appear.
|| = R x
=R =] (Dx - (XT - - RD
(26)
= =IIVDx - -
18

---

Now, by bounding vDx by its largest and smallest cigen values, namely C# and C we get the bounds on this term.
(C -
Dx <
(27)
The next step is to find the lower bound on the two remaining terms.
P P
E = 12(1)
agl
ag
(28)
R
E rt())
By inverting the sum in i and j. and taking the minimum of maximum over j. we get the bounds.
min i p
0 -
(29)
p
1 P
(lay 2 + ||0 1)
min
Σ p
1
p (1a,1 + ||,
(30)
From equation (25), we use the equation (27) as well as equation (29) for the lower bound and (30) for the upper bound and find the expected bounds on the local-PL curvature.
Proof. of Theorem 1
This is a proof based on the sketch visible in Section 3. The proof convergence relies on three key points:
(i) The loss strictly decreases as long each example is activated by at least neuron.
(ii) For a data point, there exists a neuron which is activated at initialization, then at least one neuron remains activated throughout the dynamics.
(iii) At initialization, the previous condition satisfied with large probability.
We finish the proof with the lower bounds on put) and (pss).
(i) First, Lemma 7 shows that, by computing the derivatives of the loss, we get a lower bound on the curvature.
P la
n(t) 2 ((0-)2-1xx3) - Dx min
-
(31)
We want to show the strict positivity of this lower bound. First, using Assumption 2, we have for all that
- (C7) (1
1 C
1 2/2 ( (C (32)
3
2/n Ct
which also holds for n since then ||X"XX Dxll = 0. Moreover, thanks to the asymmetric initialization, have |a, 12 la, (0) I0, [2 0, which means that p(l) is bounded away from 0 as long as for all there exists j satisfying (t)(a)) > 0, i.e., that 1,,5 = 1.
(ii) Let fix the data index i [I, and y, 0 without loss of generality. Let us define the index of the largest correctly initialized neuron j.
of
arg m (t))(z) a
(33)
19

---

Since aj cannot change sign thanks to Assumption 1, (wi; (4)) is continuous, and has a derivative over each constant segment of Jr. We can write the derivatives of this neuron as
a
w dl
(2))
Th (x
aj:
T x P R 6
" (Dx - -x - Dx)P;;
n
(34)
[ri1 11 12,18; ||X* X Dx Dx||||[]
0j
Fillz:|' 15,5, - 11x - -xxllv (0,
az
[r|laz 12 157585; - ||x x Dxllv (0.(
We use Assumption 2 to have || Dxll < 2/7 (C,) C5 and lemma with to have L(0)) < 2(C with propability at least 1 1. Moreover, 83;81 O, gets us the following inequality.
C3
Cy )C
|
(wo; (2s)
|ay
(35)
n
yh
Now, the strict positivity (w;; (xn) is an invariant of the system: if 2 1, then (wip (ax) strictly increases, and otherwise we have
1 p
p
lay
0
(wylz))+
(1) (z,)
(36)
y1
yi
Which implies that (my; (x)) stays strictly positive throughout the dynamics.
(iii) As shown in Lemma 5, for p 2 4 log 2m
we have the strict positivity with probability 1 - 2
P(Vi, Fj. (wy (0) x 0 ayys > 0) 2 -
anay
(37)
Finally, we prove the lower bounds on the PL. Let us recall that (ayl 2 ||y/| (w,(())=;)- which gives us
and that 15.6 2
1
y/ rt(t)
Σ
a,
1
as (w,l
(38)
p
C
We can plug these into equation (31) to obtain
6 (C
(t())
m(t)
Cy min
(39)
5m
yi
We obtain the final lower bound on the local-PL curvature by seeing that /2 2 2- last equation, by integration, obtain
From this
1 L p(u)du
1
6 (2=)²
Cū (1 Jo
ri(u)
t
5n
C+
max
yi
du
(40)
Let satisfying max; (ra(t)) < for all 2 ts. to exists and finite since the loss reaches 0. Thus, we have for any d > 0 that
1 l u(u)du 2
6 (0
(
ts
max (mml(Ou)
t- L5 6
1
(41)
5n C
v/b
20

---

whic the limit t + too gives
(c Cy (1- -8)
(1ra) 2 5n C
(42)
Taking d gives the desired bound on the average-PL curvature. In total, we use two bounds valid with probability 1 2. we by the union bound, the Theorem valid with probability least
1 s. Moreover, we check that taking in the statement Ca.w = [1) allows us to use both lemmas 5 and 6.
A.2 Lemma
Proof. of Lemma 3
This proof heavily relies the result of Vershynin [2010, Remark 5.59] the concentration of sub-Gaussian random variables. It states that if A E Raxd a matrix, the columns of which independent centered, whitened', sub- SabbGaassian random variables in dimension d, then with probability -t-
1 AAAAA A La S Vd
(43)
with > 0 depending only on max; ||Aille the sub-Gaussian norm of the columns. We use this property with A, vdi, which satisfies every hypothesis, in particular is uub-Gaussian since the norm is constant. Taking log (2), we obtain the following bound.
||'X - 1al
1 - A la
n
log 2
(44)
d
Moreover, we can link this concentration inequality with the control term of Assumption
x Dxxl -
D
Ia)
p |
2
D x
XD
Ta
s (C 1|8T8 Tall
(45)
log (2) d
s (Ct)
n CV
d
Thus, the condition in Assumption is satisfied with probability as least 1 if
C
(ohn²
2 n nog
d
(46)
Cy
C.
Recall that C+.- are independent of n since Px, has compact support away from v.3
Proof. of Corollary 1
To prove the corollary, we simply use Lemma instead of Assumption the proof of Theorem
Moreover, check that taking p in the statement allows to have each Lemma 3, 5, and 6with
A.3 Proposition
Lemma 8. Let > O. Suppose that
1. the (x.) form an orthogonal family of non zero vectors, and that (y:)i= are non- zero,
"I this article, Vershynin [2010, Remark 5.59] uses the isotropy of the columns, but defines it as [[xx]]= La which we rather refer to whitened distribution.
21

---

2. for all j E [1.p]. (1u))) A for some constant > 0,
3. and that for all E [1, nd], there exist j E [1. such that (w)(0))z)) > and 0 (0)y: 0.
Then, there exist a constant к depending only on C2.y A. ||llos and [| [2] such that if d 2 klog(p) log (mp) log (t)², then with probability at least 1 the initialization of the network, ln
2n
max (w, (0))(O0))))) (0) we have
C5 Cr
a
ay (O) > 0 = (tn)()))=z)+ 2 (wy(0)/z)) a (0) 0 = (1n((4)))z))- S 0.
(47)
This Lemma states that, for orthogonal data, incorrectly initialized neuron, i.e. neurons for which ajyi O, vanish in finite time, and cannot become active again. Thus, after time ln the system is decoupled between the positive and negative labels, and only correctly initialized neuron, which are useful the prediction, persist.
In particular, it is possible to show that neurons vanish if y: = 0. but the vanishing doesn't happen in finite time.
Proof. of Lemma 8 We start by computing the derivative of a neuron in the orthogonal setting, which is given from equation (13).
d (wyl
(48)
dt
This equation shows that neuron is null or negative at any point in time, then it stays O. Thus, let us only discuss the case of neurons that are positive at initialization. We will show that, before any r; can change sign, each neurons for which (0))) 0 reaches 0. Let & be the first time any Ir; Vel > 2
v. For t < t neurons evolve monotonously depending on the sign of a, (0);;:
for j.ú such that ay (0)g; < the neuron decreases, and for a, (0)y; > the neuron increases. If a (0)B) < 0, we have
d (wylar) S V [la,(0]22 [0)] M/
|,5||
dt
2n
(49)
M
(wylzz)+ < (w)(0))21)-
L,, 2n
|
where [a,(0)]2 ||w, (0) A Other wise the same equation gives for ay a;(0)
d di (wyl aa,(0)]² || [0]]
| |,,:||11,
2n
(50)
1, 1v
(wylxz)+ 2 (0)(0))
b |x
Let En = 2n max, (ur, if in < t then we have extinction in finite time, i.e., the incorrectly
C C
initialized neurons have reached In the meantime, neurons for which a,(0) > 0 will stay positive. Let us show that f., residuals have almost not moved. We thus suppose t First, bound the second-layer neurons aj using equation (14).
1
dt 0.
ruy (x:)+
(51)
3C'
(w (r1)+
2n
From equation (48), we also have the following bound.
|a, |r 1
di (w, (xi))a))+++ 5
C (C:
(52)
n
2n
22

---

Combining both bound give a differential equation on a, which we can solve.
d
aaو = K
layl
dt
n
(53)
aay S lay (0)lek
Where K = (CC))))((C)) We get similar bound on the neurons.
d dt max(w)));2)++
max d di
(1ylkr))
[aj]
max Ira
m
K
(1y 12))
(54)
n
K
m max(wu)lx))
max
S max (0)la;)
The previous bounds show us that the growth of both layers' neurons are only constant for times of order n.. Formally we have the following bound.
Ira(t) Vil
4y (1(1)|z1)+
p
|ayl (uy|æz))
j=1
(55)
la)(0)
1=1
C+
max aa (0) max 1.
(d)
2k
Vd
Now let us note that, the norm of w was taken to be independent of d, n, So, we have by rotational invariance that for any orthonormal basis of the space (ei)i=1ad, we have the following equality for any > O.
1
E
E
(56)
Thus ([(dwle)))(lp $ [[[
do2" with the upper bound that doesn't 't depend on d, n. p. We now use Proposition 2.7.6 from Vershynin [2018] to conclude that
ot2 IP max |a,(0) s1) 2 1 clla1is lox(e)
1515P
(57)
o22 cl|<vauls), (z) 113, tox(1p)
(V) ) 51) 2 1 2e
max 1.
where C, are constants. Thus we conclude that with probability e, we have
4 max (a,(0) < ||alles| log(p) log
1515p
(58)
max (.j
(Vdw, (0) 5;
< (Vddllz)
log(np) log
4
This give the new upper bound of
C+
C log
(4)
(r:(t) yal s
||(1ke||2)21
||al|o
log (np) log(p)e 2K 2K
(59)
Vd
23

---

Now, we pose En with the following definition.
Vd
C+ C -log 33/aal/s (21kw12))11 sbz Cy
in 2k log
(60)
Vlg(p) (np( log (2)
This means that In 5- Finally, since we have I S Thus, there exists a constant k depending only on A, Ot |1 (2) p and | such that for d 2 log(p) log(np) log (t)² 2 we have En En.
We have that (re(Tn)) Vil S - z.
Vo / /c log(np) log (:)
C [1(1///112 |2
This concludes the proof, showing that the neuron initialized with 0yy < 0 reach 0 before E. of order n.
Proof. of Proposition 1
Thanks to Lemma 8, there exists i, such that for 1. 2 ln- each example has only correctly activated neurons. Without loss of generality suppose that all labels are positive. Then the network only has positive contributions ag (t)((wu)lr) (x,) 2 O for all i. Let N (j. the number of indices such that
(u(t) S (t(t)Wp) We have
N(J
a (1,
S
1
Σg
p
y/4 rs
(61)
p 7m
Thus, we can bound the norm of w/y
||w s a9 100
af (x))
p²
Y/ T/d
(62)
N(j 2)2
|2ai||
2
p²
y/ - Pi
Σ
S max
Cz
This helps us upper bound the sum of layl" / + ||00112
1 p
Σ (las) 2 + ||w0,113) 1530 S
(1w;((0) (11,(0)==11u;(0)]
1
1 +
P Σ
2
||0cy1 |1
p j=
max; (yi - r;)
p2
I c
CT
N 2j.
j=1
< + 2 max; (yi - rr))
(63)
Cz
N(,
max: ri)
1
C
P
N(J,2}²
/=1
2
max;(y; -rs)
<C + x
/np
3
Ci
Using the upper bound of equation (23) with the previous inequality gives us the upper control on (t)..
2 (Ct)2 ((t) s 2TV
t max
1
r;
P 2
+
PC
(64)
CF
Us
n
24

---

Thus, the constant C' from the Proposition statement is
max
max (0)(a)))))
CF A
2(())²² 21
(laz(0))² (|ws(0)) 15,6
1=1
(65)
2 (C
2T
C
3 C
K
with &. the constant of Lemma 8.
A.4 Proposition! 2
Proof. of Proposition 2
Recall that we initialize the network with po neurons, for which there are exactly in examples positively correlated with it, i.e., for o j that (wylx?) 0 at all time. This means that we can Pm
write h=/) "
p.. (wyyl=z [ = ||w ||+ (xy)) and s, does not change by Lemma 1. This
implies that the dynamics decoupled: w, and Wi can be studied separately.
Let us compute the dynamics for the neuron j. We let D" EI v. Ry = Et= r/al
| Σi (wyl))) and . -ell We first consider the alignment between wy and DJ:
d (D di
DT) la mt (15)"²
1 d |10g 11+ di ws
1 (D3)Ta -wj (w)) ( R₂)
1 (D2)Ia - (wx)) )r Dn $1 ||05|++03))
(66)
Pn
Vall | (1 (D7) (D
n
(1 - DDJ)(
This equation has closed- form solution which is
sinh (c) + (1715 (0)) cosh (c)))
(Dy) ( cosh ( (Dyls s wt (0)) sinh (hitt
(67)
1 d
2 dt [log (cosh (c. + (Df
1s u (0)) sinh (c)))
Now we can compute the norm of the neuron.
A no
||5 = 21|w5]
dt
2
|uyl ((D7)s
Pn 110)122)
n
||w 112 em nn Já (1,,( du = (0)1 = Si s,07 (a))
(68)
u S6 (1w5((1)) - 1
2
||w (0)1 / c (D))e, o do
npn
J (D a (w))
[|w,(1)11
(0)(0)1 1 (D)le (o)) du
1 + my.
25

---

Finally, we can replace the expression the correlation.
(t){+ Pa Po ID x (0)l (cosh (cht) (D) [5y0 (0)) sinh (cl,t)
(69)
Pa Payk, P31 + wyy (0) (inh cittt (Dy)e 1syn (cos (htt - 1)
We use this equation in Lemma 7, and easily obtain the upper bound thanks to the monotonicity of |lws < [t +o0 Pv V A,l1:
4 npp
max Σ (t)2 max, 110,
40, Vkn
40
ptt)= -
(70)
npp
na
For the lower bound, we have the bound for t 1 d
2
a
n
30
log (n(Ct)
2
20
log(pav DII)) by monotonicity. Indeed,
cosh (cht) + (D) [5y0 (0)) sinh (cltt 2
peth (1 (D))s, (0)))
1
(71)
2
and
sinh (c,,) (Dfls, (c)sh (cht) 1) s
1
c (1+ (D}ls,
(72)
2
which implies that
(,,,(1))1 2 Pa v km DJI| (wy (0)] c (1 (D) -ū, (0))
2pn. v km D
+ ||wy e c (1+ (D) 8, 05 (0))
[00) (1 + (D) 35 (0)))
2 Pr V km |D7
(73)
2 (0) [ (1 + (Dz 1,,03 (0))
(0)]12
2 Pn km |Dj
2 (0)
since (5 (0)) 2 0. Finally, we obtain the desired lower bound.
2min 100
20,
||w, (0)1
pat) 2
min Σ
Juy (t,
min 2 (0)
(74)
ntp
7Pp
n2
L
A.5
Lemma
Proof. of Lemma 4
Recall that, in this proof, p and n are independent parameters of the system. Let us recall the equation of the local-PL curvature on the system that was found in equation (16).
2 np
m4))=
(w)(0)* XP, R(O)) + ||
j=1
R(O)T
1
Σ
x x w, +1: (0, R(0)
(75)
p j=1
R(0)
n
Recall that we note P3 the diagonal matrix with diagonal 1ز, = [(wyla))-00 This means that since all terms in the sums can be computed from 0j and (wylaa) which are mutually independent random variable, that variables in the sum are mutually independent as well, and by Central Limit Theorem we have
TXP M (D) = Euca [P_ x- wid XP +1x + S
vp
26

---

where the expectancy is taken over the neurons of the network, but not over the data X and Y, and
So g-ttio S~ N' (0, V Vu.a x" www XP + |app"" x)) = -0 v()). We now apply the Central Limit Theorem on the residual R(()).
R(O) Y az Py, my Y Fu, F (aPx w|
1
So
y
S
(76)
vp
vp
with Sp have that
p-++00 E N (0. Vw w)) -N va,a (f)). Now, using equations 75 and 76, we
2 Ewwa [w0T (w=XXP)2 + 11
80
m(0)
(77)
p-+00 n
72
and for the next order
Vp(mp(0) - B0) p-+tio ~O)
(78)
with
= --VI(CC) + 2V(E) [p' x2 wwm XP |a|=p=
(79)
n
A.6
Theorem 2
Proof. of Theorem 2
We consider the setting of Proposition 2 but with fixed number of neuron p, and as in its proof, we focus on one specific neuron j for which we suppose 8, = 1. We can rewrite equation 69.
PV km
D2 Il (0)1 (cosh (c2,1) + (D (0)) sinh (ct,))
||w,
(80)
PVK,,| Dy + 1|w (0)1 sinh (cht) + (Dy wa (0)) (cosh (cht) - 1)
Let us rewrite the loss of the group j.
(1(t) 2k
(r2)
kn
|1 11+ (1n5
2 (oot (o;))
(81)
y
2kn
i=1
1
||
2
10 )| 1y + kapp || 11
2
VEnP
Let (k)) ot log(spykn) km 12))), where c/. 2 which depends on the variable >> 0.
We have
xc| x0]1,(0011 (1 + K(in) + (D' 10 (0)) (1- K(jgn)"
(1w (x)) k/k,, |D
2 + s: (0) 1 k(im)² + (D3110 (0)) (1 k(j.n) 2
(82)
with K(jnn)
Ve.PllDp11 Moreover, we have
K(jm)
+ (D (0)) (1 K(jm)) N²
(t 1 K(in)² x²
x²
(83)
+ (D)10) (0)) (I- K(j,n)
x²
Thus, by taking n large enough, there exists k(j, n) e) such that L' (t) (NG[), n, (n) = L (t)
=
E|| For simplification, we use (E) 13 (1()) (,))), Moreover, n(j, n,, - k² (E) when goes to infinity.
vo (=)) (0)1 2 = E 2 - (=)))|,
1 | ((((())) + 2
(84)
2
27

---

11 This shows that x² (c) ( 1 (I1-v))) Thus, we have phase transition since the lost goes from 1 - e in a time which, after normalization, goes to O. The time of the phase transition is
(E())
log(n(J, n, doynplog(n)
1
(85)
tn
|Dj1
and its cutoff window is
1 (5) 1 - E)
x(j,n,))
R (E) 12 E)
log
K(j n, -E)
Cit
~n
2
log
log(n)
(86)
where we recall that tn phase transition at times
log(n). We conclude that the normalized loss thus has at most Moreover, the constant in the Theorem is
D
(1 VE) 1+
1 1 (1 vT-E) 8
1 2
(5)
(87)
VE)
(I-VI-8
8 1 +|11711
A.7 Other results
Proof. of Lemma 1
We verify that ( wy (uy) aj क7 dj. using the derivations from equations (14) and (13). Integrating this equality gives the expected invariance.
d
Proof. of Lemma 2
By definition, we have p(t) I(Or). Thus,
LV and by property of the gradient flow, [V)(),)) L(P.)
d dt L(e,) = (())
log(L(O.)) - log(L(((0))) = [: p(x)dxx
(88)
L(O.) e(((0))e- (p(0))
B Experiments
This Appendix contains additional details on the experiments done in Section 5. Data generation and weight initialization were performed follows: initialize all neurons independently as Wy ~ (0, Ta) as well as Ja,T ~ ((([1,, and layl - ||w5|| ~ Exp(1) which implies (a,(0) > ||w; (0)]]- For the data, we consider y; [([ -1] U [], [1,
and ||ææ|| 2{[1, 2]) in order to
control the constants C= C. 2 and C CJ < 2. Finally, in order to fall within the assumptions
of Lemma 3, we let
TEsT U($d11) in Section 5. and zi_ be orthogonal family in Section 5.2.
Experiment 1. For the experiment in Figure 3, trained 500 networks in dimension 100, with between 2500 and 3500, with 25 runs for each value of n. We used p log( x
+ neurons for each experiment with 0.05, since this the optimal threshold obtained in Lemma 5. We trained
the networks with gradient descent using a learning rate of 1 for total time too = 1.5 x log(np) and thus e fe epochs.
C2 We considered that network converged as long as its loss went below žn which then guarantees convergence We thus early stopped the training and declared the loss was exactly O. Otherwise, the convergence went for all epochs and the network assumed to not be able reach 0 loss. In
28

---

Convergence Threshold with 30 neurons.
Convergence Threshold N(d, p)
N(d, p)
1200
Linear regression
1000
800
600
400
200
0
20
40
60
80
100
Dimension of the ambient space
Figure 4: This graph shows the scaling law the convergence threshold for a fixed number of neurons. It suggests that the scaling is linear in d: (d. C(p)d.
Convergence Threshold with fixed dimension 3
Convergence Threshold N(d, p)
400
375
350
325
300
N(d, p)
275
Regression: ap
250
Regression: avp +
Regression: alog(p)
225
50
100
150
200
250
300
350
400
Number of neurons
Figure 5: This graph show the scaling law of the convergence threshold for a fixed number of neurons. It suggests that the scaling is not linear in d, but it is hard to differentiate between sub- linear polynomial growth or a logarithmic growth.
doted line, we interpolate the probability plot using a sigmoid function, and learned automatically p).
the convergence threshold
For the scaling law on d, we fixed p at 30, and trained networks with dimension varying from 10 to 100, and n ranging from N(d, p) 15d to N(d,p) p) + 15d, with step d. For each dimension, we interpolate the probability graph using a sigmoid, and plotted the linear trend on Figure For the scaling in p, we fixed d = 30, and varied p from 50 to 400, and plotted the trend Figure 5 which shows that the scaling in is sub-linear.
Experiment 2. For this experiment, we trained 500 networks in dimension 2000, with between 1000 and 2000, with 25 runs for each value of n. We used the same number of neurons, learning rates, and epochs in experiment 1. Let recall the 4 measures plotted on the Figure 6:
29

---

PL at convergence in dimension 2000
-1.0
u(tw)
Log scale for the PL
-1.
(1m)
Slope -0.52
Hlow
-2.
Hupp
-2.5
-3.0
-3.5
Slope -0.55
-4.0
Slope -0.57
-4.5
Slope -0.52
6.9
7.0
7.1
7.2
7.3
7.4
7.5
7.6
Log Dataset size
Figure 6: Scaling laws in log-log for different measures of the local-PL. curvature in dimension 2000. Each curve is in fact linear with slope close to 2 which is expected by Conjecture 1.
1. The instantaneous local- -LL curvature at the end of the training, p(loc) log
L(tra-1)
L(toe
2. The average-PI. curvature throughout the training, (1x0) = log 1(0]
I(t
3. The lower bound on local-PL at the end of the training, Nlow 2 min; 1 Sy |a,) 1
4. The upper bound on the local-PL. the end of the training, Mupp n max; 1 Eー= 1
16
Each of the slope being close to 2. we conclude from this log-log graph that (Hoc) foreseen in Conjecture 1.
K vT
as
Each plot's related experiments were performed on MacBook Air under 2 hours without accelera- tion materials.
C Additional results
C.1 Collapse of the second layer
Similar to the carly aligmment phenomenon described by Boursier and Flammarion [2024a,b, Theo- rem 2], where the neurons can rotate and collapse to align on single vector preventing minimization of the loss, the weights a, of the second layer can also collapse
single direction. Under the hy- pothesis that [0)( Z [[wr(()) (O)]l, the scalar a, cannot change sign, which prevents this scenario in the article's results. But if (a) ||w,(0)]f they change sign, and prevent global minimiza- tion even when the neurons are correctly initialized. Proposition gives an example of such collapse in low dimension.
Proposition 3. Suppose that d = p 2. Let (x1,22) be the canonical basis of R2, with the outputs satisfying 9192 < 0, = 22 |. Let (a (0)). (2)) 8, and let minz (wy (0)(())z))) 0. Then,
v1
for 8 small enough, y1 large enough, and
8 max max(w, (w)(0)=z)))))))))))))))) 3,1
min,, (0) xz))
<
(89)
maxj. (w)(0)
30

---

we have lim ((Os)
The proof relies the ratio between outputs being large A, in order to steer the aj to change signs, but not too large to then make the neuron go extinct before the signs of 0j may change again. This traps the network in state of sub-optimal loss, and if aj were initialized large as the vectors, this collapse could not have happened.
Proof. of Proposition 3 Without loss of generality, let suppose y1 0 and y2 0. We will show that there are values of X, e for which the system will not converge. The derivatives of at the beginning of the dynamics writes
d
di " (ri(wa)r)) + (2ww)(122)
d
01 ((w1lar) - 1(w1/ [x2))
$ mmax((a1l) |a2)) max [/ ||. ||
(90)
dt
d M1 ((22/21) - {(wz|
02
$ max((a1l; (a2)) max([|u) ||. ||mz||
dt
and the derivatives of (wyl
d
(w (24))
dt
d
0,3/1 1
(w [m1)
S max((a1): I (a2)) max || [||l: ||. [[we]]
(91)
d
(wy)a
(12)
max((an); | (a2)) max wi [[02
dt
Now suppose that for s T. |ayb ||w/|1 < M and (wy)rr)))) 2 > 0, have
a1(1) 2 - + 1/1 (m AM) a/2)
(92)
a,(() s + 1/1
(M- 2m) + M²)
4
Thus, for T
(m- 252) with A 2 m and y/ 2 m- we have ay(T) > 0. We now wish M
4M2
to find the constants M, m such that the previous equation will hold. To find the constraint on m and M, let write
(wylla1) 2 (w)(0))=1
2 3IM + +M2
(wy 2 (1)(0))=22
BI M + +M²
(93)
(w)lka)) S (0))aa)
U + M²
(wylxz) < (0)(0))
21 3I + M²
Thus, the constraints are
8 2y1 M + 4M12
m 2 min
(w, (mn)a);(0))))))
3/ (m AM) - 4M2
(94)
M < max (1x + 8 2y: M + 4MM
31 (m AM) 4MM
We see that the constraint are satisfied with > min,, (w)))(( - 28 > 0 and M <
m (w, (0) (12) + 8 small enough, 31 is large enough, and À max,, (myy (2]
(we Thus,
there exists T > 0 such that time T, we have a (T), (T) 0, and no neurons went extinct.
31

---

Now, let us show that neurons (wylay) (22) will go to 0 for some time T> while the neurons a stay positive. We can use the same equations before, with this time w/yll N for t S T. and get
(2 -
(wylx2)) S (w,(00)(z2)
(95)
Thus, for T 2 max (we (0] and Ay 2N, we have extinction of the neurons.
To find the constraint on .N, use the bounds on the growth of aj and (w,(0)|z1). The constraint
Agy 2N
V1 + 2N
N max (max((y(0))2))).)) + 2 max
(96)
Xy1 2N
Thus, the constraints satisfied with N maxy, (w, (0) (1+ ) long yı is large enough, and
max (0){=) y1
(97)
After time T, the neurons (w, (0) went extinct, and thus we have L(O)) 2 O.
C.2 Non-uniqueness of the gradient flow
Since =ReLU is non differentiable at O, the gradient flow equation might have multiple solution for single initialization. To see this, let us take the example of orthogonal data, we have for every neuron Wy and data Z;, zt (wy (1)++ = ned ||>:||11,,,, L..j. As long as (wyl<z)+ >> 0, then 1,, = the neuron doesn't change anymore, and cannot become active. We are interested in the case when (wylzz) = O, which is the non-d eon-differentiable point of ReLU.
d
and the neuron can change, and if (wylat (z.)) O, then 1ij
Suppose that for t E [t1, tz). we have (t)r(((t) > and (w, (t))())) = 0. Then for each E [t1, tel there exist trajectories 0f such that at (0)(a)) ( and 1 (f)aa) 0. This means that there
exist trajectories such that the neuron (wylæ4) start growing from even if the neuron was previously deactivated. The trajectory 8¹ is as follow: for t F, 0 o¹ (t2). and then 6* solve the gradient flow equation without 1 in the derivative of (wylæ,).
Although there are different possible trajectories for single initialization of the neurons, only one of them realistic the sense that it is represent what happens in practice: the trajectory where neuron don't 't reactivate alone, which is the limit trajectory of the trajectories from the gradient descent for small step-size.
32


Reviews:
[{"review_id": "YSj51iFTmK", "reviewer": "Reviewer_PKJq", "summary": "This paper investigates the training dynamics of a two-layer ReLU neural network in a mean-field setup. When the data matrix is low-correlated (Assumption 2), it is shown that the gradient flow with the regression loss converges to the interpolating solution with order $O(\\exp(-t/n))$, where t is the training time and n is the number of samples.  They confirm that Assumption 2 holds when the data dimensionality d satisfies $d\\gtrsim n^2$ with high probability. Moreover, for orthogonal data, they provide a more detailed analysis of the convergence speed and conclude that a phase transition exists with respect to the number of neurons, where the convergence speed changes from $1/n$ to $1/\\sqrt{n}$.", "questions": "Besides what I raised above, I have the following questions:\n- Can the framework based on PL curvature be applied to other activation functions? It appears that the lower bound on the curvature (7) is crucial for achieving global convergence, which may be extended by replacing the indicator function with the derivative of other activations. \n- What is the primary motivation for employing the mean-field scaling? Since Theorem 1 only requires $p=O(log n)$, the significant difference between the NTK regime and the mean-field scaling may not occur during training. \n- Can the framework be extended to the multi-layer networks (for example, by considering the PL curvature with respect to the output layer weights)?", "limitations": "The authors properly address the limitations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**\n- The authors address the challenge of theoretically understanding deep learning training, a significant issue in the field of deep learning. The global convergence analysis using the PL-curvature in the mildly overparameterized mean-field setup is a novel approach, and it achieves a novel global convergence guarantee.\n- This paper is well-written. All theoretical results seem solid.\n\n**Weakness**\n- One significant limitation of the results is that Corollary 1 requires a huge dimensionality of $d\\gtrsim n^2$ (as also mentioned by the authors), which will be violated in practical situations. Can this condition be mitigated by considering a wider network in the same theoretical framework? While Theorem 1 only requires the network width of $O(\\log n)$, I wonder if this narrow width restricts the convergence performance of the network. \n- The group initialization defined in section 4 seems quite restrictive. Can this setting be applied to the case where we employ the Gaussian initialization?\n- The presentation of Theorem 2 seems confusing. For example, the sentence “the transitions happen at each time $t^j=...$”. Moreover, what is the motivation for comparing $t_n^j(\\epsilon)$ and $t_n^j(1-\\epsilon)$? Perhaps I have any misunderstandings about this part, so it would be helpful if these points could be clarified. \n- In Theorem 1, the formal definition of $r_i(t)$ is lacking in the main paper.", "was_revised": true, "final_justification": "While I have several concerns about the strict assumption and the potential of the PL-curvature framework, the authors' response partially addresses this, especially in dealing with the loss plateau. Unfortunately, the authors have not responded to my last question, but I would like to change my score to accept.", "rebuttal": "**Response**: Thank you for your review and interesting questions. We address them below.\n\n**1. Width of the Network**. The large input dimensionality $d$ and the large network width $p$ are two distinct components in our proof. The dimensionality is crucial for ensuring that the weights do not interact too strongly, which allows us to establish the Polyak-Łojasiewicz (PL) lower bounds. The width of the network, on the other hand, is mainly used to guarantee a good initialization—specifically, that for each input $x_i$, there exists some neuron $w_j$ that is positively correlated with it, with high probability. The scaling $p = \\log(n)$ primarily arises due to the ReLU non-linearity; different activation functions require different scalings. For instance, non-zero Leaky ReLU requires only a constant number of neurons. That said, increasing the network width could potentially strengthen the results, but doing so would require a different analysis that is compatible with, yet distinct from, the PL framework.\n\n**2. Group Initialization**. The group initialization setup is a toy example intended solely to demonstrate that the lower and upper bounds are tight for orthogonal data. Its purpose is not to model any real-world data distribution. As stated in Claim 5.2 of our experimental section, we expect that Gaussian data should converge at a rate of $\\frac{1}{\\sqrt{n}}$.\n\n**3. Theorem 2**. We apologize for the lack of clarity in the original statement. Theorem 2 aims to show that under group initialization, the network learns one group at a time in the large-$n$ limit. This is demonstrated by rescaling the loss, which becomes a piecewise constant and decreasing function in the limit. Consequently, within a short interval of order $\\log(n)$, the network fully learns a group. We also quantify the width of this transition using the times $t_n^j(\\epsilon)$ and $t_n^j(1 - \\epsilon)$, following the methodology used in cutoff phenomena for Markov chains. This analysis reveals that *the transition width decreases as $\\frac{1}{\\log(n)}$*, which is very slow and hence not visible in practice. We will make that discussion clearer in the revised version of the paper.\n\n**4. Residual**. Thank you for pointing this out—we indeed omitted the definition of the residual. We will clarify that $r_i(t) = y_i - h_{\\theta(t)}(x_i)$ denotes the $i$-th residual of the loss.\n\n**5. Activation Function**. It is possible to use other activation functions and still obtain convergence results. A simple example is any monomial function of the form $x \\mapsto \\alpha x^\\beta$, with $\\beta > 1$ and $\\alpha \\neq 0$. Such functions satisfy Lemma 1 up to a constant, and the proofs adapt easily. We believe other monotonic activation functions could also work well, though computing their convergence rates might be more challenging. While various activation functions are indeed applicable, we chose not to discuss them in the main text as they do not significantly contribute to the intuition. However, we will include an appendix discussing how different activation functions affect the convergence probability and rate.\n\n**6. Mean-Field Scaling**. We adopted mean-field scaling to normalize the network and to clearly distinguish our regime from the Neural Tangent Kernel (NTK) regime, even as $d$, $n$, or $p$ become large. Using other scalings often hides key constants (e.g., $\\frac{1}{p}$) inside initialization terms, as is done in PyTorch, which makes the limit $p \\to \\infty$ less transparent. We chose this scaling for the sake of clarity and interpretability.\n\n**7. Multi-Layer Networks**. Multi-layer networks are more difficult to control due to the possibility of intermediate layers collapsing before fitting is complete. In our setup, collapse is avoided thanks to Lemma 1 (which prevents $a_j$ from approaching zero) and by controlling the weights $w_j$. However, in deeper architectures or with multi-dimensional outputs, our result no longer holds, as it becomes difficult to simultaneously control multiple sets of weights. Understanding why deep networks avoid collapse in our regime is an interesting and important question, which warrants further investigation and will likely require new techniques for managing groups of neurons."}, {"review_id": "UwlGvvbZrC", "reviewer": "Reviewer_6fYV", "summary": "This paper analyzes the convergence properties of one-hidden-layer ReLU networks trained via gradient flow on finite datasets. The main contribution shows that when input data have low correlations (which occurs naturally in high dimensions when d ≳ n²), networks with only O(log n) neurons can achieve global convergence with high probability, regardless of initialization scale. The analysis employs a Polyak-Łojasiewicz (PL) framework to characterize convergence rates, proving exponential convergence at rate 1/n in the general case. For orthogonal data, the authors provide refined analysis showing convergence rates between 1/n and 1/√n, and demonstrate phase transition phenomena in the convergence dynamics. The theoretical results are supported by numerical experiments that validate the predicted scaling behaviors.", "questions": "1. **Necessity of assumptions**: How critical is the asymmetric initialization assumption (Assumption 1)? Can you provide more insight into whether this is merely sufficient or actually necessary? Have you explored alternative initialization schemes that might work?\n\n2. **Scaling improvements**: Your experiments suggest the convergence threshold scales as N(d,p) ≃ C(p)d rather than the theoretical √d. Can you comment on the gap between theory and experiments? Is there potential to improve the theoretical bound to linear scaling in d?\n\n3. **Extension to deeper networks**: How might your analysis extend to networks with more than one hidden layer? Are there fundamental obstacles, or is it primarily a technical challenge?\n\n4. **Practical implications**: Given the restrictive dimensionality requirements, can you discuss scenarios where your results might be practically relevant? Are there applications where d >> n² naturally occurs?\n\n5. **Comparison with existing methods**: How does the performance of networks in your regime compare to other approaches (e.g., kernel methods, linear models) that might be more natural in the high-dimensional, low-sample regime?", "limitations": "The authors adequately acknowledge several key limitations:\n\n1. The restriction to shallow networks and square loss\n2. The artificial nature of the asymmetric initialization\n3. The high-dimensional requirements\n\n\nHowever, they could better address:\n\n1. **Computational considerations**: Training in extremely high dimensions (d ≳ n²) has significant computational costs that aren't discussed\n2. **Statistical considerations**: In the regime where d >> n, overfitting becomes a major concern that the paper doesn't address\n3. **Broader applicability**: More discussion of when the assumptions might be realistic in practice would be valuable\n\nThe limitations discussion is reasonable but could be more comprehensive regarding practical deployment considerations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. **Novel theoretical contribution**: The paper identifies a new regime for neural network convergence that doesn't rely on either the lazy training regime (NTK) or infinite-width assumptions (mean-field). The requirement of only O(log n) neurons is particularly striking and practically relevant.\n\n2. **Rigorous mathematical analysis**: The use of trajectory-wise Polyak-Łojasiewicz analysis is sophisticated and provides sharp convergence rate characterizations. The proofs appear technically sound and the bounds are non-asymptotic.\n\n3. **Natural assumptions**: Unlike previous work requiring carefully tuned initialization scales, the low-correlation assumption (Assumption 2) arises naturally in high dimensions, making the results more broadly applicable.\n\n4. **Comprehensive analysis**: The paper provides both general results and refined analysis for the orthogonal case, including interesting phase transition phenomena that add theoretical depth.\n\n5. **Experimental validation**: The numerical experiments effectively support the theoretical predictions, particularly regarding scaling laws and convergence thresholds.\n\nWeaknesses:\n1. **Restrictive dimensionality requirement**: The condition d ≳ n² is quite strong and may limit practical applicability. While the authors show this leads to √d data points on average, this is still restrictive compared to typical machine learning scenarios where n >> d.\n\n2. **Asymmetric initialization assumption**: Assumption 1 requiring |aj(0)| ≥ ||wj(0)|| is somewhat artificial and doesn't align with standard initialization schemes (as the authors acknowledge). While they provide a counterexample when this fails, the necessity of this assumption is questionable.\n\n3. **Limited scope**: The analysis is restricted to one-hidden-layer networks with square loss. Extension to deeper networks or other loss functions is unclear, limiting the broader impact.\n\n4. **Gap between theory and practice**: The orthogonal data assumption, while mathematically convenient, is unrealistic. The general case requires very high dimensions, creating a disconnect from practical scenarios.\n\n5. **Experimental limitations**: The experiments are conducted on relatively small scales (d=100-2000, n≤3500) and don't fully explore the boundary cases where the theory might break down.", "was_revised": true, "final_justification": "I would like to keep the same score as the limitations are still prevalent.", "rebuttal": "**Response**: Thank you for your positive review and thoughtful questions. We’re glad you appreciated the paper. Please find our responses to your comments below:\n\n**1. Necessity of assumptions**. The paper shows that the convergence holds with the asymmetric assumption, i.e.for **all** $j, \\, |a_j| > ||w_j||$, and that it may not hold **when** $|a_j| < ||w_j||$ for all $j$, as shown in Appendix C.1. This makes this assumption necessary for the result to hold. Now, the assumption-free case makes room for edge cases that look like the proof from Proposition 3. However, these edge cases often require initializations which are unlikely, and thus can be excluded in a reasonning in high probability. While we believe this assumption is unnecessary, we were unable to rigorously prove this within the scope of the present work.\n\n**2. Scaling improvements**. We do think that the gap between Theorem 1 and the experiments can be improved. In the proof of Theorem 1, we need a constraint on the dimension in two critical steps: 1. the lower bound in equation (23) which requires only $d > n$, this is a rank constraint, and cannot be improved with our method, 2. the lower bound between equations (24) and (25) requires the constraint $n \\sim \\sqrt(d)$, and comes from an upper bound on the norm of the residuals $|r_i(t)|$. The second constraint could be losened up by having a better control on the residuals. In this case, the theoretical scaling would become $d \\sim n$.\n\n**3. Extension to deeper networks**. Multi-layer networks are more difficult to control due to the possibility of intermediate layers collapsing before fitting is complete. In our setup, collapse is avoided thanks to Lemma 1 (which prevents $a_j$ from approaching zero) and by controlling the weights $w_j$. However, in deeper architectures or with multi-dimensional outputs, our result no longer holds, as it becomes difficult to simultaneously control multiple sets of weights. Understanding why deep networks avoid collapse in our regime is an interesting and important question, which warrants further investigation and will likely require new techniques for managing groups of neurons.\n\n**4. Practical implications**. Our goal in this paper was to understand convergence of neural networks in the most natural training setup. Unfortunately, this requires unrealistic assumptions on the data, which should be lifted by future work. In practice, since one-layer networks are not really used, it is hard to find examples to compare ourselves with. To illustrate, if we compare our model in terms of parameters-data ratio, and cite Phi-2 with a 519:1 or the ResNet-50 trained on Cifar with a 460:1 ratio. Given the sizes of the models, this is still far from the scaling $d * p \\sim n^2\\log(n)$. But should Theorem 1 be extended to the empirical scaling $d\\sim n$, the ratios would be very close for some architectures, with a $\\sim d*\\log(d):d$ ratio.\n\n**5. Comparison with existing methods**. While this would certainly be valuable, we did not compare with existing methods in this paper. This is because the theoretical understanding of neural networks remains far from practical setups. We focused our efforts on understanding convergence rather than generalization. Nonetheless, studying test-time behavior and the properties of the minima found is a natural and important direction for our future work."}, {"review_id": "3uwFbhNhC8", "reviewer": "Reviewer_5dzT", "summary": "This paper studies the convergence rate of two-layers ReLU networks on \"almost\" orthogonal data. The authors first show a convergence rate of $\\Omega(1/n),$ for the weak-correlated data case, where the correlation of the data points are of order $O(1/\\sqrt{n}).$ Then the authors show the upper bound of convergence rate is of order $\\O(1/\\sqrt{n})$ for completely orthogonal data, and $O(1/n^\\alpha)$ for any $alpha \\in [1/2, 1]$ under extra initialization assumptions. Finally, the authors show the different stages of training under the settings with completely orthogonal data and the initialization assumptions.", "questions": "1. Please also refer to the Strengths and Weaknesses part.\n\n2. For the results in Proposition 2, what are the technical difficulties that require the completely  orthogonal data? \n\n3. For the group initialization, is it possible to prove it for any reasonable initialization of the weights? For example, random initialization with small enough variance.", "limitations": "There's no potential negative societal impact of this work in my opinion. The authors discuss the limitations in the checklist.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths \n\n1. The paper proved the convergence rate of two-layer ReLU networks on \"almost\" orthogonal data, with $O(\\log(n))$ neurons, I think it's an interesting result.\n\n2. The paper proved the convergence rate by lower-bounding the local-PL curvature, which looks interesting and could technically benefit future works.\n\n3. The paper is in general well-written and is easy to follow the main points. The definition of $r_i(t)$ in Theorem 1 is not clear enough though, I suggest the authors define it properly.\n\n\n### Weaknesses\n\n1. This paper only discussed the convergence rates of the two-layer ReLU networks, while I believe the results are new and interesting, I'm not sure how significant are the results. I wonder if there are further insights, such as the implicit bias of the  weights, can be induced from the results?\n\n2. The results in Proposition 2 which requires the group initialization are a bit restrictive. In particular, the group initialization requires each neuron to be active with only one different group of data points. This seems to mean that: (1) the weights are already learned some non-trivial information of the data, (2)  since all the data are orthogonal, the weights are moving in different subspaces, and the training of the networks are equivalent to training $p_n$ independent $1$-neuron ReLU network on different datasets.\n\n3. There are also a few other assumptions that limit the scope of the results, such as the requirements of large $d,$  special initialization of $|a_j(0)| \\geq \\|w_j(0)\\|_2,$ and completely orthogonal data for faster rates. However, I believe those assumptions may reflect the broader challenge in developing rigorous theoretical descriptions of neural networks, and I do not consider them as major weaknesses.", "was_revised": true, "final_justification": "This paper studies the convergence rate of two-layers ReLU networks on \"almost\" orthogonal data. After the rebuttal. My initial major concern is on the strong group initialization, and a feww other assumptions. In the rebuttal, the authors mentioned that it is possible to generalize the results to Gaussian initialization with small enough variance, which justifies the utility of the theoretical results better in my opinion. Thus, I would like to keep my initial evaluation.", "rebuttal": "**Response**: Thank you for the review, we addressed your questions below.\n\n**1. Proposition 2**. Orthogonal data enables us to integrate exactly the system, and have the tight bound in equation (10), of order $\\frac{1}{n^{\\alpha}}$. We need this tightness to show that all speeds in the interval $[\\frac{1}{n}, \\frac{1}{\\sqrt{n}}]$ can be achieved by appropriate weight initialization.\n\n**2. Group Initialization**. We think that there exists a small enough variance for which the Polyak-Łojasiewicz (PL) curvature still remains of order $\\frac{1}{n^{\\alpha}}$, but the lack of differentiability of the problem makes this a non-trivial claim which we should further verify. Note that the main point of the group initialization is to show that the speed interval $[\\frac{1}{n}, \\frac{1}{\\sqrt{n}}]$ are achieved by some initialization of the weights.\n\n**3. Implicit Bias**. The problem of the implicit biases are intertwined with our Conjecture: if the weights are approximately equal in magnitude (i.e., implicit bias of an L2-norm), then the speed should be of order $\\frac{1}{\\sqrt{n}}$; and if the weights are very unequal (i.e., implicit bias of an L1 norm), then the speed will be of order $\\frac{1}{n}$. The experiments in section 5.2 suggests a speed of order $\\frac{1}{\\sqrt{n}}$, and thus an implicit bias minimizing the L2 norm. We did not discuss why convergence speed would be related to implicit bias, and think this would be an interesting direction for future work.\n\n**4. Residual Definition**. Thank you for pointing this out — we will add the definition to the paper. For completeness, we provide it here $r_i(t) = y_i - h_{\\theta(t)}(x_i)$."}, {"review_id": "1Trm7cKFhx", "reviewer": "Reviewer_usDV", "summary": "The paper establishes convergence guarantees for one-hidden-layer ReLU Networks, trained on high- dimensional data. Based on gradient flow, a continuous-time version of gradient descent, they analyse\nthe local Polyak-Lojasiewicz (PL) curvature of the training dynamics. Establishing a lover bound of\nthe local PL-curvature, they show that for weakly-correlated inputs, at least 4 log(n/ε) hidden-layer\nneurons and under some initialization constraints (the second layer weights have larger or equal norm\nthan the weights from the first layer), the loss converges to zero with exponential rate of at least 1/n\nwith probability 1−ε. Considering the orthogonal case in particular, they can establish an upper\nbound, ensuring a rate of convergence between 1/n and 1/√n and show empirically that a rate of\n1/√n is met with high probability. Lastly they show that in the case of group initialization, there\nare abrupt phase transitions between an initial convergence rate of 1/n, intermediate rates, and the\nasymptotic convergence rate 1/√n.", "questions": "1- I am a bit confused with the rates in Theorem 1: in my understanding, the rates slow down, when n increases, and when the norm of data grows fast (role of C);  can the authors elaborate more about these points? \n\n2-In line 64--66, authors mentioned that ``...to understand a simplified version of the optimization dynamics of this neural network, we study the continuous-time limit of gradient descent.'' Could authors please elaborate why and how this setting and the corresponding results can be adapted to discrete time setting which happens in practice? \n\n3-I am confused with the role of p in equation 3? Could authors please elaborate more on that?\n\n\n4. Also, according to results in the literature, local minima exist in shallow ReLU networks. So, what is the main message of the paper? Is it claiming that such suboptimal points do not exist, or that the optimization process escapes them?", "limitations": "No limitation", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The authors address an important topic of convergence dynamics of shallow ReLU networks in more\nrealistic conditions than in previous works. They explain their results in details. Especially giving a sketch of proof for the main results makes it a lot more understandable and intuitive. Further, by giving an example of a setting in which their assumptions are\nsatisfied, or explaining the implications of their results, they well illustrate their work and it’s relevance.", "was_revised": true, "final_justification": "My main concerns are answered and I would keep my rating.", "rebuttal": "**Response**: Thank you for your review and questions, which we address below. Please feel free to follow up if any of our responses do not fully resolve your concerns.\n\n**1. Theorem 1**. The convergence rate decreasing with $n$ is due to the orthogonality constraint. Note that $n$ could not grow larger than $d$, and hence the limit $n \\to \\infty$ (which would break down the result due to the infinitely slow convergence) cannot happen.  Moreover, imagine the case $p=1$, we have for all $i$ that $y = ||w||<w|x_i>$, where the $x_i$ are orthonormal. This implies $||w||^2 = \\sqrt{n}y$, and thus the PL is at most of order $\\frac{1}{\\sqrt{n}}$.\n\n**2. Gradient Descent**. The gradient flow corresponds to the limit of a gradient descent with the step size going to 0. In the small but positive step size limit, any equation of the form $\\frac{d f(t)}{dt} = c(t)$ becomes $\\frac{f(t + s) - f(t)}{s} = c(t) \\sim c(t + s)$ with $s$ the step size. Now, we can carry the same computations and inequalities as before to find a valid discrete equivalent to Theorem 1, up to a constant depending on $s$. Taking $s$ small enough guarantees the convergence, but $s$ might need to depend on $p, n, d$ or the constants $C_{x,y}^{+,-}$.\n\n**3. Gradient Flow Equation**. This is indeed quite confusing (even for the author up until writing the paper), and comes from the normalization of the network. We wanted to find a way to normalize both the network $h$ and the loss $L$ in order to have consistent definition if $p$, $n$ or $d$ would go to infinity. We thus introduce the $\\frac{1}{p}$ before the summation in $h$, which introduces a temporal dilatation: the more neurons, the slower each neuron learns. To have learning in the regime $p\\rightarrow+\\infty$, we thus rescale the gradient descent equation by a factor $p$. Note that this is strictly equivalent to having the normal equation without $p$, a network without the normalization, and weights initialized with norm $\\frac{1}{\\sqrt{p}}$, which is the default equations used in pytorch.\n\n**4. Local Minima**. Local minima exist in this setup, but the paper claims that in average, we will avoid them all. This works in two steps: first, with enough neurons, we put ourselves into a high probability zone of the parameter space which do not trap us into local minima (example: all the $|a_j|$ are positive, hence no negative label can be fitted), and second, the near-orthogonality hypothesis says that we don’t have local minima created from the weights moving around and interacting (see the example in appendix C.1). In particular, the local-PL viewpoint means that although the local-minima exist, they are avoided on the trajectory starting from the high probability zone."}]

Author rebuttal:

Meta-review: This paper identifies a regime of global convergence for gradient flow in one-hidden-layer ReLU networks trained on high-dimensional, finite datasets. The main result establishes an exponential convergence rate of $1/n$ for gradient flows (scaled ODE), under: (Assumption  1) initialization conditions, (Assumption 2) weakly correlated data, and (3) a number of neurons $O(\log n)$, where $n$ is the number of samples. Convergence in this regime follows from the observation that low correlation is typical for sub-Gaussian data in high dimensions $(d = \Omega(n^2))$. The results are further refined to a convergence rate between $1/n$ and $1/\sqrt{n}$ for orthogonal data, with a phase-transition phenomenon in the convergence rate demonstrated along the trajectories. The theoretical predictions are corroborated by experiments that display matching empirical rates.

Reviewers highlighted the paper’s solid analysis within a newly identified regime requiring $O(\log n)$ neurons, along with its technical rigor and clear exposition. Initial concerns regarding the assumptions of the analysis were largely addressed to the reviewers’ satisfaction, with further clarification on the implications, relevance, and applicability of the results. Overall, the paper is recommended for acceptance.
Decision: Accept (poster)