Depth Separation with Multilayer Mean-Field Networks
Authors: Yunwei Ren
Mo Zhou
Rong Ge
Venue: ICLR 2023 notable top 25% (2023)
Keywords: depth separation
mean-ﬁeld
nonconvex optimization

Abstract: Depth separation—why a deeper network is more powerful than a shallow one—has been a major problem in deep learning theory. Previous results often focus on representation power, for example, Safran et al. (2019) constructed a function that is easy to approximate using a 3-layer network but not approximable by any 2-layer network. In this paper, we show that this separation is in fact algorithmic: one can learn the function constructed by Safran et al. (2019) using an overparametrized network with polynomially many neurons efﬁciently. Our result relies on a new way of extending the mean-ﬁeld limit to multilayer networks, and a decomposition of loss that factors out the error introduced by the discretization of inﬁnite-width mean-ﬁeld networks.

Published as a conference paper at ICLR 2023
DEPTH SEPARATION WITH MULTILAYER MEAN-FIELD NETWORKS
Yunwei Ren
Mo Zhou
Rong Ge
Carnegie Mellon University sewweir@andee cmm.cdu
Duke University mo zhou cs duke. edu
Duke University
ronggelca cs duke. edu
ABSTRACT
Depth separation- deeper network is more powerful than shallower one- has been a major problem in deep learning theory. Previous results often focus on representation power. For example, Safran et al. (2019) constructed function that is easy to approximate using 3-layer network but not approximable by any 2-layer network. In this paper, we show that this separation is in fact algorithmic: one can learn the function constructed by Safran et al. (2019) using an overparam- eterized network with polynomially many neurons efficiently. Our result relies on a new way of extending the mean-fichl field limit to multilayer networks, and a de- composition of loss that factors out the error introduced by the discretization of tffnite-width mean-field networks.
INTRODUCTION
One of the mysteries in deep learning theory is why we need deeper networks. In the early attempts, researchers showed that deeper networks can represent functions that are hard for shallow networks approximate(EElann & Shamir, 2016; Telgarsky, 2016; Poole et al., 2016; Daniely, 2017; Yarotsky, 2017; Liang & Srikant, 2017; Safran & Shamir, 2017; Poggio et al., 2017; Safran et al., 2019;
Malach & Shalev-Shwartz, 2019; Vardi & Shamir, 2020; Venturi al., 2022: Malach et al., 2021). In particular, seminal works of Eldan & Shamir (2016); Safran et al. (2019) constructed a simple function (x) = ReLU(1 - [|=|]) which can be computed by 3-layer neural network but cannot be approximated by 2-layer network.
However, these results are only about the representation power of neural networks and do not guarantee that training deep neural network from reasonable initialization can indeed learn such functions. this paper, we prove that one can train neural network that approximates fz(x) ReLU(1 ||>|]) to any desired accuracy - this gives algorithmic separation between the power of 2-yayer and 3-layer networks.
To analyze the training dynamics, we develop new framework to generalize mean-field analysis of neural networks (Chizat & Bach, 2018; Mei et al., 2018) to multiple layers. As a result, all the layer weights change significantly during the training process (unlike many previous works on neural tangent kernel or fixing lower-layer representations). Our analysis also gives a decomposition of loss that allows to decouple the training of multiple layers.
In the remainder of the paper, we first introduce our new framework for multilayer mean-fied field anal- ysis, then give our main result and techniques. We discuss several related works in the algorithmic aspect for depth separation in Section 1.3. Similar to standard mean-field analysis, we first consider the infinite-width dynamics in Section 3, then discuss our new ideas in discretizing the result to a polynomial-size network (see Section 4).
1.1 MULTI-LAYER MEAN-FIELD FRAMEWORK
We propose way to extend the mian-field analysis multiple layers. For simplicity, state it for 3-layer networks here. See Appendix A for the general framework. In short, we break the middle layer into two linear layers and restrict the size of the layer in between. More precisely,

---

Published as a conference paper at ICLR 2023
Outaut: (())
Output: f(x)
0g
W/2
Wg: 00 x co
F(x)
A
W
Wi
Input
Input
Figure Difference between previous Nguyen Pham (2020) (Left) and our framework (Right).
define
f(x) a (W2F())) F(x) = A11(W
m2
mi
where Wi E Rimixdd A E Dxmi, W₂ Rm2xD a2 E Rm are the parameters, and F(x) E RD represents the hidden feature. See Figure for illustration. Later we will refer to the step of x + F(x) as the first layer and F(x) + f(x) as the second layer, even though both them actually are two-layer networks.
In the width limit, we will fix hidden feature dimension D and let the number of neurons mi, M2 go infinity. Then, get the infinite-widih network
f(x
E a20(w22 F(x)), F.(x:) (a),w))))p
E a10 x)), Vi E [D],
(ag.wp))-pp
where (HI,))EED)) are distributions over RI+d with a shared marginal distribution over wt, and μl2 distribution over II+D, Note that, unlike the formulation in Nguyen & Pham (2020), here the hidden layers are described using distributions of neurons, whence are automatically invariant under permutation of neurons, which is one of the most important properties of mean-field networks. One can choose P2 to be empirical distributions over finitely many neurons to recover a finite-width network. In fact, we will do so in most parts of the paper so that our results apply to finite-width networks of polynomially many neurons. The network can be viewed as a 3-layer network with intermediate layer A,A, which is low rank. This reminiscent of the bottleneck structure used in ResNet (He et al. (2016)) and has also been used in previous theoretical analyses such as Allen-Zhu & Li (2020) for other purposes.
Learner network Now we are ready to introduce the specific network that we use to learn the target function. We set D = and couple aj with wi.
F(x) = F(x; = E
[|ww|] oww x)},
w-yn
(I)
f(x)
12, p1) (wibb)>us
E (wwFF(x;p)) b2).
Here, a is the ReLU activation, and μn E (RR) and E (RR2) are distributions encoding the weights of the first and second hidden layers, respectively. We multiply each first layer neuron by ||w||| to make F more regular. This 2-homogeneous parameterization is also used in Li et al. (2020) and Wang al. (2020). In most parts of the paper, μi and μ2 are empirical distributions over polynomially many neurons. We use μ1, #2 to unify the notations in discussions on infinite- and finite-width networks.
Restricting the intermediate layer to have only one dimension (D = 1) is sufficient one can learn & + a | for some a E with the first layer F(x) and a |||||||||||| + a(1 - || [] with the second layer For the network that computes F(x), we do not need a bias term as the intended function is homogeneous in æ. Though we restrict the first layer to be positive, it does not restrict the representation power of the network the second layer can be either positive negative. For the second layer, even though a single neuron sufficient, we follow the framework and over- parameterize the network.
2

---

Published as a conference paper at ICLR 2023
1.2 MAIN RESULT AND OUR TECHNIQUES
Our main result applies the framework in the previous section to the function constructed in Safran al. (2019) (see details in Section 2). Informally, we prove:'
Theorem 1.1 (Main result, Informal). Given the learner network defined in (I) with input dimension d. for any > O, we can choose layer widths as my = -pollyd (d, 1/e), m2 ((1) so that, with probability at least 1 - 1/ poly d, 1/E) over random initialization, running simple variant of gradient flow² reduces the loss f == Ex {(f_(z) - (a=)) /2 to within T = poly(d, 1/e) time.
This result shows that one can train multilayer neural network to learn the function RcLU ||a=]] that cannot be approximated by any 2-layer network. There are some technical details caused by the choice of a heavy-tail input distribution in Safran et al. (2019) which we discuss in Section 2.
To prove such a result, we first characterize the infinite-width dynamics (see Section 3). In particular, show that in the infinite-widde dynamics, the first layer will always compute multiple of ||>||| while the second layer will behave like a single neuron.
However, it is often difficult to discretize such an infinite-width analysis to polynomial-widhe network. The main difficulty is in the potential amplification of error in the network: if at the beginning, the first layer is 8-close to computing multiple of ||=||, this 8 value can potentially increase exponentially during the training process (Mei et al. (2018)). Given the large polynomial training time for dynamics, this exponential increase would not be acceptable.
To fix this issue, we partition the analysis into two phases, and for the time-consuming second phase, rely on decomposition of the loss function:
1 L: 1 E ((t))) 2 2
f(x))
E ((f((=) 2
+ w
(F(z) ( F(x))) (2)
Here F(x) is a multiple of || that is close to the actual first-layer output F(x), f(xx is the output of the network if the first layer is replaced by F(x) - that is, if the first layer actually computes a multiple of ||œ||| (see (5) for precise definition). The first term therefore characterizes the loss conditioned on perfect first-layer; while the second term characterizes the difference between the first-layer output and a multiple of ||=||| We show that the gradients of these two terms do not affect each other, least approximately. Therefore, we can view the training process simultane- ously doing two things: minimizing the loss given a good first-layer representation (reducing first term), and making first-layer output closer to a multiple of ||æ]|| (reducing second term). We believe such a decomposition highlights how the lower-layer in the neural network receives useful gradient information learn good representation for this particular objective.
1.3 RELATED WORKS
Algorithmic aspect of depth separation There have been other works that add algorithmic in- sights into depth separation. Allen-Zhu & Li (2020) showed that multi-layer quadratic networks can learn certain target functions in hierarchical way, which cannot be Iearned by any kernel meth- ods or shallow neural networks. Our work deals with more standard neural network architectures and target functions. A concurrent work Safran & Lee (2021) considers similar problem ours, where they show that GD with a certain three-layer network can learn the ball indicator which not approximable by any two-layer network. Conceptually the main difference between our results lies in the training dynamics the first layer of Safran & Lee (2021) is fixed while we train both layers. This leads very different training dynamics and proof techniques.
Overparametrized Neural Networks One line of works studied the optimization of overparame- terized neural network which couples the training dynamics to kernel regression with neural tangent kernel (NTK) (e.g., Jacot et al., 2018; Allen-Zhu et al., 201 80;8;; Du et al., 2018). However, it is shown
We say some quantity is (dly 1/c) if it is bounded by C(d/s) for some universal constant C 0 that may change across lines.
'Though gradient flow, strictly speaking, is not proper algorithm, it is common to use it as surrogate for gradient descent in theoretical analysis. See Appendix E for discussions on how to convert the argument to gradient descent one.
3

---

Published as a conference paper at ICLR 2023
that neural network behaves like kernel methods in NTK regime, and several lower bounds have been developed (Ychudai & Shamir, 2019; Wei et al., 2019; Ghorbani et al., 2019: 2020). Our training dynamics is not in the NTK regime as all the weights change significantly. Another line of works studied the optimization of overparameterized neural network in the mean-field limit (Mei et al., 2018; Chizat & Bach, 2018; Nitanda & Suzuki, 2017; Wei et al., 2019; Rotskoff & Handen-Fijnden 2018; Sirignano & Spiliopoulos, 2020). Chizat et al. (2019) showed that the parameters can move away from its initialization in mean-field regime and learn useful features, which is different from NTK regime. However, most of the existing works require exponentia//ininite number of neurons and do not provide a polynomial convergence rate. See more discussions in Appendix A.
Multi-layer mean-field Although mean-field analysis has been successful for the optimization of two-layer overparameterized network, it is not easy to extend it to multiple-layer network since the width of intermediate layer goes infinity. Many works have tried address this issue to generalize mean-field analysis to deep networks. See e.g., Nguyen & Pham (2020); Pham & Nguyen (2021); Araújo et al. (2019); Sirignano Spiliopoulos (2021); Fang et al. (2021); Lu et al. (2020); Ding et al. (2021) and references therein. Unlike most of the existing works, our multi-layer mean-field framework still has finite hidden feature dimension while the number of neurons can go to infinity to become distribution of neurons. See Section 1.1 and Appendix A for more discussions.
Mildly overparameterized neural networks Recently there are many works that consider the problem of learning certain target function with mildly overparameterized (polynomial size) net- work (Allen-Zi) Zhu et al., 201 8a; Allen-Zhu & Li, 2019; Bai & Lee, 2019; Dyer & Gur-Ari, 2019; Woodworth et al., 2020; Bai et al., 2020; Huang & Yau, 2020; Chen et al., 2020; Li et al., 2020; Wang et al., 2020; Zhou et al., 2021). In particular, these works are different from the typical mean- field analysis where usually the infinite-width network are considered, or the typical NTK analysis where neural network behaves like kernel method. Our work is in a similar direction, but need new insights to extend the discretization to our new multilayer framework.
PRELIMINARIES
In this section, we discuss the additional technical conditions for the input distributions in Safran et al. (2019), and how we deal with this in the training process.
Notations For a vector we let |m>| denote its Euclidean norm. We use a = + as a shorthand for the condition a E [b 1b-16 [cllcl,b- + |c]]. For a distribution μt, we write e E 14 for the condition e is in the support of μ.. Other notations we use are mostly standard. We usually use i and w to denote a first layer neuron, and (2) and (w2, b2) to denote a second layer neuron. Keeping two sets of notations for neurons is intentional. When
taking expectations over neurons, w1 and (w2, b2). When considering a single neuron, we use i1 and (12, r2). For vectors, we write : o/ || We will use E, as a shorthand for EnED when it is clear from the context. We also use u E as a shorthand for v E supp((4).
use
Target Function and Input Distribution
The target function we consider is f=() = a(1 - | |x])),
where R
R is the ReLU activation. To describe the input distribution, first, define
(p()) =
J2/2(2T R. [|=:]),, where R2 = -े (T(/2++1)) and Jn is the Bessel function of the first kind of order v. Let a, 8 > be the universal constants from Safran et al. (2019) (cf. the proof of Theorem 5). We assume the inputs x IR. are sampled from the distribution DD whose density is given by x + (VdBa) ( (Vd5ax). It has been verified in Eldan & Shamir (2016) and Safran et al. (2019) that this is indeed a valid probability distribution. Also, note that D is a spherically symmetric distribution. For more properties of D. see Appendix B.2. By Theorem 5 of Safran et al. (2019). no two-layer networks of width poly(d, 1/E) can approximate fa to accuracy e in (D). 3 This distribution is heavy-tailed in the sense that Eg<D []] is undefined. The choice of such heavy-tailed distribution is mostly required for proving the lower bound. Our training result holds for most reasonable spherically symmetric distributions.
[., (ffr)) T
d/2
Sttrctly speaking, the result in Safran et al. (2019) requires - O(1/d)). Even in that regime, our algo- rithm learns the function using poly(d) neurons, which is not achievable by any two-layer network, therefore it is stilla valid separation.
4

---

Published as a conference paper at ICLR 2023
Training Algorithm and Main Result We gradient flow with clipping MSE loss train a polynomial-sioe size network. We write the loss as
1 {(-(z)) - - -
C(u1, 2 anD
(3)
Define S(a:) (a) the neurons are given by
(ax) b2 (0'(w22(a)) b2)m²2)- One can verify that the dynamics of
01 E
(T (S(x) (010 x) || d' (m) x)m)]}
d2
= 2nD D
[IIRo [(f(()) - f(x)) (1z)) + +2))
(4)
i/2 E
(IR.. (a+(x) - (()))o F(x) + r2)]}
where I stands for the projection to the ball of radius R, and Re. = ((d), R., O(d)), R2 = (1) are the projection threshold. We add these additional gradient clipping because without them the gradients are not well-defined due to the heavy-tailed property of the distribution D. Note that gradient clipping is indeed widely used in practice to avoid exploding gradients (Pascanu et al., 2013; Zhang al., 2020). In fact, we believe optimization result without using gradient clipping would still be true for a general spherically symmetric distribution DD as long as it is more regular.
To initialize the learner network, we use (oi to initialize the first layer weights wi, (0, oσ) for the second layer weights W2, and choose all second layer bias by to be or, where 02,02 or some small positive real numbers. We initialize wi on the sphere instead using Gaussian only for technical convenience. We initialize the bias term to be small positive value so that all second layer neurons are activated at initialization avoid zero gradient.
Now we are ready to give our main result. It shows that gradient flow with a polynomial-sized learner network (1) defined in our mean-field framework can learn fx()) a(1 - [[=|]] efficiently, which is not approximable by any two-layer network (Safran et al., 2019).
Theorem 2.1 (Main result). Given the learner network defined in (I) with initialization described above and suppose we run gradient flow, assuming exists, on this finite- wnite-width network with clipping (4) on loss (3). Then, for any c O. we can choose
poly mylymy (d, 1/c), my = (1).
1/c), Ø2 = 1/ 11/poly., pdl (d)) or (1), Rv, = (d)), Rag = @())) and Rrg = 1/ poly,, o, (d,
((1) so that with probability at least - 1/ poly(d, 1/e) over the random initialization, we have loss C S within T poly(d, 1/e) time.
THE INFINITEWIDTHH DYNAMICS
Our proof consists of analyzing the dynamics of the indinite-width mean-field network and con- trolling the discretization error. In this section, we characterized the infinite-widhh dynamics. For ease of presentation, we pretend there is no projection and the gradients are well-defined in this subsection and defer the discussion on handling the projections to Section
First, note that both the input distribution D and the infinite-width network are spherically symmet- ric. That is, for any x, x Rd with || || ||x|||, II. the density/function value are the same. Any spherically symmetric satisfies h[[[=]]) g(æ)). For convenience, we will abuse notation to also use g IR + denote
Rd + R can be characterized by a function h 10. oc) + IR which
this function h.
Assuming that the distribution 14 of the first layer neurons is spherically symmetric, which true least at initialization, we can approximate the first layer with simple function using the following lemma. The proof of it can found in Appendix B.3.
Lemma 3.1. Let μ be spherically symmetric distribution. We have
| a(w x) =Cr Euwwy ||
D(d/2)Vd where Cr 2/TT((dd + 1)/2)*
E wmnp
||ج|||
Vd
Note that, - cc, we have Cr - 1/v 2m, so Or is universally bounded for all d.
5

---

Published as a conference paper at ICLR 2023
This lemma implies that, in the infinite- width limit, we have F(x) a ||>||| for some real 0, at least at initialization. This suggests defining the infinite- widhh approximation as:
Cr E |lw 11
a = Vd wimpi
F(x)= == a ||ح||| f(x) = E oWw + r2).
(5)
(wr (wa,
Note that (5) is well-defined matter μ1 is infinite-width not, though only in the infinite-widee case will one have F = F. Later in Section 4 we will show that F & 1' throughout the entire process in the discretization part of the proof.
For the infinite-wide network, spherically symmetric at time t, then no first layer neuron will change its direction and the change in norm is also uniform, i.c., it does not depend on the direction 8n (See Appendix B.4 for the proof.) As a result, Al will remain spherically symmetric. Formally, one can show that, for any spherically symmetric g Rd I., we have
can imagine that, thanks to the symmetry, as long as μl is
Cr
Cr Vd
(g(z)) (v x)} vd
E (g(z)
|
||e|||
and (gg x)2}
E (g(x)) | v
where è // ||-||| Again, the proof of these two identities can be found in Appendix B.3. Apply these identities to 81 with g and one obtain
2Cr
d1 vd E (S(x) ||]||]] vi.
As result, Yn is always uniform distribution over some sphere. Moreover, we have
da dwi 40% E (5(x)
4Cr (S(x) |
E ||]||]]
201 w|
wi ow, di
vd
This implies that the dynamics of the first layer can also be characterized by a alone. This reduces the dynamies of the first layer a single real number a. That is, the outputs of the first layer depend only on a and æ, and the dynamics of a also depend only on a instead of every single neuron w). case. In other words, we do not need to look at the actual dynamics of wi in this infinite-wite We will later show that the spread of the second layer is always small, hence the second layer can be approximated by a |x|| + a (1z2 || + b2) where (w2, b2) = E(w2, b2). Combining these observations, one can characterize the dynamics of the entire network using three quantities: o, and b2.
We close this section with another interpretation of F. which is going to be handy in Section 4.2. Since we know that, in the idealized case, F should be spherically symmetric. Hence, it makes sense to define the "idealized" F be the average over the sphere, that is, F(xx) = E| F(x'). Note that in Lemma 3.1, the expectation is taken over the neurons while here it is over the inputs. However, similar to the proof Lemma 3.1, one can still show that
|w/| ow x) = Cr Ewons [
E x E 8d-- F(x')
||||||
a
||=|||
4m x' |
Vd
In other words, these two derivations are equivalent. In some sense, this means that the infinite-width network can be interpreted as a symmetrization the actual finite-width network.
DISCRETIZING THE DYNAMICS WITH POLYNOMIAL-SIN NETWORK
In this section, we show how to discretize the fhfnite-width dynamics to get our main results. See Fig. 2 for simulation results. As we can see, even though the network has a finite width, at any time step, the function f(x) is close to a function of the form + ob22 @2al(æ1)) and throughout the training the second layer weights are well-concentrated.
Let 62 == (12,))) (122, r2) - (vg, r5) be the spread of the second layer, we will split the training procedure into two stages. Recall that (w2, b2) := (( be) (W2, b2). Stage 1, Wh will decrease to (dly(d)82. We show that after this condition is true, the projection operators in (4) can be ignored (that is. the corresponding terms never exceed the thresholds, see Lemma 4.1). In Stage show that the network can fit the target function in polynomial time.
As in the standard mean-fiel arguments, we rescale the gradients by m so that it does not go to 0 as co. In most cases regarding gradient calculation, this is equivalent to using the formal rule O F. g(w) (rg(r).

---

Published as a conference paper at ICLR 2023
6-D0
0.6
1X1, step=0
0.04
0.4
function value
AXl, step=1000
0.3
fxd, step=3000
loss
0.03
fid, step=7500
0.0
V2. step=0
fx). step=15000
D. step-0
0.02
-0.2
V2. step=1500
0.1
-0.4
6. 1tep==1000
snd - </e
0.01
-0.6
v2. step-3500
5. 3t0p=3500
-0.8
5000
20000
15000
20000
steps
|||||
Figure 2: Simulation results. The left figure shows the loss during training. Each vertical dashed line corresponds to time point plotted in the other two figures. The center figure depicts the shape of f at certain steps. The right figure shows the values of the second-layer neurons certain steps. One can observe that f f indeed holds, and the second layer neurons are concentrated around (02, b2). which matches our theoretical analysis. Simulation is performed on finite-width network with widths m1 = 512, ma = 128 and input dimension 100.
4.1 STAGE 1: REMOVING THE PROJECTIONS
Our first step shows that after a short amount of time in training, it is OK to ignore the projection operators (4). To see why the projections can be ignored in certain circumstances, first note that f f, second layer neurons concentrate around their mean. 82 ((1) and W2 < O. then f= ( ||^||| + b2) vanishes outside [||z||| S O(1 ///za])) whence the gradients also vanish for those large æ. Meanwhile, by upper bounding the norm of the gradients, one can show that order for the projections to be triggered, it is necessary for ||ж=|| to be large. As result, when f decreases sufficiently fast, f fxx) will reach O before ||ж||| becomes too large. Formally, we have the following lemma, whose proof can be found in Appendix C.
Lemma 4.1. Choose the projection threshold Re, = (d). Rog (dd)) and Ryg = O(1) in (4). Suppose that a = O(1 /d). Then, the projection operators in 12 ún and i2 will no longer be activated if all second layer weights are nonpositive, - ((1)8g for some large constant, and -w2 2 ((1)/Bry// for some large constant, respectively.
Based on this lemma, we further split Stage I into three substages. We define Ti.1 to be the first time all second layer weights become negative, and T1.2 and Ti,3 the first time |ūby] becomes O (d))2 and ((1/Rzz), R, respectively. They represent the end time of Stage 1.1, 1.2, and 1.3, respectively. We require [W2) to be (d))o2 instead of (1))o, at the end of Stage 1.2 so that the starting state of Stage 1.3 is more regular. By definition and Lemma 4.1, after each substage, one more projection can be ignored, and all of them can be ignored after Stage 1.
The main lemma of Stage is as follows. Recall that Roy Rug Rr, are the clipping thresholds Lemma 4.2 (Stage 1, informal). Define the end time of Stage I as Tı := inf 2 0 -W2(t) = C1/ / Rwy) } for some large constant Ct. Under the assumptions of Theorem 1. we have Ti S poly(d, 1/)) and the following conditions hold throughout Stage 1.
(a) Approximation error of the first layer. For each V1 μi, both the tangent movement and the radial spread can be controlled as [|ō (t) o (0)] S (t)(() and ||e, 11 = (1 = i (L))
E u. 11 where 5(1) and 8(1) are two processes which are always small.
(b) Spread of the second layer. For any (22, (122 r2) μ2, (1 r2) (1/, r2)11 is small.
(c)
Regularity conditions. T2 +(1) for all (12,T2) E u2, |جقا O(1/R..) O(1/d)) and = ((va Rw, @11/2155)
The first two conditions mean the approximation f(x) x (wza ||>||| Stage I and the third condition describes the shape of f in Stage 1. To maintain these conditions, use the so-called continuity argument, which can be viewed as a continuous version of mathematical induction. See Appendix B.1 for explanations of this technique.
+ b2) is valid throughout
7

---

Published as a conference paper at ICLR 2023
With the approximation F(x) a ||ق||| and the fact f(z)) + r2) f(x) for most æ, can rewrite the dynamics of 222 as
1/ E R,,, -
- f(z)) [[]]]] [121]
Since much flatter than f., f is still ((1) when f. vanishes because ||>||| 2 1. As a result, the RHS is always negative. In fact, show that it is (a log d). Recall that Ti.2 is the time [ reaches ((d5)). If 82 roughly remains constant, the time needed for Stage 1.1 and Stage 1.2 proportional the initial 02. Then, we make the initial 82 small by selecting small enough This also helps control the movement of vi and 12 in Stage 1.1 and Stage 1.2 as their dynamics
depend on /w2l-
One also needs to show that 82 cannot increase too much during Stages 1.1 and 1.2 to maintain the approximation f(x) ss ())))(()) + b2). Intuitively, this is because for inputs with small || the gradient ve (x)) does not depend on (22, r2) itself; for the inputs with a large norm, they cannot contribute too much to the gradient due to gradient clipping. As result, the dynamics of 02 are approximately uniform in Stage 1.1 and Stage 1.2, whence the distance between different (U2, r2), (1/2 r22) stays small.
The same method does not work in Stage 1.3 as now the target value of úh no longer depends on 82, and we need finer analysis for the first layer. Recall that, after Stage 1.2, the projection in é can be ignored. Therefore, we can decompose úi along the radial and tangent direction
ú1 RRd((1) Tan((1) (01, 01) (I 615,] )
2 2 (5(z)o0) x)} + || lI (S())o' x) 8n 0 )a}
x
Then, write S(x=) = ( related f- f is essentially what one should expect have in the indtnite-width dynamics. For those terms, the radial movement is uniform and tangent movement is 0. Then, we bound terms related to f
f()))
- f + (f(x) [2 The terms
using the radial spread and tangent movement of the first layer to obtain O(1) (1()) o1.77 (cf. Lemma C.16). Though, with this bound, the error can de (0 I,T 2 22.6
d
grow exponentially fast (exp(t/d this is sufficient since Stage 1.3 only takes (dd time.
4.2 STAGE 2: FITTING THE TARGET FUNCTION
The goal of Stage 2 for the gradient flow to converge point with loss at most in polynomial time. The main difficulty in this stage is that we need to bound the approximation error of the first layer more carefully, as Stage 2 is potentially long and the brute-force estimations used Stage is too loose towards the end of training. We write F == F/a and measure the approximation error using Fls - 1|l and | - 11- 1 Strictly speaking, for the L eгror, we only consider those x with |0||| < 0(1/ ) poly since otherwise it can be ill-defined. This is valid because, as we have discussed earlier, f vanishes for large æ. In Stage 2, Egg always means El ( [0sa)) and, for the simplicity of presentation, we usually do not explicitly state this. The main result of Stage is as follows.
Lemma 4.3 (Stage 2, informal). Define the end time of Stage 2 T2 = inf(l Ti L :). Under the assumptions of Theorem 2.1, we have T2 - Ti I poly(d, 1/E) and the following conditions hold throughout Stage 2:
(a) Approximation error of the first layer. Both ||F ||-II]| Lr and |F small.
111
1 are
(b) Spread of the second layer. (azr)))) (1(22, r2) - (6))l does not grow.
(c) Regularity conditions. The shape of f is similar to the one shown in Figure 2.
As we mentioned, the main technical challenge to bound the approximation error of the first layer. The overall strategy is first show that, in Stage 2, the L error barely grows and then show that, as long as the L error small, the L enror can also be controlled. Unlike Stage 1, [ūza| is fairly large in Stage and, result, the first layer can receive some signal from the loss function.
8

---

Published as a conference paper at ICLR 2023
Intuitively, this signal should push the first layer become closer to a multiple of ||=||| as that is what the global optimal solution would do. Formally, we first show the following approximation:
C
2 E
in the sense that the gradients Ve, of both sides are approximately the same, where f(x) is defined as (2 ((r) The first term of (6) measures the distance between the target function and the wnftttte-width network and the second term measures the approximation error of the first layer. In some sense, one can view this formula as a bias-variance decomposition for discretizing mean-field networks.
With this approximation in hand, we then show that, thanks to the 2-homogeneity of F, the first term, after certain normalization, does not affect the approximation error of the first layer. Meanwhile, since we are following the gradient flow, the second term can only decrease the approximation error.
To establish (6), we first decompose the loss function as
1 - (
1 2 {ff(x) f(x)) + (ff(())
f(x))
2
=: =: + +2+
We claim that L2 approximately the second term of (6) and the third term is approximately 0 Let X, be the largest spherically symmetric set on which (x) + r2 > 0 for all (12,72) E μ2. We show that those z outside X2 contribute little. Therefore, we can rewrite L2 as
E (w2F(xx) + b2)) ) wr.b2
C2 ~
E (wg 102
( b2)
2x
~ w6 E (F(x)) - F(z))²} 2 W2 F. (J.(=)) f(=))) F(xi)) Recall from Section 3 that F(x) = Ex F(x). With this in mind, one can casily verify that, for any spherically symmetric function Rd R, Ex (g(z) Ex { { Setting g f- fx) f(x) gives L3 x Combine these two estimations together and obtain (6). Provided that the 2 error is always small, we show that, up to some higher order terms,
-F()))
2 XI
Similarly, can rewrite La La
F()) S -
Vi E Sd-11
dt
In words, the change of de small long as we choose sufficiently large mi so that F(x))zegs-: is close to at initialization. This should not be surprise since, after all, in the infinite-width dynamics F F( 1. The formal proof of the above argument can be found in Section D.2.
F(x) can be bounded by the 1.2 error. Hence, || 11| is always
Given that the approximation error can be controlled, one can then derive convergence rate using the wndthite-width dynamics. See Section D.3 for details.
CONCLUSION
In this paper give new framework for extending mean-field limit to multilayer networks, and use this framework to show that three-layer networks can learn a function that is not approximable by two-layer networks. There are still many open problems: for the current objective the loss is spherically symmetric so the first-layer neurons don't 't move much tangentially, what if the function instead o || PParl) []) where Ps is projection to some unknown subspace? How about functions that require an intermediate layer of size more than !? Can one generalize the saddle point analysis deeper networks? We hope this work will be starting point for understanding how deep neural networks can learn useful features.
For the ease of presentation, here we are talking about the function values instead of the gradients. Strictly speaking, this is incorrect as the function value being small does not necessarily imply the gradient is small. The ideas, however, are essentially the same. See Section D.2 for the actual proof.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work is supported by NSF Award DMS-2031849, CCF-1845171 (CAREER), CCF-1934964 (Tripods) and Sloan Research Fellowship.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv:1905. 10337, 2019.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.04413 2020.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang, Learning and generalization in overparameter- ized neural networks, going beyond two layers. arXiv preprint
2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: 181103981 2018b.
Dyego Araújo, Roberto I Oliveira, and Daniel Yukimura. A mean-field limit for certain deep neural networks. arXiv preprint arXiv: 190.00996 2019.
Yu Bai and Jason D Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. arXiv preprint arXiv:1910.016/ 2019.
Yu Bai, Ben Krause, Huan Wang, Caiming Xiong, and Richard Socher. Taylorized training: Towards better approximation neural network training at finite width. arXiv preprint arXiv:2002.04010, 2020.
Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits neural representations. arXiv preprint arXiv:2006. 1.:000....4..... 2020.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in neural information processing systems, pp. 3036-3046, 2018
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pp. 2033-29929990 204-2993,, 2019.
Amit Daniely. Depth separation for neural networks. In Conference on Learning Theory, pp. 690- 696. PMLR, 2017.
Zhiyan Ding, Shi Chen, Qin Li, and Stephen Wright. Overparameterizzatio of deep resnet: zero loss and mean-field analysis. arXiv preprint 1rXiv:2105.14417, 2021.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arX1v:1810.02054, 2018.
Ethan Dyer and Guy Gur-Ari. Asymptotics of wide networks from feynman diagrams. arXiv preprint arXiv: 11304, 2019.
Ronen Eldan and Ohad Shamir. The Power of Depth for Feedforward Neural Networks. In Vi- taly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 907-940, Columbia Uni- versity, New York, New York, USA, June 2016. PMLR. URL http:::/tc/cceeehetttte mlr. press/v49/es elann 6. html.
Cong Fang, Jason Lee, Pengkun Yang, and Tong Zhang. Modeling from features: a mean-field framework for werrpparameterized deep neural networks. In Conference on learning theory, pp- 1887-1936. PMLR, 2021.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. In NeurlPS, 2019.
10

---

Published as a conference paper at ICLR 2023
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? arXiv preprint WrXiv:2006.134000 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016. doi: 00.1199/VPRR.201.9900
Jiaoyang Huang and Horn--Tzer Yau. Dynamics of deep neural networks and neural tangent hier- archy. In International Conference on Machine Learning, pp. 4542 4551. PMLR, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
I. Krasikov. Uniform bounds for bessel functions. Journal of Applied Analysis, 12(1):83-99) 91, 2006. doi: doi: 15..155//AAA.206..55. URL https: http:::/dooooooooo 1tt.://...../1....//.......... 1515/JJA, 2006. 83.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on Learning Theory, pp.
PMLR, 2020.
Shiyu Liang and R Srikant. Why deep neural networks for function approximation? In 5th Interna- tional Conference on Learning Representations, ICLR 2017, 2017.
Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean field analysis of deep resnet and beyond: Towards provably optimization via overparameterizztion from depth. In In- ternational Conference on Machine Learning, pp. 6426-6423 6436. PMLR, 2020.
Eran Malach and Shai Shwaav-Shwartz. Is deeper better only when shallow good? Advances in Neural Information Processing Systems, 32, 2019.
Eran Malach, Gilad Yehudai, Shai Chalev-Schwartz and Ohad Shamir. The connection between approximation. depth separation and learnability neural networks. In Conference on Learning PMLR, 2021.
Theory, pp.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665-E777) 2018.
Phan-Minh Nguyen and Huy Tuan Pham. A rigorous framework for the mean field limit of multi- layer neural networks. arXiv preprint arXiv:2001. 2020.
Atsushi Nitanda and Taiji Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv preprint ar 1712.071 2017.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on International Conference on Machine Learning Volume 28, ICML' 13, pp. 1I1-1310-111-311 JMLR.org, 2013.
Huy Tuan Pham and Phan-Minh Nguyen. Global Convergence of Three-layer Neural Networks in the Mean Field Regime. In International Conference on Learning Representations, 2021. URL
https: /wwpeeeeeeveeeeeeeeeeeeeeeeeeeee
.nt/ forummdddKvyxFFF
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but but not shallow-networks avoid the curse of dimensionality: a review. Inter- national Journal of Automation and Computing, 14(5)5003-519, 2017.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29, 2016.
Grant M Rotskoff and Eric Vanden-Eijnden. Trainability and accuracy of neural networks: An interacting particle system approach. arXiv preprint 1 009500 2018.
Itay Safran and Jason Lee. Optimization-basee separations for neural networks. arXiv preprint arXiv:2/ 12..22/22.229333 2021.
11

---

Published as a conference paper at ICLR 2023
Itay Safran and Ohad Shamir. Depth- Width Tradeoffs in Approximating Natural Functions with Neural Networks. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th Interna- tional Conference search, pp. 2979-2987. PMLR, August 2017. URL wtt.https://proceeee v70/safres 1araaalaa.. 7a html.
Machine Learning. volume 70 of Proceedings of Machine Learning Re-
/ ppwceedooeeeeeopooooooooooooeece
mmlr .press/
Itay Safran, Ronen Eldan, and Ohad Shamir. Depth Separations in Neural Networks: What is Actually Being Separated? In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Shcroy-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 2664-2666, Phoenix, USA, June 2019, PMLR. URL http:// htttpppp/rpoooeiiggsss. mlr. www.ppeessvveee v99/ safsaaaarannln/ 9a. html.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis neural networks: central limit theorem. Stochastic Processes and their Applications, 130(3):1800-1852 2020.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of deep neural networks. Math- ematics of Operations Research, 2021.
Terence Tao. Nonlinear dispersive equations: local and global analysis. Number no. 106 in Confer- ence Board of the Mathematical Sciences regional conference series in mathematics. American Mathematical Society, 2006. ISBN 978-0-8218-4143- OCLC: ocm65165500
Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pp- 1517-1539. PMLR, 2016.
Gal Vardi and Ohad Shamir. Neural networks with small weights and depth-separation barriers. Advances in neural information processing systems, 33:19433-19442, 2020.
Luca Venturi, Samy Jelassi, Tristan Ozuch, and Joan Bruna. Depth separation beyond radial func- tions. Journal of Machine Learning Research, 23(122):1-56, 2022.
Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond lazy training for over-parameterized tensor decomposition. arXiv preprint arXiv:2010.11356, 2020.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems, pp. 9712-9777 9724, 2019.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pp. 3635-3673. PMLR, 2020.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv:1904.000 006877 2019.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Rep- resentations, 2020. URL https: : opwnreveeveeeeeeee/e/eeeee net/ Btte:/Errummii-BBuueee
Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over-paree ever-parameterized two- layer neural network. In Conference Learning Theory, pp. 4577-4632. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2023
A MULTI-LAYER MEAN-FIELD NETWORKS
In this section, first briefly review existing theories of two-layer mean-field networks, and then introduce our framework for multi-layer mean-field networks.
A. TWO-LAYER NETWORKS AND PERMUTATION INVARIANCE
two-layer network f of width m can usually be represented by
f(x: W. a)
1 a (Wx) m
Σ awo -2).
where W [Rmd is the weight matrix of the hidden layer and R the output weights. Let μ be the empirical distribution of {aa, w C Rd+1, Then, we can write
f(z: p)
E (oo(wxx)) (a,w)ry
By allowing yu to be an arbitrary sufficiently regular distribution over Rd4, we obtain a neural network, represented by (8), that contain infinitely many neurons.
To describe the gradient flow of this infinite- width network, it suffices to assign a vector field to R++1 that describes how each neuron (a, w) gd+ should move time t. One simple heuristic way to do so is to first compute the gradient in the finite-width case and then replace summations with expectations in (8) and treat the gradient vector field. We now illustrate the idea under realizable setting and with the MSE loss
C C=
The theory can be generalized to much more general settings and can be formally justified using the theory of Wasserstein gradient flow. Readers can refer to, for example, Chizat & Bach (2018) and Mei et al. (2018) for details. For finite-width network (7), the gradient of L w.r.t. neuron (ake wx) is
m 0e L = -E((( f(x; W. a))o x)}
m V w. L = ((f.(x)) f(x; W. a)) x)x}
Replace f(x; W, a) with f(x; pi), treat (ax, wx) generic neuron, and obtain vector field V R2++1 Rd+1
-
w) w) (1.(o) (
alw ao'(w x)x
At each time f, we update the neurons in f according to -
One of the most important properties of this mean-field formulation is that it factors out the permu- tation invariance of neurons. That is, we can permute (a1, wi)...., (am: Wm) without changing the output of the network. However, when we treat training as optimization problem over the space of (a, W), i.e., R. x Rexd permuting (a,, w;) entirely changes (a, W). On the other hand, if we describe the network using distribution μ over IR+11, then it is automatically permu- tation invariant. Note that this is not restricted to infinite-width networks. When we choose μ to be an empirical distribution over finitely many neurons, recover finite-width network without breaking the permutation invariance.
'Here, w, E d means the i-th row of W. Later we will notations v., a, to denote i-th row or column of the corresponding matrix. Whether it is row or column can be easily inferred from the dimension. The general rule is that if V DDx where represents the number of neurons, then E TR. is i-th column, and if W RD then wy E R the i-th row.
13

---

Published as a conference paper at ICLR 2023
A.2 MULTI-LAYER MEAN-FIELD NETWORKS
Unfortunately, the above strategy cannot be directly generalized to multi-layer networks. Consider the three-layer network
1 -a'' T (Wzh(a; h(2; Wi) -===--o -o(()x)
f(x; a, W2, Wi)
112
m1
where a E mR W2 E R
W1 E Rm xd. One can still write
m2
fl; 22, Wi)
awo h(;; Wi))
E 3
{oo h(æ; Wi))}.
m2
However, now H2 is distribution over Ri and m - oc, will become distribution over R which is not readily defined. One way to resolve this issue is to view W2 as function from handle the infinite-widhh case by replacing the index sets [m2]. [mi] by two general index sets 12, I that can potentially be uncountable. For example, we can choose I l R. This is the strategy employed by Nguyen & Pham (2020). (See Pham & Nguyen (2021) for more accessible version of this paper.) The drawback of this formulation is that, with the introduction of index sets, the permutation invariance is no longer factored out. Though with this formulation, it is still possible to obtain global convergence results for infinite- width networks, it become less useful when we want to analyze a finite-width network as becomes essentially the same the usual matrix formulation.
[m2] [mi] IR and then generalize
We now present a formulation that does factor out the permutation invariance of neurons, and is built upon composing sequence of vector-valued two-layer networks. As first step, we consider a two-layer network with D-dimensional outputs:
A. W) A
m (Wx),
where A E Dxm and W E mxd For each index E [D], we still have
Σ awso x) f((: = m ==1
{ao x)};
(a.w)~uu
where μ4 is the empirical distribution of {(ar,j, w;)]semm C Rd+1, Range over and we obtain the output vector of this network. For two-layer networks with scalar outputs, in order to obtain its mean-field counterpart, it suffices to allow j to take a general distribution over R x Rd. This, however, is not the case for networks with vector outputs the W parts of μ4; coupled. Hence, we need to additionally impose the constraint that all (p:) (ps)sE[D] share the same second margin, that is, #1; = μw for some distribution μ' over dRd and all E [D). where IR x IRd + Rd is the projection that takes (a, w) to w. Intuitively, this condition says that they share the same first layer weights W. We formalize this idea in the following definition.
Definition A.1. Let (D))SE(D) be D sufficiently regular? distributions over R x Rdd We call (pa). an admissible configuration of dimension (D,d) if there exists measure μo over Rd such that #2 = pw holds for all i e [D].
Note that here, by a neuron, we mean a (D + d))dimensional vector (a)...., aD w7). In the finite-width network (9), this corresponds to row in W and the corresponding column in A. This point of view is important when deriving the infinite-width gradient flow since, as the two- layer case, the vector field at the position of certain neuron can only depend the other neurons as a whole.
Remark.
To complement the discussion, here we consider the problem that, given an admissible infinite-wine width configuration (D)) how to obtain finite-width network with m neurons. For vallur
"Our focus is on factoring out the permutation invariance and, in this paper, essentially all distributions are empirical distributions over finitely many neurons, with respect to which the integral is just summation and is always well-defined. We leave the work of figuring out specific regularity conditions future works.
14

---

Published as a conference paper at ICLR 2023
mean-field network characterized by μ., it suffices to generate samples from μ. For vector- valued network, the procedure is slightly different. We first sample a weight vector w from the shared margin Pw- Then, for each i [D], we generate real number a, conditioning gives us a neuron (a1,..., ODD w) E IRD x Rd. Repeat this procedure m times and we obtain a finite-width network with neurons.
This
We formally define two-layer vector-valued mean-field networks as follows.
Definition A.2. Given an admissible (μi)iE(D) the two-layer vector-valued network it defines
F(x: ;i,...,,pp)) = (Fi(a; (app)==(F((:::))) Fb(o:
(10)
where
pa) =
E
{ao x)}, Vi e [D).
(a.w)mpp
Now, we are ready to define a multi-layer mean-field network. Basically, a multi-layer mean-field network is composition of sequence of two-layer vector-valued networks (10).
Definition A.3. Let L 2 1 be an integer. Let D(")...,
be a sequence of positive in- tegers and put D = d. For each I E [L]. let (1) (14") )ean) be an admissible configuration of dimension (D(t), D(t-1)). The T--layer mean-field network f defined by the configuration
= seTDA))eeL)) is defined recursively as
f(x: θ) FF()) (x:; O),
F (x: + F (Fll11) (x; 0):11 pT.). 4A 1,
(11)
(x; θ) == x;
where the two-layer mean-field network given by (10).
Example As example, consider the case L 3 here. In this case, the finite-width network corresponding to (11) is
1 (21() mi
f (a; A2, W2, A1, Wi)
A20
W₂
m7
which is exactly the usual multi-layer network used in practice except the normalizing terms 1 1/m2, 1/mi and an additional matrix A E DR Xm,, This matrix compresses an dimensional feature vector D dimensional one, where D2 is an integer that does not go to co. Is reminiscent of the bottleneck structure used in ResNet (He al. (2016)).
Remark. Note that this formulation is indeed invariant under permutation of each layer's neurons.
However, does not factor out all permutation invariance of deep network. For example, one can permute the columns of W1 and adjusting A,, W2, A₂ accordingly without changing the output of the network. In some sense, this corresponds to permuting the entires the hidden feature F(1), We believe it is not necessary useful factor out this symmetry since, after all, even in the two-layer case, we do not permute the entries of the inputs æ.
Finally, we consider the problem of formulating mean-field gradient flow so that matches the usual gradient flow. The idea is simple: We compute the gradient in the finite-width setting and then replace summations with integrals. For the ease of presentation, we consider three-layer network and the MSE loss. Again, this framework be easily generalized deeper networks and other loss functions. We write
f(x) = f(a; W2, V1, Wi)
T (W2Fla;V, V1 Wi)),
m2
F(x) = F(x: VI Wi) = Vio(Wiz),
-= Cla, W2, V. Wi) 2
((f((x) s(a;a We, V, Wi))3),
15

---

Published as a conference paper at ICLR 2023
where E R' W2 R V1 E R Pxmi, W1 Rm We have
m1 V C E (a) l (a)))o(w2, F(z))),
Wi e [ma]]
m2 V 22 - E ((f f(z))a (w2s F(x))F(x))
vi [mal.
mg
-1n V Vv. - E
(f+(z) f(x))
a F(z))u2
Vi E [m]]
m1
1
m2
-m1 V wn C E
(f.( - -(x)))
Vi E [m]] (w23 F(x)) (122,, v1 d' o'(1, x) }.
m2
Replace summations with integrals and we obtain
alw2 . F(x))
V (a, E (f.(x)) f(x))
ao ao'(w2- ((x))
-V (V1om)) E (f=(z)) f(x))
E (a.
caol(uz F(x))
owwi w)w (102, 01) (ww x) }} (12)
Namely, at each step f, we update the second layer neurons (a, W2) with - (a)w)) and first layer neurons (U1, wi) with V (ith- (w)) Note that, unlike many other multi-layer mean-field frameworks, we do not introduce any notion of paths. The dynamics of each first layer neuron depends on the second layer as a whole as we take expectation over μ2 in (12). The same also true for second layer neurons. In some sense, the additional matrix Vi decouples the dynamics of the first and second layer neurons.
B PRELIMINARIES
B.1 INDUCTION HYPOTHESIS AND CONTINUITY ARGUMENT
We extensively use the continuos-time version of mathematical induction in our proof, which is also called the continuity argument. We briefly discuss this technique in this subsection and explain some conventions we employ in the writing of the proof. One may refer to, for example, Chapter 1.3 of Tao (2006) for details.
Similar to the discrete-time induction argument, the goal is to maintain a collection of conditions, which we call the Induction Hypothesis, throughout a period of time (cf. Induction Hypothesis C.2 and Induction Hypothesis D.1). There are mainly two types of conditions.
The first type has the form "certain process A, bounded by another process B₁". In the proof, A, is usually the eтror we want to control and B, an non-decreasing process representing the cor- responding upper bound. To maintain this type of condition, suffices show that A, I B, at initialization and Á, < B, as long as the Induction Hypothesis is true.
For this type of condition, usually we also have an upper bound for B,, say. B, < B The most rigorous way to maintain these bounds to argue by contradiction. Let T be the minimum between the time Ti the process ends and the time T2 this bound first get violated. By definition, the Induction Hypothesis holds for any / < T. Using the Induction Hypothesis, one can then derive an upper bound T' Ti, which then leads to upper bound on T. Then, all we need to show is that By is smaller than Bx so that is attained by T₁ instead of Tz. For the case of presentation, for this type of conditions, instead of arguing by contradiction explicitly, we will simply show that, provided that the Induction Hypothesis is true over [0, Ti). then By; & Ba holds.
The second type has the form "certain process C₁ is bounded some value D Here, C. is usually some quantity related to the shape of the learner function such as Wy and a. In order to maintain, say, C, < D, we show that when C, E [D E, D]. we have Ć < O. This implies that, as long as Ct is continuous, this implies C₁ never reach D.
16

---

Published as a conference paper at ICLR 2023
B.2 PROPERTIES OF THE INPUT DISTRIBUTION
In this subsection, we derive some basic properties of the input distribution that will be useful in later analysis.
The following lemma gives the distribution of || and its tail bound.
Lemma B.1. Let x and let |D]] denote the distribution of ||=|| We have
d J2 (2T (2TTRaRB O
1
IDD| (r)
Vr > O.
12
As a result, we have the tail bound: for all R > 0, a
2 R] S (1/RR)
We now give some regularity conditions on the input distribution that will be used in our proof. Roughly speaking, it shows that the distribution is heavy-tailed and still has large enough mass for ||a||| E [0, 1]
Lemma B.2 (Regularity conditions input distribution). For the input distribution D, we have
(a) |a ||-||| ((1)
(b) E fz) (2()).
(c) E | | 2 O(log d) and P[allispoly(a)) ||ق||| S (log(d)).
Proof of Lemma B.I. Recall that the input distribution of æ is
(Sava) 2Baxxx dæ),
where a, B are the universal constants from Safran al. (2019) (ef. the proof of Theorem 5),
Rd ||==|]
((x))=
Ja [=]]),,
Rdd
=(v7) (Lemma 5 in Eldan & Shamir (2016)) and J. is the Bessel function of the first kind of order. Note that since yp only depends on |æ>] we can abuse the notation use <rr) to denote (xx)) with ||a=|| =r.
Ra =
For any test function
R + IR, we have
E [[([==>)>]| J (([æz]]) (Sava) (B dz)dd xnD
-Sava) Sa-1 1 ((r))2 ar dr.
where Sa-1 4/2 (dd/2) is the surface of unit ball gd-1, Therefore, we have the density of ||||| with | = ri
2/2 (Bava)
Rd (Bavdr)
(Bava)
d Sa (2 (2m Ry dr dr
T(d/2)
22 (2TRBBaVdr)
=0
where the fact that (2( 0(1/ (Krasikov (2006)). Then, it is easy that P[[|=|| 2 R) = O).RR..
17

---

Published as a conference paper at ICLR 2023
Proof of Lemma B.2.
(a) is easy see the upper bound
|
S 0.99.
.0.99
For lower bound, note that E |an
$0.999
|
0.1 I |||||| S 0.99). Hence, it suffices
to lower bound P(.1 s ||>|||
0.99).
We have
0.99
d
P(0.1 < ||>|||
I 0.99)
d/2 (2 RaSavarddr
0.1
Jo.2 f
1.98x
20(1)
(r)2(r)dr
-0(1
where in the last line Lemma 23 in Eldan & Shamir (2016). This implies that E |all0000 ||œ||| = (1)). Together with the upper bound, we have E a| 50.99 ||>|||
(1).
(b) We have
E far))
= E [1 |=||]
>
E
1 - |
|
||
$0.99
2 0.01 |[ < 0.99) 2 0.01 S || S 0.99) = 0(1),
where the last inequality use the calculation in (a).
(c) The upper bound follows directly from the tail bound || (r) - 0(1/r²). For the lower bound, recall the density of || when || is { (2x RaBav For notational simplicity, put RD = ((d). We have
Rp
E
|
=
(2222(2 Ra Jr)dr
|||| RR
PaRaRoDava
(r)
2n Ra.aavdd
20(1) 1222(r)dr,
where is large enough constant.
To lower bound E |,||| it suffices to lower bound scol (r))( In the following, we will lower bound it by following similar calculation in Lemma 23 in Eldan & Shamir (2016). From the proof of Lemma 23 in Eldan & Shamir (2016), have for
22 (z) N 2 cos?
(- (-(d+)
(d 1)TT
+ fd,
3r 3x-
4
where fa,x is quantity that depends on d and and satisfies 1.3 2 fax 2 0.85.
Then, we have
retf
f
ped?
2
(- (d (d+ + 1)m
f pod?
12)2()ddz
cos?
+ sa dr
3x 22
cd
π
4
cd
2
rdta
(d + 1)m
3(d - 1) cdl
cos2
+ fd.10))
dr
π
Note that in the proof of Lemma 23 in Eldan & Shamir (2016), it shown that
d²
--1
dr (fa. = v1 1-
<
4x
18

---

Published as a conference paper at ICLR 2023
Then, since 1.3 2 fa,z 0.85 we have
2
cdd
(d + 1)
1)T
cos
+ Sa.a dx
cd
4
rode
0.85
(d + 1)
cos?
+ fd.200
Ox (fd.o))dz
od
f
4
0.85
(d+ 1)st
cos?
+ dz
faleaed
4
1.7
(..850de
(d + 1)TT
cos2
+ dz.
π
1.3ed
2
Then, using integration by parts and the fact that cos (z (d+++//+/// = ( (d + 1) 22)/4)/4 we have
0.85cd
(- ()TT 1)TT
cos²
+
dz
1.3cd
6 +
1
sin
(2z
(d+1)x)
))
0.85ed
0.85ed
( + 1 4 sin(2z 2
[d+1)s
4
dz
22
1.3ed
1.3ed
1 0.85cd2
0.85ed2
1
+
4z de
1.3cd
1.3cd
1
1
0.85cd
In
(lllg d).
0.85cd2
1.3cd
1.3cd
Therefore, we have
(z) = 2(log d),
ed
which implies E ((ll) ||=||| = 2(log d).
B.3 PROPERTIES OF SPHERICALLY SYMMETRIC FUNCTIONS AND DISTRIBUTIONS
In this subsection, we give some useful proprieties of spherically symmetric functions and distribu- tions. These will be useful tools in our later analysis. Basically, these lemmas allow us to disentangle input æ and neuron a when considering integration against spherically symmetric function. Lemma 3.1. Let μ be spherically symmetric distribution. We have
|w]l [(w x)) Cr Ewnn ||0|| ||ج||| where Cr 2VTT(((d 1)/2)
r(d/2)Vd
E wmi
Vd
Note that, as xc, we have Or + 1/v27, so Cr is universally bounded for all d. Lemma B.3. For any spherically symmetric g: Bd IR and Rd, we have
Cr T.. - m)) Vd m
T (g(x)a( m
(g(x)) ||x|]] ||m|]
Corollary B.4. Let g Rd + R be a spherically symmetric We have (lg(z))(())) = a [|x
Lemma B.5. Let g Rdd R a spherically symmetric function. Then, for any a E Rd, we have
Cr 6.
E (g(x) x)x}= = E {g(x)
|
=nD
vd
19

---

Published as a conference paper at ICLR 2023
Proof of Lemma 3.1. For simplicity, put g(x) Bwva | o(w x). Since o is 1-homogenous and i is spherically symmetric, we have
g(x)
|2/|| 022 ())(w) du
RR
S r0 2))(((()) (o
n u(r) dr [ 2od-
For the first term, note that
[
00
/ r² (o (w)dr l(d/2) /
2T///2 0o0 - ,d=)
|20l2 ((w) dw =
m(r) dr.
Rd
0
Hence,
d+ (()) dr r(d/2) 2/2
/ ||o|| u(w) dw
Idd/2) IE ||/l| wiyj
2/d/2
Then we compute the second term as follows. Since it is also spherically symmetric, we have
I ga-1 o(i - x)) dodd-((w)) | / ow,) dod
||0|||
/
L8 /i/dd do
(w)
2
ga-1
Define I - Sga /wn le-lllluu ||wlll dw. We have
d II ==1
oi dw ( |wile- dwi
1=
will
II
e
u² dw; = (d-1)/2
Rd
1=2
We also have
100 c c- d
1
r/wgle
- drdo -- (10)
dr
(ii/do -o
90
gd-1
3g8-1
I((d+ + 1)/2)
[1
88-1
Therefore,
||:||
(d-1)//2
J a(w xx) ddd-"(w))
| do do (w))
||||||
(13)
2
-d-1
r((d + 1)/2)
Thus,
l(d/2)
(d-11)/2
E Ewn ||||
g(x)
E
||
||0||| Cr
||0|||
2/2/2
www
T((d 1)/2)
Vd
Proof of Lemma B.3. We compute
E (g(x))(( x)} = f (0)oo((x)(D(a)) dx a~D
[__ g(ra)o(o (r=))D(ræ)) d-1 d- (x)
[ g())o(v ())r do (w:)rr
g(r)D(r)rdd dr
30-1 alv do -
(d-11//2
g(r)D(r)r dr r((d+ ((dd+)// 1)/2)
||
'Recall the surface of the d-dimensional unit sphere is do
4/2
[(4/2)
20

---

Published as a conference paper at ICLR 2023
where the last line comes from (13). (Note the integral is taken w.r.. it instead of w here.) For the first term, note that
E
(g())
|
g(x)) [(x]) ((x)) dæ
Rd
Pc
(a)dr J8n g(r)D(x))r do a (x)dr
J (())D(x)r do - (z)dr
r(d/2) / g(r)D(z)r" dr.
2T1/22
Thus,
2/2
n (d-1)/2
E ænD
(g(x))((
x))
E {g(x)) ||]|]]
[((d (1/2) ||20|
ænD
T(d/2)
Cr
E a>D
(g(x))
|-]||
||0/||
Vd
Proof of Corollary B.4. By the previous Lemma, have
E (()(z)F(x))}
E
g(x)
E
[|
a(w
m))
wo-pe
E
{1lus] [r
E (g(a)) (w m²)
wap1
Cr
E
||00||
E {g(z))
||]||]
a E (g(x)) ||=|]-
wrpi
Proof of Lemma B.S. Define R Tū (I. matrix associated with B. Since D is spherically symmetric, we have R#D D. For the same reason, g = g. Moreover, by construction, Rv v. Hence,
200 T
Ia. That is, R is the reflection
1
(g(x) x) BND
E
E
(g(x))' x))x))))+++ æ>R#D (g(x)) (v x)
2
m>D
1
{9(x) (v x) g (R Rx Ra)
2
L
1
(9(x) (v x) g (R))o Rv a) Ra.
2
1
{g(z) (v (x (x)+))))
2
D
Note that x + Ra 200
x
(ū, x) G. Hence,
Cr
E æ>D
(0( ()))))))))))))))))))))())) E (0(=) x) E a~D
{g(x)
||=||]
anD vdd
where the second identity comes from Lemma B.3.
B.4 THE NIINITE-WIDTH NETWORK REMAINS SPHERICALLY SYMMETRIC
In this subsection, we show that the infinite width network remains spherically symmetric through- out the whole process. Clear that μ1 is spherically symmetric initialization. Now, assume that spherically symmetric at time t. We claim that v does not move tangentially, and its radial speed does not depend its direction e1. That is, é h([l o for some function h.
21

---

Published as a conference paper at ICLR 2023
By our induction hypothesis, S is also spherically symmetric at time t. Let := 20, io Ia be the reflection w.r.t. 21- Clear that Te = V1. Morcover, does not change the norm and, as a result, S(Tx) Sxx), T#D D and II cT T I1. Hence, we have
E ænD RI,, (S(x) (010(v1 x) + l| d'1 x)))]}
E (IIRR, (S(x) (ōl0(v) x) + | o (v) x)æ)}}
x~D
E xTT#D
mm (5(x) (010(1) =) | o' (or x)m)]}
For the second term, we have
E
[URR,, (()))(()(( xx) + | (11 x))x))))]}}
#D
E [M.., (S(x) (0 Tx) + | d( Tx Tx)]}
D>D
E
(IRR,, [S(z) (010(v1 x) | o' Tx)}]
E RMR.. [5(x) (a(0) m) + || (0) m)m)]}
D~D
E D
(Til,, [S(x)) (a(m w)e + ('m x))]]}
Thus,
11
= 2
(I+T) T)
E RRR,, (S(x) (0 x) + | o'(o x)))}} RR., (S(x) (ō10(w) m) | x))))}} 51
anD
=2 ū1 E
m>D
Namely, 81 h(01))0 where
h( = U1, æ~D
{RR,, (S(x) (010(w) x) + || o' (w) m)):)}}
Now, we show that / is spherically symmetric to complete the proof. Let R be an arbitrary rotation matrix. We have
h Roy = Roi, E anD
[TR,, [S(x) (Rooo Ruy .)) + ||i||| (Ro: m)m)1})
2 Rii, E. {nn.,
(S(x) (R R x)) | o (v1 R x)) RR x)]})
Rö a- R
[I Ruy [5(x) Ro x)) || d'( R)))
#D
Röj R anD
(URR, (S(x) (v)o(V) x) + ||ll| (v) x)+)1}}
2 01. E m>D
RR., [5(x) (010(v1 x) + || o' x))))
=((v)).
Thus, h is spherically symmetric.
C STAGE 1
The goal of Stage 1 is for all V2 to decrease to -1(L/R,,) so that we ignore all projection operators in r2, ú1 and 12. We split Stage 1 into three substages, (oly and -Q Rg.). respectively. By Lemma C.3, at the end of each substage, more projection operator can be ignored. We also show that, in Stage 1, the approximation error of the first layer and the spread of second layer cannot grow too much.
which V2 decreases to O,
First, for the initialization, by some standard concentration argument, we have the following lemma.
22

---

Published as a conference paper at ICLR 2023
Lemma C.1 (Initialization). We choose mı poly(d. m2 @(1) 01 = 1/vd. 02 1/ poly(d, 1/E), and o, to be a small constant. We initialize wi ~ (ni for pt. and W2
~ W2-- (0, x3) and b2 o, for N2.
Given 81.1 = 1/ poly (d, 1/s), we choose a sufficiently large m, so that, at initialization, with probability at least 1/ poly(d). - I 81,1- . We also choose d2 = 8,,1 With probability at least 1/ poly(d), we have maxw> [ua] - Ollo d)o2.
Then, we formally state the Induction Hypothesis we are going to maintain for Stage
Induction Hypothesis C.2 (Stage 1). We define Ti == inf (t 2 0 - (t) = (11) Rog for some some
large constant. Define 61 1. 622 as
6
(11)
(1) 1,7 (0).
|0 (t) E1(0)]]
max
max
2y EP
||21| Ew: ||wu 1|
((1)
8 {(1)
1,R max
1.R
EPE
Eun, |1209 112
in Stage 1.1 and Stage 1.2,
02
((1)
max
(11) (0),
max (2a.ra)(o(h.r))
(1(22)22) (1/2 +2)1
and
dt 1.T ReLU
d
(1)
d max dt 1iEP1
[[) (t) (2(0)))
|1
d (1)
d max dt #1EM1
U 11 Es,, |120 (0] )
dt 1.R ReLU
Stage 1.3,
Ew, /|wil" 11?
d (0)) ReLU
d max dt (=2.r2).(oG.r1))
(122, (06, (0b)+221))
dt
with initial value (0) (0) We say that this Induction Hypothesis is tue at time t E [0, Til if the following hold.
(0) 0 and 2 Tt (0) (0)2 logd).
(a) Approximation error the first layer. For each Us E pr, (1) - 5 (0]] s 8 and
|u112 = [ Ew wp ||wr 1|
- (b) Spread of the second layer. For any (uz, r2), (1b, uo, (2) (1),r1))1
800
(c) The bias term. For any (22, U2, T2 O())
(d) Size of f. |W2|| = 0 (r.,) = (1/dd)) and a =m)
(e) Bounds for the errors. 6/-) Old's d)o2) and (1)
0 < Old (log d)oz + 81.1)
The next lemma describes when the projection operators can be ignored. Roughly speaking, we first bound the gradients to show that in order for a projection operator to be triggered, | must be larger than a certain quantity. Meanwhile, note that f, whence the gradients, vanishes for those x with ||=||| > ((1/)1z2a)) Hence, as long as (11/[ is smaller than that quantity, we can ignore the projection.
Note that we define these 8's to be upper bounds of the corresponding values instead the values themselves. The only reason we define these d's in such a twisted way is to make the proof easier to write rigorously. See the footnote in Induction Hypothesis D.I. where this type of definitions plays more technically important role, for further discussions.
10The first two conditions actually follow directly from the definition of the ò's. We put repeat them here only for easier reference. The actual result we need to prove for these 5's is condition (c), which says that these 8's are always small.
23

---

Published as a conference paper at ICLR 2023
Lemma C.3. Suppose that Induction Hypothesis C.2 is true. The projection operators in i22 è1 and i2 will no longer be activated if all second layer weights are nonpositive, -i2 > (1)622 for some large constant, and - z (1)/ Rwg for some large constant, respectively.
Remark. Though only need -102 to be ((1)8 to ignore the projection operator in ø1, will
actually define the end of Stage 1.2 to be the time Ú2 becomes poly(d)62 to get a more regular start for Stage 1.3.
Now, we present the main lemma of Stage One can see that, by properly choosing the parameters, the errors can be made arbitrarily small without affecting the final value of a and W2 To prove the main lemma, it suffices combine Lemma C.6, Lemma C.9 and Lemma C. together.
Lemma C.4 (Main lemma Stage 1). Induction Hypothesis C.2 true throughout Stage 1. Stage takes at most O 02 + 1/d amount of time. At the end of Stage 1, we have a = O(1/d /s and 22 ()1/d). For the errors, we have 6/²) I O(d) -5 log do.) and 6(2) + 61.r S O
Proof of Lemma C.3. First, note that when all U2 are nonpositive, we have f ( Since choose R,, to be a large constant, this implies the projection operator in ý2 will not be activated.
When - U2 > 0(1) we have f(x) I (ewsa a ||>|| + O(1)) for some small constant 0. As a result, f vanishes on { [||0|| 2 (-cūza) Then, for those æ with || S (-ciza -1 the gradient w.r.t 81 can be bounded
vV [(x)\ < ((1) ||ح||| |1 S (1)
|0
O(d). i2g
Since we choose Ray ((d) with a large constant, this implies the projection operator in in will not be triggered. Finally, for d2e for those x with ||>||| S (-cūgaa)1 we have
0(1)
[v,C(x) & 0(1)a
x < [222
By assumption, |W2| (1)/RR, for some large constant. Hence, this inequality implies the projection operator in d2 will not be triggered.
C.1 STAGE 1.1
The goal of Stage 1.1 is to make that all second layer weights vs become non-positive, that is,
Tı inf 2 0 v(U2, 12) #2, 022 S 0).
As result, at the end of Stage 1.1, f is O(1) and, by Lemma C.3, the projection operator in r2 can be ignored. Since this stage only takes a very small amount of time, we shall control the first layer error by directly bounding the movement of 01. For the second layer, bound the movement of the bias term in the same brute-force way. For second layer weights, we show that those positive U2's decrease faster than the negative V2's, so the spread will not increase.
Lemma C.5. Suppose that Induction Hypothesis C.2 is true time and t Tu Then the following hold.
(a) |لl|| < Rv, and l/2| S Rey.
(b) maxw; W22 min We is non-increasing.
(c) For any positive second layer weight v2, we have ú2 < - -Oog d/d2.5).
Remark. In fact, (c) holds whenever 2(1/d and uy +r 2 O(1) for any (V2, r2) E μo and x E { [|]]| S d'.53, which is always true throughout Stage This estimation will also be used in Stage 1.2 and Stage 1.3.
24

---

Published as a conference paper at ICLR 2023
Lemma C.6 (Main lemma of Stage 1.1). Stage 1.1 takes at Odd 62 ( At the end of Stage 1.1, all second layer weights v2 are non-positive. Hence, O(1) and, by Lemma C.3, the projection operator in inz can no longer be activated.
(0)) amount of time.
For the errors, we have 62" (Ti.) S O(d (0)), and both ( (TI.( and ( (Ti1) can be bounded by O(d 2( (0)).
Proof of Lemma C.5.
(a) This is obvious.
(b) First, decompose 02
h
E ((((a))((=)))FF)) ||~||
E |=]
Rm,,, ((z:)o'(222 r2))))
Note that the first term does not depend on U2, and, for the second term, o' (t2 F(x) +r²) = 1 whenever 12 2 0. As result, the speed of positive v2 is uniform and more negative than those 022 < 0. Thus, maxw,, W2 ming, W2 is non-increasing.
(c) Clear that |a ((f( f())))(()) = O For the second term, first note that for any with ||=||| I dd.s, we have
(()) (1 1
max w2a ||0||| a ||||||| S Res and f(x) 2 O(1) max 4/
wyla max |||||| = O())
As a result,
[IRR. (f(z))'(v22(() +12) 2 O(a)
E
| = θ ((log d)a).
|
15 <
Thus, -(llgdd/d1)
Proof of Lemma C.6. By Lemma C.5, it takes most (f (0)) amount of time for all 02 to become nonpositive. Within this amount of time, 12 at most changes 0( Since the spread of w2 does not increase, this implies 6 (Ti.) < O(11.8 (0)). Finally, the change of vn can be bounded by O 6 (((())) (0)). As result, both (1)) (TT.) and o (Ti.)) can be bounded by o(d (0)).
C.2 STAGE 1.2
The goal of Stage 1.2 is to make sure - d (Ti.1). Namely,
T12: inf ( 12.1111 - = =ds! (Ti.))
Ti.1
We will also show that 8/22) 2(")(Ti2)) (Ti.2) ) 010 (Ti.)) of (T122)/00)) O(1/d) at the end of Stage 1.2. Moreover, by Lemma C.3, at the end of Stage f.2, the projection operator in új will no longer be activated. We also show that 72 remains (1)) throughout Stage in this subsection.
The first layer error is again controlled in brute-force way. For the second layer spread, we show that since |0y| is small, ('v)F((x) r2) for most of æ and, result, the change of (02, r2) is approximately uniform.
Lemma C.7. Suppose that Induction Hypothesis C.2 is true at time t. Then, for any (U2, T2) E pa. f when < f./2 and in < 0 when > 2T fa. As result, 12 +(1) throughout Stage 1.
25

---

Published as a conference paper at ICLR 2023
Lemma C.8 (Spread of the second layer). Suppose that Induction Hypothesis C.2 is true time t and S T1.2. Then, for any (V2, r2), (22, E 12, we have
dt (2) (oz: r1)0 & O(d2.) (05))
Though, by this Lemma, the error a can grow exponentially fast and the growth rate is quite large, will not blow up as 812 S (loog d/ d/d"."), so the time needed for Stage 1.2 is much shorter than 1/d2.5.
Lemma C.9 (Main lemma of Stage 1.2). Stage 1.2 takes at most O (Ti.)) amount of time. At the end of Stage 1.2, we have, any (U2, r2) E p2. - U2 2 O()6)) (Ti.).
For the errors, the spread of the second layer is (1 o(1))6 (Ti.1). and both (T.2(112) and 1 (T22) can be bounded by O(d 6 (Ti.)).
Proof of Lemma C.7. We write
122 (() ((z)) + r2)] = (.())))) -0 ((()))'(v22(()) r2))
Since the spread of by is o(1), when 12 I Eg (x) = ( the RHS is a positive con- stant. In other word, r2 will keep grow. Meanwhile, since the second term can be bounded as Eg (f (v2/(v/2(a + +2)) 2 Ei {f())} 2 (1 - o(1))b,, when 72 2 E fo (œ), ñ'2 will become a negative constant and ra will decrease. Combine this two cases together, and we complete the proof.
Proof of Lemma C.8. Since |02| < d8. (Ti1), F(x) O(a) ||||||| and 0(1), I @(Va/52
O for all with |
(1) (Ti.)). Hence, we can rewrite 022 as
d2
E
{IR., [(f((z) - [())) (U)()))((())((())))))))
[ (Tra))
| 2 (TT.)) {IR.., (v)(()))))))))++))))))))))))))))
E
The first term does not depend 02 and, by the tail bound, the second term be bounded by O 5( (Tr.)/Va). Similarly, for r2, we have
(f((x) - f(x)) +0 (ONNTVV))))
a22 |e|leeva (T..))
Hence, for any (v2, r2), (1/, r2) μı, we have
(1) (Tin) (
+(22-r6)0 (80
(Ti.1) $ 5 (D50)
dt (1(2, - 12) (12- 06)0
Vd
vd
Proof of Lemma C.9. Recall from Lemma C.5 that ú2 -((ood//d-.) whence Stage 1.2 takes at most (1225 x (Ti.)) amount of time. By Lemma C.8, we have
(TT2) < (05 (T.))) 2 exp (o(d)) (T..) s (1 (1+) (IT))
For Un similar to the proof of Lemma C.6. both of (TT.2) and (Ti.) can be bounded by ((118())(1 (Tia)).
n
26

---

Published as a conference paper at ICLR 2023
C.3 STAGE 1.3
The goal of Stage 1.3 is to make sure -W2 - (1/R2a) for some large constant, so that, by Lemma C.3, the projection operator in 022 can be ignored. That is, define
Ti3 == inf {t 2 T1. (t = (11
The time needed for this stage is longer than the time needed for previous stages, so we need less brute-force ways to control the errors. For the first layer, we show that the tangent movement is almost zero and the radial movement is approximately uniform. For the second layer, we show that the spread 8/2) cannot grow too fast.
Lemma C.10 (Main lemma of Stage 1.3). Stage 1.3 takes at most O(1/dl-5) amount of time. At the end of Stage 1.3, have W ((1/Roy) Rog) and O ((vd/Ro.).
For the errors, the spread of the second layer is O 15 (Ti.)) and the first layer errors are (( + (1) (T1.) + d1,1 + log(d)62")T..)
Proof. Since dp = (log d/d s) and R,, (dd)) Stage 1.3 takes at most O(1/d'5) amount of time. Within this amount of time, by Lemma C.18, we have
(1(1) 1 00 0 (Ti3)) (620(( (Ti2)) exp d2.5 d
(1+ (1))0)))))
For the first layer, by Lemma C.16, we have
(00) (Tis)) (TT(T - 8 (T. + (2) (112)
0(1)
51 + (1og(d)o()) exp
0(1) d2.5 d=.5
d
= (o
61
log(d)02 (T)
d
Finally, by Lemma C.17, we have (Ti.)) = (1 (T)))
C.3.1 ESTIMATIONS RELATED TO o'(2FF(x) r2)
First, we need some helper results handle a' o' ((z) r2). The conditions for them to hold mild and are always true throughout the entire training procedure, and we will use these results in later stages, too.
First, we show that when the value of d'(r)F(x) + r2) can change across different (02, r2), the function value must be small. Note that the error here depends on the ratio 52/ ///l0zz] and this is why we need |حa to be ((d)2 instead of merely (())a² at the end of Stage 1.2.
Lemma C.11. Suppose that r2 = ((1, -02 2 M()2) for any (V2, r2) E u2, where 82 is the spread of the second layer. If u2F(x) r2 0 for some (V2, E u2, then F(x) + r2 S
O(((0211 + +))2) for all (w/, r2) E μ22
72 = 0. As long as vz)(()) + r2 < O and F()) + r > 0 for some ( r2),, (re, ri) E H2, by the continuity, there always exists some point (V2, r2) between (vg, r²)) and (ny r/) such that 02F(x) + 72 0.
Remark. is not necessary that there really exists (v2, r2) E u2 with (x) +12
Moreover, this point is within the spread of the second layer, so this lemma still applies.
Then, we show that we can absorb o' into fo and f.
Lemma C.12. Suppose that the hypothesis of Lemma C. /1 is true, and all second layer neurons activated on [||=|| < 1}. Then, for any (V2, 12) E (22 and x E TRd we have
(= (12 ((x) + r2) fx( and
+ r2) f(x) + 0 ((102)- + 1)62)
As a corollary, we have
f(x) = o F(2 +r2) 4 0 ((/ē2l + 1)82)
f(x) = a F(x) (2) + + (( 1)ō2)
27

---

Published as a conference paper at ICLR 2023
As corollary of Lemma C.1I, the measure which (()) + r2) can differ for different (U2, (2) is also small. Here we also use the fact that those a are around [20l) the tail bound
|P] (r) S Q(1/r²).
Lemma C.13. Suppose that Induction Hypothesis C.2 is tree at time t. For any (2), (02, r2) e P2,, we have
+2)) - 0 (ad)²).
Proof of Lemma C.11. For any (u2, r2) E μ2, can write
1/2 Fa:)
r/ vg F(x) + r2 + (122 02) + (r22 -r2)
012
U2 (12 1 + (r2 r2) -
U/
1/2
(r22 r2).
U2
12
The last term can be bounded ((((02] 1)62).
Proof of Lemma C.12. Since all second layer neurons are activated on {||=|| < 1]. we always have
(xx) (v2 Fx)) + r2) = (x).. Now we consider / [()) )o ((z))o((u2F(( (#2F(x) + 12). If 02 F(x) ) + r2 > 0,
then done. If (())( r2 0 for all (2/, r2) μ2, then both f(z) (22 (x) r2) and
f(x) are 0. Therefore, it suffices to consider the case where (z) + S while f(z) > 0. By
Lemma D.6, in this case, we have f(x) S O ((102) 1))2).
Proof of Lemma C.13. Since the norm and direction of are independent, it suffices to fix direc- tion & and consider
E r~|
(lo(( + - σ' (16)
For notational simplicity, define ((02, T2, r) = F r2. The integrand nonzero iff the signs of fu(12, 72, r) and h(22,, r(.r) are different. To bound the length of the interval on which the signs can differ, we write
( r2.
h(V2, r2, r) (x) by (U2 - (2) + (12 1 bz)
= い12 = o 6 rF(a) + b2 + 0 ((11
Therefore, the length of this interval can be bounded by ( (mza)). Moreover, note that this interval is at ((1/[uza)) whence the density on it is O Ow Thus, the measure of this interval O(ao
C.3.2 ESTIMATIONS FOR THE FIRST LAYER
Before we control the eгror growth, we need a lemma that relates the approximation error with the langent movement and radial spread of the first layer.
Lemma C.14. Suppose that the tangent movement and radial spread of the first layer neurons can be bounded | (t) v, (0)ll 81. and || (1 d1,1z) Ew, l|,:112 Then
F(x: p1) (1 (1+ + 81,1 + vdői.R + vdōi.T) a ||س|||
As simple corollary, we have the following. Corollary C.15. Suppose that Induction Hypothesis C.2 is true at time t. Then, we have
[5(z) - f(x)) = (5i.r + vdo(2), i. + vds(.)) wza ||
As a result, we have
E (f((()) f(x)) [|xl]] 5 (0a.1 + vdo(1) + vdo(.k) E|a
5 501,t + vdd + vas(1)
28

---

Published as a conference paper at ICLR 2023
Now, ready the control the error of the first layer.
Lemma C.16. Suppose that Induction Hypothesis C.2 is true at time t and E [Ti.2, T1.s]. Then we have
(5))
(( + -Vo + vasl. w22 + +0 (log(d)o!")
dt
0(1) 2.
(i,1 (1.1 + 011)
11.1 + (log(d)(55)
Finally, we estimate the radial speed of to provide an estimation for the magnitude of a at the end of Stage Lemma C.17. Suppose that Induction Hypothesis C.2 is true at time t and [Ti.2, Ti.3). Then have
log vd
11 ==
U2 ||01112
dt
Proof of Lemma C.14. Define 2 = Eu,, || 11 Let u be the distribution obtained by setting the
norm neurons in P1 N. We have
F(x; p1
E
{(1 N2. =)} (4); O6 ||=]])..
Let ue be the distribution obtained by moving (t) to ú1 (0) in μ1 Then, we have
F(x; (4)
N
E 201 (0)
to æ)} O |x||| N
F(a; + O (f1. |
Finally, note that
N F(a:A)) = F(
N No
(1 61,) ||ج||| (1 + 61.1)a ||=|||
No
Combine these together and we complete the proof.
Proof of Lemma C.16. First, we decompose in along the tangent and radial directions as follows: Rad(01) = (01, 01) 01 = 2 {S(z)o(v) x)} 01,
Tan(0;) [I . )0 | 11 (S(x)oo' at)(I 0 o1ū )m)
Note that új Rad( (1) + (1). By Lemma C.12, we have
Rad( à1) 2 E {(f- (x) f()))o((1 x)} 01 O (log(d)0 [[0ill).
Tan(o:) (1) = | 22 E æ
(ff(x) - f(z)) (v) - x1 - 0, 02 )x} + (log(d)65") [[oil).
For the radial term, by Lemma B.3 and Lemma C.15, we have
Rad((;) 200 (f=(x) f(z)))((u 2) 01 2w ((f()) f())))((e) x)} or 0 (log(d)0{)) ||
2Cr#a E (V.(())) f(x)) ||<||| |
Vd
# (0 vāol.) + vas(!k] we [ea1l) + + (log(d)({") [|0i1l)
Therefore,
d di |1ll Rad(t))
4Crw2 B (f(((()) - f(x)) ||=||] ||
vd
#0 (010 Vdol%k + vaol.h) th (1111²) +0 (log(d)o{) [laal?))
29

---

Published as a conference paper at ICLR 2023
For any U1, 0f E ja with |/2a|| || 2 ||e/|l, we have
d |eill /1rll=-100 -|ooo11 de
d
(1101l2 - -1ooi IP) ||01|| 2 - ||011 at |
11o1
df |0/1
||0/112
|| 1|
| 1
4Cr102
E (J)((x)) - ((x)) | || 1 - |eill
vd x
(1111 + Va + vdo(.k) T35) + o (log(a)o!")
+
1 1
|0y 12 4Cru2 (1](())) f(x))) ||xe|]
|| 1|
Vd x
- 1
110211 ((6.1+
(oil + vdo Wzz 1
| 11 |
O (log(d)o3))
110
|
+ ((6., + vao vad (2)) o (10g(d)05")
Now we consider the tangent movement. By Lemma B.5 and Lemma C.15, we have
Tan( = || 22 (f-(()) f(=))oo(v) x) 010 )x)
+ || U2 w2 x
(f(x) - f())) ( x)(1 - 010e )ae + (log(d)of) [will)
= =0 (( (61, + Vd + vdo(.h) 22 [1lil) + O (log(d)o{)) (00ll)
As result,
dt i1 Tan(d1) || = =0 ((o..+ Vao + vdol w2) = (1og(d)o5)).
Combine these two bounds together and we complete the proof.
Proof of Lemma C.17. By the proof of Lemma C. 16,, we have
2Cr
Rad(
E (f=(z)) - f(x)) | 01
Va
+ 0 (( (01, + va + va)(.k) ih (1m1l) + O (log(d)(5") [|ill)
= log d
Vd 22 +0 =0((0n vaoli R vaolik) ) Uh [eeil]) + o (log(d)05)) |will)
Recall that 1/2) $ | /d. Hence,
d di
||0|
1|2
= 0
log d vd
W2 || 11 1 0 (6o.5 + vaolih + vao(.n) th || |10:11²) + 0 (log(a)o$)) (o:11²))
log dl Vd
θ
W2 ||0 12
C.3.3 ESTIMATIONS FOR THE SECOND LAYER
Now, we bound the growth of the spread of the second layer. Readers may first check the proof of Lemma 1. which is essentially a simpler case of this result where we do not need to deal with the projections. In Lemma 1.14, we show that the spread will never grow. Here, the error comes from the projection.
Lemma C.18. Suppose that Induction Hypothesis C.2 is true at time t. Then we have
d
(62
ك d2.5 (5 (
((1)
dt
30

---

Published as a conference paper at ICLR 2023
Proof. write
Let (02,72). (12) E Al and define h2(x)) 12F((x) + and h((a)) o2F((x) + + We
d2
E ( f(x)))
|| T (1xa) (1))) + (2))))
||
Tj does not depend on 02. For T2, note that
a
II / (bax)
Similarly, for 12, we have
d
dt (r2 1222==22
R
(( -12))
1|0
=-2
E
- (12((2)))) r/)}
21
2
E
- (((b))))))
||
Combine these two equations together and we obtain
dt ((02 - r2) + (r2 722)))
{ (Innz//(aa) [f(x)] (o (h2(z)) - -d (h2(x) 11((z))
=-2 E |
2 2 E ||
(d2()(2 F -f
(hb(()))) -1))
Since o' is non-decreasing, the first term is nonpositive. For the second term, by Lemma C.I I and Lemma C.13, it can be bounded as
0(1) 22.5
max (=sgn( (ar)
|||||| f(x)x EE (l0((h2(=)) o' (1) 5o
S
(5)
(
7822
D STAGE 2
The goal of Stage is for gradient flow converge point with loss maintain a set of induction hypotheses.
Similar to Stage
Induction Hypothesis D.I. Define Tr = inf 2 Ti f ==
Define 1!2 ,1, ,8,0 as
((2)
d (2) di $1.13 ReLU (4 11- --1---11=:)
d
6022)
00 ReLU
(
Flss 111 1112=))
di' 02
d (2)
0,
di
di
with initial value satisfying!! "1
117
(6
< 8(2)
s 2
5(2)
n
1.12 0
(2)
d7
((2) (Ti) 0 (144.
1
(2)
<0
d1o
For any 1 E (T,TT]] we say that this Induction Hypothesis is true if the following hold.
11 As have mentioned in the footnote in Induction Hypothesis C.2, these 8's defined upper bounds
corresponding errors. This gives certain degree of freedom in choosing their initial value. By Lemma C.4, we can choose the parameters so that the errors at the beginning of Stage is arbitrarily small and these conditions can indeed be satisfied. The first condition, which requires the L error to be left and right controlled by the 0 error, may seem strange the first sight. The only reason we need it is to merge some second order terms into first order ones.
31

---

a E Published as a conference paper at ICLR 2023
(a) Error of the first layer: || |1-1111z S 1,12 and || 11 50,,mm
(b) Spread of the second layer. (1(12, - (1/2 r3)1 S 8222 for all (l2, (222 p2
(c) Regularity conditions. b2 < 1 1- W2a 2 -1+0(vE) |لح S d. أج2 N (1/dd))
(1/dd
a
(d) Bounds for the errors. 6 =6.82=
(Ti)) and 5 0(6(22
The main lemma for Stage is as follows. Lemma D.2 (Stage 2). Induction Hypothesis D.I is true throughout Stage 2 and Stage takes at most ( /e) amount of time.
The rest of this section is organized as follows. In Section D.I, we collect some auxiliary results that will be used later. In Section D.2, we show that Induction Hypothesis D. is always true throughout Stage 2. (Also see Section B. for discussion on the techniques used and some conventions.) Then, we derive lower bound on the convergence rate in Section D.3. Finally, we prove Lemma D.2 in Section D.4.
D.1 AUXILIARY LEMMAS
D.1.1 THE DYNAMICS OF F. AND
Recall that, in Stage 2, we can ignore the projection operators, whence the dynamics of the neurons given by
t1 ((((x) (0:0(1 x) + || d'i m))))
d2 E f F(x) + (2)))
((xx)))) +2))
i
Now, we derive the equations which describes the dynamics of a, F, and the loss C. Lemma D.3 (Dynamics of a). In Stage 2. have
4Cr E (((('))F(2')
à Vd
Lemma D.4 (Dynamics of F). In Stage 2. for each fixed x, we have
dt F(x) = -4 4E { x!
S(x') E {o(w1 x a')o(ww1 x)}
S(a') E.
||mi d'(v1 x do)o'(n 2)) ((I o "
)a' .²)
Note that in the above lemma, we decompose áे sponds to the radial movement of and the second term the tangent movement.
F(x) into two terms where the first term corre-
Lemma D.5 (Dynamics of L). Define W2(2)) have
Emggd (w(2FF()) + b2)w2}. Stage 2, we
- C
E 02.
V b2 11?
di
where
o' d'(u2F(a)) + F(x)
F'(wz((x)) + b2)
Wy Wwy.ba W: == E'
(fa(z)-f(())
-
|| (2(2)o'( x) w w )
The entries of V ur. to, correspond to the movements of U2 r2, radial movement of 8 and tangent movement of vi, respectively.
The proofs of these three lemmas follows.
32

---

Published as a conference paper at ICLR 2023
Proof of Lemma D.3. Recall that = Cp Bwi || 1 Hence, à 2Cr vd
Bw: (wi, wo1). We com-
vd
pute
(0), v1)
E (S(x) (a(v) x) (ūi, + ||ll| d'( x) vi))] 2 22 (8(x) 10l1o x)}
Hence,
à
4Cr vd
E (E((())
will ow- - x)}}
4Cr
S(x) E Allwillorr x)}
4Cr E F())))
vd
vd
Proof of Lemma D.4. First, we write
dt dt E ||
d F(z)
d
ow =)}- - E { {(
d
dt |1w111
ow x)}
J E ||2,ll
d
o m)}
dt
By the proof of Lemma D.3, the first term is E (S(x') Bw, fo x' (0)o x)}} For the second term, we compute
di 0 (2) x) = o'v1 x)
(I ( )1
(1-
|0il| 1
i1
c'(ni x)
E ((((z')) (0) x. x')(I 01 )a' pa')a00 .x)
E (S(x'' (m1---)))o) 2')o'(11 x)) ((I - 0 )a',,))}
Hence, the second term
E || 1|
dt 0 a²)
E x¹
W. ((x')
||wm d' a')o'(1 x)) ((I i1 "ar x)
mi
Combine these together and we complete the proof.
Proof of Lemma D.5. First, we write
d dt f(x) = 102
d (o2) + bb))igF(x)) + {d'(w2F(x)) + b2)b2} + W2(x) F(x) dt
_
w2.ba
d f(x)) + +T3
d
Ti
f(x))
+ T
((x))
dt
dt
dt
Note that # C = - Σi= Ez {L. (x) [())) (+ [())) } Now we compute each of these three
terms separately. We have
(1((00)) - [())T
(
T (d))
d
E
- [1
wiz)
w2,b2
(B(().()) (o)) 2
E
w2.b2
d E (f((z) (
à ((()))
- [[)
[
w2.b2
{
(B((U())) (w=)) (2)) 2
w2
Meanwhile, for Ts. by Lemma D.4, we have d dt f(a))
E ((=)))
E (f((z)) (()))
d F(x)}
dt
(v.(0)) - f(x) E. S(x')
4B
E (alw al)o m²)
wi
+E (1..(0) -((x)) E
5(x')
E
|| 1| d'wn x''o'(w, x)) ((I 20 2 )ac' xx)
wi
E E (S(x)o))))) m3)] =)))))
E (S(x) |m o' dw( a)([ 20, uo )az) 113]
E
33

---

Published as a conference paper at ICLR 2023
Combine these together and we complete the proof.
D.1.2 ERROR-RELATED ESTIMATIONS
We collect some error-related estimations here. Most of them have been proved in Stage 1 except that here we have used [22| 2 @(1/d") to replace (|02| 11021-1+0 +11) with (d We repeat the statement here for easier reference.
Lemma D.6. Suppose that Induction Hypothesis D.I is true at time t. If 02 F(x) + = 0 for some (V2, r2) E P2, then u/ F(x) + + S SOO00 (d for all (12, r22) E u2-
Proof. See Lemma C.11.
Lemma D.7. Suppose that Induction Hypothesis D.1 true at time Then, for any (22, E μ22 and x E Rd, we have
I. (())) [a(r) and (o))d + = f(x) + + (0'00(10) (8'052)
As a corollary, we have
f(x) o()2F()) + + (d
f(x) (02 b2) + d (d²²!
Proof. See Lemma C.12.
Lemma D.8. Suppose that Induction Hypothesis D.1 is true time t. Then we have |15 -
O (102a10(.22)
Proof. Since is 1-Lipschitz, we have
(olwzF(x) + b2) o(w)F(x) bi)} 50 00 (w221(((()) F(z:)))
[f(z) f(x) = E
Thus,
il 00 ((waa' ||00
|| 1111112)
D.2 MAINTAINING THE INDUCTION HYPOTHESIS
In this section, we show that Induction Hypothesis D. is true throughout Stage 2. See Section B. for discussion and conventions on the techniques used here.
D.2.1 ERROR OF THE FIRST LAYER
Recall that we can decompose the loss as
2 - - + E -(z))) + (E((A(()) - f(x)) - -f(x)) }
=: =: + + Ls-
( (f)x) F(x)) and L3 0, so that can decomposed into two terms where the first term captures the difference between the target function f. and the infinite-width network f, and the second term measures the approximation error between F and F. We will show in Lemma D.11 that, one may expect, Li does not affect Estimating the gradients of L2 and C3 is slightly more complicated. First we need introduce the following partition the input space.
As we have discussed in the main text, the goal is to show that L2 x wi E
34

---

Published as a conference paper at ICLR 2023
Lemma D.9. Define
R1 = {R > 0 (222, E po, x R84-1 (2F + 0)
R2 = R > 0 : E(U2,12) r2) E P2, x E RS (x) + > 0f.
Then, we partition the input space into
X1 = f||==| S R1}.
X2 S |||| R2), 33 fR2 S |
In words, X1 is the largest spherically symmetric which all second layer neurons are tivated, and X1 U X2 is the largest spherically symmetric set on which at least one second layer neuron activated. Suppose that Induction Hypothesis D.1 true at time t. Then the following hold.
(a) fa vanishes on X2 X3, i.e,, R1 2 1, vanishes on X3, and Rs S 0(1/ (2///2l/a).
(b) R2 RR1 5.
1, d6!2))
1022
Xx'
As corollary, we have P[X2] 0 (0%)
(c) f s 0 (D22) on X2.
The above lemma implies that L2 2/2 Bx {f(x)) [(m))] 0h Ex, {((()) F(x))2 and
L3 Ex, {(f((z) f()))((()) f(z)) i Ex, (f.(()) f(=))(((xx) - F(x))} O. We formally establish this approximation in the following lemma.
Lemma D.10 (Gradient of C2 and L3). Suppose that Induction Hypothesis D.1 is true at time t. Then, for each Un E fl. we have
Wh
(((o))F(())))) #0 (002))2
V L2 = V.
a |
2 X1
V., L3 = #0
(1(2)
|0l||.
Now, we are ready to derive the equation that governs the dynamics of F. Note that this Lemma implies that, least approximately, the dynamics of F depends only on L2.
Lemma D.11 (Dynamics of F). Suppose that Induction Hypothesis D.I is true at time Then, for each fixed x; we have
dt F(z)
w E 2
F(a)
Vw, wi x'ex;
E
(1(())=F(x')))) -(()))))) (va
2 Xx
1
||||||
Then, we show that the signal term de F (x) can only decrease the L error, which is intuitively true as, after all, L2 the (rescaled) I error. As result, the I error barely grows. Lemma D.12 (L2 approximation error). Suppose that Induction Hypothesis D.I is true time Then we have
d || -1-11-- so s0 (d (0 di
(6
Finally, we show that the change Fla--1 depends on the I,2 error. As result, as long as the T,2 error is small, the 0 error cannot grow too fast.
Lemma D.13 (L approximation error). Suppose that Induction Hypothesis D.1 is true at time t. Then, for any gd-1 have
d So
50
(86(2)
dl (8%)
F()) dt
The proofs of these lemmas follows.
35

---

Published as a conference paper at ICLR 2023
Proof of Lemma D.9.
(a) This one follows directly from the construction of the partition and Induction Hypothe- sis D.I.
(b) First, we write
F(x) = a|
|>|||
||||||
f11-- a ||]|| +
[322
where the last equality comes from the fact I vanishes on {||0o|| 2 92(-b2/ //2 ls/l Similarly, for any (v2, r2) E 12, we have
ü82 1})
22 F(F( + +
U2
F(z)
112 02
F(x)]
U2
F(x))
r2
1
122
82
.2 (x)) + bg +
0/
aa
||:0 11
= (2) + b +
d8'
Hence, for any R >>> 0 and RSa-1 we have
12F(()) r2 W2a |||||| + bo +0
0/.21 1
+ 0
=: Srop
Therefore,
b2 8rmp
STeP
(2 r2 0, if ||a|||
<
R.
u22
W2a
52 + 81mp
8gmp
12F(())
r2 0, if |
R
w2a
W2a
In other words, R1 2 R
txe uza
and R2 I R +
fiee
Thus,
R₂ R1
8 8mp
0
(2) 1,10
+0 (12
a =dx2-
Uza
To complete the proof, it suffices to invoke Lemma B.1.
(c) Note that by the definition of Rz, for any 3bp E R we have f((0) = -. Hence, for any X2, there exists some Do with fwo) and | zoll S Ra Ri (2)
Since f is Oi1)-Lipschitz, we have, for any E X2, fxx) f(x) f(xo) s 0
Proof of Lemma D.10. Since both f. and f vanishes on X3. suffices consider X1 and X2. Recall that that all second layer neurons are activated on X1. Hence,
1 E (((())((()))
w3z E 2
C2
xi 2
C3 .x
= x ( s(x)) = T22 EE Xi -(a)
0,
where the last equality comes from Corollary B.4. Now, we bound the influence of X2. Note that both Vo, and V., f(x) are bounded by O(w52 || [|]]]) Recall from Lemma D.9 that
f SS ) on X2 and P[X2] S (() Therefore,
Vo C2
<0 O xxx)
O
[wa
||
1 0 W2la
(
21 1 a ((02)
| lll
X2
The proof for V.,, La Xx is the same.
36

---

Published as a conference paper at ICLR 2023
Proof of Lemma D.II. For fixed æ R,, write
d
F(x) F(x)) á = E (V,)) Vw, C) + F(x)= a wi
df F(z)=
E
(Vw, a, Vw, C).
a
a a wi
First, we consider L.1 For each v1 E pl, we have
Vo,Li = - E x
- (ff((z) f(x)) f(x))
20r E { (f((z)) - -(x))
{o(waa ||||| + b2)/wz) } 01 =Cmm,,1U-
E
vd
w2.b2
Meanwhile, note that
vV F(z), 21) = (Vn, (1|ba 11 oθ 22)) = (100))10)))) 2x) 01) = 1|21 1| Fo100 x),
Cr av) Vd
{ Ven | 2 01
2CT
| ||/11
vd
Hence,
d F(x)
V L1) + F(x) 1
=
E wi
( w
F (x)
E (Vw, a, Vw, L1)
dt
C 1mp.11
2
E
{ || 12 o 2)} (imp,1(()) vd wi
2Cr
E ||w ||
a wi
2
Cmmp.1
F(x)) + 10
0.
Namely, LI does not affect F. Now we consider L2. By Lemma D.10, we have
1
F(x))
E V wi
F(x).
V w L2) + F(xx)
L2) w a, V L2) E (V
dt
L2
wi
1
Wh
V
Vwi F(x)) V E
-((a)))))))
a: mi
2
x'EX
+ m
F(x))
E
V Vwia, a
E x'EX
(F((')-F((a)) F(x1))²
2
wi
2
+
|
Note that we can rewrite the V F(x:) in the first term as (Vw, F)) + +v w F(x)) so that part of it cancel with the second term. Then, we get
d df
F(x)
w3 E wi
{
(Vw, Vw,
E x'eX, (((a)) } (va ((12)) 2
(va()22)
|
=
C2 2
For L2, we can simply merge it into the error term of a de
F(x)ecr
Proof of Lemma D.12. By Lemma D.11, we have
d
||
11-111 1.2 E
(F(t)) (|ar])
dt F(x))
d
dt
3
E (F(x)) - ||=|||
E
{
m
F(x),
Vol E. x'Ex, {((('') -F(3)))
2 x
wi
+ (F(z) - ||01)0
Vd
((2)
The second term can be bounded by o
(22)
(2)
2
d
The first term is equal to
1.0²
X2
Tmp
E. w.
V
E
(F((())
|| 2]
V mi
E x'ex;
{aa
F(2))81)
37

---

Published as a conference paper at ICLR 2023
To complete the proof, it suffices to show that this is negative. For each W1, have
V Vw,
{(a ||=||=o|| F(z'))*) æ'EX1
E
E ((F(2") - ||>11))² Vw,, a² a² E æ'EX,
(Vu, (F(x') [|=11)))
x'EX,
Since the distribution of is spherically symmetric, Ex'xx, { (F(w') || and Em { V wi (F(x) = have the same direction. Hence,
Tmp S
((((2))
| 1))} Vw, a2)
{(F(x') - 1| E n'Ex,
4 wi
CT
E {(F(x))
|| ||>11)> E E {(V m0 (F(x) - || wm }}
Vd
2
x'eXi
Then, we compute
Vw, F(x)
Vw, a
(ww (F(x)) 1x+1)) = =2(F(x)) - ||~|])
-F(x))
w1
2 |1/ ||? o(31 x))
1 2C
=2(F(x)) - ||x||)
F(x)
| 1?
vd
Take expectation over wy and one that this is O. Thus, Tmp $ 0.
Proof of Lemma D.13. Recall from Lemma D.11 that
d
w/2 ( V Vui E w'Ex,
((((a))-((())))) VV
(1()
2
F(z)
E
|
dt
wi
X2
For the first term, we have
Vw, F(x)( 5
V F(x)
F(x)
á + F(x)
_
0
20(leeg) ||101|1 |1
a
a
{ (((aa')((aa))) 1(a0)) $1]
Van x'EXi
E
< E
(1
M(a')] +
+1| V F(x')l)
x'EX,
O(1)
E
) - F(x')
|| ||
x'ex,
((2)
|100
1,62
Val
[
Thus,
F())
<0
wg E
w
(2)
1
/wil| 1)
+0 ( (va
2 )²())))²
||ح|||
w1
a
122
0
Vd dd/0g/
Vax
1.5
1,62
||
+
Vd
(
(((2)
|
0
d (2(2)
1.12 + d2 02%0)
||0|||
D.2.2 SPREAD OF THE SECOND LAYER
Lemma D.14. Suppose that Induction Hypothesis D.I is true at time t. Then for any (Uz, r2), (b).r)) E H2. de [1((2, - -wbh r5)1 & O. In words, the spread of the second layer never grows.
d
38

---

Published as a conference paper at ICLR 2023
Proof. Let (22, (4/, r2) μl be two second layer neurons. For notational convenience,
define hz(2) = 12 + r2 and (z) = u2F(2) + r/.. We have
1 d
((22 -
r22)²)
2 dt
(n2
m (()((())) [(x)) (o' d'
+ (
(d - d' (x)()))))
[().(()) f(()) (h2(2) - -12(2)))) (o' (h2(2)) - d'()(()))))
By Lemma D.9, o' (12(2)) d(()((z)) = 0 for all a with | < 1. Hence,
((22 - 122² + (r2 - r2))))
2 dt
= R ((.((z) - (ax) (a) (²(())) (12())))) - (1((()))))
2
(f(z)) (x) - h2(x)) (o (h2 - (1k
=
Note that f 2 0 and, since o' is non non-decreasing, (h2(x) h2(x))) (o (h2(()))) of (h((z))) > 0.
Thus, 1 d dz ((22 v + (r2 r22)²) - O.
D.2.3 REGULARITY CONDITIONS
As we have mentioned earlier, we will mainly use the continuity argument to maintain the regularity conditions, the problem can be reduced into estimating the derivative on the boundary. As an example, suppose that by 1- - d for some small å > 0. Then by Lemma D.15, which upper bounds the loss using by and 1 Tza, we know
Tza must be large, otherwise we would have L < E. Then, we can use the fact that | - W2a is large to estimate the derivative. The proof for the other regularity conditions similar except the proof for [ū2) which is the same spirit with the ones for first layer errors.
Lemma D.15. Suppose that Induction Hypothesis D.1 is true at time t. Then we have (-1-
S ==0((=b)) (1-=
=2aa) + (
Lemma D.16. Suppose that Induction Hypothesis D.1 is true at time and b2 = 11 111-0(1 O(VE). Then, d 4b2- 0.
Lemma D.17. Suppose that Induction Hypothesis D.I true at time and W2a - +1 +OVE). Then we have (1z2a) O.
Lemma D.18. Suppose that Induction Hypothesis D.1 is true throughout Stage 2. Then [zz S d.
Lemma D.19. Suppose that Induction Hypothesis D.1 is true throughout Stage 2. Then [02) 2 ((1dd²) and a 2 (11/d255).
The proofs of this subsubsection are gathered bellow.
Proof of Lemma D.15. For any x Rdd by Lemma D.7 and the Lipschitzness of we have, for any x E X1 U X2,
(()) = o (wzaF b2) O (d' (1²x{²)
= a - ||=|] + +1 bzl |- |||||| - F + (17(22)
By Induction Hypothesis D.I, for any x E X1 X2. we have
|- ||>||| (x))
= -|-1 aza F [z) ||=|||
(1-----0aa) w2al ) +0 +0(0722m))
S0 60
1-1--zal]
< و |
F(#)
||0||
39

---

Published as a conference paper at ICLR 2023
Therefore,
= (x)===())= b0/=0 (
w2cx
0 (6 + )
Thus,
2 - 2 x
S
1
[1- by + +0
12
+ + (5(2)) +0(0192 + d (3622)
x (1 - b2)²
(-1
w2a)2
+
(8(2)
1, + doog
wza²
Proof of Lemma D.16. By Lemma D.7, for any (U2, E 12, we have
f = E (f-(z) - (ū, b2)} = O d (())
Then, by Induction Hypothesis D.I and the Lipschitzness of a, we have
(w2)(xx) + b2) = oiūza | F(z) + b2) = σiūa x + b2) = 0 (01:2=)
Therefore,
b = E (f-(x) - [12 b2) + 20(00% (01.1 + +c6
Since L 2 e, by Lemma 15, we have
(-1 - )²a)²
2 [(E)) - -00)))000))00100 (6f2 + + ) 2 S(E).
Since W2a 2 -1, this implies V2a 2 -1+0
In fact, this implies W2a 2 -1+ (((E)) even when [0 o(1), as, in that case, Wza 2 -1 + 52( (8) directly holds. Hence,
( | b2) ((-1 |0||| + 5) (1 | + 2 (Ve||=])) 8)
Thus,
=2=B(f((>)) (1 |||||||| 2 (V=||=]) - (V=[[=l))
+ 0 (519) 1 + dà
$ be|
(1- | - (1- | + Ω (VE - 0)} + 0 (0 + d 238
= - Ω (VE) + + (,92)- + -
As long as the constant in = 0(vE) is sufficiently small, this implies b2 < 0 when 82 = 1 --d 6.
Proof of Lemma D.17. By Lemma D.3 and Lemma D.7, we have
d
(a+ 4Crwg
(20a) E (f) o (wza |>||| F(#) b2)) F(x:)
Vd
+ (olog()oo))) a (
4Crwz
Vd
Now we estimate the coefficient of the first term. Suppose that W2a = -1 -1 5 for some 8 < e with sufficiently small constant. Then, by Lemma D.15, we have (1 62)² > ((E) 0
O(s). Hence, b2 < (VEE). Also note that uza = O(1) implies that suffices to consider x with | (1)) As result, have
a (wūa | F(x) + b2) = a ( ||||||| + b2) + O (111)
< a (1 |||| - O(VE)) +0 (012) (1
40

---

Published as a conference paper at ICLR 2023
Then, decompose the coefficient
E (J=( - (ixze ||a||| F(x) + b2)) F(x)) 12 (f.((())) σ (iūza | F(x)) + b2)) F(x)}
{ ( -0 ( F(x)
2
|
2
Thus,
(ūza) 2 (2((V)) - 0 - log(d) a (a+ 4Crw2
> 0.
dt
Vd
Proof of Lemma D.18. By Lemma D.3 and Lemma D.7, we have
i2 = [{((f((>) - f(x)) - log do?
2
4Cr
E ((f((x) - f(z)) +0 (log
Vd x
As result,
2Cr a Vi ( dt
d
0 s 0 < (
Also recall that w3 < a at Tr. Thus, throughout Stage 2, we always have Since |uza| < 1, this implies أحه < O(d'/8) < d.
2Cr vd
< 1/d.
Proof of Lemma D.19. Recall from the proof of Lemma D.18 that Ja when a ((1/d" we have [6y| s (1/dd). The estimations in Stage 1, mutaris mutandis, show that both and [2 will grow in this case.
2Cr vd
w
<< 1/d. Hence,
D.3 CONVERGENCE RATE
Recall from Lemma D.5 that d = En 02,001 ae
V w2.b2 be, || where
o' (wyF((x) + F(x)
d'(wF((z) + b2)
by E (f.(x) f(x))
( x))
|| W2(2)o' (w) x)(I
w w x
Lemma D.20. Suppose that Induction Hypothesis D.1 is true at time t. Then have
d c s -|=| +0 ((0.)) + + d²).
where
E= (f.(z)- ||]||| / /22 a/2
4Cr
wāa
vd
Lemma D.21. Suppose that Induction Hypothesis D.1 is true at time t. Then we have
A a(aC) O (5..) + &d!!
Lemma D.22 (Stage 2). Suppose that Induction Hypothesis D.1 1 is true throughout Stage 2. Then T2 - Ti < O(d3/s)
Proof of Lemma D.20. Since it is the norm of V Vwy 22 we can safely ignore the last entry and only consider the first three entries. By Lemma D.7, we have
F(x:
11 +0 d?!!2)
W2 |0 log(d)) 1):
a log(d)
V ww..bra Ww..b..w.11 =E x (f((x) f(x))
+0
120g (w) . x))
41

---

Published as a conference paper at ICLR 2023
Furthermore, we have
= E ((f((())))))))) (am0))f((x))))) f()))a) |+||] + (() f()))a(F(() ||=-1))
= (1f((()) - f()))a ||||| + 0 (ad{.1²)
Meanwhile, for (V by 13. by Lemma B.3 and Lemma D.8, we have
2x0 E (()((z) - f()))o((u) =²)
20 E { (J-((t) - f( - æ)} + 2 E { (f((x) - ((x)))o(2))-- -2) 20)
x
2Cr
E (ff.(z)) - f(x)) | ||m,
+ 2003 ||0|| || / 5111=
E xxxx
1|x/11
Vd x
V
WCr
E (J=(a)) f(x)) | ||0, || + O
[Miiz] 1.5 0.5 ||20|| || (,1.2)
Va
Repeat the above procedure and we can replace the f in the first term with f. Therefore,
< ||
V Wwy.bg,u0 b 11:3
E
(f(()))(()))
2Cr 1iz va
||a=||
loo((d
0
1,12
8(2)
0
- 0
&
d
1
[0>2
1.5
0.5
||w1|]
Wi ||20 || log(d)
a ||<=|| 1
-((x)) E (fx(z)
2Cr
||
w
vd
+ +0 (699 + )
a log d)
| || (og(d)]
Now, we estimate the the expected norm of [V Vws,b,,wn 1133 First, we have
(z) - f()) [[=]) 2 a² ===0((0))) + d6(7)) a² log(d))
[V Wan wn I7 =
(x) - ((())) + 0 (12) + doo
V u2 b2 w L
For [V w2 b2 13, we have
4CR
E V
12 by wy
12
E (f.(()) f(x)) ||
E wm 1|?
d
0
(687)) + d3 d3)(00)
E w
log(d))
Vd
40rw3
E (x) - f((x)) ||=)))
a
vd
O (( (607)) + )b wza log(d))
Thus,
E (() - f(x)) |m]1]] 2 a² 4Cpw3 ) + E (f=(() - r(2)))²
[[ wy ww 11s11
vd
= 00((5)) (011)) dz (999 d²)
= || 2 0 ( (5(2) + 2s a*))
42

---

Published as a conference paper at ICLR 2023
Proof of Lemma D.21. For notational simplicity, put A = Va²+ 1Cr va
wza. Then we can write
V (f((z) - f(x)) [A ||/1
E x
(f((x)))(x)))
Define
4 -11 - 0022
A(1 - -2))
By Induction Hypothesis D.I, 4 - (()) Hence, in order to lower bound A
it suffices to
lower bound V, V
We have
V = AE ((f((a) f(x)) (- |||||||| + - (av02 |||||| + b2)) }.
First, for those x E { {||=||| - 1}. we have fx)) = |||||| + and
f(x) = ر, F + by u2a | + 62 +
||=+|).
Hence, we have
|||| ((f f(x)) (- ||=||| +1 (ari2 ||=||| + b2))
| {(f((x) - f(x))) | [(f((x) - (z)))za((((()) - |x]1)}
|| {(f-(x)) - -(x))) = 0 [ 1,62)
Then, for {||>|| 2 1}. note that | 1 S and fx(x) Therefore, we have
E
{(f((z) - fxx) (-||=| + (ا:ل || |ا||| + b2))}
||
E
[f(z) (-||a] + (aw || > b2)) 2
E 21
(f(z) ||>||| + b2)}
a 21
Then, we compute
E {f(2) ||>||| + bb)}
|
E
{f(x) F(x) + b2)} + |
( - F(x))))
|
E |
(z)))
(z)
0
(x²) + (
where the second equality comes from Lemma D.7 and Induction Hypothesis D.I. Combine these two cases together and we obtain
V
V AE (() fz))) o (Iw2a1112) (,2) 0 (dxx
Finally, note that A 2 a. Thus,
I(aL) - o (5(2) d A
Proof of Lemma D.22. By Lemma D.20 and Lemma D.21,
d L < -Q((2 + +0 ((11)) 1.12 + ( d²) 5 S
L2
dt
/3
Thus, for any T' [T]TT]]
-1
C(T) < (d-
0
C(Ti)
T T-T
Thus, takes most OdP/e) amount of time for L to reach e.
43

---

Published as a conference paper at ICLR 2023
D.4 PROOF OF THE MAIN LEMMA
Proof of Lemma D.2. The Induction Hypothesis maintained in Section D.2 and by Lemma D.22, have T2 - Ti ((d%e)) Now consider the first layer errors. Recall that
(6 = 0
d &
(xx2)
2
1,12
dt 1
d [2))
0
d (20 dd
(2) 2
X2
Recall that ōx, (()dddd.30 (6 (61, dd d8))))) For simplicity, we choose 1, 2 d'8 so that
8x, 0 -,,00 Then, we have
66 (1,12) 0
di
(2) 0 1.12 + d (01,1=)))
dt
We choose [1.11= (Ti) and 01 (Ti) such that
1
+
S 1,12
(22) S +
do (1.1m and 1,2 (Ti) θ E
)1
(14)
Note that this is possible because 1.12 mially small. When this is true, we have
((2) (Ti and 6(2) (Ti) can be chosen to be arbitrarily polyno-
( 1.12
(3 (1)))))) and dt
d
=0
00 5(2) d3
1.
i,L-)
Thus, by induction, within Old*/s) amount of time, these two errors can at most ( (Ti)) and 1,19
( (Ti)). respectively.
E
FROM GRADIENT FLOW TO GRADIENT DESCENT
Converting the above gradient flow argument to a gradient descent one can be done in a standard one, provided that small step size, one can make sure within each step, the difference between gradient descent and gradient flow is inverse polynomially small. Note that our argument is built upon the induction hypotheses. Hence, we do not need to worry about the accumulation of errors. Moreover, our estimations can tolerate an inverse polynomially large error. Then, at each step of gradient descent, generate sufficiently (but still polynomially) many samples to ensure that with high probability, difference between the population gradient the finite-sample gradient is sufficiently small. Since it only takes polynomial iterations to finish the process, the total amount of samples needed is polynomial.
generate fresh samples at each iteration. First, by choosing sufficiently
44


Reviews:
[{"review_id": "vJYbdggbctU", "reviewer": "Reviewer_i3qA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the problem of learning the target function $f(x) = \\rm{relu}(1+||x||)$ under the following setting:\n\n- *Data*: Data is sampled from a specific distribution $x\\sim\\mathcal{D}$ (see Section 2, \"*Target Function and Input Distribution*\")\n- *Model*: A three layer neural-network with low-rank second layer weights.\n- *Algorithm*: Clipped gradient flow on the population mean-squared error, with small random initialisation.\n\nDespite specific, the interest in the target (and data distribution) above lies on a recent depth separation result by [Safran et al. '19] showing that it requires *at least* three-layers to be approximated with polynomially many neurons. The key theoretical result in this work is to show that indeed it can be learned algorithmically, i.e. the low-rank architecture converges to the target under clipped gradient flow from random initialisation in polynomial time.\n\nOn a technical note, the proof strategy introduces a mean-field approximation for multi-layer neural nets with low-rank middle layers which can be of independent interest.\n", "summary_of_the_review": "This work studies the relevant problem of depth separation in neural networks. Despite considering a specific setting, it provides interesting results on the convergence of gradient flow for overparametrised three-layer neural networks in polynomial time. This sort of result is scarce in the theoretical literature. Therefore, I believe it is a submission of interest to the ICLR community.  \n", "strength_and_weaknesses": "**Strengths**:\n- [+] Algorithmic separation and convergence rates results for neural-nets are scarce. Therefore, even if the setting is specific this is a very interesting result.\n- [+] The paper is well-written and easy to follow, even for a non-expert reader. In particular, the authors make an effort to intuitively explain every step in the proof, which is helpful.\n- [+] The extension of the mean-field limit to deeper (although low-rank) architectures can be of independent interest to the community.\n\n**Weaknesses**\n- [-] The proof is cumbersome, and despite the effort highlighted above, one sometimes get lost in the big scheme. It would be useful to have a bullet list in Section 2 summarising the key steps and pointers to the Lemmas / Theorems establishing them, e.g. \"First, we show that for spherical symmetry of initialisation is preserved by the first layer measure throughout the infinite-width dynamics\", etc.\n- [-] It is not so clear which of the assumptions needed for the result are crucial for the result to hold and which are not. e.g. what is the role of the cumbersome distribution of inputs?\n- [-] The setting is quite specific. However, as highlighted above I think this is a minor point.\n\n**Questions**:\n\n- **[Q1]**: The data distribution seems to play an important role in the theoretical analysis. Aside from the technical proof, would changing the distribution (e.g. $x\\sim\\mathcal{N}(0,I_{d})$ or spherical) completely change the phenomenology?\n- **[Q2]**: The separation of scales $T_{1}, T_{2}, T_{3}$ in the dynamics is an important element in the proof. If I understood correctly, these scales are independent of the hidden-layer widths $m_{1}, m_{2}$,and only scale with input dimension $d$. Can the authors clarify this scaling more explicitly?\n- **[Q3]**: Overparametrisation plays an important role in the proof. However, as noted by the authors in the discussion below eq. (1) a single second-layer neuron suffices to learn the target. Aside from the technical details of the theorem, can the authors comment on why overpamatrisation is benign to the optimisation in this setting?\n- **[Q4]**: If I understand it correctly, the initialisation of the first layer weights on the sphere is important to establish spherical symmetry of the first layer measure throughout the dynamics. Is this condition stable? For instance, would a small angular fluctuation (e.g. Gaussian initialisation) drives the dynamics away from the radial direction?\n\n**Comments**:\n\n- **[C1]**: I find Fig. 1 cryptic. First, the font size is very small and one needs to zoom a lot the pdf to read them. Second, the specific details of what is being plotted is not given. For instance: what are the red dashed vertical lines in Fig. 2 (left)? What is the input dimension $d$ in this simulation (this is quite relevant, since the authors claim convergence is polynomial in $d$)? Are these finite network simulations (if yes, what is $m_1$ and $m_2$?) or theoretical, infinite-width curves?\n\n- **[C2]**: In page 6, first equation $\\bar{v}$ is not defined explicitly.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "l_P7IRnSB6", "reviewer": "Reviewer_5SVU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the benefits of Depth in neural networks with an emphasis on algorithmic separations. \n\nTypically, previous works have focused on proving depth separations by proving the existence of certain functions that on the one hand, can be easily approximated with a depth 3 neural net, yet cannot be approximated well by any depth-2 network. The paper here asks can we prove the analogous statement but with a learnable deep network. \n\nThe main result relies on previous work using a radially symmetric function (i.e., one that depends on the norm $||x||$ of the input) and importantly show how to train and converge to a network that provably approximates the function at hand. This requires several technical extensions of prior works to multilayer mean-field networks. The network studied is overparameterized and has polynomially many neurons. One interesting aspect of the analysis is to decompose the loss into the discretization loss (going from infinite width to fixed width) and the approximation error (w.r.t. to the hypothses classes and the function to be approximated).", "summary_of_the_review": "The paper is a solid contribution to the theory of approximation/expressivity of neural nets. Many prior works have studied the depth separation question from an existential point of view, and this work shows that for some simple case (namely the radial function $||x||$), the result was indeed algorithmic. But to do so several technical obstacles are overcome in terms of the optimization process.", "strength_and_weaknesses": "Strengths:\n+ nice technique that extends previous techniques based on mean field analysis of 1 layer.\n+ proving that one can train a network to find the hard-to-represent-by-shallow-nets function is itself a clean and nice result.\n+ it's interesting that his paper studies training of both the layers. Training dynamics for one layer while keeping the previous fixed, were studied but this paper deviates.\n+ perhaps the idea of truncating the mean field analysis, studying the introduced discretization error could be useful for future problems.\n\nWeaknesses:\n- the architecture itself is somewhat simple as the intermediate layer has dimension only 1. This suffices for learning the norm function, but it's not clear how crucial it is for the analysis. Would the analysis be able to be carried out for internal dimension d? What would the dependencies on d be?\n-Some omissions in the literature and how the paper compares to them: \n\n-What happens in the case where depth is not 3, but rather a parameter D and we want to learn a \"simple\" function? Telgarsky's paper on \"Benefits of depth in neural networks\" provides similar separation in the \"deep regime\" based on an admittedly very simple function, namely the triangle wave f(x)=2x for x in [0,0.5] and f(x) = 2(1-x) for x in [0.5,1]. \nCould your result somehow be made algorithmic even in the case of learning compositions of the triangle wave? \nMore generally, Chatziafratis et al. in \"Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem\" generalized Telgarsky's construction based on periodic 3 functions. Could this also be made algorithmic?\n\n-The authors should compare or at least mention connections to computational complexity and neural networks based on the work of Vardi, Shamir in \"Neural Networks with Small Weights and Depth-Separation Barriers\", where showing separations beyond depth 4 is connected to some basic questions in complexity.\n\n- The authors should also mention \"Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations\" by Awasthi et al. since they study the very related question on learning a ReLU net. Are the techniques used there similar to the ones in your paper?  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cwHLNt1NTS", "reviewer": "Reviewer_wTzk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In (Safran et al. 2019), the authors describe a function which is $ReLU(1-\\lVert x\\rVert)$, which can be well approximated by a depth 3-network, while a depth 2-network requires $\\Omega(\\exp(d\\log d))$ width for the same. In this paper the authors show that, this separation is also, algorithmic, in the sense that one can learn the hard function $ReLU(1-\\lVert x\\rVert)$ using a depth 3-network in time polynomial in $(d, 1/\\varepsilon)$ using mean-field dynamics and an appropriate discretization scheme. ", "summary_of_the_review": "Overall, even though it is tied to learning a specific hard function, I think the techniques could be useful to understand optimization with deeper architectures. So I feel it might be of interest to the DL theory community.", "strength_and_weaknesses": "Strengths:\nPrior work by (Safran and Lee 2021), train GD on a depth 3-network, but for different activation functions other than the standard ReLU and their first layer-weights are fixed throughout the training. In this work, the authors use a splitting technique to deal with moving weights and also to ensure permutation invariance of the distribution of neurons. \nAfter initialization of the weights and under the infinite width regime they obtain a distribution over the weights, which is spherically symmetric and then they are able to show under an appropriate discretization scheme, they can transfer the results to a finite polynomial width network.  I think it is one of the few results that show polytime learnability with depth 3 network, albeit on a specific instance. Potentially some of the techniques could be of interest to the community.\n\nWeaknesses:\n1) As this a depth separation result, even though they train a deep network, the methods are more or less, specific to the particular function. Can the authors comment on whether there is a larger class of functions and input distributions such that a depth 3-network can learn in polytime?\n2) The equations in (4) describe the dynamics, please indicate what is $\\bar{v}_1$. One of the concerns is the assumption on the spherical symmetry of the distributions, which is satisfied in the beginning, but could the authors please clarify why it continues to be satisfied as the dynamics changes the weights? Does this always ensure that the assumption is valid and also when you discretize and deal with the finite width regime?\n3) Can the authors comment about dealing with polynomially many samples from the input distribution? Does one run standard GD, with gradient clipping in this case?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "SVnI_bsynt-", "reviewer": "Reviewer_JRVm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes the gradient flow learning of a particular mean-field (MF) network with more than 2 layers and shows that it can learn a radial target function (and a specific data distribution) with width polynomial in the data dimension $d$. This target function was previously shown to be inapproximable by 2-layer networks whose widths are $poly(d)$.", "summary_of_the_review": "The paper presents an interesting and encouraging result, though there are several downsides, including a somewhat restricted problem setting, the MF network idea being already known, several unnatural design choices of the neural net that already reveal quite a lot about the desired target function before learning takes place, and the questionable necessity of the proposed multilayer MF network.\n", "strength_and_weaknesses": "\nThe result of the paper constitutes an interesting example where it shows the algorithmic advantage of a deep network against a shallow network. Global convergence results in the MF literature typically show (multilayer) neural nets can learn a certain generic class of target function or distribution, often without a rate and without an explicit comparison against shallower models. Here the paper focuses on a very specific setting and pulls through the main technical hurdle, which is to show the convergence time $T = poly(d)$ while avoiding the typical Gronwall’s inequality bound on the width whose dependency is exponential in time, hence achieving a $poly(d)$ width guarantee. Though I haven’t read the proof carefully, I quite like the analysis that takes a keener look at the role of the gradient flow in Lemma D.12 and D.14, which in particular helps keep the bound on $\\frac{d}{dt}(\\delta_{1,L_2}^{(2)})^2$ on the smaller, useful order (i.e. $\\frac{d}{dt}(\\delta_{1,L_2}^{(2)})^2 \\ll \\delta_{1,L_2}^{(2)}(\\delta_{1,L_\\infty}^{(2)})^2$ instead of $\\frac{d}{dt}(\\delta_{1,L_2}^{(2)})^2 \\ll \\delta_{1,L_2}^{(2)}\\delta_{1,L_\\infty}^{(2)}$, which would have been bad).\n\nThere are a few items that should warrant attention:\n\n- The type of MF networks proposed by the paper is actually a known idea. It is basically a concatenation of multiple 2-layer MF networks. Similar ideas exist, for example, MF Resnets in a paper by Jianfeng Lu, Lexing Ying and coauthors, which is one of the cited references. As far as I know, the same proposal was discussed at least in one talk by Eric Vanden-Eijnden.\n\n- There are several important parameters that have been chosen so as to “hint” the learning at the desired solution. These choices could be unnatural. In particular, the initialization of $w_2$ is chosen to be very small and basically close to 0. As a result, this hints the network to learn an atomic solution. The initialization of $w_1$ (given by $\\sigma_1 = 1/\\sqrt{d}$ in Lemma C.1) and the unnatural architecture $F(x) = \\vert w \\vert \\sigma(w\\cdot x)$ again hint directly at the solution, as $\\bar{F}(x; t=0) = \\vert x \\vert$. Due to the small initial $w_2$, in the first stage, $w_1$ has almost no movement. Hence in the first stage, the network $F(x)$ stays “at the right place”, which is necessary for it to stay again at the right place in the second stage, as shown on page 43. \n\n  Zooming out, one can see that with the choice of parameters, most things are already at their right places from the beginning (the first layer $\\bar{F}$, the spread of $w_2$). Perhaps the only thing that has large movement through the learning is $\\bar{w}_2$, which is a scalar and does not quite convey the necessity of MF infinite-width networks. The same can be said about the bias term.\n\n- A more critical point is whether the proposed MF network is really important to establishing the result. The proof actually suggests that if the second width $m_2=1$, the result can be readily proven — perhaps with less technical work. That is, it is not necessary that one has $m_2\\to\\infty$. However when $m_2=1$, the “MF” part of the network would then be just a 2-layer MF network, not a multilayer one.\n\n  One may say it is more natural to consider large $m_2$ than $m_2=1$. But we should also recall the aforementioned design choices that hint at the desired solution. With these design choices, the consideration of large $m_2$ seems to demand heavier technical work and yet does not reveal insights on whether or why a large width is necessary.\n\n- The paper also advertises that the proposed MF network factors out neuron-permutation invariance due to the use of the distributions $\\mu_1$ and $\\mu_2$ in the representation, but the analysis does not make use of the representations $\\mu_1$ and $\\mu_2$. This is quite unlike the 2-layer MF literature, where the movement of the neuron distribution $\\mu$ is described by a Wasserstein gradient flow and where the analysis makes use of this fact.\n\n  More generally a typical MF framework goes by passing from the large-width MF network to the MF (infinite-width) limit and then using this MF limit as an analytical object. The advantage of this framework is that it removes the width out of the analysis and thus allows to exploit certain properties that only exist in the infinite-width limit. The paper does not follow this approach: it does not identify the MF limit and it analyzes directly the large-width MF network. Furthermore the analysis looks rather restricted to the particular problem setup under consideration. As such, at the time it is hard to judge whether this type of analysis can be expanded into a proper framework.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LY2BxoDMdT1", "reviewer": "Reviewer_Lcb7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "\nThe paper uses a mean field type analysis on non shallow networks. The work is motivated by a result of Safran, Eldan, and Shamir (2019) which shows that shallow networks cannot capture sufficiently complex functions. The main result guarantees the learning of the function Relu(1-||x||^2), by a neural network with several multiple hidden layers with a polynomial number of units in each layer (which is a novelty)\n", "summary_of_the_review": "\n\n- On page 2, last paragraph, the sentence “Restricting the intermediate layer to have only one dimension ” is not very clear. What you do is your restrict the connections between the first and second layer  \n- In Theorem 1, I would recall the definition of the main parameters. This would clearly improve readability (Let d denote the input dimension, …). Also, what do you mean exactly by poly(d, 1/eps)?\n- It would also be good to recall that gradient flow is an intractable algorithm in practice as it optimizes in the space of measure (which is infinite dimensional)\n- On page 4, when you introduce the distribution related to phi(x), it is not clear whether the impossibility to approximate f_* is related to the distribution or not. \n- Which loss are you using between (2) and (3) ? I would use distinct notations\n- In your main theorem, when you say gradient flow, you mean a flow algorithm on a polynomial number of particles, right? I think it would improve readability to say it that way or to add that somewhere. \n- page 6 first paragraph. what do you mean by “the change in norm is also uniform ”\n- your defintions of mu_1 and mu_2 are sometimes ambiguous. From what I understand, by mu_1 and mu_2 (at least when you derive the polynomial width), you mean multi-atomic distributions, don’t you? if so, why not writing the corresponding decomposition mu_1 = sum_{i} alpha_i delta(w - w_i) somewhere?\n- On page 6, when you say that the dynamics of the first layer reduces to alpha, from what I understand, it is because you can initialize v1 to a given (let us say random) vector and then derive the update from the update on alpha ? I think you should expand a little more on this. E.g. provide one iteration, v_1 = v_1 + eta* d\\alpha/dt * (1/alpha)* v_1\n\n- On page 6, it took me some time, to get the flow on alpha and I think (although everything is sound) it would be good for the (general) reader  to recall the meaning of \\cdot{alpha} here. I.e. the fact that \\cdot{\\alpha} denotes the variation of alpha through the gradient iterations. Perphaps you could add something like alpha(t+eta) = \\alpha(t)+ eta d alpha/dw_1  * dw_1/dt and recall that dw_1/dt is the evolution of w_1 throughout the gradient iterations. I.e. indicate that dw_1/dt is computed as w_1(t+eta) = w_1(t) + eta* dL/dw_1\n- It would be good to clarify the notation E_x (Given that you have other averages with respect to the distribubtions mu_i and you sometimes use \\mathbb{E} without subscript). Perhaps add a line somewhere such as E_x \\left\\{ f(x)\\right\\} = \\int_{-\\infty}^{\\infty} f(x)\\; dx\n- On page 7, when you discuss the vanishing of the gradients, it would be easier for the reader to recall the definitions of f and F   \n- On page 7, the sentence “As a result, when f decreases sufficiently fast, f will become 0 before ∥x∥ becomes large” is unclear.\n- On page 7, when you introduce the times T_{1,1}, T_{1,2} and T_{1,3}, those times are critical to the analysis, I’m wondering if they should not be introduced as a list. Moreover, just before the statement of lemma 4.2, when you introduce the T_{1,i}, I would emphasize that the projectors are not needed anymore after T_{1,1}. At the end of the day this is the point of the section. \n\nMy general comments for lemma 4.2. are the following: The statement of the lemma is perfect for a journal but there are too many details for conference proceedings. I would make it even more informal and simply say something like the first phase of the optimisation is characterized by small changes in alpha and (v_2, r_2) (including small changes in the mean \\overline{w}_2 and spread \\|v_2 - v_2’\\| across the layer). Then if you really want you can give the estimates on \\overline{w}_2, r_2 and alpha but you should explain why those are important. \n\n- In lemma 4.2., is \\overline{v}_1 the same as \\mathbb{E} w_1 ?\n- In lemma 4.2., how do you control the variance \\mathbb{E}\\|w_1\\|^2 ?\n- In lemma 4.2. “spread of the second layer” and “regularity condition”, when you say for all (v_2, r_2) \\in \\mu_2, I guess you mean for all (v_2, r_2) \\in \\supp(\\mu_2) \n\n- On page 7, if I understand well, T_{1,1} is the stage where you still need the projectors ? if so I would indicate it. \n- In the statement of Lemma 4.1 I would recall the meaning of R_{v_1}, R_{v_2} and R_{r_2}.\n- On page 7, you use ‘f(x)sigma’(v_2 F(x) + r_2) \\approx f(x) ‘ is that because d/dx relu(x) =1 on the positive x ? if so then what does the approximation mean?\n- On page 7, “Since f is much flatter than f∗ , the RHS is always negative” ? What does that even mean? I don’t understand why the flatness of f_* vs f implies that f_* - f will be negative?\n- In fact at the end of p7 you say “In fact, we show that it is −Θ(α log d) = −Θ(logd/d1.5) “ Where do you show this ?\n- “One also needs to show that δ2 cannot change much during Stages 1.1 and 1.2.” —> Why ?\n- I would recommend changing the sentence “the dynamics of v2 is approximately uniform in Stage 1.1 and Stage 1.2, and δ2 does not change much” to the distance between successive iterates (v_2’, r_2’) and (v_2, r_2) does not change much\n- At the beginning of page 8, the sentence “Recall that stages 1.1. and 1.2. only requires” —> “recall that T_13” corresponds to the time at which |w_2| = Theta(d)\\delta_2\n- “We can make σ2 small by selecting a small enough σ2” the sentence does not make sense. I would replace by something like “Recall that sigma_2 refers to the variance of the Gaussian distribution used to initialize w_1, by taking this parameter small enough, we can guarantee that the initial value of w_1 will be small enough which can in turn be used to control the deviation between the iterates” or even better “the deviation between the iterates in v_1 and r_2 depend on the value of sigma_2 (which is used to initialize the weights w_1 and which can be taken sufficiently small to control this distance)”\n- I don’t see why the fact that “v_2” has a uniform dynamics (i.e. the successive gradient steps are approximately constant) implies that delta_2 will be small. This implies delta_2 will be approximately constant but not necessarily small. I might be missing something here\n\t\n- I think the paragraph at the end of page 7 and beginning of page 8 should be rewritten or removed. You are trying to explain a proof which you can’t expand and that makes the paper unclear. Honestly I think the best would be to remove this and replace your statement of lemma 4.2 with something very informal\n\n\nPage 8\n\n- on page 8, it is not clear to me why \\overline{w}_2 does not depend on \\delta_2\n- on page 8, I guess when you say “the length of Stage 1.1 and Stage 1.2 is proportional to \\delta_2” what you mean is the total variation in the weights? if so it might be helpful for the reader to specify which weights\n- Generally speaking the part where you explain lemma 4.2. is not clear  \n- When you explain how you control the \n- In the last paragraph of page 8, perhaps you could recall the definition of \\tilde{f} ?\n\n===================================\n\nAdditional typos:\n\n===================================\n\n\n- page 2, end of paragraph 2: “has also been in used” —> “has not been used” or “”has not been in use” (although the second is less correct)\n- page 7, “Stages 1.1 and 1.2 only requires” —> “only require”\n- page 8, beginning of the page : “if δ2 remain relatively constant” —> “if delta_2 remainS constant”\n\n\n", "strength_and_weaknesses": "The paper is well written and is definitely interesting. My main concern is with (1) the relatively restrictive nature of the architecture and training machinery considered. The authors essentially focus on an example from Safran, Eldan, and Shamir (2019)  (which shows that shallow networks are limited in their expressive power and will fail to learn sufficiently complex functions such as Relu(1-||x||^2)) and consider a network that is designed specifically for that example which reduces the applicability of the result. (2) the fact that the readability/impact of the paper would benefit from a longer and more detailed exposition (see my comments below). This is a strong paper, why not submitting it to a journal?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%