Leveraging the two-timescale regime to demonstrate convergence of neural networks
Authors: Pierre Marion
Raphaël Berthier
Venue: NeurIPS 2023 poster (2023)
Keywords: neural networks
non-convex optimization
gradient flow
convergence proof
two-timescale algorithm
TL;DR: We prove convergence of shallow neural networks when learning the inner layer more slowly than the outer layer.

Abstract: We study the training dynamics of shallow neural networks, in a two-timescale regime in which the stepsizes for the inner layer are much smaller than those for the outer layer. In this regime, we prove convergence of the gradient flow to a global optimum of the non-convex optimization problem in a simple univariate setting. The number of neurons need not be asymptotically large for our result to hold, distinguishing our result from popular recent approaches such as the neural tangent kernel or mean-field regimes. Experimental illustration is provided, showing that the stochastic gradient descent behaves according to our description of the gradient flow and thus converges to a global optimum in the two-timescale regime, but can fail outside of this regime.

Leveraging the two-timescale regime to demonstrate convergence of neural networks
Pierre Marion
Sorbonne Université, CNRS,
Laboratoire de Probabilités, Statistique Modélisation, LPSM, F-75005 Paris, France
pierre www.:r/oooooooboommueeeeeeeeiiia fr
Raphaël Berthier
EPFL, Switzerland raphael.berthierre bertherrpbrrrerrrr...cch
Abstract
We study the training dynamics of shallow neural networks, in a two-timescale regime which the stepsizes for the inner layer are much smaller than those for the outer layer. In this regime, we prove convergence of the gradient flow to global optimum of the non-convex optimization problem in simple univariate setting. The number of neurons need not be asymptotically large for our result to hold, distinguishing our result from popular recent approaches such as the neural tangent kernel or mean-field regimes. Experimental illustration is provided, showing that the stochastic gradient descent behaves according to our description of the gradient flow and thus converges to global optimum in the two-timescale regime, but can fail outside this regime.
Introduction
Artificial neural networks are among the most successful modern machine learning methods, in particular because their non-linear parametrization provides flexible way to implement feature learning (see, e.g., Goodfellow et al., 2016, chapter 15). Following this empirical success, a large body of work has been dedicated understanding their theoretical properties, and in particular analyzing the optimization algorithm used to tune their parameters. It usually consists in minimizing loss function through stochastic gradient descent (SGD) variant (Bottou et al., 2018). However, the non-linearity of the parametrization implies that the loss function is non-convex, breaking the standard convexity assumption that ensures global convergence of gradient descent algorithms.
In this paper, we study the training dynamics shallow neural networks, i.e., the form
f( u) = ao + Σ a,g(;; uy):
where m denotes the number of hidden neurons, a (ap .......... 0m) and u (ui,..., .,, Um) denote respectively the outer and inner layer parameters, and g(x; u) denotes a non-linear function of and u. The novelty of this work lies in the use so-called two-timescale regime (Borkar, 1997) to set stepsizes for the inner layer to be an order of magnitude smaller
train the neural network: than the stepsizes of the outer layer a. This ratio is controlled by parameter e. In the regime < 1, the neural network can be thought of as a fitted linear regression with slowly evolving features
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

g( uy), = I...., m: this reduction enables us to precisely describe the movement of the inner layer parameters Uj.
Our approach proves convergence of the gradient flow to a global optimum of the non-convex landscape with fixed number of neurons. The gradient flow can be seen the simplifying yet insightful limit of the SGD dynamics as the stepsize h vanishes. Proving convergence with fixed number of neurons contrasts with two other popular approaches that require take the limit m - oe: the neural tangent kernel (Jacot et al., 201 8; Allen-Zhu et al., 2019; Du et al., 2019; Zou et al., 2020) and the mean-fiele feeld approach (Chizat and Bach, 2018: Mei et al., 2018; Rotskoff and Vanden-Eijnden 2018; Sirignano and Spiliopoulos, 2020). As consequence, this paper is intended as a step towards understanding feature learning with a moderate number of neurons.
While our approach through the two-timescale regime is general, our description of the solution of the two-timescale dynamics and our convergence results specific to simple example showcasing the approach. More precisely, we consider univariate data x E [0. 1] and non-linearities of the form uz)). where u; is a variable translation parameter, n is fixed dilatation parameter, and a is a sigmoid-like non-linearity. Finally, we restrict ourselves to the approximation of piecewise constant functions.
g(;; uz) (n (n--((x
Organization of this paper. In Section 2, we detail our setting and state our main theorem on the convergence of the gradient flow to a global optimum. Section articulates this paper with related work. Section 4 provides a self-contained introduction to the /wo-timescale limil e - O. We explain how it simplifies the analysis of neural networks, and provides heuristic predictions for the movement of neurons in our setting. Section 5 gives a rigorous derivation of our result. We prove convergence first in the two-timescale limit ε + O, then in the two-timescale regime with æ small but positive. Section 6 presents numerical experiments showing that the SGD dynamics follow closely those of the gradient flow in the no-timescale regime, and therefore exhibit convergence to global optimum. On the contrary, SGD can fail to reach global optimum outside of the wwo-timescale regime.
2 Setting and main result
We present setting in which piecewise constant univariate function f* [0, 1] - R. is learned with gradient flow on a shallow neural network. Our notations are summarized on Figure 1. We begin by introducing our class of functions of interest.
Definition 1. Let > 2, A E (0,1), 0
ft
and M > 1. We denote AF.Av.AfM the class of functions f" [0, 1] - I satisfying the following conditions:
Af
f
*f* is piecewise constant: there exists
0 0= vo < <1 1 Un-1 < Un =1
and fo fo...., fã-1 E R such that
Vz E (v,, u141), (xx = f:"
f6
for all i [1....., m), 10,,0, 2/- - Vi-1 ž Av,
17
17/M2
10g
for all [I...., n1
1), - -fi-l > Af,
Figure I: Notations of the paper. The target f is in blue and the neural network f(; a, u) in orange.
for all E (0. (0...., n 1}, 1f2 < M.
Let us now define our class of neural networks. Consider o R + R an increasing, twice continuously differentiable non-linearity such that (xx) = 0 if & -1/2, (z) = 1 if x > 1/2, and o 1/2 is odd. Then, our class of shallow neural networks is defined by
m
f(x; u) ag + Σ
a, uz),
0,(xx) a
j=1
2

---

where < & 1 measure the sharpness of the non lineerirarit on, Note that that inner layer parameter u, determines the translation of the non-linearity; no parameterized multiplicatiie operation on is performed in this layer. We refer to the parameter sometimes, simply as the "neurons") and to the parameter a as the "weights" of the neurons. We define the quadratic loss as
the "positions" of the neurons (or,
Laa u) 2 2./ (f*()) S u)) dr.
We use gradient flow on to fit the parameters and u: they evolve according to the dynamics du
da vVaa(((()))
dt ()===v)L((())
(1)
where corresponds to the ratio of the stepsizes of the iterations.
Main result. By leveraging the two-timescale regime where & is small, our theorem shows that, with high probability, neural network trained with gradient flow is able to recover arbitrary piecewise constant function to an arbitrary precision. The proof is relegated to the Appendix.
Theorem 1.
Let E, >> and f* piecewise constant function from F A Assume that the neural network has m neurons with
6 Av
log 1
m
(4
(2)
Assume that, initialization, the positions Ui...., Um the neurons are i.i.d. uniformly distributed on [0, 1] and their weights ag .a....aam are equal to zero.
Then there exists Q > O and Q2 > 0 depending E, 8, m, AJ, M such that, if
E Q1
E E< Q2
then, with probability at least the solution the gradient flow (1) is defined at least until T = e(Affz and
S. ((;a)()( ( dr E
C1
8((A))² (m + 1)
C20²
(8(A))² m + .6) for
Further, Q
M2 + min
and Q2 M + 1)17/2
min
some universal constants C1 C2 > 0.
For this result to hold, the inequality (2) requires the number of neurons in the neural network to be large enough. Note that the minimum number of neurons required approximate the n pieces of f" is equal to n. If the length of all the intervals is of the same order of magnitude, then Av ④ /n) and thus the condition m [nn(1 log log 1/8)). In this case, condition (2) only adds logarithmic factor in and 8. Moreover, the lower bound on does not depend on the target precision g. Thus we observe some non-linear feature learning phenomenon: with fixed number of neurons, gradient flow on a neural network can approximate any element from the infiniteddimessional space of piccewise constant functions to an arbitrary precision.
The recovery result of Theorem is provided under two conditions (3). The first one should not surprise the reader: the condition on 17 enables the non-linearity be sharp enough order to approximate well the jumps of the piecewise constant function f*. The novelty of our work lies in the condition on e, that we refer as the rwo-timescale regime. This condition ensures that the stepsizes taken in the positions u are much smaller than the stepsizes taken in the weights a. As consequence, weights a are constantly close to the best linear given the current positions u. This property decouples the dynamics of the two layers of the neural network; this enables a sharp description of the gradient flow trajectories and thus the recovery result shown above. This intuition is detailed in Section 4.

---

3 Related work
Two-timescale regime. Systems with two timescales, or slow-fast systems, have a long history in physics and mathematics, see Berglund and Gentz (2006, Chapter 2) for an introduction. In particular, iterative algorithms with two timescales have been used in stochastic approximation and optimization, see Borkar (1997) or Borkar (2009, Section 6). For instance, they are used in the training of generative adversarial networks, decouple the dynamies of the generator from those of the discriminator (Heusel et al., 2017), in reinforcement learning, to decouple the value function estimation from the temporal difference learning (Szepesvári, 2010), or more generally in bilevel optimization, to decouple the outer problem dynamics from the inner problem dynamics (Hong et al., 2023). However, to the best of our knowledge, the two-timescale regime has not been used to show convergence results for neural networks.
Layer- learning rates. Practitioners are interested in choosing learning rates that depend on the layer index to speed up training or improve performance. Using smaller learning rates for the first layers and higher learning rates for the last layer(s) improves performance for fine-tuning (Howard and Ruder, 2018; Ro and Choi, 2021) I) and a common practice for transfer learning (see, e.g., Li et al., 2022). Another line of work proposes to update layer-wise learning rates depending on the norm of the gradients on each layer (Singh et al., 2015; You et al., 2017; Ko et al., 2022). However, they aim to compensate the differences across gradient norms in order to learn all the parameters at the same speed, while on the contrary we enjoy the theoretical benefits of learning different speeds.
Theory of neural networks. A key novelty of the analysis of this paper is that we show recovery with fixed number of neurons. We now detail the comparison with other analyses.
The neural tangent kernel regime (Jacot et al., 2018; Allen-Zhu et al., 2019; Du et al., 2019; Zou et al., 2020) corresponds to small movements of the parameters of the neural network. In this case, the neural network can be linearized around its initial point, and thus behaves like a linear regression. However, in this regime, the neural network can approximate only finite dimensional space of functions, and thus it is necessary to take m + 0o to be able to approximate the duinite-dimensione space of piecewise constant functions to arbitrary precision.
The mean-field regime (Chizat and Bach, 2018; Mei et al., 2018; Rotskoff and Vanden-Eijnden, 2018; Sirignano and Spiliopoulos, 2020) describes the dynamics of two-layer neural networks in the regime m >> 1 through a partial differential equation on the density of neurons. This regime is able to describe some non-linear feature learning phenomena, but does not explained the observed behavior with a moderate number of neurons. In this paper, we show that in the two-timescale regime, only single neuron aligns with each of the discontinuities of the function I*. However, it should be noted that the neural tangent kernel and mean-field regimes have been applied to show recovery in a wide range of settings, while our work is restricted to the recovery of piecewise constant functions. Extending the application of the two-timescale regime is left for future work.
Our work includes a detailed analysis of the alignment of the positions of the neurons with the discontinuities of the target function f* This is analogous to a line of work (see, e.g.. Saad and Solla (1995); Goldt et al. (2020); Veiga et al. (2022)) interested in the alignment of a "student" neural network with the features of "teacher" neural network that generated the data, for high- nigh-diimesional Gaussian input. In general, the non-linear evolution equations describing this alignment are hard to study theoretically. On the contrary, thanks to the two-timescale regime and to the simple setting of this paper, we are able to give precise description of the movement of the neurons.
Our study bears high-level similarities with the recent work of Safran et al. (2022). In a univariate classification setting, they show that two-layer neural network achieves recovery with a number of neurons analogous to (2): inversely proportional to the length of the smallest constant interval of the target, up to logarithmic terms in the number of constant intervals and in the failure probability. However, the two papers have different settings: Safran et al. (2022) consider classification with ReLU activations while we consider regression with sigmoid- activations. More importantly, the authors do not use the two-timescale regime. Instead, by specific initializaaton scale, they ensure that the neural network has first lazy phase where the positions of the neurons do not move significantly. For the second rich phase, they describe the implicit bias of the limiting point; this approach does not lead to an estimate of the convergence time while the fine description of the two-ting wo-timmsscale limit does.

---

Finally, related technique is the so-called layerwise training, which consists in first training the inner layer with the outer layer fixed, and then doing the reverse. This setup has been used in theoretical works to show convergence of (stochastic) gradient descent in a feature learning regime with moderate number of neurons (Abbe et al., 2023; Damian et al., 2022). The two-timescale regime can be seen as a refinement of this technique since we allow both layers to move simultaneously instead of sequentially, which is closer to practical setups.
non-rigorous introduction to the two-timescale limit
This section introduces the core ideas of our analysis in non-rigorous way. Section 4.1 introduces the limit of the dynamics when и + O, called the two-timescale limit. Section 4.2 applics the two-timescale limit to predict the movement of the neurons.
4.1 Introduction to the two-timescale limit
Let us consider the gradient flow equations (1) and perform the change of variables T = et:
da 1 dr VaL(a,
du dr = u).
(4)
In the two-timescale regime ε < 1, the rate of the gradient flow in the weights a is much larger than then the rate in the positions u. Note that L is marginally convex in and thus, for fixed u, the gradient flow in a must converge to a global minimizer of + L(a, u). More precisely, assume that {on,(- ui),.... .,(.
um)} forms independent set of functions in [[, 1]). Then the global minimizer of a + L(a, u) is unique; we denote it as a" (u). In the limit e + O, we expect that evolves sufficiently quickly with respect
that converges instantaneously to a" (u). In other words, the gradient flow system (4) reduces to its so-called awo-timescale limit when & -> 0:
du dr L,, (u))
a' (u),
(5)
The two- tro-timescale limit considerably simplifies the study of the gradient flow system because it substitutes the weights a, determined to equal to a" (u). However, showing that (4) reduces to (5) requires some mathematical care, including checking that a"(u) is well-defined.
Remark (abuse notation). Equation (5) contains an ambiguous notation: does V, (w), u) denote the gradient in of the map L + L(a"(u, u) or the gradient (V..L) (a,u) laken at a a" (u)? In fact, by definition of a² (u), both quantities coincide:
(V.L")(u) (dee da" (w)) (VaL)aa u) + (w) (V du
(
da' denotes the differential of a" in and we use that, by definition of a (u), (V. (V. (n), = This a special case of the envelope theorem (Border, 2015, Sec. 5. 5.10).
where du
The discussion in this section is not specific to the setting of Section 2. Using the two-timoesn timescale limit to decouple the dynamies of the outer layer a and the inner layer u is general tool that may be used in the study of any two-layer neural network. We chose the specific setting of this paper so that the two-timescale limit (5) can be easily studied, thereby showcasing the approach. The next section devoted to sketch of this study.
4.2 Sketch of the dynamics of the two-timescale limit
In this section, in order to simplify the exposition of the behavior of the two-timescale limit (5), we consider the limiting case 17 + O. Note that this is coherent with Theorem I that requires 7) to be small. This limit is neural network with a non lineariyyy equal to the Heaviside function
(z(x)= = 0 if x < 0,
oo(x) = 1/2 if r =0
σu(x) =1 if x > 0.
Note that de would a poor choice of nin-aiiyy in practice: as its derivative everywhere, the positions would not move. However, it is a relevant tool to get an intuition about the dynamics of our system for a small 7). Moreover, as we will see in Section 6, the dynamics sketched here match closely those of the SGD (with 17 > 0).
almost
5

---

R
15
Figure 2: Sketch of the dynamies of the neurons in the two-timescale limit with Heaviside non- linearity. Only the neurons next to a discontinuity of the target move.
The set (l, -u)...., .o.. um)) generates the space of functions that are piecewise constant
with respect to the subdivision {wi..... Um ). Furthermore, if uı,..., Mm are distinct and in (0, 1), then this set is an independent set of functions in r, 1.2((0, 1)). Thus a"(w) well defined and represents the coefficients of the best piecewise constant approximation of f with subdivision {u1,--.. Um
This quantity is straightforward to describe under the mild additional assumption that there are at least two neurons uj in each interval (f;-1, 04) between two points of discontinuity of f*. For each 1 < i & n, let ut denote the largest position of neurons below e; and už denote the smallest position above U, (with convention up = 0 and u 1). By assumption, = up < uf < u <
L < un < u are distinct. A simple computation then shows the following identities:
R
.
for all i E m. for all E (u uB), [(xaa (u), u) u
1 1-1
U/
u
and for all i (I...., 1}, for all (n w f(x; a" (u), u) fi-1
where we recall that fü denotes the value of f on the interval (1,, 1141). Figure 2 illustrates the situation. Moreover, the loss L(a" Lua"(u), u). which is half of the square error of this optimal
approximation, can be written
(or (u. u - uf
vi) (f+ -f-
L(a" L(a 2
(6)
The dynamics of the two-timoee two-timescale limit (5) corresponds to the local optimization of the subdivision of
in order to minimize the loss (6). A remarkable property of this loss is that it decomposes local losses around the jump points v; for {I...., n - 1}. Each element of the sum involves only the two neurons located u. and uR. As consequence, the dynamics of the two-timescale limit (5) decompose as n independent systems of two neurons uf and wh: for
all i E {l,..., 1}.
duf dL
+ (u vz)2
(a (u), u)
(fr f/ (n. u
dr dut
duR dL
1 (v. 4/
(a (u), = 2 (u. 1 (s: - 2
dr
duR
R
All neurons other than u/. uR 2h RR do not play role in the expression (6), thus they do not move in the two-timescale limit (5). The position ut moves right and wft moves left, until one of them hits the point U;. This shows that the positions of the neurons eventually align with the jumps of the function fr, and thus that the function f* is recovered.

---

5
Convergence of the gradient flow
In this section, we give precise mathematical statements leading the convergence of the gradient flow to a global optimum, first in the two-timescale limit e + 0, then in the two-timescale regime with small but positive. All proofs are relegated to the Appendix.
5.1 In the two-timescale limit
This section analyses ses rigorously the two-timescale limit (5), which we recall for convenience:
du - v,, (u).
a" (u) arg min ((a, u)
(8)
dr
We start by giving a rigorous meaning to these equations. First, for L to be differentiable in we require the parameter 17 of the non- non-linearity to be positive. Second, for a" (u) to be well-defined, we need u + [(, u) to have unique minimum. Obviously, if the ", are not distinct, then the features {ar(( "1) ... .a((- um)] are not independent and thus the minimum can not be unique. We restrict the state space of our dynamics to circumvent this issue. For u E [0, 1)m, we denote
min Auu) ofj
[1j ukl,
with the convention that uo = -n/2 and Um++1 = 1 + n/2. Further, we define U = {u E 1|m (u)
2n}. The proposition below shows that 2 gives good candidate for set supporting solutions of (8).
Proposition 1. For u E U1 the Hessian (u) of the quadratic function I(-,u) is positive definite and its smallest eigenvalue is greater than Alwl/s. In particular, L(., u) has a unique minimum a" (u).
The bound on the Hessian is useful in the following, in particular in the proof of the following result. Proposition 2. Let G(u) (aL (u), u) for E U. Then G U + R is Lipsehitz-continuuuu
Then, the Picard-Lindeles theorem (see, e.g., Luk, 2017 for a self-contained presentation and Arnold, 1992 for textbook) guarantees, for any initialization u(0) E U, the existence and unicity of maximal solution of (8) taking values in 24. This solution is defined on a maximal interval [o, Tmax) where it could be that Tmax < oo if u hits the boundary of U. However, the results below show that the target function f is recovered before this happens (with high probability over the initialization), and thus that this notion of solution is sufficient for our purposes. To this aim, we first define some sufficient conditions that the initialization should satify.
Definition 2. Let D be a positive real. We say that vector of positions [0, 10m is D-good
(a) for all E (....., n 1}, there are least 6 positions uj in each interval [ui, v441].
(b) (uu) > D, and
(c) for all i E {1...., 1}, denoting up the position closest to the left of vs and wn the position closest to the right, we have |u + u. 2u,] > D.
Condition (a) is related to the fact that the derivation in Section 4.2 is valid only if there at least two neurons per piece. This requirement that the neurons be distributed on every piece of the target seems to be necessary for result to hold, and provide in Appendix D.1 counter-example where recovery fails otherwise. Condition (b) indicates that the neurons have to be sufficiently spaced initialization, which is not surprising since we have guarantee that ((u(r))
21/, that is, w(T) E U, for all t until the recovery of / happens. Finally, condition (c) also helps to control the distance between neurons: although of and uft move towards each other, as shown by (7), their distance can be controlled throughout the dynamics as function of ju.- + ut 20g/.
We can now state the Proposition showing the recovery in finite time. The proof resembles the sketch of Section 4.2 with additional technical details since we need to control the distance between neurons, and the fact that 1) > makes the dynamics more delicate to describe.
Proposition 3. Let f E Fu,Av.Af.M. Assume that the initialization u(0) is D-good with D 213/2 (m + 1 least on [0, for T = 6/(A)), and the end of this time interval, there is a neuron at distance less than 1) from each discontinuity of f
Then the maximal solution of (8) taking values in ld is defined at
7

---

This Proposition is the main building block to show recovery in the next Theorem, along with some high-pre peob-bbbbbbiltyy bounds ensure that an i.id. uniform initialization is D-good.
Theorem 2. Let ç, ò O, and f' piecewise constant function from An.Av,AA.M. Assume that the neural network has m neurons with
6 (4 log + log 1 ()
m
Av
Assume that, initialization, the positions U1...., Um the neurons are i.i.d. uniformly distributed on [0, 1]. Then there exists Q depending on E, ò, m, ff, M such that, if
n n Q,
then, with probability at least 8, the maximal solution to the two-timescale limit (8) is defined at least until T (Af)z and
Jr (5())) (();)) (u(T)) (()
C
5) for some universal constant C 0. (Im + 175
(a(f))
Furthermore, we have Q min
M
5.2 From the two-timescale limit the two-timescale regime
We now briefly explain how the proof for the wwotiimescale limit can be adapted for the gradient flow problem in the two-timescale regime (1), that is with a small but non- son--nnishing- First note that the existence and uniqueness of the maximal solution to the dynamics (1) follow from the local Lipschitz-continuity of V. and L with respect both their variables.
The heuristics of Section 4.1 indicate that, for small enough, at any time f, the weights a(t) are close to a" (u())), the global minimizer of L(-, u())). The next Proposition formalizes this intuition. Proposition 4. Assume that a(0) = 0 and that, for all E [0, there at least 2 positions uy us(s) in each interval [vi, v++1] and ((u(s) > D/2 for some D 2 32n. Finally, assume that & 2-16 D M (m + 1) -/22, Then
Pot 2 3 (m + 1)3 8.
||a(1] - a"((())) &
Texp
D2
The crucial condition in the Proposition is A(u(s)) > D/2; it is useful to control the conditioning of the quadratic form L(,, u(s)). The Proposition shows that (la(t) - a (u(t)) is upper bounded by the sum of two terms; the first term is consequence to the initial gap between a0)) and a" (u(()) and decays exponentially quickly. The second term is negligible in the regime e < 1.
Armed with this Proposition, we show that the two-timescale regime has the same behavior as the two-timescale limit and thereby prove Theorem 1.
Numerical experiments and discussion
Numerical illustration in the setting of Section 2. We first compare the dynamics of the gradient
flow the two-timescale limit presented in Section 4.2 with the dynamics of SGD. To simulate the SGD dynamics, we assume that have access noisy observations of the value of f Fn.Av.Af.M let (xp. Yp)p21 be i.i.d. random variables such that X, is uniformly distributed on [o, 1), and Y, (*(X,) Np where N, is additive noise. The (one-pass) SGD updates then given by
ap+1 0p hV hV ((px1x Yp+1i ap; Up)
Up+1 = up eh e,V,, (,,((((p1, Ypt1i Up),
with ((X, u) JY - f(X: u)) The experimental settings, as well as additional results, given in the Appendix.
Remarkably, the dynamies SGD in the two-timescale regime with n small match closely the gradient flow in the two-timescale limit with 7 0, as illustrated in Figure 3. This validates the use

---

of the gradient flow to understand the training dynamics with SGD. Both dynamics are close until the wwo-tieescale limit achieves perfect recovery of the target function, which point the SGD stabilizes to small non-zero error. The fact that SGD does not achieve perfect recovery is not surprising, since SGD performed with 7) > and f is not in the span of {1, 7, w1),.... ...., on Mi...., tm and for 0. On the contrary, we simulated the dynamics of gradient flow for 0, as presented in Section 4.2, enabling perfect recovery in that case.
um for any
10
SGD Two-timesctle limit
Target
SGD
TT limit
10
3
10
10-2
1
0.0
0.5
1.0
1.5
P
x10*
0.0
0.2
0.4
016
0.8
1.0
(a) Loss L as a function of the number of steps
(b) Plot of the functions after 2.7 - 10 steps
Figure 3: Comparison between the SGD (9) with r7 = 4 10 -3 in the two-timescale regime (s
2 1) and the gradient flow in the two-timescale limit (5) with 1 O. In the left-hand plot, to align the SGD and the two-timescale limit, we take T = chp. In the right-hand plot, the target function is in blue, the gradient flow in the two-timescale limit is in green, and the SGD is in orange.
Next, we compare the SGD dynamics in the twotiimeeelle regime (e < and outside of this regime (e < 1). In Figure 4, we see that the network trained by SGD (in orange) in the two-timescale regime & 2- 10-5, achieves near-perfect recovery. we change 1, while keeping all other parameters equal, the algorithm fails to recover the target function (Figure 5). This shows that, in our setting with moderate number of neurons m, recovery can fail away from the two-timescale regime. could seem that we are favouring the two-timescale regime by running it for more steps. In fact, it is not the case since both regimes are run until convergence. We refer to Appendix C for details.
Note that the dynamics of the neurons in Figures 4 and 5 are different. In the two-timescall regime, only the neurons closest a discontinuity move significantly, while the others do not. These dynamies correspond to the sketch of Section 4. Interestingly, it means that in this regime, the neural network learns sparse representation of the target function, meaning that only n out of the m neurons are active after training. On the contrary, when 1, all neurons move to align with discontinuities of the target function, thus the learned representation is not sparse. Furthermore, since the number of neurons is moderate, one of the discontinuities is left without any neuron.
Turge
SGD
0.0
0.2
0.5
0.5
1.0
0.2 0.6
(a) initialization p
(b) After 5.4 10th steps
(c) After 10 steps
Figure 4: Simulation the two-timescale regime
2- 10-5 The target function is in blue and the SGD (9) is in orange with 1) = 4 10 10 / = 5 The positions uI...., um of the neurons are indicated with vertical dotted lines. In a first short phase, only the weights aj..... am of the neurons evolve to match as best as possible the target function (second plot). Then, in longer phase, the neuron closest to each target discontinuity moves towards (third plot). Recovery is achieved.

---

Tangst
SCD
0.2
At initialization p
After 10 steps
(c) After p 10 steps
Figure 5: Simulation outside of the two-timescale regime (s = 1). The target function is in blue and the SGD (9) is in orange with 7) 4 10 -0 h 10 The positions W1s...: Um of the neurons are indicated with vertical dotted lines. The dynamics create zone with no neuron, hindering recovery.
Discussion. The two-timescale regime decouples the dynamics of the two layers of the neural network. As consequence, it is useful theoretical tool simplify the evolution equations. In this paper showcasing the approach, the two-timescale regime enables to show the alignment of the neurons with the discontinuities of the target function in the piecewise constant 1D case, and thus to prove recovery. A full general understanding of the impact of the two-timescale regime is open question, which is left for future work. We provide the following some practical evidence of the applicability of this regime to other settings (higher-dimension) sample size). Additional technical difficulties significantly complicate the proof in these settings, but we believe that there is no fundamental reason that mathematical approach should not apply.
problems, ReL.U networks, finite
Higher dimensions. We consider piecewise constant functions on Rd with pieces that are cuboids aligned with the axes of the space (see Figure 6). Neural networks are of the form f(z; o, u) = ao Σド= Ei (f ujk), where the j-th neuron has d-dimensional position (ug+)ıgked and weight (a,k) (gkk)) The results are similar to the ID case: convergence to global minimum is obtained in the two-timescale regime but not in the standard regime.
10
0.7
Target
Target
0.5
Nemrons
Neurons
0.3
0.3
0.0
0.0
(a) After training standard regime
(b) After training in two-timescale regime
Figure 6: 2D experiment with piecewise-constant target (each shade of blue depicts constant piece). The orange lines show the positions of the neurons after training by SGD. In the standard regime, a discontinuity of the target at x 0.3 is not covered by neuron. In the two-timescale regime, all the target discontinuities are covered. See Appendix C for more results with 2, 10.
ReLU networks. Appendix C reports the case of using ReLU activations to approximate piecewise- affine targets. A similar conclusion holds.
Finite sample size. We believe that it should be possible to generalize our results to finite sample sizes (say, for single-pass SGD), following a perturbation analysis similar to the one Section 5.2, with additional terms due to random sampling. Numerically, Figure shows that SGD indeed closely follows the behavior of the two-timescale limit. Some ideas about the proof are provided in Appendix D.2.
10

---

Acknowledgments and Disclosure of Funding
The authors thank Emmanuel Abbé for many discussions and suggestions on this project, and Quentin Berthet for pointing them towards the envelope theorem. The authors are grateful towards the Simons Institute for the Theory of Computing where this work was initiated. P.M. supported by a grant from Région fe-de-Francc, by Google PhD Fellowship and by Mines Paris PSL.
References
Emmanuel Abbe, Enric Boix Adserà, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theary, volume 195 of Proceedings of Machine Learning Research, pages 2552-2623, PMLR, 2023.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 242-255 2019.
Vladimir Amold. Ordinary Differential Equations. Springer Berlin Heidelberg, 1992.
Nils Berglund and Barbara Gentz. Noise-induced phenomena in slow-fast dynamical systems: sample-paths approach. Springer Science & Business Media, 2006.
Kim Border. Miscellaneous notes on optimizatiion theory and related topics, 2015. URL: https: // healy econ. ohio- state. wdw/kc///a///e///////e http///dddddyy/////aiiaaaaaaaaaa ottpo///aaaaaa/////////////////a
(version: 2023-02-08).
Vivek Borkar. Stochastic approximation with two time scales. Systems & Control Letters, 29(5):
291-294, 1997.
Vivek Borkar. Stochastic approximation: dynamical systems viewpoint, volume 48. Springer, 2009.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311, 2018.
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.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 Proceedings of Machine Learning Research, pages 5413-5452. PMLR. 2022.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1675-1685, 2019.
Sebastian Goldt, Madhu Advani, Andrew Saxe, Florent Krzakala, and Lenka Zdeborová. Dynamies of stochastic gradient descent for two-layer neural networks in the teacher-student setup. Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124010 2020.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning. MIT Press, 2016.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by two time-scale update rule converge local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Mingyi Hong, Hoi-To To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33( 33(1):147-180 2023.
Jeremy Howard and Sebastian Ruder. Universal language model fine-tuning for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 328-339 2018

---

Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances Neural Information Processing Systems, 31, 2018.
Yunyong Ko, Dongwon Lee, and Sang-War Wook Kim. Not all layers are equal: A layer-wise adaptive approach toward large-scale DNN training. In Proceedings of the ACM Web Conference 2022, page 1851-1859, 2022.
Fei-Fei Li, Jiajun Wu, and Ruohan Gao. Deep learning for computer vision course, 2022. URL: https://ca231n, wtt.hhu....otttaff-eeeeerreeeeee
(version: 2023-02-02).
Jonathan Luk. Notes on existence and uniqueness theorems for ODEs, 2017. URL: http:
stanford. edu/" wwtt://lu///ateeaaaeeeeee
170408. pdf (version: 2023-01-19).
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, 15563)) 2018.
Youngmin Ro and Jin Young Choi. AutoLR: Layer- Laser-wise pruning and auto-tuning of learning rates in fine-tuning of deep networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35 (0:2486-24994 2021.
Grant Rotskoff and Eric Vanden-Eijnden. Trainability and accuracy of neural networks: An interacting particle system approach. arXiv preprint urXiv:/805.009 000050 2018.
David Saad and Sara Solla. On-line learning in soft committee machines. Phys. Rev. E, 52:4225-42443 Oct 1995.
Itay Safran, Gal Vardi, and Jason D Lee. On the effective number of linear regions in shallow univariate relu networks: Convergence guarantees and implicit bias. Advances in Neural Information Processing Systems, 35, 2022.
Bharat Singh, Soham De, Yangmuzi Zhang, Thomas Goldstein, and Gavin Taylor. Layer-specific adaptive learning rates for deep networks. In 2015 IEEE 14th International Conference on Machine Learning and Applications (ICMLA), pages 364-368, 2015.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: a central limit theorem. Stochastic Processes and their Applications, 130(3):1820-18 2020.
Csaba Szepesvári. Algorithms for reinforcement learning. Springer, 2010.
Rodrigo Veiga, Ludovic Stephan, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Phase
diagram of stochastic gradient descent in high-dimensional two-layer neural networks. Advances in Neural Information Processing Systems, 35, 2022.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling SGD batch size to 32k for imagenet training. arXiv preprint arXiv: 1708.007000000 033888 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes parameterized deep ReLU networks. Machine Learning, 109(3):467-492, 2020.
12

---

Appendix
Organization of the Appendix In Section we introduce additional notations that will be used throughout the Appendix, then proceed to prove useful technical lemmas. We proceed in Section B to prove the results presented in the main text. Section contains details about our experimental settings as well as some additional simulations. Section D gives a couple of additional insights about our results.
A Additional notations and technical lemmas
For a vector a, we denote ||a]] its normm, ||a]|ı its el -norm and ||a||s its -orm. For matrices H, ||||| denotes the operator norm associated to the e norm and || denotes the Frobenius norm. For real-valued functions f. |I// loo denotes the supremum norm.
-1/2 and Um++1 = n/2. Note that o, uo) = 1 for all E [0, 1], meaning that o- uo) corresponds to the bias term. This notation allows to treat the bias term in a unified fashion with respect the other terms of f(x; a, u). Since u, E (0, 1) for i {I...., m). we assume in the following w.l.o.g. that the (u,)osigm++ are ordered in increasing order. Note that prove in the following that the (u))ıgimm do not cross during the dynamics, so they remain ordered throughout the dynamics.
In all of the Appendix, we denote
The proofs involve comparisons of some quantities when 17 > 0 and when 0. To avoid confusion, we make explicit the dependency of I. on rj 2 0, i.e., we let T.y (a, u) place of L,a, u) of the main paper, and similarly, when the arg min is well-defined and unique,
0r (u) = arg min [a,(a, u). aERm+1
in place of a" (u). Similarly, we now make explicit the dependence of f on 7) 3> 0, i.e., we denote
- ag + Σ a, - -2) = = uz).
1=0
The Hessian the quadratic function (.( 1) is denoted (n p(++1)x(m+)) (in place of H (u)), and satisties that, for E (t,...., m,].
Hn,)(u) = / on ( po(x-uu)o,,e - -un--uyll -u,) )xx
Also let, for > and e Rm, (u) E Rm+l such that, for j E (m.....m..
(n) ['' (()),,(x-uu uz)
Finally, we let Mr in place of U/ in the paper.
With these notations, we have, for > 0 and a, R.
abn (a, Oug
/' 05((za (Jy(z;a,u) (x))
d
Ouj
= - / oz(2x -u)-
Σ
000 ux) - ff (x)
(10)
and
I.n (a, u)
001(1;a, -x)
daj
da,
S' 0n(x uz) (2) axo,(x uc) - (xx) dx
(n) T (nn(
(11)
We now move on to series to lemmas that will be helpful in the proofs of Appendix B.
13

---

Lemma 1. For 1j > 0 and u E RT, we have
[bb(()) bo(u)ll & Miym+1 and [|b( & Mvm+1.
Proof. For any E {0,...,.0 m.
(u) - bo.)(u)] =If (())(an( - uz) oo(x - uz)) 1
< lllf / 10n(0 uz) -ou( uy)ldr
< M1)
where in the last step we use that || & M and that (2(2)) = 0 for & -n/2, (n(()) [0, 1] for
-n/2 < x < n/22 and (x) for n/22.
Similarly,
a (w)(w)]= 11. (z)0,(( ( & lo & M.
Lemma 2. For 2 0 and u E Un. (u) = Ho(u) + Dry where Da is diagonal matrix whose elements are independent of and bounded absolute value by n/2.
Proof. Let i,j E [0,...,m], and denote = max(u;, Uz 0). Then
Ho. = 1'' oolx -u)oolo - uz) = cc i O, max(u; uz) -1/2, and (n.ij(u) Ho.,s Ifi if 0. Hn)s(u)= = //'² o,(x cc)
rtn122
= 1 - c 17
+
0g - 2)
2
Je-n/2
1/2 0².
= Ho,ig (1)
+ 1
2
-12
Note that the last integral is non-negative and less than 1, hence (u) Ho,ss(u) & n/2. Finally, if à since lu, Utj > 77.
(u) (' 0,1(s
uz)dr ((d o,(s max(mi uz))dx.
u:)o,(0 a,(x--u)o,,(e
Furthermore, 0 < max(u;, u²)= <1--- thus
H (n)) = (/'' 0x c)da 1 1 c-nl2
ptn//2
0n(x c)dx = C,
where the last equality comes from the oddness of a 1/2.
Lemma 3. For 1) > O, let at; : u E Un + (u, Then at differentiable and any u E Un.
0ag (1)
22(m + (1)ll +M)
Iu
(
Proof. By Proposition 1 (whose proof does not rely on this lemma), for u E Ug, Top('s u) has unique minimizer ar,ww, which equal (u)- by (11). Furthermore, Hy and b, are differentiable with respect to u, hence a; is also differentiable with respect to u, and we have
(ut = (1) OH, (u)a H,) Ouk
Bb (u)
Dup
Oup
14

---

positions of the neurons, evaluated for a (u), J. that is the best piecewise constant approximation of f" with subdivision {ui...., Mm Note that the formulae the same as in Section 4.2, but the Denote wx(u)= = eHn (u)a, and (u) the (m + 1) x (m + 1) matrix formed by stacking column-wise the vectors (wxl uu)oekmmm Then
Oug
(u) ( - (W)) +
Dbn du
(u).
Iu
We now estimate the Frobenius norm of the matrix (u). By Lemma 2. for u E Un Hn(u) Ho(u) + Dg- Take i.j E {0....,,). m), then
(u) = Ho,sz + Pm. = [ cn(o (0)oo (opola--u)ddr uz)de Dqj3 = max(u;, Ujj 0) D Da.i.
8Hn. = 0 if i + k. Further, if and j + k
Hence
dus
HHn (u)
(1 max(u;, uz)) &
Ouk
Ou:
Of course, the bound | (u) < 1 also holds when j = k and + j. Finally, similar bound Dux
shows that SHn.i
(2) <
when = = k.
As consequence, for k i E {o,....,17 m).
HHndd
[
if k, if = k.
[w)x E -
(w) la [()ر &
Oue
aa ( (w)) (w)
1=0
Thus
[W]lll
m m Σ
wk ww,x(w))2)
1/2
m
Wkk (u))
1/2
k=
(21let (w)l))) 1/2
2
a
With reasoning similar to the above, note that 0b,, (u) is diagonal matrix with diagonal entries in [-M, M). Finally, putting these elements together, using Proposition and that [W(lll < [W(u]]lF. obtain
dai((u) Iu
< (|W))
(b, Iu
<
8 A
(2Vm+ (1),( + +M).
The following lemma gives exact formulae for the derivative of the loss L, with respect to the
derivation is slightly more intricate since we consider here the loss I, and not Lo-
Lemma 4, Take > and u E Un such that there are at least two neurons on each piece [vs, 1441l of fr. Then, if uj does not flank discontinuity of f*,
OL, Ou,
(az(u), u) = 0.
Furthermore, for discontinuity va. denote u. is the closest neuron to its left and ui the closest
neuron its right. If v; up! and u. 82 3 2'
? then
a.,
(u. )2
(az(u), u)
(5r
ouf
[uR wt
0Lg (az(u), = 2 (ul w
1 (v; )
(Jr 12-1)
OuR
15

---

Proof. In this proof, let us denote for simplicity (u( At the condition that there is at least two neurons on each piece of fr, Section 4.2 gives the optimal approximation fo(æ; a, u) of f that is piecewise constant with respect to the subdivision {ui,... ..m J. As consequence, we easily get the value of a. Namely, if uy does not flank a discontinuity of f", the value of fo(æ; a, u) is locally constant around uj. thus aj = 0. Plugging into (10), we obtain
aLn
(a, u) = 0. Ouj
Further, for a discontinuity vi, denote respectively a and a the coefficients associated to uf and -u
uf. At ut, the value of fo(æ; a, u) jumps from fi-1 wp- Ji -u!
S thus
U; u
Vi
u U2 (ft f;-1). !i
Px
fi
u 1
R
R
1
L
"
Similarly, have
R
Uj
(5r f7-1).
R
u
We now compute, using (10),
θh, du:
(a, at _ o0(l5 o (fr(t,a)) (x))
/ -a 14 de - (z))
Using that A(u) > 2n and that there are at least two neurons on each piece of f³, we have
that un 1
2m. Since, in addition, by assumption, 8i uf > 7. get that for
uut 2.2 ut 311 (x) fi Moreover, using again Auu) > 2n that oy is equal on on (-o0, -n/2] and (n/2, oo), we have for x E [ut n ut + }].
(,; = Σ an ux) = So (ut T
2i 2,,, u) + aton(x --t) fi at ut).
Thus we obtain
aLy Oul
///+1/2
(a, u) = -a!
o,(x (r -, o - u/'aa'o,,z
u//-n/2 n/2
(a!)2
o, ? ))
on (on(())
2
(a
2
(u, R 02)
(fr - ff
(u. u
The computation of aLg Sut (a, u) is similar.
Lemma 5. Consider 7) 2 0 and E My such that there are at least two neurons each piece [v,, R441l of f Then, for all x E [0, 1). (x; (2; (n()), w) & M.
Proof. In the case where 7) = 0, the result easily follows from the expressions for fo(a; (u), u) provided in Section 4.2. We now assume 1) 0.
16

---

Denote Ag(u) = E)=o Cuz(u) (with the convention (") = 0). Recall the convention uo
-n/2. We compute
Σ
to (1) u))
k=
(Af(u) -Ap-1(u) on ux)
Σ Az(u) (o,(2 ux) -o,( ux+1)) + A (u)o, um)
Note that Ag(u) = -im fo(:; af (u), u), and thus, from the case 7 = O, we have |AZ(u) M.
Moreover, on is increasing and the up are in increasing order. We thus get
m
(f((r & M
Σ k=
(an - un) - -,,( uk+1)) + o,, - um)
=M un) & M.
Lemma 6. Consider n 0 and E Un such that there are least two neurons each piece [vi, vita] of fr Then, for j E {o....,m. m).
[ < 2M
and, for any a E mRm+11
aLn Oug
aLn Ou,
(a, u)
(aj(u), u) & (v m ( 1)lla aj(u)] Vm + Illa az(2)]12
Proof. The first statement of the Lemma comes from the explicit formulac for ag (u) given in the proof Lemma 4, namely each d is either zero or less magnitude than the gap between two pieces of f that is less than 2M.
By (10), we have
0L, Oug
a (ar(u).u) un
(a, u)
Ou,
a ('' o - -,) f((x)) dr
-as(()) I' - (1)(; (x) dr
< a, (لm( / of(x - uz) ( (x) dr
|ayl / (z)
- u) dr.
We bound the two terms separately. For the first term, we use L.mma
[ d' ( -(o) / o,(x - u,) (16((2 an(u), u) (s*())))
< 2M S' of uyyddr & 2M
We now continue with the second term.
1f a, u) fn az (w), u)l =
Σ
(az (u)(u)) -wa) < 1a-aa(1))l2
km
17

---

and thus
L. (((=-1))1f(2200222 - fy (u(), wr ||a -- (ل(0il / og(2 - u, )r
||a a
Returning to our initial upper bound, we obtain, using the first statement of the Lemma,
Th (aū(u), w) ÖT.n (a, u) Ou,
< 2M a di(") (1a5, (w) + - (w)))) aل(1))
Öuj
< 2M ال(ا0هl + (2M + ||a - -b((w)l) I||a - aل(u)l ab(a))l + v 1 -
+ 1)(la 2M
Lemma 7. For 1j e 0 and u E Un
16M / In A(u)
[a)(u)) a-(")ll E
Proof. By (11),
H,(u)a,(u) = bu)
and by (11) and by Lemma 2,
H,(())a(()= Ho(w)a((w) (u) (D bu(u) + D,)ā(u).
According to Proposition I (whose proof does not rely on this lemma), (u) is invertible with (u) -I < (/)(u). We thus have
(u) az(w) ( (1, ()(())((())
(uu (u) bo(u) - (t)l
Auu) (Ilb, - bb((a)) + |D, (u)ll
A(u) (11b,,()) - bo(w))l " 2 (1)l)
The result then unfolds from Lemmas and 6.
Lemma 8. Let n O, u E R and a, a' gm+1 Then
IV, u|ll < Vm I||a|| 2 + M [|]]|
[V,L, u)ll < Vm- - 1[IlallVm + 1 1 M).
As a consequence of the second inequality, by the fundamental theorem of calculus for line integrals, |nn(,, u) L,, u)l vm + (max([|a]), [aal)))lll+++++ M) Ila a'll
Proof. Recall that, for all j fl,...,m, m). and for all a, u E R
aI. (a, u. = aaj /'' of - (,) m Ouj
ato,( - -us) - f f()x( dx, dr,
k=
aon (a, u) = ('' onlax - uz)
m
aR (x ux) - (r()) dx.
Daz
From the first equality, have
aL
(a, w) < layl 1''' 10 (e((=-ws)] Σ 1 ux) + 1s (x:()()) de
Ou,
|asI[laa|l + M) L/'' 1 1 uz)ldr
<lag1(laall + M).
18

---

As consequence, Similarly, from the second equality, we have
VV, u)ll ||||[[|a||| + +M) & Vm+l||a| M M||a
QL (a. u) Daz
< ||a|1 + M.
As consequence,
(a w)ll & /m + I([aa|| M) vm + T(Iaa] /m + M).
Lemma 9, Consider ij 2 0 and u E Un such that there is neuron at distance less than vy from each discontinuity of I and 3n Av. Then
[ a, (aa))))((())) (x) & 6m
Proof. By definition of (u,(u,
L (1 f"))
L (1 (
min aERm=1
Thus is enough exhibit some for which the latter integral is smaller than 6M2 conclude.
We construct such an a as follows: set ag = (0), and for each discontinuity v, set the coefficient of neuron at distance less than 7) to the value ft f and set all other neurons to zero. Note that the active neurons are distinct since 31 < Av.
Then the neural network is equal to the target function everywhere except on an interval of size 3n/2 around each discontinuity, where they disagree (in infinite norm) by at most 2M.
Lemma 10. Let be positive integer and Up....: Un be i.i.d. uniform random variables in [o, 1]. Assume that
m Au (1 4o log + log }
Then, with probability at least 8, the vector u is D-good with 6(m++122-
Proof. We define the following events:
(a) A is the event "there are at least positions u, in each interval [u,, ve41l for i E fO....,
1)"
(b) the event "A(u)= D"
(c) for all f1...., 1}. E, is the event "there least neuron the left and on the right of vx" and C₁ is the event F2 holds and |u + u. 2n >> D
Note that by Definition 2, u is D-good if and only if the event A n B n (N, Ci) this holds with high probability, we bound the probability of the complement
holds. To show that
(c:i)) AUB B (Uc:) = A'B (U(C)nA)
An B
CPUB (U(C)E))
(as A C E.).
Thus
P((u is not D-good) < P(A") + IPB") + Σ P(C nE).
Below, we bound separately the three terms of the right hand side.
19

---

(a) Denote m' 1m/6]. For any iE fo..... - 1), the set A, = {j E fi....,m' uy e (uy, 13+1]}} is empty with probability (1 (U,+1 2z)) x (1 Au)mi Thus by the union bound, the probability that at least one of A1...... An is empty is upper bounded by nt(1 - Ar)m'.
We now check that n21 - Au)m & 6/18. Indeed,
772
1 + log n + log
18 log n2 + log 5
log n + log 1
m'
6
Av
Av
log(L Av)
3.3 3 > log(18), and log(1 - Av) < - Au < O. This gives the desired where Au < incquality.
In other words, the probability that at least one of the intervals [t; 2441] contains none of the u1..... Unnn' is bounded by 8/18. As consequence, by the union bound, the probability that at least one of the intervals (ug, 1/+1] contains strictly less than 6 of the t/1..... Um is bounded by 8/3, i.e., P(A") < 8/3.
(b) Recall that by convention, uo y and um+11 1++ 4. For all {0,.............. ................................ m 1}, denote 4 = (u, - D, u4 D). Denote Fj the event "uy E 1; for some i E {O..... m + 1). i + j Note that 8 ド
Fix j 1...., m. By conditioning i, for all i E {0..... ( 1}. i + P(F)) < 2mm + D) By the union bound,
that
PPBB) & 2m + 1)D < 6
(c) Take E (1,.... n - 1}. For convenience, we define the random variable uf (resp. w on the full probability space by setting u.- 0 (resp. uf = 1) when there is no neuron on the left (resp. the right) of v, We compute the joint cumulative distribution function of (u) R)
(with convenient change of inequality): for all 0 < y < < = < 1,
P(u! < y, u =) IP(Vj E {1,..., m............. uy $ =)) (1 (2 y))
We observe that the joint cumulative distribution function of (u.: u. is a smooth function of (u. 2) when (u, =) (0,
(v,, 1). Note that the events Eş and {(u), uB) E (0, u)) x
(e;, 1)} are equal up to null set. Therefore, on this event, (u uft is an absolutely continuous random variable with density g (0, v2) x (v;, 1) + R,
02
gly. z) Oyd2
Plu
> 2) = m(m - 11 - -==-9)) -2=- < u
We compute
P(C ( E P(( +uj 20gl D) E,)
-Jocsr m(m 1) - -(z (z-1)) --)mm +lu+=-2u, ddydz..
We make the change of variables 0 v-V= y.
m(m - 1)
P(C n Ex)
(1 (1-18 mm 1 20, I EDdde
ff < <015
m(m 1)
(1-)mm-20l m () (/ 11-2001
Dm.
Using m > 2e > 24n, we have
8
Σ
1m-m)
<
24 6
3
This concludes the proof.
20

---

B Proofs of the results of the main text
B.1 Proof of Proposition
Let us lower-bound the smallest eigenvalue of Hu) which is equal
min T (u)a
||||=1
Now for a E R=+11 such that |a|| = 1,
a (u)a = Σ S o u,)o,(0 u = S( ""' L0 uz) dr.
m
m
2
0:4; =
Since Au 2n/ (because U)) and ug -1/2, um+1 1+ 1/2 the intervals [u+ + m 2, Us+1 17/2] for: E {0,.... m are disjoint and included in [0, 1]. Thus
Mit1 n/2
a (u)a
Σ
Ea.a(e u:) dx. 2=0
attn/2
1=0
Since (x) 0f < 112 and (xx) 1 if x 1/2, we have that (,((x) if x -1/2 and
(x) = if x > n/ Further recall that the are ordered increasing order. As a consequence,
n/2
a Hn >
Σ
0k
dr
k==0
Σ
[4i+1
11
k=
ak
(12)
2
i=0
h=0
where the last step, we used that (uu) > 2n and thus u4+1 U4 - 7 > A(u) > A(u)
A (u) (2))/2. Now, denote on = and e = Σt= ax. Then [|a|| = writes
(GH1 c;)² =1
1=0
Furthermore,
m+1 & Σ o
> (G41 0;) 2=
c+1 Σ
2
G419
1=0
1=0
Hence
Σ
2
1
4'
1=
which shows in conjunction with (12) that the smallest eigenvalue of H,)u) is lower-hounded by Au 8
B.2 Proof of Proposition
To show that G(u)= = (V (a, u) is Lipschitz-contimuouu on Un, we show that it is differen- tiable on Wd, and that its derivatives are uniformly bounded. The chain rule gives
0G,
m Da (u) OLL, (a; u) du,
8 Ln (a), ou,du;
Duk
Dux
21

---

From (10), using that a is twice continuously differentiable, it can be checked that Shn is differ- entiable in both its arguments and its derivatives uniformly upper-bounded when is bounded. Furthermore, for u E Ug.
8uy
8Mym. +1
(1)ل < [H) (1) &
A(u)
by Lemma I and Proposition 1. Finally, according to Lemma 3, aj is differentiable with derivatives uniformly upper- upper-bounde bounded on Uy, This concludes the proof.
B.3 Proof of Proposition
In this proof, we denote us (7) (resp. u. (T)) the position at time r of the neuron that initialization closest to to the left (resp. the right). Note that because of the movement of the neurons, it could be that up (resp. uff) does not remain the neuron closest to the left (resp. the right) throughout the dynamics. Our proof discusses when this phenomenon occurs. Similarly, denote w. (resp. R the neuron second closest to the left (resp. the right) of ug. Since the initialization is D-good, note that all these neurons are distinet.
Denote T the minimal time r E [0, Tmax) such that A(u(T)) & 2/2 or there are less than two neurons in some piece (Ut, Ut+1] of f*. Note that by assumption, A(u(0) > D > D/2 and there least 6 neurons in each interval initialization, thus T > 0. Furthermore, using the trivial inequalities 2 M /m+1// Af
8n 2n. Recall that 21 is the quantity defining the set U1 supporting the maximal solution of the equation (8). As consequence, do have T < Tmax- At the end of the proof, check that T < T, by controlling carefully the movement of each neuron.
M /2, +1 > 1 and 1///2 > 1). have -
Let us first bound the difference between the dynamics of and the dynamics that would have if at each time т, the weights a were given by aj (u(()). the best approximation of f by a piecewise constant function with subdivision u(r). For any T and j E (l,...,m, m}. by Lemma 6, we have
duj
(7) Ohy (ab(u(r)), dr
Ou,
=1 و@ا (a (u(()), u(T)) 0Lg Juj
(a (((((u(())))))))) u(T))
Ou, < 2M22M 1)]la, (u(T)) (u(T)) Vm c6(())())) (13)
We are therefore led bounding (u(T)) (u(T))) as follows:
2 M m + In
le,((((T) (((u()))
(by Lemma 7)
(u((T) 2 M m II
(since A(u(T)) > D/2)
D D(
(by definition of D).
2 M Vm +
Then the first term in (13) is less than
(mm +I+ 1)D(2))
D(A))²
27 2 +
26
and the second term in (13) less than
216 M2 D(A))2
D²(Af)
using D E A(u(0) < Af < 2M and m
214
Hence we obtain, for any < T and j E (l....,m. du
dr (r) + aL, (at(u(T)),
D
Ag
(14)
Du;
60
22

---

Now, let us examine how the neurons move. by leveraging Lemma 4 that gives exact formulae for ah, (u)()))), u(T)) = 0, hence
akn (u(((())) u(T)). First, if uj is not next to a discontinuity, Bug Buy
luy(7) (,(0)l < (Ag)T.
Let us now study what happens next to discontinuity v, Denote (ōf). = ft ff- W.l.o.g. assume that
In the reverse case, the proof is the same by swapping the roles of u, and uf and of uz and uf We are going to show that the dynamics up are divided into two phases. Define Ti as the minimal R (0)
- u.)
T E [0, 7i such that u! (T) = 2 7/2. In the first phase [0, Ti] we have u/((T) < 2/2 ? and u! moves towards In the second phase [T;: 7]. we show below that (T( [u; 7, + 1). Note that we can have T; = 0 if (0) > 3. It is also possible that T; = oo priori; this means that the second phase does exist. We show below that this case does not happen. Figure 7 depicts the two phases.
SaN
8a
f1a
211
12
14
02
12 o2
25 L1
300 16
14
(a) Phase
(b) Phase
Figure 7: Dynamics of the neurons next discontinuity e; In the first phase, of and uf move towards Us until the closest neuron (in this case u()) reaches the interval of size 7 centered in d In the second phase, of remains in an interval of size 2n around and none of the neurons move significantly.
Beginning by the first phase, we have, while (T) vi 3 and (B(r) > + according to Lemma 4,
aL,
(a (u(T)) u(T) = 1 - (T))
du.
(u.
OL,
(vi (t()))((8S)
(a
u (u(() u())
Ou R
(u) (T))2
For ease of computation, let d: (7) 0, - (T) and df((T) uf) - v. the distances between the neurons and Then, by (14),
ddR i dr
(r) + ddt
1 [(d (7)) + (T)) 24g
dr (T) <
2
(a) (T) dB (T))
(A
D(A
< (Aʃ)
60
since ((u(O)) 1. Thus, in some time less than T ( (T (7 < n, that is.
R either u/ reaches v, or u reaches + 7. Let check that the second event cannot actually
23

---

happen: while (T) < v and u (T) > + 3. we also have
dd dr (7) dr (7)
ddt
-2ng
+
- -T)))1 -20g.
(T) d (T)
By condition (c) of Definition 2 and by (14), we have di d) > D 604g
602g and
(A
(+T)
furthermore (r) + dff (7) < 1. An easy reasoning then shows that aß df is increasing. Therefore uit must remain further away from than u²:
In summary, we showed that there exists some time T/ < T when (T) = 12 - 3 which marks the end of the first phase, and we also have
d (T.) (T. (0) (0) > D.
Moving to the study of the second phase, let show that ut (r) stays in the interval (o; 7) e + n]
for [Te, T). Consider any & T such that u!! (T) U/ 17. Then have by (14) and Lemma
du dr (T)
(u: (T) - 2; (6)f (u. (T) U/ + 1))2
Ag Ag,
(15)
where the second upper bound comes from the fact that we have (T) A(u(T)) D/2, and furthermore, (x+n)² is increasing, hence
> 2 since
x²
(u. - 25)) (u. - U, n22
17 2
(Af)² 4 > 2Ag.
2
D
(D/222n)
Equation (15) implies that (T) t2- 7 for all E [T., 7). Similarly, consider any & 7 such that u!!(( (T) = v; + Note that, for such r, (T) is now on the right of U; and the neurons flanking
U/ are uz LL and ur. Thus we have by (14) and Lemma 4
du! dr (7) <
(e: (5)) (u; + 77 (T))
+
where the second lower bound unfolds similarly as previously. This shows that (T) u, + n for all E [Tr. T).
We now check that T < T, that is, for all + < T, ((u(T)) > D/2 and there are at least two neurons in each interval (2), 1. Starting with the first condition, we say that neurons uy and ug collide if (T)(T) - uy (T) = D/2 for some < T. Let us show that no pair of neurons collide.
We start by showing that there is no collision between wft and uf. In the first phase [0, TiJ, we have duf
dott dr (r) Ag. Recall that we also have dr (r) > -Ag and thus for 7 < Ts
4D
(T) - (T) > ut (0) (0) - 2T >
5
since u²(()- - (0) > D and T Ag = 1/10 by definition of T and Ag. As a consequence, uf- and up do not collide during the first phase, and we have
(T) < (T))
4D 0
17
4D
(16)
In the second phase, we can have wf E [1i, 0 + v] in which case uLd becomes the neuron flanking to the left and wh the neuron flanking to the right. Then (14) and Lemma 4 give
dufL dr
(ut - -0) - -
2 A <
+ Ag.
D
24

---

Of course, this bound also holds when wi [o--N) 77, U/]. because then second phase T E [7s, 71, by the previous upperbound and the fact that u (T)
du.L dr
Ag. Thus, in the
2 vi 2.2
M
(F(T) us (r) > 02 2
" [1 (Ta) + (
+ +Ag)
D
4D
T
1612 M²
Ag),
D
by (16). Let us now upper-bound each of the last two terms by P/10 to conclude. By definition of D,
(A
7 = 2m + 1)M²
Thus
M
3
D
<
1)2
221 (m + 1)2
10
using the definition of T, D (u((0) & 1, Af < 2M and m > 1. Finally, TAg D/10. Thus wtth and up do not collide.
We now show that uf and u.t do not collide. In the first phase [0, Tal, we have
(F( (7() uf (T) e; (7) d (r) D. As a consequence, up and uß do not collide during the first phase, and we have
(T) D (T.)
7 2
(17)
In the second phase, ui plays role symmetric to uL it can be, or not, the neuron closest the right of u; depending on whether u!! E [u; 17, u. or u!! [us, vy + m). As for I. we can show that in any case, for E [T., T).
du
16
Ag.
dr
D2
Thus one concludes as before: for T E [Te, TT, by the previous lowerbound and the fact that u/ (7) vi 3.
16 (16 + +0) (0o
(B(T) (T((T) > u (T.) (r Ti)
D2
Then, by (17),
(F(()) - (F) > D 7 (T( 16 M2
(1o
+ Ag)
D
2
where the last lower-bount unfolds similarly as for u.! and w.. Thus there is no collision between uf and uR.
The reader check that all other pairs of neurons do not collide, including those involving Up = - and um+11 = + n/2. fact, the proof is easier than for u L.. uf and uf u, because the discontinuity at e; attracts these neurons together.
Furthermore, we proved that before time T at most one neuron can escape on each side of a piece [u;, 0:41] of f. Since we start with at least four (and even six) neurons per piece, there is always before at least two neurons per piece.
This shows that T < T, and we also proved that at time T. all discontinuities have finished their first phase, hence there is a neuron at distance less than 77 from each discontinuity the target function.
B.4 Proof of Theorem 2
Take C' = 1-9 Then by assumption of Theorem 2,
8²
11 & 219 219 + 1)5
25

---

Moreover, by the definition of D from Proposition 3,
(A
1 213 21 1)
This implies that
82
D2 < 2m + 1)4
and in consequence
8 D
6m + 1)2
Then Lemma 10 shows that the initialization D-good with probability at least 8 (since the D-good property is monotonous in D).
Hence, with probability at least 1 1- according to Proposition 3, the maximal solution to (8) defined at least until T and at that time, there is neuron at distance less than from each discontinuity of the target function. Furthermore, 3r) < -
m+I < Av, hence Lemma 9 applies. This implies that
J. (x)) (n(T)), (T)) & 6M
The assumption on allow to conclude that the upper-bound less than &.
Remark 2. We did not try to optimize the value of C since our goal was to show convergence to global optimum and the dependency of the dynamics on the parameters (for instance, is remarkable that T does not depend on E).
B.5 Proof of Proposition 4
For I, Proposition holds since for (uu()) 16n > 2n. Thus (u(s))) well-defined and verifies
(aln(a,(((s)), u(s)) = 0.
Let, for L, = [|a(s) a (u(()) Recall that, by (11),
Val,(a, H,(u)a bu(
Hence, for & t,
(a(s) (on
= -a(ss - (((()())) (o., u(s) (oln((((((())) u(s)))
= (a(s) (1(s),)), (n((()))(a(s)) ar(((())))
A(u(s)) ((s)
8
D
>
V(s)2,
16
where the first lower bound is consequence of Proposition 1. Then have, for any
d ( ((())) (a(s) (u((ss)) da
di (s) (s) ds a(((((s))
ds 2
(a(ss) d;,((())), V.L, u(s)) de [(((ss)))
d
D v(s) + (u(()) V(s).
-
d
16
Let us now upper bound the norm appearing in the second term. We first have by the chain rule
daz
(s))) du
ds (x((s()))
(s).
du
ds
26

---

By Lemma (which holds since for A(u(s)) > 16n > 2n).
dag Ou
8
(u(s))
<
(2(m + (v(s)) + M).
(u((s)
Besides,
du ds (s)
< [e][vL,(((()),
By Lemma 8,
V (VLL(((ss)..(s)) < vm M|](s)
M||a(s)]l
(18)
Furthermore,
|a(s)||| < || (u,( (1)) + [la(s) - (u((s))) = II) + V(s).
By Lemmas 6 and 7, which apply since (uu())) > 2n and since there are at least two positions uy uy(s) in each interval [0%, 2t+1] for < t,
[a,((()))I < (u))( + [[ag(((s)) - (u(+))
16M m I1
< 2M mm +1+
(u(ss)
32M v Vm + In
< 2M 3Mvm+1 +1+
D
3M +1,
where the last upper bound is implied by the assumption D > 32n.
Now define Tmax inf {s > V(s) > 3M +1 and assume & min(t, Tmax) that (s)) & 3M + 1. Then we proved that [|a(s)] & 6MVm 1. Going back (18), we deduce that
VuLn(((s)) u(+))I & (m + 1)3/2 + 6M Vm + 1< 2 22 + 1)3/2.
(19)
Putting everything together, we obtain
d
2 (m + 1)3/22
2 M (0/3mm
(m + 1)3
at (u(s)))
(6M(m+ + 1)3/2 M)=
ds
A ((u(s))
D
All in all.
d (1 1
((s)))
-- v(s) vs)) + 2 (m + 1)3
D
ds 2
16
D
Hence
_ (V))) = V(s) ds 1 v()))) <
d
1 d
D V() -
2/3 (m 1)3 E.
ds
D
By Grönwall's inequality, for all & (t, T Tmax).
217 3 (m + 1)3
P V(0)= V(s) & exp
E(1 exp -
(20)
D22
23 (m + 1)3
< exp P V(0)
D E.
(21)
Finally note that (0 = |4)(00 < 2M / + and 2 ( < 2M / m + I by the as-
D sumption of the Proposition on E. Hence (20) implies that for all & min(t, Tmax). V(s) is (weighted) average of two terms less than 2M /m hence it less than 2M Vmm + T. This shows that T Tmaxx > t, which concludes the proof since (21) is then valid for = t.
27

---

B.6 Proof of Theorem 1
In the proof, we take C1 -2 and C2 = 2-36 Denote
5
D 6(m + 1)2
Lemma 10 shows that the initialization is D-good with probability at least 1 - 8. In the following, we study the case where this event happens.
Denote 7 the minimal time & > 0 such that A(u(t)) & D/2 or there are less than two neurons in some piece [us U+41] of f or ||a(t)]] || > 7M - Note that T >> O since the initialization is D-good. By Lemma 8, VuLy, and VaLy are Lipschitz-continuun
on compacts, hence the solution of the gradient flow is well defined for t < ' since defines a compact set of parameters.
Then all the assumptions of Proposition 4 are satisfied the time interval j0, t| for any < T. More precisely, the assumptions that do not come directly from the definition of T are the lower bound for D and the upper bound for e. The lower bound for D come from
6
D
32n)
(22)
6(m + 1)3
by (3) and the simple bounds d & 1, Af since & < 23 (m 1)29/2
2M, + 1 1> 1. The upper bound for comes from (3)
(Af))
8²
D
36 M (m 1)13/2 2 + 1)5/2
where the second upper bound uses m > 0, 5 < and Af < 2M. Therefore, according to Proposition 4,
2 M (m + 1)3 ||a(t) - a0 (u(t))l < 3M 3M + 1 exp f +
E,
(23)
D2
Furthermore, the proof of Proposition 4 actually implies that
[la, & 3Mvm+1 and ||a(t)] < 6M
+1. II.
(24)
The second bound implies that the condition [la(t)]| > 7M / m + I in the definition of T never active. Let us distinguish between two phases: letting
is actually
16 D
266 M (m + 1)3 96(m 1)2
216 M + 1)3
To
log
8 log
6(a.))²
8(Ar)²
then the first phase corresponds to t To and the second phase for t To-
Analysis of the first phase. In the first phase, each neuron moves at most by
ÖLy (a()),(()) TTollV (a, u(+)) 2 ToM 1)3/2
To max Du,
where the second upper bound comes from (19) in the proof of Proposition 4. This quantity is less than 8
6144(m + M2
2 16 M (m + 1)3 ) < 48(m 1)2
(m
5
8 log
8(A))2
Let us check this condition: we have
6144(m M2
M2 (m 1)3
5 log
8(Af)² E
16- 6144(m + 1)7/2M2
2M (m + 1)3/16
log
81/16(Af)1/8
16- 6144(m + 1)7/2 M
44M(m + 1))e, 6Df
log
28

---

since m + m+ 1, < 1, and 2M/ > 1, hence (2M/Af) 188 & 2M/Af. Next, upper-bounding (z) by x, we have, by (3),
768(m + 1)7/2 M
2 2 + 1)3
64 14.6144((m + 1)8
6
log
8(Af)2
E
6144)(Af)
22 M (m + 1)5
6
48(m + 1)2
using Af < 2M and m > 0. Note that the upper bound =T (m + 1)3/2 < D/s also implies that
T
To < 2 1)3/2
(25)
2=(
12
since m > 0, < 1 and A < 2M. Since each neuron moves by at most D/8 in the time interval [0, Tol and since (u(())
D. we deduce that
3 D.
A(u(To)) >
(26)
Similarly, by condition (c) the definition of a D-good vector, for all discontinuities Vis
(u, + uz x4 - 2n >> D,
thus
3 D. > 4
Iu (To) + (To 20y
(27)
Furthermore, there at least four neurons each piece of f at To. because at most move out of each piece by either side between and TV.
Analysis of the second phase.
Let
8(Af)² 2 m +I 6 M (m + 1)5/2
2
Aa
In the second phase > To. we are able to control by Aa the distance between a(t) and the weights aj (u(t)) that are the best approximation of f* by a piecewise affine function with subdivi- sion u(t). To show this, first note that the first term in (23) is smaller than Aa when
Aa
3M m 1 P <
which is equivalent to
12M \m + I
16
t t> log
Aa
D
which is implied by t > Ty. Furthermore, the second term in (23) is smaller than Aa because, by definition of D and by (3),
217 3 (m
1)3
36
217 1LTM3(m 1)7
63
Aa
D2
82
2 2 (m + 1)5/2
210
Hence, for all To < 1 < T.
< Aa
||a(t) - ((((()t))l
2
29

---

Furthermore, note that the assumption of Lemma 7 applies for t < T since A(u(t) > D > 2n by (22). Therefore, by Lemma and by (3),
Mv +1 A(u(t)) "
(a]((())) ao(u(t))
2 M V +
2 16M + 115//2
68( ()(
2 M (m + 1)5/2
6 Aa Aa
27
By the triangular inequality, we deduce the upper bound that we were after, that is
||a(t) a](((()) < Aa.
As in the proof of Proposition 3. we can now control the distance between the true dynamics and the one that would have if the weights were equal to (u()). Namely, for any To < and j E (1....,,,, m). by Lemma 6 (which applies since ((u(t)) > 2n by (22)), we have duy de
0Ln (aā(u(t)), u(t))
(1) +
Ou,
ÖLn
(a(t), u(t)) ((t)),((t)) aL, Ou, (ai(u(t)). u(t))
=
Duy
< 2MM + 1)la((t) af(u(t))l + vm T](a(t) a
The first term is less than
(Vm+I- 1)D(
D(D
2M + 1)
2 2 +1
27
and the second term is less than
D2(Af)*
D(
Vm + +I(a))))2 228 22 +1
216
using D & ((u(0)) < 1, AS < 2M and m + 1 > 1. Hence we obtain, for any To & < and j E mJ
duj (t) + I.m (ağ (ut)),,), u(t)) & Ou,
D(AS)
dt
120
We are therefore in a situation very similar to the proof of Proposition 3, starting from (14). One can check that all the arguments used in the proof also apply here. On top of the estimate above that resembles (14), the crucial facts that make the argument of Proposition 3 work here are the bounds (26) and (27) as well the fact that there are at least four neurons together are very similar to the conditions ensuring that (0) is D D-good in the proof of Proposition 3. Another key point is (25), ensuring that time at least equal to 112/11 12 remains after the first phase of this proof, which is enough time for the dynamics described in the proof of Proposition 3 to unfold.
each piece f at To. which
This yields that T' T. and that at time T, there is a neuron distance less than y from each discontinuity of f*. Furthermore, 3n & T <
Av, hence Lemma 9 applies. Thus
L. (1lla x(T)) (x)) < 6M2mm mm
2
where the second upper bound comes from n < m + and from (3). Furthermore, by (24) and by Lemma 8,
(T,((((),, u(T) I,,(at u()))
vm T 1) M)]la(T) - (T)(il)))
16M (m - - -
30

---

Let us show that this term is less than 5/4. Recall that, by (23),
|a(T)) az (u(())) & 3M Vm + lexp v 2 3 (m + 1)3
D2
By definition of D and T, by using exp( -x) 1/2 for and by (3),
8
16 1)8/2. 3M V lexp P 48M (m + exp exp 16(m
())
48 16M2 (m (Af)
8 ((A))) 231 (m + 1)0/2
using Af & 2M, 1, and + 1 1. Furthermore, by (3), get that
16M (m 1)3/2. 277 1)3 3 221 M + 1)
D
We therefore obtain the sought 5/4 upper- upper-bound bound and can conclude that
Sf ((( < ( (Ults (xx)) (x
(a()), - L,, ((()) E
C Experimental details and additional experiments
Our code is available https: http:////ththh...ooo///ee//eeeea
Numerical illustration in the setting of Section 2. To obtain Figures 3 and 4, we use the parameters of Table 1. For Figure 5, we use the parameters of Table 2.
Name
Value
Name
Value
m
20
20 1
10-5
E
7)
4 10
4 10
P
1.8 10
108
h Additive noise
10-5
10-5
Uniform on [-1,1]
Additive noise
Uniform on [-1,1]
Table 1: Parameters of Figures and 4.
Table 2: Parameters of Figure 5.
Our target function is defined by f" on [o., 0.2], 0..35, 0.5), (0.65, 0.8). /" 0.5, 0.65 and f = 4 elsewhere. The activation function is a piecewise cubic polynomial defined by x + min(max(446) (4 + 0.5)3,0) 0.5) + min(max(O..
4(0.5 2²3 , 0.5).
We re-run the same SGD experiment as above twenty times, and plot in Figure 8 the average L2 distance the target as function of E, averaging over the initialization randomness and SGD randomness. This confirms that, in our setting, the SGD is able to recover the target function in the two-timescale regime (e < but fails outside of the two-timescale regime (E = 1). The transition between the two regimes seems to occur for zs 0.1.
The number of iterations in Table is much larger than the one in Table 2. There are two levels of analysis to explain this difference. The most straightforward reason that the positions u evolve at speed eh, which is much smaller in Table 1. However, one may note that it is not larger by
31

---

10c
entos
10-2
0.01
Figure 8: L2 distance with the target as a function of in the ID experiment, with repeats
factor 1/s 50, 000 but "only" by factor ~ 200. To understand why, we have to get more into the details of the dynamies, to understand the order of magnitude of the number of steps required before convergence. In the two-timescale regime, the limiting factor for convergence is the movement of the positions u. At each step, they move by an order of ch 10-10, The positions need to move on scale of 5 10-2 to align with the discontinuities of the target. Hence the required number of steps is 0.05/(2 10 10-19) 2 10 In the standard regime, on the contrary, the limiting factor for convergence is the movement of the weights They move by an order of h = 10-5 at each step, and they need to move by distance of = necessitating = 5 10 steps to achieve convergence.
Finally, note that it is possible to increase h in Table while keeping the same behavior (in our experiment, h is kept the same value in Table 2 in order facilitate the comparison). More precisely, taking h = 10-3 in Table 1 yields similar results while dividing the computational cost by 100.
Higher dimensions. In 2D, we use the parameters of Table and 4. The positions are initialized uniformly over (0, 1] and the weights uniformly over [0,3]. The target is
8 (x, = 1.20.3 + 1u20.5 + 1.30.7 + 1930.3 + 1,00.5 + 1,20.7.
The activation function is the same as in the one-dimensional case. We SGD with batch size 10
Name
Value
Name
Value
10
10
1
6
10-2
1]
10-2
1]
10
P
300
P
5 103
h
1.0
1.0
Additive noise
None
Additive noise
None
Table 3: Parameters of Figure 6a.
Table Parameters of Figure 6b.
As in the one-dimensional case, we re-run the experiment twenty times and report the results in Figure 9a.
We perform similar experiment in 10D, using the same setup. The target
f" 210)
Σ 1 20.3 + 12,00. + 10,20.7
We use SGD with batch size 10a. The results in terms of L2 distance reported in Figure 9b.
32

---

0.025
0.020
0.020
0.015
I eaTor
0.015
1g eror
0.010
0.010
0.005
0.005
0.000
0.01
1G
0,01
10
In 2D
(b) 10D
Figure 9: L2 distance with the target as function of e in the higher disberr-immnsionall experiment, with 20 repeats.
ReLU networks. The goal of this experiment use ReLU activations to approximate piecewise- affin targets in 1D. The target is a ReLU network with positions u [0.3, 0.5, 0.7] and weights a = [1.0, - 2.0, 3.0J. We use the same setup as for the 2D experiment described above. The results reported in Figure 10.
0.5
Thrzyt
0.6
Targst
218131
0.5
0.5
20015
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.1
00
0.0
0.01
0.8
0.2
0.4
0.5
0.2
1.0
0.0
0.2
0.6
0.5
0.5
(a) After training in the standard (b) After training the two- (c) T2 distance with the target as a regime
timescale regime
function of e, 20 repeats
Figure 10: Experiment with ReLU activation and piecewise affine targets. In the standard regime, some kinks of the target are not covered by neurons. This is not the case in the two-timescale regime.
D Additional remarks
D.1 Counter-example in the case non-uniform initialization
It is easy to craft an example where gradient flow in the two-timescale limit does not converge to the global minimum if the positions of the neurons not drawn uniformly at random initialization. Take for instance the case where there are three pieces in the target, the leftmost piece at level 1, the second one at level -1 and the third one level Consider the case where all neurons are in the third piece at initialization. Then (in the two-timeseas timescale limit) the bias and the weights are all instantly equal to zero, which is the solution of the optimization problem in a. Looking at (10), this shows that the positions do not move, and thus that the neurons remain in this local minimum.
This example may seem artificial, but in fact, more generally, the case where consecutive pieces are not covered by any neuron often corresponds to local minimum of the two-timescale dynamics. This is why we require neurons on every piece initialization avoid falling in this local minimum.
D.2 Ideas of proof for SGD
The proof of Theorem consists bounding the difference between the actual dynamics and the dynamics that would have if the weights were given by aj (u(t)), that is, by the weights in the
33

---

two-timescale limit with 17 = 0. This requires to bound two errors terms, one coming from the fact that 7) > and one coming from the fact that 0. By making and small enough, we ensure that both terms are small, which in turn allows to describe the trajectories of the weights and of the positions throughout the dynamies.
Moving from gradient flow to stochastic gradient descent induces two additional error terms: discretization error, and noise error. However, taking small enough step size allows bound both error terms and thus ensures that (with high probability) the SGD dynamics are close to the gradient flow dynamics. For this reason, we believe that our proof structure (namely, bounding the difference with the two- awo-timescale limit as in Proposition 4, then showing that this bound allows to describe the trajectories of the weights and of the positions as Theorem 1) should adapt the SGD case, the condition that the step size is small enough.
34


Reviews:
[{"review_id": "WnSsuwxrLp", "reviewer": "Reviewer_WNiU", "summary": "The paper studies the training dynamics of fitting a one hidden layer shallow network with heaviside activation to a piecewise ground truth function with one-dimensional input. It proves that gradient flow always recovers the ground truth in finite time with only mild over-parametrization.", "questions": "The paper would greatly benefit from a few comments on whether the authors would expect the same phenomenon to be observed in high dimension and what the difficulty would be. Some numerical experiments in the high dimensional case would be a great addition as well.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper is well-written, and intuitions behind technical proofs are well-presented, and theoretical results are well-supported by numerical experiments. The theoretical result itself is a nice observation, despite being in the simple one-dimensional input case.", "weaknesses": "The paper only considers the one-dimensional case. Based on the proof techniques, it is not clear if it is extendable to high dimension, which is of ultimate interests in the deep learning theory community, since the derivation in section 4.2 would not hold any more. While it is understandable that such a result would be difficult to obtain in high dimension, the paper didn't present any experimental results in the high-dimensional case either.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Your question on the generalization to higher-dimensional problems, including numerical experiments, is shared with the other reviewers. It is thus addressed in the common rebuttal."}, {"review_id": "6ljY3s4QJj", "reviewer": "Reviewer_JDX5", "summary": "In this paper, the authors considered the problem of learning piece-wise linear function in 1d using two-layer neural network. They considered gradient flow on mean-square loss with different learning rates for 2 layers (two-timescale). Specifically, the outer layer weights are moving much faster than the inner layer weights. The activation used in 2-layer network is similar to a rescale version of sigmoid activation. This paper shows that under proper choice of the parameters, GF converges to small loss within polynomial time in relevant parameters. Experiments are provided to support the results.", "questions": "1.\tIn the experiments, I was wondering if one could elaborate in Figure 5 that why ‘the dynamics create a zone with no neuron’. It seems to me that there are neurons near every discontinuity of $f^*$. Also, it seems in Figure 4(c) and Figure 5(c), the number of steps for training are different, what is the reason for that?", "limitations": "The limitation is discussed in the paper. This is a theoretical work and therefore no foresee negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tUnderstanding the training dynamics and convergence of neural networks is an important problem.\n2.\tThe paper is overall easy to follow and clearly written. The proof sketch is given so that the reader can understand the main proof idea.\n3.\tThe idea of this two-timescale/two different learning rates in analyzing the training dynamics for neural networks seems to be interesting.\n", "weaknesses": "1.\tThe problem considered is only in 1d and it would be interesting to see if the analysis could be generalized to multi-dimension.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The problem considered is only in 1d and it would be interesting to see if the analysis could be generalized to multi-dimension.\n\nThis question is shared with the other reviewers and is adressed in the common rebuttal.\n\n> In the experiments, I was wondering if one could elaborate in Figure 5 that why ‘the dynamics create a zone with no neuron’. It seems to me that there are neurons near every discontinuity of $f^*$.\n\nIn Figures 4 and 5, **the neurons are represented by vertical dashed lines** (the orange round markers do not represent neurons, they are only present for black&white and color blind lisibility). In Figure 5(c), the discontinuity of the target function at $x=0.5$ is not covered by a neuron: the neural network has a flat zone between $0.41$ and $0.6$, whereas it should jump at $0.5$ if it were optimal. This stands in sharp contrast with Figure 4(c) where neurons are evenly distributed on the whole interval. We will improve the readability of this figure in the next version.\n\n> Also, it seems in Figure 4(c) and Figure 5(c), the number of steps for training are different, what is the reason for that?\n\nIt could seem like we are favouring the algorithm in the two-timescale regime by running it on a larger number of steps. In fact, it is not the case because **we ran both algorithms until convergence**; running the algorithm with $\\varepsilon = 1$ for a larger number of steps would not lead to an improvement.\n\nFurther, we can elaborate on the difference of steps to reach convergence in the two cases. There are two levels of analysis to explain this difference. The most straightforward reason is that the number of steps should scale more or less as the inverse of $\\varepsilon$, since each step (in $u$) gets scaled down by $\\varepsilon$ in the two-timescale regime. This explains why the number of steps is much larger in Figure 4.\n\nHowever, you may note that it is not larger by a factor $1/\\varepsilon = 50{,}000$, but “only” by a factor $\\simeq200$. To understand why, we have to get more into the details of the dynamics, to understand the order of magnitude of the number of steps required before convergence. \nIn Figure 4, the limiting factor for convergence is the movement of the positions $u$. At each step, they move by an order of $\\varepsilon h \\simeq 10^{-10}$. The positions need to move on a scale of $5 \\cdot 10^{-2}$ to align with the discontinuities of the target. Hence the required number of steps is $0.05 / (2 \\cdot 10^{-10}) \\simeq 2 \\cdot 10^8$.\nIn Figure 5, on the contrary, the limiting factor for convergence is the movement of the weights $a$. They move by an order of $h \\simeq \n 10^{-5}$ at each step, and they need to move by a distance of $\\simeq 5$, necessitating $\\simeq 5 \\cdot 10^5$ steps to achieve convergence.\n\nWe will include a precision on this point in the camera-ready paper if accepted.\n"}, {"review_id": "Dn979hMWr6", "reviewer": "Reviewer_83X8", "summary": "This paper studied the problem of fitting a piecewise constant univariate function with a shallow neural network. Specifically, the authors consider a gradient flow with a time-scale difference between the dynamics of the first and the second layer weights. It is shown that the trained shallow network can be arbitrarily close to the target function in $\\mathcal{L}_2$, as long as the weight update on the first layer is much slower than one on the second layer.", "questions": "See \"Weaknesses\"", "limitations": "See \"Weaknesses\"", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The two-time-scale regime seems novel in training neural networks. The results are well presented and their proofs are clearly explained.", "weaknesses": "Only a very special problem is studied. \n\n1. The target function is univariate, piece-wise constant. This is very restrictive. \n\n2. The loss is a population loss, thus the case of finite samples (fixed design or random samples) is not considered.\n\n3. Network is quite different from those studied in other works. The activation function is a smoothed version of a stair function; the first layer is only parametrized by the bias at every neuron. \n\nWith this many assumptions/restrictions, even though the main results are well presented and explained, it is hard to see whether those observations can give insights into the usefulness of implementing two-time-scale training for practical networks. The author did not discuss the limitations of these assumptions, nor did they show how two-time-scale training can be used in practice, even empirically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We agree with the reviewer that the main focus of this paper is on the study of a specific problem and that it does not readily lead to practical implications. Below, we detail why we still believe that our work contributes towards a theory of neural networks.\n\n**The theory of the optimization of neural networks is a notoriously hard problem; consequently, research on this topic makes progress at small steps.** For instance, the NeurIPS paper of Safran et al. (2022), to which we compare in detail, is similarly restricted. The other related works to which we compare in Section 3 are also restricted to specific settings: for instance, the mean-field setting is restricted to infinitely large neural networks and does not lead to quantitative convergence rates; the neural tangent kernel approach is also restricted to large neural networks and does not explain feature learning. Our work also has important restrictions, but is novel in providing a theory for neural networks with a moderate width and feature learning dynamics. Moreover, our description of the non-linear dynamics is remarkably precise and quantitative, compared to the other approaches. \n\nFurthermore, our paper underlies the **general applicability of the two-timescale technique** (see Section 4.1), beyond the specific one-dimensional illustration that we study in depth. The two-timescale regime is mathematically tractable if one can solve the two-timescale limit equations (5) of the paper. In this paper, we restrict ourselves to a simple setting for which the solution is simple (Section 4.2). This enables a fluid illustration of the central concept of this paper, the two-timescale regime. However, **any other setting for which Eqs. (5) can be solved could lead to a convergence analysis following the same lines.** \n\nMore precisely, we have the following expectations for the generalizations that the reviewer suggests:\n1. We believe that **the generalization to higher dimensional problems is possible, as shown by simulations**, although it is a theoretical challenge, which we reserve for future work. We develop this point in the **common part of the rebuttal**.\n2. **Our results can be generalized to finite sample sizes** (say, for single-pass SGD) at the cost of greater technicalities in controlling the deviation from the two-timescale limit. This follows a perturbation analysis similar to the one of Section 5.2, with additional terms due to random sampling. This setting actually corresponds to the experiment described in lines 279-281, that shows that SGD indeed closely follows the behavior of the two-timescale limit. We will mention this possible generalization and add a rough sketch of proof in the next version of the paper.\n3. We believe that **our results can be adapted to ReLU networks for approximating piecewise-affine functions, as shown by simulations** and as stated in the conclusion of the paper. Simulations show that the expected alignment of neurons with the discontinuities (of the derivative) still holds **(see common part of the rebuttal)**, although the mathematical derivations is more arduous. \n\nIn dimension $1$, we also believe that **it should be possible to analyze more standard parametrizations of the inner layer** of the form\n$$f(x; a, u) = a_0 + \\sum_{j=1}^m a_{j} \\sigma_\\eta (v_j x - u_{j}).$$\nHowever, this would make the parametrization of the “position” of neuron $j$, namely $u_j / v_j$, less natural, and thus would add technical difficulties to the proofs. We avoided this technicality for simplicity. \n"}, {"review_id": "tbGsSOEzgo", "reviewer": "Reviewer_VU9p", "summary": "This paper studies the training of 2-layer neural networks and proposes a two-timescale limit/regime. In this \nlimit/regime, the learning rate of the first layer is much smaller than the learning rate of the second layer. \nAs a result, the training of the network can be viewed as training the first layer and performing linear regression \nover the first layer outputs, which is simpler/more structured than training both layers at the same rate. To \ndemonstrate the usefulness of this strategy, this paper considers a toy model and shows that a 2-layer network can fit \na certain family of 1D piecewise constant functions. The authors also empirically show that SGD can fail to fit this \nfamily of functions outside the two-timescale regime.", "questions": "* How general is this strategy? Is it possible to apply this strategy to problems (even toy ones) with dimension higher \n  than $1$ and more standard 2-layer networks?\n* Can we relax the requirement on the initialization? For example, can we remove the requirement that each interval \n  contains at least $6$ $u_j$?\n  Intuitively, when some interval contains no neurons, it is still possible that some neurons from those fitted \n  intervals can move to that interval and fit the target function on that interval. \n  I know the current requirement is reasonable in your setting, I am asking this because I feel this type of global \n  feature learning process is important when the dimension is high. ", "limitations": "This is a theoretical work and, as far as I can see, has no potential negative societal impacts. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The presentation is clear.\n* This paper not only contains results in the $\\varepsilon \\to 0$ limit, but also non-asymptotic results for small but \n  non-vanishing $\\varepsilon$. The derivation in the $\\eta \\to 0, \\varepsilon \\to 0$ limit is clean (Sec. 4.2), and \n  the asymptotic-to-non-asymptotic parts are also easy to follow.\n* This paper reminds me of a technique that is gaining popularity in the theory community: training the network for \n  one (large) step, freezing the first layer, and then performing linear regression in the second layer using the \n  features learned in the first layer (cf. [AAM22], [DLS22]). The limitation of this technique is that since the \n  first layer is fixed after the first layer, it lacks the ability to refine the learned features. I feel the \n  strategy introduced in this paper is a potential remedy to this problem, as here we also have the linear regression \n  part of the argument, but the first layer can be trained for multiple steps. \n\n[AAM22] Abbe, Emmanuel, Enric Boix Adsera, and Theodor Misiakiewicz. “The Merged-Staircase Property: A Necessary and Nearly Sufficient Condition for SGD Learning of Sparse Functions on Two-Layer Neural Networks.” In Proceedings of Thirty Fifth Conference on Learning Theory, 4782–4887. PMLR, 2022. https://proceedings.mlr.press/v178/abbe22a.html.\n\n[DLS22] Damian, Alex, Jason D. Lee, and Mahdi Soltanolkotabi. “Neural Networks Can Learn Representations with Gradient Descent.” arXiv, June 30, 2022. http://arxiv.org/abs/2206.15144.", "weaknesses": "* Almost all things in this paper are 1D and somewhat tailored to this specific piecewise constant function class. \n  I wonder whether/how this can be generalized to higher dimensions, other network architectures, and more general \n  function classes. \n* It seems that the dynamics are still relatively local. That is, we need some neurons in each target interval at \n  initialization, which may not be reasonable when the dimension is high.\n* The authors should probably add some discussion on the training-for-one-large-step-type technique (see the Strengths \n  part of the review). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> How general is this strategy? Is it possible to apply this strategy to problems (even toy ones) with dimension higher than 1 \n and more standard 2-layer networks?\n\nWe have evidence showing that **the two-timescale strategy applies to other settings (higher-dimensional problems, ReLU networks for approximating piecewise-affine functions), see the common rebuttal**. Nevertheless, a full general understanding of the impact of the two-timescale regime is an open question, which is left for future work.\n\n> Can we relax the requirement on the initialization? For example, can we remove the requirement that each interval contains at least $6 u_j$ ? Intuitively, when some interval contains no neurons, it is still possible that some neurons from those fitted intervals can move to that interval and fit the target function on that interval. I know the current requirement is reasonable in your setting, I am asking this because I feel this type of global feature learning process is important when the dimension is high.\n\nWe are rather pessimistic, for the following reason. It is reasonably easy to craft an example of a local minimum of the two-timescale problem (equation (5) of the paper) where a discontinuity of the target function is not covered by any neuron. **Without any assumption on the initialization, it is possible that the gradient flow dynamics may fall into this local minimum.** Avoiding such minima is a challenging next step which would certainly require additional ingredients. We will add this discussion (and exhibit such an example of a local minimum) in the next version of the paper.\n\n> The authors should probably add some discussion on the training-for-one-large-step-type technique (see the Strengths part of the review).\n\nFinally, we agree that the two-timescale regime can be seen as a refinement of layer-wise training, where we cyclically take one gradient step in the inner layer and many gradient steps in the outer layer. We thank you for the additional references; we will make sure to add them in the paper and discuss the connection.\n"}]

Author rebuttal:
Dear reviewers,

We warmly thank you for your time and relevant comments, which will help us improve our work. If accepted, we will take into account your suggestions, making use of the additional page. 

Since all reviewers raised the relevant question of the **applicability of our approach to more general settings**, in particular beyond dimension 1, we address it below, and leave the answers to other questions in individual responses. 

Sincerely,

The authors

------

This paper introduces the two-timescale regime in a general setting (Section 4.1). The choice of the specific setting we analyze in detail (1D, piecewise-constant target, and bias-only first layer) is motivated by the simplicity to derive mathematically tractable expressions for dynamics of the two-timescale limit (Section 4.2). Relaxing these assumptions makes the analysis more complicated and is postponed to future work. Nevertheless, following the comments of the reviewers, we next present preliminary experimental results in dimension larger than 1 and for ReLU networks.

**Dimension larger than 1.** We first emphasize that piecewise constant functions are a complicated class in higher dimensions; for example, a neural network with sigmoid activations is able to learn such a function only under certain conditions, including that the shape of the constant regions should be polygons. 
As a first step, on $\mathbb{R}^d$ $(d > 1)$, we consider multivariate neural networks of the form 
$$f(x; a, u) = a_0 + \sum_{j=1}^m \sum_{k=1}^d a_{jk} \sigma_\eta (x_k - u_{jk}),$$
where the $j$-th neuron has a $d$-dimensional position $(u_{jk})$ and a $d$-dimensional weight $(a_{jk})_{1 \leq k \leq d}$. To ensure that the neural network can approximate the target piecewise constant function, we choose a target function of the same form. We then perform similar experiments as in Figures 4 and 5 in the main paper (and Figure 7 in the appendix), that is, to train the neural network with gradient descent, both in a two-timescale regime and in the standard regime. 
We report the results in the attached PDF file for $d=2$ and $d=10$. In a nutshell, **the conclusions are similar to the paper: recovery can fail in the standard regime**, due to discontinuities of the target function that are not covered by neurons after training (or, in other words, the gradient descent converges to a local minimum). **By keeping the exact same setting but lowering epsilon to transition into the two-timescale regime, we obtain convergence to a global minimum.**

We expect that the corresponding mathematical derivation should be doable with similar tools as in our proof, at the cost of significant additional technicalities. Further generalizations beyond this somewhat artificial example are left for future work.

**ReLU networks.** In a similar spirit, it is also possible to consider the case of using **ReLU activations to approximate piecewise-affine targets**. The results are also reported in the attached PDF file (for dimension 1, but we could mix both extensions and also consider higher-dimensional problems in this case), and **a similar conclusion holds**. Here again, there are additional technical difficulties that complicate the proof, but we believe that there is no fundamental reason that our mathematical approach should not apply to this case.

These discussions and experiments will be added in the next version of the paper. 


Meta-review: The reviewers unanimously find the paper interesting and result worth publication. The area chair agrees with the evaluation after reading the discussion and the manuscript.
Decision: Accept (poster)